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

《《离散数学》同步练习答案.docx》由会员分享，可在线阅读，更多相关《《离散数学》同步练习答案.docx（25页珍藏版）》请在三一办公上搜索。

1、离散数学同步练习答案华南理工大学网络教育学院 离散数学练习题参考答案 第一章命题逻辑 一填空题 设：p：派小王去开会。q：派小李去开会。则命题： “派小王或小李中的一人去开会” 可符号化 为： (pq) (pq) 。 设A，B都是命题公式，AB，则AB的真值是 T 。 设：p：刘平聪明。q：刘平用功。在命题逻辑中，命题： “刘平不但不聪明，而且不用功” 可符号化为： p q 。 设A , B 代表任意的命题公式，则蕴涵等值式为 A BA B 。 设，p：径一事；q：长一智。在命题逻辑中，命题： “不径一事，不长一智。” 可符号化为： pq 。 设A , B 代表任意的命题公式，则德 摩根律为

2、A B） 。 设，p：选小王当班长；q：选小李当班长。则命题：“选小王或小李中的一人当班长。” 可符号化为： (pq) (pq) 。 设，P：他聪明；Q：他用功。在命题逻辑中，命题： “他既聪明又用功。” 可符号化为： P Q 。 对于命题公式A，B，当且仅当 A B 是重言式时，称“A蕴含B”，并记为AB。 设：P：我们划船。Q：我们跑步。在命题逻辑中，命题： “我们不能既划船又跑步。” 可符号化为： (P Q) 。 设P , Q 是命题公式，德摩根律为： P Q） 。 设 P：你努力。Q：你失败。在命题逻辑中，命题：“除非你努力，否则你将失败。” 可符号化为： PQ 。 设 p：小王是10

3、0米赛跑冠军。q：小王是400米赛跑冠军。在命题逻辑中，命题：“小王是100米或400米赛跑冠军。” 可符号化为： p q 。 设A，C为两个命题公式，当且仅当 AC 为一重言式时，称C可由A逻辑地推出。 二判断题 1. 设A，B是命题公式，则蕴涵等值式为ABAB。 2. 命题公式pqr是析取范式。 3. 陈述句“x + y 5” 是命题。 4. 110 (p=1,q=1, r=0)是命题公式 (pq)r)q 的成真赋值。 5. 命题公式 p(pq) 是重言式。 6. 设A，B都是合式公式，则ABB也是合式公式。 7. A(BC)( AB)(AC)。 8. 陈述句“我学英语，或者我学法语” 是

4、命题。 9. 命题“如果雪是黑的，那么太阳从西方出”是假命题。 10. “请不要随地吐痰！” 是命题。 11. P Q P Q 。 12. 陈述句“如果天下雨，那么我在家看电视” 是命题。 13. 命题公式是析取范式。 14. 命题公式 (PQ) R (PQ) 是析取范式。 三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。 1设：P：天下雪。Q：他走路上班。则命题“只有天下雪，他才走路上班。”可符号化为 。 PQ Q P Q P Q P 2(1 ) 明年国庆节是晴天。 (2 ) 在实数范围内，x+y3。 (3 ) 请回答这个问题！ (4 ) 明天下午有课吗

5、？ 在上面句子中，是命题的只有 (1 ) 。 3命题公式A与B是等值的，是指 (4 ) 。 A与B有相同的命题变元 AB是可满足式 AB为重言式 AB为重言式 4(1 ) 雪是黑色的。 (2 ) 这朵花多好看呀！。 (3 ) 请回答这个问题！ (4 ) 明天下午有会吗？ 在上面句子中，是命题的是 (1 ) 。 5设：P：天下大雨。Q：他乘公共汽车上班。则命题“只要天下大雨，他就乘公共汽车上班。” 可符号化为 。 QP P Q Q P Q P 6设：P：你努力；Q：你失败。则命题“除非你努力，否则你将失败。” 在命题逻辑中可符号化为 。 QP P Q P Q Q P 7(1 ) 现在开会吗？ (

6、2 ) 在实数范围内，x+y 5。 (3 ) 这朵花多好看呀！ (4 ) 离散数学是计算机科学专业的一门必修课。 在上面语句中，是命题的只有 (4 ) 。 8设：P：天气好。Q：他去郊游。则命题“如果天气好，他就去郊游。” 可符号化为 PQ 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 ) 天气多好

