離散數(shù)學(xué)習(xí)題答案2015

1、離散數(shù)學(xué)習(xí)題答案習(xí)題一1、利用邏輯聯(lián)結(jié)詞把下列命題翻譯成符號邏輯形式（1） 他既是本片的編劇，又是導(dǎo)演 - P Q（2） 銀行利率一降低，股價(jià)隨之上揚(yáng)- P Q（3） 盡管銀行利率降低，股價(jià)卻沒有上揚(yáng)- P Q（4） 占據(jù)空間的、有質(zhì)量而且不斷變化的對象稱為物質(zhì) - M ßà(SPT)（5） 他今天不是乘火車去北京，就是隨旅行團(tuán)去了九寨溝- P Q（6） 小張身體單薄，但是極少生病，并且頭腦好使- P Q R（7） 不識廬山真面目，只緣身在此山中- P Q（解釋：因?yàn)樯碓诖松街校圆蛔R廬山真面目）（8） 兩個(gè)三角形相似，當(dāng)且僅當(dāng)他們的對應(yīng)角相等或者對應(yīng)邊成比例- S &#

2、223;à(ET)（9） 如果一個(gè)整數(shù)能被6整除，那么它就能被2和3整除。如果一個(gè)整數(shù)能被3整除，那么它的各位數(shù)字之和也能被3整除解：設(shè) P 一個(gè)整數(shù)能被6整除Q 一個(gè)整數(shù)能被2整除R 一個(gè)整數(shù)能被3整除S 一個(gè)整數(shù)各位數(shù)字之和能被3整除翻譯為：（P （Q R） （R S）2、判別下面各語句是否命題，如果是命題，說出它的真值（1）BASIC語言是最完美的程序設(shè)計(jì)語言- Y，T/F（2）這件事大概是小王干的- N（3）x2 = 64- N（4）可導(dǎo)的實(shí)函數(shù)都是連續(xù)函數(shù)- Y，T/F（5）我們要發(fā)揚(yáng)連續(xù)作戰(zhàn)的作風(fēng)，再接再厲，爭取更大的勝利- N（6）客觀規(guī)律是不以人們意志為轉(zhuǎn)移的- Y，

3、T（7）到2020年，中國的國民生產(chǎn)總值將趕上和超過美國- Y，N/A（8）凡事都有例外- Y，F(xiàn)3、構(gòu)造下列公式的真值表，并由此判別哪些公式是永真式、矛盾式或可滿足式（1）（P （P Q） Q解：PQP QP （P Q）（P （P Q） Q可滿足式00001011111001011011（2）（4）表略：（2）可滿足式、（3）永真式 、（4）可滿足式4、利用真值表方法驗(yàn)證下列各式為永真式（1）（8）略5、證明下列各等價(jià)式（3）P（Q R）ó （P Q）（P R）證明：左式óPQ Ró PQP Ró （PQ）（P R）ó （P Q）（P R）&

4、#243; 右式（4）（P Q）（R Q）（R P）ó （P Q）（R Q）（R P）證明：左式ó(（PR） Q）（R P）ó (（PR）R) ) (（PR）P) ) （QR）（QP）ó （P Q）（R Q）（R P）ó 右式6、如果P Q ó QR,能否斷定 P ó R ？ 如果P Q ó QR，能否斷定 P ó R？如果P ó R，能否斷定 P ó R？解：（1）如果P Q ó QR，不能判斷P ó R，因?yàn)槿绻?Q = P R, 那么P Qó PP

5、R ó QR，但P可以不等價(jià)于R. （2）如果P Q ó QR，不能判斷P ó R，因?yàn)槿绻?Q = P R, 那么P Qó PP R ó QR，但P可以不等價(jià)于R.（3）如果P ó R，那么有P ó R，因?yàn)镻 ó R，則P <-> R為永真式，及有P <-> R為永真式，所以P ó R.8、把下列各式用等價(jià)表示出來（1）(PQ) P解：原式 ó (PQ) (PQ) (PP)ó (PQ) (PQ) (PQ) (PQ) (PP) (PP)9、證明： 是最小功能完

