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

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

2、。命題符號(hào)化為：p。 3解 如果李春遲到了，那么他錯(cuò)過(guò)考試。 要么李春遲到了，要么李春錯(cuò)過(guò)了考試，要么李春通過(guò)了考試。 李春錯(cuò)過(guò)考試當(dāng)且僅當(dāng)他遲到了。 如果李春遲到了并且錯(cuò)過(guò)了考試，那么他沒(méi)有通過(guò)考試。4解 p(qr)。pq。qp。q p。習(xí)題1.2 1解 是1層公式。 不是公式。 一層： pq，p 二層：pq所以，是3層公式。 不是公式。 (pq)(q( qr)是5層公式，這是因?yàn)?一層：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)為可滿(mǎn)足式。 設(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所示，所以公式僅為可滿(mǎn)足式。表2-19001011011101100100110100 真值表如表2-20所示，

8、所以公式是重言式。表2-20pqr pqrqpr(pq)(rq)(pr)qA000110111001100011010110111011110111100010011101001001110110111111111111 5解 設(shè)p：他努力學(xué)習(xí)；q：他會(huì)通過(guò)考試。則命題符號(hào)化pq。其否定(pq) pq。 所以語(yǔ)句的否定：他學(xué)習(xí)很努力但沒(méi)有通過(guò)考試。 設(shè)p：水溫暖；q：他游泳。則命題符號(hào)化pq。其否定(pq) pq。 所以語(yǔ)句的否定：當(dāng)且僅當(dāng)水不溫暖時(shí)他游泳。 設(shè)p：天冷；q：他穿外套；r：他穿襯衫。則命題符號(hào)化p(qr) 其否定( p(qr) (p(qr) p( qr) p(q r) 所以語(yǔ)句

9、的否定：天冷并且他不穿外套或者穿襯衫。 設(shè)p：他學(xué)習(xí)；q：他將上清華大學(xué)；r：他將上北京大學(xué)。則命題符號(hào)化其否定所以語(yǔ)句的否定：他努力學(xué)習(xí)，但是沒(méi)有上清華大學(xué)，也沒(méi)有上北京大學(xué)。 6解 設(shè)p：張三說(shuō)真話(huà)；q：李四說(shuō)真話(huà)；r：王五說(shuō)真話(huà)。則：pq, qr(qr), r(pq)為真,因此p(pq)(ppq)(p(pq)pq為真。因此，p為假，q為真，所以r為假。故張三說(shuō)謊，李四說(shuō)真話(huà)，王五說(shuō)謊。 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：后天下雨。命題符號(hào)化。 設(shè)p：明天我將去北京；q：明天我將去上海。命題符號(hào)化。 2解 3證明 因?yàn)?，是功能完備?lián)結(jié)詞集，所以，含有外的其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含中的聯(lián)結(jié)詞的公式。又因?yàn)榧春械墓骄梢赞D(zhuǎn)換為僅含中的聯(lián)結(jié)詞的公式。因此，含外其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含中的聯(lián)結(jié)詞的公式。 故是功能完備聯(lián)結(jié)詞集。 4證明 是極小功能完備集，因而只需證明中的每個(gè)聯(lián)結(jié)詞都可以用 表示，就說(shuō)明是功能完備集。只有一個(gè)聯(lián)結(jié)詞，自然是極小功能完備集。事實(shí)上，p(pp)pp，pq(pq)(pq)(pq)(pq

11、)。對(duì)于證明是極小功能完備集，可類(lèi)似證明。習(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所示, 所以其極小項(xiàng)是pq，極大項(xiàng)為pq，pq，pq。表2-21p

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

13、主合取范式為：(pqr)(pqr)(pqr) 。 真值表如表2-24所示,所以其極小項(xiàng)為pqr,pqr,pqr,pqr,pqr,而極大項(xiàng)分為pqr，pqr，pqr.主合取范式為(pqr)(pqr)(pqr),主析取范式為(pqr)(pqr)(pqr,)(pqr)(pqr)。表2-24pqr00010001110101001111100011010111010111115解 (pq)(pq)(pq)(pq) q (pq)(pq)， 故為可滿(mǎn)足式。 故為重言式。(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。 故為矛盾式。 故僅為可滿(mǎn)足式。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：他們按照指定時(shí)間到達(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化簡(jiǎn)rr T合取證明 p P附加前提引入pq Pq 析取三段論rq Pr 拒取式pr CP證明 p P附加前提引入p(qr) Pqr T假言推理q P附加前提引入r T假言推理(rs)t Prst T蘊(yùn)涵等價(jià)式st T析取三段論h(st) Pst h T假言易位 h T假言推理 qh TCP13. p(qh) TCP 3解 推理不正確。在到化簡(jiǎn)時(shí)，只能對(duì)整個(gè)公式進(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：汽車(chē)開(kāi)得快；s：馬路塞車(chē)。前提：pq，qr，rs，s結(jié)論：p證明pq Pqr Ppr 推理三段論rs Pps 推理三段論s P p 拒取式復(fù)習(xí)題1 1解 設(shè)p：3是偶數(shù)，q：中國(guó)人的母語(yǔ)是漢語(yǔ)。命題符號(hào)化。 設(shè)p：你抽煙，q：你很容易得病。命題符號(hào)化。 設(shè)p：今天是星期一，q：明天才是星期二。命題符號(hào)化。 設(shè)p：李春這個(gè)學(xué)期離散數(shù)學(xué)考了100分。q：

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

18、)(pq)pqpq因此，李剛會(huì)拳擊并且李春不會(huì)唱歌。 4解 A的極小項(xiàng)對(duì)應(yīng)于其真值表中的成真賦值0001，0110，1000，1001，1010，1100，1101，1111。成真賦值對(duì)應(yīng)二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)就是A的極小項(xiàng)的下標(biāo)。由此可得，A的極小項(xiàng)為： ；。 相應(yīng)的，A的極大項(xiàng)對(duì)應(yīng)于其真值表中的成假賦值，成假賦值對(duì)應(yīng)二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)就是A的極大項(xiàng)的下標(biāo)。由此可得，A的極大項(xiàng)為： ；。 由問(wèn)題得到了A的極小項(xiàng)和極大項(xiàng)，于是與A等值的主析取范式和主合取范式可以直接得到，分別為：；。 從A的主析取范式出發(fā)，進(jìn)行等值演算化簡(jiǎn)，可得析取范式的最簡(jiǎ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 從真值表可見(jiàn)，公式所在列的填入值有1也有0，故僅為可滿(mǎn)足式。(pq)(qp)(pq)(qp)(2,3)為其主合取范式，可見(jiàn)公式僅為可滿(mǎn)足式。 公式真值表如表2-28所示：表2-28pqr0000100111010110111110011101111101

20、111111 p(pqr)ppqr1(0,1,2,3,4,5,6,7) 從真值表可見(jiàn)，公式所在的列的填入值均為1，等值演算，以及求出的主析取范式均說(shuō)明公式是重言式。A=(pq)(qr)(pr)真值表見(jiàn)習(xí)題2.2第4(4)題。(pq)(qr)(pr)(pq)(qr)(pr)(pq)(qr)pr1. 從真值表可見(jiàn)，公式所在的列的填入值均為1，由等值演算，以及求出的主析取范式均說(shuō)明公式是重言式。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化簡(jiǎn)pq Pq T假言推理(qs) Pqs T德摩根律q T化簡(jiǎn)qq T合取由得到矛盾，可見(jiàn)pq，(qs)，pr不能同時(shí)成立。9解 設(shè)p：小王曾經(jīng)到過(guò)受害人的房間，q：小王11點(diǎn)以前離開(kāi)，r：小王犯了謀殺罪，s：看門(mén)人看到小王。符號(hào)化：(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。由此可以說(shuō)明(pq)r)p(qs)s)r為重言式，即(pq)r)p(qs)s)r成立。 10解 邏輯學(xué)家手指A門(mén)問(wèn)旁邊的一名強(qiáng)盜（A）說(shuō)：“這扇門(mén)是生門(mén)，他（指強(qiáng)盜B）將回答是，他的回答對(duì)嗎？”設(shè)：強(qiáng)盜A回答“對(duì)”；：強(qiáng)盜B回答“對(duì)”；：這扇門(mén)（A）是生門(mén)。因?yàn)椋瑑蓚€(gè)強(qiáng)盜一個(gè)總說(shuō)真話(huà)，而另一個(gè)強(qiáng)盜一個(gè)總說(shuō)假話(huà)，因此該問(wèn)題符號(hào)化為：(pq)r。(pq)r(pq)(pq)r(pqr)(pqr)邏輯學(xué)家的提問(wèn)可知，r和q都為真，由公式可以看出這時(shí)p為真，即p為假。所以，當(dāng)被問(wèn)強(qiáng)盜A回答“否”，則邏輯學(xué)家開(kāi)啟所指的門(mén)從容離去。當(dāng)被問(wèn)強(qiáng)盜A回答“

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

