《離散數(shù)學(xué)第1-7章 習(xí)題詳解》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第1-7章 習(xí)題詳解（15頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 第一章 命題邏輯基本概念 課后練習(xí)題答案 1、是命題的為（1）、（2）、（3）、（6）、（7）、（10）、（11）、（12）、（13） 是簡單命題的為（1）、（2）、（7）、（10）、（13） 是真命題的為（1）、（2）、（3）、（10）、（11） 真值現(xiàn)在不知道的為（13） 2、3略 4.將下列命題符號(hào)化，并指出真值： 　?。?）p∧q,其中，p:2是素?cái)?shù)，q:5是素?cái)?shù),真值為1； 　　（2）p∧q,其中，p:是無理數(shù)，q:自然對(duì)數(shù)的底e是無理數(shù),真值為1； 　　（3）p∧┐q,其中，p:2是最小的素?cái)?shù)，q:2是最小的自然數(shù),真值為1； 　?。?）p

2、∧q,其中，p:3是素?cái)?shù)，q:3是偶數(shù),真值為0； 　?。?）┐p∧┐q,其中，p:4是素?cái)?shù)，q:4是偶數(shù),真值為0. 5.將下列命題符號(hào)化，并指出真值： 　?。?）p∨q,其中，p:2是偶數(shù)，q:3是偶數(shù),真值為1； 　　（2）p∨q,其中，p:2是偶數(shù)，q:4是偶數(shù),真值為1； 　?。?）p∨┐q,其中，p:3是偶數(shù)，q:4是偶數(shù),真值為0； 　　（4）p∨q,其中，p:3是偶數(shù)，q:4是偶數(shù),真值為1； 　　（5）┐p∨┐q,其中，p:3是偶數(shù)，q:4是偶數(shù),真值為0； 6.（1）(┐p∧q)∨(p∧┐q),其中，小麗從筐里拿一個(gè)蘋果，q：小麗從筐里拿一個(gè)梨；

3、　?。?）(p∧┐q)∨(┐p∧q),其中，p：劉曉月選學(xué)英語，q：劉曉月選學(xué)日語；. 7.因?yàn)閜與q不能同時(shí)為真. 8. 設(shè)p:2<1，q:3<2 (1) p→q，真值為1 (2) p→┐q，真值為1 (3) ┐q→p，真值為0 (4) ┐q→p，真值為0 (5) ┐q→p，真值為0 (6) p→q，真值為1 9.（2）、（6）真值為0，其余為1 10. （1）、（4）真值為0，其余為1 11、12略 13.設(shè)p:今天是星期一，q:明天是星期二，r:明天是星期三： 　　（1）p→q，真值為1（不會(huì)出現(xiàn)前件為真，后件為假的情況）； 　?。?）q→p，真值為1

4、（也不會(huì)出現(xiàn)前件為真，后件為假的情況）； 　?。?）pq，真值為1； 　?。?）p→r，若p為真，則p→r真值為0，否則，p→r真值為1. 14略 15、p、q為真命題，r為假命題，（4）的真值為1，其余為0 16、（4）的真值為1，其余為0 17、真 18、小王會(huì)唱歌，小李不會(huì)跳舞 19、（1）（4）（6）為重言式，（3）為矛盾式，其余為非重言式的可滿足式 20、（1）01,10,11 （2）00,10,11 （3）00,01,10 （4）01,10,11 21、（1）011；（2）010,110,101,100；（3）100,101 22、無成真賦值 23、無