6、備集合證明:因?yàn)? 是最小功能完備集合,所以,如果 能表示出,則其是功能完備集合。由于 P Q ó (P) Q ,所以 是功能完備集合。因?yàn)?不能相互表示，所以 是最小功能完備集合；同理可證：非，條件非也能將或表示出來：P Q ó (P ! Q)8、分別利用真值表法和等價(jià)變換法求下列公式的主合取范式及主析取范式:(3) P(R(QP)解：真值表法PQRQPR(QP)P(R(QP)000101001111010001011001100100101111110100111111所以：主合取范式為 = (PQR) (PQR) = M4M6主析取范式為 = (PQR)(PQR)(P

7、QR)(PQR)(PQR)(PQR) = m0m1m2m3m5m7等價(jià)變換法（略）(4) (P(QR) (P(QR)解：真值表法PQRQRQRP(QR)P(QR)(P(QR) (P(QR)0000111100100100010001000111010010001010101000101100001011110111所以：主合取范式為 = (PQR) ( PQR) ( PQR) (PQR) ( PQR) ( PQR) = M1M2M3M4M5M6主析取范式為 = (PQR)(PQR) = m0m7等價(jià)變換法（略）14、從A,B,C,D 4個(gè)人中派2人出差，要求滿足下列條件：如果A去，則必須在C或

8、D中選一人同去；B和C不能同時(shí)去；C和D不能同時(shí)去。用構(gòu)造范式的方法決定選派方案。解：由題設(shè) A：A去，B：B去，C：C去，D：D去則滿足條件的選派應(yīng)滿足如下范式：（A（CÑD）（BC）（CD）構(gòu)造和以上范式等價(jià)的主析取范式（A（CÑD）（BC）（CD）Û（AB C D ）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）共有八個(gè)極小項(xiàng)，但根據(jù)題意，需派兩人出差，所以，只有其中三項(xiàng)滿足要求： （ABCD），（ABCD），（ABCD）即有三種方案：A和C去或者A和D去或者B和D去。15、證明下列蘊(yùn)含試：（1）PQ=>P (PQ

9、)證明：PQ Û P Q Û T(P Q) Û (PP) (P Q) Û P (PQ)Û P (PQ)所以，這是個(gè)等價(jià)式，因此也是個(gè)蘊(yùn)含式（2）(PQ) Q=> (PQ)證明：(PQ) Q Û (PQ) Q Û (PQ) Q Û (PQ) (QQ) Û (PQ) T Û (PQ)所以，這是個(gè)等價(jià)式，因此也是個(gè)蘊(yùn)含式（3）PPR=>S證明：PPR Û F => S (F可蘊(yùn)含任何命題公式)（4）P=>QRR證明：P=>T Û QRR （任何公式可蘊(yùn)

10、含永真式）18、一個(gè)有錢人生前留下了一筆珍寶，藏在一個(gè)隱秘處。在他留下的遺囑中指出尋找珍寶的線索如下：（1） 如果藏寶的房子靠近池塘，那么珍寶不會藏在東廂房。（2） 如果房子的前院栽有大柏樹，那么珍寶就藏在東廂房。（3） 藏寶房子靠近池塘。（4） 要么前院栽有大柏樹，要么珍寶埋在花園正中地下。（5） 如果后院栽有香樟樹，珍寶藏在附近。請利用蘊(yùn)含關(guān)系找出藏寶處解：根據(jù)給定的條件有下述命題：P：珍寶藏在東廂房Q：藏寶的房子靠近池塘R：房子的前院栽有大柏樹S：珍寶藏在花園正中地下T：后院栽有香樟樹M：珍寶藏在附近根據(jù)題意，得出：（QP）（RP）Q（RS）（TM） Þ？（QP）（RP）Q（R

11、S）（TM） ÞP（RP）（RS）（TM） ÞR（RS）（TM） ÞS（TM）ÞS 即珍寶藏在花園正中地下20、演繹證明下面各蘊(yùn)含式：（4）(RQ) (RS),(QE) (SB), (EB),(PR) Þ P證明：運(yùn)用反證方法，將結(jié)論的非納入前提，證明步驟如下1Pp(附加前提)2PRp3RT 1,2 I4(RQ) (RS)p5QST 3,4 I6(QE) (SB)p7EBT 5,6 I8(EB)p9F(矛盾式)T 7,8 E（5）P(QR),Q(RS) Þ P(QS)證明：運(yùn)用cp法，將結(jié)論條件式的前件作為前提，證明步驟如下1Pp(附

12、加前提)2P(QR)p3QRT 1,2 I4Q(RS)p5R(QS)T 4 E6QST 3,5 I7P(QS)CP 1,621、把下列句子演繹成邏輯形式，并給出證明（2）某公司發(fā)生了一起盜竊案，經(jīng)仔細(xì)偵察，掌握了如下一些事實(shí)：l 被盜現(xiàn)場沒有留下任何痕跡l 失盜時(shí)，小花或則小英正在卡拉ok廳l 如果失竊時(shí)小胖正在附近，他就會習(xí)慣性地破門而入偷走東西后揚(yáng)長而去l 如果失盜時(shí)小花正在卡拉ok廳唱歌，那么金剛是最大的嫌疑者l 如果失盜時(shí)小胖不在附近，那么他的女友小英會和他一起外出旅游l 如果失盜時(shí)小英正在卡拉ok廳唱歌，那么瘦子是最大的嫌疑者根據(jù)以上事實(shí)，請通過演繹推理找出偷竊者解：根據(jù)給定的條件有

13、下述命題：P：現(xiàn)場無任何痕跡Q：失竊時(shí)，小花在OK廳R：失竊時(shí)，小英在OK廳S：失竊時(shí)，小胖在附近T：金剛是偷竊者M(jìn)：瘦子是偷竊者則根據(jù)案情有如下命題公式：P，QR，S P，Q T， S R，R M P P SP P S TI SR P R TI QR P Q TI QT P T TI即 金剛是偷竊者23、利用消解法證明下列各蘊(yùn)含式：（3）P(QR),Q(RS) Þ P(QS)證明：P(QR) Û PQRQ(RS) Û QRS（P(QS)）Û PQS因此子句集合 = PQR，QRS，P，Q，S 消解過程如下：1PQRp2Pp3QR由1，2歸結(jié)4Qp5R由

14、3，4歸結(jié)6QRSp7Sp8QR由6，7歸結(jié)9R由4，8歸結(jié)10FLASE 由5，9歸結(jié)導(dǎo)出空子句習(xí)題二1、把下列謂詞翻譯成謂詞公式（1）每個(gè)有理數(shù)都是實(shí)數(shù)，但是并非每個(gè)實(shí)數(shù)都是有理數(shù)，有些實(shí)數(shù)是有理數(shù)解： R(x)-x是實(shí)數(shù)Ra(x)-x是有利數(shù)翻譯如下："(x)( Ra(x) R(x) "(x)( R(x) Ra(x)$(x)( R(x) Ra(x)）（2）直線a和b平行當(dāng)切僅當(dāng)a和b不相交解：A(x)-x是直線 F(x，y)-x與y平行G（x,y)-與相交 翻譯如下："()"()（A()A() (F(，) «G（,)）)（3）除非所有的會

15、員都參加，這個(gè)活動(dòng)才有意義解：A(x)-是會員B(x)-x有意義-這個(gè)活動(dòng)F(x，y)-參加翻譯如下：B（）"(x)（A(x)F(x，)） 或"(x)（A(x)F(x，)）B（）（4）任何正整數(shù)不是合數(shù)就是質(zhì)數(shù)解：A(x)-是正整數(shù)(x)-是合數(shù)(x)-是質(zhì)數(shù)翻譯如下："(x)（A(x)(x)Ñ(x)）（6） 凡是存錢的人都想有利息，如果沒有利息，人們就不會存錢解：A(x)-是存錢的人F(x，y)-想有P-存錢沒有利息Q:-人們不存錢a:-利息翻譯如下："(x)（A(x)F(x，a)）（PQ）2、設(shè)論域D = 0, 1, 2，把下列公式用不含量

16、詞的公式表示出來（3）"(x) P(x) $(x)Q(x)解：上式 Û （P(0) P(1) P(2)） Q(0) Q(1) Q(2)3、指出下列公式中的約束變元和自由變元，并確定公式的轄域解：略5、把下列語句符號化，并確定相應(yīng)謂詞公式是永真式、可滿足式、還是矛盾式（1）如果兩個(gè)數(shù)的積等于0，那么至少其中一個(gè)數(shù)為0，數(shù)x-1不等于0，所以數(shù)x-1和x+1的積也不等于0解：設(shè)論域在任意數(shù)域集合，運(yùn)用常規(guī)的數(shù)學(xué)符號，翻譯如下"(x) "(y)( xy = 0 (x=0 y=0) (x-1 0) (x-1)(x+1) 0)這是一個(gè)可滿足式，但不是永真式，因?yàn)榇?/p>

17、在x=-1時(shí)，謂詞公式不成立，但其它情況均成立，如果論域中不包含-1，為真，包含就不成立（2）誠實(shí)的人都講實(shí)話。小林不是誠實(shí)的，因而小林不講實(shí)話解：H(x)-x誠實(shí)T(x)-x講真話a-小林翻譯如下：（"(x)(H(x) T(x) H(a)） T(a)這是一個(gè)可滿足式，因?yàn)榉穸l件命題前件，不一定后件命題一定為假。及小林雖然不誠實(shí)，但也可能講實(shí)話6、對于題目給定的解釋，求下列各公式相應(yīng)的真值（1） A = "(x) P(x) Q(x) R(a)，解釋 D =1,2,3，P(x): x2+x=2; Q(x): x是素?cái)?shù)；R(x): x<3; a = 1解： 根據(jù)解釋，A

18、變?yōu)?（P(1) Q(1)）（P(2) Q(2)）（P(3) Q(2)）R(1)，根據(jù)P(x), Q(x), R(x)的定義，顯然P(1) Q(1) = 1，P(2) Q(2) = 1，P(3) Q(2) = 1，R(1) =1，所以整個(gè)公式解釋為真（2） A=P(a, f(b) P(b,f(a), B="(x) $(y)P(y,x), C = $(y) "(x)P(y,x), E = "(x) "(y)P(x,y) P(f(x),f(y)，解釋：D=2,3, a = 3, b = 2, f(2)=3, f(3) =2，P(2,2)=0, P(2,3)=

19、0, P(3,2)=P(3,3) = 1解： 根據(jù)解釋，A變?yōu)?P( 3, 3 ) P( 2, 2 ) = 1 0 = 0 ，真值為假B變?yōu)?(P(2,2) P(2,3) (P(3,2) P(3,3) = （00）（11）= 0，真值為假C變?yōu)?(P(2,2) P(2,3) (P(3,2) P(3,3) = （00）（11）= 1，真值為真E變?yōu)?(P(2,2) P(3,3) (P(2,3) P(3,2) (P(3,2) P(2,3) (P(3,3) P(2,2) = （01）（01）（10）（10）= 0，真值為假7、設(shè)論域?yàn)檎麛?shù)集合Z，試判定下面各公式是否是永真式，矛盾式或可滿足式（1）&

20、quot;(x)x>-10x20答：為假命題（2）$(x)2x>8x2-6x+50答：為真命題，當(dāng)4，5使?jié)M足謂詞公式（3）"(x) $(y)x+y=1024答：為真命題，對任意整數(shù)x，y取值為1024-x及可（4）$(y) "(x)xy<10x+y2答：為真命題，y=0及成立9、證明下列各式成立：（1）"(x) "(y)P(x) Q(y) ó$(x)P(x) "(y)Q(y)證明：右式 ó "(x) "(y) P(x) Q(y) ó "(x) P(x) "

21、(y)Q(y) ó$(x)P(x) "(y)Q(y)10、判別$(x)P(x) Q(x)ó $(x)P(x) $(x)Q(x)是否成立，如果成立，請給出證明；如果不成立，找一個(gè)解釋予以說明解：$(x)P(x) Q(x) ó $(x) P(x) Q(x) ó $(x) P(x) $(x)Q(x) ó "(x) P(x) $(x)Q(x) 顯然和$(x)P(x) $(x)Q(x)不等價(jià)，現(xiàn)構(gòu)造如下解釋設(shè)論域?yàn)镈=a,b，P(a) = 0, P(b) = 1, Q(a) = 0, Q(b) = 0, 則$(x)P(x) Q(x)解

22、釋為真，而$(x)P(x) $(x)Q(x)解釋為假，所以不等價(jià)11、把下列公式化為等價(jià)的前束范式，再求出對應(yīng)的SKolem范式（4）"(x) P(x,0) ($(y)P(y,f(x) "(z)Q(x,z)解：原式 ó "(x) P(x,0) ($(y)P(y,f(x) "(z)Q(x,z) ó "(x) $(y) "(z) P(x,0) (P(y,f(x) Q(x,z)其SKolem范式為："(x) "(z) P(x,0) (P(g(x),f(x) Q(x,z)13、證明下列各式成立（1）$(

23、x) $(y)P(x) Q(y) Þ$(x)P(x)證明：左式 ó $(x) P(x) $(y)Q(y) Þ $(x)P(x)（2）($(x)P(x) Q(a) Þ$(x)P(x) Q(a)證明：左式 ó $(x)P(x) Q(a) ó $(x)P(x) Q(a)15、下面給出了對"(x) P(x) Q(x) Þ"(x) P(x) "(x)Q(x)的證明：（原證明過程略）試判斷這個(gè)證明是否正確。你能給出一個(gè)證明嗎？答：這個(gè)證明不正確，因?yàn)椋喝绻?P Þ Q 則QÞ P 而 P

24、 Þ Q不一定成立，因此在這個(gè)證明過程中，第二步到第三步的蘊(yùn)含不成立17、判別下面各個(gè)推理是否正確，如果不正確，指出錯(cuò)在什么地方（題目不再重復(fù)）（1）答：不正確，全稱指定應(yīng)該變?yōu)槠渌莤的變元，可修改為：P(y) Q(x)（2）答：正確（3）答：不正確，全稱指定應(yīng)該使用相同的個(gè)體常量，可修改為：P(a) Q(a)（4）答：題目不正確，存在量詞的指導(dǎo)變元應(yīng)該是另外的變元符號（5）答：不正確，存在量詞的轄域應(yīng)該包含全部的謂詞，可修改為：$(x)P(x) Q(x) （6）答：不正確，對不同的個(gè)體常元應(yīng)該用不同的變元進(jìn)行存在指定，可修改為：$(x)P(x) Q(b) （7）答：不正確，推理過

25、程中，應(yīng)該先使用存在指定，然后使用全稱指定習(xí)題三4、仔細(xì)區(qū)分集合中的關(guān)系符號 和Í，并判斷下列各蘊(yùn)含關(guān)系的真假（題目內(nèi)容，見課本）（1）真，根據(jù)子集的定義，任何屬于B集合的元素也屬于C集合（2）假，例如：A = 1,2 B = 1,2, 2, 3 C=B，1屬于A，但并不是C集的元素（3）假，例如：A=1,2 B=1,2,3 C=1,2,3，A不是C的元素（4）假，例如：A=1,2 B=1,2,3 C=1,2,3，A不是C的子集（5）假，例如：A=1 B=1,2,3 C=1,2,3，A不是C的元素（6）真，子集關(guān)系具有傳遞性9、證明下列各式（1）A(B-C) = (AB)-(AC)

26、證明：左式 = A(BC) = (ABC) (ABA) = (AB) (CA) = (AB) (AC) = (AB)-(AC) = 右式（2）A - (BC) = (A-B) (A-C)證明：右式 = (AB)(AC) = ABC = A(BC) = A - (BC) = 左式（3）(A-B)-C = A-(BC)=(A-C)-B證明：(A-B)-C = ABC = A(BC) = A-(BC) = ACB = (A-C)-B（4）A(BC)=(AB) C ó CÍA證明：充分性 A(BC)=(AB) C ó (AB) (AC) = (AB) C假設(shè)C不是A的子集

27、，則C中必存在元素c在C中而不在A中，那么c一定不在等式的左端集合中，而一定在右端集合中，矛盾 CÍA必要性 CÍA ， AC = C ，等式兩端同時(shí)并上另一個(gè)集合，等式成立 (AB) (AC) = (AB) C ó A(BC)=(AB) C（5）A(BC) = (AB) (AC)證明：左式 = A（B C-BC）= A（(B C) (BC)）= A(B C) (BC)=ABC + ACB右式 = （(AB) (AC)）- （(AB) (AC)）= （A(BC)）（ABC）= A(BC) (ABC) = ABC + ACB 所以，左式 = 右式10、下面三式中，哪

28、個(gè)可得出B=C的結(jié)論（1）AB=AC答：不能得出此結(jié)論，因?yàn)槿绻?B C,但B,C都是A的子集，AB=AC成立（2）AB=AC答：不能得出此結(jié)論，因?yàn)锽 C，但A是CB子集，AB=AC成立（2） AB=AC答：能，因?yàn)锳A = ,A = A=A,同時(shí)，（AB）C = A（BC）所以，已知等式兩端 AAB= AAC óB =C ó B=C16、求A=Æ, a, b的冪集解：2A = Æ, Æ , a , b , Æ,a , Æ,b , a, b , Æ, a, b17、設(shè)A,B是任意兩集合，證明（1）2A È

29、; 2B Í 2 A È B，給出等號成立的條件證明：X Î 2A È 2B Û X Î 2A Ú X Î 2B Û X Í A Ú X Í B => X Í A È B Û X Î 2 A È B等號成立的條件: A Í B或B Í A(因?yàn)槿鬉和B沒有子集關(guān)系, 必有a ÎA B和 b ÎB A，使a, b Î 2 A È B ，但a, b Ï 2

30、A È 2B )（2）2AÇ 2B = 2 A Ç B 證明：X Î 2AÇ 2B Û X Î 2A Ù X Î 2B Û X Í A Ù X Í B Û X Í A Ç B Û X Î 2 A Ç B附加題：證明等式(AB) C = A(BC)證明：A(BC) = A(B-C)(C-B) = (A - (B-C)(C-B) (B-C)(C-B)- A)= ABC + ABC + ABC + ABC(AB)

31、 C = C(AB)那么按上式的劃簡方式，就是把C替換為A, 把A替換為B,將B替換為C,所以C(AB) = CAB + CAB + CAB + CAB = ABC + ABC + ABC + ABC習(xí)題四1、設(shè)A=1,2,3,4,B=0,1,4,9,12.分別把下面定義的從集合A到集合B的二元關(guān)系R用序偶的集合表示出來（1）xRy Ûx|y解: R = (1,0) ,(1,1),(1,4) ,(1,9) ,(1,12) ,(2,0) ,(2,4) ,(2,12) , (3,0) ,(3,9) ,(3,12) ,(4,0) ,(4,4) ,(4,12)（2）xRy Û x&

32、#186;y(mod 3)解: R =(1,1), (1,4) , (3,0) , (3,9) , (3,12) , (4,1) , (4,4)（3）xRy Û y/x £ (y-x)/2解: R =(3,9), (3,12) , (4,9) , (4,12)2、用關(guān)系圖和關(guān)系矩陣表示第1題中的各個(gè)關(guān)系解：略6、設(shè)在整數(shù)集Z上定義如下二元關(guān)系，試填寫下表： 解：填表如下R自反性反自反性對稱性反對稱性傳遞性x|y×××xy(mod m)××xy>0×××xy0××

33、5;x=y或|x-y|=1×××x2> y2××(1) 因?yàn)閤|x成立，所以自反性成立；所以反自反性不成立；因?yàn)閤0時(shí)，x|0成立，但0|x不成立，所以對稱性不成立，因?yàn)?1|-1，和-1|1成立，所以反對稱性不成立；但x|y,y|z成立，就一定有x|z成立，所以傳遞性成立(2) 因?yàn)槟相等是整數(shù)集合上的等價(jià)關(guān)系，所以具有自反、對稱、傳遞性(3) 因?yàn)?0 = 0，所以自反性不成立；因?yàn)閤 0時(shí)必有 xx>0,所以反自反性不成立；因?yàn)閤y >0 必有yx>0,所以對稱性成立；因此反對稱性不成立；因?yàn)閤y>0,yz

