離散數(shù)學(xué)(第2版,劉愛民)習(xí)題解答(1)(1)

1、附錄2 習(xí)題答案習(xí)題一答案1.1下列各語句中哪些是命題?1) 不是； 2) 是； 3) 不是； 4) 不是；5) 不是； 6) 是；7) 是； 8) 不是 9) 不是；10)是； 11)不是；12)是。1.2 將下列命題符號(hào)化。 1) p Ø q, p:太陽明亮,q:濕度高； 2) q® Ø p, p:明天你看到我，q:我要去深圳。 3) p®q, p:我出校，q:我去圖書城； 4) q®p , p:你去,q:我去； 5) 5.1) pq；5.2) pØq; 5.3) pq；5.4) pØq；6) 6.1) pq 6.2)

2、Ø(p « q) 6.3) p¬q 6.4) ¬ (pr)6.5) (pq) ®r6.6) ¬ (r ® (pq) 7) p:藍(lán)色和黃色可以調(diào)配成綠色； 8) Ø(p«q), p:李蘭現(xiàn)在在宿舍, q:李蘭在圖書館里； 9) ¬p®¬ q, p:一個(gè)人經(jīng)一事，q:一個(gè)人長(zhǎng)一智；10) (p¬q) ® Ø(r« s), p:晚上小王做完了做業(yè), q: 晚上小王沒有其他事情，r: 晚上小王看電視, s: 晚上小王看電影。11) Ø

3、(r« s), r:小飛在睡覺, s:小飛在游泳；12) ¬p¬qr, p:這個(gè)星期天我看電視，q: 這個(gè)星期天我外出，r:這個(gè)星期天我在睡覺。13) p®q , p:衛(wèi)星上天了，q:國(guó)家強(qiáng)大了；14) p®q, p:今天沒有課，q:我呆在圖書館里；15) p®q,p:我去圖書城，q:我有時(shí)間；16) ¬p®¬q , p:人們辛勞，p: 人們收獲1.3 1) 小李家住北大西門外, 他現(xiàn)在坐在公共汽車?yán)锟磿瑳]有考慮問題； 2) 小李在思考問題, 他沒有乘坐公共汽車，也沒有看書； 3) 小李只要乘坐公共汽車

4、，他就看書或考慮問題； 4) 小李乘坐公共汽車，要么看書不考慮問題，要么考慮問題不看書， 5) 同4); 6) 如果小李家住北大西門外,則他現(xiàn)在沒有乘坐公共汽車，沒有看書，也沒有考慮問題。1.4 1) 是2) 不是，因?yàn)槁?lián)結(jié)詞后沒有字母3) 是4) 是5) 不是，因?yàn)閜q之間缺聯(lián)結(jié)詞6) 不是，因?yàn)?不能構(gòu)成公式7) 是*1.5 1) q是0層公式，Øq是1層公式，(p Øq)是2層公式，原公式是3層公式; 2) p是0層公式，Øp是1層公式，(Øp®q) 是2層公式，(q®r) 是1層公式，(Øp®q) (q&#

5、174;r)是3層公式，(p®r)是1層公式，原公式是4層公式；3) r，s是0層公式，r s是1層公式，(q ® r s)是2層公式， (p (q ® r s)是3層公式，Ø(p (q ® r s)是4層公式，(p®q) s是2層公式，原公式是5層公式。4) p，q是0層公式，(p q)是1層公式，(p q)®r是2層公式，(r®s) 是1層公式，原公式是3層公式.1.6 p ð q ® r s，q ð p ® q1) (q ® r s) Ø( p

6、74;q)®r ;2) (Ø(q ® r s)®( p®q) (p®q)®r)®( (q ® r s)®r)；3) Ø(q ® r s) ( p®q) ® r s) ® (q ® r s)® ( p®q) s； 4) (q ® r s) ( p®q)®r « (r®s).1.7 AB, A的成真賦值或B的成真賦值，故為000,011,100,110,111, 101;

7、 ØAB, A®B: ØA的成真賦值或B的成真賦值，001,010,101, 000,110; AB: 同時(shí)是A和B的成真賦值，000,110；ØAØB: 同時(shí)是ØA和ØB的成真賦值，001, 010；A«B: 同時(shí)是A和B的成真賦值或成假賦值，000,110, 001, 010；1.8 1) ( p q ) ® q 2) (p ® q) « ppqp q( p q ) ® qpqp ® q(p ® q) « p00010010010101101

