《大連理工大學(xué)軟件學(xué)院離散數(shù)學(xué)習(xí)題答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《大連理工大學(xué)軟件學(xué)院離散數(shù)學(xué)習(xí)題答案（100頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、目 錄 第一章 命題邏輯 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 第十一章 樹 90 100 / 100文檔可自由編輯打印 第一章 命題邏輯 1. （1）不是命題；（2）不是命題；（3）不是命題；（4）是命題；（5）是命題； 2. （1）并非大連的每條街都臨海；（2）2不是一個(gè)偶數(shù)或者8不是一個(gè)奇數(shù)；（3）2不是偶數(shù)

2、并且-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ù)。 逆否命題：如果我能完成這

3、項(xiàng)任務(wù)，則我獲得更多的幫助。 4. （1）T；（2）T；（3）T；（4）F； 5. （1） P Q R 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 （3） P Q R 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 （2）（4）略 6. （1） P:他聰明；Q:他用功；命題

4、：P∧Q。 （2） P:天氣好；Q:我騎車上班；命題：Q→P。 （3） P:老李是球迷；Q:小李是球迷；命題：P∨Q。 （4） P:休息好；Q:身體好；命題：Q→P。 7. 證明： P Q P→Q Q→P P«Q 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 8. 真值表： x y z (x∧y)∧z x∧(y∧z) (x∨y)∨z x∨（y∨z） 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1

5、 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 x y z (x→y)→z x→(y→z) (x«y)«z x«（y«z） 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 可

6、得：∧，∨，«是可結(jié)合的。 9. （1）（P∧Q）→R； （2）┓P； （3）（┓P∧┓Q）→┓R 10. 不依賴于命題變?cè)恼嬷抵概?，而總?cè)（1）的命題公式，稱為重言式（永真式）；不依賴于命題變?cè)恼嬷抵概?，而總?cè)（0）的命題公式，稱為永假式（矛盾式）；至少存在一組真值指派使得命題公式取值為T的命題公式稱為可滿足的。本題可用真值表求解： （4）得真值表如下： P Q 0 0 1 0 1 1 1 0 1 1 1 1 可見不論命題變?cè)恼嬷抵概扇绾危}公式總?cè)?，故為重言式。 （8）得真值表如下： P Q R 0 0

7、0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 可見不論命題變?cè)恼嬷抵概扇绾?，命題公式總?cè)?，故為重言式。 其他小題可用同樣的方法求解。 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）

8、 第（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 故：左式Û右式，證明完畢。 根據(jù)對(duì)偶式定義，該式的

9、對(duì)偶式為： （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∨

10、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）證明：假設(shè)P∧Q為真，則P為真且Q為真，則P→Q為真。 所以：P∧Q Þ P→Q。 （3）證明：右側(cè)Û┓P∨

11、Q，假設(shè)┓P∨Q為假，則P為真且Q為假，則P→Q為假。 所以：P→Q Þ P→P∧Q。 （5）證明：假設(shè)Q→R為假，則Q為真且R為假，則左側(cè)為假。 所以：（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

12、）∨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

13、））∨（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∧

14、┓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）證明： 左側(cè)Û（┓P∨Q）∧（┓P∨R） Û（┓P∨Q∨R）∧（┓P∨Q∨┓R）∧（┓P∨Q∨R）∧（┓P∨┓Q∨R） Û∏（4,5,6） 右側(cè)Û┓P∨（Q∧R）

15、9;…Û∏（4,5,6） 左側(cè)Û右側(cè)，得證。 （3）證明： 左側(cè)Û┓（┓P∨Q）∨（P∧Q） Û（P∧┓Q）∨（P∧Q） Û∑（2,3） 右側(cè)Û（P∨Q）∧（P∨┓Q） Û（P∧P）∨（P∧┓Q）∨（P∧Q）∨（Q∧┓Q） Û（P∧┓Q）∨（P∧Q） Û∑（2,3） 左側(cè)Û右側(cè)，得證。 第（2）、（4）小題方法相同，解答略。 19. 對(duì)于A,B,C,D,E5個(gè)變?cè)乃姓嬷抵概?，推出前提A?B，B?（C∧D），C?（A∨E），A∨E和結(jié)論A∧E的值，得到真值表。當(dāng)真值表中