25、半球。命題符號(hào)化：。 選取個(gè)體域?yàn)樗腥说募?。設(shè)：x在中國(guó)居?。唬簒是中國(guó)人。命題符號(hào)化：選取個(gè)體域?yàn)樗腥说募?。設(shè)：x是藝術(shù)家；：x是導(dǎo)演；：x是演員。命題符號(hào)化：$x(M(x)F(x)G(x)。 選取個(gè)體域?yàn)樗胸埖募稀ＴO(shè)M(x)：x是好貓；F(x)：x捉耗子。命題符號(hào)化：$xM(x)x(F(x)M(x)。 4解 設(shè)：x喜歡開(kāi)汽車(chē)；：x喜歡騎自行車(chē)。命題符號(hào)化：。 設(shè)：x喜歡開(kāi)汽車(chē)；：x喜歡騎自行車(chē)；：x是人。命題符號(hào)化：。 設(shè)：x必須學(xué)好數(shù)學(xué)。命題符號(hào)化：。 設(shè)：x必須學(xué)好數(shù)學(xué)；：x是學(xué)生。命題符號(hào)化：。 設(shè)：x的平方是質(zhì)數(shù)；：x是質(zhì)數(shù)。命題符號(hào)化： 。 同。 設(shè)：x的平方是質(zhì)數(shù)。

26、命題符號(hào)化：。習(xí)題2.2 1解 x的轄域?yàn)镻(x)Q(x)，個(gè)體變?cè)獂是約束變?cè)?x的轄域?yàn)镻(x)$yQ(x,y)，$y的轄域?yàn)镼(x,y)，個(gè)體變?cè)獂是約束變?cè)?，個(gè)體變?cè)獃是約束變?cè)?x的轄域?yàn)镕(x,y)，其中個(gè)體變?cè)獂是約束變?cè)?，個(gè)體變?cè)獃是自由變?cè)坏妮犛驗(yàn)镼(x,y)，其中個(gè)體變?cè)獂是自由變?cè)瑐€(gè)體變?cè)獃是約束變?cè)?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為任意解釋?zhuān)鋫€(gè)體域?yàn)镈，若$xP(x)為真，即$xP(x)為假，則$xP(x)xP(x)為真；若$xP(x)為假，即$xP(x)為真，則就是說(shuō)在個(gè)體域中不存在使得P(x)為真的個(gè)體，故xP(x)為假，即$xP(x)xP(x)為假。因此$xP(x)xP(x)僅為可滿(mǎn)足式。 設(shè)I為任意解釋?zhuān)鋫€(gè)體域?yàn)镈，若xA(x)為假,則xA(x)為真，就是說(shuō)對(duì)于個(gè)體域中任意一個(gè)個(gè)體A(x)均為真，那么A(x)必為假，所以$x(A(x)必為假；若xA(x)為真，即xA(x)為假，則就是說(shuō)對(duì)于個(gè)體域中至少存在一個(gè)體使A(x)均為假，那么對(duì)于個(gè)體域中至少存在一個(gè)個(gè)體使A(x)為真，所以$x(A

28、(x)必為真，總之xA(x)$x(A(x)對(duì)于個(gè)體域中任意一個(gè)個(gè)體必為真，即其為邏輯有效式。設(shè)I為任意解釋?zhuān)鋫€(gè)體域?yàn)镈，若$x(P(x)Q(x)為真，即是說(shuō)在個(gè)體域中至少存在一個(gè)個(gè)體使得P(x)和Q(x)同時(shí)為真，此時(shí)$x(P(x)Q(x)可真可假，所以，$x(P(x)Q(x)$x(P(x)Q(x)可真可假。因此，僅為可滿(mǎn)足式。習(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解 錯(cuò)。在一個(gè)邏輯推理過(guò)程中，若同時(shí)用到ES和US，并且選用代替的個(gè)體變?cè)嗤瑫r(shí)應(yīng)先用ES，再用US。 錯(cuò)

31、，在用UG規(guī)則時(shí)，引入的個(gè)體變?cè)谠瓉?lái)的公式中不能自由出現(xiàn)過(guò)。錯(cuò)。 錯(cuò)，在用兩次ES規(guī)則時(shí)，引入的個(gè)體常元不能是一樣的。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化簡(jiǎn)Q(c)Q(c) T合取 由得到矛盾，由間接證明原理，原命題得證明。 3 解 設(shè)M(x)：x是鳥(niǎo)；N(x)：x是猴子，F(xiàn)(x)：x會(huì)飛。 前提：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)