8、001100011111111這是重言式。這是可滿足式。 3) (p®Øp) ® Øp 4) p ® (p q)pqØpp®Øp(p®Øp) ® Øppqp qp ® (p q)001110001011110111100011011110011111這是重言式。這是重言式。 5) Ø(p®q) q 6) (Øq®Øp) « (p ® q)pqØ(p®q) qpq(Øq

9、®Øp)«(p ® q)000100011111010100101111101001010010110101101011這是矛盾式這是重言式。 7) (p®r) ® (p®r) ®(pq)®r) 8) Ø(p®q) p rpqr(p®r)®(p®r)®(pq)®r)pqrØ(p®q)pr000111101000010000111110100101000101010100100100011111111011010010

10、00101101001010101111111101101111001011011001001111111111110100 這是可滿足式 這是可滿足式1.9 這里僅僅是無數(shù)個(gè)命題形式中的兩個(gè)，讀者可以另外給出F：矛盾式，用一個(gè)矛盾式與任何一個(gè)公式合取即可，即(pØp) AF1=(pØp) (qr), F2=p Ø qØr (qr)G：重言式，簡(jiǎn)單的可以是一個(gè)重言式與任何一個(gè)公式析取，(pØp) A如：G1=(pØp) (qr), G2= p (pq) Øp r，重言式拆分在不同的位置H：前四行可看成蘊(yùn)涵式的否定，后四行與p

11、相同，兩種情況相或。所以H1= p (Ø(q® r) ; p (Ør q)還是分成前后四行分析，如果以p作為蘊(yùn)涵式的后件：A®p，后四行總成立，想法構(gòu)成前件，使得前四行的第三行為0，其它行為1，正是蘊(yùn)涵式q® r。所以可寫成H2=q ® r ® pR：只有全0的才為0，所以最簡(jiǎn)單的是用析取式，R1=pqr這個(gè)公式再與其它的確保p,q,r三個(gè)為0時(shí)一定為0的公式相析取即可；R2= pqr (p q)， pqr (pr)S：類似H的分析，前四行和后四行情況相或，S1=p (qr)如果以p作為蘊(yùn)涵式的后件：A®p，后四行

12、總成立，想法構(gòu)成前件，使得前四行的第三行為0，其它行為1，正是蘊(yùn)涵式q®Ø r。所以可寫成S2=q ® Ør ® p習(xí)題二答案2.1 1) 不能。CÛ1時(shí)，兩邊總是等值； 2) 不能。CÛ0時(shí)，兩邊總是等值； 3) 能。由否定之否定可得。2.2 1) 證明下列等值式：(1) p®(q®r) Û Øp(Øqr) (2) Ø(p « q) ÛØ(p®q)(q®p)Û ØpØqrÛ

13、Ø (Øpq)(Øqp)Û Ø qØprÛ (pØq) (qØp) Û Øq(Øpr) Û (pq)(ØpØq)Û q ® (p ® r)Û (pq)Ø(pq)(3) p®(q®p) Û Øp (Øq p)(4) (p®r) (q ® r) Û (Øpr) (Øq r)Û p (Ø

14、;p Øq) (重言式)Û (Øp Øq) r Û p (p ® Øq)Û Ø (p q) rÛ Øp ® (p ® Øq)Û (p q) ® r(5) (p®q) (p ® r) Û (Øp q) (Øp r) Û Øp (qr) Û p ® q r 2) 判定命題形式類型：(1) (p«q)®Ø(pØp)

15、(Øpq) (2) Ø(qØ(Øp q) p) Û (p«q)® Ø(Øpq)Û Øq (Øp q) p) Û Ø (p®q) (q®p) Û Øq (q p) Û Ø (Øpq) (Øqp)Û 0 Ø(Øpq)這是矛盾式 Û (pØq) (qØp) Ø(Øpq)Û (pØq)