16、各前提的真值都為1時(shí)，若結(jié)論也為1，則結(jié)論有效，否則結(jié)論無效。 20. （1）采用真值表證明： P Q P→Q P→（P∧Q） 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 根據(jù)真值表可看出，當(dāng)前提為1時(shí)，結(jié)論也為1，則結(jié)論有效。 （3）采用推理方法證明：P∧Q為真，可得P為真且Q為真，又P→（Q→R）為真且P、Q為真，得R也為真。則結(jié)論有效。 第（2）、（4）小題方法相同，解答略。 21. （1）證明： 假設(shè)公式全部同時(shí)成立，由┓S為真得到S為假，由┓P→S為真，得P為真，由P?Q為真得到Q為真，由Q→R為真得到R為真，由

17、┓R∨S為真得到S為真。這與前面“S為假”矛盾，則公式不能同時(shí)成立。 （2）證明： 假設(shè)公式全部同時(shí)成立，由┓S為真得到S為假，由┓R∨S為真得到R為假，由R∨M為真得到M為真，由┓M為真得到M為假，矛盾。則公式不能同時(shí)成立。 22. 首先符號(hào)化：P:大連獲得冠軍；Q:北京獲得亞軍；R:上海獲得亞軍；S:廣州獲得亞軍。 即求公式：P→（Q∨R），R→┓P，S→┓Q，PÞ┓S是否成立。 {1} （1） P P規(guī)則 {2} （2） R→┓P P規(guī)則 {1,2} （3） ┓R T規(guī)則 {4} （4） P→（Q∨R） P規(guī)則 {1,2,4}

18、 （5） Q T規(guī)則 {6} （6） S→┓Q P規(guī)則 {1,2,4,6} （7） ┓S T規(guī)則 23. （1）證明： （1） ┓R P規(guī)則 （2） ┓Q∨R P規(guī)則 （3） ┓Q T規(guī)則（1）（2） （4） ┓（P∧┓Q） P規(guī)則 （5） ┓P T規(guī)則（3）（4） （3）題目有誤 （5）證明： （1） P P規(guī)則（附件前提） （2） P→（P∧Q） P規(guī)則 （3） P∧Q T規(guī)則（1）（2） （4） Q T規(guī)則（1）（3） （5）

19、 P→Q CP規(guī)則 第（2）、（4）小題方法相同，解答略。 24. （1）證明： （1） ┓┓P P規(guī)則（假設(shè)前提） （2） P T規(guī)則（1） （3） P→Q P規(guī)則 （4） Q T規(guī)則（2）（3） （5） R→┓Q P規(guī)則 （6） ┓R T規(guī)則（4）（5） （7） R∨S P規(guī)則 （8） S T規(guī)則（6）（7） （9） S→┓Q P規(guī)則 （10） ┓Q T規(guī)則（8）（9） （11） Q∧┓Q T規(guī)則（4）（10） （12）

20、 ┓P F規(guī)則（1）（11） （2）證明： （1） ┓R P規(guī)則 （2） R∨S P規(guī)則 （3） S T規(guī)則（1）（2） （4） S→┓Q P規(guī)則 （5） ┓Q T規(guī)則（3）（4） （6） P?Q P規(guī)則 （7） ┓P T規(guī)則（5）（6） （3）原式修改為：┓（P→Q）→┓（R∨S），（Q→P）∨┓R，RÞ P?Q 證明： （1） R P規(guī)則 （2） R∨S T規(guī)則（1） （3） ┓（P→Q）→┓（R∨S） P規(guī)則

21、（4） P→Q T規(guī)則（2）（3） （5） （Q→P）∨┓R P規(guī)則 （6） Q→P T規(guī)則（1）（5） （7） （P→Q）∧（Q→P） T規(guī)則（4）（6） （二） P?Q T規(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))

22、 （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)(Pa∧Vx?Ta,x) 2. （1）約束變?cè)簒，轄域：P(x)→Q(x)和R(x,y)；自由變?cè)簓。 （2）約束變?cè)篜x∨Qy中的x,y和R(x)?Sz中的z；自由變?cè)篟(x)?Sz中的x。 （3）約束變?cè)簒,y，轄域：P(x,y)?Qy,z；自由變?cè)簔。 3. 參考教材2.3部分。 4. （1）證明： （1） ("x)&

23、#172;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)；(&q

24、uot;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)

