离散数学试题及答案

╰+哭是因爲堅強的太久メ 2024-03-24 14:42 95阅读 0赞

**离散数学试题及答案**

**一、填空题**

**1** 设集合A,B，其中A＝\{1,2,3\}, B= \{1,2\}, 则A - B＝\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_; r(A) - r(B)＝ \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ .

2. 设有限集合A, |A| = n, 则 |r(A×A)| = \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

**3.** 设集合A = \{ *a*, *b*\}, B = \{1, 2\}, 则从A到B的所有映射是\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ \_\_\_\_\_\_\_\_\_\_\_\_\_, 其中双射的是\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

4. 已知命题公式G＝Ø(P®Q)∧R，则G的主析取范式是\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

5.设*G*是完全二叉树，G有7个点，其中4个叶点，则*G*的总度数为\_\_\_\_\_\_\_\_\_\_，分枝点数为\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

**6** 设A、B为两个集合, A= \{1,2,4\}, B = \{3,4\}, 则从AÇB＝\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_; AÈB＝\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_;A－B＝ \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ .

**7**. 设R是集合A上的等价关系，则R所具有的关系的三个特性是\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

**8**. 设命题公式G＝Ø(P®(QÙR))，则使公式G为真的解释有\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_，\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

9. 设集合A＝\{1,2,3,4\}, A上的关系R1 = \{(1,4),(2,3),(3,2)\}, R1 = \{(2,1),(3,2),(4,3)\}, 则 R1·R2 = \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_,R2·R1 =\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, R12 =\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

10. 设有限集A, B，|A| = m, |B| = n, 则| |r(A´B)| = \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

**11** 设A,B,R是三个集合，其中R是实数集，A = \{x | -1≤x≤1, xÎR\}, B = \{x | 0≤x < 2, xÎR\},则A-B = \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ , B-A = \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ ,

A∩B = \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ , .

**13.** 设集合A＝\{2, 3, 4, 5, 6\}，R是A上的整除，则R以集合形式(列举法)记为\_\_\_\_\_\_\_\_\_\_\_ \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_*.*

14. 设一阶逻辑公式G = "xP(x)®$xQ(x)，则G的前束范式是\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ \_\_\_\_\_.

15.设G是具有8个顶点的树，则G中增加\_\_\_\_\_\_\_\_\_条边才能把G变成完全图。

16. 设谓词的定义域为\{ *a*, *b*\},将表达式"xR(x)→$xS(x)中量词消除，写成与之对应的命题公式是\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

17. 设集合A＝\{1, 2, 3, 4\}，A上的二元关系R＝\{(1,1),(1,2),(2,3)\}, S＝\{(1,3),(2,3),(3,2)\}。则R×S＝\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_,

R2＝\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

**二、选择题**

**1** 设集合A=\{2,\{a\},3,4\}，B = \{ \{a\},3,4,1\}，E为全集，则下列命题正确的是( )。

(A)\{2\}ÎA (B)\{a\}ÍA (C)ÆÍ\{ \{a\}\}ÍBÍE (D)\{ \{a\},1,3,4\}ÌB.

2设集合A=\{1,2,3\},A上的关系R＝\{(1,1),(2,2),(2,3),(3,2),(3,3)\}，则R不具备( ).

(A)自反性 (B)传递性 (C)对称性 (D)反对称性

3 设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B = \{2,3,4,5\},则元素6为B的( )。

(A)下界 (B)上界 (C)最小上界 (D)以上答案都不对

**4** 下列语句中，( )是命题。

(A)请把门关上 (B)地球外的星球上也有人

(C)x + 5 > 6 (D)下午有会吗？

**5** 设I是如下一个解释：D＝\{a,b\},

则在解释I下取真值为1的公式是( ).

(A)$x"yP(x,y) (B)"x"yP(x,y) (C)"xP(x,x) (D)"x$yP(x,y).

6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( ).

(A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6).

7. 设G、H是一阶逻辑公式，P是一个谓词，G＝$xP(x), H＝"xP(x),则一阶逻辑公式G®H是( ).

(A)恒真的 (B)恒假的 (C)可满足的 (D)前束范式.

**8** 设命题公式G＝Ø(P®Q)，H＝P®(Q®ØP)，则G与H的关系是( )。

(A)GÞH (B)HÞG (C)G＝H (D)以上都不是.

9设A, B为集合，当( )时A－B＝B.