16、1Û 1這是重言式(3) (p®q)(Øq®p) «p (4) (q®p)(Øp®q) Û(Øpq)(qp) «pÛ (Øqp)(pq)Û(Øp p) q) «p Û (Øq q) p Û q « pÛ p 這是可滿足式這是可滿足式(5) Ø(Ø(p q) ® Øp) (6) (p ® q r) (Ør®(p 

17、4; q) ÛØ( (p q) Øp)Û(Øp q r) (r (Øp q) ÛØ( (pØp) q)ÛØp (q r) r Øp q ÛØ 1ÛØp r q ÛØ0這是可滿足式 這是矛盾式2.3 提示：對(duì)偶式是將與互換、0與1互換。但要注意括號(hào)省略問題。1) Ø (ØpØq) Ø (Øpq) Û (p q)(pØq) Û p( q &#

18、216;q) Û p對(duì)偶式是：Ø (ØpØq) Ø (Øpq) Û p2) q Ø(Øpq) p) Û q Ø(q p) Û q Øq Øp Û 1對(duì)偶式是：q Ø(Øpq) p) Û 03) (pq) (pØq) (ØpØq) Û (pq) (p Øp)Øq) Û (pq) Øq Û (pq) Øq Û p

19、 ØqÛ Ø(Øpq)對(duì)偶式是：(pq) (pØq) (ØpØq) Û Ø(Øpq)2.4 香農(nóng)定理：ØA(p1, p2, , pn, 0, 1, Ø, , ) Û A(Øp1, Øp2, , Øpn, 1, 0, Ø, , )對(duì)偶式的定義為：A*(p1, p2, , pn, 0, 1, Ø, , )Û A(p1, p2, , pn, 1, 0, Ø, , )對(duì)偶式定義是重言式，其任何的替換實(shí)例仍

20、然是重言式，以Øpi替換pi，所以A*(Øp1, Øp2, , Øpn, 0, 1, Ø, , ) Û A(Øp1, Øp2, , Øpn, 0, 1, Ø, , )從而ØA(p1, p2, , pn, 0, 1, Ø, , ) Û A*(p1, p2, , pn, 0, 1, Ø, , )這就是香農(nóng)定理的對(duì)偶式表示式，簡(jiǎn)寫成 ØA(p1, p2, , pn) Û A*(Øp1, Øp2, , Øpn)。

21、顯然1) 若A是重言式，則A*是矛盾式； 2)若A是矛盾式，則A*是重言式； 都成立。*2.5 已知 Ø, , 是全功能集。Øp Û Øp；p q Û Ø(Øp Øq) Û Ø( p ®Øq)p q Û ØØp q) Û Ø p ® q即Ø, , 可有Ø, ®表示，所以Ø, ®是全功能集。實(shí)際上Øp Û p®0，Ø可用®

22、;表示，是冗余聯(lián)結(jié)詞，所以Ø, ®不是極小全功能集。*2.6 找出下式的等值的盡可能簡(jiǎn)單的由Ø,和Ø, 生成的公式:1) p(Øq (r®p) Û p¬ (q r) ¬, Û ¬ (¬p(¬q ¬r) ¬,2) p ® (q ® p) Û ¬p p ¬, (重言式) Û ¬(p ¬p) ¬, 3) (p q) r ® (p r) Û &#

23、172;p p ¬,(重言式) Û ¬(p ¬p) ¬, 4) p(Øq r®p) Û pq ¬r ¬, Û ¬( ¬p¬q r) ¬, 5) (p ® q Øq) Øp qÛ ¬ (p¬q) ¬, Û ¬p q ¬ ¬,*2.7 1) Ø,®: (Øp ® q)®r 2) Ø,

24、: Ø(Ø (Øp Øq) ¬r) 3) Ø,: ¬(p q) r 4) ­；(p­p) ­ (q­q)­ (r­r) 5) ¯: (p¯q) ¯r) ¯ (p¯q) ¯r)2.8 1) (pq) (Øpq) r) 2) (pqr) (q(Øpr) *3) (pq) ¯ (Øpqr) *4) (p ­ q) (Øp¯Øq)2.9

