《离散数学》同步练习答案.docx

离散数学同步练习答案华南理工大学网络教育学院 离散数学练习题参考答案 第一章命题逻辑 一填空题 设：p：派小王去开会。q：派小李去开会。则命题： “派小王或小李中的一人去开会” 可符号化 为： (pÚØq) Ù (ØpÚq) 。 设A，B都是命题公式，AÞB，则A®B的真值是 T 。 设：p：刘平聪明。q：刘平用功。在命题逻辑中，命题： “刘平不但不聪明，而且不用功” 可符号化为： pÙ q 。 设A , B 代表任意的命题公式，则蕴涵等值式为 A ® BÛØA Ú B 。 设，p：径一事；q：长一智。在命题逻辑中，命题： “不径一事，不长一智。” 可符号化为： Ø p®Øq 。 设A , B 代表任意的命题公式，则德 · 摩根律为 ØÛ ØA Ú ØB） 。 设，p：选小王当班长；q：选小李当班长。则命题：“选小王或小李中的一人当班长。” 可符号化为： (pÚØq) Ù (ØpÚq) 。 设，P：他聪明；Q：他用功。在命题逻辑中，命题： “他既聪明又用功。” 可符号化为： PÙ Q 。 对于命题公式A，B，当且仅当 A ® B 是重言式时，称“A蕴含B”，并记为AÞB。 设：P：我们划船。Q：我们跑步。在命题逻辑中，命题： “我们不能既划船又跑步。” 可符号化为： Ø (PÙ Q) 。 设P , Q 是命题公式，德·摩根律为： ØÛ ØP ÙØ Q） 。 设 P：你努力。Q：你失败。在命题逻辑中，命题：“除非你努力，否则你将失败。” 可符号化为： ØP®Q 。 设 p：小王是100米赛跑冠军。q：小王是400米赛跑冠军。在命题逻辑中，命题：“小王是100米或400米赛跑冠军。” 可符号化为： p Úq 。 设A，C为两个命题公式，当且仅当 A®C 为一重言式时，称C可由A逻辑地推出。 二判断题 1. 设A，B是命题公式，则蕴涵等值式为A®BÛØAÙB。 2. 命题公式ØpÙqÙØr是析取范式。 3. 陈述句“x + y > 5” 是命题。 4. 110 (p=1,q=1, r=0)是命题公式 (Ø(pÙq)®r)Úq 的成真赋值。 5. 命题公式 p®(ØpÙq) 是重言式。 6. 设A，B都是合式公式，则AÙB®ØB也是合式公式。 7. AÚ(BÙC)Û( AÚB)Ú(AÚC)。 8. 陈述句“我学英语，或者我学法语” 是命题。 9. 命题“如果雪是黑的，那么太阳从西方出”是假命题。 10. “请不要随地吐痰！” 是命题。 11. P ® Q Û Ø P Ù Q 。 12. 陈述句“如果天下雨，那么我在家看电视” 是命题。 13. 命题公式Ú是析取范式。 14. 命题公式 (PÙØQ)Ú R Ú (ØPÙQ) 是析取范式。 三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。 1设：P：天下雪。Q：他走路上班。则命题“只有天下雪，他才走路上班。”可符号化为 。 P®Q Q ® P Ø Q ®Ø P Q ÚØP 2(1 ) 明年国庆节是晴天。 (2 ) 在实数范围内，x+y3。 (3 ) 请回答这个问题！ (4 ) 明天下午有课吗？ 在上面句子中，是命题的只有 (1 ) 。 3命题公式A与B是等值的，是指 (4 ) 。 A与B有相同的命题变元 A«B是可满足式 A®B为重言式 A«B为重言式 4(1 ) 雪是黑色的。 (2 ) 这朵花多好看呀！。 (3 ) 请回答这个问题！ (4 ) 明天下午有会吗？ 在上面句子中，是命题的是 (1 ) 。 5设：P：天下大雨。Q：他乘公共汽车上班。则命题“只要天下大雨，他就乘公共汽车上班。” 可符号化为 。 Q®P P ® Q Ø Q ®Ø P Q ÚØP 6设：P：你努力；Q：你失败。则命题“除非你努力，否则你将失败。” 在命题逻辑中可符号化为 。 Q®P P ® Q Ø P ®Q Q ÚØP 7(1 ) 现在开会吗？ (2 ) 在实数范围内，x+y >5。 (3 ) 这朵花多好看呀！ (4 ) 离散数学是计算机科学专业的一门必修课。 在上面语句中，是命题的只有 (4 ) 。 8设：P：天气好。Q：他去郊游。则命题“如果天气好，他就去郊游。” 可符号化为 P®Q Q ® P Ø Q ®Ø P Q ÚØP 9下列式子是合式公式的是 。 Ø） Ù Q ® R 10 1101110 中国人民是伟大的。 全体起立！ 计算机机房有空位吗？ 在上面句子中，是命题的是 。 11 设：P：他聪明；Q：他用功。则命题“他虽聪明但不用功。” 在命题逻辑中可符号化为 。 P Ù Q P ® Q P Ú ØQ P ÙØQ 12 (1 ) 如果天气好，那么我去散步。 (2 ) 天气多好呀！ (3 ) x=3。 (4 ) 明天下午有会吗？ 在上面句子中 (1 ) 是命题。 13 设：P：王强身体很好；Q：王强成绩很好。命题“王强身体很好，成绩也很好。”在命题逻辑中可符号化为 。 P Ú Q P ® Q P ÙØQ P Ù Q 四、解答题 1设命题公式为®。 求此命题公式的真值表； 给出它的析取范式； p q p pq qp T T F T F T F F T T F T T T T F F T F T ® Û Û ÛØqØp 2设命题公式为Ù。求此命题公式的真值表； 给出它的析取范式； p q r pq pÚr T T T T T T T F T T T F T F T T F F F T F T T T T F T F T F F F T T T F F F T F ® F T T T p ® q）Ù T T F F T F T F Ù ÛÙ Û(ØpÚq)Ùp )Ú(ØpÚq)Ùr) Û(ØpÙp ) Ú(qÙp)Ú(ØpÙr) Ú(qÙr) Û (qÙp)Ú(ØpÙr) Ú(qÙr) 3设命题公式为 (Ø Q Ù)® Ø P。 求此命题公式的真值表； 求此命题公式的析取范式； (1) P Q Q PQ P Q T T F T F F T F T F F F F T F T T F F F T T T T (2) 解：(Ø Q Ù)® Ø P Û(Ø Q Ù）® Ø P Û(Ø Q Ù）Ø P Û）Ø P ÛQ Ø P 4完成下列问题 求命题公式）S的析取范式。解：）S Û）S Û）S Û）S (Q)P T T T T ÛPS ÛPS 5设命题公式为）® Q。 求此命题公式的真值表； 求此命题公式的析取范式； P Q PQ P T T T T T F F F F T T F F F T F 解：）Q Û）Q Û）Q Û）Q ÛPQ ÛPQ 6设命题公式为ÙØP）® Q。求此命题公式的真值表； 给出它的析取范式； P Q PQ P P T T T F F T F T F F F F F T F F T T T T P Ù）® Q T T T T P）Q T T T T 解：ÙØP）® Q ÛÙØP）Q Û）Q ÛPQ）PQ ÛT 7用直接证法证明 前提：P Ú Q，P ® R，Q ® S 结论：S R 证明： 1）PQ P 2） PQ T 1）E 3）QS P 4）PS T 2）3）I 5）SP T 4）E 6）PR P 7）SR T 5）6）I 8）SR T 7）E 8用直接证法证明 前提：P ® (Q Ú R)，S ® Ø Q，P，S。 结论：R 证明： 1）P ® (Q Ú R) P 2） P P 3）(Q Ú R) T 2）3）I 4）S ® Ø Q P 5）S P 6）Ø Q T 4）5）I 7）R T 3）6）E 第二章谓词逻辑 一填空题 若个体域是含三个元素的有限域a，b，c，则 $xA(x)Û A(a) Ú A(b) Ú A(c) 取全总个体域，令F(x)：x为人,G(x)：x爱看电影。则命题“没有不爱看电影的人。”可符号化为_Ø($x(F(x) Ù G(x)_。 若个体域是含三个元素的有限域a，b，c，则 "xA(x)Û A(a) Ù A(b) Ù A(c) 。 取全总个体域，令M(x)：x是人,G(y)：y是花, H(x,y)：x喜欢y。则命题“有些人喜欢所有的花。”可符号化为 $x(M(x)Ù("y(G(y)® H(x,y)。 取个体域为全体人的集合。令F(x)：x在广州工作,G(x)：x是广州人。在一阶逻辑中，命题“在广州工作的人未必都是广州人。”可符号化为_"x(F(x) ® G(x)_。 P(x)：x是学生，Q(x)：x要参加考试。在谓词逻辑中，命题： “每个学生都要参加考试” 可符号化为： "x(P(x) ® Q(x) 。 M(x)：x是人，B(x)：x勇敢。则命题“有人勇敢，但不是所有的人都勇敢”谓词符号化为 _$x(M(x)Ù B(x) Ù"x(M(x) ® B(x)_。 P(x)：x是人，M(x)：x聪明。则命题“尽管有人聪明，但不是一切人都聪明”谓词符号化为 _$x(P(x)Ù M(x) Ù"x(P(x) ® M(x)_。 I(x)：x是实数，R(x)：x是正数，N(x)：x是负数。在谓词逻辑中，命题： “任何实数或是正的或是负的” 可符号化为： "x(I(x) ® (R(x) Ú N(x) 。 P(x)：x是学生，Q(x)：x要参加考试。在谓词逻辑中，命题： “每个学生都要参加考试” 可符号化为： "x(P(x) ® Q(x) 。 令M(x)：x是大学生,P(y)：y是运动员, H(x, y)：x钦佩y。则命题“有些大学生不钦佩所有运动员。”可符号化为_$x(M(x)Ù("y(P(y)® H(x,y)_。 二判断题 1. 设A，B都是谓词公式，则"x A«ØB也是谓词公式。 2. 设c是个体域中某个元素，A是谓词公式，则A(c)Þ "xA(x)。 3. "x"yA(x,y)Û "y"xA(x,y) 。 4. "x$yA(x,y)Û $y"xA(x,y) 。 5. 取个体域为整数集，则谓词公式"x"y(x ´ y = y ) 是假命题。 6. ("x)Û ("x)。 7. 命题公式 (PÙØQÚ R) Ú (ØPÙQ) 是析取范式。 8. 谓词公式("x)(A (x) ® B(x, y) ÙR(x) 的自由变元为x, y。 9. A® B）Û® B）。 10. R(x)：“x是大学生。” 是命题。 三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。 1设F：x是火车，G：x是汽车，H：x比y快。命题“某些汽车比所有火车慢”的符号化公式是 (2) 。 $y®"xÙH） $yÙ"x®H） "x $y®ÙH） $y®"x®H） 2设个体域为整数集，下列真值为真的公式是 。 $y"x (x y =2) "x"y(x y =2) "x$y(x y =2) $x"y(x y =2) 3设F：x是人，G：x早晨吃面包。命题“有些人早晨吃面包”在谓词逻辑中的符号化公式是 。 ® G） Ù G） ® G） Ù G） 5下列式子中正确的是 。 ØPÛP ØPÛØ P ØPÛØ P ØPÛØ P 6下面谓词公式是永真式的是 b) 。 a) P® Q b) P®P c) P®P d) Ø P®P 5设S：x是运动员，J：y是教练员，L：x钦佩y。命题“所有运动员都钦佩一些教练员”的符号化公式是 c) 。 a) "xÙ " yÙ L） b) "x $y®® L） c) "x® $yÙ L） d) $y"x®Ù L） 6下列式子是合式公式的是 。 Ø） Ù Q ® Ù R 7下列式子中正确的是 。 ØPÛP ØPÛØ P ØPÛØ P ØPÛØ P 四、解答题 1构造下面推理的证明： 前提：$ x F®"yÚ G）® R）， $ x F。 结论：$ x R。 证明： $ x F®"yÚ G）® R） 前提引入 $ x F 前提引入 "yÚ G）® R） 假言推理 F EI FÚ G 附加 Ú G）® R UI R 假言推理 $ x R EG 2在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令F(x)：x喜欢步行，G(x)：x喜欢坐汽车，H(x)：x喜欢骑自行车。 前提： "x® ØG）, "xÚ H）, $ x (Ø H) 结论：$ x (Ø F) 证明 $ x (Ø H) 前提引入 Ø H EI "xÚ H） 前提引入 GÚ H UI G "x® ØG） 前提引入 F® ØG UI Ø F $ x (Ø F) EG 3在命题逻辑中构造下面推理的证明： 如果他是理科学生，他必须学好数学。如果他不是文科学生，他必是理科学生。他没学好数学，所以他是文科学生。 令F(x)：x是理科学生，G(x)：x学好数学，H(x)：x是文科学生。 前提： "x® G）, "x）, $ x (ØG) 结论：$ x (H(x) 证明 "x® G） 前提引入 $ x (ØG) 前提引入 $ x (ØF) TI "x） 前提引入 $ x (H(x) TI 4用直接证法证明： 前提： WR），Q） 结论：R）。 推理： 1) ("x)(C(x) W(x) R(x) P 2) ($x)(C(x) Q(x) p 3) C(a) Q(a) ES2) 4) C(a) W(a) R(a) US1) 5) C(a) T3)I 6) W(a) R(a) T4)5)I 7) Q(a) T3)I 8) R(a) T6)I 9) Q(a) R(a) T7)8)I 10) ($x)(Q(x) R(x) EG9) 第三章集合与关系 一填空题 如果|A|n，那么|A×A| n2 。A上的二元关系有_2n_2个。 集合A上关系R的自反闭包r=_RÈI_。 设集合A上的关系R和S，R=，S=，则SR= (1,2), (2,2), (2,3) 。 如果|A|n，那么|P(A)| 2n 。 设集合A上的关系R和S，R=<1，2>，<2，1>，<3，4>，<4，3>，S=<1，3>，<3，1>，<2，4>，<4，2>，则RS= <1,4>, <2,3>, <3,2>, <4,1> 。 设集合E=a, b, c，E的幂集P(E) _。 设R是定义在集合X上的二元关系，如果对于每个x, yÎX， _ _ _ ，则称集合X上的关系R是对称的。 设关系R和S为，R=<1，2>，<3，4>，<2，2>，S=<4，2>，<2，5>，<3，1>，<1，3>，则RS =_ _ _ _。 设R是定义在集合X上的二元关系，如果对于每个x, yÎX， _ _ _ ，则称集合X上的关系R是自反的。 二判断题 1设A、B、C为任意的三个集合，则A×(B×C)=A×(B×C)。 2设S，T是任意集合，如果S -T = Æ，则S = T。 3集合A=1,2,3,4上的关系<1,2>,<2,3>,<2,4>,<3,4>是一个函数。 4集合A=1，2，3，4上的整除关系是等价关系。 5集合A 的幂集P(A)上的包含关系是偏序关系。 6设A=a, b, c, RÎ A×A且R=< a, b>,< a, c>, 则R是传递的。 6设A，B是任意集合，如果B ¹ Æ，则A B ¹ A。 7集合A=1,2,3上的关系<1,1>,<2,2>,<3,3>,<1,2>是传递的。 8集合A=1，2，3，4上的小于关系是等价关系。 9关系<x1, x2>½x1, x2ÎN, x1+x2<6能构成一个函数。 10集合A 上的恒等关系是偏序关系。 11集合A=1,2,3上的关系S=<1,1>,<1,2>,<3,2>,<3,3>是自反的。 12设X=1, 2, 3, Y=a, b, c。函数F=<1, a>,<2, c>,<3, b>是双射。 13集合A上的关系R的自反闭包r(R)=RIA。 14集合A上的偏序关系R是自反的、对称的、传递的。 15. 设A，B是任意集合，则A Å B (A-B) (B-A)。 三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。 1设A=a，b，c，B=a，b，则下列命题不正确的是 a) 。 a) AB=a，b b) AB= a，b c) AÅB=c d) BÍA 2设 A = a, b, c, d, A 上的关系R = <a, b>, <b, a>, <b, c>, <c, d>，则它的对称闭包为 c) 。 a) R = <a, a>, <a, b>, <b, b>, <b, a>, <b, c>, <c, c>, <c, d>， b) R = <a, b>, <b, a>, <b, c>, <c, b>, <c, d>， c) R = <a, b>, <b, a>, <b, c>, <c, d>, <c, b>, <d, c>， d) R = <a, a>, <a, b>, <b, a>, <b, c>, <c, d>, <d, c>， 3对于集合1, 2, 3, 4上的关系是偏序关系的是 a) 。 a) R=<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,3>,<2,4>,<3,3>,<3,4>,<4,4> b) R=<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,1>,<2,4>,<3,1>,<3,4>,<4,4> c) R=<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,1>,<3,1>,<3,3>,<4,1>,<4,4> d) R=<2,1>,<1,2>,<1,3>,<1,4>,<2,2>, <4,3>,<2,4>,<3,3>,<3,4>,<4,4> 4设A=1，2，3，4，5，B=6，7，8，9，10，以下哪个关系是从A到B的单射函数 b) 。 a) f =<1，7>，<2，6>，<3，5>，<1，9>，<5，10> b) f =<1，8>，<2，6>，<3，7>，<4，9>，<5，10> c) f =<1，7>，<2，6>，<3，5>，<4，6> d) f =<1，10>，<2，6>，<3，7>，<4，8>，<5，10> 5设 A = a, b, c，要使关系<a, b>, <b, c>, <c, a>, <b, a>R 具有对称性，则 d) 。 a) R = <c, a>, <a, c> b) R = <c, b>, <b, a> c) R = <c, a>, <b, a> d) R = <c, b>, <a, c> 6设S=F，1，1，2，则S的幂集P有 (4) 个元素 3 6 7 8 7设R为定义在集合A上的一个关系，若R是 ，则R为等价关系 。 反自反的，对称的和传递的 自反的，对称的和传递的 自反的，反对称的和传递的 对称的，反对称的和传递的 8设S，T，M为任意集合，下列命题正确的是 c) 。 a) 如果ST = SM，则T = M b) 如果S-T = F，则S = T c) S-T Í S d) S Å S = S 9设 A = a, b, c，要使关系<a, b>, <b, c>, <c, a>, <b, a>R 具有对 性，则 。 R = <c, a>, <a, c> R = <c, b>, <b, a> R = <c, a>, <b, a> R = <c, b>, <a, c> 10设A=1，2，3，4，5，B=a，b，c，d，e，以下哪个函数是从A到B的入射函数 b) 。 a) F =<1，b>，<2，a>，<3，c>，<1，d>，<5，e> b) F=<1，c>，<2，a>，<3，b>，<4，e>，<5，d> c) F =<1，b>，<2，a>，<3，d>，<4，a> d) F=<1，e>，<2，a>，<3，b>，<4，c>，<5，e> 四、解答题 1已知偏序集，其中A=a，b，c，d，e，“”为， ，IA。 画出偏序集的哈斯图。 求集合A的极大元，极小元，最大元，最小元。 (1) e b c d a 集合A的极大元是e，极小元a，最大元e，最小元a。 2设R是集合A = 1, 2, 3, 4, 5, 6, 7, 8, 9上的整除关系。 给出关系R；画出关系R的哈斯图； 指出关系R的最大、最小元，极大、极小元。 R=<1,1>,<1,2> , <1,3>, <1,4>, <1,5>, <1,6>, <1,7>, <1,8>, <1,9>, <2,2>, <2,4>, <2,6>, <2,8>, <3,3>, <3,6>, <3,9>, <4,4>, <4,8>, <5,5>, <6,6>, <7,7>, <8,8>, <9,9> (2) 8 4 2 9 6 3 5 7 1 关系R的无最大，最小元是1，极大元是8和9，极小元是1。 3设R是集合A = 1, 2, 3, 4, 6, 12上的整除关系。 给出关系R； 给出COV A 画出关系R的哈斯图； 给出关系R的极大、极小元、最大、最小元。 R=<1,1>,<1,2> , <1,3>, <1,4>, <1,6>, <1,12>, <2,2>, <2,4>, <2,6>, <2,12>, <3,3>, <3,6>, <3,12>, <4,4>, <4,12>, <6,6>, <6,12>, <12,12> (2) COV A=<1,2> , <1,3>,<2,4>, <2,6> <3,6> <4,12>, <6,6>, <12,12> (3) 12 6 3 4 2 1 关系R的极大、最大元是12，极小元、最小元是1。 第五章代数结构 一填空题 集合S的幂集P(S)关于集合的并运算“”的零元为 _S_。 集合S的幂集P(S)关于集合的并运算“”的零元为 _f_。 集合S的幂集P(S)关于集合的并运算“”的么元为 _f_。 一个代数系统S, * ，其中S是非空集合。*是S上的一个二元运算，如果 * 在S上是封闭的 ，则称代数系统S, * 为广群。 二判断题 1含有零元的半群称为独异点。 2运算“”是整数集I上的普通加法，则群<I, >的么元是1。 三、填空题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。 1下列群一定为循环群的是 e) 。 e) <I，> f) <R0，×> g) <Q，> h) <P，Å > 是集合S的幂集，“Å”为对称差） 2运算“”是整数集I上的普通减法，则代数系统 <I, > 满足下列 性质 。 结合律 交换律 有零元 封闭性 3设I是整数集，N是自然数集，P是S的幂集，“×，”是普通的乘法，加法和集合的交运算。下面代数系统中 是群。 <I，×> <I，> <P(S)，> <N，+> 4下列代数系统不是群的是 。 <I，> <P，> 是集合S的幂集，“”为交运算） <Q，> <P，Å > 是集合S的幂集，“Å”为对称差） 第七章图论 一填空题 一个无向图G=是二部图当且仅当G中无 奇数 长度的回路。 任何图(无向的或有向的)中，度为奇数的顶点个数为 偶数 。 设D是一个有向图，若D中任意一对顶点都是相互可达的，则称D是_双向连通的_。 既不含平行边，也不含环的图称为 简单图 。 经过图中 每条边 一次且仅一次并的回路，称为欧拉回路。 一棵有n个顶点的树含有_n1_边。 设G =，G¢ =是两个图，若 V= V 且 EÍ E ，称G¢是G的生成子图。 经过图中 每个结点 一次且仅一次的回路，称为哈密尔顿回路。 二判断题 15个顶点的有向完全图有20条边。 2连通无向图的欧拉回路经过图中的每个顶点一次且仅一次。 3图中的初级通路都是简单通路。 4已知n (n³2)阶无向简单图G有n 1条边，则G一定为树。 5n阶无向完全图Kn的每