(A)A＝B (B)AÍB (C)BÍA (D)A＝B＝Æ.

10 设集合A = \{1,2,3,4\}, A上的关系R＝\{(1,1),(2,3),(2,4),(3,4)\}, 则R具有( )。

(A)自反性 (B)传递性 (C)对称性 (D)以上答案都不对

**11** 下列关于集合的表示中正确的为( )。

(A)\{a\}Î\{a,b,c\} (B)\{a\}Í\{a,b,c\} (C)ÆÎ\{a,b,c\} (D)\{a,b\}Î\{a,b,c\}

**12** 命题"xG(x)取真值1的充分必要条件是( ).

(A) 对任意x，G(x)都取真值1. (B)有一个x0，使G(x0)取真值1.

(C)有某些x，使G(x0)取真值1. (D)以上答案都不对.

13. 设G是连通平面图，有5个顶点，6个面，则G的边数是( ).

(A) 9条 (B) 5条 (C) 6条 (D) 11条.

14. 设G是5个顶点的完全图，则从G中删去( )条边可以得到树.

(A)6 (B)5 (C)10 (D)4.

15. 设图G的相邻矩阵为

，则G的顶点数与边数分别为( ).

(A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8.

**三、计算证明题**

**1.**设集合A＝\{1, 2, 3, 4, 6, 8, 9, 12\}，R为整除关系。

(1) 画出半序集(A,R)的哈斯图；

(2) 写出A的子集B = \{3,6,9,12\}的上界，下界，最小上界，最大下界；

(3) 写出A的最大元，最小元，极大元，极小元。

1. 设集合A＝\{1, 2, 3, 4\}，A上的关系R＝\{(x,y) | x, yÎA 且 x ³ y\}, 求

(1) 画出R的关系图；

(2) 写出R的关系矩阵.

2. 设R是实数集合，s,t,j是R上的三个映射，s(x) = x+3, t(x) = 2x, j(x) ＝ x/4,试求复合映射s•t，s•s, s•j, j•t，s•j•t.

4. 设I是如下一个解释：D = \{2, 3\},

*a*

*b*

*f* (2)

*f* (3)

*P*(2, 2)

*P*(2, 3)

*P*(3, 2)

*P*(3, 3)

试求 (1) *P*(*a*, *f* (*a*))∧*P*(*b*, *f* (*b*));

(2) "*x*$*y P* (*y*, *x*).

**5.** 设集合A＝\{1, 2, 4, 6, 8, 12\}，R为A上整除关系。

(1) 画出半序集(A,R)的哈斯图；

(2) 写出A的最大元，最小元，极大元，极小元；

(3) 写出A的子集B = \{4, 6, 8, 12\}的上界，下界，最小上界，最大下界.

6. 设命题公式G = Ø(P→Q)∨(Q∧(ØP→R)), 求G的主析取范式。

7. (9分)设一阶逻辑公式：*G* = ("*xP*(*x*)∨$*yQ*(*y*))→"*xR*(*x*)，把*G*化成前束范式.

9. 设R是集合A = \{a, b, c, d\}. R是A上的二元关系, R = \{(a,b), (b,a), (b,c), (c,d)\},

(1) 求出r(R), s(R), t(R)；

(2) 画出r(R), s(R), t(R)的关系图.

**11.** 通过求主析取范式判断下列命题公式是否等价：

(1) G = (P∧Q)∨(ØP∧Q∧R)

(2) H = (P∨(Q∧R))∧(Q∨(ØP∧R))

13. 设*R*和*S*是集合*A*＝\{ *a*, *b*, *c*, *d*\}上的关系，其中*R*＝\{(*a*, *a*),(*a*, *c*),(*b*, *c*),(*c*, *d*)\}, *S*＝\{(*a*, *b*),(*b*, *c*),(*b*, *d*),(*d*, *d*)\}.

(1) 试写出*R*和*S*的关系矩阵；

(2) 计算*R*•*S*, *R*∪*S*, *R*－1, *S*－1•*R*－1.

**四、证明题**

1. 利用形式演绎法证明：\{ *P*→*Q*, *R*→*S*, *P*∨*R*\}蕴涵*Q*∨*S*。

2. 设A,B为任意集合，证明：(A-B)-C = A-(B∪C).

3. (本题10分)利用形式演绎法证明：\{ØA∨B, ØC→ØB, C→D\}蕴涵A→D。

4. (本题10分)A, B为两个任意集合，求证：

A－(A∩B) = (A∪B)－B .

**参考答案**

一、填空题

1. \{3\}; \{ \{3\},\{1,3\},\{2,3\},\{1,2,3\}\}.

3. a1= \{(*a*,1), (*b*,1)\}, a2= \{(*a*,2), (*b*,2)\},a3= \{(*a*,1), (*b*,2)\}, a4= \{(*a*,2), (*b*,1)\}; a3, a4.

4. (P∧ØQ∧R).

5. 12, 3.

6. \{4\}, \{1, 2, 3, 4\}, \{1, 2\}.

7. 自反性；对称性；传递性.

8. (1, 0, 0), (1, 0, 1), (1, 1, 0).

9. \{(1,3),(2,2),(3,1)\}; \{(2,4),(3,3),(4,2)\}; \{(2,2),(3,3)\}.

10. 2m´n.

11. \{x | -1≤x < 0, xÎR\}; \{x | 1 < x < 2, xÎR\}; \{x | 0≤x≤1, xÎR\}.

12. 12; 6.

13. \{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)\}.

14. $x(ØP(x)∨Q(x)).

15. 21.

16. (R(a)∧R(b))→(S(a)∨S(b)).

17. \{(1, 3),(2, 2)\}; \{(1, 1),(1, 2),(1, 3)\}.

**二、选择题**

1. C. 2. D. 3. B. 4. B.

5. D. 6. C. 7. C.

8. A. 9. D. 10. B. 11. B.

13. A. 14. A. 15. D

**三、计算证明题**

(1)

(2) B无上界，也无最小上界。下界1, 3; 最大下界是3.

(3) A无最大元，最小元是1，极大元8, 12, 90+; 极小元是1.

**2.**R = \{(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)\}.

(1)

(2)

3. (1)s•t＝s(t(x))＝t(x)+3＝2x+3＝2x+3.

(2)s•s＝s(s(x))＝s(x)+3＝(x+3)+3＝x+6,

(3)s•j＝s(j(x))＝j(x)+3＝x/4+3,

(4)j•t＝j(t(x))＝t(x)/4＝2x/4 = x/2,

(5)s•j•t＝s•(j•t)＝j•t+3＝2x/4+3＝x/2+3.

4. **(1)** ***P*****(*****a*****,** ***f*** **(*****a*****))∧*****P*****(*****b*****,** ***f*** **(*****b*****)) =** ***P*****(3,** ***f*** **(3))∧*****P*****(2,** ***f*** **(2))**

= *P*(3, 2)∧*P*(2,3)

= 1∧0

= 0.

(2) "*x*$*y P* (*y*, *x*) = "*x* (*P* (2, *x*)∨*P* (3, *x*))

= (*P* (2, 2)∨P (3, 2))∧(*P* (2, 3)∨P (3, 3))

= (0∨1)∧(0∨1)

= 1∧1

= 1.

**5.** (1)

(2) 无最大元，最小元1，极大元8, 12; 极小元是1.

(3) B无上界，无最小上界。下界1, 2; 最大下界2.

6. G = Ø(P→Q)∨(Q∧(ØP→R))

= Ø(ØP∨Q)∨(Q∧(P∨R))

= (P∧ØQ)∨(Q∧(P∨R))

= (P∧ØQ)∨(Q∧P)∨(Q∧R)

= (P∧ØQ∧R)∨(P∧ØQ∧ØR)∨(P∧Q∧R)∨(P∧Q∧ØR)∨(P∧Q∧R)∨(ØP∧Q∧R)

= (P∧ØQ∧R)∨(P∧ØQ∧ØR)∨(P∧Q∧R)∨(P∧Q∧ØR)∨(ØP∧Q∧R)

= m3∨m4∨m5∨m6∨m7 = S(3, 4, 5, 6, 7).

7. ***G*** **= ("*****xP*****(*****x*****)∨$*****yQ*****(*****y*****))→"*****xR*****(*****x*****)**

= Ø("*xP*(*x*)∨$*yQ*(*y*))∨"*xR*(*x*)

= (Ø"*xP*(*x*)∧Ø$*yQ*(*y*))∨"*xR*(*x*)

= ($*x*Ø*P*(*x*)∧"*y*Ø*Q*(*y*))∨"*zR*(*z*)

= $*x*"*y*"*z*((Ø*P*(*x*)∧Ø*Q*(*y*))∨*R*(*z*))

9. (1) r(R)＝R∪IA＝\{(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d)\},

s(R)＝R∪R－1＝\{(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)\},

t(R)＝R∪R2∪R3∪R4＝\{(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)\}；

(2)关系图:

**11.** G＝(P∧Q)∨(ØP∧Q∧R)

＝(P∧Q∧ØR)∨(P∧Q∧R)∨(ØP∧Q∧R)

＝m6∨m7∨m3

＝å (3, 6, 7)

H = (P∨(Q∧R))∧(Q∨(ØP∧R))

＝(P∧Q)∨(Q∧R))∨(ØP∧Q∧R)

＝(P∧Q∧ØR)∨(P∧Q∧R)∨(ØP∧Q∧R)∨(P∧Q∧R)∨(ØP∧Q∧R)

＝(P∧Q∧ØR)∨(ØP∧Q∧R)∨(P∧Q∧R)

＝m6∨m3∨m7

＝å (3, 6, 7)

G,H的主析取范式相同，所以G = H.

13. **(1)**

(2)*R•S*＝\{(*a*, *b*),(*c*, *d*)\},

*R*∪*S*＝\{(*a*, *a*),(*a*, *b*),(*a*, *c*),(*b*, *c*),(*b*, *d*),(*c*, *d*),(*d*, *d*)\},

*R*－1＝\{(*a*, *a*),(*c*, *a*),(*c*, *b*),(*d*, *c*)\},

*S*－1•*R*－1＝\{(*b*, *a*),(*d*, *c*)\}.

**四 证明题**

1. 证明：\{ *P*→*Q*, *R*→*S*, *P*∨*R*\}蕴涵*Q*∨*S*

(1) *P*∨*R* P

(2) Ø*R*→*P* Q(1)

(3) *P*→*Q* P

(4) Ø*R*→*Q* Q(2)(3)

(5) Ø*Q*→*R* Q(4)

(6) *R*→*S* P

(7) Ø*Q*→*S* Q(5)(6)

(8) *Q*∨*S Q(7)*

2. 证明：(A-B)-C = (A∩~B)∩~C

= A∩(~B∩~C)

= A∩~(B∪C)

= A-(B∪C)

3. 证明：\{ØA∨B, ØC→ØB, C→D\}蕴涵A→D

(1) A D(附加)

(2) ØA∨B P

(3) B Q(1)(2)

(4) ØC→ØB P

(5) B→C Q(4)

(6) C Q(3)(5)

(7) C→D P

(8) D Q(6)(7)

(9) A→D D(1)(8)

所以 \{ØA∨B, ØC→ØB, C→D\}蕴涵A→D.

3. 证明：A－(A∩B)

= A∩~(A∩B)

＝A∩(~A∪~B)

＝(A∩~A)∪(A∩~B)

＝Æ∪(A∩~B)

＝(A∩~B)

＝A－B

而 (A∪B)－B

= (A∪B)∩~B

= (A∩~B)∪(B∩~B)

= (A∩~B)∪Æ

= A－B

所以：A－(A∩B) = (A∪B)－B.

**离散数学试题（A卷及答案）**

一、（10分）某项工作需要派*A*、*B*、*C*和*D* 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

(1)若*A*去，则*C*和*D*中要去1个人；

(2)*B*和*C*不能都去；

(3)若*C*去，则*D*留下。

解 设*A*：*A*去工作；*B*：*B*去工作；*C*：*C*去工作；*D*：*D*去工作。则根据题意应有：*A*®*C*Å*D*，Ø(*B*∧*C*)，*C*®Ø*D*必须同时成立。因此

(*A*®*C*Å*D*)∧Ø(*B*∧*C*)∧(*C*®Ø*D*)

Û(Ø*A*∨(*C*∧Ø *D*)∨(Ø*C*∧*D*))∧(Ø*B*∨Ø*C*)∧(Ø*C*∨Ø*D*)

Û(Ø*A*∨(*C*∧Ø *D*)∨(Ø*C*∧*D*))∧((Ø*B*∧Ø*C*)∨(Ø*B*∧Ø*D*)∨Ø*C*∨(Ø*C*∧Ø*D*))

Û(Ø*A*∧Ø*B*∧Ø*C*)∨(Ø*A*∧Ø*B*∧Ø*D*)∨(Ø*A*∧Ø*C*)∨(Ø*A*∧Ø*C*∧Ø*D*)

∨(*C*∧Ø *D*∧Ø*B*∧Ø*C*)∨(*C*∧Ø *D*∧Ø*B*∧Ø*D*)∨(*C*∧Ø *D*∧Ø*C*)∨(*C*∧Ø *D*∧Ø*C*∧Ø*D*)

∨(Ø*C*∧*D*∧Ø*B*∧Ø*C*)∨(Ø*C*∧*D*∧Ø*B*∧Ø*D*)∨(Ø*C*∧*D*∧Ø*C*)∨(Ø*C*∧*D*∧Ø*C*∧Ø*D*)

ÛF∨F∨(Ø*A*∧Ø*C*)∨F∨F∨(*C*∧Ø *D*∧Ø*B*)∨F∨F∨(Ø*C*∧*D*∧Ø*B*)∨F∨(Ø*C*∧*D*)∨F

Û(Ø*A*∧Ø*C*)∨(Ø*B*∧*C*∧Ø *D*)∨(Ø*C*∧*D*∧Ø*B*)∨(Ø*C*∧*D*)

Û(Ø*A*∧Ø*C*)∨(Ø*B*∧*C*∧Ø *D*)∨(Ø*C*∧*D*)

ÛT

故有三种派法：*B*∧*D*，*A*∧*C*，*A*∧*D*。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。

(

)：

是专家；

(

)：

是工人；

(

)：

是青年人；则推理化形式为：

(

)∧

(

))，

(

)

(

)∧

(

))

下面给出证明：

(1)

(

) P

(2)

(*c*) T(1)，ES

(3)

(

)∧

(

)) P

(4)

( *c*)∧

( *c*) T(3)，US

(5)

( *c*) T(4)，I

(6)

( *c*)∧

(*c*) T(2)(5)，I

(7)

(

)∧

(

)) T(6) ，EG