5、成假賦值 24、均為重言式 25、均為矛盾式 26、前者為矛盾式，后者為重言式 27略；28不能；29略；30不能 返回 第二章 命題邏輯等值演算 本章自測答案 3、（1）矛盾式；（2）重言式；（3）可滿足式 5.(1)：∨∨,成真賦值為00、10、11； 　(2)：0，矛盾式，無成真賦值； 　(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部為成真賦值； 7.(1)：∨∨∨∨?∧∧； 　(2)：∨∨∨?∧∧∧； 8.(1)：1?∨∨∨,重言式； 　(2)：∨?∨∨∨∨∨∨； 　(3)：∧∧∧∧∧∧∧?

6、0，矛盾式. 11.(1)：∨∨?∧∧∧∧； 　(2)：∨∨∨∨∨∨∨?1； 　(3)：0?∧∧∧. 12.A?∧∧∧∧?∨∨. 第三章 命題邏輯的推理理論 本章自測答案 ? 6.在解本題時(shí)，應(yīng)首先將簡單陳述語句符號(hào)化，然后寫出推理的形式結(jié)構(gòu)*，其次就是判斷*是否為重言式，若*是重言式，推理就正確，否則推理就不正確，這里不考慮簡單語句之間的內(nèi)在聯(lián)系 　　(1)、(3)、(6)推理正確，其余的均不正確，下面以(1)、(2)為例，證明(1)推理正確，(2)推理不正確 　　(1)設(shè)p:今天是星期一，q:明天是星期三，推理的形式結(jié)構(gòu)為 　　　　(p→q)∧p→q(

7、記作*1) 　　在本推理中，從p與q的內(nèi)在聯(lián)系可以知道，p與q的內(nèi)在聯(lián)系可以知道，p與q不可能同時(shí)為真，但在證明時(shí)，不考慮這一點(diǎn)，而只考慮*1是否為重言式. 　　可以用多種方法（如真值法、等值演算法、主析取式）證明*1為重言式，特別是，不難看出，當(dāng)取A為p,B為q時(shí)，*1為假言推理定律，即 　　　　(p→q)∧p→q ? q 　　(2)設(shè)p:今天是星期一，q:明天是星期三，推理的形式結(jié)構(gòu)為 　　　　(p→q)∧p→q(記作*2) 　　可以用多種方法證明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等 　　　　(p→q)∧q→p 　　?(┐p∨q) ∧q →

8、p 　　?q →p 　　?┐p∨┐q 　　??∨∨ 　　從而可知，*2不是重言式，故推理不正確，注意，雖然這里的p與q同時(shí)為真或同時(shí)為假，但不考慮內(nèi)在聯(lián)系時(shí)，*2不是重言式，就認(rèn)為推理不正確. 9.設(shè)p:a是奇數(shù)，q:a能被2整除，r:a：是偶數(shù) 　　推理的形式結(jié)構(gòu)為 　　　　(p→q┐)∧(r→q)→(r→┐p) (記為*) 　　可以用多種方法證明*為重言式，下面用等值演算法證明： 　　　　(p→┐q)∧(r→q)→(r→┐p) 　　?(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) 　　(使用了交換律) 　　?(p∨q)∨(┐p∧r)∨┐q∨┐r 　　?(┐p∨

9、q)∨(┐q∧┐r) 　　?┐p∨(q∨┐q)∧┐r 　　?1 10.設(shè)p:a,b兩數(shù)之積為負(fù)數(shù)，q:a,b兩數(shù)種恰有一個(gè)負(fù)數(shù)，r：a，b都是負(fù)數(shù). 　　推理的形式結(jié)構(gòu)為 　　　　(p→q)∧┐p→(┐q∧┐r) 　　?(┐p∨q) ∧┐p→(┐q∧┐r) 　　?┐p→(┐q∧┐r) 　　(使用了吸收律) 　　?p∨(┐q∧┐r) 　　?∨∨∨ 　　由于主析取范式中只含有5個(gè)W極小項(xiàng)，故推理不正確. 11.略 14.證明的命題序列可不惟一，下面對(duì)每一小題各給出一個(gè)證明 　　① p→(q→r)　　　　　前提引入 　?、?P　　　　　　　　　前提引入 　　

10、③ q→r　　　　　　　 ①②假言推理 　?、?q　　　　　　　　　前提引入 　?、?r　　　　　 　　　 ③④假言推理 　?、?r∨s　　　　　　　 前提引入 　（2）證明： 　?、?┐(p∧r)　　　　　 前提引入 　?、?┐q∨┐r　　　　　 ①置換 　　③ r　　　　　　　　　前提引入 　?、?┐q 　　　　　　　 ②③析取三段論 　?、?p→q　　　　　　　 前提引入 　?、?┐p　　　　　　　?、堍菥苋∈? 　（3）證明： 　?、?p→q　　　　　　　 前提引入 　?、?┐q∨q　　　　　　 ①置換 　　③ (┐p∨q)∧(┐p∨p) ②置換 　?、?┐

11、p∨(q∧p　　　　 ③置換 　?、?p→(p∨q) 　　　　 ④置換 15.(1)證明： 　　① S　　　　　　　　結(jié)論否定引入 　?、?S→P　　　　　　 前提引入 　?、?P　　　　　　　　①②假言推理 　?、?P→(q→r)　　　　前提引入 　　⑤ q→r　　　　　　 ③④假言推論 　?、?q　　　　　　　　前提引入 　　⑦ r　　　　　　　?、茛藜傺酝评? 　（2）證明： 　?、?p　　　　　　　　附加前提引入 　　② p∨q　　　　　　 ①附加 　?、?(p∨q)→(r∧s)　前提引入 　　④ r∧s　　　　　　 ②③假言推理 　?、?s　　　　　　

12、　?、芑? 　?、?s∨t　　　　　　 ⑤附加 　　⑦ (s∨t)→u　　　　前提引入 　?、?u　　　　　　　?、蔻呔苋∈? 16.(1)證明： 　?、?p　　　　　　　　結(jié)論否定引入 　　② p→ ┐q　　　　　前提引入 　?、?┐q ①②　　　　 假言推理 　?、?┐r∨q　　　　　 前提引入 　?、?┐r　　　　　　?、邰芪鋈∪握? 　　⑥ r∧┐s　　　　　 前提引入 　?、?r　　　　　　　　⑥化簡 　?、?┐r∧r　　　　　 ⑤⑦合取 　（2）證明： 　?、?┐(r∨s)　　　　 結(jié)論否定引入 　?、?┐r∨┐s　　　　 ①置換 　?、?┐r　　

13、　　　　?、诨? 　?、?┐s　　　　　　?、诨? 　?、?p→r　　　　　　 前提引入 　?、?┐p　　　　　　　③⑤拒取式 　?、?q→s　　　　　　 前提引入 　?、?┐q　　　　　　　④⑦拒取式 　?、?┐p∧┐q　　　　 ⑥⑧合取 　?、?┐(p∨q)　　　　 ⑨置換 　　口 p∨q　　　　　　 前提引入 　?、息倏?┐(p∨q) ∧(p∨q) ⑩口合取 17．設(shè)p：A到過受害者房間，q: A在11點(diǎn)以前離開，r：A犯謀殺罪，s：看門人看見過A。 　　前提：(p∧┐q) →r , p ,q →s , ┐s 　　結(jié)論：r 　　證明： 　　　?、?q→s 前提

14、引入 　　　?、?┐s 前提引入 　　　　③ ┐q ①②拒取式 　　　?、?p 前提引入 　　　　⑤ p∧┐q ③④合取 　　　?、蓿╬∧┐q）→r 前提引入 　　　　⑦ r ⑤⑥假言推理 18．（1）設(shè) p：今天是星期六，q：我們要到頤和園玩，s：頤和園游人太多。 　　前提：p→(p∨r) , s→┐q , p , s 　　結(jié)論：r 　　證明： 　　　?、?s→┐q　　　 前提引入 　　　?、?s　　　　　　前提引入 　　　?、?┐q　　　　　①②假言推理 　　　?、?p　　　　　　前提引入 　　　?、?p→(q∨r)　　前提引入 　　　　⑥ q∨r　　　

15、　 ④⑤假言推理 　　　　⑦r　　　　　　 ③⑥析取三段論 （2）設(shè)p:小王是理科學(xué)生，q：小王數(shù)學(xué)成績好，r：小王是文科學(xué)生。 　　前提：p→q ,┐r→p ,┐q 　　結(jié)論：r 　　證明： 　　　?、?p→q　　　　 前提引入 　　　?、?┐q　　　　　前提引入 　　　?、?┐p　　　　　①②拒取式 　　　?、?┐r→p　　　 前提引入 　　　?、?r　　　　　?、邰芫苋∈? 返回 第四章 (一階)謂詞邏輯基本概念 本章自測答案 4.(1)┐x(F(x)∧ ┐G(x))?x( F (x) →G (x) ),其中,F(x)：x是有理數(shù),G(x) ：x能表示成分?jǐn)?shù)

