大連理工大學(xué)軟件學(xué)院離散數(shù)學(xué)習(xí)題答案

目 錄第一章命題邏輯2第二章 謂詞邏輯9第三章 集合論習(xí)題答案13第四章 二元關(guān)系習(xí)題答案21第五章 函數(shù)習(xí)題答案42第六章 代數(shù)系統(tǒng)習(xí)題答案51第七章 群與環(huán)習(xí)題答案57第八章 格與布爾代數(shù)習(xí)題答案66第九章 圖的基本概念及其矩陣表示71第十章 幾種圖的介紹82第十一章 樹90100 / 100文檔可自由編輯打印第一章 命題邏輯1. （1）不是命題；（2）不是命題；（3）不是命題；（4）是命題；（5）是命題；2. （1）并非大連的每條街都臨海；（2）2不是一個(gè)偶數(shù)或者8不是一個(gè)奇數(shù)；（3）2不是偶數(shù)并且-3不是負(fù)數(shù)；3.（1） 逆命題：如果我去公園，那么天不下雨。否命題：如果天下雨，我將不去公園。逆否命題：如果我不去公園，那么天下雨。（2） 逆命題：如果我逗留，那么你去。否命題：如果你不去，那么我不逗留。逆否命題：如果我不逗留，那么你不去。（3） 逆命題：如果方程無整數(shù)解，那么n是大于2的正整數(shù)。否命題：如果n不是大于2的正整數(shù)，那么方程有整數(shù)解。逆否命題：如果方程有整數(shù)解，那么n不是大于2的正整數(shù)。（4） 逆命題：如果我不能完成這項(xiàng)任務(wù)，那么我不獲得更多的幫助。否命題：如果我獲得更多的幫助，則我能完成這項(xiàng)任務(wù)。逆否命題：如果我能完成這項(xiàng)任務(wù)，則我獲得更多的幫助。4. （1）T；（2）T；（3）T；（4）F；5.（1）PQR00010011010101111000101111011111（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«（y«z）0000100001111101001110111100100111110111001111111可得：，«是可結(jié)合的。9. （1）（PQ）R；（2）P；（3）（PQ）R10. 不依賴于命題變元的真值指派，而總?cè)（1）的命題公式，稱為重言式（永真式）；不依賴于命題變元的真值指派，而總?cè)（0）的命題公式，稱為永假式（矛盾式）；至少存在一組真值指派使得命題公式取值為T的命題公式稱為可滿足的。本題可用真值表求解：（4）得真值表如下：PQ001011101111可見不論命題變元的真值指派如何，命題公式總?cè)?，故為重言式。（8）得真值表如下：PQR00010011010101111001101111011111可見不論命題變元的真值指派如何，命題公式總?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）左式Û（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）（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）證明：假設(shè)PQ為真，則P為真且Q為真，則PQ為真。所以：PQ Þ PQ。（3）證明：右側(cè)ÛPQ，假設(shè)PQ為假，則P為真且Q為假，則PQ為假。所以：PQ Þ PPQ。（5）證明：假設(shè)QR為假，則Q為真且R為假，則左側(cè)為假。所以：（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（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）證明：左側(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個(gè)變元的所有真值指派，推出前提AB，B（CD），C（AE），AE和結(jié)論AE的值，得到真值表。當(dāng)真值表中各前提的真值都為1時(shí)，若結(jié)論也為1，則結(jié)論有效，否則結(jié)論無效。20. （1）采用真值表證明：PQPQP（PQ）0011011110001111根據(jù)真值表可看出，當(dāng)前提為1時(shí)，結(jié)論也為1，則結(jié)論有效。（3）采用推理方法證明：PQ為真，可得P為真且Q為真，又P（QR）為真且P、Q為真，得R也為真。則結(jié)論有效。第（2）、（4）小題方法相同，解答略。21. （1）證明：假設(shè)公式全部同時(shí)成立，由S為真得到S為假，由PS為真，得P為真，由PQ為真得到Q為真，由QR為真得到R為真，由RS為真得到S為真。這與前面“S為假”矛盾，則公式不能同時(shí)成立。（2）證明：假設(shè)公式全部同時(shí)成立，由S為真得到S為假，由RS為真得到R為假，由RM為真得到M為真，由M為真得到M為假，矛盾。則公式不能同時(shí)成立。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ī)則（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ī)則（假設(shè)前提）（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）（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好學(xué)；a：表示小明，命題：S(a)L(a)。（2）S(x)：x是素?cái)?shù)；G(x,y)：x大于y，命題：(x)(S(x)(y)(S(y)G(y,x)（3）U(x)：x是大學(xué)生；S(x)：x能成為科學(xué)家，命題：(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）("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) ¬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）("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(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)¬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)(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）是錯(cuò)誤的。8. 錯(cuò)誤。第二行的y是泛指，第四行的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）（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（假設(shè)）（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)($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）解：前束析取范式：前束合取范式：第三章 集合論習(xí)題答案對應(yīng)課本頁數(shù)：P51-541. 寫出下列集合的表達(dá)式。(1) 所有一元一次方程的解所組成的集合：答案：集合可表示為 (2) 在實(shí)數(shù)域中的因式集。答案：集合可表示為(3) 直角坐標(biāo)系中，單位圓內(nèi)（不包括單位圓）的點(diǎn)集。答案：集合可表示為(4) 極坐標(biāo)系中單位圓外（不包括單位圓）的點(diǎn)集。答案：集合可表示為(5) 能被5整除的整數(shù)集。答案：集合可表示為2.解：設(shè)戲劇、音樂、廣告分配的時(shí)間分別為(1) 可表示為(2) 可表示為(3) 可表示為(4) 可表示為3.給出集合、和的例子，使得，而。解：4.確定下列命題是否為真。(1) 該命題為真命題(2) 該命題為假命題(3) 該命題為真命題(4) 該命題為真命題(5) 該命題為真命題(6) 該命題為真命題(7) 該命題為真命題(8) 該命題為假命題。5. ，是可能的么，給予證明。解：可能。若，則且。6.(1) 解：設(shè) 則(2)解：設(shè)則(3) 解：設(shè)則(4) 解：設(shè) 則(5)解：設(shè)則7.設(shè)，解： (1) ，(2) ，(3) ，8.設(shè)某集合有101個(gè)元素，試問：(1) 可構(gòu)成多少個(gè)子集：2101(2) 其中有多少個(gè)子集的元素為奇數(shù)：2100(3) 是否會有102個(gè)元素的子集：不會9.解：把17化為二進(jìn)制，是00010001，；把31化為二進(jìn)制，是00011111，編碼為01000110，為，編碼為10000001，為10.求AB，AB。解： 11. 解： 12.解： (1) (2) (3) (4) 13.證明對于所有集合A,B,C有，當(dāng)且僅當(dāng)。證明：充分性：由于 所以，即 充分性得證。 必要性：由于 所以 所以 必要性得證。14.證明對所有集合A,B，C，有：（1）證明： （2）證明： （3）證明：因此，15.確定下列各式的運(yùn)算結(jié)果。解: 16.假設(shè)A和B是E的子集，證明下列各式中每個(gè)關(guān)系式彼此等價(jià)。(1) 證明： 證明BA。充分性：若，則若，那么必有。因此，若，則必有，即若xB，則有xA，即BA；必要性：若BA，則若xB，則有xA，即若，則必有。那么，若，那么必有，即；由以上兩點(diǎn)可知：BA。 證明：AB=B 充分性：若，那么有或。 若，則由可知，必有，所以若，必有，即； 若，那么必有，即，所以AB=B，充分性得證； 必要性：因?yàn)锳B=B，所以，對于任意的，必有，所以，必要性得證； 由以上兩點(diǎn)可知：AB=B 證明：AB=A 充分性：若，那么必有，即；若，那么由可知，必有，所以，即，所以，AB=A； 必要性：因?yàn)锳B=A，所以對于任意的，必有，所以；由以上兩點(diǎn)可知，AB=A。由以上三點(diǎn)可知，BA AB=BAB=A。(2) 證明:AB 充分性：因?yàn)?，所以對于任意的，若，則必有，即xB，所以AB； 必要性：因?yàn)锳B，所以對于任意的，若，則必有xB，即，所以；由以上兩點(diǎn)可知：AB 證明：BA 充分性：因?yàn)椋詫τ谌我獾?，若，則必有，即xA，所以BA； 必要性：因?yàn)锽A，所以對于任意的，若，則必有xA，即，所以；由以上兩點(diǎn)可知：BA.由上可知：ABBA.(3) 證明：AB=EAB充分性：因?yàn)?AB=E，所以若，則必有，即若xA，則必有，所以AB；必要性：因?yàn)锳A=E，又AB，必有AB=E；由以上兩點(diǎn)可知：AB=EAB 證明：AB=EBA充分性：因?yàn)?AB=E，所以若，則必有，即若xB，則必有，所以BA；必要性：因?yàn)锽B=E，又BA，必有AB=E；由以上兩點(diǎn)可知：AB=EBA.由上可知：AB=EABBA.。(4) 證明：A=BAB=充分性：由于A=B，所以AB=,BA= 所以AB=ABBA=必要性：因?yàn)锳B=ABBA= 所以AB=且BA= 因?yàn)锳B=，所以AB 又BA=，所以BA 所以A=B。由上可知：A=BAB=。17.化簡下述集合公式。(1) 結(jié)果：AB(2) 結(jié)果：A-B(3) 結(jié)果：A(4) 結(jié)果：C（AB）18.設(shè)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)CAE(2)AC20.設(shè)A,B,C為任意集合，是判斷下面命題的真假。如果為真，給出證明，否則給出反例。21.設(shè)在10名青年中有5名是工人，7名是學(xué)時(shí)，其中兼具工人與學(xué)生雙重身份的青年有三人，求既不是學(xué)生也不是工人的青年有多少？設(shè)A，B分別代表工人、學(xué)生，則：所以既不是學(xué)生也不是工人的青年有 1 人。22.求1到250之間能夠被2,3,5,7中任何一個(gè)整除的整數(shù)的個(gè)數(shù)。設(shè)A= 2502=125，B= 2503=83，C= 2505=50，D= 2507=35則所求的答案表達(dá)式為ABCD。求解：ABCD=125 + 83 +50 +31 (41+25+17+16+11+7)+(8+5+3+2)-(1) =189;所以,這樣的數(shù)共有189個(gè)。23. 解： 設(shè)A，B，C分別表示參加足球隊(duì)、籃球隊(duì)和棒球隊(duì)的隊(duì)員的集合即同時(shí)參加兩個(gè)對的隊(duì)員共有18個(gè)。24. 解：設(shè)A，B，C分別表示讀甲種、乙種、丙種雜志的學(xué)生的集合。(1) 所以確定讀兩種雜志的學(xué)生的百分比為60%。(2) 所以不讀任何雜志的學(xué)生的百分比為30%。第四章 二元關(guān)系習(xí)題答案對應(yīng)于課本88-93頁1.如果A=0,2和B=1,2，試求下列集合。（1）解：（2）解（3）解：2.解：表示在在笛卡爾坐標(biāo)系中，且的矩形區(qū)域內(nèi)的點(diǎn)集。3.（1）證明：任取,有 由取值的任意性知，。（2）當(dāng)且僅當(dāng)才，才有證明： 當(dāng)時(shí)，于是。當(dāng)時(shí)，任取，可知，由知，于是得到。所以，。4.證明： 必要性：若，； 同理，若，； 若，則顯然有； 必要性得證。 充分性性：由于 所以對于任意的,必有 即若則必有；若，則必有，所以當(dāng)時(shí)，； 充分性得證。5.（1）解：任取,有選擇A=1，B=2，C=a，D=b則因此該等式不成立。（2）解：任取,有選擇A=1，2，B=1，C=a，b，D=a因此，該等式不成立。（3）解：設(shè)A=1，2，B=2，C=3，4，D=4則因此，該等式不成立。（4）解：取,有因此，該等式成立。（5）解：任取取,有因此，該等式成立。（6）存在集合A使得AA×A；取A= ，則該命題成立。（7）PA×PA=PA×A假設(shè)結(jié)合A有n個(gè)元素，則PA有2n個(gè)元素，則PA×PA共有22n個(gè)元素；則A×A有n2個(gè)元素，PA×A則有2n2個(gè)元素，顯然兩者元素?cái)?shù)不一樣，故命題不成立。6.設(shè)A=1,2,3,4，列出以下關(guān)系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,2，4,4（4）R= x,yx,yA y 為素?cái)?shù)解：R=1,2，1,3，2,2，2,3，3,2，3,3，4,2，4,37.列出集合A=2,3,4上的恒等關(guān)系IA和全域關(guān)系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.給出下列關(guān)系R的所有序偶。（1）解：（2）解：9.設(shè)和都是從到的二元關(guān)系，并且求、。解：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.設(shè)集合A=1,2,3，問A上有多少種不同的二元關(guān)系。解：232=512種關(guān)系。11.設(shè)關(guān)系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.設(shè)關(guān)系R=，求R-1，R2，R3，R，R,R|,R， R。解：R-1=，R2= ，R3= R = ，R|= R|=， R= 13.說明以下關(guān)系R具有那些性質(zhì)并說明理由。（1）：反自反的、反對稱的、可傳遞的；（2）：反自反的、對稱的、不可傳遞的；（3）：自反、對稱、可傳遞；（4）：自反、對稱、可傳遞；14.設(shè)A是所有人的集合，定義A上的二元關(guān)系R1和R2，說明R1和R2具有哪些性質(zhì)。解：R1具有的性質(zhì)：反自反的、反對稱的、可傳遞的；R2具有的性質(zhì)：自反、對稱、可傳遞；15. 設(shè)和是集合X中的二元關(guān)系。試證或反證下列命題：（1）如果和是自反的，則也是自反的。（2）如果和是反自反的，則也是反自反的。（3）如果和是對稱的，則也是對稱的。（4）如果和是反對稱的，則也是反對稱的。（5）如果和是可傳遞的，則也是可傳遞的。解：（1）證明：任取，由于和是自反的，因此，可得，由x取值的任意性可知，是自反的。（2）設(shè)，則，不是反自反的。（3）設(shè)，則，不是對稱的。（4）設(shè)，則，不是反對稱的。（5）設(shè) ，則，不可傳遞。 16.證明：若R是集合A上的自反和可傳遞關(guān)系，則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. 如果關(guān)系R和S都是自反的。證明：，也是自反的。證明：設(shè)R是集合A上的二元關(guān)系，S是集合B上的二元關(guān)系。因?yàn)镽和S都是自反的，所以對于都有，對于都有。（1）設(shè)，那么或。若，有，那么必有。若，有，那么必有。因此，當(dāng)時(shí)，必有，所以也是自反的。（2）設(shè)，那么因此且，即。所以也是自反的。18.證明：如果關(guān)系R和S都是自反的、對稱的、可傳遞的，證明：也是自反的、對稱的和可傳遞的。證明：設(shè)R是集合A上的二元關(guān)系，S是集合B上的二元關(guān)系。自反性的證明如題4。 對于任意的，若，那么且因?yàn)镽和S都是對稱的，所以且，所以。即對于任意的，若，則必有，所以是對稱的。 對于任意，若且，那么有。因?yàn)镽和S都是可傳遞的，所以有且，即。即對于任意，若且，都有。所以是可傳遞的。19.設(shè)集合A是有限集，且A=n，求：（1）A上有多少不同的對稱關(guān)系。解：也就是說集合A有n平方個(gè)有序?qū)Γ蓪ΨQ定義可知，對于。另外知道在n平方個(gè)有序?qū)χ杏衝 個(gè)有序?qū)?，相?yīng)的就有個(gè)有序?qū)Γ╔,Y)且X，定義可知后面的個(gè)有序?qū)χ荒艹蓪Τ霈F(xiàn)，所以有對。前面的那n對可以出現(xiàn)任意多對。圖片如下。（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n) n個(gè)有序?qū)?(2,1) (3,1).(n,n-1) ()/2個(gè)有序?qū)?共有n+ ()/2 個(gè)元素 即 ()/2個(gè)所以得到對稱關(guān)系數(shù)為：（2）A上有多少不同的反對稱關(guān)系。由定義：如果 如下圖。（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n) n個(gè)有序?qū)?(2,1) (3,1).(n,n-1)這n個(gè)有序?qū)梢猿霈F(xiàn)任意多次 ( )/2個(gè)有序?qū)?(由6可知）所以得結(jié)果 ：即（3）A上有多少不同的既非自反又非反自反的關(guān)系。解：20.試著畫出R的關(guān)系圖并寫出對應(yīng)的關(guān)系矩陣。解：關(guān)系圖如下：21. 設(shè)，和是A中的關(guān)系，試求出關(guān)系矩陣：；。解： 由此可得： 所以： 22. 給定集合。圖4-6給出了A中的關(guān)系R的12個(gè)關(guān)系圖。對于每個(gè)關(guān)系圖，寫出相應(yīng)的關(guān)系矩陣，并證明被表達(dá)的關(guān)系是否是自反的或反自反的；是否是對稱的或反對稱的；是否是可傳遞的。（1）自反的、不對稱的、不可傳遞的；其對應(yīng)的關(guān)系矩陣為：（2）不自反的、反對稱的、不可傳遞的； 其對應(yīng)的關(guān)系矩陣為：（3）自反的、對稱的、可傳遞的； 其對應(yīng)的關(guān)系矩陣為：（4）自反的、不對稱的、不可傳遞的； 其對應(yīng)的關(guān)系矩陣為:（5）不自反的、不對稱的、不可傳遞的； 其對應(yīng)的關(guān)系矩陣為：（6）不自反的、對稱的、不可傳遞的； 其對應(yīng)的關(guān)系矩陣為：（7）自反的、反對稱的、可傳遞的； 其對應(yīng)的關(guān)系矩陣為：（8）自反的、不對稱的、不可傳遞的； 其對應(yīng)的關(guān)系矩陣為：（9）不自反的、對稱的、可傳遞的；此題圖有錯(cuò)誤 其對應(yīng)的關(guān)系矩陣為：（10）自反的、反對稱的、不可傳遞的； 其對應(yīng)的關(guān)系矩陣為：（11）自反的、反對稱的、可傳遞的； 其對應(yīng)的關(guān)系矩陣為：（12）不自反的、反對稱的、可傳遞的。 其對應(yīng)的關(guān)系矩陣為：23. 設(shè)X是一個(gè)集合，和是X中的二元關(guān)系，并設(shè)，試證明：（1）（2）（3）證明：a）因?yàn)?，故R1IAR2IA，即 b）因?yàn)閟（R1）對稱，且s（R1）R1，但R1R2，故s（R1）R2，由s（R2）的定義，s（R2）是包含R2的最小對稱關(guān)系，故 s（R1）s（R2） c）因?yàn)閠（R1）傳遞，且t（R1）R1，但R1R2，故t（R1）R2因t（R2）是包含R2的最小傳遞關(guān)系，所以 t（R1）t（R2）24.在圖4.23中給出三個(gè)關(guān)系圖。試求每一個(gè)的自反的、對稱的和可傳遞的閉包，并畫出閉包的關(guān)系圖。（1）解：由關(guān)系圖可知， 則： （2）解：由關(guān)系圖可知， 則： （3）解：由關(guān)系圖可知， 則： 25和是集合A中的關(guān)系。試證明：（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）因?yàn)镽1R2R1，由習(xí)題3-98，則t（R1R2）=t（R1） 同理 t（R1R2）=t（R2） 所以 t（R1R2）= t（R1）t（R2）26. 設(shè)集合，是中的二元關(guān)系，圖4-12給出了的關(guān)系圖。試畫出可傳遞閉包的關(guān)系圖，并求出。解：由關(guān)系圖可知，則：27. 設(shè)是集合中的任意關(guān)系。試證明：（1）（2）（3）證明：a）（R+）+= t（t（R），因?yàn)閠（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 c）因?yàn)閞（R）是自反的，有習(xí)題3-97a），tr（R）是自反的，根據(jù)定理3-8.1， rtr（R）= tr（R），即tr（R*）= R*。所以，（R*）*= R*。29設(shè)是集合A的劃分。試證明：是集合的劃分。證明：因?yàn)槭羌系膭澐郑?所以 （1）因?yàn)?所以 （2）（3）（1），（2），（3）構(gòu)成滿足劃分的條件，因此是集合的劃分。30. 把個(gè)元素的集合劃分成兩個(gè)類，共有多少種不同的分法？解：31. 在圖4.25中給出了集合中的兩個(gè)關(guān)系圖，判斷這兩個(gè)關(guān)系是否是等價(jià)關(guān)系。解：左側(cè)的關(guān)系不是等價(jià)關(guān)系，因?yàn)椴粷M足可傳遞性；右側(cè)的關(guān)系是等價(jià)關(guān)系。32. 在等價(jià)關(guān)系圖中，應(yīng)如何識別等價(jià)類？解：如果兩個(gè)元素之間有兩條連線，那么說明這兩個(gè)元素是等價(jià)類。33. 設(shè)R是集合X中的關(guān)系。對于所有的，如果，就有，則稱關(guān)系R是循環(huán)關(guān)系。試證明：當(dāng)且僅當(dāng)R是一個(gè)等價(jià)關(guān)系，R才是自反的和循環(huán)的。證明：（1）當(dāng)R是個(gè)等價(jià)關(guān)系時(shí)，由等價(jià)關(guān)系的定義知，等價(jià)關(guān)系滿足自反性，即R是自反的。任取，由R的可傳遞性，知，再由R的對稱性，知。根據(jù)x，y，z取值的任意性，知R是循環(huán)的。（2）當(dāng)R是自反的，可知對任意，。任取，使得，因?yàn)镽是循環(huán)的，故當(dāng)，時(shí)，。由x，y取值的任意性知，R是對稱的；任取，由R的循環(huán)性知，因?yàn)镽是對稱的，因此，由x，y，z取值的任意性，知R是可傳遞的。因?yàn)镽是自反的、對稱的和可傳遞的，因此R是一個(gè)等價(jià)關(guān)系。34. 設(shè)和是集合X中的等價(jià)關(guān)系。試證明：當(dāng)且僅當(dāng)中的每一個(gè)等價(jià)類都包含于的某一個(gè)等價(jià)類之中，才有。證明：設(shè)等價(jià)關(guān)系造成的集合X的劃分為，等價(jià)關(guān)系造成的集合X的劃分為（1） 當(dāng)中的每一個(gè)等價(jià)類都包含于的某一個(gè)等價(jià)類之中時(shí)，任取中的一個(gè)等價(jià)類，則必包含在的一個(gè)等價(jià)類里，設(shè)包含在中，。任取中兩元素x，y，由等價(jià)類的性質(zhì)知，。由，可知若，則，即。由i,j,x,y取值的任意性知，。（2） 如果，那么對任意的 永真，等價(jià)于x,y落入的某個(gè)等價(jià)類中，等價(jià)于x,y落入的某個(gè)等價(jià)類中，即若，則，由x,y的任意性可知，,由i的任意性可知，中的每一個(gè)等價(jià)類都包含在的某一個(gè)等價(jià)類之中。綜上所述，當(dāng)且僅當(dāng)中的每一個(gè)等價(jià)類都包含于的某一個(gè)等價(jià)類之中，才有。37. 設(shè)和是集合X中的等價(jià)關(guān)系，并分別有秩和。試證明：也是集合X中的等價(jià)關(guān)系，它的秩至多為。還要證明不一定是集合X的一個(gè)等價(jià)關(guān)系。證明：(1) 因?yàn)槭亲苑吹?，所以對于任意的，都有對于任意的，故，所以是自反的?對于任意的，若，則且。又是對稱的，所以有，故，即是對稱的； 對于任意的，若，則，且，。又是可傳遞的，所以有，故，即是可傳遞的；綜上，是等價(jià)關(guān)系。(2) 因?yàn)槭亲苑吹?，所以對于任意的，都有對于任意的，故，所以是自反的?對于任意的，若，則可能有三種情況：若且，那么因?yàn)槭菍ΨQ的，所以有，故，即是對稱的； 若但，那么有且，此時(shí)，即是對稱的；所以是對稱的；若但，那么有且，此時(shí)，即是對稱的； 對于任意的，若，當(dāng) ，時(shí)，不能確定，故不是可傳遞的。由上可知，不是等價(jià)關(guān)系。（1）（2），（3），合并后，有 ，（4），（5），合并，得 ，綜上，最大相容類有四個(gè)，分別是，。38. 給定集合的覆蓋，如何才能確定此覆蓋的相容關(guān)系。解：相容關(guān)系是具有反對稱性的關(guān)系，集合的任何一個(gè)覆蓋均能確定一個(gè)相容關(guān)系，反之亦然。設(shè)是集合的一個(gè)覆蓋，則由此覆蓋確定的上的相容關(guān)系是：，其中指的子集的笛卡爾積。如是的一個(gè)覆蓋，則此覆蓋確定的上的相容關(guān)系是：39. 設(shè)集合，R是X中的關(guān)系。圖4-23給出了R的關(guān)系圖。試畫出的關(guān)系圖。解：40. 假定是集合X中的恒等關(guān)系，R是X中的任何關(guān)系。試證明：是相容關(guān)系。證明：設(shè)（1）由于，因此，。知是自反的；（2）任取，則或者或者。若，則，；若，則，；若，則，?？芍獰o論任何情況，若，則。故是對稱的。綜上所述，既是自反的又是對稱的，因此，是相容關(guān)系。41. 給定等價(jià)關(guān)系R和S，它們的關(guān)系矩陣是 試證明：不是等價(jià)關(guān)系。證明：可知不是對稱的，因此，不是等價(jià)關(guān)系。42. 設(shè)集合。求出X中的等價(jià)關(guān)系和，使得也是個(gè)等價(jià)關(guān)系。解：設(shè)則和是集合X中的等價(jià)關(guān)系。此時(shí)，也是個(gè)等價(jià)關(guān)系。43. 對于下列集合中的整除關(guān)系畫出哈斯圖。（1）（2）解：（1）（2）44. 如果R是集合X中的偏序關(guān)系，且。試證明：是A中的偏序關(guān)系。證明：因?yàn)镽是集合X中的偏序關(guān)系，所以R是自反的，反對稱的，可傳遞的。（1）因?yàn)镽是自反的，所以； 又，所以； 所以R是自反的。（2）對于任意，若,那么且；又R是反對稱的，所以，即，所以是反對稱的。（3）對于任意，若，那么且。又R是可傳遞的，所以，即：，所以是可傳遞的。由此可知，滿足自反性、反對稱性、可傳遞性，即是A中的偏序關(guān)系。45. 試給出集合X的實(shí)例，它能使是全序集合。解：，則此時(shí)，對于任意的，都有所以是全序集合。46. 給出一個(gè)關(guān)系，它是集合中的偏序關(guān)系又是等價(jià)關(guān)系。解：集合上的恒等關(guān)系，既是偏序關(guān)系又是等價(jià)關(guān)系。47. 證明下列命題：（1）如果是擬序關(guān)系，則也是擬序關(guān)系。（2）如果是偏序關(guān)系，則也是偏序關(guān)系。（3）如果是全序關(guān)系，則也是全序關(guān)系。（4）存在一個(gè)集合和中的關(guān)系R，使得是良序的，但不是良序的。證明：設(shè)是上的二元關(guān)系，（a）若是自反的，則，由于的轉(zhuǎn)置仍是，因此，故