25、 1) Øp r ® q 2) ØrØp ® (p«Øq) Û Ø (Øp r) q ÛØ (ØrØp ) (pØq) (Øpq)Û Øp Ør qÛ (p Ør) (pØq) (Øpq)Û M5 Û(pqØr) (pØqØr) (pØq r)主合取范式，僅含有一個(gè)極大項(xiàng)， (Øpq r) (

26、16;pqØr)所以是可滿足式 Ûm6m4m5m3m2 含有5個(gè)極小項(xiàng)，是可滿足式 3) (p ® q r) (Øp ® Øq Ør) 4) p q (ØpØq) Û (Øp q r) (p Øq Ør)Û (p q Øp) (p q Øq) Û (p q r) (Øp Øq Ør) Û 0 Û m7m0 主析取范式，含有兩個(gè)極小項(xiàng)主析取范式不含有任何極大項(xiàng)， 所以是可滿足式是

27、矛盾式。2.10 1) (a) (pq)(Øpqr) (b) (p(qr)(q(Øpr) Û (pqr)(pqØr)(Øpqr) Û(p q)(qr)(Øpqr)Û m7m6m3Û(p q r)(p qØr)(pqr) Û M5M4M2M1M0 (pqØr)(Øpqr) Ûm7m6m3 Û M5M4M2M1M0主范式都相同，兩者等值。 2) (a) p®(q®r) (b) q®(p®r) Û

28、16; p (Øqr) ÛØ p (Øqr) Û M6Û M6 Û m0m1m2m3m4m5m7Û m0m1m2m3m4m5m7主范式都相同，兩者等值。 3) (a) p (ØpØq) (b) Ø(Øpq) Û p Øq Û p Øq Û m2Û m2 Û M0M1M3Û M0M1M3主范式都相同，兩者等值。 4) (a) (p®q)® p q (b) (Øp

29、4;p) (r®p) Û Ø (Øpq) p q Û (p p) (Ørp) Û (pØq) p q Û pÛ (pØq r) (pØqØr) Û (pØq r) (pØqØr) (p q r) (p qØr)(p q r) (p qØr) Û m5m4m7m6Û m5m4m7m6 Û M0M1M2M3Û M0M1M2M3 主范式都相同，兩者等值。2.11 指派需要同

30、時(shí)滿足1), 2), 3)條件，以及只派兩個(gè)人的條件。條件1)： A®Ø(C«D) Û ØA Ø(CD) (ØCØD) Û ØA (ØCØD) (CD) Û (ØA ØCØD) (ØACD) Û (ØABØCØD) (ØAØBØCØD) (ØABCD) (ØAØBCD) Û M11M15M8M12條件2)：

31、Ø(BC) Û ØBØC Û (AØBØCD) (AØBØCØD) (ØAØBØCD) (ØAØBØCØD) Û M6M7M14M15條件3)： C®ØD Û ØCØD Û (ABØCØD) (AØBØCØD) (ØABØCØD) (ØAØBØC&#

32、216;D) Û M3M7M11M15這三個(gè)條件同時(shí)滿足，是合取關(guān)系。即為M11M15M8M12M6M7M14M3而指派的情況是各種可能的情況，是析取關(guān)系，為此得到析取范式，為m0m1m2m4m5m9m10m13這就是可能的情況，其中下標(biāo)的二進(jìn)制數(shù)對(duì)應(yīng)位置為1的就是要指派的人。如1：0001，只指派D條件只指派兩人，就是5：0101，9：1001，10：1010；即可以指派的情況有三種：B和D，A和D，或A和C2.12 解：按照題意，三個(gè)推測(cè)只有一個(gè)是對(duì)的。推測(cè)1：Ø(b «c)；推測(cè)2：ØaØb；推測(cè)3：Ø(b «d)推測(cè)

33、正確為肯定，推測(cè)錯(cuò)誤為否定。推測(cè)1正確：Ø(b «c) Ø(ØaØb) (b «d)ÛaØbcd 推測(cè)2正確：(b «c) (ØaØb) (b «d) Û ØaØbØcØd推測(cè)3正確：(b «c) Ø (ØaØb) Ø (b «d) Û (abc) (ØabØc)( acd)可以看到，只有推測(cè)3正確時(shí)(ØabØc)中含