34、>0,能得到x,y,z同號且不為0，所以，xz>0,所以傳遞性成立(4) 因?yàn)閤x0,所以自反性成立；因此，反自反性不成立；因?yàn)閤y0,所以yx0，因此對稱性成立；因此，反對稱性不成立；因?yàn)?1*0 0，0*10，但-1*1 < 0,所以傳遞性不成立(5) 因?yàn)?x=x，所以自反性成立；因此反自反性不成立；因?yàn)閨x-y|=1，所以| y-x |=1，因此對稱性成立；所以反對稱性不成立；因?yàn)閨1-2|=1，|2-3|=1，但|1-3|=2，所以傳遞性不成立因?yàn)?xx = xx，所以自反性不成立；反自反性成立；因?yàn)閤2> y2 成立，那么y2> x2就不成立，所以對稱

35、性不成立，反對稱性成立；傳遞性成立7、設(shè)R是集合A上的一個(gè)二元關(guān)系，合于xRy yRz => xRz,稱R是A上的一個(gè)反傳遞關(guān)系。試舉一個(gè)實(shí)際的反傳遞關(guān)系的例子解：例如在人群集合上，建立父子關(guān)系，那么就是一個(gè)反傳遞關(guān)系，因?yàn)槿绻?甲是乙的父親，乙是丙的父親，那么甲和丙就一定不存在父子關(guān)系；另外，在正整數(shù)域上建立的倍數(shù)關(guān)系，也是一個(gè)反傳遞關(guān)系，因?yàn)槿绻?a 是 b的2倍，b是c的2倍，那么a 一定不是c的2倍8、設(shè)R和S都是集合A上的二元關(guān)系，它們經(jīng)過關(guān)系運(yùn)算后得到A上的一個(gè)新關(guān)系。試判別當(dāng)R和S同時(shí)具有下表左列某種指定性質(zhì)時(shí)，經(jīng)過指定的運(yùn)算后所得到新關(guān)系也仍保持這種性質(zhì)，把所得結(jié)論以，&