25、 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)

26、 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）

27、($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)∨

28、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)

29、 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）

30、 （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）

31、 ，(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

32、)(( 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(

33、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

34、(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

35、)))) 11. （2）解：前束析取范式： 由于是基本和，因此前束合取范式與前束析取范式一樣： （4）解：前束析取范式： 前束合取范式：  第三章 集合論習(xí)題答案 對(duì)應(yīng)課本頁數(shù)：P51-54 1. 寫出下列集合的表達(dá)式。 (1) 所有一元一次方程的解所組成的集合： 答案：集合可表示為 (2) 在實(shí)數(shù)域中的因式集。 答案：集合可表示為 (3) 直角坐標(biāo)系中，單位圓內(nèi)（不包括單位圓）的點(diǎn)集。 答案：集合可表示為 (4) 極坐標(biāo)系中單位圓外（不包括單位圓）的點(diǎn)集。 答案：集合可表示為 (5) 能被5整除的整數(shù)集。 答案：集合可表示為 2.

36、解： 設(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è)

37、 則 (5) 解：設(shè) 則 7.設(shè)， 解： (1) ， (2) ， (3) ， 8.設(shè)某集合有101個(gè)元素，試問： (1) 可構(gòu)成多少個(gè)子集：2101 (2) 其中有多少個(gè)子集的元素為奇數(shù)：2100 (3) 是否會(huì)有102個(gè)元素的子集：不會(huì) 9. 解：把17化為二進(jìn)制，是00010001，； 把31化為二進(jìn)制，是00011111， ，編碼為01000110，為 ，編碼為10000001，為 10.求A∪B，A∩B。 解： 11. 解： 12.解：

38、 (1) (2) (3) (4) 13.證明對(duì)于所有集合A,B,C有，當(dāng)且僅當(dāng)。 證明：充分性：由于 所以，即 充分性得證。 必要性：由于 所以 所以 必要性得證。 14.證明對(duì)所有集合A,B，C，有： （1） 證明： （2） 證明： （3） 證明： 因此， 15.確定下列各式的運(yùn)算結(jié)果。 解:

39、 16.假設(shè)A和B是E的子集，證明下列各式中每個(gè)關(guān)系式彼此等價(jià)。 (1) 證明： ① 證明～B?～A。 充分性：若，則若，那么必有。因此，若，則必有，即若x∈～B，則有x∈～A，即～B?～A； 必要性：若～B?～A，則若x∈～B，則有x∈～A，即若，則必有。那么，若，那么必有，即； 由以上兩點(diǎn)可知：～B?～A。 ② 證明：A∪B=B 充分性：若，那么有或。 若，則由可知，必有，所以若，必有，即； 若，那么必有，即，所以A∪B=B，充分性得證； 必要性：因?yàn)锳∪B=B，所以，對(duì)于任意的，必有，

40、所以，必要性得證； 由以上兩點(diǎn)可知：A∪B=B ③ 證明：A∩B=A 充分性：若，那么必有，即； 若，那么由可知，必有，所以，即，所以，A∩B=A； 必要性：因?yàn)锳∩B=A，所以對(duì)于任意的，必有，，所以； 由以上兩點(diǎn)可知，A∩B=A。 由以上三點(diǎn)可知，～B?～A? A∪B=B?A∩B=A。 (2) ① 證明:A?～B 充分性：因?yàn)?，所以?duì)于任意的，若，則必有，即x∈～B，所以A?～B； 必要性：因?yàn)锳?～B，所以對(duì)于任意的，若，則必有x∈～B，即，所以； 由以上兩點(diǎn)可知：A?～B ② 證明：B?～A 充分性：因?yàn)?，所以?duì)于任

41、意的，若，則必有，即x∈～A，所以B?～A； 必要性：因?yàn)锽?～A，所以對(duì)于任意的，若，則必有x∈～A，即，所以； 由以上兩點(diǎn)可知：B?～A. 由上可知：A?～B?B?～A. (3) ① 證明：A∪B=E?～A?B 充分性：因?yàn)?A∪B=E，所以若，則必有，即若x∈～A，則必有，所以～A?B； 必要性：因?yàn)锳∪～A=E，又～A?B，必有A∪B=E； 由以上兩點(diǎn)可知：A∪B=E?～A?B ② 證明：A∪B=E?～B?A 充分性：因?yàn)?A∪B=E，所以若，則必有，即若x∈～B，則必有，所以～B?A； 必要性：因?yàn)锽∪～B=E，又～B?A，必有A∪B=E； 由以上兩

