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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
# Y, h! ^- _- ?3 p4 t7 u# w 离散数学 X 试 卷（作业考核 线上2）  A  卷（共    4    页）
" `/ [. d! m5 `, D, z* G/ M总分        题号        一        二        三        四        五        六        七        八        九        十
) z" X& A$ R5 w$ _; Z3 f4 w        得分                                                                               
一、 (13分)有两个小题
$ m4 X. N3 B2 \# Y$ G1 S1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。


  [  E3 T+ ^- c' `
* F. o5 h7 r& x0 y( a6 P



2．分别列出PQ、PQ、PQ、PQ的真值表(填下表)。
6 L8 ~& V# l& rP        Q        PQ        PQ        PQ        PQ
# }% \$ J6 `6 R3 y, `; y$ ]                                       
& L+ \2 U" |6 D( T# o0 }                                       
                                       
                                       
6 m9 h  n3 j6 l0 A/ d2 t  J
  h# \8 a: Q; {  _, h$ M0 [
  |* i0 t! b! q+ r3 f+ R
& l; n" H" ^7 g2 G/ Q' J
二、 (10分)写出命题公式 (Q→&#61656)→Q 的主合取范式。（要求有解题过程）

( ?+ I6 b0 P) k. W# |
# K+ P8 w$ h2 r4 T9 l. u2 @  e

/ v; m5 t/ `1 ^- l  e4 m



' g- Z" R+ ]# x) Z4 g: J

# n, }/ _) |, ^% A: `


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

6 l- L& b& l3 M


0 }) |  V5 w& m8 o. Z3 j4 M; L
  t* R& c9 e7 O. M' n



  A) W- B& n6 J% h2 ~四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
. R; }- v( f. w. W  （注意：要求有计算过程，不能直接写出结果！）
& ?/ s5 f5 A( k6 e(1)  A×P(B)
(2)  A⊕B
(3)  P(A)－P(B)
' l4 p  l; p1 t


0 P) w" w: I  o  X

1 s- |$ }; |# j
0 ]/ l5 F9 B/ s$ r+ }
/ j1 k8 e# b- Y! l; K

; p" l4 m8 F6 F5 F
3 d0 n7 d7 X, l

五. (25分)给定集合A={1,2,3},定义A上的关系如下：
R={<1,2>,<2,3>,<3,1>}
& ^  h5 g5 ], j2 e0 [1 {! lS=A×A(完全关系（全域关系）)
4 k; b: ?9 b+ T% e3 D) KT={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
1.写出关系R的矩阵；再画出上述各个关系的有向图。
, M# s  b3 P/ L# X2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
        自反的        反自反的        对称的        反对称的        传递的
R                                       
S                                       
( Z0 J, @$ D) O) o4 ?: d5 e, GT                                       
M                                       
1 G5 L1 h4 t$ V) _" Y6 o3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
对等价关系，写出此等价关系的各个等价类。
* M$ b# ~7 n5 L) j- Z: {9 @4.求复合关系RoT

1 ~: {' J. g8 }! j

4 a8 A& R9 p3 R; Y  ~: A
9 }( U# l& ^) n) a; t4 f9 m8 Z3 P5 g

* A* Q  I6 h$ \" O7 {0 B





1 X1 @8 H; i* d4 m. Q
  L, i! |% s0 m9 K! Z
- b1 U: e' m* j0 A$ E4 o$ T6 C六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
# Y5 H- B  ^7 G! W7 p1 R. W1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
填下表：
6 C4 L% C5 u- B        |x-y|        max         ×        min        +
有交换性                                       
有结合性                                       
9 U& v' U6 n* O/ z有幂等性                                       
有幺元                                       
6 F8 x9 \. g- Z有零元                                       
+ X5 C% F/ D9 T; P" N% u. O( q% q2.指出R对上面哪些运算构成群？.
! t) ^0 D- J$ e2 n2 D  D



" O2 N) x( l; B. }2 L- \! S




% a8 k2 Z4 _  a5 R
, Y3 q( ^4 p; q3 j5 }


8 @& [- P9 e4 \7 r7 m
) ^' q2 c2 l. e6 b. m/ |" @2 R- f


/ h7 X/ I% X4 f
$ T+ l* D1 _$ n% p3 j4 o
; H8 k" E0 {+ ^( |1 e

# {" a6 z' @9 p  p, e七. (14分) 有三个小题
5 h' o5 m# E6 |" q5 I+ D3 o   1. 指出下面各个图中哪些是彼此同构的.

+ R. i5 `. O5 Z( [2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
- Q3 k8 T9 E% a. `" S% O3.请画出五个具有五个结点的无向图，使之分别满足：
    (1) 是欧拉图但不是汉密尔顿图。
9 u, K; \# @8 w- Z% U8 p    (2) 既是欧拉图也是汉密尔顿图。
    (3) 是完全图K5。
! Y9 Z" u# o, j( e) b8 S1 O(4) 是棵树。
& e6 O3 d, k  x(5) 是汉密尔顿图但不是欧拉图 。  

/ a9 T5 d: i+ C/ `1 U




8 c4 q  K* E1 m. w+ p/ p




/ n! T. X* Y5 g4 r* e





# W6 |- _# I  c5 m" m
9 }* j" N/ }, ?4 }4 X

3 o2 }8 s6 i# N# C2 {+ S, X
% @/ p+ {8 {; p" l3 }

- Q9 K( a9 M- z8 ^4 E! [; O  a& r
4 E6 V2 P+ D- U; g4 i0 S) {
0 W0 m/ ?# \9 d