36、#215;的形式填在下表中相應(yīng)的位置上RSRSR-SRS-RR-1自反性××反自反性××對稱性×反對稱性×××傳遞性××××（1） 自反性的保持情況說明：因?yàn)镽,S都具有自反性，所以IAÍR, IAÍS，因此IAÍRS, IAÍRS,所以自反性在RS，RS上保持因?yàn)镮AÍS，所以IA不是S補(bǔ)集的子集，因此也不是R-S的子集，所以自反性在R-S上不保持因?yàn)镽,S是自反的，所以對任意的a A，（a,a）R,S，所以（a,a）RS，

37、因此自反性在RS上保持因?yàn)椋╝,a）R，所以（a,a）不屬于-R,所以-R不具有自反性因?yàn)椋╝,a）R，所以（a,a）R-1，因此R-1具有自反性（2） 反自反性的保持情況說明：因?yàn)镽,S都具有反自反性，等價(jià)于 IAR = , IAS = 因?yàn)镮ARS =，IA（RS）=，所以RS，RS都是反自反的因?yàn)镮AR-S =，所以 R-S也是自反的對于RS，假設(shè)（a,b）R,（b,a）S, 那么（a,a）RS, 所以反自反在RS上不一定保持因?yàn)椋╝,a）不屬于R，所以（a,a）一定屬于-R，所以-R一定是自反的，一定不是反自反的因?yàn)椋╝,a）不屬于R，所以（a,a）也不屬于R-1，因此R-1一定是反自