三、（10分）设*A*、*B*和*C*是三个集合，则*A*Ì*B*ÞØ(*B*Ì*A*)。

证明：*A*Ì*B*Û"*x*(*x*∈*A*→*x*∈*B*)∧$*x*(*x*∈*B*∧*x*Ï*A*)Û"*x*(*x*Ï*A*∨*x*∈*B*)∧$*x*(*x*∈*B*∧*x*Ï*A*)

ÛØ$*x*(*x*∈*A*∧*x*Ï*B*)∧Ø"*x*(*x*Ï*B*∨*x*∈*A*)ÞØ$*x*(*x*∈*A*∧*x*Ï*B*)∨Ø"*x*(*x*∈*A*∨*x*Ï*B*)

ÛØ($*x*(*x*∈*A*∧*x*Ï*B*)∧"*x*(*x*∈*A*∨*x*Ï*B*))ÛØ($*x*(*x*∈*A*∧*x*Ï*B*)∧"*x*(*x*∈*B*→*x*∈*A*))

ÛØ(*B*Ì*A*)。

四、（15分）设*A*＝\{1，2，3，4，5\}，*R*是*A*上的二元关系，且*R*＝\{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>\}，求*r*(*R*)、*s*(*R*)和*t*(*R*)。

解 *r*(*R*)＝*R*∪*IA*＝\{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>\}

