離散數(shù)學答案命題邏輯

1、第二章 命題邏輯習題2.11解 不是陳述句，所以不是命題。 x取值不確定，所以不是命題。 問句，不是陳述句，所以不是命題。 驚嘆句，不是陳述句，所以不是命題。 是命題，真值由具體情況確定。 是命題，真值由具體情況確定。 是真命題。 是悖論，所以不是命題。 是假命題。 2解 是復合命題。設(shè)p：他們明天去百貨公司；q：他們后天去百貨公司。命題符號化為。 是疑問句，所以不是命題。 是悖論，所以不是命題。 是原子命題。 是復合命題。設(shè)p：王海在學習；q：李春在學習。命題符號化為pÙq。 是復合命題。設(shè)p：你努力學習；q：你一定能取得優(yōu)異成績。p®q。 不是命題。 不是命題 。是復合

2、命題。設(shè)p：王海是女孩子。命題符號化為：Øp。 3解 如果李春遲到了，那么他錯過考試。 要么李春遲到了，要么李春錯過了考試，要么李春通過了考試。 李春錯過考試當且僅當他遲到了。 如果李春遲到了并且錯過了考試，那么他沒有通過考試。4解 Øp®(qÚr)。p®q。q®p。q ® p。習題2.2 1解 是1層公式。 不是公式。 一層： pÚq，Øp 二層：Øp«q所以，是3層公式。 不是公式。 (p®q)ÙØ(Øq«( q®

3、6;r)是5層公式，這是因為 一層：p®q，Øq，Ør 二層：q®Ør 三層：Øq«( q®Ør) 四層：Ø(Øq«( q®Ør) 2解 A=(pÚq)Ùq是2層公式。真值表如表2-1所示：表2-1pq0000011110101111 是3層公式。真值表如表2-2所示：表2-2pq00101011101000111111 是3層公式。真值表如表2-3所示：表2-3pqr0000001001000101000110110011100001

4、1101001111010111111111是4層公式。真值表如表2-4所示： 3解 真值表如表2-5所示：表2-5pq001111011000100101110001所以其成真賦值為：00，10，11；其成假賦值為01。 真值表如表2-6所示：表2-6pqr0000100100010010110010001101001101111111所以其成真賦值為：000，010，100，110，111；其成假賦值為001，011，101。真值表如表2-7所示，所以其成真賦值為：00，11；成假賦值為：01，10，。 4解 設(shè)，其真值表如表2-8所示：表2-8pq00011010111001111101

5、故為重言式。 設(shè)A=(pÙq)ÙØ(pÚq)，其真值表如表2-9所示：表2-9pqpÙqpÚqØ(pÚq)A000010010100100100111100故A=(pÙq)ÙØ(pÚq)為矛盾式。 設(shè)A=(p®q)«(Øp«q)，其真值表如表2-10所示：表2-10pq001010011111100100110010故A=(p®q)«(Øp«q)為可滿足式。 設(shè)，其真值表如表2-11所示：表2-1

6、1pqr0001111100111111010100110111111110001001101010111101000111111111故為重言式。習題2.3 1解 真值表如表2-12所示：表2-12pq0011101011001010010101100010由真值表可以看出和所在的列相應(yīng)填入值相同，故等值。 真值表如表2-13所示：表2-13pq001000010000101011110101由真值表可以看出和所在的列相應(yīng)填入值相同，故等值。 真值表如表2-14所示：表2-14pq0011111011011110010101100100由真值表可以看出Øp和(p®q)&#

7、217;(p®Øq)所在的列相應(yīng)填入值相同，故等值。真值表如表2-15所示：pqrq®r p®(q®r) pÙq (pÙq)®r 00011010011101010010101111011001101101110111000101111111表2-15 由真值表可以看出p®(q®r)和(pÙq)®r所在的列相應(yīng)填入值相同，故等值。2證明 (pÙq)ÚØ (ØpÚq)Û (pÙq)Ú( pÙ

8、;Øq)Û pÙ (qÚØq)Û p。(p®q)Ù(q®p)Û(ØpÚq) Ù(ØqÚp)Û(ØpÙØq)Ú(ØpÙ p)Ú( qÙØq)Ú(qÙ p)Û( pÙq)Ú(ØpÙØq)。由可得，Ø(p«q)ÛØ( pÙq)

9、Ú(ØpÙØq)Û(Ø pÚØq)Ù(pÚq)Û(q®Øp)Ù(Øp®q)ÛØp«q。p®(q®r)ÛØ pÚ(ØqÚ r)ÛØ qÚ(ØpÚ r)Û q®( p ®r)。 3解 Ø(p®Øq)ÛØ(Ø

10、;pÚØq)ÛpÙq Ø(Øp®Øq)ÛØ( pÚØq)ÛØpÙq Ø(p«Øq)ÛØ(p®Øq)Ù(Øq®p)ÛØ(p®Øq)ÚØ(Øq®p)Û(pÙq) Ú(ØpÙØq)Û p«q。同理

11、可證Ø(Øp«q)Û p«q。 4解 與習題2.2第4（4）相同。 真值表如表2-16所示：表2-16p q Øp Øq p®q Øq ®Øp A 0011111011011110010011100111所以公式是重言式。真值表如表2-17所示，所以公式是矛盾式。表2-170011100011010010010101100100 真值表如表2-18所示，所以公式是重言式。表2-18000001001001010001011001100001101001110101111111 真值表如

12、表2-19所示，所以公式僅為可滿足式。表2-19001011011101100100110100 真值表如表2-20所示，所以公式是重言式。表2-20pqr p®qr®qpÙr(p®q)Ù(r®q)(pÙr)®qA000110111001100011010110111011110111100010011101001001110110111111111111 5解 設(shè)p：他努力學習；q：他會通過考試。則命題符號化p®q。其否定Ø(p®q)Û pÙØq。 所以

13、語句的否定：他學習很努力但沒有通過考試。 設(shè)p：水溫暖；q：他游泳。則命題符號化p«q。其否定Ø(p«q)Û p«Øq。 所以語句的否定：當且僅當水不溫暖時他游泳。 設(shè)p：天冷；q：他穿外套；r：他穿襯衫。則命題符號化p®(qÙØr) 其否定Ø( p®(qÙØr) ÛØ(ØpÚ(qÙØr) Û pÙØ( qÙØr) Û pÙ(Ø

14、qÚ r) 所以語句的否定：天冷并且他不穿外套或者穿襯衫。 設(shè)p：他學習；q：他將上清華大學；r：他將上北京大學。則命題符號化其否定所以語句的否定：他努力學習，但是沒有上清華大學，也沒有上北京大學。 6解 設(shè)p：張三說真話；q：李四說真話；r：王五說真話。則：p«Øq, q«Ør(ÛØq«r), r«(ØpÙØq)為真,因此p«(ØpÙØq)Û(pÙØpÙØq)Ú(Ø

15、pÙ(pÚq)ÛØpÙq為真。因此，p為假，q為真，所以r為假。故張三說謊，李四說真話，王五說謊。 7解 設(shè)p：甲得冠軍；q：乙得亞軍；r：丙得亞軍；s：丁得亞軍。前提：p®(qÚr)，q®Øp，s®Ør，p結(jié)論：Øs證明 p®(qÚr)為真，其前件p為真，所以qÚr為真，又q®Øp為真，其后件Øp為假，所以要求q為假，所以r為真。又s®Ør為真，其后件Ør為假，所以要求s為假，故

16、16;s為真。習題2.4 1解 設(shè)p：明天下雨；q：后天下雨。命題符號化。 設(shè)p：明天我將去北京；q：明天我將去上海。命題符號化。 2解 3證明 因為，是功能完備聯(lián)結(jié)詞集，所以，含有外的其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含中的聯(lián)結(jié)詞的公式。又因為即含有的公式均可以轉(zhuǎn)換為僅含中的聯(lián)結(jié)詞的公式。因此，含外其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含中的聯(lián)結(jié)詞的公式。 故是功能完備聯(lián)結(jié)詞集。 4證明 是極小功能完備集，因而只需證明中的每個聯(lián)結(jié)詞都可以用­ 表示，就說明是功能完備集。只有一個聯(lián)結(jié)詞，自然是極小功能完備集。事實上，ØpÛØ(pÙp)Ûp

17、3;p，pÙqÛØØ(pÙq)ÛØ(p­q)Û(p­q)­(p­q)。對于證明是極小功能完備集，可類似證明。習題2.5 1解 ； 2解 即為其析取范式。即為其合取范式。即為其合取范式。ØpÙ(q«r)ÛØpÙ(qÙr)Ú(ØqÙØr)Û(ØpÙqÙr)Ú(ØpÙØqÙØ

18、r) 即為其析取范式。即為其合取范式。為其析取范式。即為其析取范式和合取范式。 3解 即為其主合取范式。其主析取范式為å3ÛpÙq。 。故其主析取范式為å(0,1,2,3)=(ØpÙØq)Ú(ØpÙq)Ú(pÙØq)Ú(pÙq)。 即為其主合取范式。其主析取范式為å(2,4,5,6,7) Û (ØpÙqÙØr)Ú(pÙØqÙØr)

19、8;(pÙØqÙr)Ú(pÙqÙØr)Ú(pÙqÙr)。 即為其主合取范式。其主析取范式為。 4解 真值表如表2-21所示, 所以其極小項是pÙØq，極大項為pÚq，pÚØq，ØpÚØq。表2-21pq0010011010011110其主析取范式是：pÙØq，主合取范式為：(pÚq)Ù( pÚØq)Ù(ØpÚØq)。

20、真值表如表2-222所示, 所以其極小項是ØpÙq, pÙØq, pÙq, 極大項為pÚq。表2-22pq000100011101101011111101其主析取范式是：(ØpÙq)Ú(pÙØq)Ú(pÙq)，主合取范式為：pÚq。 真值表如表2-23所示，所以其極小項是ØpÙqÙr,pÙØqÙØr, pÙØqÙr, pÙqÙØ

21、r,pÙqÙr,表2-23pqr000100001100010100011111100001101001110001111001極大項為pÚqÚr，pÚqÚØr，pÚØqÚr。其主析取范式是：(ØpÙqÙr)Ú(pÙØqÙØr)Ú(pÙØqÙr)Ú(pÙqÙØr)Ú(pÙqÙr)，主合取范式為：(pÚ

22、;qÚr)Ù(pÚqÚØr)Ù(pÚØqÚr) 。 真值表如表2-24所示,所以其極小項為ØpÙØqÙr,ØpÙqÙr,pÙØqÙØr,pÙØqÙr,pÙqÙr,而極大項分為pÚqÚr，pÚØqÚr，ØpÚØqÚr.主合取范式為(pÚqÚr

23、)Ù(pÚØqÚr)Ù(ØpÚØqÚr),主析取范式為(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙØqÙØr,)Ú(pÙØqÙr)Ú(pÙqÙr)。表2-24pqr00010001110101001111100011010111010111115解 (ØpÚq)Ù(Ø(

24、ØpÙØq)Û(ØpÚq)Ù(pÚq)Û qÛ (ØpÙq)Ú(pÙq)， 故為可滿足式。 故為重言式。Ø(pÚ(qÙr)«(pÚq)Ù(pÚr)ÛØ(pÚ(qÙr)«(pÚ(qÙr)Û(pÚ(qÙr)Ú(pÚ(qÙr)ÙØ(pÚ

25、(qÙr)ÚØ(pÚ(qÙr)Û(pÚ(qÙr)ÙØ(pÚ(qÙr)Û(pÚ(qÙr)ÙØpÙØ(qÙr)Û(ØpÙqÙr)Ù(ØqÚØr)Û0。 故為矛盾式。 故僅為可滿足式。6證明 右邊已經(jīng)是主合取范式。而左邊主合取范式已是ØpÙØq，因此，Ø(pÚ q)

26、ÛØpÙØq，證畢。右邊(pÚ q)Ù(pÚØq)已經(jīng)是主合取范式。pÛpÚ(qÙØq)Û (pÚ q)Ù(pÚØq)。因此，。左邊p®(q®r)ÛØpÚ(ØqÚr)ÛØpÚØqÚr，而右邊ÛØ(pÙq)ÚrÛØpÚØqÚ

27、;r，因此，。習題2.61解 設(shè)p：這里有演出；q：這里通行是困難的；r：他們按照指定時間到達。前提：p®q, r®Øq,r結(jié)論：Øp證明 r Pr®Øq PØq T假言推理p®q P Øp T拒取式2證明 s Ps®p P p T假言推理p®q Pq T假言推理證明 r P附加前提引入r®q Pq T假言推理p®Øq PØp T拒取式Øp®s Ps T假言推理r®s TCP證明 p P否定結(jié)論引入p®q

28、Pq T假言推理q®r Pr T假言推理ØrÙs PØr T化簡rÙØr T合取證明 p P附加前提引入ØpÚq Pq 析取三段論r®Øq PØr 拒取式p®Ør CP證明 p P附加前提引入p®(q®r) Pq®r T假言推理q P附加前提引入r T假言推理(rÙs)®t PØrÚØsÚt T蘊涵等價式ØsÚt T析取三段論Øh®(s&

29、#217;Øt) PØsÚt ®h T假言易位 h T假言推理 q®h TCP13. p®(q®h) TCP 3解 推理不正確。在到化簡時，只能對整個公式進行而不是子公式。 4解 正確。P，P附加前提引入；T析取三段論；P；T假言推理；P；T假言推理；TCP。 5解 設(shè)p：張三努力工作，q：李四高興，r：王五高興，s：劉六高興 前提：p®(qÚr)，q®Øp，s®Ør 結(jié)論：p®Øs 證明：p P附加前提引入p®(qÚr) P

30、qÚr T假言推理q®Øp PØq T拒取式r T析取三段論s®Ør PØs T拒取式p®Øs TCP 6解 設(shè)：p：天下雪；q：馬路結(jié)冰；r：汽車開得快；s：馬路塞車。前提：p®q，q®Ør，Ør®s，Øs結(jié)論：Øp證明p®q Pq®Ør Pp®Ør 推理三段論Ør®s Pp®s 推理三段論Øs P Øp 拒取式復習題2 1解 設(shè)p：3

31、是偶數(shù)，q：中國人的母語是漢語。命題符號化。 設(shè)p：你抽煙，q：你很容易得病。命題符號化。 設(shè)p：今天是星期一，q：明天才是星期二。命題符號化。 設(shè)p：李春這個學期離散數(shù)學考了100分。q：李春這個學期數(shù)據(jù)結(jié)構(gòu)考了100分。命題符號化。 設(shè)p：下雪路滑，q：他遲到了。命題符號化。 設(shè)p：經(jīng)一事，q：長一智。命題符號化。 設(shè)p：一朝被蛇咬，q：十年怕井繩。命題符號化。 設(shè)p：以物喜，q：以己悲。命題符號化。 2. 解 命題中的“或”是不可兼或，因此，可以直接用“”符號化；根據(jù)聯(lián)結(jié)詞的性質(zhì)及其之間的轉(zhuǎn)換關(guān)系，可知命題“李春生于1979年或生于1980年”的本意是“李春生于1979年（但不能生于19

32、80年）或生于1980年（但不能生于1979年）”，因此，也可以轉(zhuǎn)化為“”對其進行符號化。3解 設(shè)p：李剛會拳擊，q：李春會唱歌。命題符號化(ØpÚØq)ÙØ(p®q)。而(ØpÚØq)ÙØ(p®q)Û(ØpÚØq)ÙØ(ØpÚq)Û(ØpÚØq)ÙpÙØqÛpÙØq因此，李剛會拳擊并且李春不會唱歌

33、。 4解 A的極小項對應(yīng)于其真值表中的成真賦值0001，0110，1000，1001，1010，1100，1101，1111。成真賦值對應(yīng)二進制數(shù)轉(zhuǎn)化為十進制數(shù)就是A的極小項的下標。由此可得，A的極小項為： ；。 相應(yīng)的，A的極大項對應(yīng)于其真值表中的成假賦值，成假賦值對應(yīng)二進制數(shù)轉(zhuǎn)化為十進制數(shù)就是A的極大項的下標。由此可得，A的極大項為： ；。 由問題得到了A的極小項和極大項，于是與A等值的主析取范式和主合取范式可以直接得到，分別為：；。 從A的主析取范式出發(fā)，進行等值演算化簡，可得析取范式的最簡形式：(ØpÙØqÙØrÙs)

34、8;(ØpÙqÙrÙs)Ú(pÙØqÙØrÙØs)Ú(pÙØqÙØrÙs)Ú(pÙØqÙrÙØs)Ú(pÙqÙØrÙØs)Ú(pÙqÙØrÙs)Ú(pÙqÙrÙs)Û(ØpÙØq&

35、#217;ØrÙs)Ú(qÙrÙs)Ú(pÙØqÙØr)Ú(pÙØqÙrÙØs)Ú(pÙqÙØr)Û(pÙØr)Ú(ØpÙØqÙØrÙs)Ú(qÙrÙs)Ú(pÙØqÙrÙØs)Û(pÙ&#

36、216;r)Ú(ØqÙØrÙs)Ú(qÙrÙs)Ú(pÙØqÙrÙØs)Û(pÙØr)Ú(ØqÙØrÙs)Ú(qÙrÙs)Ú(pÙØqÙØs) 5 證明 6解 公式的真值表如表2-27所示：表2-27p0011111011011110011001100010 從真值表可見，公式所在列的填入值有1也有

37、0，故僅為可滿足式。(p®Øq)Ù(Øq®Øp)Û(ØpÚØq)Ù(qÚØp)ÛÕ(2,3)為其主合取范式，可見公式僅為可滿足式。 公式真值表如表2-28所示：表2-28pqr0000100111010110111110011101111101111111 p®(pÚqÚr)ÛØpÚpÚqÚrÛ1Ûå(0,1,2,3,4,5,6,7) 從

38、真值表可見，公式所在的列的填入值均為1，等值演算，以及求出的主析取范式均說明公式是重言式。A=(p®q)Ù(q®r)®(p®r)真值表見習題2.2第4(4)題。(p®q)Ù(q®r)®(p®r)ÛØ(ØpÚq)Ù(ØqÚr)Ú(ØpÚr)Û(pÙØq)Ú(qÙØr)ÚØpÚrÛ1. 從真值表可見，公

39、式所在的列的填入值均為1，由等值演算，以及求出的主析取范式均說明公式是重言式。7證明 p P附加前提引入p®(q®r) Pq®r T假言推理q P附加前提引入q®(r®s) Pr®s T假言推理q®s T假言三段論p®(q®s) TCP證明 Øw Pu®w PØu T拒取式ØsÚu PØs T析取三段論ØrÚs PØr T析取三段論(pÚq)®r PØ(pÚq) T拒取式

40、16;pÙØq) T德×摩根律證明 p P附加前提引入p®qÚr PqÚr T假言推理q®Øp PØq T拒取式r T析取三段論s®Ør PØs T拒取式p®Øs TCP8解 pÙr Pp T化簡p®q Pq T假言推理Ø(qÚs) PØqÙØs T德×摩根律Øq T化簡ØqÙq T合取由得到矛盾，可見p®q，Ø(qÚ

41、s)，pÙr不能同時成立。9解 設(shè)p：小王曾經(jīng)到過受害人的房間，q：小王11點以前離開，r：小王犯了謀殺罪，s：看門人看到小王。符號化：(pÙØq)®r)ÙpÙ(q®s)ÙØs)Þr。形式構(gòu)造推理證明前提：(pÙØq)®r，p，q®s，Øs結(jié)論：r證明 Øs Pq®s PØq T拒取式p PpÙØq T合取(pÙØq)®r P T假言推理真值表技術(shù)：真值表如表2-30所示，設(shè)A=(pÙØq)®r)ÙpÙ(q