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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
& d2 ^9 d# R' c0 S 离散数学 X 试 卷（作业考核 线上2）  A  卷（共    4    页）
总分        题号        一        二        三        四        五        六        七        八        九        十
2 ~+ Z! n3 p9 Z0 G: e" |/ [        得分                                                                               
一、 (13分)有两个小题
1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。




2 E# Y1 x* j0 |( Y
5 |5 \* A% F$ O( u! E% G9 n

: S- ^0 O8 `  {! Z2．分别列出PQ、PQ、PQ、PQ的真值表(填下表)。
P        Q        PQ        PQ        PQ        PQ
                                       
                                       
4 V" `6 l5 D, P$ V6 S5 p  J# e                                       
                                       
8 O9 U! u3 b! Q3 o3 B7 N: [



二、 (10分)写出命题公式 (Q→&#61656)→Q 的主合取范式。（要求有解题过程）

2 a  g# x1 G1 C# [" r. s9 z$ V. W


; Y* e; E2 E5 M9 {/ m0 ?
0 \8 d. Q: v: W8 X0 [


# Z, R( O; w. y* l7 l  z2 y



; W3 ~! r1 a; f, B% {' V
/ i6 D( @9 b7 H& g; w! {0 m: W" Z三、(14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。   
- k' [% ]! q* m  H  xC(x), x(A(x)B(x)), x(B(x)C(x))  xA(x)



" m* N) j+ I2 m- x: ~  M
2 A5 c- T# b) p

% C3 d; o% S% n' g- a& _. I0 M


* J+ W# r; F& F% m四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
  （注意：要求有计算过程，不能直接写出结果！）
7 c7 J' O4 h( l# [% h(1)  A×P(B)
- y& d* t, g) e) N(2)  A⊕B
(3)  P(A)－P(B)

% y& J1 D7 }, o# V/ i: ^- v* w


% h7 O; o! G$ S4 |4 Z- i. _6 k
0 J- S8 y! V' w; i+ x





7 S& P) `$ b) x+ [" T) @6 g8 m% s
五. (25分)给定集合A={1,2,3},定义A上的关系如下：
R={<1,2>,<2,3>,<3,1>}
5 n; b' v: V8 [9 e$ y2 x6 |S=A×A(完全关系（全域关系）)
# @+ E/ }( o3 x# w# r# K. WT={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
$ Q7 F1 g! o4 O; ^M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
+ I9 I& ]; B+ H1.写出关系R的矩阵；再画出上述各个关系的有向图。
7 T6 C, Y! X! x) A6 D$ f2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
2 i! M) d! V! T4 _/ A% ~        自反的        反自反的        对称的        反对称的        传递的
R                                       
S                                       
/ ~1 W7 W. V5 u  s4 m' E3 S+ ]& ?T                                       
6 Z' U* ]: ^; j' r* ^9 q% wM                                       
) d: c4 T+ x, f: b+ D4 j& a# B' Q3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
7 t* b, {4 I; {/ d7 j8 v) q对等价关系，写出此等价关系的各个等价类。
4.求复合关系RoT
  h0 y' Z6 i) i/ B, |

1 W2 y6 F/ E) E8 g3 p$ B
5 w! @! v2 t0 r; @/ Y/ O& i* I4 X
* e0 P1 N. f. v, _

5 ]" r6 q1 i9 v; K$ a

# Q4 A  X( r3 q4 Z. q
& d) K, u. @4 _; D) t, `2 H
- ]* O, ^% c) h; x  c

6 U) D( Z& M$ E9 ~
  [8 s9 o0 z  [8 n$ w# [7 k
六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
1 H$ w/ h% z* x9 j- \: R1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
0 x; p$ O( u5 F- U0 E% u  e" x  E填下表：
        |x-y|        max         ×        min        +
; J0 v5 ^, e* a- s/ @& N. n有交换性                                       
有结合性                                       
有幂等性                                       
有幺元                                       
8 k6 M* T  f. d8 Y9 P1 A有零元                                       
" o: O; d( G0 b- c2.指出R对上面哪些运算构成群？.
) P9 f3 J) e, O" F! O! S- b/ u' e9 C
( v$ r4 q3 ?$ Y& T
4 S; F' \5 ^$ H6 _0 l4 {
/ f9 [' t' A, L: X


7 J  Y+ q( k; M; r  Q# A* e

/ C$ ?% L$ l. j* c- _! Y

. q4 W/ b4 P; R( S
4 C( K7 E# v. z* e; i; g

5 Y  l! r) T& H, h+ ]# T6 y

& _% v8 t. z, t( e% y
6 `3 q2 _. @) r$ A3 w. _0 F  C8 `
6 e# e9 T2 N! R7 m


" G& Q& Y" |- B! g; `" v% l3 {0 s
七. (14分) 有三个小题
2 N+ t  t# X: ^. }   1. 指出下面各个图中哪些是彼此同构的.
/ ?& r1 I3 f* k1 W$ F1 ^
2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
4 V1 H$ J  o" y- s$ q3.请画出五个具有五个结点的无向图，使之分别满足：
    (1) 是欧拉图但不是汉密尔顿图。
    (2) 既是欧拉图也是汉密尔顿图。
    (3) 是完全图K5。
4 H* X- d3 ~6 |8 m8 b6 C# J(4) 是棵树。
! T3 d. R3 o$ W(5) 是汉密尔顿图但不是欧拉图 。  


; N) r* }  [! \0 Q- y+ N& f, ]: r& o

2 _; W& `! c  X! r# t% ~



' a3 ^) G& A2 w9 |! ]% n* c4 w$ R
# F4 S8 f- ?  ?) u
2 ]! t: p" _5 T




" {: q( R8 ^* A% c' S, c
# W; `8 ~5 z! X5 L9 A; y5 n% W5 T* ]

, s; s1 v  x9 g/ e. d0 q
; M3 K& T9 r: ~, a- B6 Q8 n( a
7 S$ D' F$ L# L; ^2 e  G& k2 v$ e
* ?' D! V* p  l' N& u' ^1 S8 `
3 m* z1 O, G- d