*s*(*R*)＝*R*∪*R*－1＝\{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>\}

*R*2＝\{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>\}

*R*3＝\{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>\}

*R*4＝\{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>\}＝*R*2

*t*(*R*)＝

*Ri*＝\{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>\}。

五、（10分）*R*是非空集合*A*上的二元关系，若*R*是对称的，则*r*(*R*)和*t*(*R*)是对称的。

证明 对任意的*x*、*y*∈*A*，若*xr*(*R*)*y*，则由*r*(*R*)＝*R*∪*IA*得，*xRy*或*xIAy*。因*R*与*IA*对称，所以有*yRx*或*yIAx*，于是*yr*(*R*)*x*。所以*r*(*R*)是对称的。

下证对任意正整数*n*，*R*n对称。

因*R*对称，则有*xR*2*y*Û$*z*(*xRz*∧*zRy*)Û$*z*(*zRx*∧*yRz*)Û*yR*2*x*，所以*R*2对称。若

对称，则*x*

*y*Û$*z*(*x*

*z*∧*zRy*)Û$*z*(*z*

*x*∧*yRz*)Û*y*

*x*，所以

对称。因此，对任意正整数*n*，

对称。

对任意的*x*、*y*∈*A*，若*xt*(*R*)*y*，则存在*m*使得*xR*m*y*，于是有*yR*m*x*，即有*yt*(*R*)*x*。因此，*t*(*R*)是对称的。