42、點(diǎn)可知：A∪B=E?～B?A. 由上可知：A∪B=E?～A?B?～B?A.。 (4) 證明：A=B?A⊕B=? 充分性：由于A=B，所以A∩～B=?,B∩～A=? 所以A⊕B=A∩～B∪B∩～A=? 必要性：因?yàn)锳⊕B=A∩～B∪B∩～A=? 所以A∩～B=?且B∩～A=? 因?yàn)锳∩～B=?，所以A?B 又B∩～A=?，所以B?A 所以A=B。 由上可知：A=B?A⊕B=?。 17.化簡(jiǎn)下述集合公式。 (1) 結(jié)果：A∩B (2) 結(jié)果：A-B (3) 結(jié)果：

43、A (4) 結(jié)果：C∩（A∪B） 18.設(shè)A,B,C是任意集合，分別求使得下述等式成立的充分必要條件。 (1) B?A (2) B∩A=? (3) B=A=? (4) B=A (5) B=? (6) B=A (7) 解：由于，因此必有且。也就是并且。 （8） 解：由于，因此必有且。也就是并且。 (9) 解： 因此，意味著 (10) 解： 兩種可能，第一種，即B=C； 第二種，或者 19.借助文氏圖，考察下列命題的正確性。 E B (1) C A E (2)

44、 A C 20.設(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= 250∕2=125，B= 250∕3=83，C= 250∕5=50，D= 250∕7=35 則所求的答案表達(dá)式為A∪B∪C∪D。 求解：A∪B∪C∪D=125 + 83

45、 +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ì)的隊(duì)員共有18個(gè)。 24. 解：設(shè)A，B，C分別表示讀甲種、乙種、丙種雜志的學(xué)生的集合。 (1) 所以確定讀兩種雜志的學(xué)生的百分比為60%。 (2) 所以不讀任何雜志的學(xué)生的百分比為30%。  第四章 二元關(guān)系習(xí)題答案 對(duì)應(yīng)于課本88-93頁 1.如果A={0,2}和B={1

46、,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.證明： 必要性：若，； 同理，若，； 若，則顯然有； 必要性得證。 充分性性：由于 所以對(duì)于任意的,必有 即若則必有；若

47、，則必有，所以當(dāng)時(shí)，； 充分性得證。 5. （1） 解：任取,有 選擇A={1}，B={2}，C={a}，D= 則 因此該等式不成立。 （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使得A?A×A； 取A= ?，則該命題成立。 （7）PA×P

48、A=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,y∈A ∧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,y∈A ∧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,y

49、x,y∈A ∧x∕y∈A 解：R=1,1，2,1，2,2，3,1，3,3，4,1，4,2，4,4 （4）R= x,yx,y∈A ∧y 為素?cái)?shù) 解：R=1,2，1,3，2,2，2,3，3,2，3,3，4,2，4,3 7.列出集合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,4 8.給出下列關(guān)系R的所有序偶。 （1） 解： （2） 解： 9.設(shè)和都是從到的二元關(guān)系，并且 求、、、、、、、。 解： fld

