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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
离散数学 X 试 卷（作业考核 线上2）  A  卷（共    4    页）
总分        题号        一        二        三        四        五        六        七        八        九        十
        得分                                                                               
. U, I3 v/ c" i# g& L3 X7 G一、 (13分)有两个小题
+ _) z$ t, x+ }) m' Y5 T4 F1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。
/ M- p; d& N1 V, \

6 [' I  C% K: T0 }
7 D" S0 n0 {  O9 O. l
& [( F, I$ t* R7 q
- b: p3 @4 K& L7 Y5 K9 f7 V8 R: w2．分别列出PúQ、PùQ、P«Q、P®Q的真值表(填下表)。
+ d& X1 h6 Q+ h& TP        Q        PúQ        PùQ        P«Q        P®Q
+ c2 @/ z& e& G' \0 R$ Y                                       
/ ?0 `# I; b" ]                                       
3 R7 `/ n* m" Z7 t3 r" {                                       
6 C6 p& {* Y/ R* U# ]9 Y                                       

二. (10分)写出命题公式 (Q→&#216)→Q 的主合取范式。（要求有解题过程）
8 `/ Q5 _$ O& Q  w* X( Y
$ L3 _, Y; ?' i6 J& i5 t2 M) b" x( B

8 K3 v  l! V& x3 |5 b


( P% s4 T4 y$ @3 N3 @4 H7 P6 o: V8 v

* u, b' l$ z! G9 R) \6 Z


& Q) x6 B" ]  \# l7 o2 I0 N1 [

4 Q$ M( _; F" }
- L+ _9 {1 c2 d* x- l8 Z$ ^$ s



+ {% R0 ]) O: n( X0 p三、(14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。   
  xC(x), x(A(x)B(x)), x(B(x)C(x))  xA(x)


2 I/ K% A+ y8 j  n- |, s
2 B/ J* ^1 l, f" p; q1 q4 a



6 B. s) H5 U& Y. x  b

四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
  （注意：要求有计算过程，不能直接写出结果！）
& H& A) p: l/ m2 @. i7 f  H- }2 j  Z(1)  A×P(B)
(2)  A⊕B
(3)  P(A)－P(B)
) }* `9 O$ t7 ?$ g" u
: Y, Y8 ^0 t- N9 E0 B! E  L
: Y: }/ e) R! o; b6 B0 k

9 v4 {5 L- o, `5 J5 e
  |( n+ H9 i9 E5 V' V2 b$ `

1 v! |- Y7 s1 {# F7 E/ t/ H% l
  W- s) k8 H' q4 Y  v9 w9 Y
! t# K  o2 L( u  K# j8 g. j

; u. f$ ?9 O1 I2 @: v3 P4 q; P
五. (25分)给定集合A={1,2,3},定义A上的关系如下：
R={<1,2>,<2,3>,<3,1>}
S=A×A(完全关系（全域关系）)
T={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
' p) n5 y# w; ^* t1.写出关系R的矩阵；再画出上述各个关系的有向图。
2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
        自反的        反自反的        对称的        反对称的        传递的
. M, K6 d* q# B4 \0 xR                                       
' o6 ~% P! d+ k  KS                                       
T                                       
4 X- H* [( N* @; n0 ^+ d6 v  J6 LM                                       
3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
" G/ l( F& i  \" a- F2 n对等价关系，写出此等价关系的各个等价类。
2 ^7 d* T8 m6 H4.求复合关系RoT


* ~+ ?- Y/ {1 F% r/ m


" u) m3 G; Q! V; N- j# c% I" o6 y
& V3 C! R6 b! v

5 c. G  i; X9 N. W* m- a


2 b9 B$ K8 z* b( E
8 c2 O: D! E, t& P$ i. D* t

六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
3 _  `) H' P, N! O5 ]4 ~1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
, P5 |7 V) [& T" E: b6 t5 W填下表：
        |x-y|        max         ×        min        +
0 V% v) N% T9 g+ m' m& u1 v0 v有交换性                                       
) ]) @5 f4 a: T/ W有结合性                                       
$ O% A! p" ?  L$ @  b  `1 U有幂等性                                       
/ K' k# E7 c4 t$ `0 n有幺元                                       
) O+ x3 v0 ?, S$ Y有零元                                       
2.指出R对上面哪些运算构成群？.

$ J" J7 _' @8 \5 A0 i4 j* v$ R' @

( ~! |* v! l: {- B$ {
" O- ~3 I5 K* u4 e3 A& L
) Y$ v0 l& y, }. r' F
' H9 q+ f, R: M- e4 E$ d; V8 U
4 |3 b. L2 P) L3 T3 N- r
0 G; s1 m+ S. h5 g7 i8 \
7 w3 o0 S0 K% K) D9 p" c: J


* B8 W0 h5 t/ _6 a* Q# X. E


+ e' b* Z3 i! W6 w) W* o3 }  G

! o/ _" p9 Y1 K. B$ X( L
; A3 @# E2 ?: `
# P& t% E1 [/ \6 q* ?: ]

七. (14分) 有三个小题
2 N0 W8 p- V; v9 W. [' w% R( m   1. 指出下面各个图中哪些是彼此同构的.
+ o- p* c9 C5 l* i
& F3 k; ?7 Z" g2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
3.请画出五个具有五个结点的无向图，使之分别满足：
    (1) 是欧拉图但不是汉密尔顿图。
9 P: {7 B$ s6 Y+ B    (2) 既是欧拉图也是汉密尔顿图。
, Q6 L9 Z1 u6 S* c1 N    (3) 是完全图K5。
6 J4 v' n2 l8 @" w(4) 是棵树。
(5) 是汉密尔顿图但不是欧拉图 。  

6 t5 ]; j# F8 H* a

7 l: U, W5 ~5 p9 [, Y7 ]

- \# s% c. M. e) F3 w1 h. R





, Q8 D7 K, T# [' U; `/ \5 O! x, |



  u4 Q) |/ ?! n3 L" W" E) |
4 {( {! ]( V& d' e
/ H# i. ?+ H0 Z- h

3 V2 K* @: W% A2 k# c
3 Y1 I( h+ m2 [


# f  E& |/ V2 T9 d' z

2 w! x3 G! Z' r; c1 M( a