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

奥鹏在线作业

东 北 大 学 继 续 教 育 学 院
离散数学 X 试 卷（作业考核 线上2）  A  卷（共    4    页）
: ?8 D' H0 n1 N# u- s% e8 O总分        题号        一        二        三        四        五        六        七        八        九        十
        得分                                                                               
% p/ W$ A; Z( M0 ^/ \- _一、 (13分)有两个小题
  \( V" n3 M5 s% M1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。
5 q" d! ?! \# {& A# S- L' k  U

  Q+ L3 f+ P8 h: A1 w
5 `4 c$ v* F; `5 d3 u! B) R9 x( j, m
6 [- X- b) w1 x9 _+ ~, @9 o2 A# T2 N
2．分别列出PúQ、PùQ、P«Q、P®Q的真值表(填下表)。
P        Q        PúQ        PùQ        P«Q        P®Q
- ?: [9 R# z* j                                       
                                       
                                       
                                       
/ ~/ @9 `) ?) w
+ D% y) l8 p% U! f4 G二. (10分)写出命题公式 (Q→&#216)→Q 的主合取范式。（要求有解题过程）
3 O0 {7 z  G8 C% S% }2 J, @9 k9 u
, `- @. g) [9 Z. u
5 ~9 l  d9 S3 F3 y& ]% Q
0 e& k6 `# P* ]! ]
- D) r  x; k& N6 `
; e, p: K* C9 I* Y7 I& a! n( s7 @" |

" [1 C3 K) ]' g; N

( h8 x5 ]5 }# c8 L. J( @8 `
; e5 k3 P. m' ~" Z3 {5 w* c  |

" F3 R  }! G  K% w' w9 b+ e
7 {( t; K7 u5 y9 F
2 P: u# L6 s2 @# c7 {



0 c( {3 }; v  ]1 I2 V8 j三、(14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。   
  xC(x), x(A(x)B(x)), x(B(x)C(x))  xA(x)

' r! z  R0 t, {* `+ M
7 a0 l6 j# O- J& x  x+ t' ~
9 f+ f  R! y4 ]! W# ?- O: n$ P

3 T# X1 k2 b3 L* ^5 H; _6 D/ U



- x. n" t: q, a四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
  （注意：要求有计算过程，不能直接写出结果！）
4 H+ V: d8 T7 p, h3 I) H(1)  A×P(B)
(2)  A⊕B
(3)  P(A)－P(B)
2 H" v! M4 P$ y0 Z; s
# U" j: f0 [7 T+ t- B& Q
4 [5 v' _( U* b' v

  U; j+ d  h3 [2 F) }7 s- s5 a+ @! n
* H' ~0 _  h( Y& P
, B. B8 z5 L& |4 G2 h6 l4 F
/ N! a  Y( E8 t5 F
  |; K1 ?5 I- n/ c% c( i
! t) X# ~2 v# g7 e+ y8 l! _
- t0 c5 i$ V/ N
8 l$ |7 P! Z: c8 P- G1 E
五. (25分)给定集合A={1,2,3},定义A上的关系如下：
) V2 u6 C# u9 J5 y, AR={<1,2>,<2,3>,<3,1>}
. W# x- [4 l; {, s5 J# n, N6 O( a: LS=A×A(完全关系（全域关系）)
% S4 B: v5 S( E" R+ QT={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
1.写出关系R的矩阵；再画出上述各个关系的有向图。
2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
, D/ ~: t( t( J8 z9 Q3 d        自反的        反自反的        对称的        反对称的        传递的
R                                       
) O' J( M& Y' V& AS                                       
! m, X, S9 N+ Z; v; N$ AT                                       
M                                       
* E9 ^! M) I6 q3.上述四个关系中，哪些是等价关系？哪些是偏序关系？
对等价关系，写出此等价关系的各个等价类。
4.求复合关系RoT
" |, N$ X& \# U7 b) j- P1 _
" w) a; H: O. }! w5 ~7 f
- i" S. A9 |2 e" b- p9 A


$ d0 E" s" O: R% f" _+ U/ B

% F3 ]0 c0 D5 B3 r7 E+ G3 U0 v
6 j$ G: ~* d! A+ n8 X8 r1 L8 E
. I! I; r  f: C+ q( n
8 y, g: M8 K# v* w* z. K. c
8 O8 C/ t# M' t# b

# L, R2 ~3 X, p
  W( y/ ]' q- c$ f- c5 _) m" I; Y六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。
/ X( }. o: d+ `) O1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
+ Y0 a0 w+ N* j) [* }1 i填下表：
        |x-y|        max         ×        min        +
! U9 f& b, C0 P1 T7 v有交换性                                       
有结合性                                       
. b  D% ~  ^9 w3 m" Y8 ^有幂等性                                       
有幺元                                       
' Z8 Y, Y' u# ~- g# r4 c有零元                                       
2 ?7 S% [; O# }2.指出R对上面哪些运算构成群？.

$ L& F( f0 ~/ U" O3 S' I/ C$ A' J
! U/ l' |8 f' V. Q8 ^7 Z. n3 B! F0 v* R
) I8 ]4 @& B3 ?; P+ T- V
" s( G! t* @/ a- w5 L+ Q# g: m' Y
, B4 Y* c: g' a+ q( T; q9 h  j7 h
: K( A- d- _8 W: x+ m  J4 ^* w






! p  f; }- p$ p8 _" x3 ]2 ]
' j) y1 V% ]4 S. F- K  T



. E- N8 t5 V8 C

8 x- K" h/ Z7 V' |
七. (14分) 有三个小题
   1. 指出下面各个图中哪些是彼此同构的.
# B" h, H3 U: x4 g( A* G
, {9 g+ s; P5 S2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）
' x$ s+ |% A+ [4 y# m$ y3 w3.请画出五个具有五个结点的无向图，使之分别满足：
    (1) 是欧拉图但不是汉密尔顿图。
    (2) 既是欧拉图也是汉密尔顿图。
    (3) 是完全图K5。
& ]: ]) L" ]+ g& W+ j$ _7 z(4) 是棵树。
(5) 是汉密尔顿图但不是欧拉图 。  


5 S' W* J5 _5 X- f& h
' ]5 j. Y) |( ^& W3 Q

1 d% Y3 m. u0 K6 X0 j
9 }! h' _3 b* X$ w
8 C+ Q! j/ a, i8 i; I5 [, l
6 E2 {- t% m: d4 O* L3 n2 C
8 P* R$ K2 J& O6 n$ K


. I5 k1 R; X& Y! _7 `. ?) q2 J+ @. o% z


* ?3 ?: ]. y" G6 `% r( S7 `6 v6 I
' j9 f+ o- x' w% X0 l

$ Z$ x: g; |) f2 e# q8 R8 F* S
& }5 r& l+ F3 \! c2 F7 E, y# {
0 m; y2 Z7 G2 Y3 Q( G
* h5 u0 r7 Q! W, K1 n
3 j" N! J$ F0 U# a& J9 U$ E, S

7 S7 @5 {7 K7 U! a0 _