34、有一個(gè)肯定的b。所以該生沒有說謊，他是從b地直接返校的。*111110BC001110AØAÙCAÙØC2.14 提示：設(shè)開關(guān)向上為肯定，向下為否定，四種情況分別是：1) 搬鍵C向上, A、B同向下時(shí)：Ø pØq r 2) 搬鍵A向上, B、C同向下時(shí)：pØq Ør3) 搬鍵B、C向上, A同向下時(shí)：Øpq r4) 搬鍵A、B向上, C同向下時(shí)：pq Ør各種情況都可以成立，所以是析取關(guān)系，可采用卡諾圖化簡(jiǎn)，得到Ø pØq r pØq Ør Øp

35、q r pq Ør ÛØ p r pØr即只要A或C中的一個(gè)但又不同時(shí)控制電燈即可。*2.15 按照題意：只要A有信號(hào)，F(xiàn)A就有信號(hào)，此時(shí)不管B，C是否有信號(hào)設(shè)A，B，C有信號(hào)分別表示為p，q，r。 只要A有信號(hào)的情況就是：100，101，110，111 即：FAÛm4m5m6m7Û p Û (p¯p) ¯ (p¯p)類似A無信號(hào)，但是B有信號(hào)，C不管有無信號(hào)，F(xiàn)B輸出信號(hào)。此時(shí)情況是：010，011FBÛm2m3ÛØpq Û p ¯ Ø

36、;qÛp ¯ (q¯q)FC輸出信號(hào)必須是只有C有信號(hào)，只有001一種情況，所以FCÛm1Û ØpØq r Û Ø(pq) r Û Ø ( (pq) Ør) Û (pq) ¯ Ør Û Ø (p¯q) ¯ Ør Û (p¯q) ¯ (p¯q) ¯ (r¯r)習(xí)題三答案3.1判斷前提是否一致，即判斷他們的的合取是否不為矛盾式：下面用主范式判

37、斷： 1) (p q) (s Ør) Ø(s Ør) Û(p q s) (p qØr) (Øs r) Û(p q r s) (p qØrØs)這是可滿足式，所以前提一致。2) p1 (Øp1 p2) (Øp1 Øp2 p3) (Øp1 Øp2 Øpn-1 pn) Û p1 p2 (Øp2 p3) (Øp2 Øpn-1 pn) Û p1 p2 p3 (Øp3 Øpn-1 pn)

38、Û Û p1 p2 p3 pnn個(gè)命題變項(xiàng)的合取，這是可滿足式，前提一致。3) (p q) (Øp Øq) (p ® q) Û (p q) (Øp Øq) (Øp q) Û (p q) Øp Û 0 諸前提矛盾，不一致；3.2構(gòu)造下列推理的證明：1) 前提q ® p, q « s, s « t, t r; 結(jié)論p q s r。證明 s « t 前提引入P (t®s) (s®t)置換TE t®s 化簡(jiǎn)TI t

39、 r 前提引入P t 化簡(jiǎn)TI s 假言推理TI q « s 前提引入P (q®s) (s®q)置換TE s®q 化簡(jiǎn)TI q 假言推理TI q ® p 前提引入P p 假言推理TI p q s r 合取TI2)前提p®(q®s),Ørp,q;結(jié)論r®s。證明 p ® (q ® s) 前提引入P q ® (p ® s) 置換TE q 前提引入P p ® s 假言推理TI Ør p 前提引入P r ® p 置換TE r ® s

40、假言三段論TI3)前提Ø( pØq),Øqr, Ør; 結(jié)論Øp。證明 Øq r 前提引入P Ør 前提引入P Øq 析取三段論TI Ø( p Øq) 前提引入P Øp q 置換TE Øp 析取三段論TI3.3 用相應(yīng)證明方法證明：1) 歸謬法： 前提p ® Øq, q Ør, r Øs； 結(jié)論Øp。證明 p 否定結(jié)論作為前提P p ® Øq 前提引入P Øq 假言推理TI q Ør 前

41、提引入P Ør 析取三段論TI r Øs 前提引入P Ør r Øs 合取TI 0 置換TI推出矛盾，所以原結(jié)論正確。2) 附加前提法：前提(p q) ® (r s), (s t) ® u; 結(jié)論p ® u。證明 p 附加前提引入P p q 附加TI (p q) ® (r s)前提引入P r s 假言推理TI s 化簡(jiǎn)TI s t 附加TI (s t) ® u 前提引入P u 假言推理TI p ® uCP規(guī)則CP3) 反證法： 前提Øp Øq, 結(jié)論Ø (p q)證