38、反的（3） 對稱性的保持情況說明：因?yàn)镽,S是對稱的，所以R= R-1,S= S-1 ，-R = (-R)-1= -R-1, -S = (-S)-1= -S-1因?yàn)椋≧S）-1= R-1 S-1= RS, 所以RS具有對稱性因?yàn)椋≧S）-1= R-1 S-1= RS, 所以RS具有對稱性因?yàn)椋≧-S）-1= （R-S）-1=R-1 （-S）-1= R-1 -S-1 = R-S，所以R-S具有對稱性因?yàn)?RS)-1 = S-1 R-1 = SR ,但SR通常情況下與RS不相同，所以對稱性不一定保持，例如：R = (a,b),(b,a), S = (b,c),(c,b),則RS = （a,c）,并

39、不對稱因?yàn)椋?R）-1 = -R-1 = -R，所以R的補(bǔ)是對稱的因?yàn)?R逆的逆就是R，既等于R的逆，所以R的逆是對稱的（4） 反對稱性的保持情況說明：因?yàn)镽,S是反對稱的，所以R R-1Í IA S S-1Í IA因?yàn)椋≧S）（RS）-1 = （RR-1）（SS-1）Í IA ，所以RS具有反對稱性因?yàn)槿绻鸕 = (a,b) S = (b,a),都是反對稱的，但 RS = (a,b),(b,a)是對稱的，所以RS不一定再保持對稱性因?yàn)镽是反對稱的，而R-S在R的基礎(chǔ)上減少集合元素，因此也一定是反對稱的因?yàn)槿绻?R = (a,b),(c,a), S = (b,c)