六、（10分）若*f*：*A*→*B*是双射，则*f*－1：*B*→*A*是双射。

证明 因为*f*：*A*→*B*是双射，则*f*－1是*B*到*A*的函数。下证*f*－1是双射。

对任意*x*∈*A*，必存在*y*∈*B*使*f*(*x)*＝*y*，从而*f*－1(*y*)＝*x*，所以*f*－1是满射。

对任意的*y*1、*y*2∈*B*，若*f*－1(*y*1)＝*f*－1(*y*2)＝*x*，则*f*(*x)*＝*y*1，*f*(*x)*＝*y*2。因为*f*：*A→B*是函数，则*y*1＝*y*2。所以*f*－1是单射。

综上可得，*f*－1：*B*→*A*是双射。

七、（10分）设<*S*，\*>是一个半群，如果*S*是有限集，则必存在*a*∈*S*，使得*a*\**a*＝*a*。

证明 因为<*S*，\*>是一个半群，对任意的*b*∈*S*，由\*的封闭性可知，*b*2＝*b*\**b*∈*S*，*b*3＝*b*2\**b*∈*S*，…，*bn*∈*S*，…。

因为*S*是有限集，所以必存在*j*＞*i*，使得

＝

。令*p*＝*j*－*i*，则

＝

。所以对*q*≥*i*，有