16、； 　(2)┐x( F (x) →G (x) ) ?x(F(x)∧ ┐G(x)),其中,F (x)：x在北京賣菜,G (x) ：x是外地人； 　(3)x( F (x) →G (x) ),其中,F (x)：x是烏鴉,G (x) ：x是黑色的； 　(4)xF(x)∧ G(x)),其中,F (x)：x是人,G (x) ：x天天鍛煉身體。 因?yàn)楸绢}中沒有指明個(gè)體域,因而使用全總個(gè)體域。 5.(1)xy (F(x) ∧ G( y ) → H(x,y)),其中,F(x)：x是火車,G(y) ：y是輪船,H(x,y)：x比y快； 　(2)xy (F(x) ∧ G( y ) → H(x,y)),其

17、中,F(x)：x是火車,G(y) ：y是汽車, H(x,y)：x比y快； 　(3)┐x(F(x)∧y(G (y) → H (x,y)))?x(F(x) → y(G(y) ∧ ┐H(x,y))),其中,F(x)：x是汽車,G (y) ：y是火車,H(x,y)：x比y快； 　(4)┐x(F(x)→y(G(y) → H(x,y)))?xy(F(x)∧G(y)∧┐H(x,y))),其中,F(x)：x是汽車,G(y) ：y是火車,H(x,y)：x比y慢。 6.各命題符號(hào)化形式如下： 　(1)xy (x ．y = 0)； 　(2)xy (x ．y = 0)； 　(3)xy (y =x+1)

18、 　(4)xy(x ．y = y．x) 　(5)xy(x ．y =x+ y) 　(6)xy (x + y ＜0 ) 9.(1)對(duì)任意數(shù)的實(shí)數(shù)x和y,若x ＜y,則x ≠ y； 　(2)對(duì)任意數(shù)的實(shí)數(shù)x和y,若x–y = 0,則x＜y； 　(3)對(duì)任意數(shù)的實(shí)數(shù)x和y,若x＜y,則x–y≠0； 　(4)對(duì)任意數(shù)的實(shí)數(shù)x和y,若x–y ＜0,則x=y. 其中,(1)(3)真值為1(2)與(4)真值為0. 11.(1)、(4)為永真式,(2)、(6)為永假式,(3)、(5)為可滿足式。 這里僅對(duì)(3)、(4)、(5)給出證明。 　(3)取解釋I 為：個(gè)體域?yàn)樽匀粩?shù)集合N,F(x,y

19、)：x ≤ y,在下,xy F(x,y)為真,而xy F(x,y)也為真(只需取x =0即可),于是(3)中公式為真,取解釋 為：個(gè)體域仍為自然數(shù)集合N,而F(x,y)：x = y。此時(shí),xyF(x,y)為真(取y為x即可),可是xyF(x,y)為假,于是(3)中公式在 下為假,這說明(3)中公式為可滿足式。 　(4)設(shè)I為任意一個(gè)解釋,若在I下,蘊(yùn)涵式前件xy F(x,y)為假,則 xyF(x,y)→yxF(x,y)為真,若前件xyF(x,y)為真,必存在I的個(gè)體域D1中的個(gè)體常項(xiàng)x0,使yF(x0,y)為真,并且對(duì)于任意y∈,F(x0,y)為真,由于有x0∈,F(x0,y)為真,所以x