42、明 p q 否定結(jié)論作為前提引入P p 化簡(jiǎn)TI p q 附加TI Ø(Øp Øq) 置換TE得到否定的前提，原推理正確。3.4 反證法。否定結(jié)論推出否定的前提。否定結(jié)論，即如果2不能整除a，即a=2m+1；則a2=(2m+1)2=4m2+2m+1所以2不能整除a2。這正是否定的前提。原推理正確。*3.5 甲在最后，丙在最前，甲先推測(cè)自己戴的帽子。設(shè)甲乙丙戴紅帽子分別為p，q，r甲看到乙和丙戴的帽子推測(cè)自己帶的，乙根據(jù)看到丙所戴及甲所判斷的來確定自己所戴帽子，根據(jù)可能的情況是：(1) 乙和丙戴黑帽子，甲確定自己戴紅帽子，即pØqØr。三個(gè)前提成

43、立，丙能確定自己為Ør，即戴黑帽子；(2) 乙和丙中并非都戴黑帽子，甲不能確定自己戴什么帽子，可能的情況是(2.1) 乙和丙都戴紅帽子：qr，(2.2) 乙和丙一個(gè)戴紅帽子：(Øqr) (qØr)綜合即為(qr)(Øqr) (qØr)Û r (qØr) 一種情況就是：r，則q，Øq可能都成立，乙無法判斷自己所戴帽子，而丙一旦聽到乙無法判斷自己所戴帽子，即可確定自己帶紅帽子； 另一種情況是：(qØr)，乙看到丙帶黑帽子，確定自己帶紅帽子；丙一旦聽到乙說自己帶紅帽子，可確定自己帶黑帽子；總結(jié)就是：甲確定自己戴

44、紅帽子，丙可確定自己戴黑帽子； 甲不能確定所戴帽子：乙可確定自己戴紅帽子，丙能確定自己戴黑帽子； 乙不能確定自己所帶帽子，丙能確定自己戴紅帽子；所以丙總能判斷出自己所戴帽子。*3.6 針對(duì)其中一個(gè)人，是哥哥(p)是弟弟(Øp)，是說真話 (q)還是說謊(Øq)，都必居其一。 可能的情況是：pq，pØq，Øpq，ØpØq， 詢問只能就這幾種情況詢問，并根據(jù)答復(fù)情況確定結(jié)果。而答復(fù)可能是說真話的答復(fù)，或者說假話的答復(fù)。兩種答復(fù)都要能判斷。 如果只詢問一種情況，如pq，則肯定答復(fù)結(jié)果是(pq) q) (Ø(pq) Øq)

45、ÛpqØqÛ pØq，無法得到確定的結(jié)果；不必再討論否定答復(fù)結(jié)果。 如果只詢問兩種的情況，有共同點(diǎn)時(shí)，如pq，pØq，則肯定答復(fù)結(jié)果是(pq ØpØq) q Ø(pq ØpØq) Øq Û pq ØpØq，無法確定結(jié)果，不必再討論否定答復(fù)結(jié)果。 無共同點(diǎn)時(shí)，如pq，ØpØq，則肯定答復(fù)結(jié)果是(pq ØpØq) q Ø(pq ØpØq) Øq Û p，能確定被詢問的人是

46、哥哥；否定答復(fù)結(jié)果是Ø(pq ØpØq) q (pq ØpØq) Øq Û Øp；能確定被詢問的人是弟弟。問話為： “你是哥哥且你說了真話，或你是弟弟且你說了假話”對(duì)嗎？?？隙ㄕ呤歉绺?，否定者是弟弟。如果另外一對(duì)無共同點(diǎn)的情況，如Øpq，pØq，則肯定答復(fù)結(jié)果是(ØpqpØq) q Ø(ØpqpØq) Øq Û Øp，能確定被詢問的人是弟弟；否定答復(fù)結(jié)果是Ø(ØpqpØq) q (

47、16;pqpØq) Øq Û p；能確定被詢問的人是哥哥。問話也可為： “你是哥哥且你說了假話，或你是弟弟且你說了真話”對(duì)嗎？?？隙ㄕ邽榈艿埽穸ㄕ呤歉绺?。3.7證明下列各推理是否正確.提示：也可以直接利用等值演算方法，獲得原蘊(yùn)涵式是可滿足式，則推理不正確。1) p：我是一年級(jí)學(xué)生；q：我要學(xué)習(xí)高等數(shù)學(xué)，r：我要學(xué)習(xí)集合論；s：我是二年級(jí)學(xué)生；t：我要學(xué)習(xí)數(shù)學(xué)邏輯，u：我要學(xué)習(xí)圖論；前提：p ®( qr)，s®(tu)，ØqØs結(jié)論：ØqØrØtØu證明 ØqØs

