大连理工大学软件学院离散数学习题答案

《大连理工大学软件学院离散数学习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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.（

3、1）PQR00010011010101111000101111011111（3）PQR00000010010101111001101111011110（2）（4）略1.（1）P:他聪明；Q:他用功；命题：P∧Q。（2）P:天气好；Q:我骑车上班；命题：Q→P。（3）P:老李是球迷；Q:小李是球迷；命题：P∨Q。（4）P:休息好；Q:身体好；命题：Q→P。2.证明：PQP→QQ→PP«Q001110110010010111113.真值表：xyz(x∧y)∧zx∧(y∧z)(x∨y)∨zx∨（y∨z）00000000010011

4、01000110110011100001110100111111111xyz(x→y)→zx→(y→z)(x«y)«zx«（y«z）0000100001111101001110111100100111110111001111111可得：∧，∨，«是可结合的。4.（1）（P∧Q）→R；（2）┓P；（3）（┓P∧┓Q）→┓R5.不依赖于命题变元的真值指派，而总取T（1）的命题公式，称为重言式（永真式）；不依赖于命题变元的真值指派，而总取F（0）的命题公式，称为永假式（矛盾式）；至少存在一组真值指派使得命题公式取值为T的命题公式称

5、为可满足的。本题可用真值表求解：（4）得真值表如下：PQ001011101111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。（8）得真值表如下：PQR00010011010101111001101111011111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。其他小题可用同样的方法求解。1.（2）原式Û┓((P∨Q)∧R)∨P∨RÛ┓(P∨Q)∨┓R∨P∨RÛ┓(P∨Q)∨P∨TÛT（4）原式ÛP∨（┓（┓Q∧R）∨P）ÛP∨（Q∨┓R∨P）ÛP∨Q∨┓RÛ┓（┓P∧┓Q∧R）第（1）、（3）、

6、（5）小题方法相同，解答略。2.（3）原式Û┓P∧┓Q∧（R∨P）Û（┓P∧┓Q∧R）∨（┓P∧┓Q∧P）Û（┓P∧┓Q∧R）∨FÛ┓（P∨Q∨┓R）第（1）、（2）小题方法相同，解答略。3.（2）左式Û（P∨（┓Q∧Q））∧（┓P∨┓Q）Û（P∨F）∧（┓P∨┓Q）Û（P∧┓P）∨（P∧┓Q）ÛF∨（P∧┓Q）ÛP∧┓Q右式ÛP∧┓Q故：左式Û右式，证明完毕。根据对偶式定义，该式的对偶式为：（P∧┓Q）∨（P∧Q）∨（┓P∧┓Q）第（1）、（3）小题方法相同，解答略。4.（1）原式Û（P∧（┓P∨Q））→QÛ（（P∧┓P）

7、∨（P∧Q））→QÛ（F∨（P∧Q））→QÛ（┓P∨┓Q）∨QÛ┓P∨TÛT（3）原式Û（（┓P∨Q）∧（┓Q∨R））→（┓P∨R）Û（P∧┓Q）∨（Q∧┓R）∨（┓P∨R）Û（（P∧┓Q）∨Q）∧（（P∧┓Q）∨┓R）∨（┓P∨R）Û（P∨Q）∧（┓Q∨Q）∧（P∨┓R）∧（┓Q∨┓R）∨（┓P∨R）Û（P∨（Q∧┓R））∧（┓Q∨┓R）∨（┓P∨R）Û（（P∨（Q∧┓R））∧┓Q）∨（（P∨（Q∧┓R））∧┓R）∨（┓P∨R）Û（P∧┓Q）∨（Q∧┓R∧┓Q）∨（P∧┓R）∨（Q∧┓R∧┓R）∨（┓P∨R）Û（P∧┓Q）

8、∨（P∧┓R）∨（Q∧┓R）∨┓（P∧┓R）Û（P∧┓Q）∨（Q∧┓R）∨TÛT第（2）、（4）小题方法相同，解答略。1.（1）证明：假设P∧Q为真，则P为真且Q为真，则P→Q为真。所以：P∧QÞP→Q。（3）证明：右侧Û┓P∨Q，假设┓P∨Q为假，则P为真且Q为假，则P→Q为假。所以：P