離散數(shù)學(xué)課后習(xí)題答案(邱學(xué)紹).doc

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

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

2、。命題符號化為：p。 3解 如果李春遲到了，那么他錯過考試。 要么李春遲到了，要么李春錯過了考試，要么李春通過了考試。 李春錯過考試當(dāng)且僅當(dāng)他遲到了。 如果李春遲到了并且錯過了考試，那么他沒有通過考試。4解 p(qr)。pq。qp。q p。習(xí)題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解 設(shè)，其真值表如表2-8所示：表2-8pq00011010111001111101故為重言式。 設(shè)A=(pq)(pq)，其真值表如表2-9所示：表2-9pqpqpq(pq)A000010010100100100111100故A=(pq)(pq)為矛盾式。 設(shè)A=(pq)(pq)，其真值表如表2-10所示：表2-10pq001010011111100100110010故A=(pq)(pq)為可滿足式。 設(shè)，其真值表如表2-11所示：表2-11pqr000111110011111101010011011111111

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

6、r 00011010011101010010101111011001101101110111000101111111表2-15 由真值表可以看出p(qr)和(pq)r所在的列相應(yīng)填入值相同，故等值。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解 與習(xí)題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解 設(shè)p：他努力學(xué)習(xí)；q：他會通過考試。則命題符號化pq。其否定(pq) pq。 所以語句的否定：他學(xué)習(xí)很努力但沒有通過考試。 設(shè)p：水溫暖；q：他游泳。則命題符號化pq。其否定(pq) pq。 所以語句的否定：當(dāng)且僅當(dāng)水不溫暖時他游泳。 設(shè)p：天冷；q：他穿外套；r：他穿襯衫。則命題符號化p(qr) 其否定( p(qr) (p(qr) p( qr) p(q r) 所以語句

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

10、真。又sr為真，其后件r為假，所以要求s為假，故s為真。習(xí)題1.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(pp)pp，pq(pq)(pq)(pq)(pq

11、)。對于證明是極小功能完備集，可類似證明。習(xí)題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證明 右邊已經(jīng)是主合取范式。而左邊主合取范式已是pq，因此，(p q)pq，證畢。右邊(p q)(pq)已經(jīng)是主合取范式。pp(qq) (p q)(pq)。因此，。左邊p(qr)p(qr)pqr，而右邊(pq)rpqr，因此，。習(xí)題1.61解 設(shè)p：這里有演出；q：這里通行是困難的；r：他們按照指定時間到達(dá)。前提：pq, rq,r結(jié)論：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否定結(jié)論引入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解 推理不正確。在到化簡時，只能對整個公式進(jìn)行而不是子公式。 4解 正確。P，P附加前提引入；T析取三段論；P；T假言推理；P；T假言推理；TCP。 5解 設(shè)p：張三努力工作，

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

17、李春這個學(xué)期數(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年（但不能生于1980年）或生于1980年（但不能生于1979年）”，因此，也可以轉(zhuǎn)化為“”對其進(jìn)行符號化。3解 設(shè)p：李剛會拳擊，q：李春會唱歌。命題符號化(pq)(pq)。而(pq)(pq)(pq)(pq

18、)(pq)pqpq因此，李剛會拳擊并且李春不會唱歌。 4解 A的極小項對應(yīng)于其真值表中的成真賦值0001，0110，1000，1001，1010，1100，1101，1111。成真賦值對應(yīng)二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)就是A的極小項的下標(biāo)。由此可得，A的極小項為： ；。 相應(yīng)的，A的極大項對應(yīng)于其真值表中的成假賦值，成假賦值對應(yīng)二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)就是A的極大項的下標(biāo)。由此可得，A的極大項為： ；。 由問題得到了A的極小項和極大項，于是與A等值的主析取范式和主合取范式可以直接得到，分別為：；。 從A的主析取范式出發(fā)，進(jìn)行等值演算化簡，可得析取范式的最簡形式：(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)真值表見習(xí)題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解 設(shè)p：小王曾經(jīng)到過受害人的房間，q：小王11點以前離開，r：小王犯了謀殺罪，s：看門人看到小王。符號化：(pq)r)p(qs)s)r。形式構(gòu)造推理證明前提：(pq)r，p，qs，s結(jié)論：r證明 s Pqs Pq T拒取式p Ppq T合取(pq)r P T假言推理真值

22、表技術(shù)：真值表如表2-30所示，設(shè)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解 邏輯學(xué)家手指A門問旁邊的一名強(qiáng)盜（A）說：“這扇門是生門，他（指強(qiáng)盜B）將回答是，他的回答對嗎？”設(shè)：強(qiáng)盜A回答“對”；：強(qiáng)盜B回答“對”；：這扇門（A）是生門。因為，兩個強(qiáng)盜一個總說真話，而另一個強(qiáng)盜一個總說假話，因此該問題符號化為：(pq)r。(pq)r(pq)(pq)r(pqr)(pqr)邏輯學(xué)家的提問可知，r和q都為真，由公式可以看出這時p為真，即p為假。所以，當(dāng)被問強(qiáng)盜A回答“否”，則邏輯學(xué)家開啟所指的門從容離去。當(dāng)被問強(qiáng)盜A回答“

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

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

26、命題符號化：。習(xí)題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解 設(shè)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)僅為可滿足式。 設(shè)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)對于個體域中任意一個個體必為真，即其為邏輯有效式。設(shè)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)可真可假。因此，僅為可滿足式。習(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。 習(xí)題2.4 1解 錯。在一個邏輯推理過程中，若同時用到ES和US，并且選用代替的個體變元相同時應(yīng)先用ES，再用US。 錯

31、，在用UG規(guī)則時，引入的個體變元在原來的公式中不能自由出現(xiàn)過。錯。 錯，在用兩次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否定結(jié)論引入Q(c) TUSQ(c) T化簡Q(c)Q(c) T合取 由得到矛盾，由間接證明原理，原命題得證明。 3 解 設(shè)M(x)：x是鳥；N(x)：x是猴子，F(xiàn)(x)：x會飛。 前提：x(M(x)F(x)，x(N(x)F(x) 結(jié)論：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)