＝

。

因为*p*≥1，所以总可找到*k*≥1，使得*kp*≥*i*。对于

∈*S*，有

＝

\*(

)＝…＝

。

令*a*＝，则*a*∈*S*且*a*\**a*＝*a*。

八、（20分）（1）若*G*是连通的平面图，且*G*的每个面的次数至少为*l*(*l*≥3)，则*G*的边数*m*与结点数*n*有如下关系：

*m*≤

(*n*－2)。

证明 设*G*有*r*个面，则2*m*＝

≥*lr*。由欧拉公式得，*n－m*＋*r*＝2。于是， *m*≤

(*n*－2)。

（2）设平面图*G*＝<*V*，*E*，*F*>是自对偶图，则| *E*|＝2(|*V*|－1)。

证明 设*G*\*＝<*V*\*，*E*\*>是连通平面图*G*＝<*V*，*E*，*F*>的对偶图，则*G*\*@ *G*，于是|*F*|＝|*V*\*|＝|*V*|，将其代入欧拉公式|*V*|－|*E*|＋|*F*|＝2得，|*E*|＝2(|*V*|－1)。

**离散数学试题（B卷及答案）**

一、（10分）证明(*P*∨*Q*)∧(*P*®*R*)∧(*Q*®*S*)

*S*∨*R*

证明 因为*S*∨*R*ÛØ*R*®*S*，所以，即要证(*P*∨*Q*)∧(*P*®*R*)∧(*Q*®*S*)

Ø*R*®*S*。

(1)Ø*R* 附加前提

(2)*P*®*R* *P*

(3)Ø*P* *T*(1)(2)，*I*

(4)*P*∨*Q* *P*

(5)*Q* *T*(3)(4)，*I*

(6)*Q*®*S* *P*

(7)*S* *T*(5)(6)，*I*

(8)Ø*R*®*S* *CP*

(9)*S*∨*R* *T*(8)，*E*

二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。

设*P*(*e*)：*e*是考生，*Q*(*e*)：*e*将有所作为，*A*(*e*)：*e*是勤奋的，*B*(*e*)：*e*是聪明的，个体域：人的集合，则命题可符号化为："*x*(*P*(*x*)®(*A*(*x*)∨*B*(*x*)))，"*x*(*A*(*x*)®*Q*(*x*))，Ø"*x*(*P*(*x*)®*Q*(*x*))

$*x*(*P*(*x*)∧*B*(*x*))。

(1)Ø"*x*(*P*(*x*)®*Q*(*x*)) *P*

(2)Ø"*x*(Ø*P*(*x*)∨*Q*(*x*)) *T*(1)，*E*

(3)$*x*(*P*(*x*)∧Ø*Q*(*x*)) *T*(2)，*E*

(4)*P*(*a*)∧Ø*Q*(*a*) *T*(3)，*ES*

(5)*P*(*a*) *T*(4)，*I*

