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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
5 k+ k3 g- G4 U9 Y8 y 离散数学 X 试 卷（作业考核 线上2）  A  卷（共    4    页）
( C$ E# J4 G( V0 u5 ^总分        题号        一        二        三        四        五        六        七        八        九        十
3 F" C$ e* V- y        得分                                                                               
8 G  w1 T! Q/ b+ a) S) U/ z一、 (13分)有两个小题
8 M& y9 S2 j* B1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。
4 f! e( {/ J2 t5 g+ V& @6 ]9 h
2 w/ H" _  E! @# |& I4 I: D
9 l  @! F- l/ D, C+ m

& f& y* v1 w( k" S: Y7 Z

' c5 E9 Y/ d8 p1 A8 ?4 u8 G
$ D/ h1 Q5 O; b8 b& U2．分别列出PQ、PQ、PQ、PQ的真值表(填下表)。
P        Q        PQ        PQ        PQ        PQ
                                       
                                       
2 Y& X- Y( \  Q# B1 q                                       
5 [# V1 o0 B( u$ Z* C                                       

$ }6 q# Y$ P" P* E; V


二、 (10分)写出命题公式 (Q→&#61656)→Q 的主合取范式。（要求有解题过程）
8 o4 [9 j+ u- g% |+ K, [- g

. f4 H% B1 I" ~& `6 g. M. L
1 Z. V5 M( o  @( V8 i& B
. T: {- L0 c2 E5 _5 d
; ], D' O! }" B# P/ H  U9 \

: G0 v  G1 y. V. y( q3 _4 O
5 f" D' ~7 s  q! ?, E# [
; }+ _# D$ v* Y# F3 R
& o# b' J! Y4 H2 T. x
* }# A% Z& e0 p8 [" J

三、(14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。   
2 f8 H' U& Q# O3 y6 O- s" r2 u  xC(x), x(A(x)B(x)), x(B(x)C(x))  xA(x)
) V* f5 {/ J7 i$ O1 S0 B- ]
1 @" B) \) o& H+ x# o& d

+ ?: F% {* I/ Y$ V5 ?
; x4 `; M; ^4 e( x; h

) [$ o2 H0 N$ J/ T5 Y% M7 E  K
1 y# ^8 t) y: Y4 J

7 W$ W7 o  Z9 s5 ]0 s+ t$ h四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
2 I, {1 ^4 c  W  X  （注意：要求有计算过程，不能直接写出结果！）
3 T0 ^. t. o6 N1 s(1)  A×P(B)
# I' p0 a4 E% T) V4 ~3 E4 ^* J3 T(2)  A⊕B
(3)  P(A)－P(B)
' [& e' k: o" ~* h6 }
- E& F6 g$ F) ~9 |' H6 [
' O" u7 V/ R% v
+ h% J. z2 B9 ?* ^7 d  G* _

' W' S) x9 K1 I( N" i
/ G. k$ L; ~" h7 a2 Q+ ]+ ~

* a/ P) @! q4 v; {; j) ~2 j  _
1 v. T; d7 k) ?- C/ f7 ?) r

; r/ f! ^0 j* O$ m! ^
五. (25分)给定集合A={1,2,3},定义A上的关系如下：
R={<1,2>,<2,3>,<3,1>}
S=A×A(完全关系（全域关系）)
, I& O3 Z7 ~8 }  b: h- }2 gT={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
2 s9 y" a2 O7 Q4 c1.写出关系R的矩阵；再画出上述各个关系的有向图。
2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
6 @0 Z2 O2 x8 V$ `        自反的        反自反的        对称的        反对称的        传递的
R                                       
S                                       
- K; r3 @: [; ?T                                       
M                                       
  w7 A" A) V9 n; _5 B/ M3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
3 @; E; m# i& G对等价关系，写出此等价关系的各个等价类。
9 d1 r$ l! X4 D2 I5 l+ H4.求复合关系RoT
3 x. p9 X5 `. a4 F
; i$ h) t8 f5 q6 B7 l, ]
8 s5 E& q! C0 Y7 ~



1 E9 a& I+ y' _
$ c3 V2 P; z) E% O! `






六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
$ D& X" ~1 Y' ?/ d8 Q6 Z填下表：
  ~' v! _. W5 F( q        |x-y|        max         ×        min        +
有交换性                                       
有结合性                                       
7 E% r' G# [/ B有幂等性                                       
9 K6 s) M9 i9 v5 H5 B有幺元                                       
0 _" c1 `+ |' {0 D/ X, }# ^: P有零元                                       
2.指出R对上面哪些运算构成群？.

6 t. B! R- U. f& b- ~
! [1 [1 O' S' h5 \) V# s3 S
( b+ c% e6 D; @
  u* A  y* `  O( S




1 ~9 ^1 C/ k: ]8 R
/ U  ]6 ?- D% g
. y1 L: n7 }- I! z



6 I3 q& X) Z" i3 T; b
0 Q; p+ l) \$ F) _- ?' O6 u2 W

, n; H6 ?' I4 n- Z4 ~1 {
! u: [6 Q( c  q" S% f, r/ V
4 R( b; Y# w  g& w
七. (14分) 有三个小题
! o. |- G& _2 o: P   1. 指出下面各个图中哪些是彼此同构的.

2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
3.请画出五个具有五个结点的无向图，使之分别满足：
    (1) 是欧拉图但不是汉密尔顿图。
    (2) 既是欧拉图也是汉密尔顿图。
    (3) 是完全图K5。
. S9 D/ l) t9 T/ b( Z+ E$ i(4) 是棵树。
0 g( a: }- S& ]( U(5) 是汉密尔顿图但不是欧拉图 。  

# K& }3 b  w$ X4 b) Z! ?
" b( U5 R1 J" R
7 r  B: Y0 _$ ]& `5 X9 ^

4 X7 C/ Q4 Q& s; t" t


; m& h3 E+ T5 J+ L
1 b, U' d& Q) r# i


/ C' N- J" q, S5 J' m$ {2 @

3 R6 x3 I9 u6 k( V/ V
6 t. S. R- c/ ], p5 c1 s1 g
5 k# P9 y/ F+ _2 ^1 J


& Z3 a% h2 J3 m( N* t. a" M
- \* m) _7 c/ \  q- d
9 W* X3 m/ h" V- E; w
0 D; C1 m0 K* G3 `& `8 r; i" U5 d
7 W6 ~: ]  m" {5 R" Q  T6 ~
6 D" l3 H2 i3 i. z$ f8 ?0 I
1 ?1 O: e% {# M0 u