7、呀！ (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 qp 2设命题公式为。求此命题公式的真值表； 给出它的析取范式； p q r pq pr 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

8、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 (pq)p )(pq)r) (pp ) (qp)(pr) (qr) (qp)(pr) (qr) 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

9、 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

10、 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

11、，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勇敢。则命题“有人勇敢，但不是所有的人都勇敢”

12、谓词符号化为 _$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。则命题“

13、有些大学生不钦佩所有运动员。”可符号化为_$x(M(x)(y(P(y) H(x,y)_。 二判断题 1. 设A，B都是谓词公式，则x AB也是谓词公式。 2. 设c是个体域中某个元素，A是谓词公式，则A(c) xA(x)。 3. xyA(x,y) yxA(x,y) 。 4. x$yA(x,y) $yxA(x,y) 。 5. 取个体域为整数集，则谓词公式xy(x y = y ) 是假命题。 6. (x) (x)。 7. 命题公式 (PQ R) (PQ) 是析取范式。 8. 谓词公式(x)(A (x) B(x, y) R(x) 的自由变元为x, y。 9. A B） B）。 10. R(x)：“x

14、是大学生。” 是命题。 三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。 1设F：x是火车，G：x是汽车，H：x比y快。命题“某些汽车比所有火车慢”的符号化公式是 (2) 。 $yxH） $yxH） x $yH） $yxH） 2设个体域为整数集，下列真值为真的公式是 。 $yx (x y =2) xy(x y =2) x$y(x y =2) $xy(x y =2) 3设F：x是人，G：x早晨吃面包。命题“有些人早晨吃面包”在谓词逻辑中的符号化公式是 。 G） G） G） G） 5下列式子中正确的是 。 PP P P P P P P 6下面谓词公式是永真式的

15、是 b) 。 a) P Q b) PP c) PP d) PP 5设S：x是运动员，J：y是教练员，L：x钦佩y。命题“所有运动员都钦佩一些教练员”的符号化公式是 c) 。 a) x y L） b) x $y L） c) x $y L） d) $yx L） 6下列式子是合式公式的是 。 ） Q R 7下列式子中正确的是 。 PP P P P P P P 四、解答题 1构造下面推理的证明： 前提：$ x Fy G） R）， $ x F。 结论：$ x R。 证明： $ x Fy G） R） 前提引入 $ x F 前提引入 y G） R） 假言推理 F EI F G 附加 G） R UI R 假言

16、推理 $ 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在命题逻辑中构造下面推理的证明： 如果他是理科学生，他必须学好数学。如果他不是文科学生，他必是理科学生。他没学好数学，所以他是文科

17、学生。 令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)

18、R(a) T6)I 9) Q(a) R(a) T7)8)I 10) ($x)(Q(x) R(x) EG9) 第三章集合与关系 一填空题 如果|A|n，那么|AA| n2 。A上的二元关系有_2n_2个。 集合A上关系R的自反闭包r=_RI_。 设集合A上的关系R和S，R=，S=，则SR= (1,2), (2,2), (2,3) 。 如果|A|n，那么|P(A)| 2n 。 设集合A上的关系R和S，R=，S=，则RS= , , , 。 设集合E=a, b, c，E的幂集P(E) _。 设R是定义在集合X上的二元关系，如果对于每个x, yX， _ _ _ ，则称集合X上的关系R是对称的。 设关系R