(6)Ø*Q*(*a*) *T*(4)，*I*

(7)"*x*(*P*(*x*)®(*A*(*x*)∨*B*(*x*)) *P*

(8)*P*(*a*)®(*A*(*a*)∨*B*(*a*)) *T*(7)，*US*

(9)*A*(*a*)∨*B*(*a*) *T*(8)(5)，*I*

(10)"*x*(*A*(*x*)®*Q*(*x*)) *P*

(11)*A*(*a*)®*Q*(*a*) *T*(10)，*US*

(12)Ø*A*(*a*) *T*(11)(6)，*I*

(13)*B*(*a*) *T*(12)(9)，*I*

(14)*P*(*a*)∧*B*(*a*) *T*(5)(13)，*I*

(15)$*x*(*P*(*x*)∧*B*(*x*)) *T*(14)，*EG*

三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。

解 设*A*、*B*、*C*分别表示会打排球、网球和篮球的学生集合。则：

|*A*|＝12，|*B*|＝6，|*C*|＝14，|*A*∩*C*|＝6，|*B*∩*C*|＝5，|*A*∩*B*∩*C*|＝2，|(*A*∪*C*)∩*B*|＝6。

因为|(*A*∪*C*)∩*B*|＝(*A*∩*B*)∪(*B*∩*C*)|＝|(*A*∩*B*)|＋|(*B*∩*C*)|－|*A*∩*B*∩*C*|＝|(*A*∩*B*)|＋5－2＝6，所以|(*A*∩*B*)|＝3。于是|*A*∪*B*∪*C*|＝12＋6＋14－6－5－3＋2＝20，

＝25－20＝5。故，不会打这三种球的共5人。

四、（10分）设*A*1、*A*2和*A*3是全集*U*的子集，则形如

*Ai*¢(*Ai*¢为*Ai*或

)的集合称为由*A*1、*A*2和*A*3产生的小项。试证由*A*1、*A*2和*A*3所产生的所有非空小项的集合构成全集*U*的一个划分。

证明 小项共8个，设有*r*个非空小项*s*1、*s*2、…、*sr*(*r*≤8)。

对任意的*a*∈*U*，则*a*∈*A*i或*a*∈

，两者必有一个成立，取*A*i¢为包含元素*a*的*A*i或

，则*a*∈

*Ai*¢，即有*a*∈

*si*，于是*U*Í

*si*。又显然有

*si*Í*U*，所以*U*＝

*si*。

任取两个非空小项*sp*和*sq*，若*sp*≠*sq*，则必存在某个*Ai*和

分别出现在*sp*和*sq*中，于是*sp*∩*sq*＝Æ。

综上可知，\{ *s*1，*s*2，…，*sr*\}是*U*的一个划分。

五、（15分）设*R*是*A*上的二元关系，则：*R*是传递的Û*R*\**R*Í*R*。

证明 (5)若*R*是传递的，则<*x*，*y*>∈*R*\**R*Þ$*z*(*xRz*∧*zSy*)Þ*xRc*∧*cSy*，由*R*是传递的得*xRy*，即有<*x*，*y*>∈*R*，所以*R*\**R*Í*R*。

反之，若*R*\**R*Í*R*，则对任意的*x*、*y*、*z*∈*A*，如果*xRz*且*zRy*，则<*x*，*y*>∈*R*\**R*，于是有<*x*，*y*>∈*R*，即有*xRy*，所以*R*是传递的。

六、（15分）若*G*为连通平面图，则*n*－*m*＋*r*＝2，其中，*n*、*m*、*r*分别为*G*的结点数、边数和面数。

证明 对*G*的边数*m*作归纳法。

当*m*＝0时，由于*G*是连通图，所以*G*为平凡图，此时*n*＝1，*r*＝1，结论自然成立。

假设对边数小于*m*的连通平面图结论成立。下面考虑连通平面图*G*的边数为*m*的情况。

设*e*是*G*的一条边，从*G*中删去*e*后得到的图记为*G*¢，并设其结点数、边数和面数分别为*n*¢、*m*¢和*r*¢。对*e*分为下列情况来讨论：