40、,(a,a), 那么RS = （a,c），（c,a）,變?yōu)閷ΨQ的，所以反對稱性，在復(fù)合運(yùn)算下不一定保持因?yàn)槿绻鸕 = （a,b）,(c,c)是反對稱的，但-R = （a,a）,(b,b),(b,a),(a,c,),(c,a),(b,c),(c,b),不是反對稱的，所以反對稱性在補(bǔ)集運(yùn)算上不保持因?yàn)镽 R-1Í IA，有因?yàn)?R = (R-1)-1,所以R-1是反對稱的（5） 傳遞性的保持情況說明：因?yàn)镽,S是傳遞的，所以R2ÍR, S2ÍS因?yàn)椋≧S）2 = （RS）（RS）Í R2S2(RS)(SR) Í RS，所以傳遞性保持如果R = (a

41、,b), S=(b,c),都是傳遞關(guān)系，但RS = (a,b),(b,c)不再是傳遞關(guān)系，所以傳遞性在RS上不一定保持如果R=(a,b),(b,c),(a,c),S=(a,c),分別是兩個(gè)傳遞關(guān)系，但R-S = (a,b),(b,c)不再是傳遞關(guān)系，所以傳遞性在R-S上不一定保持如果R=(a,b),(c,d),S=(b,c),(d,e), 分別是兩個(gè)傳遞關(guān)系，但RS = (a,c),(c,e)不再是傳遞關(guān)系，所以傳遞性在RS上不一定保持如果A = a,b,c, R = (a,b), 那么 R = A ×A R,顯然不是傳遞的，所以傳遞性在-R上不一定保持因?yàn)镽2ÍR，所以