50、R1-R2=fld1,2,3,3=1,2∪2,3=1,2,3 R1°R2=1,4,2,2 R2°R1=1,3,4,4 R12=1,4,3,3 R23=4,4,2,2 10.設(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，求R°R，R-1，R1,2，R1,2 解： R°R= 0,2，0,3，1,3 R-1= 1，0，2，0，3，0，2，1，3，1，3，2 R1,2= 1，2，1，3，2，3 R1,2= 2,3 12.設(shè)關(guān)系R=?，?，?，?，?，求R-1，R2，R3，

51、R?，R?,R|?,R?， R?。 解：R-1=?，?，?，?，? R2= ?，?，? R3= ? R? = ?，?，? R|?= ? R|?=?，? R?= ? 13.說明以下關(guān)系R具有那些性質(zhì)并說明理由。 （1）：反自反的、反對(duì)稱的、可傳遞的； （2）：反自反的、對(duì)稱的、不可傳遞的； （3）：自反、對(duì)稱、可傳遞； （4）：自反、對(duì)稱、可傳遞； 14.設(shè)A是所有人的集合，定義A上的二元關(guān)系R1和R2，說明R1和R2具有哪些性質(zhì)。 解：R1具有的性質(zhì)：反自反的、反對(duì)稱的、可傳遞的； R2具有的性質(zhì)：自反、對(duì)稱、可傳遞；

52、 15. 設(shè)和是集合X中的二元關(guān)系。試證或反證下列命題： （1）如果和是自反的，則也是自反的。 （2）如果和是反自反的，則也是反自反的。 （3）如果和是對(duì)稱的，則也是對(duì)稱的。 （4）如果和是反對(duì)稱的，則也是反對(duì)稱的。 （5）如果和是可傳遞的，則也是可傳遞的。 解：（1）證明：任取，由于和是自反的，因此，，可得，由x取值的任意性可知，是自反的。 （2）設(shè)，則，不是反自反的。 （3）設(shè)，則，不是對(duì)稱的。 （4）設(shè)，則，不是反對(duì)稱的。 （5）設(shè) ，則，不可傳遞。 16.證明：若R是集合A上的自反和可傳遞關(guān)系，則R°R=R。 證明：任意取x,y∈A ,x,y∈R,由于R是集合

53、A上的自反，則可知y,y，x,x∈R， 則R = {x,y,x,y,y,y,x,x} R°R= {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都是自反的， 所以對(duì)于都有， 對(duì)于都有。 （1）設(shè)，那么或。 若，有，那么必有。 若，有，那么必有。 因此，當(dāng)時(shí)，必有， 所以也是自反的。 （2）設(shè)，那么 因此且，即。 所以也是自反的。 18.證明：如果關(guān)系R和S都是自反的、對(duì)稱的、可傳遞的，證明：也是自反的、對(duì)稱的和可傳遞的。

54、 證明：設(shè)R是集合A上的二元關(guān)系，S是集合B上的二元關(guān)系。 ①自反性的證明如題4。 ② 對(duì)于任意的，若， 那么且 因?yàn)镽和S都是對(duì)稱的，所以且， 所以。 即對(duì)于任意的，若，則必有， 所以是對(duì)稱的。 ③ 對(duì)于任意，若且， 那么有。 因?yàn)镽和S都是可傳遞的， 所以有且，即。 即對(duì)于任意，若且，都有。 所以是可傳遞的。 19.設(shè)集合A是有限集，且A=n，求： （1）A上有多少不同的對(duì)稱關(guān)系。 解： 也就是說集合A有n平方個(gè)有序?qū)?，由?duì)稱定義可知，對(duì)于。另外知道在n平方個(gè)有序?qū)χ杏衝 個(gè)有序?qū)?，相?yīng)的就有個(gè)有序?qū)Γ╔,Y)且X，定義可知后面的個(gè)有序?qū)χ荒艹蓪?duì)出現(xiàn)，所