20、F(x,y)為真,又其中y是任意個(gè)體變項(xiàng),所以 yxF(x,y )為真,由于I的任意性,所以(4)中公式為永真式(其實(shí),次永真式可用第五章的構(gòu)造證明法證明之)。 　(5)取解釋為：個(gè)體域?yàn)樽匀粩?shù)集合,F(x,y)：x = y在下,(5)中公式為真,而將F(x,y)改為F(x,y)：x ＜ y,(5)中公式就為假了,所以它為可滿足式。 13．（1）取解釋為：個(gè)體域?yàn)樽匀粩?shù)集合N，F(xiàn)（x）：x為奇數(shù)，G（x）：x為偶數(shù)，在 下， x（F（x）∨G（x））為真命題。 　　取解釋為：個(gè)體域?yàn)檎麛?shù)集合Z，F(xiàn)（x）：x為正整數(shù)，G（x）：x為為負(fù)整數(shù)，在 下， x（F（x）∨G（x））為假命題。

21、 　　（2）與（3）可類似解答。 14．提示：對(duì)每個(gè)公式分別找個(gè)成真的解釋，一個(gè)成假的解釋。 返回 第五章 謂詞邏輯等值演算與推理 本章自測答案 2.(1) (F(a)∧ F(b)∧ F (c)) ∧ (G (a )∨G (b)∨G (c)) 　(2) (F(a)∧ F(b)∧ F (c)) ∨ (G (a)∧G (b)∧G (c)) 　(3) (F(a)∧ F(b)∧ F (c)) → (G (a)∧G (b)∧G (c)) 　(4) (F(a ,y) ∨ F(b,y)∨ F (c,y)) → (G (a)∨G (b)∨G (c)) 5.提示：先消去量詞，后求真值，注

22、意，本題3個(gè)小題消去量詞時(shí)，量詞的轄域均不能縮小，經(jīng)過演算真值分別為：1,0,1 . (1) 的演算如下： 　　　xyF(x,y) 　　?x (F(x,3)∨F(x,4)) 　　?(F(3,3)∨F(3,4))∧(F(4,3)∨F(4 ,4)) 　　?1∧1?1 6.乙說得對(duì)，甲錯(cuò)了。本題中，全稱量詞 的指導(dǎo)變?cè)獮閤 ，轄域?yàn)?F (x)→G(x,y)),其中F(x )與G(x,y)中的x都是約束變?cè)蚨荒軐⒘吭~的轄域縮小。 7.演算的第一步，應(yīng)用量詞轄域收縮與擴(kuò)張算值式時(shí)丟掉了否定聯(lián)結(jié)詞“ ┐”。演算的第二步，在原錯(cuò)的基礎(chǔ)上又用錯(cuò)了等值式，即 　　(F(x)∧(G(y)→

23、 H(x,y))) ≠(F(x) ∧G(y)→H (x,y)) 12.公式的前束范式不唯一，下面每題各給出一個(gè)答案。 　(1) xy (F(x)→ G(z,y)); 　(2) xt (x,y) → G(x,t,z)); 　(3) x4 ((F(,y) →G(,y))∧(G(,y) →F(x4,y))); 　(4) ((F()→G(,)) → (H () → L(,))); 　(5) (F(,)→(F() → ┐G (,))). 13.(1)xy(F(x) ∧G(y) ∧H(x ,y)),其中，F(xiàn)(x):x是汽車，G(y)：y是火車，H(x，y)：x比y跑的快； 　 (2

24、)xy(F(x) ∧G(y)→H(x ,y)),其中，F(xiàn)(x):x是火車，G(y)：y是汽車，H(x，y)：x比y跑的快； 　 (3)xy(F(x) ∧G(y) ∧┐H(x ,y)),其中，F(xiàn)(x):x是火車，G(y)：y是汽車，H(x，y)：x比y跑的快； 　 (4)xy(F(x) ∧G(y) → ┐H(x ,y)),其中，F(xiàn)(x):x是飛機(jī)，G(y)：y是汽車，H(x，y)：x比y慢； 14.(1)對(duì)F(x) → xG(x)不能使用EI規(guī)則，它不是前束范式，首先化成前束范式。 　　　　　F(x) → xG(x) <=> x(F(y)→G(x)) 　　因?yàn)榱吭~轄域(F(y)→G(x

25、))中，除x外還有自由出現(xiàn)的y，所以不能使用EI規(guī)則。 　 (2)對(duì) x F(x) → y G(y)也應(yīng)先化成前束范式才能消去量詞，其前束范式為 x y(F(x) →G(y)),要消去量詞，既要使用UI規(guī)則，又要使用EI規(guī)則。 　 (3)在自然推理系統(tǒng)F中EG規(guī)則為 　　　　　A(c)/∴x(x) 　　其中c為特定的個(gè)體常項(xiàng)，這里A(y) = F(y) →G(y)不滿足要求。 　 (4)這里，使F(a)為真的a不一定使G(a)為真，同樣地使G(b)為真的b不一定使F(b)為真，如，F(xiàn)(x):x為奇數(shù)，G(x):x為偶數(shù)，顯然F(3)∧G(4)為真，但不存在使F(x)∧G(x)為真的個(gè)