42、（R2）-1ÍR-1 ，即（R-1）2ÍR-1，所以傳遞性在逆運(yùn)算下保持10、設(shè)R是集合A上的一個(gè)二元關(guān)系，證明（1）R是自反的 Û IAÍR證明: R是自反的 => IAÍR因?yàn)?，R是自反的，所以對任意的A中元素a，有（a,a）R，即IA中任意元素都屬于R，所以IAÍRIAÍR => R是自反的因?yàn)?，對任意的A中元素a，有（a,a）IA，又IAÍR，所以（a,a）R，所以R是自反的綜上所述，R是自反的 Û IAÍR（2）R是反自反的 Û IAR = 證明：R是反自反的 =

43、> IAR = 因?yàn)?，IA中的任意元素(a,a)，都不屬于R，所以IAR = IAR = => R是反自反的因?yàn)镮AR = ，所以IA中的任意元素(a,a)，都不屬于R，即對任意的A中元素a，有（a,a）IA，都不屬于R，所以R是反自反的綜上所述，R是反自反的 Û IAR = （3）R是對稱的 Û R = R-1證明：R是對稱的 => R = R-1因?yàn)閷中的任意元素（a,b）,因?yàn)镽是對稱的，所以（b,a）R，那么（a,b）R-1,所以RÍ R-1因?yàn)閷-1中的任意元素（a,b）,那么（b,a）R，因?yàn)镽是對稱的，那么（a,b）R,所以R-

44、1Í R所以 R = R-1R = R-1 => R是對稱的對R中的任意元素（a,b），因?yàn)镽 = R-1 ,所以（a,b）也屬于R-1，所以（b,a）R，因此R是對稱的綜上所述，R是對稱的 Û R = R-1（4）R是反對稱的 Û RR-1ÍIA證明:R是反對稱的 => RR-1ÍIA因?yàn)閷θ我?a,b) RR-1 ,那么其就同時(shí)屬于R和R-1 ，那么（b,a）也屬于R，根據(jù)反對稱的定義，a = b，所以（a,b）IA ,所以RR-1ÍIARR-1ÍIA => R是反對稱的假設(shè)R不是反對稱的，那么必定存在

45、 a b(a,b) R (b,a) R，那么（a,b）RR-1 ,但（a,b）不屬于IA，矛盾；因此R必是反對稱的綜上所述，R是反對稱的 Û RR-1ÍIA（1） R是傳遞的 Û R2ÍR證明：R是傳遞的 => R2ÍR因?yàn)閷θ我猓╝,b）R2 ,必存在c，使得（a,c）,(c,b)屬于R，因?yàn)镽是傳遞的，所以(a,b)屬于R，因此R2ÍRR2ÍR => R是傳遞的因?yàn)閷θ我獾腞中的元素（a,b），(b,c)，那么(a,c)必定屬于R2,也就屬于R，所以R是傳遞的綜上所述，R是傳遞的 Û R2Í

46、;R11、設(shè)A=1,2,3,4,定義A上的關(guān)系 R = (a,b)|a=b+2,S = (x,y)|y=x+1x=2y 求：R。S,R。S-1。R,R2,(S-1)2解：根據(jù)題意，R=(3,1),(4,2)，S=(4,2),(1,2),(2，3)，（3，4）所以：R。S = （3，2），（4，3） S-1 = （2，4），（2，1），（3，2），（4，3）所以：R。S-1 = (4,4),(4,1) R。S-1。R = (4,2) R2 = Æ (S-1)2 = (2,3),(3,4),(3,1),(4,2)12、設(shè)A=a,b,c,d,e,f,g,h，A上的二元關(guān)系R對應(yīng)的關(guān)系圖4-