55、以有對(duì)。前面的那n對(duì)可以出現(xiàn)任意多對(duì)。圖片如下。 （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ū)?duì) 共有n+ ()/2 個(gè)元素 即 ()/2個(gè) 所以得到對(duì)稱關(guān)系數(shù)為： （2）A上有多少不同的反對(duì)稱關(guān)系。 由定義：如果 如下圖。 （1,1) (2,2

56、)......................(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ū)?duì) (由6可知） 所以得結(jié)果 ：即 （3）A上有多少不同的既非自反又非反自反的關(guān)系。 解： 20.試著畫出R的關(guān)系圖并寫出對(duì)

57、應(yīng)的關(guān)系矩陣。 解： 關(guān)系圖如下： 21. 設(shè)，和是A中的關(guān)系， 試求出關(guān)系矩陣：；；；；；。 解： 由此可得： 所以： 22. 給定集合。圖4-6給出了A中的關(guān)系R的12個(gè)關(guān)系圖。對(duì)于每個(gè)關(guān)系圖，寫出相應(yīng)的關(guān)系矩陣，并證明被表達(dá)的關(guān)系是否是自反的或反自反的；是否是對(duì)稱的或反對(duì)稱的；是否是可傳遞的。 （1）自反的、不對(duì)稱的、不可傳遞的； 其對(duì)應(yīng)的關(guān)

58、系矩陣為： （2）不自反的、反對(duì)稱的、不可傳遞的； 其對(duì)應(yīng)的關(guān)系矩陣為： （3）自反的、對(duì)稱的、可傳遞的； 其對(duì)應(yīng)的關(guān)系矩陣為： （4）自反的、不對(duì)稱的、不可傳遞的； 其對(duì)應(yīng)的關(guān)系矩陣為: （5）不自反的、不對(duì)稱的、不可傳遞的； 其對(duì)應(yīng)的關(guān)系矩陣為： （6）不自反的、對(duì)稱的、不可傳遞的； 其對(duì)應(yīng)的關(guān)系矩陣為： （7）自反的、反對(duì)稱的、可傳遞的； 其對(duì)應(yīng)的關(guān)系矩陣為： （8）自反的、不對(duì)稱的、不可傳遞的； 其對(duì)應(yīng)的關(guān)系矩陣為： （9）不自反的、對(duì)稱的、可傳遞的；

59、此題圖有錯(cuò)誤 其對(duì)應(yīng)的關(guān)系矩陣為： （10）自反的、反對(duì)稱的、不可傳遞的； 其對(duì)應(yīng)的關(guān)系矩陣為： （11）自反的、反對(duì)稱的、可傳遞的； 其對(duì)應(yīng)的關(guān)系矩陣為： （12）不自反的、反對(duì)稱的、可傳遞的。 其對(duì)應(yīng)的關(guān)系矩陣為： 23. 設(shè)X是一個(gè)集合，和是X中的二元關(guān)系，并設(shè)，試證明： （1） （2） （3） 證明：a）因?yàn)?，故R1∪IA??R2∪IA，即 b）因?yàn)閟（R1）對(duì)稱，且s（R1）?R1，但R1?R2，故s（R1）?R2，由s（R2）的定義，s（R2）是包含R2的最小對(duì)稱關(guān)系，故 s（R1）?s（R

60、2） c）因?yàn)閠（R1）傳遞，且t（R1）?R1，但R1?R2，故t（R1）?R2 因t（R2）是包含R2的最小傳遞關(guān)系，所以 t（R1）?t（R2） 24.在圖4.23中給出三個(gè)關(guān)系圖。試求每一個(gè)的自反的、對(duì)稱的和可傳遞的閉包，并畫出閉包的關(guān)系圖。 （1）解：由關(guān)系圖可知， 則： （2）解：由關(guān)系圖可知， 則： （3）解：由關(guān)系圖可知， 則： 25．和是集合A中的關(guān)系。試證明： （1） （2） （3） 證明： (

61、1)r（R1∪R2）= R1∪R2∪IA= R1∪IA∪R2∪IA =r（R1）r∪（R2） 2）s（R1∪R2）=（R1∪R2）∪（R1∪R2）C = R1∪R2∪R1C∪R2C =（R1∪R1C）∪（R2∪R2C） =s（R1）∪s（R2） 3）因?yàn)镽1∪R2?R1，由習(xí)題3-98，則t（R1∪R2）=t（R1） 同理 t（R1∪R2）=t（R2） 所以 t（R1∪R2）= t（R1）∪t（R2） 26. 設(shè)集合，是中的二元關(guān)系，圖4-12給出了的關(guān)系圖。試畫出可傳遞閉包的關(guān)系圖，并求出。 解：由關(guān)系圖可知， 則： 27. 設(shè)是集合中的任意關(guān)系

62、。試證明： （1） （2） （3） 證明： a）（R+）+= t（t（R）），因?yàn)閠（R）是傳遞的，根據(jù)定理3-8.1，t（t（R））= t（R）， 即（R+）+= R+。 b）R○R*= R○（tr（R））= R○（rt（R））= R○（t（R）∪IA） ∞ = R○t（R）R○∪IA= R○R∪ ∞ ∞ i=1 =R∪iR=R∪∪i= 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

63、*。 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)如何識(shí)別等價(jià)類？ 解：如果兩個(gè)