若*e*为割边，则*G*¢有两个连通分支*G*1和*G*2。*Gi*的结点数、边数和面数分别为*ni*、*mi*和*ri*。显然*n*1＋*n*2＝*n*¢＝*n*，*m*1＋*m*2＝*m*¢＝*m*－1，*r*1＋*r*2＝*r*¢＋1＝*r*＋1。由归纳假设有*n*1－*m*1＋*r*1＝2，*n*2－*m*2＋*r*2＝2，从而(*n*1＋*n*2)－(*m*1＋*m*2)＋(*r*1＋*r*2)＝4，*n*－(*m*－1)＋(*r*＋1)＝4，即*n*－*m*＋*r*＝2。

若*e*不为割边，则*n*¢＝*n*，*m*¢＝*m*－1，*r*¢＝*r*－1，由归纳假设有*n*¢－*m*¢＋*r*¢＝2，从而*n*－(*m*－1)＋*r*－1＝2，即*n*－*m*＋*r*＝2。

由数学归纳法知，结论成立。

七、（10分）设函数*g*：*A*→*B*，*f*：*B*→*C*，则：

(1)*f*o*g*是*A*到*C*的函数；

(2)对任意的*x*∈*A*，有*f*o*g*(*x*)＝*f*(*g*(*x*))。

证明 (1)对任意的*x*∈*A*，因为*g*：*A*→*B*是函数，则存在*y*∈*B*使<*x*，*y*>∈*g*。对于*y*∈*B*，因*f*：*B*→*C*是函数，则存在*z*∈*C*使<*y*，*z*>∈*f*。根据复合关系的定义，由<*x*，*y*>∈*g*和<*y*，*z*>∈*f*得<*x*，*z*>∈*g*\**f*，即<*x*，*z*>∈*f*o*g*。所以*Df*o*g*＝*A*。

对任意的*x*∈*A*，若存在*y*1、*y*2∈*C*，使得<*x*，*y*1>、<*x*，*y*2>∈*f*o*g*＝*g*\**f*，则存在*t*1使得<*x*，*t*1>∈*g*且<*t*1， *y*1>∈*f*，存在*t*2使得<*x*，*t*2>∈*g*且<*t*2，*y*2>∈*f*。因为*g*：*A*→*B*是函数，则*t*1＝*t*2。又因*f*：*B*→*C*是函数，则*y*1＝*y*2。所以*A*中的每个元素对应*C*中惟一的元素。

综上可知，*f*o*g*是*A*到*C*的函数。

(2)对任意的*x*∈*A*，由*g*：*A*→*B*是函数，有<*x*，*g*(*x*)>∈*g*且*g*(*x*)∈*B*，又由*f*：*B*→*C*是函数，得<*g*(*x*)，*f*(*g*(*x*))>∈*f*，于是<*x*，*f*(*g*(*x*))>∈*g*\**f*＝*f*o*g*。又因*f*o*g*是*A*到*C*的函数，则可写为*f*o*g*(*x*)＝*f*(*g*(*x*))。

八、（15分）设<*H*，\*>是<*G*，\*>的子群，定义*R*＝\{<*a*，*b*>|*a*、*b*∈*G*且*a*－1\**b*∈*H*\}，则*R*是*G*中的一个等价关系，且\[*a*\]*R*＝*aH*。

证明 对于任意*a*∈*G*，必有*a*－1∈*G*使得*a*－1\**a*＝*e*∈*H*，所以<*a*，*a*>∈*R*。

若<*a*，*b*>∈*R*，则*a*－1\**b*∈*H*。因为*H*是*G*的子群，故(*a*－1\**b*)－1＝*b*－1\**a*∈*H*。所以<*b*，*a*>∈*R*。

若<*a*，*b*>∈*R*，<*b*，*c*>∈*R*，则*a*－1\**b*∈*H*，*b*－1\**c*∈*H*。因为*H*是*G*的子群，所以(*a*－1\**b*)\*(*b*－1\**c*)＝*a*－1\**c*∈*H*，故<*a*，*c*>∈*R*。

综上可得，*R*是*G*中的一个等价关系。

对于任意的*b*∈\[*a*\]*R*，有<*a*，*b*>∈*R*，*a*－1\**b*∈*H*，则存在*h*∈*H*使得*a*－1\**b*＝*h*，*b*＝*a*\**h*，于是*b*∈*aH*，\[*a*\]*R*Í*aH*。对任意的*b*∈*aH*，存在*h*∈*H*使得*b*＝*a*\**h*，*a*－1\**b*＝*h*∈*H*，<*a*，*b*>∈*R，*故*aH*Í\[*a*\]*R*。所以，\[*a*\]*R*＝*aH*。