19、和S为，R=，S=，则RS =_ _ _ _。 设R是定义在集合X上的二元关系，如果对于每个x, yX， _ _ _ ，则称集合X上的关系R是自反的。 二判断题 1设A、B、C为任意的三个集合，则A(BC)=A(BC)。 2设S，T是任意集合，如果S -T = ，则S = T。 3集合A=1,2,3,4上的关系,是一个函数。 4集合A=1，2，3，4上的整除关系是等价关系。 5集合A 的幂集P(A)上的包含关系是偏序关系。 6设A=a, b, c, R AA且R=, 则R是传递的。 6设A，B是任意集合，如果B ，则A B A。 7集合A=1,2,3上的关系,是传递的。 8集合A=1，2，3，

20、4上的小于关系是等价关系。 9关系x1, x2N, x1+x26能构成一个函数。 10集合A 上的恒等关系是偏序关系。 11集合A=1,2,3上的关系S=,是自反的。 12设X=1, 2, 3, Y=a, b, c。函数F=,是双射。 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)

21、 AB=c d) BA 2设 A = a, b, c, d, A 上的关系R = , , , ，则它的对称闭包为 c) 。 a) R = , , , , , , ， b) R = , , , , ， c) R = , , , , , ， d) R = , , , , , ， 3对于集合1, 2, 3, 4上的关系是偏序关系的是 a) 。 a) R=, , b) R=, , c) R=, , d) R=, , 4设A=1，2，3，4，5，B=6，7，8，9，10，以下哪个关系是从A到B的单射函数 b) 。 a) f =， b) f =， c) f =， d) f =， 5设 A = a, b,

22、c，要使关系, , , R 具有对称性，则 d) 。 a) R = , b) R = , c) R = , d) R = , 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，要使关系, , , R 具有对

23、性，则 。 R = , R = , R = , R = , 10设A=1，2，3，4，5，B=a，b，c，d，e，以下哪个函数是从A到B的入射函数 b) 。 a) F =， b) F=， c) F =， d) F=， 四、解答题 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的最大、最小元，极大、极小元。

24、R=, , , , , , , , , , , , , , , , , , , , , , (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=, , , , , , , , , , , , , , , , , (2) COV A= , , , , (3) 12 6 3 4 2 1 关系R的极大、最大元是12，极小元、最小元是1。 第五章代数结构 一填空题 集合S的幂集P(S)关

25、于集合的并运算“”的零元为 _S_。 集合S的幂集P(S)关于集合的并运算“”的零元为 _f_。 集合S的幂集P(S)关于集合的并运算“”的么元为 _f_。 一个代数系统S, * ，其中S是非空集合。*是S上的一个二元运算，如果 * 在S上是封闭的 ，则称代数系统S, * 为广群。 二判断题 1含有零元的半群称为独异点。 2运算“”是整数集I上的普通加法，则群的么元是1。 三、填空题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。 1下列群一定为循环群的是 e) 。 e) f) g) h) 是集合S的幂集，“”为对称差） 2运算“”是整数集I上的普通减法，则代数系统

26、 满足下列 性质 。 结合律 交换律 有零元 封闭性 3设I是整数集，N是自然数集，P是S的幂集，“，”是普通的乘法，加法和集合的交运算。下面代数系统中 是群。 4下列代数系统不是群的是 。 是集合S的幂集，“”为交运算） 是集合S的幂集，“”为对称差） 第七章图论 一填空题 一个无向图G=是二部图当且仅当G中无 奇数 长度的回路。 任何图(无向的或有向的)中，度为奇数的顶点个数为 偶数 。 设D是一个有向图，若D中任意一对顶点都是相互可达的，则称D是_双向连通的_。 既不含平行边，也不含环的图称为 简单图 。 经过图中 每条边 一次且仅一次并的回路，称为欧拉回路。 一棵有n个顶点的树含有_n1_边。 设G =，G =是两个图，若 V= V 且 E E ，称G是G的生成子图。 经过图中 每个结点 一次且仅一次的回路，称为哈密尔顿回路。 二判断题 15个顶点的有向完全图有20条边。 2连通无向图的欧拉回路经过图中的每个顶点一次且仅一次。 3图中的初级通路都是简单通路。 4已知n (n2)阶无向简单图G有n 1条边，则G一定为树。 5n阶无向完全图Kn的每