26、體。 　 (5)這里c為個(gè)體常項(xiàng)，不能對(duì)F(c)→G(c)引入全稱量詞。 15.(1)證明：①xF(x)　　　　　　　　　　　前提引入 　　②xF(x)→ y((F(y)∨G(y)) →R(y)) 　 前提引入 　?、踶((F(y)∨G(y)) →R(y) 　　　　　?、佗诩傺酝评? 　　④F(c) 　　　　　　　　　　　　　　　?、貳I 　　⑤(F(c)∨G(c))→R(c) 　　　　　　　　 ③UI 　?、轋(c)∨G(c)　　　　　　　　　　　　 ?、芨郊? 　　⑦R(c)　　　　　　　　　　　　　　　　 ⑤⑥假言推理 　?、鄕R(x)　　　　　　　　　　　　　　 ?、逧G

27、 (2)證明①xF(x)　　　　　　　　　　　　　 前提引入 　?、趚((F(x)→G(a)∧R(x)))　　　　 　　前提引入 　　③F(c)　　　　　　　　　　　　　　　　 ①EI 　?、蹻(c)→G(a)∧R(a)　　　　　　　　　 ?、赨I 　　⑤G(a)∧R(c)　　　　　　　　　　　　 ?、邰芗傺酝评? 　　⑥R(c)　　　　　　　　　　　　　　　　 ⑤化簡 　?、逨(c)∧R(c)　　　　　　　　　　　　　 ③⑥合取 　?、鄕(F(x)∧R(x))　　　　　　　　　　　⑦EG (3)證明：①┐xF(x)　　　　　　　　　　　 前提引入 　?、趚┐F(x)　　　　

28、　　　　　　　　　?、僦脫Q 　?、郓碏(c)　　　　　　　　　　　　　　　 ②UI 　?、躼(F(x)∨G(x))　　　　　　　　　　 前提引入 　?、軫(c)∨G(c)　　　　　　　　　　　　　 ④UI 　?、轋(c)　　　　　　　　　　　　　　　　 ③⑤析取三段論 　?、選F(x)　　　　　　　　　　　　　　?、轊G (4)證明①x(F(x)∨G(x))　　　　　　　　　前提引入 　　②F(y)∨G(y)　　　　　　　　　　　　　 ①UI 　?、踴(┐G(x)∨┐R(x))　　　　　　　　 前提引入 　?、堠碐(y)┐R(y)　　　　　　　　　　　　 ③UI 　?、輝

29、R(x)　　　　　　　　　　　　　　 前提引入 　?、轗(y)　　　　　　　　　　　　　　　　 ⑤UI 　　⑦┐G(y)　　　　　　　　　　　　　　　 ④⑥析取三段論 　?、郌（y）　　　　　　　　　　　　　　　 ②⑦析取三段論 　?、醲F(x)　　　　　　　　　　　　　　 ⑧UG 17．本題不能用附加前提證明法. 20.(1)與(2)均可用附加前提證明法。 22.(1)設(shè)F(x)：x為偶數(shù)，G(x):x能被2整除。 　　前提:x(F(x)→G(x))，F(xiàn)(6) 　　結(jié)論：G(6) (2)設(shè)F(x)：x是大學(xué)生，G(x):x是勤奮的，a：王曉山。 　　前提:x(F

30、(x)→G(x))，┐G(a) 　　結(jié)論：┐F(a) 23.(1)設(shè)F(x)：x是有理數(shù)，G(x):x是實(shí)數(shù)，H(x)：x是整數(shù)。 　　前提:x( F(x)→G(x))， x(F(x)∧H(x)) 　　結(jié)論:x(G(x)∧H(x)) 　　證明提示：先消存在量詞。 (2)設(shè)F(x)：x是有理數(shù)，G(x):x是無理數(shù)，H(x)：x是實(shí)數(shù)，I(x)：x是虛數(shù)。 　　前提:x((F(x)∨G(x)) →H(x))， x( I(x)→┐H(x)) 　　結(jié)論:x(I(x)→(┐F(x)∧┐G(x))) 　　證明①x(I(x)→(┐H(x))　　　　　　　　　　前提引入 　　　　②I(y

31、)→H(y)　　　　　　　　　　　　　　 ①UI 　　　　③x((F(x)∨G(x))→H(x))　　　　　　　 前提引入 　　　?、?F(y)∨G(y))→H(y)　　　　　　　　　?、踀I 　　　?、荸碒(y)→(┐F(y)∧┐G(y))　　　　　　　④置換 　　　?、轎(y)→(┐F(y)∧┐G(y))　　　　　　　　②⑤假言三段論 　　　?、選(I(x)→(┐F(x)∧┐G(x))　　　　　　⑧UG 24.設(shè)F(x)：x喜歡步行，G(x)：x喜歡騎自行車，H(x)：x喜歡乘汽車。 　　前提:x(┐F(x)→┐G(x))， x(G(x)∨H(x))， x┐H(x) 　　結(jié)

32、論:x┐F(x) 　　證明①x┐H(x)　　　　　　　　　　　　　　　 前提引入 　　　　②┐H(c)　　　　　　　　　　　　　　　　?、賃I 　　　?、踴(G(x)∨H(x))　　　　　　　　　　　　前提引入 　　　?、蹽(c)∨H(c)　　　　　　　　　　　　　　　③UI 　　　?、軬(c)　　　　　　　　　　　　　　　　　?、冖芪鋈∪握? 　　　　⑥x(F(x) →G(x))　　　　　　　　　　　 前提引入 　　　?、逨(c)→┐G(c)　　　　　　　　　　　　　?、轚I 　　　　⑧┐F(c)　　　　　　　　　　　　　　　　?、茛呔苋∈? 　　　　⑨x┐F(x)　　　　　

33、　　　　　　　　　　 ⑧UG 25.設(shè)F(x)：x是科學(xué)工作者，G(x)：x是刻苦鉆研的，H(x)：x是聰明的，I(x)：x在事業(yè)中獲得成功。 　　前提:x(F(x)→G(x))，x(G(x)∧H(x)→I(x))，a：王大海，F(xiàn)(a)，H(a) 　　結(jié)論：I(a) 　　證明①F(a)　　　　　　　　　　　　　　　　　　前提引入 　　　　②x(F(x)→G(x))　　　　　　　　　　　　 前提引入 　　　?、跢(a)→G(a)　　　　　　　　　　　　　　?、赨I 　　　　④G(a)　　　　　　　　　　　　　　　　　?、佗奂傺酝评? 　　　?、軭(a)　　　　　　　　　　　　　　　

34、　　　前提引入 　　　?、辺(G(x)∧H(x)→I(x))　　　　　　　　　前提引入 　　　?、逩(a)∧H(a)→I(a)　　　　　　　　　　　 ⑥UI 　　　　⑧G(a)∧H(a)　　　　　　　　　　　　　　　④⑤合取 　　　?、酙(a)　　　　　　　　　　　　　　　　　?、撷嗉傺酝评? 返回 第六章 集合代數(shù) 本章自測答案 4.(1) ③ (2) ④ (3) ⑤ (4) ⑦ (5) ⑧ 6.只有(2)為真，其余為假。 9.(1) {4}；(2) {1,3,5,6}；(3) {2,3,4,5,6}；(4) {, { 1 }}；(5) {{ 4 },{1,4}}. 11

35、.(1)； (2) {1,4,5}. 22.(2)、(3)、(4)、(8)、(10)為真，其余為假。 24.(1)為真，其余為假，因?yàn)? 　　　　(P-Q) = P ? (P-Q)∩Q = P∩Q ? = P∩Q 　　(2)(3)(4)的反例：P ={1} ，Q ={2} 26.(A–B)∪(B–A) = (A∩B)∪(B∩A) 　　=(A∪B)∩(B∪B)∩(A∪A)∩(B∪A) 　　=(A∪B)∩E∩(A∩B)=(A∪B)-(A∩B) 27.(1)(A-B)-C = A∩B∩C =A∩(B∪C) = A-(B∪C) 　 (2)(A-C)-(B-C)A∩C∩(B∩C

36、) 　　　 =A∩C∩(B∪C) = (A∩C∩B)∪(A∩C∩C) 　　　 =A∩∩C=(A–B)- C 　 (3)(A–B-C=A∩B∩C =A∩C∩B=(A–C)–B 28.(1)A∩(B∪A) = (A∩B)∪(A∩A) =(A∩B)∪ 　　　 =A∩B=B∩A 　 (2)((A∪B)∩A) = (A∪B)∪A 　　　 =(A∩B)∪A = A 29.由第26題有(A-B)∪(B-A)=(A∪B)–(A∩B)，故(A-B)∪(B-A)A∪B。假若x∈A∩B，那么x∈A∪B，因此x(A∪B)-(A∩B),與(A-B)∪(B-A) = (A∪B)-(A∩B) = A∪B矛盾

37、. 30.AB?x(x∈A→x∈B)?x(xB→xA) 　　　 ?x(x∈B→x∈A)?BA 　　　 AB ? A∪AA∪B ? EA∪B 　　而A∪BE，因此AB ? A∪B=E反之， 　　　 A∪B = E ? A∩(A∪B)= A ? A∩B = A ? AB 　　綜合上述，AB?A∪B = E 　　　 AB ? A-B = ? A-BB 　　反之A-BB ? (A-B)∪BB ? A∪BB ? A∪B = B ? AB 　　綜合上述AB?A-BB 31.任取x ,x∈A ? {x} A=>{x}∈P(A)=>{x}∈P(B)=>{x}B ? x∈B 32.先證C

38、A∧CB ? CA∩B,任取x,x∈C ? x∈C∧x∈C ? x∈A∧x∈B ? x∈A∪B,從而得到CA∪B.再證CA∩B ? CA∧CB，這可以由CA∩BA,CA∩BB得到。 33.PQ ? P-Q= ? P-QP，反之，P-QP ? P∩(P-Q)P∩P ? P-Q= ? PQ 34.令X=，則有∪Y =，即Y = . 35.AB ? A∪AB∪A ? EB∪A因?yàn)镋為全集,B∪AE綜合上述B∪A=E. 36.由A∩CB∩C,A-CB-C，利用A∪CB∪D有： 　 (A∩C)∪(A-C) (B∩C)∪(B-C) 　 ? (A∩C)∪(A∩C)(B∩C)∪(B∩C) 　 ?

39、 (A∩(C∪C)(B∩(C∪C) ? A∩EB∩E ? AB 37.恒等變形法 　　B=B∩(B∪A)=B∩(AB)=B∩(AC) 　　 =(B∩A)∪(B∩C)=(A∩C)∪(B∩C) 　　 =(A∪B)∩C=(A∪C)∩C=C 39.任取x，有x∈P(A) ? x A ? x B ? x∈P(B)，因此P(A)P(B). 40.(1)任取x有 　　x∈P(A)∩P(B)?x∈P(A)∧x∈P(B)?xA∧xB 　　　　　　　　　?xA∩B?x∈P(A∩B) (2)任取x有 　　x∈P(A)∪P(B)?x∈P(A)∨x∈P(B)?xA∧xB 　　　　　　　　　 ? x

40、A∪B?x∈P(A∪B) 　　注意與(1)的推理不同，上面的推理中有一步是“ ? ”符號(hào)，而不是“?”符號(hào)。 (3)反例如下：A = {1}，B = {2}，則 　　P(A)∪P(B)= {,{1},{2}} 　　P(A∪B)={,{1},{2},{1,2}} 返回 第七章 二元關(guān)系 本章自測答案 3.(1) 任取< x,y >,有 　　∈(A ∩ B)×(C ∩ D) <=>x∈A ∩ B ∧ y ∈C ∩ D 　?x ∈A∧x ∈ B∧y ∈C∧y ∈ D 　?(x ∈A∧y ∈C )∧(x∈B∧y∈D) 　?∈A×C∧< x,y >∈B

41、×D 　?∈(A×C)∩(B×D) 　(2)都為假,反例如下: 　　A ={1}, B ={1,2}, C ={2}, D ={3} 4.(1)為假,反例如下:A ={1}, B =,C = {2}; 　(2)為真,證明如下:任取有 　　∈A×(B∩C)×(C∩D)?x∈A∩B∧y∈B∧y∈C 　?(x∈A∧y∈B)∧(x∈A∧y∈C) 　?∈A×B∧∈A×C?∈(A×B)∩(A×C) 　(3)為真,令A(yù) = 即可; 　(4)為假,反例如下: A = 7.={<2,2>,<3,3 >,<4,4>} 　={

42、<2 . 3>,<2,4>,<3,2>,<3,4>,<4,2>,<4,3>} ∪ 　LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} 　DA={<2,2>,<2,4>,<3,3>,<4,4>} 9.(1){<1,2>,<1,4>,<1,6>,<2,1>,<2,2>,<2,4> <2,6>,<4,1>,<4,2>,<4,4>, <4,6> <6,1>, <6,2>,<6,4> <6,6>} 　(2){<1,2>,<2,1>}; 　(3){<1,1>,<2,1>,<4,1>,<6,1>,<2,2>,<4,2>,<4,4>,<6,6>} 　(4){<1,

43、2>,<2,2>,<4,2>,<6,2>} 12.（略） 13.A∩B = {<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}, A ∩ B ={<2,4>} 　　domA = {1,2,3},domB = {1,2,4},dom(A ∪ B) = {1,2,3,4} 　　ranA = {2,3,4},ranB = {2,3,4},ran(A ∪ B) = {4},fld(A - B) = {1,2,3} 14.RR = {<0,2>,<0,3>,<1,3>} 　 R= {<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} 　 R{0,1}

44、= {<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} 　 R[{1,2}] = {2,3} 18.(1)F(G∪H) = FG∪FH 　　任取 ,有 　　　　∈F (G∪H)?t(∈F∧∈G∪H) 　　?t(∈F∧(∈G∨∈H)) 　　?t((∈F∧∈G)∨(∈F∧∈H)) 　　?t(∈F∧∈G)∨t(∈F∧∈H)) 　　?∈FG∨∈FH?∈FG∪FH 　 (2)和(4)類似可證 1

45、9.(2)任取y,有 　　y∈R[T∪W]?x(x∈T∪W∧∈R) 　　　?x((x∈T∨x∈W)∧∈R 　　　?x((x∈A∧∈R)∨(x∈W∧∈R)) 　　　?x(x∈T∧∈R)∨x(x∈W∧∈R) 　　　?y∈R[T]∨y∈R[W]?y∈R[T]∩R[W] (3)任取,有 　　∈F(A∩B)?x∈A∩B∈F 　　　?x∈A∧x∈B∧∈F 　　　?(x∈A∧∈F)(x∈B∧∈F) 　　　?∈FA∧∈FB 　　　?∈FA∩F B

46、20.(1)任取,有 　　∈(∪) <=>∈∪ 　　　?∈∨∈ 　　　?∈∨∈ 　　　?∈∪ 　 (2)和(1)類似可證. 21.只有對(duì)稱性,因?yàn)?+1≠10,<1,1>R,R不是自反的,又由于<5,5>∈R,因此R不是反自反的,根據(jù)xRy?x+y = 10=>yRx ,可知R是對(duì)稱的,又由于<1,9>,<9,1>都是屬于R,因此R不是反對(duì)稱的, <1,9>,<9,1>都屬于R,如果R是傳遞的,必有<1,1>屬于R.但這是不成立的,因此R也不是傳遞的. 22.(1)關(guān)系圖如圖7.15所示; (P

47、148) 　 (2)具有反自反性、反對(duì)稱性、傳遞性. 26.(1)R={<3,3>,<3,1>,<3,5>}, = {<3,3>,<3,1>,<3,5>} 　 (2)r(R)={<1,1>,<1,5>,<2,2>,<2,5>,<3,3>,<3,1>,<4,4>,<4,5>,<5,5>,<6,6>} 　　　s(R)={<1,5>,<5,1>,<2,5>,<5,2>,<3,3>,<3,1>,<1,3>,<4,5>,<5,4>} 　　　T(R)={<1,5>,<2,5>,<3,3>,<3,1>,<3,5>,<4,5>} 31.(1)R = {<2,3>,<3,2>,<2,4>,<4,2>

48、,<3,4>,<4,3>}∪；(2)R； (3)R. 32.(1)不是等價(jià)關(guān)系，因?yàn)?1,1> R，R不是自反的； 　 (2)不是等價(jià)關(guān)系，因?yàn)镽不是傳遞的，1R3，3R2但是沒有1R2； 　 (3)不是等價(jià)關(guān)系，因?yàn)?2,2> R，R不是自反的； 　 (4)不是等價(jià)關(guān)系，因?yàn)镽不是傳遞的。 　 (5)是等價(jià)關(guān)系。 33．關(guān)系圖如圖7.17說示 (P151) 　 [a] = [b] ={a,b},[c] = [d] = {c,d} 　　 38.現(xiàn)取x，有x∈A ? ∈R ? ∈R∧∈R 　　 ? ∈R∧∈ ? ∈

