[东北大学]21年1月考试《离散数学X》考核作业

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
离散数学 X 试 卷（作业考核 线上2）  A  卷（共    4    页）
; _0 U& D# N+ Z3 B- `总分        题号        一        二        三        四        五        六        七        八        九        十
        得分                                                                               
一、 (13分)有两个小题
8 j& Q. b1 P: b  ^& ~& ?1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。

/ Y4 B) }9 O1 E  z' J$ Z" Y



3 a1 n8 v' }9 t) k
; u# z# U; t( Y3 C5 Z
0 N  q+ s" Q5 r% A. t: z3 a# P2．分别列出PQ、PQ、PQ、PQ的真值表(填下表)。
+ I5 \7 ^" b& {P        Q        PQ        PQ        PQ        PQ
                                       
                                       
                                       
" ]; B2 G7 b7 D: U- W6 Z, W                                       

) q! b0 R, E+ p, f6 [; t

* J! `- N! i3 b8 p
二、 (10分)写出命题公式 (Q→&#61656)→Q 的主合取范式。（要求有解题过程）




, h# r2 j5 i* ?2 l& Z

  I" q( J$ v1 ~  i
5 [' b& Z2 N. Z+ q; a. ]* C4 J8 h



3 a) b" r+ \& A& d7 [5 S0 d3 Z: v
" @' T; H! h! d/ v7 Q: m4 C
- U! o& M5 N8 h三、(14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。   
! q( c7 B5 t/ ?  xC(x), x(A(x)B(x)), x(B(x)C(x))  xA(x)

( @6 n5 Q) ^4 V7 m8 ]# R
/ d4 W; n  s+ L2 c5 N, q! X

5 p: ~) J: e4 V. [
" C0 o& C# H% x: x) M' y, A, u



四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
  （注意：要求有计算过程，不能直接写出结果！）
/ R* d6 R: L' {" l( i; ]% c# y6 Y+ @(1)  A×P(B)
# b. |8 X+ ?" E4 M(2)  A⊕B
: r- p1 S% Z1 ~2 q(3)  P(A)－P(B)


! G) s$ v2 Y; p& s3 D3 D+ a
! I, K/ p9 N: i, w$ l! b6 {7 z' \( F



. ~' a8 q+ ^9 c6 t9 A8 R  G
4 o2 F0 F' C- A  ^. p
6 `0 Q. x- B5 n: S0 R" O
2 R( y: i4 V+ s' v8 c( k
. F; X9 y! r: d3 N1 O
五. (25分)给定集合A={1,2,3},定义A上的关系如下：
0 a5 A6 F* Y! ^! hR={<1,2>,<2,3>,<3,1>}
S=A×A(完全关系（全域关系）)
T={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
5 N* `; M4 M" k% o# A% JM={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
' q6 ^8 o) q$ o8 e4 b1 N0 s1.写出关系R的矩阵；再画出上述各个关系的有向图。
2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
        自反的        反自反的        对称的        反对称的        传递的
R                                       
S                                       
T                                       
M                                       
8 c4 k+ h2 `( C% a  V" m, J3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
对等价关系，写出此等价关系的各个等价类。
4.求复合关系RoT
8 o5 W" g$ L2 D' o
  x; K5 F4 x+ ?; F6 U1 n

+ p( R/ \1 b( ^$ T& g
! e. p7 @) C7 H, i* d/ [8 K8 {


& r: ]2 [8 ?) V5 y- l' C4 [" h: u3 V



% A' B9 _6 B; {

0 T9 [' `# M: y0 S  e: _& w& c3 Y
, W: P5 W$ M% Z! e/ S5 t- M7 X六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
! A, R6 v3 s" F- n. M# Q1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
% h! I$ {* |- }" U* h; b" U" m" m& M; L填下表：
        |x-y|        max         ×        min        +
有交换性                                       
+ s) `& J* ^0 F6 @有结合性                                       
1 h# ?* L' M9 Q2 A; Q有幂等性                                       
9 t! U, h; t' f0 j) @有幺元                                       
: l3 b9 n8 U5 \, h有零元                                       
2.指出R对上面哪些运算构成群？.
/ I$ h2 \, o# j" j% l) Y+ d
5 ^. c1 I7 x7 ?* f7 [- Z

% V, \& C0 W- h7 @7 `1 r  U' ?7 ^
3 n5 C8 ?7 I' r1 U$ D; I- M" q
+ b6 P% N+ e4 @/ o/ j: [6 o4 a4 C
; m; ?+ E8 b" Y0 I: D$ U: R, f
; M. g  o6 Z! E1 [- ?0 e
9 \  v! E" v4 s) _. U
% Y: v3 G5 [+ J. Z
/ u1 O( `: Q2 j3 [/ ~* Y



0 S) L- |' s0 G/ ]' b

* p& u6 c, G0 Z* t2 \: h
4 t& i. H* \+ _
9 X/ |$ J; [& i" i9 @# _+ d
& F9 h4 A" O: f7 p" V

! W& D! |0 t4 N) G' x5 _七. (14分) 有三个小题
   1. 指出下面各个图中哪些是彼此同构的.

2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
3.请画出五个具有五个结点的无向图，使之分别满足：
  _4 a: F/ p4 ]$ F    (1) 是欧拉图但不是汉密尔顿图。
0 |0 B( x' r  q0 j. S    (2) 既是欧拉图也是汉密尔顿图。
5 p# e1 I( h" W5 u1 J; @    (3) 是完全图K5。
9 \( j, r* ?2 o) }' T(4) 是棵树。
(5) 是汉密尔顿图但不是欧拉图 。  
1 v6 H5 ~3 Y; f! C) C# j; s* _) `. K
4 S, Z8 K5 {1 _3 g- |
! n3 D5 |' [3 X8 ~$ N  `


/ \& V' r" x7 G( ~" @1 k* [' l
6 T: e8 B, \* `4 }& M& ~
. I' |/ Y/ Z& a8 x6 G4 t, P
7 f# z9 V" _1 ?8 ]( U% d
: ?& G$ O7 Y9 E' T. n# \0 S


# {1 D7 h. N4 Y" n


$ G5 M& V3 m' _4 c

' Q2 {; e+ r- ~' J2 g/ O# f
8 j6 E) s  h& b2 p; |  I1 c6 H; Z
6 i, q: V% i2 T. m. d7 S



# O) O0 W5 i( o% {

- H1 q- ?# r* \% L