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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
离散数学 X 试 卷（作业考核 线上2）  A  卷（共    4    页）
总分        题号        一        二        三        四        五        六        七        八        九        十
4 X9 h* P# x$ P; J, X' L$ l        得分                                                                               
一、 (13分)有两个小题
1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。

* l* c. M8 a6 }  Z


7 V6 p+ W2 |" r: w( F7 O% K, x9 q


2．分别列出PQ、PQ、PQ、PQ的真值表(填下表)。
P        Q        PQ        PQ        PQ        PQ
                                       
* f+ H1 J4 a6 s' v! n2 d& m                                       
                                       
                                       

/ z3 |. C7 C4 U$ V& ^6 ~% F


; g) Q$ ~2 E/ g/ x4 Z二、 (10分)写出命题公式 (Q→&#61656)→Q 的主合取范式。（要求有解题过程）

' Y& a7 S: z( E. M* W, b

5 K6 S& r: ]) J+ E4 Q, w' Z
. n# q1 d0 P3 }# Z3 q& d3 ]






/ L% M# G7 Q: O

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


! G* j& r' z  H5 e" O  l% A
& V8 L& i! ?+ p9 m2 r( g



! n* R) W' E3 y# M" q
: z2 {; Z0 K0 y  ^
四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
  （注意：要求有计算过程，不能直接写出结果！）
9 e7 u' T5 M9 U. f! W(1)  A×P(B)
(2)  A⊕B
(3)  P(A)－P(B)

/ |9 X5 p4 v* D9 O7 {+ F4 N* r. h
. G3 D0 `7 k# \


4 ?2 A. }8 y! r6 o% M2 U


7 `& s  v9 k4 \9 e7 T9 ^


, S2 s& u: N. A, j& m% O- i; E
) E" D3 |. I- T9 X  m( M五. (25分)给定集合A={1,2,3},定义A上的关系如下：
R={<1,2>,<2,3>,<3,1>}
1 J5 g" C( ^, tS=A×A(完全关系（全域关系）)
5 O4 b8 c+ v7 u/ l: uT={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
2 C1 M, S7 R" Z: o# n* `1.写出关系R的矩阵；再画出上述各个关系的有向图。
2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
        自反的        反自反的        对称的        反对称的        传递的
$ O5 c2 _9 ~1 d5 {+ YR                                       
% m! Q( X$ R" M" V  P# a4 K3 YS                                       
T                                       
8 G4 Z! V( V) @' U3 |M                                       
3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
对等价关系，写出此等价关系的各个等价类。
4.求复合关系RoT
6 c8 @* e" ~$ D$ X% `- @

( r, j1 Q" B# P9 X) I


2 |+ x2 k# `( ]- `, ^
$ @; x: J% g& n- B7 D
, A; Z* w4 Y4 |) _% V1 q' t



+ O- ~0 Z; x( _, x; K
- X9 f5 T, J; K* y6 h3 M

六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
6 r* D2 f7 o3 T$ \! E+ Z+ n1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
+ m+ G& x, v. T. `填下表：
4 O, z3 i, H; ^2 W9 k# q        |x-y|        max         ×        min        +
有交换性                                       
有结合性                                       
有幂等性                                       
& m$ U+ i" [$ m5 j6 o& v0 ^( Z( j有幺元                                       
有零元                                       
2.指出R对上面哪些运算构成群？.

5 j/ t" i/ N  i0 `6 M4 Z4 j

3 M3 V9 g- J* G9 v# c6 I
, F* z; [( Y, ~* W


0 h0 V6 _7 X6 T7 q4 ~8 A
0 ?- ?2 n, P1 z, K. R0 G8 n  V
0 p1 ^4 f9 h, J  A. k/ k( Y6 D
# Y$ B# F; `; R



! [) d2 y/ G$ }+ l# j
& v5 P( J3 `$ U. `. G$ P
" v6 w+ s+ n4 h! [% n! `
: R% p" `6 N" e4 I0 ?/ i

6 d. B0 _* a' K2 W
/ R' \% Z9 [* U
七. (14分) 有三个小题
   1. 指出下面各个图中哪些是彼此同构的.

2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
3.请画出五个具有五个结点的无向图，使之分别满足：
    (1) 是欧拉图但不是汉密尔顿图。
: f! P7 W1 T  F    (2) 既是欧拉图也是汉密尔顿图。
    (3) 是完全图K5。
(4) 是棵树。
6 S3 Z1 m! v# O# j4 ~: j5 ^(5) 是汉密尔顿图但不是欧拉图 。  



0 r( ^6 A7 R+ U0 |



0 T" }: T. d2 W# Y2 y" M2 v" U
1 t3 y3 a# |& g: n/ F$ E
2 `, \8 x- d, o- k  k
3 l( i  d1 {; T  O/ X
6 s7 |5 b; q8 T5 Q7 J  v



. [: |9 g( E1 x+ t& I1 T( B  n
, K' }+ S: j/ ?) i% S

/ f0 w8 v7 i7 e4 B9 i

$ Z1 m9 a4 {9 ?% _* q" s) q" A
8 B( O' P0 m4 C$ W3 l3 c
1 s7 M. ]2 R4 b
9 u! L/ R$ A) X$ y7 B% i
2 h1 H5 G  }" ]; C