48、前提引入P Øq 化簡(jiǎn)TI Øs化簡(jiǎn)TI p ®( qr) 前提引入P到此無法繼續(xù)往下推理，所以無法證明，即原推理是錯(cuò)誤的。2) p：我復(fù)習(xí)完功課；q：我打籃球，r：我打乒乓球；前提：q ® p，q®Ør，Øp結(jié)論：ØqØr證明 q ® p 前提引入P Øp 前提引入P Øq 拒取式TI q®Ør 前提引入P到此無法繼續(xù)往下推理，所以無法證明，即原推理是錯(cuò)誤的。3) p：我的程序通過了；q：我高興，r：我生活愉快；前提：p ® q，r®

49、q，p結(jié)論：r證明 p ® q 前提引入P p 前提引入P q 假言推理TI r®q 前提引入P到此無法繼續(xù)往下推理，所以無法證明得到r，即原推理是錯(cuò)誤的。3.8 解：符號(hào)化：p：甲獲勝；q：乙獲勝；r：丙獲勝；s：丁獲勝；前提：p®Øq，r®q，Øp®s，結(jié)論：r®s r®q 前提引入P p®Øq 前提引入P q®Øp 置換TE r®Øp假言三段論TI Øp®s前提引入P r®s 假言推理TI3.9 解：符號(hào)化：p

50、：今天天晴；q：今天下雨；r：我去看電影；s：我看書；前提：p q，p®r， r®Øs，結(jié)論：s®q p®r 前提引入P r®Øs 前提引入P p®Øs假言三段論TI p q®Øs q前后件附加TI p q 前提引入P Øs q假言推理TI s®q 置換TIE提示：3.8、3.9可用CP規(guī)則。*3.10 機(jī)器證明是：歸謬法，并利用轉(zhuǎn)換成合取范式，以便得到各簡(jiǎn)單析取式，各簡(jiǎn)單析取式之間消解。1) 前提q ® p, q « s, s « t

51、, t r; 結(jié)論p q s r。證明 Ø(p q s r) 否定結(jié)論引入得合取范式Øp Øq Øs Ør，也是簡(jiǎn)單析取式 q ® p前提引入得合取范式Øq p，也是簡(jiǎn)單析取式 q « s 前提引入得合取范式(Øq s) (q Øs)，再得Øq s q Øs 得到的第二個(gè)簡(jiǎn)單析取式 s « t 前提引入得合取范式(Øt s) (t Øs)，再得Øt s t Øs得到的第二個(gè)簡(jiǎn)單析取式 t r 前提引入為合取范式，得到t r得到

52、的第二個(gè)簡(jiǎn)單析取式 Øq Øs Ør 消解TI Øp Øq Ør消解TI Øp Øs Ør 消解TI Øp Øq Øt Ør消解TI Øp Øq Øs 消解TI p Øs 消解TI Øq t 消解TI q Øt消解TI s消解TI q消解TI Øp Øq消解TI Øq消解TI(21) 空消解TI得空，所以原推理正確。注：機(jī)器證明中有許多過程是機(jī)器的，得到的結(jié)果在后續(xù)可能并沒用，

53、如上面得到，。2)前提p®(q®s),Ørp,q; 結(jié)論r®s。證明 Ø(r®s) 否定結(jié)論得合取范式rØs，得簡(jiǎn)單析取式r和 Ø s 得到第二個(gè)簡(jiǎn)單析取式 p®(q®s)前提引入得合取范式Øp Øq s Ør p 前提引入P q 前提引入P p 消解TI Øp Øq 消解TI Øp消解TI 空消解TI得空，所以原推理正確。3)前提Ø( pØq),Øqr, Ør; 結(jié)論Øp。證明 p 否

