离散数学

第一章 集合

2

$$a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd$$

8

1 对,其余错

9

略

10

1. $\varnothing$
2. $A$
3. $B$
4. $A \cap B$
5. $A$
6. $B-A$

13

1. $B\cap C \nsubseteq A$ or $B \cap C = \varnothing$
2. $A - (B \cap C) = \varnothing$
3. $ B \cup C \nsubseteq A$
4. $A - (B \cup C) = \varnothing$
5. $A \subseteq B \oplus C$
6. $A \subseteq B \cap C$

16

均正确

18

$2^{100}$ , $2^{99}$

20

$B \subseteq A$ or $A \subseteq B $

27

15, 52
详见: Bell Number

$$B_n = \sum_{k=0}^{n-1} \binom{n-1}{k} B_k$$

33

$$\left [ \frac{50-1}{4} \right ] + 1 =13$$

$$\left [\frac{50-8-1}{3} \right] + 1 = 14$$

35

52

38

194

40

枚举得 30

第二章 关系

4

$$R= \{<0,3>,<1,2>,<3,0>,<2,1>\}\\ S =\{<1,0>,<2,1>,<3,2>\}$$

依据此计算各结果

5

略

8

1. $R= \{<1,1>,<1,2>,<2,2>,<2,3>,<3,1>,<3,3>\}$
   $R^2= \{<1,1>,<1,2>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>\}$
2. 略
3. 略

9

考虑 1,2 轮换
$R_1 = \{<1,2>,<2,3>,<3,1>\}$
$R_2 = \{<1,3>,<2,1>,<3,2>\}$

11

$n^2,n,n^2,(n^2-n)/2,n^2-n,0$

13

1. $R = \varnothing $
2. $R = \{<1,2>,<2,3>,<1,3>\}$
3. 同上
4. $R = \{<1,1>,<1,2>,<2,1>,<2,3>\}$

16

if $a+ib=0$ : 自反, 对称, 传递
if $a+ib \neq 0$ : 反自反

17

自反, 反对称,传递

20

$\forall x,y,z \in A$
if $<x,x> , <x,y> , <y,z> \in R$

$$<x,y>\circ <y,z> \implies <y,z> \in R\circ R\implies R\circ R \subseteq R$$

if $<x,y> \in R, <x,x>\in R$

$$<x,y> = <x,x>\circ <x,y>\implies R\subseteq R\circ R$$

26

if $\exists <x,y> \in S\circ R$ but $<x,y> \notin R\circ S$
$<x,z> \in S,<z,y>\in R \implies <z,x> \in S, <y,z> \in R \implies <y,x> \in R\circ S$
since $R\circ S \subseteq S\circ R$, we have $<y,x> \in S\circ R$
this implies $<x,y> \in R\circ S$, contradiction.

29

自反,对称性显然保持,验证转递:
对$\forall <x,y> ,<y,z> \in R\cup S$, 前者属于 R, 后者属于 S 则显然, 两个都属于R 或者都属于 S 也显然, 前者属于 S 后者属于 R 时:

$$<z,y>\circ<y,x> \implies <z,x> \in R\cup S$$

31

叙述两种格的定义, 并说明定义等价