離散數學課后習題答案(邱學紹).doc

《離散數學課后習題答案(邱學紹).doc》由會員分享，可在線閱讀，更多相關《離散數學課后習題答案(邱學紹).doc（77頁珍藏版）》請在裝配圖網上搜索。

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

2、。命題符號化為：p。 3解 如果李春遲到了，那么他錯過考試。 要么李春遲到了，要么李春錯過了考試，要么李春通過了考試。 李春錯過考試當且僅當他遲到了。 如果李春遲到了并且錯過了考試，那么他沒有通過考試。4解 p(qr)。pq。qp。q p。習題1.2 1解 是1層公式。 不是公式。 一層： pq，p 二層：pq所以，是3層公式。 不是公式。 (pq)(q( qr)是5層公式，這是因為 一層：pq，q，r 二層：qr 三層：q( qr) 四層：(q( qr) 2解 A=(pq)q是2層公式。真值表如表2-1所示：表2-1pq0000011110101111 是3層公式。真值表如表2-2所示：表2

3、-2pq00101011101000111111 是3層公式。真值表如表2-3所示：表2-3pqr00000010010001010001101100111000011101001111010111111111是4層公式。真值表如表2-4所示： 3解 真值表如表2-5所示：表2-5pq001111011000100101110001所以其成真賦值為：00，10，11；其成假賦值為01。 真值表如表2-6所示：表2-6pqr0000100100010010110010001101001101111111所以其成真賦值為：000，010，100，110，111；其成假賦值為001，011，101。

4、真值表如表2-7所示，所以其成真賦值為：00，11；成假賦值為：01，10，。 4解 設，其真值表如表2-8所示：表2-8pq00011010111001111101故為重言式。 設A=(pq)(pq)，其真值表如表2-9所示：表2-9pqpqpq(pq)A000010010100100100111100故A=(pq)(pq)為矛盾式。 設A=(pq)(pq)，其真值表如表2-10所示：表2-10pq001010011111100100110010故A=(pq)(pq)為可滿足式。 設，其真值表如表2-11所示：表2-11pqr000111110011111101010011011111111

5、0001001101010111101000111111111故為重言式。習題1.3 1解 真值表如表2-12所示：表2-12pq0011101011001010010101100010由真值表可以看出和所在的列相應填入值相同，故等值。 真值表如表2-13所示：表2-13pq001000010000101011110101由真值表可以看出和所在的列相應填入值相同，故等值。 真值表如表2-14所示：表2-14pq0011111011011110010101100100由真值表可以看出p和(pq)(pq)所在的列相應填入值相同，故等值。真值表如表2-15所示：pqrqr p(qr) pq (pq)

6、r 00011010011101010010101111011001101101110111000101111111表2-15 由真值表可以看出p(qr)和(pq)r所在的列相應填入值相同，故等值。2證明 (pq) (pq) (pq)( pq) p (qq) p。(pq)(qp)(pq) (qp)(pq)(p p)( qq)(q p)( pq)(pq)。由可得，(pq)( pq)(pq)( pq)(pq)(qp)(pq)pq。p(qr) p(q r) q(p r) q( p r)。 3解 (pq)(pq)pq (pq)( pq)pq (pq)(pq)(qp)(pq)(qp)(pq) (pq)

7、pq。同理可證(pq) pq。 4解 與習題2.2第4（4）相同。 真值表如表2-16所示：表2-16p q p q pq q p A 0011111011011110010011100111所以公式是重言式。真值表如表2-17所示，所以公式是矛盾式。表2-170011100011010010010101100100 真值表如表2-18所示，所以公式是重言式。表2-18000001001001010001011001100001101001110101111111 真值表如表2-19所示，所以公式僅為可滿足式。表2-19001011011101100100110100 真值表如表2-20所示，

8、所以公式是重言式。表2-20pqr pqrqpr(pq)(rq)(pr)qA000110111001100011010110111011110111100010011101001001110110111111111111 5解 設p：他努力學習；q：他會通過考試。則命題符號化pq。其否定(pq) pq。 所以語句的否定：他學習很努力但沒有通過考試。 設p：水溫暖；q：他游泳。則命題符號化pq。其否定(pq) pq。 所以語句的否定：當且僅當水不溫暖時他游泳。 設p：天冷；q：他穿外套；r：他穿襯衫。則命題符號化p(qr) 其否定( p(qr) (p(qr) p( qr) p(q r) 所以語句

9、的否定：天冷并且他不穿外套或者穿襯衫。 設p：他學習；q：他將上清華大學；r：他將上北京大學。則命題符號化其否定所以語句的否定：他努力學習，但是沒有上清華大學，也沒有上北京大學。 6解 設p：張三說真話；q：李四說真話；r：王五說真話。則：pq, qr(qr), r(pq)為真,因此p(pq)(ppq)(p(pq)pq為真。因此，p為假，q為真，所以r為假。故張三說謊，李四說真話，王五說謊。 7解 設p：甲得冠軍；q：乙得亞軍；r：丙得亞軍；s：丁得亞軍。前提：p(qr)，qp，sr，p結論：s證明 p(qr)為真，其前件p為真，所以qr為真，又qp為真，其后件p為假，所以要求q為假，所以r為

10、真。又sr為真，其后件r為假，所以要求s為假，故s為真。習題1.4 1解 設p：明天下雨；q：后天下雨。命題符號化。 設p：明天我將去北京；q：明天我將去上海。命題符號化。 2解 3證明 因為，是功能完備聯結詞集，所以，含有外的其他聯結詞的公式均可以轉換為僅含中的聯結詞的公式。又因為即含有的公式均可以轉換為僅含中的聯結詞的公式。因此，含外其他聯結詞的公式均可以轉換為僅含中的聯結詞的公式。 故是功能完備聯結詞集。 4證明 是極小功能完備集，因而只需證明中的每個聯結詞都可以用 表示，就說明是功能完備集。只有一個聯結詞，自然是極小功能完備集。事實上，p(pp)pp，pq(pq)(pq)(pq)(pq

11、)。對于證明是極小功能完備集，可類似證明。習題1.5 1解 ； 2解 即為其析取范式。即為其合取范式。即為其合取范式。p(qr)p(qr)(qr)(pqr)(pqr) 即為其析取范式。即為其合取范式。為其析取范式。即為其析取范式和合取范式。 3解 即為其主合取范式。其主析取范式為3pq。 。故其主析取范式為(0,1,2,3)=(pq)(pq)(pq)(pq)。 即為其主合取范式。其主析取范式為(2,4,5,6,7) (pqr)(pqr)(pqr)(pqr)(pqr)。 即為其主合取范式。其主析取范式為。 4解 真值表如表2-21所示, 所以其極小項是pq，極大項為pq，pq，pq。表2-21p

12、q0010011010011110其主析取范式是：pq，主合取范式為：(pq)( pq)(pq)。 真值表如表2-222所示, 所以其極小項是pq, pq, pq, 極大項為pq。表2-22pq000100011101101011111101其主析取范式是：(pq)(pq)(pq)，主合取范式為：pq。 真值表如表2-23所示，所以其極小項是pqr,pqr, pqr, pqr,pqr,表2-23pqr000100001100010100011111100001101001110001111001極大項為pqr，pqr，pqr。其主析取范式是：(pqr)(pqr)(pqr)(pqr)(pqr)，

13、主合取范式為：(pqr)(pqr)(pqr) 。 真值表如表2-24所示,所以其極小項為pqr,pqr,pqr,pqr,pqr,而極大項分為pqr，pqr，pqr.主合取范式為(pqr)(pqr)(pqr),主析取范式為(pqr)(pqr)(pqr,)(pqr)(pqr)。表2-24pqr00010001110101001111100011010111010111115解 (pq)(pq)(pq)(pq) q (pq)(pq)， 故為可滿足式。 故為重言式。(p(qr)(pq)(pr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)(p(qr)p

14、(qr)(pqr)(qr)0。 故為矛盾式。 故僅為可滿足式。6證明 右邊已經是主合取范式。而左邊主合取范式已是pq，因此，(p q)pq，證畢。右邊(p q)(pq)已經是主合取范式。pp(qq) (p q)(pq)。因此，。左邊p(qr)p(qr)pqr，而右邊(pq)rpqr，因此，。習題1.61解 設p：這里有演出；q：這里通行是困難的；r：他們按照指定時間到達。前提：pq, rq,r結論：p證明 r Prq Pq T假言推理pq P p T拒取式2證明 s Psp P p T假言推理pq Pq T假言推理證明 r P附加前提引入rq Pq T假言推理pq Pp T拒取式ps Ps T

15、假言推理rs TCP證明 p P否定結論引入pq Pq T假言推理qr Pr T假言推理rs Pr T化簡rr T合取證明 p P附加前提引入pq Pq 析取三段論rq Pr 拒取式pr CP證明 p P附加前提引入p(qr) Pqr T假言推理q P附加前提引入r T假言推理(rs)t Prst T蘊涵等價式st T析取三段論h(st) Pst h T假言易位 h T假言推理 qh TCP13. p(qh) TCP 3解 推理不正確。在到化簡時，只能對整個公式進行而不是子公式。 4解 正確。P，P附加前提引入；T析取三段論；P；T假言推理；P；T假言推理；TCP。 5解 設p：張三努力工作，

16、q：李四高興，r：王五高興，s：劉六高興 前提：p(qr)，qp，sr 結論：ps 證明：p P附加前提引入p(qr) Pqr T假言推理qp Pq T拒取式r T析取三段論sr Ps T拒取式ps TCP 6解 設：p：天下雪；q：馬路結冰；r：汽車開得快；s：馬路塞車。前提：pq，qr，rs，s結論：p證明pq Pqr Ppr 推理三段論rs Pps 推理三段論s P p 拒取式復習題1 1解 設p：3是偶數，q：中國人的母語是漢語。命題符號化。 設p：你抽煙，q：你很容易得病。命題符號化。 設p：今天是星期一，q：明天才是星期二。命題符號化。 設p：李春這個學期離散數學考了100分。q：

17、李春這個學期數據結構考了100分。命題符號化。 設p：下雪路滑，q：他遲到了。命題符號化。 設p：經一事，q：長一智。命題符號化。 設p：一朝被蛇咬，q：十年怕井繩。命題符號化。 設p：以物喜，q：以己悲。命題符號化。 2. 解 命題中的“或”是不可兼或，因此，可以直接用“”符號化；根據聯結詞的性質及其之間的轉換關系，可知命題“李春生于1979年或生于1980年”的本意是“李春生于1979年（但不能生于1980年）或生于1980年（但不能生于1979年）”，因此，也可以轉化為“”對其進行符號化。3解 設p：李剛會拳擊，q：李春會唱歌。命題符號化(pq)(pq)。而(pq)(pq)(pq)(pq

18、)(pq)pqpq因此，李剛會拳擊并且李春不會唱歌。 4解 A的極小項對應于其真值表中的成真賦值0001，0110，1000，1001，1010，1100，1101，1111。成真賦值對應二進制數轉化為十進制數就是A的極小項的下標。由此可得，A的極小項為： ；。 相應的，A的極大項對應于其真值表中的成假賦值，成假賦值對應二進制數轉化為十進制數就是A的極大項的下標。由此可得，A的極大項為： ；。 由問題得到了A的極小項和極大項，于是與A等值的主析取范式和主合取范式可以直接得到，分別為：；。 從A的主析取范式出發(fā)，進行等值演算化簡，可得析取范式的最簡形式：(pqrs)(pqrs)(pqrs)(pq

19、rs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(qrs)(pqr)(pqrs)(pqr)(pr)(pqrs)(qrs)(pqrs)(pr)(qrs)(qrs)(pqrs)(pr)(qrs)(qrs)(pqs) 5 證明 6解 公式的真值表如表2-27所示：表2-27p0011111011011110011001100010 從真值表可見，公式所在列的填入值有1也有0，故僅為可滿足式。(pq)(qp)(pq)(qp)(2,3)為其主合取范式，可見公式僅為可滿足式。 公式真值表如表2-28所示：表2-28pqr0000100111010110111110011101111101

20、111111 p(pqr)ppqr1(0,1,2,3,4,5,6,7) 從真值表可見，公式所在的列的填入值均為1，等值演算，以及求出的主析取范式均說明公式是重言式。A=(pq)(qr)(pr)真值表見習題2.2第4(4)題。(pq)(qr)(pr)(pq)(qr)(pr)(pq)(qr)pr1. 從真值表可見，公式所在的列的填入值均為1，由等值演算，以及求出的主析取范式均說明公式是重言式。7證明 p P附加前提引入p(qr) Pqr T假言推理q P附加前提引入q(rs) Prs T假言推理qs T假言三段論p(qs) TCP證明 w Puw Pu T拒取式su Ps T析取三段論rs Pr

21、T析取三段論(pq)r P(pq) T拒取式pq) T德摩根律證明 p P附加前提引入pqr Pqr T假言推理qp Pq T拒取式r T析取三段論sr Ps T拒取式ps TCP8解 pr Pp T化簡pq Pq T假言推理(qs) Pqs T德摩根律q T化簡qq T合取由得到矛盾，可見pq，(qs)，pr不能同時成立。9解 設p：小王曾經到過受害人的房間，q：小王11點以前離開，r：小王犯了謀殺罪，s：看門人看到小王。符號化：(pq)r)p(qs)s)r。形式構造推理證明前提：(pq)r，p，qs，s結論：r證明 s Pqs Pq T拒取式p Ppq T合取(pq)r P T假言推理真值

22、表技術：真值表如表2-30所示，設A=(pq)r)p(qs)s)。表2-29pqrsqspq(pq)rqsA0000110110000110011000101101110011100111010001010001010001100110010101011100011110001110101001101010101011111110111011111100010100110100011011100101011111000111由真值表可以看出：(pq)r)p(qs)s)r，所以，(pq)r)p(qs)s)r成立。等值演算方法(pq)r)p(qs)s)r(pq)r)p(qs)s)r(pq)r)p(

23、qs)r(pq)r)p(qs)r(pqr)(pqs)r1。由此可以說明(pq)r)p(qs)s)r為重言式，即(pq)r)p(qs)s)r成立。 10解 邏輯學家手指A門問旁邊的一名強盜（A）說：“這扇門是生門，他（指強盜B）將回答是，他的回答對嗎？”設：強盜A回答“對”；：強盜B回答“對”；：這扇門（A）是生門。因為，兩個強盜一個總說真話，而另一個強盜一個總說假話，因此該問題符號化為：(pq)r。(pq)r(pq)(pq)r(pqr)(pqr)邏輯學家的提問可知，r和q都為真，由公式可以看出這時p為真，即p為假。所以，當被問強盜A回答“否”，則邏輯學家開啟所指的門從容離去。當被問強盜A回答“