54、定結(jié)論引入P Ø( p Øq) 前提引入得Øp qP，E Øqr 前提引入P Ør 前提引入P q 消解TI Øpr 消解TI Øq 消解TI 空消解TI得空，所以原推理正確。習(xí)題四答案4.1 將下列命題用0元謂詞符號(hào)化： 1) P(x): x是素?cái)?shù), Q(x): x是偶數(shù)；a:2; P(a) Q(a) 2) P(x,y): x大于y, a:2, b:3, c:4；P(a,b) ®P(a,c); 3) P(x,y): x比y高, a:張明, b: 李民, c: 趙亮; P(a,b) P(b,c) ®P(a

55、,c)； 4) P(x): x是素?cái)?shù), a:3; ØP(a)； 5) P(x): x是素?cái)?shù), a:2,b:3; P(a) P(b)； 6) P(x,y): x能被y整除,a:16,b:4,c:8；P(a,b) P(a,c) 7) P(x,y): x能整除y, a:7,b:100,c:3, P(a,b) ®P(c,b); 8) P(x,y): x能整除y , Q(x): x是偶數(shù),b:2; P(2,a) « Q(a)。4.2 解：個(gè)體域全部為全總個(gè)體域： 1) P(x): x是火車，Q(x):x是輪船，R(x,y):x比y快； "x(P(x) ®

56、"y(Q(y) ® R(x,y) 2) P(x): x是汽車，Q(x):x是火車，R(x,y):x比y慢； $x(P(x) "y(Q(y) ® R(x,y) 3) P(x): x是實(shí)數(shù)，Q(x，y):x大于y； Ø$x(P(x) "y(P(y) ® Q(x,y) 4) P(x,y): x和y是對(duì)頂角，Q(x，y):x等于y； "x"y(P(x,y) ® Q(x,y) 5) P(x): x是人, Q(x): x會(huì)犯錯(cuò)誤； Ø$(P(x) ØQ(x) = "x(P(x)

57、® Q(x) 6) P(x): x是北京人, Q(x): x是在北京工作的人； Ø"x(Q(x)®P(x) = $x(Q(x) ØP(x) 7) P(x): x是偶數(shù), Q(x,y): x能被y整除, a:2； "x(P(x)®Q(x,a) 8) 所有能飛的動(dòng)物都是鳥； P(x): x是動(dòng)物, Q(x): x是鳥，R(x): x能飛； "x(P(x) R(x)®Q(x)4.3 解：1) 對(duì)于任意的x，存在y，使得x × y=0；(a)、(b)情況下為1，(c)、(d)情況下為0。2) 存在x，對(duì)

58、于所有y，均有x × y=0；(a)、(b)情況下為1，(c)、(d)情況下為0。3) 對(duì)于任意的x，存在y，使得x × y=1；(a)、(b)、(c)情況下為0，(d)情況下為1。4) 存在x，對(duì)于所有y，均有x × y=1；任何情況下為0。5) 對(duì)于任意的x，存在y，使得x × y=x；任何情況下為1。6) 存在x，對(duì)于所有y，均有x × y=x；(a)、(b)情況下為1，(c)、(d)情況下為0。7) 對(duì)于任意的x，y，存在z，使得x - y=z；(a)、(b)情況下為1，(c)、(d)情況下為0。4.4 解1) P(x): x2-1 =

59、 (x+1)(x-1) (a) 個(gè)體域?yàn)樽匀粩?shù)集合: "xP(x), 真 (b) 個(gè)體域?yàn)閷?shí)數(shù)集合: "xP(x), 真 (c) 個(gè)體域?yàn)橐磺惺挛? "x(Q(x)®P(x), Q(x): x是數(shù)，真2) P(x): x + 5 = 2 (a) 個(gè)體域?yàn)樽匀粩?shù)集合: "xP(x), 假 (b) 個(gè)體域?yàn)閷?shí)數(shù)集合: "xP(x), 真 (c) 個(gè)體域?yàn)橐磺惺挛? "x(Q(x) P(x), Q(x): x是數(shù)， 真4.5 解1) x<0: L(x, 0) Ø$x L(x, 0)真2) x + 0 = x: F(x, 0, x) "xF(x, 0, x)真3) x · y = y