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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
. }2 {) K" d8 r+ K- P1 @! | 离散数学 X 试 卷（作业考核 线上2）  A  卷（共    4    页）
总分        题号        一        二        三        四        五        六        七        八        九        十
        得分                                                                               
+ k- |; m9 |9 @. O% I! F一、 (13分)有两个小题
1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。
1 L% q3 F  `0 a; r

6 o7 b5 l( ]; w' F
& P& O8 S3 e8 t6 H: t+ H! r7 E


& C; W" i) x$ t
2．分别列出PQ、PQ、PQ、PQ的真值表(填下表)。
P        Q        PQ        PQ        PQ        PQ
                                       
& R$ Y! P) {4 q2 B8 I0 w: v                                       
; j1 q" F) d3 ]# T  I                                       
: m+ S, x0 z) Z0 q" n/ |0 R& s1 c                                       
( p% N, R: L+ N- H" z5 n9 i* Y

2 [5 x& k5 Y  I( R
. v/ b' H8 c- z: C: v4 s" d9 T% V
, M0 h$ ]# s8 A二、 (10分)写出命题公式 (Q→&#61656)→Q 的主合取范式。（要求有解题过程）
! F1 V1 y3 i2 d+ f  M1 r/ o7 d( _

; F0 x/ W: w( W' {0 s5 [& x" T9 h: _' s


+ i* d5 B8 Q2 e/ e: O& b

8 K4 I# C5 Z1 a0 I6 B, s
6 u; G" R. P( ?+ m7 c' B: D
3 e* Y2 f  E: s, w& X- y% k" M3 j. e% ^
) f' f. ^8 S' D; o* S8 l1 }& o

! E' X- ?3 T  E6 b2 B
4 S5 P( m- ]% e9 Y! @  z三、(14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。   
. {3 S9 s; ~; _' I( m" ?  xC(x), x(A(x)B(x)), x(B(x)C(x))  xA(x)
( `4 R/ o9 i2 K' C- q. z
6 R5 m6 ~+ I  c

% N# r& H+ h5 f; T4 k
/ V( |% h. J) e6 a' u
9 g6 {$ I% e% v

& }, l9 e$ \# O( C
# I, Z, m. b+ `
: n3 @( M8 m" x6 ~3 `) j: U四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
0 z- s" a# O3 |  （注意：要求有计算过程，不能直接写出结果！）
(1)  A×P(B)
(2)  A⊕B
(3)  P(A)－P(B)
! p# A' K) O. F; I! m

2 w9 b" w5 ^3 ^2 F+ x% l4 P/ Z
, G- l  X" N8 R3 m

/ q9 A9 D% X6 N5 w( ^5 I  H) O' ~, Y
) G9 B5 x- P+ Q1 w$ T
- c; T, A  C1 n1 v1 K

( ]+ Q) z. [6 u" H! F8 x6 L
+ _- L/ L5 t+ [; l3 Y' N

8 ]9 W+ m) C7 ~% B; R8 p* O# @  ^五. (25分)给定集合A={1,2,3},定义A上的关系如下：
R={<1,2>,<2,3>,<3,1>}
7 h2 Q4 b5 v; b" J, F+ U$ \' m; N* p/ lS=A×A(完全关系（全域关系）)
T={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
7 H2 f: L; `7 K0 HM={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
4 P% Y3 ^. S4 s1.写出关系R的矩阵；再画出上述各个关系的有向图。
2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
        自反的        反自反的        对称的        反对称的        传递的
R                                       
S                                       
2 J! T1 f  O9 G! h& v+ I% l2 OT                                       
; |- E6 c- n+ S* CM                                       
4 B: O9 _+ ^5 l# Z* O3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
  R2 t5 x1 h) H3 J0 T9 g对等价关系，写出此等价关系的各个等价类。
9 t& R+ @6 {" f0 f. N" a8 B4.求复合关系RoT
& W4 i; b2 l" W, P% o
9 g, @2 k8 ~4 O4 C  A1 u2 r


4 l  F& l  z. Q; a* X  ~
- o7 V# |5 O$ y9 s5 b. M




* x3 C! [8 w( Y; r5 ^

7 ~4 y1 ^4 @7 t% p3 ?/ P

六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
! W. L4 d7 X9 E" z% f( N1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
填下表：
* m: n- `  {5 g5 }- ~# W        |x-y|        max         ×        min        +
( ]6 C9 X/ K- L有交换性                                       
有结合性                                       
+ B  C: _( D0 k- x2 N4 U8 y有幂等性                                       
+ `2 I1 O% d5 j# |有幺元                                       
有零元                                       
2.指出R对上面哪些运算构成群？.
6 @# e: R* r1 P" B, H
) ?5 {* G4 Z+ s8 E5 F- N/ E* v/ l



: `) ~& B: N4 n( h6 N: c
7 f$ ]3 s' @' d8 i/ u% Q. u' k6 i
, b+ @7 K  G8 ]! m" \7 U) J
- T8 w* E# x9 V



5 D1 {3 T; x& h




- c' J8 e4 G# ^6 J. _& q% D
2 x. T( W, p4 h& v& d
* g9 ~+ o6 d% l% @) b4 \2 v# H# K: e

& U6 L4 K1 K8 E! b0 e七. (14分) 有三个小题
   1. 指出下面各个图中哪些是彼此同构的.
7 d1 O7 x0 f) O5 Y
2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
* N3 J& K* |) s+ Q" |3.请画出五个具有五个结点的无向图，使之分别满足：
    (1) 是欧拉图但不是汉密尔顿图。
    (2) 既是欧拉图也是汉密尔顿图。
    (3) 是完全图K5。
(4) 是棵树。
(5) 是汉密尔顿图但不是欧拉图 。  


: E6 G, @( s( J0 }6 W, b8 X' |
7 s6 L4 e) C$ |1 b$ v

3 b/ h5 O. i( x& l- m

, i/ A" q; y# ~- \  o
" ~# }8 [6 I* Z' N




( Z$ T6 e6 `  M: \3 g


/ L  k& w0 H/ ~
8 q* a  t! u& E5 B  Q$ P) t- g2 S
  G9 ?" ~' [5 n8 Q) w# `


2 z; a/ `3 b+ p# U& t8 x
. G9 h& E4 j' k& C1 K* ^


7 J) A# {0 h% `) b7 @