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

目录第一章命题逻辑...........................................................................................................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）逆命题：如果我逗留，那么你去。否命题：如果你不去，那么我不逗留。逆否命题：如果我不逗留，那么你不去。（3）逆命题：如果方程无整数解，那么n是大于2的正整数。否命题：如果n不是大于2的正整数，那么方程有整数解。逆否命题：如果方程有整数解，那么n不是大于2的正整数。（4）逆命题：如果我不能完成这项任务，那么我不获得更多的帮助。否命题：如果我获得更多的帮助，则我能完成这项任务。逆否命题：如果我能完成这项任务，则我获得更多的帮助。4.（1）T；（2）T；（3）T；（4）F；5.（1）PQR00010011010101111000101111011111（3）PQR00000010010101111001101111011110（2）（4）略6.（1）P:他聪明；Q:他用功；命题：P∧Q。（2）P:天气好；Q:我骑车上班；命题：Q→P。（3）P:老李是球迷；Q:小李是球迷；命题：P∨Q。（4）P:休息好；Q:身体好；命题：Q→P。7.证明：PQP→QQ→PPQ001110110010010111118.真值表：xyz(x∧y)∧zx∧(y∧z)(x∨y)∨zx∨（y∨z）0000000001001101000110110011100001110100111111111xyz(x→y)→zx→(y→z)(xy)zx（yz）0000100001111101001110111100100111110111001111111可得：∧，∨，是可结合的。9.（1）（P∧Q）→R；（2）┓P；（3）（┓P∧┓Q）→┓R10.不依赖于命题变元的真值指派，而总取T（1）的命题公式，称为重言式（永真式）；不依赖于命题变元的真值指派，而总取F（0）的命题公式，称为永假式（矛盾式）；至少存在一组真值指派使得命题公式取值为T的命题公式称为可满足的。本题可用真值表求解：（4）得真值表如下：PQ001011101111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。（8）得真值表如下：PQR00010011010101111001101111011111可见不论命题变元的真值指派如何，命题公式总取1，故为重言式。其他小题可用同样的方法求解。11.（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）、（5）小题方法相同，解答略。12.（3）原式┓P∧┓Q∧（R∨P）（┓P∧┓Q∧R）∨（┓P∧┓Q∧P）（┓P∧┓Q∧R）∨F┓（P∨Q∨┓R）第（1）、（2）小题方法相同，解答略。13.（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）小题方法相同，解答略。14.（1）原式（P∧（┓P∨Q））→Q（（P∧┓P）∨（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）∨（P∧┓R）∨（Q∧┓R）∨┓（P∧┓R）（P∧┓Q）∨（Q∧┓R）∨TT第（2）、（4）小题方法相同，解答略。15.（1）证明：假设P∧Q为真，则P为真且Q为真，则P→Q为真。所以：P∧QP→Q。（3）证明：右侧┓P∨Q，假设┓P∨Q为假，则P为真且Q为假，则P→Q为假。所以：P→QP→P∧Q。（5）证明：假设Q→R为假，则Q为真且R为假，则左侧为假。所以：（P∨┓P→Q）→（P∨┓P→R）Q→R。第（2）、（4）、（6）小题方法相同，解答略。16.（1）代入可得：（（（P→Q）→（（P→Q）→R））→（P→Q））→（P→Q）（2）代入可得：（（Q→┓P）→（┓P→Q））17.（1）主析取范式：原式（P∧Q）∨（P∧┓Q）m2∨m3∑（2,3）主合取范式：原式（（P∧Q）∨P）∧（（P∧Q）∨┓Q）P∧（P∨Q）∧（P∨┓Q）∧TP∨（Q∧┓Q）M0∧M1∏（0,1）（3）主析取范式：原式（（（┓P∨Q）∧┓P）∨（（┓P∨Q）∧R））∧（（（P∨┓Q）∧P）∨（（P∨┓Q）∧┓R））（┓P∨（┓P∧Q）∨（┓P∧R）∨（Q∧R））∧（（P∧Q）∨（P∧┓Q）∨（P∧┓R）∨（┓Q∧┓R））（（┓P∧┓Q）∨（┓P∧Q）∨（┓P∧R）∨（Q∧R））∧（（P∧Q）∨（P∧┓Q）∨（P∧┓R）∨（┓Q∧┓R））（（┓P∧（┓Q∨R））∨（Q∧（┓P∨R）））∧（（P∧（Q∨┓R）∨（┓Q∧（P∨┓R）））F∨（Q∧（┓P∨R）∧P∧（Q∨┓R））∨（┓P∧（┓Q∨R）∧┓Q∧（P∨┓R））∨F（P∧Q∧R∧Q）∨（P∧Q∧R∧┓R）∨（┓P∧┓Q∧┓R）∨（┓P∧┓R∧R）（P∧Q∧R）∨（┓P∧┓Q∧┓R）m0∨m7∑（0,7）主合取范式：原式（┓P∨（Q∧R））∧（P∨（┓Q∧┓R））（┓P∨Q）∧（┓P∨R）∧（P∨┓Q）∧（P∨┓R）（┓P∨Q）∨（R∧┓R）∧（┓P∨R）∨（Q∧┓Q）∧（P∨┓Q）∨（R∧┓R）∧（P∨┓R）∨（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）M1∧M2∧M3∧M4∧M5∧M6∏（1,2,3,4,5,6）第（2）、（4）小题方法相同，解答略。18.（1）证明：左侧（┓P∨Q）∧（┓P∨R）（┓P∨Q∨R）∧（┓P∨Q∨┓R）∧（┓P∨Q∨R）∧（┓P∨┓Q∨R）∏（4,5,6）右侧┓P∨（Q∧R）…∏（4,5,6）左侧右侧，得证。（3）证明：左侧┓（┓P∨Q）∨（P∧Q）（P∧┓Q）∨（P∧Q）∑（2,3）右侧（P∨Q）∧（P∨┓Q）（P∧P）∨（P∧┓Q）∨（P∧Q）∨（Q∧┓Q）（P∧┓Q）∨（P∧Q）∑（2,3）左侧右侧，得证。第（2）、（4）小题方法相同，解答略。19.对于A,B,C,D,E5个变元的所有真值指派，推出前提A↔B，B↔（C∧D），C↔（A∨E），A∨E和结论A∧E的值，得到真值表。当真值表中各前提的真值都为1时，若结论也为1，则结论有效，否则结论无效。20.（1）采用真值表证明：PQP→QP→（P∧Q）0011011110001111根据真值表可看出，当前提为1时，结论也为1，则结论有效。（3）采用推理方法证明：P∧Q为真，可得P为真且Q为真，又P→（Q→R）为真且P、Q为真，得R也为真。则结论有效。第（2）、（4）小题方法相同，解答略。21.（1）证明：假设公式全部同时成立，由┓S为真得到S为假，由┓P→S为真，得P为真，由P↔Q为真得到Q为真，由Q→R为真得到R为真，由┓R∨S为真得到S为真。这与前面“S为假”矛盾，则公式不能同时成立。（2）证明：假设公式全部同时成立，由┓S为真得到S为假，由┓R∨S为真得到R为假，由R∨M为真得到M为真，由┓M为真得到M为假，矛盾。则公式不能同时成立。22.首先符号化：P:大连获得冠军；Q:北京获得亚军；R:上海获得亚军；S:广州获得亚军。即求公式：P→（Q∨R），R→┓P，S→┓Q，P┓S是否成立。{1}（1）PP规则{2}（2）R→┓PP规则{1,2}（3）┓RT规则{4}（4）P→（Q∨R）P规则{1,2,4}（5）QT规则{6}（6）S→┓QP规则{1,2,4,6}（7）┓ST规则23.（1）证明：（1）┓RP规则（2）┓Q∨RP规则（3）┓QT规则（1）（2）（4）┓（P∧┓Q）P规则（5）┓PT规则（3）（4）（3）题目有误（5）证明：（1）PP规则（附件前提）（2）P→（P∧Q）P规则（3）P∧QT规则（1）（2）（4）QT规则（1）（3）（5）P→QCP规则第（2）、（4）小题方法相同，解答略。24.（1）证明：（1）┓┓PP规则（假设前提）（2）PT规则（1）（3）P→QP规则（4）QT规则（2）（3）（5）R→┓QP规则（6）┓RT规则（4）