47、5所示，求使Rm=Rn的最小整數(shù)m和n(m < n)答：R = R16；簡要說明如下：本關(guān)系圖分為兩個(gè)部分，R = R1 R2,因?yàn)?R1。R2 = R2。R1 = Æ, 所以R2 = R12 R22 ,同理Rn = R1n R2n ,又因?yàn)?I1 = R13,I2=R25 ；3，5的最小公倍數(shù)為15，所以I = R15 ,所以R = I º R15 = R º R15 = R1613、設(shè)R是集合A上的二元關(guān)系，證明：（1）IAn = IA證明：因?yàn)閱挝魂P(guān)系的關(guān)系矩陣為單位矩陣，而復(fù)合運(yùn)算就是矩陣的乘法，根據(jù)單位矩陣的性質(zhì)，IAn = IA（2）IA

48、86; R=R ºIA =R證明：同上，因?yàn)閱挝痪仃囎蟪?、右乘一個(gè)矩陣，結(jié)果不變；所以IA º R=R ºIA =R（3）(RIA)n=IARR2R3Rn證明：根據(jù)書中并集關(guān)系復(fù)合的定理（4.2），展開，并利用上述1，2的結(jié)論，及可得證（嚴(yán)格可用歸納法）15、寫出第12題中關(guān)系圖對應(yīng)的關(guān)系矩陣，并利用warshall算法求這個(gè)關(guān)系的傳遞閉包解：習(xí)題五1、設(shè) A = (a,b)| a,b Î N，定義A上的一個(gè)二元關(guān)系 R = (a,b),(c,d) | ad = bc 證明：R 是 A 上的等價(jià)關(guān)系證明：（自反性）因?yàn)?對任意（a,b）Î A,

49、 都有：ab = ba, 既(（a,b）,(a,b) Î R，所以R是自反的（對稱性）如果（a,b）,(c,d)）Î R ,那么ad = bc, 所以 cb = ad,既（c,d）,(a,b)）ÎR, 所以R是對稱的（傳遞性）如果（a,b）,(c,d)）Î R, (c,d),(e,f) Î R, 那么 ad = bc ,cf = ed ,因此，adcf = bced (注：如果 0 N 中)， 那么af = eb, 所以（a,b）,(e,f)）Î R,R具有傳遞性綜上所證，R是A上的等價(jià)關(guān)系3、集合 A = 1，2，3，4的一個(gè)分化為

50、 S0=1,2,4,3,求由S0導(dǎo)出的A上的一個(gè)等價(jià)關(guān)系R解：等價(jià)關(guān)系R = 1，2，4×1，2，43×3 = （1，1），（2，2），（4，4），（1，2），（1，4），（2，1），（2，4），（4，1）,(4,2),(3,3)4、試確定在4個(gè)元素的集合上可以定義的等價(jià)關(guān)系數(shù)目解：在此集合上可以確定的4分劃個(gè)數(shù)為：1在此集合上可以確定的3分劃個(gè)數(shù)為：c(4,2) = 6在此集合上可以確定的2分劃個(gè)數(shù)為：c(4,1) + c(4,2) /2 = 7在此集合上可以確定的1分劃個(gè)數(shù)為：c(4,4) = 1所以共可定義15個(gè)等價(jià)關(guān)系6、設(shè)R是非空集合A上的一個(gè)二元關(guān)系，具有對稱性

51、和傳遞性。證明：如果對每一個(gè)xÎA，存在yÎA使xRy，那么，R是A上的等價(jià)關(guān)系證明：因?yàn)閷γ恳粋€(gè)xÎA，存在yÎA使xRy，由于R是對稱的，所以yRx；又因?yàn)镽是傳遞的，當(dāng)xRy 并且 yRx，那么xRx。所以R是自反的。綜上所述，R是自反的，對稱的和傳遞的，因此R是A上的等價(jià)關(guān)系8、設(shè)A是由54的正因子構(gòu)成的集合，“|”表示整除。畫出偏序集<A,|>對應(yīng)的Hasse圖解：先求出偏序集，然后求處相應(yīng)的cover，然后畫出Hasse圖A=1，2，3，6，9，18，27，54COVER(|)=(1,2), (1,3), (2,6), (3,6)

52、, (3,9),(6,18), (9,18), (9,27), (18,54), (27,54)最大元：54最小元：1有4個(gè)包含元素最多的全序子集:L1=54,27,9,3,1L1=54,18,9,3,1L1=54,18,6,3,1L1=54,18,6,2,1182639541279、設(shè)A=a,b,c,畫出偏序集合對應(yīng)的Hasse圖。試比較本題與上題Hasse圖的異同解：a,b,ca,ba,cb,cabcÆ兩圖的相同點(diǎn) ： 都有最大（小）元 不同點(diǎn)：最大線序一個(gè)為5，一個(gè)為411、設(shè)R是集合A上的一個(gè)等價(jià)關(guān)系?，F(xiàn)在在等價(jià)類之間定義一個(gè)新關(guān)系S使得R的任何等價(jià)類a和b滿足aSb óaRb，判別S是一個(gè)什么關(guān)系解:根據(jù)題目信息，猜測是等價(jià)關(guān)系，說明如下：（1） 因?yàn)閷θ我獾腶ÎA，aRa成立（R是A上的