《大连理工大学软件学院离散数学习题答案.docx》由会员分享，可在线阅读，更多相关《大连理工大学软件学院离散数学习题答案.docx（99页珍藏版）》请在金锄头文库上搜索。
1、目 录第一章命题逻辑2第二章 谓词逻辑9第三章 集合论习题答案13第四章 二元关系习题答案21第五章 函数习题答案42第六章 代数系统习题答案51第七章 群与环习题答案57第八章 格与布尔代数习题答案66第九章 图的基本概念及其矩阵表示71第十章 几种图的介绍82第十一章 树90第一章 命题逻辑1. （1）不是命题；（2）不是命题；（3）不是命题；（4）是命题；（5）是命题；2. （1）并非大连的每条街都临海；（2）2不是一个偶数或者8不是一个奇数；（3）2不是偶数并且-3不是负数；3.（1） 逆命题：如果我去公园，那么天不下雨。否命题：如果天下雨，我将不去公园。逆否命题：如果我不去公园，那么
2、天下雨。（2） 逆命题：如果我逗留，那么你去。否命题：如果你不去，那么我不逗留。逆否命题：如果我不逗留，那么你不去。（3） 逆命题：如果方程无整数解，那么n是大于2的正整数。否命题：如果n不是大于2的正整数，那么方程有整数解。逆否命题：如果方程有整数解，那么n不是大于2的正整数。（4） 逆命题：如果我不能完成这项任务，那么我不获得更多的帮助。否命题：如果我获得更多的帮助，则我能完成这项任务。逆否命题：如果我能完成这项任务，则我获得更多的帮助。4. （1）T；（2）T；（3）T；（4）F；5.（1）PQR00010011010101111000101111011111（3）PQR00000010
3、010101111001101111011110（2）（4）略6.（1） P:他聪明；Q:他用功；命题：PQ。（2） P:天气好；Q:我骑车上班；命题：QP。（3） P:老李是球迷；Q:小李是球迷；命题：PQ。（4） P:休息好；Q:身体好；命题：QP。7. 证明：PQPQQPPQ001110110010010111118. 真值表：xyz(xy)zx(yz)(xy)zx（yz）0000000001001101000110110011100001110100111111111xyz(xy)zx(yz)(xy)zx（yz）0000100001111101001110111100100111110
4、111001111111可得：，是可结合的。9. （1）（PQ）R；（2）P；（3）（PQ）R10. 不依赖于命题变元的真值指派，而总取T（1）的命题公式，称为重言式（永真式）；不依赖于命题变元的真值指派，而总取F（0）的命题公式，称为永假式（矛盾式）；至少存在一组真值指派使得命题公式取值为T的命题公式称为可满足的。本题可用真值表求解：（4）得真值表如下：PQ001011101111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。（8）得真值表如下：PQR00010011010101111001101111011111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。其他
5、小题可用同样的方法求解。11. （2）原式 (PQ)R)PR (PQ)RPR (PQ)PT T（4）原式 P（QR）P） P（QRP） PQR （PQR）第（1）、（3）、（5）小题方法相同，解答略。12. （3）原式 PQ（RP） （PQR）（PQP） （PQR）F （PQR）第（1）、（2）小题方法相同，解答略。13. （2）左式（P（QQ）（PQ） （PF）（PQ） （PP）（PQ） F（PQ） PQ右式 PQ故：左式右式，证明完毕。根据对偶式定义，该式的对偶式为：（PQ）（PQ）（PQ）第（1）、（3）小题方法相同，解答略。14. （1）原式（P（PQ）Q（PP）（PQ）Q（F（PQ）
6、Q（PQ）Q PT T（3）原式（PQ）（QR）（PR）（PQ）（QR）（PR）（PQ）Q）（PQ）R）（PR）（PQ）（QQ）（PR）（QR）（PR）（P（QR）（QR）（PR）（P（QR）Q）（P（QR）R）（PR）（P Q）（QRQ）（P R）（QRR）（PR）（P Q）（P R）（QR）（P R）（P Q）（QR）T T第（2）、（4）小题方法相同，解答略。15. （1）证明：假设PQ为真，则P为真且Q为真，则PQ为真。所以：PQ PQ。（3）证明：右侧PQ，假设PQ为假，则P为真且Q为假，则PQ为假。所以：PQ PPQ。（5）证明：假设QR为假，则Q为真且R为假，则左侧为假。所以：（
7、PPQ）（PPR） QR。第（2）、（4）、（6）小题方法相同，解答略。16. （1）代入可得：（PQ）（PQ）R）（PQ）（PQ）（2）代入可得：（QP）（PQ）17. （1）主析取范式：原式（PQ）（PQ） m2m3（2,3）主合取范式：原式（PQ）P）（PQ）Q）P（PQ）（PQ）T P（QQ）M0M1（0,1）（3）主析取范式：原式（PQ）P）（PQ）R）（PQ）P）（PQ）R）（P（PQ）（PR）（QR）（PQ）（PQ）（PR）（QR）（PQ）（PQ）（PR）（QR）（PQ）（PQ）（PR）（QR）（P（QR）（Q（PR）（P（QR）（Q（PR）F（Q（PR）P（QR）（P（QR）Q
8、（PR）F（PQRQ）（PQRR）（PQR）（PRR）（PQR）（PQR）m0m7（0,7）主合取范式：原式（P（QR）（P（QR）（PQ）（PR）（PQ）（PR）（PQ）（RR）（PR）（QQ）（PQ）（RR）（PR）（QQ）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）M1M2M3M4M5M6（1,2,3,4,5,6）第（2）、（4）小题方法相同，解答略。18. （1）证明：左侧（PQ）（PR）（PQR）（PQR）（PQR）（PQR）（4,5,6）右侧P（QR）（4,5,6）左侧右侧，得证。（3）证明：左侧（PQ）（PQ）（PQ）（PQ）（2,3）右侧（P
9、Q）（PQ）（PP）（PQ）（PQ）（QQ）（PQ）（PQ）（2,3）左侧右侧，得证。第（2）、（4）小题方法相同，解答略。19. 对于A,B,C,D,E5个变元的所有真值指派，推出前提AB，B（CD），C（AE），AE和结论AE的值，得到真值表。当真值表中各前提的真值都为1时，若结论也为1，则结论有效，否则结论无效。20. （1）采用真值表证明：PQPQP（PQ）0011011110001111根据真值表可看出，当前提为1时，结论也为1，则结论有效。（3）采用推理方法证明：PQ为真，可得P为真且Q为真，又P（QR）为真且P、Q为真，得R也为真。则结论有效。第（2）、（4）小题方法相同，解答略
10、。21. （1）证明：假设公式全部同时成立，由S为真得到S为假，由PS为真，得P为真，由PQ为真得到Q为真，由QR为真得到R为真，由RS为真得到S为真。这与前面“S为假”矛盾，则公式不能同时成立。（2）证明：假设公式全部同时成立，由S为真得到S为假，由RS为真得到R为假，由RM为真得到M为真，由M为真得到M为假，矛盾。则公式不能同时成立。22. 首先符号化：P:大连获得冠军；Q:北京获得亚军；R:上海获得亚军；S:广州获得亚军。即求公式：P（QR），RP，SQ，PS是否成立。1（1）PP规则2（2）RP P规则1,2（3）RT规则4（4）P（QR）P规则1,2,4（5）QT规则6（6）SQP规则1,2,4,6（7）ST规则23. （1）证明：（1） RP规则（2） QRP规则（3） QT规则（1）（2）（4） （PQ）P规则（5） PT规则（3）（4） （3）题目有误（5）证明：（1） PP规则（附件前提）（2） P（PQ）P规则（3） PQT规则（1）（2）（4） QT规则（1）（3）（5） PQCP规则第（2）、（4）小题方法相同，解答略。24