49、R∩R 　 任取,有∈ R∩ ? ∈R∧∈ 　　 ? ∈ ∧∈R ? ∈R∩R 　 任取,,有 　　　 ∈R∩ ∧∈R∩ 　　 ? ∈R∧∈ ∧∈R∧∈ 　　 ? (∈R∧∈R)∧(∈ ∧∈ 　　 ? ∈R∧∈R ? ∈R∩R 42.x,x∈A ? ∈R ? ∈R∧∈R ? ∈T,T是自反的。 　　　 x,

50、y∈A,∈T?∈R∧∈R 　 ?∈R∧∈R ? ∈T,T是對(duì)稱的。 　　　 x,y,z∈A,∈T∧∈T 　 ?∈R∧∈R∧∈R∧∈R 　 ? ∈R∧∈R∧∈R∧∈R 　 ? ∈R∧∈R ? ∈T 　 T是傳遞的。 43．哈斯圖如下圖所示. 　　 44.(a)偏序集,A={1,2,3,4,5},R={<1,3>,<1,5>,<2,4>,<2,5>,<3,5>,<4,5>}∪

51、　 (b)偏序集,A={a,b,c,d,e,f},R={,,}∪ 　 (c)偏序集,A={1,2,3,4,5}, R={<1,2>,<1,4>,<1,5>,<1,3>,<2,4>,<2,5>,<3,4>,<3,5>,<4,5>}∪ 45.(a)A={a,b,c,d,e,f,g}, ={,,,,,,, ,,}∪ 　 (b)A = {a,b,c,d,e,f,g},R口 = {,,,,,

52、f>,}∪ 46.哈斯圖如圖7.19所示 （P153） ?。?）極大元e,f；極小元a,f；沒有最大與最小元。 　（2）極大元a,b,d,e；極小元a,b,c,e；沒有最大與最小元。 返回 5、設(shè)無向圖G有10條邊，3度與4度頂點(diǎn)各2個(gè)，其余頂點(diǎn)的度數(shù)均小于3，問G至少有多少個(gè)頂點(diǎn)？在最少頂點(diǎn)的情況下，寫出度數(shù)列、。 　　解：由握手定理圖G的度數(shù)之和為： 　　　　3度與4度頂點(diǎn)各2個(gè)，這4個(gè)頂點(diǎn)的度數(shù)之和為14度。 　　　　其余頂點(diǎn)的度數(shù)共有6度。 　　　　其余頂點(diǎn)的度數(shù)均小于3，欲使G的頂點(diǎn)最少，其余頂點(diǎn)的度數(shù)應(yīng)都取2, 　　所以，G至少有7個(gè)頂點(diǎn), 出度

53、數(shù)列為3,3,4,4,2,2,2,. 7、設(shè)有向圖D的度數(shù)列為2，3，2，3，出度列為1，2，1，1，求D的入度列，并求， ,. 解：D的度數(shù)列為2，3，2，3，出度列為1，2，1，1，D的入度列為1,1,1,2. ,, 14、下面給出的兩個(gè)正整數(shù)數(shù)列中哪個(gè)是可圖化的？對(duì)可圖化的數(shù)列，試給出3種非同構(gòu)的無向圖，其中至少有兩個(gè)時(shí)簡單圖。 (1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇數(shù)，不可圖化； (2) 2＋2+2+2+3+3+4+4=16, 是偶數(shù)，可圖化；