64、元素之間有兩條連線，那么說明這兩個(gè)元素是等價(jià)類。 33. 設(shè)R是集合X中的關(guān)系。對(duì)于所有的，如果，就有 ，則稱關(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的對(duì)稱性，知。根據(jù)x，y，z取值的任意性，知R是循環(huán)的。 （2）當(dāng)R是自反的，可知對(duì)任意，。任取，使得，因?yàn)镽是循環(huán)的，故當(dāng)，時(shí)，。由x，y取值的任意性知，R是對(duì)稱的；任取，，由R的循環(huán)性知，，因?yàn)镽是對(duì)稱的，因此，由x，y，z取值的任意性，知R是可傳遞的。因?yàn)镽是自反的、對(duì)稱的和

65、可傳遞的，因此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） 如果，那么對(duì)任意的→ 永真，等價(jià)于x,y落入的某個(gè)等價(jià)類中，等價(jià)于x,y落入的某個(gè)等價(jià)類中，即若，則，由x,y的任意性可知，,由i的任意性可知，中的每一個(gè)等價(jià)類都包含在

66、的某一個(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)槭亲苑吹模詫?duì)于任意的，都有對(duì)于任意的，故，所以是自反的； ② 對(duì)于任意的，若，則且。又是對(duì)稱的，所以有，，故，即是對(duì)稱的； ③ 對(duì)于任意的，若，，則，且，。又是可傳遞的，所以有，，故，即是可傳遞的； 綜上，是等價(jià)關(guān)系。 (2) ① 因?yàn)槭亲苑吹?，所以?duì)于任意的，都有對(duì)于任意的，故，所以是自反的； ② 對(duì)于任意的，若，則可

67、能有三種情況： 若且，那么因?yàn)槭菍?duì)稱的，所以有，，故，即是對(duì)稱的； 若但，那么有且，此時(shí)，即是對(duì)稱的； 所以是對(duì)稱的； 若但，那么有且，此時(shí)，即是對(duì)稱的； ③ 對(duì)于任意的，若，，當(dāng) ，時(shí)，不能確定，故不是可傳遞的。 由上可知，不是等價(jià)關(guān)系。 （1） （2）， （3），，，，，合并后，有 ， （4），， （5），，，，，，合并，得 ，，， 綜上，最大相容類有四個(gè)，分別是，，，。 38. 給定集合的覆蓋，如何才能確定此覆蓋的相容關(guān)系。 解：相容關(guān)系是具有反對(duì)稱性的關(guān)系，集合的任何一個(gè)覆蓋均能確定一個(gè)相容關(guān)系，反之亦然。 設(shè)是集合的一個(gè)覆

68、蓋，則由此覆蓋確定的上的相容關(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）任取，，則或者或者。 若，則，，； 若，則，； 若，則，。 可知無論任何情況，若，則。故是對(duì)稱的。 綜上所述，既是自反的又是對(duì)稱的，因此，是相容關(guān)系。 41. 給定等價(jià)關(guān)系R和S，它們的關(guān)系矩陣是 試證明：不是等價(jià)關(guān)系。

69、 證明： 可知不是對(duì)稱的，因此，不是等價(jià)關(guān)系。 42. 設(shè)集合。求出X中的等價(jià)關(guān)系和，使得也是個(gè)等價(jià)關(guān)系。 解：設(shè) 則和是集合X中的等價(jià)關(guān)系。 此時(shí)，也是個(gè)等價(jià)關(guān)系。 43. 對(duì)于下列集合中的整除關(guān)系畫出哈斯圖。 （1） （2） 解：（1） （2） 44. 如果R是集合X中的偏序關(guān)系，且。試證明：是A中的偏序關(guān)系。 證明：因?yàn)镽是集合X中的偏序關(guān)系，所以R是自反的，反對(duì)稱的，可傳遞的。 （1）因?yàn)镽是自反的，所以； 又，所以； 所以R是自反的。 （2）對(duì)于任意，若,那么且；又R是反對(duì)稱的，所以，即，所以是反對(duì)稱的。 （3）

70、對(duì)于任意，若，那么且。又R是可傳遞的，所以，，即：，所以是可傳遞的。 由此可知，滿足自反性、反對(duì)稱性、可傳遞性，即是A中的偏序關(guān)系。 45. 試給出集合X的實(shí)例，它能使是全序集合。 解：，則 此時(shí)，對(duì)于任意的，都有 所以是全序集合。 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)置仍是，因此，，故