离散数学试题及答案 ╰+哭是因爲堅強的太久メ 2024-03-24 14:42 24阅读 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) 3 2 3 2 0 0 1 1 试求 (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\}\}. 2. . 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. (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*。
还没有评论，来说两句吧...