《大連理工大學軟件學院離散數(shù)學習題答案》由會員分享，可在線閱讀，更多相關《大連理工大學軟件學院離散數(shù)學習題答案（100頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、目 錄第一章命題邏輯2第二章 謂詞邏輯9第三章 集合論習題答案13第四章 二元關系習題答案21第五章 函數(shù)習題答案42第六章 代數(shù)系統(tǒng)習題答案51第七章 群與環(huán)習題答案57第八章 格與布爾代數(shù)習題答案66第九章 圖的基本概念及其矩陣表示71第十章 幾種圖的介紹82第十一章 樹90100 / 100文檔可自由編輯打印第一章 命題邏輯1. （1）不是命題；（2）不是命題；（3）不是命題；（4）是命題；（5）是命題；2. （1）并非大連的每條街都臨海；（2）2不是一個偶數(shù)或者8不是一個奇數(shù)；（3）2不是偶數(shù)并且-3不是負數(shù)；3.（1） 逆命題：如果我去公園，那么天不下雨。否命題：如果天下雨，我將不去
2、公園。逆否命題：如果我不去公園，那么天下雨。（2） 逆命題：如果我逗留，那么你去。否命題：如果你不去，那么我不逗留。逆否命題：如果我不逗留，那么你不去。（3） 逆命題：如果方程無整數(shù)解，那么n是大于2的正整數(shù)。否命題：如果n不是大于2的正整數(shù)，那么方程有整數(shù)解。逆否命題：如果方程有整數(shù)解，那么n不是大于2的正整數(shù)。（4） 逆命題：如果我不能完成這項任務，那么我不獲得更多的幫助。否命題：如果我獲得更多的幫助，則我能完成這項任務。逆否命題：如果我能完成這項任務，則我獲得更多的幫助。4. （1）T；（2）T；（3）T；（4）F；5.（1）PQR0001001101010111100010111101
3、1111（3）PQR00000010010101111001101111011110（2）（4）略6.（1） P:他聰明；Q:他用功；命題：PQ。（2） P:天氣好；Q:我騎車上班；命題：QP。（3） P:老李是球迷；Q:小李是球迷；命題：PQ。（4） P:休息好；Q:身體好；命題：QP。7. 證明：PQPQQPP«Q001110110010010111118. 真值表：xyz(xy)zx(yz)(xy)zx（yz）0000000001001101000110110011100001110100111111111xyz(xy)zx(yz)(x«y)«zx«
4、;（y«z）0000100001111101001110111100100111110111001111111可得：，«是可結(jié)合的。9. （1）（PQ）R；（2）P；（3）（PQ）R10. 不依賴于命題變元的真值指派，而總?cè)（1）的命題公式，稱為重言式（永真式）；不依賴于命題變元的真值指派，而總?cè)（0）的命題公式，稱為永假式（矛盾式）；至少存在一組真值指派使得命題公式取值為T的命題公式稱為可滿足的。本題可用真值表求解：（4）得真值表如下：PQ001011101111可見不論命題變元的真值指派如何，命題公式總?cè)?，故為重言式。（8）得真值表如下：PQR0001001101
5、0101111001101111011111可見不論命題變元的真值指派如何，命題公式總?cè)?，故為重言式。其他小題可用同樣的方法求解。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）左式Û
6、（P（QQ）（PQ）Û （PF）（PQ）Û （PP）（PQ）Û F（PQ）Û PQ右式Û PQ故：左式Û右式，證明完畢。根據(jù)對偶式定義，該式的對偶式為：（PQ）（PQ）（PQ）第（1）、（3）小題方法相同，解答略。14. （1）原式Û（P（PQ）QÛ（PP）（PQ）QÛ（F（PQ）QÛ（PQ）QÛ PTÛ T（3）原式Û（PQ）（QR）（PR）Û（PQ）（QR）（PR）Û（PQ）Q）（PQ）R）（PR）Û（PQ）（QQ）（PR）（QR）
7、（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）證明：右側(cè)ÛPQ，假設PQ為假，則P為真且Q為假，則PQ為假。所以：PQ Þ PPQ。（5）證明：假設QR為假，則Q為真且R為假，則左側(cè)為假。所以：（PPQ）（PPR）Þ
8、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
9、）（PQ）（PR）（QR）Û（P（QR）（Q（PR）（P（QR）（Q（PR）ÛF（Q（PR）P（QR）（P（QR）Q（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
10、,4,5,6）第（2）、（4）小題方法相同，解答略。18. （1）證明：左側(cè)Û（PQ）（PR）Û（PQR）（PQR）（PQR）（PQR）Û（4,5,6）右側(cè)ÛP（QR）ÛÛ（4,5,6）左側(cè)Û右側(cè)，得證。（3）證明：左側(cè)Û（PQ）（PQ）Û（PQ）（PQ）Û（2,3）右側(cè)Û（PQ）（PQ）Û（PP）（PQ）（PQ）（QQ）Û（PQ）（PQ）Û（2,3）左側(cè)Û右側(cè)，得證。第（2）、（4）小題方法相同，解答略。19. 對于A,B,C,D,E5個變元的
11、所有真值指派，推出前提AB，B（CD），C（AE），AE和結(jié)論AE的值，得到真值表。當真值表中各前提的真值都為1時，若結(jié)論也為1，則結(jié)論有效，否則結(jié)論無效。20. （1）采用真值表證明：PQPQP（PQ）0011011110001111根據(jù)真值表可看出，當前提為1時，結(jié)論也為1，則結(jié)論有效。（3）采用推理方法證明：PQ為真，可得P為真且Q為真，又P（QR）為真且P、Q為真，得R也為真。則結(jié)論有效。第（2）、（4）小題方法相同，解答略。21. （1）證明：假設公式全部同時成立，由S為真得到S為假，由PS為真，得P為真，由PQ為真得到Q為真，由QR為真得到R為真，由RS為真得到S為真。這與前面“S
12、為假”矛盾，則公式不能同時成立。（2）證明：假設公式全部同時成立，由S為真得到S為假，由RS為真得到R為假，由RM為真得到M為真，由M為真得到M為假，矛盾。則公式不能同時成立。22. 首先符號化：P:大連獲得冠軍；Q:北京獲得亞軍；R:上海獲得亞軍；S:廣州獲得亞軍。即求公式：P（QR），RP，SQ，PÞS是否成立。1（1）PP規(guī)則2（2）RP P規(guī)則1,2（3）RT規(guī)則4（4）P（QR）P規(guī)則1,2,4（5）QT規(guī)則6（6）SQP規(guī)則1,2,4,6（7）ST規(guī)則23. （1）證明：（1） RP規(guī)則（2） QRP規(guī)則（3） QT規(guī)則（1）（2）（4） （PQ）P規(guī)則（5） PT規(guī)則（
13、3）（4） （3）題目有誤（5）證明：（1） PP規(guī)則（附件前提）（2） P（PQ）P規(guī)則（3） PQT規(guī)則（1）（2）（4） QT規(guī)則（1）（3）（5） PQCP規(guī)則第（2）、（4）小題方法相同，解答略。24. （1）證明：（1） PP規(guī)則（假設前提）（2） PT規(guī)則（1）（3） PQP規(guī)則（4） QT規(guī)則（2）（3）（5） RQP規(guī)則（6） RT規(guī)則（4）（5）（7） RSP規(guī)則（8） ST規(guī)則（6）（7）（9） SQP規(guī)則（10） QT規(guī)則（8）（9）（11） QQT規(guī)則（4）（10）（12） PF規(guī)則（1）（11）（2）證明：（1） RP規(guī)則（2） RSP規(guī)則（3） ST規(guī)則（1）（2
14、）（4） SQP規(guī)則（5） QT規(guī)則（3）（4）（6） PQP規(guī)則（7） PT規(guī)則（5）（6）（3）原式修改為：（PQ）（RS），（QP）R，RÞ PQ證明：（1） RP規(guī)則（2） RST規(guī)則（1）（3） （PQ）（RS）P規(guī)則（4） PQT規(guī)則（2）（3）（5） （QP）RP規(guī)則（6） QPT規(guī)則（1）（5）（7） （PQ）（QP） T規(guī)則（4）（6）（二） PQT規(guī)則（7）第二章 謂詞邏輯1. （1）S(x)：x聰明；L(x)：x好學；a：表示小明，命題：S(a)L(a)。（2）S(x)：x是素數(shù)；G(x,y)：x大于y，命題：(x)(S(x)(y)(S(y)G(y,x)（3）U
15、(x)：x是大學生；S(x)：x能成為科學家，命題：(x)(U(x)¬S(x)（4） N(x)：x是自然數(shù)；A(x)：x是奇數(shù)；B(x)：x是偶數(shù)，命題：(x)(N(x)(A(x)B(x)（5）P(x)：x是詩人；T(x,y)：x游覽y；V(x)：x是名山大川；a：表示李白 命題：(x)(PaVxTa,x)2. （1）約束變元：x，轄域：P(x)Q(x)和R(x,y)；自由變元：y。（2）約束變元：PxQy中的x,y和R(x)Sz中的z；自由變元：R(x)Sz中的x。（3）約束變元：x,y，轄域：P(x,y)Qy,z；自由變元：z。3. 參考教材2.3部分。4. （1）證明：（1）(
16、"x)¬B(x)P（2）¬B(x)US（1）（3）("x)(¬A(x)B(x)P（4）¬A(x)B(x)US（3）（5）A(x)T（2）（4）（6）($x)A(x)EG（5）（3）證明：由于：("x)(A(x)B(x) Þ("x)A(x) ("x)B(x)；("x)(C(x)¬B(x) Þ("x)C(x) ("x) ¬B(x)；("x)(C(x)¬A(x) Þ("x)C(x) ("x)
17、¬A(x)即證：("x)A(x) ("x)B(x)，("x)C(x) ("x) ¬B(x) Þ("x)C(x) ("x) ¬A(x)（1）("x)C(x)P（附加）（2）C(x)US（1）（3）("x)C(x) ("x) ¬B(x)P（4）C(x) ¬B(x)US（3）（5）¬B(x)T（2）（4）（6）("x)A(x) ("x)B(x)P（7）A(x) B(x)US（6）（8）¬A(x)T（5）（7）（9
18、）("x)¬A(x)UG（8）（10）("x)C(x) ("x)¬A(x)CP（1）（9）第（2）、（4）小題方法相同，解答略。5. （1）證明：（1）("x)P(x)P（附加）（2）P(x)US（1）（3）("x)(P(x)Q(x)P（4）P(x)Q(x)US（3）（5）Q(x)T（2）（4）（6）("x)Q(x)UG（5）（7）("x)P(x) ("x)Q(x)CP（1）（6）（2）證明：由于：("x)P(x)($x)Q(x) Û($x)¬P (x) ($x)Q
19、(x)即證：("x)(P(x)Q(x) Þ($x)¬P (x) ($x)Q(x)（1）($x)¬P (x)P（附加）（2）¬P (x)ES（1）（3）("x)(P(x)Q(x)P（4）P(x)Q(x)US（3）（5）Q(x)T（2）（4）（6）($x)Q(x)EG（5）（7）($x)¬P (x)($x)Q(x)CP（1）（6）6. （1）W(x)：x喜歡步行；C(x)：x喜歡乘汽車；B(x)：x喜歡騎自行車；即需證：("x)(W(x)¬C(x), ("x)( C(x)B(x), ($x)
20、2;B(x) Þ($x)¬W(x)證明：（1）($x)¬B(x)P（2）¬B(x)ES（1）（3）("x)( C(x)B(x)P（4）C(x)B(x)US（3）（5）C(x)T（2）（4）（6）("x)(W(x)¬C(x)P（7）W(x)¬C(x)US（6）（8）¬W(x)T（5）（7）（9）($x)¬W(x)EG（8）（3）F(x)：x是資深人士；S(x)：x是院士；P(x)：x是參事；C(x)：x是委員；a：張偉；即需證：("x)(F(x)( S(x)P(x), ("x)
21、(F(x)C(x), F(a)¬S(a) Þ($x)(C(x)P(x)證明： （1）("x)(F(x)C(x)P（2）F(a)C(a)US（1）（3）F(a)¬S(a)P（4）F(a)T（3）（5）C(a)T（2）（4）（6）("x)(F(x)( S(x)P(x)P（7）F(a)( S(a)P(a) US（6）（8）¬S(a)T（3）（9）P(a)T（4）（7）（8）（10）C(a)P(a)T（5）（9）（11）($x)(C(x)P(x)EG（10） 第（2）、（4）小題方法相同，解答略。7. （d）是錯誤的。8. 錯誤。第二行的y是
22、泛指，第四行的y是特指。修改如下：（1） P（2） ，(1)（3） P（4） ，（3）（5） T，（2），（4）和（6） ，（5）9. （1）證明：（1）($x)P(x)P（2）P(a)ES（1）（3）($x)Q(x)P（4）Q(b)ES（3）（5）($x)P(x) ("x)( P(x)Q(x) R(x)P（6）("x) ( P(x)Q(x) R(x)T（1）（5）（7）( P(a)Q(a) R(a)US（6）（8）P(a)Q(a)T（2）（9）R(a)T（7）（8）（10）( P(b)Q(b) R(b)US（6）（11）P(b)Q(b)T（4）（12）R(b)T（10）（
23、11）（13）R(a)R(b)T（9）（12）（14）($y)( R(a)R(y)EG（13）（15）($x)($y)( R(x)R(y)EG（14）（2）證明：（1）($x)P(x)("x)Q(x)P（假設）（2）¬ ($x) P(x)("x)Q(x)T（1）（3）("x)¬P(x)("x)Q(x)T（2）（4）("x)(¬P(x)Q(x)T（3）（5）("x)(P(x)Q(x)T（4）10. （1）原式Û("x)(¬P(x)($y)Q(y)Û("x)(
24、$y)(¬P(x)Q(y)（3）原式Û("x)($y)A(x,y)($x)("y)(B(x,y)("y)( A(x,y) B(x,y)Û("x)($y)A(x,y)($u)("v)(B(u,v)("z)( ¬ A(z,u) B(u,z)Û("x)($y)($u) ("v) ("z)( A(x,y)( B(u,v)(¬ A(z,u) B(u,z)11. （2）解：前束析取范式：由于是基本和，因此前束合取范式與前束析取范式一樣：（4）解：前束析取范式
25、：前束合取范式：第三章 集合論習題答案對應課本頁數(shù)：P51-541. 寫出下列集合的表達式。(1) 所有一元一次方程的解所組成的集合：答案：集合可表示為 (2) 在實數(shù)域中的因式集。答案：集合可表示為(3) 直角坐標系中，單位圓內(nèi)（不包括單位圓）的點集。答案：集合可表示為(4) 極坐標系中單位圓外（不包括單位圓）的點集。答案：集合可表示為(5) 能被5整除的整數(shù)集。答案：集合可表示為2.解：設戲劇、音樂、廣告分配的時間分別為(1) 可表示為(2) 可表示為(3) 可表示為(4) 可表示為3.給出集合、和的例子，使得，而。解：4.確定下列命題是否為真。(1) 該命題為真命題(2) 該命題為假命題
26、(3) 該命題為真命題(4) 該命題為真命題(5) 該命題為真命題(6) 該命題為真命題(7) 該命題為真命題(8) 該命題為假命題。5. ，是可能的么，給予證明。解：可能。若，則且。6.(1) 解：設 則(2)解：設則(3) 解：設則(4) 解：設 則(5)解：設則7.設，解： (1) ，(2) ，(3) ，8.設某集合有101個元素，試問：(1) 可構(gòu)成多少個子集：2101(2) 其中有多少個子集的元素為奇數(shù)：2100(3) 是否會有102個元素的子集：不會9.解：把17化為二進制，是00010001，；把31化為二進制，是00011111，編碼為01000110，為，編碼為1000000
27、1，為10.求AB，AB。解： 11. 解： 12.解： (1) (2) (3) (4) 13.證明對于所有集合A,B,C有，當且僅當。證明：充分性：由于 所以，即 充分性得證。 必要性：由于 所以 所以 必要性得證。14.證明對所有集合A,B，C，有：（1）證明： （2）證明： （3）證明：因此，15.確定下列各式的運算結(jié)果。解: 16.假設A和B是E的子集，證明下列各式中每個關系式彼此等價。(1) 證明： 證明BA。充分性：若，則若，那么必有。因此，若，則必有，即若xB，則有xA，即BA；必要性：若BA，則若xB，則有xA，即若，則必有。那么，若，那么必有，即；由以上兩點可知：BA。 證明
28、：AB=B 充分性：若，那么有或。 若，則由可知，必有，所以若，必有，即； 若，那么必有，即，所以AB=B，充分性得證； 必要性：因為AB=B，所以，對于任意的，必有，所以，必要性得證； 由以上兩點可知：AB=B 證明：AB=A 充分性：若，那么必有，即；若，那么由可知，必有，所以，即，所以，AB=A； 必要性：因為AB=A，所以對于任意的，必有，所以；由以上兩點可知，AB=A。由以上三點可知，BA AB=BAB=A。(2) 證明:AB 充分性：因為，所以對于任意的，若，則必有，即xB，所以AB； 必要性：因為AB，所以對于任意的，若，則必有xB，即，所以；由以上兩點可知：AB 證明：BA 充
29、分性：因為，所以對于任意的，若，則必有，即xA，所以BA； 必要性：因為BA，所以對于任意的，若，則必有xA，即，所以；由以上兩點可知：BA.由上可知：ABBA.(3) 證明：AB=EAB充分性：因為 AB=E，所以若，則必有，即若xA，則必有，所以AB；必要性：因為AA=E，又AB，必有AB=E；由以上兩點可知：AB=EAB 證明：AB=EBA充分性：因為 AB=E，所以若，則必有，即若xB，則必有，所以BA；必要性：因為BB=E，又BA，必有AB=E；由以上兩點可知：AB=EBA.由上可知：AB=EABBA.。(4) 證明：A=BAB=充分性：由于A=B，所以AB=,BA= 所以AB=AB
30、BA=必要性：因為AB=ABBA= 所以AB=且BA= 因為AB=，所以AB 又BA=，所以BA 所以A=B。由上可知：A=BAB=。17.化簡下述集合公式。(1) 結(jié)果：AB(2) 結(jié)果：A-B(3) 結(jié)果：A(4) 結(jié)果：C（AB）18.設A,B,C是任意集合，分別求使得下述等式成立的充分必要條件。(1) BA(2) BA=(3) B=A=(4) B=A(5) B=(6) B=A(7)解：由于，因此必有且。也就是并且。（8）解：由于，因此必有且。也就是并且。(9) 解： 因此，意味著(10) 解： 兩種可能，第一種，即B=C；第二種，或者19.借助文氏圖，考察下列命題的正確性。EB(1)C
31、AE(2)AC20.設A,B,C為任意集合，是判斷下面命題的真假。如果為真，給出證明，否則給出反例。21.設在10名青年中有5名是工人，7名是學時，其中兼具工人與學生雙重身份的青年有三人，求既不是學生也不是工人的青年有多少？設A，B分別代表工人、學生，則：所以既不是學生也不是工人的青年有 1 人。22.求1到250之間能夠被2,3,5,7中任何一個整除的整數(shù)的個數(shù)。設A= 2502=125，B= 2503=83，C= 2505=50，D= 2507=35則所求的答案表達式為ABCD。求解：ABCD=125 + 83 +50 +31 (41+25+17+16+11+7)+(8+5+3+2)-(1
32、) =189;所以,這樣的數(shù)共有189個。23. 解： 設A，B，C分別表示參加足球隊、籃球隊和棒球隊的隊員的集合即同時參加兩個對的隊員共有18個。24. 解：設A，B，C分別表示讀甲種、乙種、丙種雜志的學生的集合。(1) 所以確定讀兩種雜志的學生的百分比為60%。(2) 所以不讀任何雜志的學生的百分比為30%。第四章 二元關系習題答案對應于課本88-93頁1.如果A=0,2和B=1,2，試求下列集合。（1）解：（2）解（3）解：2.解：表示在在笛卡爾坐標系中，且的矩形區(qū)域內(nèi)的點集。3.（1）證明：任取,有 由取值的任意性知，。（2）當且僅當才，才有證明： 當時，于是。當時，任取，可知，由知，
33、于是得到。所以，。4.證明： 必要性：若，； 同理，若，； 若，則顯然有； 必要性得證。 充分性性：由于 所以對于任意的,必有 即若則必有；若，則必有，所以當時，； 充分性得證。5.（1）解：任取,有選擇A=1，B=2，C=a，D=b則因此該等式不成立。（2）解：任取,有選擇A=1，2，B=1，C=a，b，D=a因此，該等式不成立。（3）解：設A=1，2，B=2，C=3，4，D=4則因此，該等式不成立。（4）解：取,有因此，該等式成立。（5）解：任取取,有因此，該等式成立。（6）存在集合A使得AA×A；取A= ，則該命題成立。（7）PA×PA=PA×A假設結(jié)合A有
34、n個元素，則PA有2n個元素，則PA×PA共有22n個元素；則A×A有n2個元素，PA×A則有2n2個元素，顯然兩者元素數(shù)不一樣，故命題不成立。6.設A=1,2,3,4，列出以下關系R。（1）R= x,yx,yA x+y 2 解：R=1,2，1,3，1,4，2,1，2,2，2,3，2,4，3,1，3,2，3,3，3,4，4,1，4,2，4,3，4,4（2）R= x,yx,yA x-y=1解：R=1,1，1,3，1,4，2,2，2,4，3,1，3,3，4,1，4,2，4,4（3）R= x,yx,yA xyA 解：R=1,1，2,1，2,2，3,1，3,3，4,1，4
35、,2，4,4（4）R= x,yx,yA y 為素數(shù)解：R=1,2，1,3，2,2，2,3，3,2，3,3，4,2，4,37.列出集合A=2,3,4上的恒等關系IA和全域關系EA。解：IA= 2,2，3,3，4,4；。EA= 2,2，2,3，2,4，3,2，3,3，3,4，4,2，4,3，4,48.給出下列關系R的所有序偶。（1）解：（2）解：9.設和都是從到的二元關系，并且求、。解：fldR1-R2=fld1,2,3,3=1,22,3=1,2,3R1R2=1,4,2,2R2R1=1,3,4,4R12=1,4,3,3R23=4,4,2,210.設集合A=1,2,3，問A上有多少種不同的二元關系。
36、解：232=512種關系。11.設關系R= 0，1，0，2，0，3，1，2，1，3，2，3，求RR，R-1，R1,2，R1,2 解：RR= 0,2，0,3，1,3R-1= 1，0，2，0，3，0，2，1，3，1，3，2R1,2= 1，2，1，3，2，3R1,2= 2,312.設關系R=，求R-1，R2，R3，R，R,R|,R， R。解：R-1=，R2= ，R3= R = ，R|= R|=， R= 13.說明以下關系R具有那些性質(zhì)并說明理由。（1）：反自反的、反對稱的、可傳遞的；（2）：反自反的、對稱的、不可傳遞的；（3）：自反、對稱、可傳遞；（4）：自反、對稱、可傳遞；14.設A是所有人的集合
37、，定義A上的二元關系R1和R2，說明R1和R2具有哪些性質(zhì)。解：R1具有的性質(zhì)：反自反的、反對稱的、可傳遞的；R2具有的性質(zhì)：自反、對稱、可傳遞；15. 設和是集合X中的二元關系。試證或反證下列命題：（1）如果和是自反的，則也是自反的。（2）如果和是反自反的，則也是反自反的。（3）如果和是對稱的，則也是對稱的。（4）如果和是反對稱的，則也是反對稱的。（5）如果和是可傳遞的，則也是可傳遞的。解：（1）證明：任取，由于和是自反的，因此，可得，由x取值的任意性可知，是自反的。（2）設，則，不是反自反的。（3）設，則，不是對稱的。（4）設，則，不是反對稱的。（5）設 ，則，不可傳遞。 16.證明：若R
38、是集合A上的自反和可傳遞關系，則RR=R。證明：任意取x,yA ,x,yR,由于R是集合A上的自反，則可知y,y，x,xR， 則R = x,y,x,y,y,y,x,x RR= x,y,x,y,y,y,x,x=R ;17. 如果關系R和S都是自反的。證明：，也是自反的。證明：設R是集合A上的二元關系，S是集合B上的二元關系。因為R和S都是自反的，所以對于都有，對于都有。（1）設，那么或。若，有，那么必有。若，有，那么必有。因此，當時，必有，所以也是自反的。（2）設，那么因此且，即。所以也是自反的。18.證明：如果關系R和S都是自反的、對稱的、可傳遞的，證明：也是自反的、對稱的和可傳遞的。證明：設
39、R是集合A上的二元關系，S是集合B上的二元關系。自反性的證明如題4。 對于任意的，若，那么且因為R和S都是對稱的，所以且，所以。即對于任意的，若，則必有，所以是對稱的。 對于任意，若且，那么有。因為R和S都是可傳遞的，所以有且，即。即對于任意，若且，都有。所以是可傳遞的。19.設集合A是有限集，且A=n，求：（1）A上有多少不同的對稱關系。解：也就是說集合A有n平方個有序?qū)?，由對稱定義可知，對于。另外知道在n平方個有序?qū)χ杏衝 個有序?qū)?，相應的就有個有序?qū)Γ╔,Y)且X，定義可知后面的個有序?qū)χ荒艹蓪Τ霈F(xiàn)，所以有對。前面的那n對可以出現(xiàn)任意多對。圖片如下。（1,1) (2,2).(n,n) (
40、1,2) (1,3).(n-1,n) n個有序?qū)?(2,1) (3,1).(n,n-1) ()/2個有序?qū)?共有n+ ()/2 個元素 即 ()/2個所以得到對稱關系數(shù)為：（2）A上有多少不同的反對稱關系。由定義：如果 如下圖。（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n) n個有序?qū)?(2,1) (3,1).(n,n-1)這n個有序?qū)梢猿霈F(xiàn)任意多次 ( )/2個有序?qū)?(由6可知）所以得結(jié)果 ：即（3）A上有多少不同的既非自反又非反自反的關系。解：20.試著畫出R的關系圖并寫出對應的關系矩陣。解：關系圖如下：21. 設，和是A中的關系，試求出關系矩陣：；。解
41、： 由此可得： 所以： 22. 給定集合。圖4-6給出了A中的關系R的12個關系圖。對于每個關系圖，寫出相應的關系矩陣，并證明被表達的關系是否是自反的或反自反的；是否是對稱的或反對稱的；是否是可傳遞的。（1）自反的、不對稱的、不可傳遞的；其對應的關系矩陣為：（2）不自反的、反對稱的、不可傳遞的； 其對應的關系矩陣為：（3）自反的、對稱的、可傳遞的； 其對應的關系矩陣為：（4）自反的、不對稱的、不可傳遞的； 其對應的關系矩陣為:（5）不自反的、不對稱的、不可傳遞的； 其對應的關系矩陣為：（6）不自反的、對稱的、不可傳遞的； 其對應的關系矩陣為：（7）自反的、反對稱的、可傳遞的； 其對應的關系矩陣
42、為：（8）自反的、不對稱的、不可傳遞的； 其對應的關系矩陣為：（9）不自反的、對稱的、可傳遞的；此題圖有錯誤 其對應的關系矩陣為：（10）自反的、反對稱的、不可傳遞的； 其對應的關系矩陣為：（11）自反的、反對稱的、可傳遞的； 其對應的關系矩陣為：（12）不自反的、反對稱的、可傳遞的。 其對應的關系矩陣為：23. 設X是一個集合，和是X中的二元關系，并設，試證明：（1）（2）（3）證明：a）因為，故R1IAR2IA，即 b）因為s（R1）對稱，且s（R1）R1，但R1R2，故s（R1）R2，由s（R2）的定義，s（R2）是包含R2的最小對稱關系，故 s（R1）s（R2） c）因為t（R1）傳遞
43、，且t（R1）R1，但R1R2，故t（R1）R2因t（R2）是包含R2的最小傳遞關系，所以 t（R1）t（R2）24.在圖4.23中給出三個關系圖。試求每一個的自反的、對稱的和可傳遞的閉包，并畫出閉包的關系圖。（1）解：由關系圖可知， 則： （2）解：由關系圖可知， 則： （3）解：由關系圖可知， 則： 25和是集合A中的關系。試證明：（1）（2）（3）證明：(1)r（R1R2）= R1R2IA= R1IAR2IA =r（R1）r（R2） 2）s（R1R2）=（R1R2）（R1R2）C = R1R2R1CR2C=（R1R1C）（R2R2C） =s（R1）s（R2） 3）因為R1R2R1，由習題
44、3-98，則t（R1R2）=t（R1） 同理 t（R1R2）=t（R2） 所以 t（R1R2）= t（R1）t（R2）26. 設集合，是中的二元關系，圖4-12給出了的關系圖。試畫出可傳遞閉包的關系圖，并求出。解：由關系圖可知，則：27. 設是集合中的任意關系。試證明：（1）（2）（3）證明：a）（R+）+= t（t（R），因為t（R）是傳遞的，根據(jù)定理3-8.1，t（t（R）= t（R），即（R+）+= R+。 b）RR*= R（tr（R）= R（rt（R）= R（t（R）IA） = Rt（R）RIA= RR i=1 =RiR=Ri= t（R）= R+ i=2 i=1同理可證 R+= R*R
45、 c）因為r（R）是自反的，有習題3-97a），tr（R）是自反的，根據(jù)定理3-8.1， rtr（R）= tr（R），即tr（R*）= R*。所以，（R*）*= R*。29設是集合A的劃分。試證明：是集合的劃分。證明：因為是集合的劃分， 所以 （1）因為 所以 （2）（3）（1），（2），（3）構(gòu)成滿足劃分的條件，因此是集合的劃分。30. 把個元素的集合劃分成兩個類，共有多少種不同的分法？解：31. 在圖4.25中給出了集合中的兩個關系圖，判斷這兩個關系是否是等價關系。解：左側(cè)的關系不是等價關系，因為不滿足可傳遞性；右側(cè)的關系是等價關系。32. 在等價關系圖中，應如何識別等價類？解：如果兩個元
46、素之間有兩條連線，那么說明這兩個元素是等價類。33. 設R是集合X中的關系。對于所有的，如果，就有，則稱關系R是循環(huán)關系。試證明：當且僅當R是一個等價關系，R才是自反的和循環(huán)的。證明：（1）當R是個等價關系時，由等價關系的定義知，等價關系滿足自反性，即R是自反的。任取，由R的可傳遞性，知，再由R的對稱性，知。根據(jù)x，y，z取值的任意性，知R是循環(huán)的。（2）當R是自反的，可知對任意，。任取，使得，因為R是循環(huán)的，故當，時，。由x，y取值的任意性知，R是對稱的；任取，由R的循環(huán)性知，因為R是對稱的，因此，由x，y，z取值的任意性，知R是可傳遞的。因為R是自反的、對稱的和可傳遞的，因此R是一個等價關
47、系。34. 設和是集合X中的等價關系。試證明：當且僅當中的每一個等價類都包含于的某一個等價類之中，才有。證明：設等價關系造成的集合X的劃分為，等價關系造成的集合X的劃分為（1） 當中的每一個等價類都包含于的某一個等價類之中時，任取中的一個等價類，則必包含在的一個等價類里，設包含在中，。任取中兩元素x，y，由等價類的性質(zhì)知，。由，可知若，則，即。由i,j,x,y取值的任意性知，。（2） 如果，那么對任意的 永真，等價于x,y落入的某個等價類中，等價于x,y落入的某個等價類中，即若，則，由x,y的任意性可知，,由i的任意性可知，中的每一個等價類都包含在的某一個等價類之中。綜上所述，當且僅當中的每一
48、個等價類都包含于的某一個等價類之中，才有。37. 設和是集合X中的等價關系，并分別有秩和。試證明：也是集合X中的等價關系，它的秩至多為。還要證明不一定是集合X的一個等價關系。證明：(1) 因為是自反的，所以對于任意的，都有對于任意的，故，所以是自反的； 對于任意的，若，則且。又是對稱的，所以有，故，即是對稱的； 對于任意的，若，則，且，。又是可傳遞的，所以有，故，即是可傳遞的；綜上，是等價關系。(2) 因為是自反的，所以對于任意的，都有對于任意的，故，所以是自反的； 對于任意的，若，則可能有三種情況：若且，那么因為是對稱的，所以有，故，即是對稱的； 若但，那么有且，此時，即是對稱的；所以是對稱
49、的；若但，那么有且，此時，即是對稱的； 對于任意的，若，當 ，時，不能確定，故不是可傳遞的。由上可知，不是等價關系。（1）（2），（3），合并后，有 ，（4），（5），合并，得 ，綜上，最大相容類有四個，分別是，。38. 給定集合的覆蓋，如何才能確定此覆蓋的相容關系。解：相容關系是具有反對稱性的關系，集合的任何一個覆蓋均能確定一個相容關系，反之亦然。設是集合的一個覆蓋，則由此覆蓋確定的上的相容關系是：，其中指的子集的笛卡爾積。如是的一個覆蓋，則此覆蓋確定的上的相容關系是：39. 設集合，R是X中的關系。圖4-23給出了R的關系圖。試畫出的關系圖。解：40. 假定是集合X中的恒等關系，R是X中的
50、任何關系。試證明：是相容關系。證明：設（1）由于，因此，。知是自反的；（2）任取，則或者或者。若，則，；若，則，；若，則，?？芍獰o論任何情況，若，則。故是對稱的。綜上所述，既是自反的又是對稱的，因此，是相容關系。41. 給定等價關系R和S，它們的關系矩陣是 試證明：不是等價關系。證明：可知不是對稱的，因此，不是等價關系。42. 設集合。求出X中的等價關系和，使得也是個等價關系。解：設則和是集合X中的等價關系。此時，也是個等價關系。43. 對于下列集合中的整除關系畫出哈斯圖。（1）（2）解：（1）（2）44. 如果R是集合X中的偏序關系，且。試證明：是A中的偏序關系。證明：因為R是集合X中的偏序
51、關系，所以R是自反的，反對稱的，可傳遞的。（1）因為R是自反的，所以； 又，所以； 所以R是自反的。（2）對于任意，若,那么且；又R是反對稱的，所以，即，所以是反對稱的。（3）對于任意，若，那么且。又R是可傳遞的，所以，即：，所以是可傳遞的。由此可知，滿足自反性、反對稱性、可傳遞性，即是A中的偏序關系。45. 試給出集合X的實例，它能使是全序集合。解：，則此時，對于任意的，都有所以是全序集合。46. 給出一個關系，它是集合中的偏序關系又是等價關系。解：集合上的恒等關系，既是偏序關系又是等價關系。47. 證明下列命題：（1）如果是擬序關系，則也是擬序關系。（2）如果是偏序關系，則也是偏序關系。（3）如果是全序關系，則也是全序關系。（4）存在一個集合和中的關系R，使得是良序的，但不是良序的。證明：設是上的二元關系，（a）若是自反的，則，由于的轉(zhuǎn)置仍是，因此，故
大連理工大學軟件學院離散數(shù)學習題答案