24、對”，則邏輯學家開啟另一扇門從容離去。第二章 謂詞邏輯習題2.1 1解 個體：離散數學；謂詞：是一門計算機基礎課程。 個體：田亮；謂詞：是一名優(yōu)秀的跳水運動員。 個體：大學生；謂詞：要好好學習計算機課程；量詞：所有。 個體：推理；謂詞：是能夠由計算機來完成的；量詞：一切。 2 解 設：x是舞蹈演員；a：小芳。命題符號化：。 設：x是一位有名的哲學家；a：蘇格拉底。命題符號化：。 設：x作完了他的作業(yè)家；a：張三。命題符號化：。 設：x身體很好；a：我。命題符號化：。 3解 選取個體域為整數集合。設：x的平方是奇數；：x是奇數。命題符號化：。 選取個體域為所有國家的集合。設：x在南半球；：x在北

25、半球。命題符號化：。 選取個體域為所有人的集合。設：x在中國居??；：x是中國人。命題符號化：選取個體域為所有人的集合。設：x是藝術家；：x是導演；：x是演員。命題符號化：$x(M(x)F(x)G(x)。 選取個體域為所有貓的集合。設M(x)：x是好貓；F(x)：x捉耗子。命題符號化：$xM(x)x(F(x)M(x)。 4解 設：x喜歡開汽車；：x喜歡騎自行車。命題符號化：。 設：x喜歡開汽車；：x喜歡騎自行車；：x是人。命題符號化：。 設：x必須學好數學。命題符號化：。 設：x必須學好數學；：x是學生。命題符號化：。 設：x的平方是質數；：x是質數。命題符號化： 。 同。 設：x的平方是質數。

26、命題符號化：。習題2.2 1解 x的轄域為P(x)Q(x)，個體變元x是約束變元。 x的轄域為P(x)$yQ(x,y)，$y的轄域為Q(x,y)，個體變元x是約束變元，個體變元y是約束變元。 x的轄域為F(x,y)，其中個體變元x是約束變元，個體變元y是自由變元；的轄域為Q(x,y)，其中個體變元x是自由變元，個體變元y是約束變元。 2解 。 。3解 (xP(x)$yQ(x)F(s,z)；$y(P(s,y)(zQ(s,z)R(s,y,v)x$rS(x,t,r)。 4解 的真值分別為：0，1，0。 的真值分別為：0，1，0。 的真值分別為：1，1，1。 的真值分別為：0，0，0。 5解 0。 1

27、。 0。 6解 設I為任意解釋，其個體域為D，若$xP(x)為真，即$xP(x)為假，則$xP(x)xP(x)為真；若$xP(x)為假，即$xP(x)為真，則就是說在個體域中不存在使得P(x)為真的個體，故xP(x)為假，即$xP(x)xP(x)為假。因此$xP(x)xP(x)僅為可滿足式。 設I為任意解釋，其個體域為D，若xA(x)為假,則xA(x)為真，就是說對于個體域中任意一個個體A(x)均為真，那么A(x)必為假，所以$x(A(x)必為假；若xA(x)為真，即xA(x)為假，則就是說對于個體域中至少存在一個體使A(x)均為假，那么對于個體域中至少存在一個個體使A(x)為真，所以$x(A

28、(x)必為真，總之xA(x)$x(A(x)對于個體域中任意一個個體必為真，即其為邏輯有效式。設I為任意解釋，其個體域為D，若$x(P(x)Q(x)為真，即是說在個體域中至少存在一個個體使得P(x)和Q(x)同時為真，此時$x(P(x)Q(x)可真可假，所以，$x(P(x)Q(x)$x(P(x)Q(x)可真可假。因此，僅為可滿足式。習題2.31解 ($xA(x)xB(x)($xA(x)xB(x)$xA(x)xB(x)$xA(x)$xB(x)xA(x)B(x)$xC(x)$xA(x)B(x)xC(x) ($xA(x)$xB(x)(xA(x)xB(x)$xC(x)。2證明 x(P(x)Q(x)($x

29、P(x)$xQ(x)x(P(x)Q(x)($xP(x)$xQ(x)$x(P(x)Q(x)xP(x)$xQ(x)(P(1)Q(1)(P(2)Q(2)(P(3)Q(3)(P(1)P(2)P(3)Q(1)Q(2)Q(3)(P(1)Q(1)(P(2)Q(2)(P(3)Q(3)(P(1)P(2)P(3)(P(1)P(2)P(3)(Q(1)Q(2)Q(3)(P(1)P(2)P(3)1。故x(P(x)Q(x)($xP(x)$xQ(x)為邏輯有效式。($xP(x)xQ(x)x(P(x)Q(x)($xP(x)xQ(x)x(P(x)Q(x)($xP(x)$xQ(x)x(P(x)Q(x)(P(1)P(2)P(3)(

30、Q(1)Q(2)Q(3)(P(1)Q(1)P(2)Q(2)P(2)Q(2)(P(1)Q(1)(P(2)Q(2)(P(3)Q(3)(P(1)Q(2)(P(1)Q(1)(P(2)Q(2)(P(1)Q(1)(P(1)Q(1)(P(1)Q(1)(P(2)Q(2)(P(3)Q(3)(P(1)Q(2)(P(2)Q(2)(P(1)Q(1)(P(2)Q(2)(P(3)Q(3)(P(1)Q(2)(P(1)Q(1)(P(1)Q(1)(P(2)Q(2)(P(3)Q(3)(P(1)Q(2)111。 習題2.4 1解 錯。在一個邏輯推理過程中，若同時用到ES和US，并且選用代替的個體變元相同時應先用ES，再用US。 錯

31、，在用UG規(guī)則時，引入的個體變元在原來的公式中不能自由出現過。錯。 錯，在用兩次ES規(guī)則時，引入的個體常元不能是一樣的。2證明 xQ(x) PQ(y) TUSx(P(x)Q(x) PP(y)Q(y) TUSP(y) T拒取式$xP(x) TEG證明 xP(x) P附加前提引入P(c) TUSx(P(x)Q(x) PP(c)Q(c) TUSQ(c) T假言推理xQ(x) TUGxP(x)xQ(x) TCP證明 x(P(x)Q(x) P$x(P(x)Q(x) T量詞否定，德摩根律P(c)Q(c) TESxQ(x) P否定結論引入Q(c) TUSQ(c) T化簡Q(c)Q(c) T合取 由得到矛盾，由間接證明原理，原命題得證明。 3 解 設M(x)：x是鳥；N(x)：x是猴子，F(x)：x會飛。 前提：x(M(x)F(x)，x(N(x)F(x) 結論：x(N(x)M(x)證明 x(N(x)F(x) PN(y)F(y) TUSx(M(x)F(x) PM(y)F(y) TUSF(y)M(y)