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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
2 W( M  l5 Q# c& R# I, B 离散数学 X 试 卷（作业考核 线上2）  A  卷（共    4    页）
0 d8 e4 U, Q0 g$ U2 q: w总分        题号        一        二        三        四        五        六        七        八        九        十
3 n& g( u" F' x3 f# ~        得分                                                                               
一、 (13分)有两个小题
5 D/ L0 m" X% B  r* G; N1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。




) S& N. s5 d; P* E
" u$ k7 [4 s  Y

2．分别列出PQ、PQ、PQ、PQ的真值表(填下表)。
P        Q        PQ        PQ        PQ        PQ
                                       
1 a' a8 ~* N/ r2 I3 t. r                                       
                                       
                                       

8 |% {& }$ h6 L8 V" P  z% M2 Q- Z# y' q. ]


% ~7 u! B$ [; r二、 (10分)写出命题公式 (Q→&#61656)→Q 的主合取范式。（要求有解题过程）



4 S* U7 h. O! S. b5 C2 r


# E: x5 p' N7 @2 y) \  q


+ \6 c4 P2 k3 b, p# d# x
) L+ o$ G: X0 r; l5 h% t" w
' n( H# Y" X. h9 m  W- w

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





  W3 c* `2 T" r6 n: P% L8 I' v% X# [
: H3 D9 ~) ~# a9 p& Z; [

5 I2 k4 G; z) N( t4 f. T
6 ?0 Y; H0 q' ^' ]四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
% T$ t3 M8 z3 s# p2 F  （注意：要求有计算过程，不能直接写出结果！）
(1)  A×P(B)
(2)  A⊕B
8 D6 M( s% V$ r+ c! C0 j0 p5 S; N(3)  P(A)－P(B)
- w6 X# v" l/ V( @- U

0 c$ N5 Q- }8 C; u( K2 d& }! ~/ J3 ~
7 @8 P$ k; }  D
7 l" U0 c/ S! B  {8 X+ i4 a: \
% u. a# k& p: n

- f- W' O" ~$ T4 Z


* ?% G! V; U- |" r, I

  @5 k; U  {$ Q五. (25分)给定集合A={1,2,3},定义A上的关系如下：
# \+ q) o1 L! s9 c0 lR={<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>}
) q) s* D4 J. J, e1 x, C$ P5 p! Y1.写出关系R的矩阵；再画出上述各个关系的有向图。
/ h0 Z- _0 [& R6 [1 D2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
        自反的        反自反的        对称的        反对称的        传递的
- S* w+ C2 _; f! B! u4 ^& P9 C# ~R                                       
$ ~, c+ m! p. B: ~' s. nS                                       
# K0 U* o# y/ U8 B; z+ u2 sT                                       
2 |* D" ]& R! P1 R; V0 v! y, K% jM                                       
& I! y0 r8 x; N! L  n! L3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
对等价关系，写出此等价关系的各个等价类。
4.求复合关系RoT


: a( @& N0 S$ D5 ]% k: G7 O

" c( U& N* \3 ]' R$ b
* v1 Q, x/ V- L7 I5 A

9 J, s6 d( p+ R
. g! @& }( ?4 M, a; b3 n


& a( \) W/ U. _% z
/ d( @* h$ F8 L4 ?- E

/ u, X' t  `6 u+ u" O1 b5 q六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
  z$ [; e$ E& W- K4 R! r1 C填下表：
6 b7 C% d5 q7 k& E- g% O! W        |x-y|        max         ×        min        +
有交换性                                       
! p: N5 h# k! f8 X& p$ r有结合性                                       
# E; `* S, K6 `- }0 g( E有幂等性                                       
有幺元                                       
3 Q5 F% f5 S  b$ j有零元                                       
2.指出R对上面哪些运算构成群？.



) @. b$ O+ K- k3 P; T' r
. z! c. Z* s! [  b) ?

' [0 u* g9 f& t% b



5 T% }0 T! J; _6 y5 J( d# `- t# j

0 ^4 V) M1 h( ~9 V: K5 m9 B

+ p1 e- H$ F& }


4 `. n4 q5 n2 M3 x4 T1 U# B' R. U

5 r+ \8 I5 ?. ?' T1 u

七. (14分) 有三个小题
) a0 R5 V) f. t3 z( L   1. 指出下面各个图中哪些是彼此同构的.
* L% M/ Z: J' o9 i  o# G
2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
3.请画出五个具有五个结点的无向图，使之分别满足：
    (1) 是欧拉图但不是汉密尔顿图。
: z% r( J  y7 r# R6 v6 \9 K    (2) 既是欧拉图也是汉密尔顿图。
    (3) 是完全图K5。
0 J: _* O: o1 U+ a* Z# l(4) 是棵树。
! f& G$ ^) u! L* D  u* y. f(5) 是汉密尔顿图但不是欧拉图 。  



/ V+ l0 A+ {, ?( C& n
! a- e: M6 t1 ]3 W3 a7 R6 A


0 l$ G/ U) z/ D0 P( Y

7 J) s( r4 g+ `) \

7 Y! {6 S" m# k9 ?+ R

' F% i. w8 |4 d) L

3 @' L% d4 L9 Q+ q# R
+ F/ Y/ Y! ^7 K+ B( s" M
8 C/ {# o  h! {) M- r4 S, ?) G


) ?" J& c* m% U9 e; y5 ?


  j. _& }% Z& L" ]
6 Y: X0 Z0 m" ]
9 V8 E2 o1 B: ]  B; [# I