離散數(shù)學(xué) 第5章 推理與證明技術(shù)

離散數(shù)學(xué)06二月2023電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院2023/2/6第5章推理與證明技術(shù)數(shù)學(xué)歸納法的使用

3CP規(guī)則相關(guān)證明4命題邏輯的推理理論

1謂詞邏輯的推理理論

22023/2/61.1本章學(xué)習(xí)要求1掌握各種不同類(lèi)型的規(guī)則和公理，特別是命題邏輯和謂詞邏輯的推理規(guī)則和公理3理解謂詞邏輯的精髓，將其思想貫穿于所有的證明之中

2熟練掌握不同證明方法的證明原理、不同的應(yīng)用場(chǎng)景

重點(diǎn)掌握一般掌握了解2023/2/65.2命題邏輯的推理理論概念描述問(wèn)題的句子AddYourTexT判斷對(duì)概念的肯定與否定的判斷推理從一個(gè)或多個(gè)前提推出結(jié)論的思維過(guò)程認(rèn)識(shí)世界的漸進(jìn)過(guò)程2023/2/6推理的有效性和結(jié)論的真實(shí)性有效的推理不一定產(chǎn)生真實(shí)的結(jié)論；而產(chǎn)生真實(shí)結(jié)論的推理過(guò)程未必是有效的。有效的推理中可能包含為“假”的前提，而無(wú)效的推理卻可能得到為“真”的結(jié)論。所謂推理有效，指的是它的結(jié)論是它前提的合乎邏輯的結(jié)果。也即，如果它的前提都為真，那么所得的結(jié)論也必然為真，而并不是要求前提或結(jié)論一定為真或?yàn)榧?，如果推理是有效的話，那么不可能它的前提都為真時(shí)，而它的結(jié)論為假。2023/2/65.2.1推理的基本概念和推理形式定義5.2.0設(shè)G,H是公式，對(duì)任意解釋I，如果I滿足G，那么I滿足H，則稱(chēng)H是G的邏輯結(jié)果(或稱(chēng)G蘊(yùn)涵H),記為GＨ，此時(shí)稱(chēng)G為前提，H為結(jié)論。2023/2/6判定定理定理5.2.0設(shè)G,H是公式，H是G的邏輯結(jié)果當(dāng)且僅當(dāng)G→Ｈ為永真公式。證明：“”若GＨ，但G→H不是永真公式。于是，必存在一個(gè)解釋I，使得G→H為假，即在解釋I下，G為真，而H為假，這與GＨ矛盾，故G→H是永真公式。“”若G→H是永真式，但GＨ不成立，故存在G,H的一個(gè)解釋I，使得G為真，而H為假，從而在解釋I下，G→H為假，這與G→H是永真公式矛盾，所以GＨ。2023/2/6推廣定義5.2.1設(shè)G1,G2,…,Gn,H是公式，稱(chēng)H是G1,G2,…,Gn的邏輯結(jié)果(G1,G2,…,Gn共同蘊(yùn)涵H),當(dāng)且僅當(dāng)H是G1∧G2∧…∧Gn的邏輯結(jié)果(logicconclusion)。記為G1,G2,…,GnＨ，此時(shí)稱(chēng)G1,G2,…,GnＨ為有效的(efficacious),否則稱(chēng)為無(wú)效的(inefficacious)。G1,G2,…,Gn稱(chēng)為一組前提(Premise),有時(shí)用集合Г來(lái)表示，記Г={G1,G2,…,Gn}。H稱(chēng)為結(jié)論(conclusion)。又稱(chēng)H是前提集合Г的邏輯結(jié)果。記為ГH。2023/2/6判定定理定理5.2.1

公式H是前提集合Г={G1,G2,…,Gn}的邏輯結(jié)果當(dāng)且僅當(dāng)G1∧G2∧…∧Gn→Ｈ為永真公式。證明：略。2023/2/6“”與“→”的不同1.“→”僅是一般的蘊(yùn)涵聯(lián)結(jié)詞，G→H的結(jié)果仍是一個(gè)公式，而“”卻描述了兩個(gè)公式G，H之間的一種邏輯蘊(yùn)涵關(guān)系，GH的“結(jié)果”，是非命題公式；2.

用計(jì)算機(jī)來(lái)判斷GH是辦不到的。然而計(jì)算機(jī)卻可“計(jì)算”公式G→H是否為永真公式。2023/2/65.2.2判斷有效結(jié)論的常用方法要求Г=｛G1,G2,…,Gn｝Г

H也就是G1∧G2∧…∧Gn→Ｈ為永真公式因而真值表技術(shù)、演繹法和間接證明方法2023/2/61、真值表技術(shù)設(shè)P1,P2,…,Pn是出現(xiàn)在前提G1,G2,…,Gn和結(jié)論H中的一切命題變?cè)?，如果將P1,P2,…,Pn中所有可能的解釋及G1,G2,…,Gn，H的對(duì)應(yīng)真值結(jié)果都列在一個(gè)表中，根據(jù)“→”的定義，則有判斷方法如下：對(duì)所有G1,G2,…,Gn都具有真值T的行(表示前提為真的行),如果在每一個(gè)這樣的行中，H也具有真值T，則H是G1,G2,…,Gn的邏輯結(jié)果。對(duì)所有H具有真值為F的行(表示結(jié)論為假的行),如果在每一個(gè)這樣的行中，G1,G2,…,Gn中至少有一個(gè)公式的真值為F(前提也為假),則H是G1,G2,…,Gn的邏輯結(jié)果。2023/2/6例5.2.1判斷下列H是否是前提G1,G2的邏輯結(jié)果(1)

H：Q； G1：P；G2：P→Q；(2)

H：┐P； G1：P→Q；G2：┐Q；(3)

H：Q； G1：┐P；G2：P→Q。解PQG1G2H00010010111010011111(1)PQG1G2H00111011011001011100(2)PQG1G2H00110011111000011011(3)是是否2023/2/62推理定律設(shè)G，H，I，J是任意的命題公式，則有：I1：G∧HG

(簡(jiǎn)化規(guī)則)I2：G∧HHI3：GG∨H

(添加規(guī)則)I4：HG∨HI5：┐GG→HI6：HG→HI7：┐(G→H)GI8：┐(G→H)┐HI9：G，HG∧H2023/2/62推理定律(續(xù))I10：┐G，G∨HH

(選言三段論)I11：┐G，GHH

I12：G，G→HH

(分離規(guī)則)I13：┐H，G→H┐G

(否定后件式)I14：G→H，H→IG→I

(假言三段論)I15：G∨H，G→I，H→II

(二難推論)2023/2/6例子1)、前提：

1.如果明天天晴，我們準(zhǔn)備外出旅游。

P→Q

2．明天的確天晴。

P

結(jié)論：我們外出旅游。

Q可描述為：P→Q，PQ

(分離規(guī)則)2)、前提：

1.如果一個(gè)人是單身漢，則他不幸福。

P→Q2.如果一個(gè)人不幸福，則他死得早。

Q→R

結(jié)論：?jiǎn)紊頋h死得早。

P→R可描述為：P→Q，Q→RP→R

(假言三段論)2023/2/6例子(續(xù)1)3)、某女子在某日晚歸家途中被殺害，據(jù)多方調(diào)查確證，兇手必為王某或陳某，但后又查證，作案之晚王某在工廠值夜班，沒(méi)有外出，根據(jù)上述案情可得前提：1.兇手為王某或陳某。

P∨Q2.如果王某是兇手，則他在作案當(dāng)晚必外出P→R3.王某案發(fā)之晚并未外出。

┐R結(jié)論：陳某是兇手。

Q則可描述為：P→R，┐R┐P

(否定后件式)

P∨Q，┐PQ

(選言三段論)2023/2/6例子(續(xù)2)4)、前提：1.如果某同學(xué)為省二級(jí)以上運(yùn)動(dòng)員，則他將被大學(xué)錄取。

P→R2.如果某同學(xué)高考總分在560分以上，則將被大學(xué)錄取。

Q→R3.某同學(xué)高考總分在560分以上或者是省二級(jí)運(yùn)動(dòng)員。

P∨Q結(jié)論：該同學(xué)被大學(xué)錄取。

R則上述例子可描述為：

P∨Q，P→R，Q→RR

(二難推論)2023/2/63演繹法

演繹法是從前提(假設(shè))出發(fā)，依據(jù)公認(rèn)的推理規(guī)則和推理定律，推導(dǎo)出一個(gè)結(jié)論來(lái)。YN觸發(fā)規(guī)則新事實(shí)事實(shí)=結(jié)論？事實(shí)庫(kù)規(guī)則匹配公理庫(kù)將事實(shí)加入到事實(shí)庫(kù)中結(jié)束引入事實(shí)2023/2/6演繹的定義定義5.2.2

從前提集合Г推出結(jié)論H的一個(gè)演繹是構(gòu)造命題公式的一個(gè)有限序列：

H1，H2，……，Hn其中，Hi或者是Г中的某個(gè)前提，或者是前面的某些Hj（j<i）的有效結(jié)論，并且Hn就是H，則稱(chēng)公式H為該演繹的有效結(jié)論，或者稱(chēng)從前提Г能夠演繹出結(jié)論H來(lái)。2023/2/6推理規(guī)則規(guī)則P（稱(chēng)為前提引用規(guī)則）：在推導(dǎo)的過(guò)程中，可隨時(shí)引入前提集合中的任意一個(gè)前提；規(guī)則T（邏輯結(jié)果引用規(guī)則）：在推導(dǎo)的過(guò)程中，可以隨時(shí)引入公式S，該公式S是由其前的一個(gè)或多個(gè)公式推導(dǎo)出來(lái)的邏輯結(jié)果。規(guī)則CP（附加前提規(guī)則）：如果能從給定的前提集合Г與公式P推導(dǎo)出S，則能從此前提集合Г推導(dǎo)出P→S。P→(Ｑ→Ｒ)＝(P∧Ｑ)→Ｒ，P(Ｑ→Ｒ)等價(jià)于(P∧Ｑ)Ｒ2023/2/6例5.2.2證明1：⑴P∨Q

P

⑵┐P→Q

T,(1),E

⑶Q→S

P

⑷┐P→S

T,⑵,⑶,I⑸┐S→P

T,⑷,E⑹PR

P⑺(P→R)(R→P) T,⑹,E⑻P→R T,⑺,I⑼┐S→R

T,⑸,⑻,I⑽S∨R

T,⑺,E設(shè)前提Г={P∨Q，PR，Q→S}，G=S∨R。證明ГG。2023/2/6例5.31(續(xù))證明2：⑴┐S P(附加)⑵

Q→S P⑶┐Q T,⑴,⑵,I⑷

P∨Q P⑸

P T,⑶,⑷,I⑹PR

P⑺(P→R)(R→P) T,⑹,E⑻P→R T,⑺,I⑼R T,⑸,⑻,I⑽┐S→R CP,⑴,⑼⑾S∨R T,⑽,E2023/2/6例5.2.3證：⑴R

P(附加)⑵┐R∨P

P⑶P

T,⑴,⑵,I⑷P→(Q→S)

P

⑸Q→S T,⑶,⑷,I⑹Q P⑺S T,⑸,⑹,I⑻R→S CP,⑴,⑺設(shè)Г={P→(Q→S)，┐R∨P，Q}，G=R→S。證明：ГG。2023/2/64間接證明法（反證法）前面使用過(guò)的一些證明方法都是正向推理。但在數(shù)學(xué)領(lǐng)域中，經(jīng)常會(huì)遇到一些問(wèn)題，當(dāng)采用正向推理時(shí)很難從前提為真推出結(jié)論為真。PQ等價(jià)于QP，因此，為了間接地證明PQ，可以假設(shè)Q為假(Q)，然后證明P為假(P)。2023/2/6例5.2.4設(shè)n是一個(gè)整數(shù)，證明：如果n2是奇數(shù)，那么n是奇數(shù)。

證明設(shè)n是偶數(shù)，則n＝2k，這里k是一個(gè)整數(shù)。于是有：

n2＝(2k)2=4k2=2(2k2)所以n2是偶數(shù)。因而證明了若n是偶數(shù)，則n2是偶數(shù)，它是已知命題的逆否式。因此，證明了所給的命題。

2023/2/6定義5.2.3

假設(shè)G1,G2,…,Gn是一組命題公式，P1,P2,…,Pn是出現(xiàn)在中的一切命題變?cè)?，若有解釋I使G1∧G2∧…∧Gn取值為“真”，則稱(chēng)公式G1,G2,…,Gn是一致的，或者說(shuō)是相容的。

如對(duì)任意的解釋I，都有G1∧G2∧…∧Gn取值為“假”，則稱(chēng)公式G1,G2,…,Gn是不一致的。或者說(shuō)G1∧G2∧…∧Gn是一個(gè)矛盾式。

G1∧G2∧…∧Gn是矛盾式當(dāng)且僅當(dāng)G1∧G2∧…∧GnＲ∧┐Ｒ，其中，R可為任意公式，R∧┐R為一矛盾式。2023/2/6間接證明方法

將結(jié)論的否定加入到前提集合中構(gòu)成一組新的前提，然后證明這組新的前提集合是不相容的，即蘊(yùn)涵一個(gè)矛盾式。G1,G2,…,Gn,┐H

R∧┐R定理5.2.2

設(shè)命題公式集合{G1,G2,…,Gn}是一致的，于是從前提集合{G1,G2,…,Gn}出發(fā)可以邏輯地推出公式H的充要條件是從前提集合{G1,

G2,…,Gn,┐H}出發(fā)，可以邏輯地推出一個(gè)矛盾（永假）式來(lái)。2023/2/6例5.2.5證明不存在有理數(shù)P/q其平方為2，即證明是無(wú)理數(shù)。證明對(duì)某兩個(gè)整數(shù)P和q，假設(shè)(P/q)2=2成立，并且P和q沒(méi)有公因子。如果原來(lái)選擇的P、q具有公因子，則可以用與它相等的無(wú)公因子的P、q來(lái)取代它。于是P2=2q2，所以P2是偶數(shù)，這就推出P是偶數(shù)，因?yàn)橐粋€(gè)奇數(shù)的平方是奇數(shù)。

因此存在某個(gè)整數(shù)n使得P＝2n成立。2023/2/6例5.2.5(續(xù))因此2q2＝P2＝(2n)2=4n2，即有q2=2n2，所以q2是偶數(shù)，從而q是偶數(shù)，于是得到P和q都是偶數(shù)，故它們有一個(gè)公因子2，這與假設(shè)相矛盾。

因此結(jié)論成立。2023/2/6例5.2.6用反證法證明二難推論P(yáng)∨Q，P→R，Q→R

R證明：⑴P→R P

⑵

┐RP(附加)⑶┐P T,⑴,⑵,I⑷

Q→R P⑸┐QT,⑵,⑷,I

⑹P∨QP⑺PT,⑸,⑹,I⑻P∧┐PT,⑶,⑺,I2023/2/6三種證明方法之間的關(guān)系

G1,G2,…,Gn,┐ＨＲ∧┐Ｒ

G1,G2,…,Gn

┐Ｈ→(Ｒ∧┐Ｒ)

G1,G2,…,Gn┐┐Ｈ∨(Ｒ∧┐Ｒ)

G1,G2,…,GnＨ反證法CP規(guī)則證明法直接證明法2023/2/65.2.3命題邏輯推理的難點(diǎn)弄清楚蘊(yùn)涵式P→Q的邏輯關(guān)系及其真值，這里Q是P的必要條件。無(wú)論蘊(yùn)涵關(guān)系如何表述，都要仔細(xì)地區(qū)分出蘊(yùn)涵式的前件和后件。推理過(guò)程中推理規(guī)則、基本等值式和邏輯蘊(yùn)涵式的引用要適當(dāng)，邏輯思維要清晰。弄清楚幾種推理方法的區(qū)別與聯(lián)系，對(duì)于命題邏輯推理而言，任何一個(gè)問(wèn)題的推理，都可以采取三種推理方法中的任何一種來(lái)證明，針對(duì)不同的問(wèn)題選用不同的推理方法。一般而言，對(duì)于結(jié)論是蘊(yùn)涵式或析取式的，大多可以采取帶CP規(guī)則的直接證明方法。2023/2/65.2.4命題邏輯推理的應(yīng)用例5.2.7

符號(hào)化下面的語(yǔ)句，并用演繹法證明結(jié)論是否有效。

或者明天下午是天晴，或者是下雨；如果明天下午是天晴，則我將去看電影；如果我去看電影，我就不看書(shū)。如果我看書(shū)，則天在下雨。

設(shè)

P：明天下午天晴；R：明天下午去看電影；則上述命題可符號(hào)化為：PQ，Q：明天下午下雨；S：明天下午看書(shū)。S→Q。P→R，R→S2023/2/6證明（1）S P(附加)

（2）R→S P

（3）R

T,(1),(2),I

（4）P→R P

（5）P T,(3),(4),I

（6）PQ P（7）Q T,(4),(7),I2023/2/6分析：令P：馬會(huì)飛； R：母雞是飛鳥(niǎo)； S：烤熟的鴨子還會(huì)跑。符號(hào)化上述語(yǔ)句為：Г={ }， G=證明ГG。如果馬會(huì)飛或羊吃草，則母雞就會(huì)是飛鳥(niǎo)；如果母雞是飛鳥(niǎo)，那么烤熟的鴨子還會(huì)跑；烤熟的鴨子不會(huì)跑。所以羊不吃草。例5.2.8Q：羊吃草；P∨Q→R，R→S，┐S┐Q2023/2/6例5.2.8證明⑴┐S P⑵R→S P⑶┐R T,⑴,⑵,I⑷P∨Q→R P⑸┐(P∨Q) T,⑶,⑷,I⑹┐P∧┐Q T,⑸,E⑺┐Q T,⑹,I2023/2/6例5.2.9一個(gè)公安人員審查一件盜竊案，已知的事實(shí)如下：

A或B盜竊了x；若A盜竊了x，則作案時(shí)間不能發(fā)生在午夜前；若B證詞正確，則在午夜時(shí)屋里燈光未滅；若B證詞不正確，則作案時(shí)間發(fā)生在午夜前；午夜時(shí)屋里燈光滅了。B盜竊了x。

設(shè)P：A盜竊了x；R：作案時(shí)間發(fā)生在午夜前；T：在午夜時(shí)屋里燈光未滅。 P∨Q，Q：B盜竊了x；S：B證詞正確；則上述命題可符號(hào)化為：QP→R，S→T，S→R，T2023/2/6例5.2.9（續(xù)）證明1采用直接證明方法（反證法請(qǐng)學(xué)生完成） （1）T P （2）S→T P （3）S T,(1),(2),I （4）

S→R P （5）R T,(3),(4),I （6）P→┐R P （7）

P T,(5),(6),I （8）P∨Q P （9）Q T,(7),(8),I2023/2/65.3謂詞邏輯的推理理論5.3.1謂詞演算的演繹與推理

定義5.3.1設(shè)G1,G2,…,Gn,Ｈ是公式，稱(chēng)H是G1,G2,…,Gn的邏輯結(jié)果(G1,G2,…,Gn共同蘊(yùn)涵H)，當(dāng)且僅當(dāng)H是G1∧G2∧…∧Gn的邏輯結(jié)果(logicconclusion)。記為G1,G2,…,Gn

Ｈ，此時(shí)稱(chēng)G1,G2,…,Gn

Ｈ為有效的(efficacious)，否則稱(chēng)為無(wú)效的（inefficacious）。G1,G2,…,Gn稱(chēng)為一組前提(Premise),有時(shí)用集合Г來(lái)表示，記Г={G1,G2,…,Gn}。H稱(chēng)為結(jié)論(conclusion)。又稱(chēng)H是前提集合的邏輯結(jié)果。記為ГH。2023/2/6定理5.3.1公式H是前提集合Г={G1,G2,…,Gn}的邏輯結(jié)果當(dāng)且僅當(dāng)G1∧G2∧…∧Gn→Ｈ為有效公式。2023/2/6一、推理規(guī)律（1）I16：(x)G(x)

(x)G(x)；（2）I17：(x)G(x)∨(x)H(x)

(x)(G(x)∨H(x))；

I18：(x)(G(x)∧H(x))

(x)G(x)∧(x)H(x)；（3）I19：(x)(G(x)→H(x))

(x)G(x)→(x)H(x)；

I20：(x)(G(x)→H(x))

(x)G(x)→(x)H(x)。2023/2/6推理規(guī)律（續(xù)）（4）I21：(x)(y)G(x,y)

(y)(x)G(x,y)；

I22：(x)(y)G(x,y)

(y)(x)G(x,y)；

I23：(y)(x)G(x,y)

(x)(y)G(x,y)；

I24：(y)(x)G(x,y)

(x)(y)G(x,y)；

I25：(x)(y)G(x,y)

(y)(x)G(x,y)；

I26：(y)(x)G(x,y)

(x)(y)G(x,y)；2023/2/6量詞關(guān)系圖E38E37(x)(y)(y)(x)I22I23(y)(x)(x)(y)I24I21(x)(y)(y)(x)I25I26(y)(x)(x)(y)2023/2/6二、推理規(guī)則1、US（全稱(chēng)特指規(guī)則，Universal

SPecify）：(x)G(x)

G(y) 其中G(x)對(duì)y是自由的推廣：

(x)G(x)

G(c) 其中c為任意個(gè)體常量2、ES（存在特指規(guī)則，Existential

SPecify）：(x)G(x)

G(c) 其中c為使G(c)為真的特定個(gè)體常量；若G(x)中還有除x以外的自由變量時(shí)，則必須用這些變量的函數(shù)符號(hào)來(lái)取代。在G(x)中，x不出現(xiàn)在量詞(y)或(y)的轄域之內(nèi)。2023/2/6推理規(guī)則（續(xù)）3、UG（全稱(chēng)推廣規(guī)則，UniversalGeneralize）：G(y)

(x)G(x)其中G(y)對(duì)x是自由的且G(y)中無(wú)自由變量x4、EG（存在推廣規(guī)則，ExistentialGeneralize）：G(c)(x)G(x)其中G(c)對(duì)x是自由的且G(c)中無(wú)自由變量x推廣：

G(y)(x)G(x)其中G(y)對(duì)x是自由的且G(y)中無(wú)自由變量x2023/2/6推理規(guī)則的正確使用(1)例5.3.1

設(shè)實(shí)數(shù)集中，語(yǔ)句“不存在最大的實(shí)數(shù)”可符號(hào)化為：

(x)(y)G(x,y)。其中：G(x,y)：y>x。推導(dǎo)1：（1）(x)(y)G(x,y) P

（2）(y)G(y,y) US,(1)分析：推導(dǎo)1是錯(cuò)誤的。正確的推導(dǎo)如下：（1）(x)(y)G(x,y) P

（2）(y)G(z,y) US,(1)注意：使用US規(guī)則來(lái)消去量詞時(shí)，若選用變?cè)獃取代x，則要求在原公式中x不能出現(xiàn)在量詞(y)或(y)的轄域之內(nèi)。2023/2/6推理規(guī)則的正確使用（2）推導(dǎo)2：（1）(x)(y)G(x,y)P（2）(y)G(z,y)US,(1)（3）G(z,c)ES,(2)

分析：推導(dǎo)2是錯(cuò)誤的。正確的推導(dǎo)如下：（1）(x)(y)G(x,y)P

（2）(y)G(z,y)US,(1)（3）G(z,f(z))ES,(2)注意：使用ES規(guī)則來(lái)消去量詞時(shí)，若還有其它自由變?cè)獣r(shí)，則必須用關(guān)于自由變?cè)暮瘮?shù)符號(hào)來(lái)取代常量符號(hào).2023/2/6推理規(guī)則的正確使用（3）推導(dǎo)3：（1）(y)G(z,y)P

（2）(y)(y)G(y,y)UG,(1)分析：推導(dǎo)3是錯(cuò)誤的。正確的推導(dǎo)如下：

（1）(y)G(z,y)P（2）(z)(y)G(z,y)UG,(1)注意：使用UG規(guī)則來(lái)添加量詞時(shí)，若選用變?cè)獂取代y，則要求在原公式中y不能出現(xiàn)在量詞(x)或(x)的轄域之內(nèi)。2023/2/6推理規(guī)則的正確使用（4）推導(dǎo)4：（1）G(x,c)P

（2）(x)G(x,x)EG,(2)分析：推導(dǎo)4是錯(cuò)誤的。正確的推導(dǎo)如下：

（1）G(x,c)P（2）(y)G(x,y)EG,(2)注意：使用EG規(guī)則來(lái)添加量詞時(shí)，若選用變?cè)獂取代c，則要求在原公式中c不能出現(xiàn)在量詞(x)或(x)的轄域之內(nèi)且原公式中中無(wú)自由變量x。2023/2/6判斷（1）(x)(y)G(x,y) P（2）(y)G(z,y) US,(1)（3）G(z,c) ES,(2)（4）(x)G(x,c) UG,(3)（5）(y)

(x)G(x,y) EG,(4)2023/2/65.3.2謂詞演算的綜合推理方法推導(dǎo)過(guò)程中可以引用命題演算中的規(guī)則P和規(guī)則T

。如果結(jié)論是以蘊(yùn)涵形式(或析取形式)給出，我們還可以使用規(guī)則CP。若需消去量詞，可以引用規(guī)則US和規(guī)則ES。當(dāng)所要求的結(jié)論可能被定量時(shí)，此時(shí)可引用規(guī)則UG和規(guī)則EG將其量詞加入。2023/2/6謂詞演算的綜合推理方法（續(xù)1）證明時(shí)可采用如命題演算中的直接證明方法和間接證明方法。在推導(dǎo)過(guò)程中，對(duì)消去量詞的公式或公式中不含量詞的子公式，完全可以引用命題演算中的基本等價(jià)公式和基本蘊(yùn)涵公式。在推導(dǎo)過(guò)程中，對(duì)含有量詞的公式可以引用謂詞中的基本等價(jià)公式和基本蘊(yùn)涵公式。2023/2/6例5.3.1解：設(shè)H(x)：x是人；M(x)：x是要死的； s：蘇格拉底。 則符號(hào)化為：(x)(H(x)M(x))，H(s)M(s)證明蘇格拉底三段論：“所有的人都是要死的；蘇格拉底是人。所以蘇格拉底是要死的?！弊C明：

(1)(x)(H(x)M(x)) P (2)H(x)M(x) US,(1) (3)H(s) P (4)M(s) T,(2),(3),I證明：(1)

(x)(H(x)M(x)) P (2)

H(s)M(s) US,(1) (3)

H(s) P (4)

M(s) T,(2),(3),I(4)錯(cuò)了！2023/2/6例5.3.2證明：

(x)(P(x)Q(x))，(x)P(x)(x)Q(x)有下面的推導(dǎo)：

(1)(x)(P(x)Q(x)) P(2)P(x)Q(x) US,(1)(3)

(x)P(x) P(4)

P(c) ES,(3)(5)Q(c) T,(2),(4),I(6)(x)Q(x) EG,(5)2023/2/6例5.3.2（２)推導(dǎo)可修改為：(1)(x)(P(x)Q(x)) P(2)P(c)Q(c) US,(1)(3)

(x)P(x) P(4)

P(c) ES,(3)(5)Q(c) T,(2),(4),I(6)(x)Q(x) EG,(5)2023/2/6例5.3.2(３)請(qǐng)看推導(dǎo)：(1)

(x)P(x) P(2)

P(c) ES,(1)(3)(x)(P(x)Q(x)) P(4)P(c)Q(c) US,(3)(5)Q(c) T,(2),(4),I(6)(x)Q(x) EG,(5)正確！2023/2/6例5.3.3證明：1)(x)(P(x)∧Q(x)) P 2)P(c)∧Q(c) ES,1) 3)P(c) T,2),I 4)Q(c) T,2),I 5)(x)P(x) EG,3) 6)(x)Q(x) EG,4) 7)(x)P(x)∧(x)Q(x) T,5),6),I證明：(x)(P(x)∧Q(x))(x)P(x)∧(x)Q(x)2023/2/6例5.3.3(續(xù)1)1)(x)P(x)∧(x)Q(x) P2)(x)P(x) T,1),I3)P(c) ES,2)4)(x)Q(x) T,1),I5)Q(c) ES,4)6)P(c)∧Q(c) T,3),4),I7)(x)(P(x)∧Q(x)) EG,6)請(qǐng)看上述推論的逆推導(dǎo)：2023/2/6例5.3.3(續(xù)2)正確地推導(dǎo)： 1)(x)P(x)∧(x)Q(x) P 2)(x)P(x) T,1),I 3)P(c) ES,2) 4)(x)Q(x) T,1),I 5)Q(b) ES,4) 6)P(c)∧Q(b) T,3),4),I 7)(y)(P(c)∧Q(y)) EG,6) 8)(x)(y)(P(x)∧Q(y)) EG,7)2023/2/6例5.3.4證明(采用反證法，CP規(guī)則的方法由學(xué)生完成)： 1)((x)P(x)∨(x)Q(x)) P(附加) 2)(x)P(x)∧(x)Q(x) T,1),E 3)(x)P(x)

T,2),I 4)(x)Q(x) T,2),I 5)(x)P(x) T,3),E 6)P(c) ES,5)證明(x)(P(x)∨Q(x))(x)P(x)∨(x)Q(x)2023/2/6例5.3.47)(x)Q(x)

T,4),E8)Q(c)

US,7)9)P(c)∧Q(c)

T,6),8),I10)(P(c)∨Q(c))

T,9),E11)(x)(P(x)∨Q(x))

P12)(P(c)∨Q(c))

US,11)13)(P(c)∨Q(c))∧(P(c)∨Q(c))T,10),12)2023/2/65.3.3謂詞邏輯推理的難點(diǎn)在推導(dǎo)過(guò)程中，如既要使用規(guī)則US又要使用規(guī)則ES消去公式中的量詞，而且選用的個(gè)體是同一個(gè)符號(hào)，則必須先先使用規(guī)則ES，再使用規(guī)則US。然后再使用命題演算中的推理規(guī)則，最后使用規(guī)則UG或規(guī)則EG引入量詞，得到所要的結(jié)論。如一個(gè)變量是用規(guī)則ES消去量詞，對(duì)該變量在添加量詞時(shí)，則只能使用規(guī)則EG，而不能使用規(guī)則UG；如使用規(guī)則US消去量詞，對(duì)該變量在添加量詞時(shí)，則可使用規(guī)則EG和規(guī)則UG。2023/2/6謂詞邏輯推理的難點(diǎn)（續(xù)）如有兩個(gè)含有存在量詞的公式，當(dāng)用規(guī)則ES消去量詞時(shí)，不能選用同樣的一個(gè)常量符號(hào)來(lái)取代兩個(gè)公式中的變?cè)?，而?yīng)用不同的常量符號(hào)來(lái)取代它們。在用規(guī)則US和規(guī)則ES消去量詞、用規(guī)則UG和規(guī)則EG添加量詞時(shí)，此量詞必須位于整個(gè)公式的最前端，并且它的轄域?yàn)槠浜蟮恼麄€(gè)公式。2023/2/6謂詞邏輯推理的難點(diǎn)（續(xù)）在添加量詞(x)、(x)時(shí)，所選用的x不能在公式G(y)或G(c)中自由出現(xiàn)且G(y)或G(c)對(duì)x是自由的。在使用規(guī)則EG引入存在量詞(x)時(shí)，此x不得僅為G(c)或G(y)中的函數(shù)變?cè)Ｔ谑褂靡?guī)則UG引入全稱(chēng)量詞(x)時(shí)，此x不得為G(y)中的函數(shù)變?cè)?因該函數(shù)變?cè)坏米鳛樽杂勺冊(cè)?。在使用規(guī)則UG引入全稱(chēng)量詞(x)時(shí)，G(y)中不得出現(xiàn)在使用規(guī)則US引入y之后由規(guī)則ES引入的常量或函數(shù)。2023/2/65.3.4謂詞邏輯推理的應(yīng)用例5.3.5

每個(gè)喜歡步行的人都不喜歡坐汽車(chē)；每個(gè)人或者喜歡坐汽車(chē)或者喜歡騎自行車(chē)；有的人不喜歡騎自行車(chē)。因而有的人不喜歡步行。設(shè)：H(x)：x是人；P(x)：x喜歡坐汽車(chē)；

Q(x)：x喜歡騎自行車(chē)；R(x)：x喜歡步行。則上述語(yǔ)句可符號(hào)化為：(x)(H(x)∧R(x)→P(x))，(x)(H(x)→P(x)∨Q(x))，(x)(H(x)∧Q(x))(x)(H(x)∧R(x))2023/2/6例5.3.5證明(x)(H(x)∧Q(x)) PH(c)∧Q(c) ES,(1)H(c) T,(2),IQ(c) T,(2),I(x)(H(x)→P(x)∨Q(x)) PH(c)→P(c)∨Q(c) US,(5)P(c)∨Q(c) T,(3),(6),IP(c) T,(4),(7),I2023/2/6例5.3.5（續(xù)）(x)(H(x)∧R(x)→P(x)) PH(c)∧R(c)→P(c) US,(9)(H(c)∧R(c)) T,(8),(10),IH(c)∨R(c) T,(11),ER(c) T,(3),(12),IH(c)∧R(c) T,(3),(13),I(x)(H(x)∧R(x)) EG,(14)2023/2/6例5.3.5每個(gè)喜歡步行的人都不喜歡坐汽車(chē)；每個(gè)人或者喜歡坐汽車(chē)或者喜歡騎自行車(chē)；有的人不喜歡騎自行車(chē)。因而有的人不喜歡步行。設(shè)：個(gè)體域D＝{人}；P(x)：人x喜歡坐汽車(chē)；

Q(x)：人x喜歡騎自行車(chē)；

R(x)：人x喜歡步行。則上述語(yǔ)句可符號(hào)化為：(x)(R(x)→P(x))，(x)(P(x)∨Q(x))，(x)(Q(x))(x)(R(x))2023/2/6證明(1)(x)(Q(x)) P(2)Q(c) ES,(1)(3)(x)(P(x)∨Q(x)) P(4)P(c)∨Q(c) US,(3)(5)P(c) T,(2),(4),I(6)

(x)(R(x)→P(x)) P(7)R(c)→P(c) US,(6)(8)

R(c) T,(5),(7),I(9)

(x)R(x) EG,(8)2023/2/6例5.3.6：證明下述論斷的正確性：所有的哺乳動(dòng)物都是脊椎動(dòng)物；并非所有的哺乳動(dòng)物都是胎生動(dòng)物；故有些脊椎動(dòng)物不是胎生的。解：設(shè)謂詞如下：

P(x)：x是哺乳動(dòng)物；

Q(x)：x是脊椎動(dòng)物；

R(x)：x是胎生動(dòng)物。則有： (x)(P(x)Q(x))， (x)(Q(x)∧R(x))(x)(P(x)R(x))2023/2/6請(qǐng)看下面推導(dǎo)：1)(x)(P(x)R(x)) P2)(P(x)R(x)) US,1)3)(P(x)∨R(x)) T,2),E4)(P(x)∧R(x)) T,3),E5)P(x) T,4),I6)R(x) T,4),I7)(x)(P(x)Q(x)) P8)P(x)Q(x) US,7)9)Q(x) T,(5),(8),I10)Q(x)∧R(x) T,6),9),I11)(x)(Q(x)∧R(x)) EG,10)12)(x)(Q(x)∧R(x)) UG,10)2023/2/6證明：1)(x)(P(x)R(x)) P2)(x)(P(x)∨R(x)) T,1),E3)(P(c)∨R(c)) ES,2)4)(P(c)∧R(c)) T,3),E5)P(c) T,4),I6)R(c) T,4),I7)(x)(P(x)Q(x)) P8)P(c)Q(c) US,7)9)Q(c) T,5),8),I10)Q(c)∧R(c) T,6),9),I11)(x)(Q(x)∧R(x)) EG,10)2023/2/6例5.3.7證明下列論斷的正確性：有些學(xué)生相信所有的教師；任何一個(gè)學(xué)生都不相信騙子；所以，教師都不是騙子。解：設(shè)謂詞如下：

S(x)：x是學(xué)生

T(x)：x是教師

P(x)：x是騙子

L(x,y)：x相信y則可符號(hào)化為：

(x)(S(x)∧(y)(T(y)L(x,y))),

(x)(y)((S(x)∧P(y))L(x,y)) (x)(T(x)P(x))2023/2/6證明：1)(x)(S(x)∧(y)(T(y)L(x,y))) P2)S(c)∧(y)(T(y)L(c,y)) ES,1)3)S(c) T,2),I4)(y)(T(y)L(c,y)) T,2),I5)T(x)L(c,x) US,4)6)(x)(y)((S(x)∧P(y))L(x,y)) P7)(y)((S(c)∧P(y))L(c,y)) US,6)8)(S(c)∧P(x))L(c,x) US,7)2023/2/6證明：9)S(c)(P(x)L(c,x)) T,8),E10)P(x)L(c,x) T,3),8),E11)L(c,x)P(x) T,10),E12)T(x)P(x) T,5),11),E13)(x)(T(x)P(x)) US,12)2023/2/6例5.3.8現(xiàn)有一智力測(cè)驗(yàn)題目(水容器問(wèn)題)：設(shè)有兩個(gè)分別能盛7升與5升的水容器，開(kāi)始時(shí)兩個(gè)容器均空，允許對(duì)容器做三種操作：（1）容器倒?jié)M水，（2）將容器中的水倒光，（3）從一個(gè)容器倒水至另一容器，使一個(gè)容器倒光而另一容器倒?jié)M。最后要求能使大容器(能盛7升的容器)中有4升水，并求其操作過(guò)程。2023/2/6大容器注滿小容器倒空解決方案S(0,0)S(7,0)S(2,5)S(2,0)S(0,2)S(7,2)S(4,5)S(4,0)大容器注滿大容器倒空小容器注滿小容器注滿倒入小容器2023/2/6證明（1）S(0,0) P（2）(x)(y)(S(x,y)S(7,y)) P（3）(y)(S(0,y)S(7,y)) US,(2)（4）S(0,0)S(7,0) US,(3)（5）S(7,0) T,(1),(4).I（6）(x)(y)(z)(S(x,y)S(z,5)) P（7）(y)(z)(S(7,y)S(z,5)) US,(6)（8）(z)(S(7,0)S(z,5)) US,(7)（9）S(7,0)S(2,5) ES,(8)2023/2/6證明（10）S(2,5) T,(5),(9),I（11）(x)(y)(S(x,y)S(x,0)) P（12）(y)(S(2,y)S(2,0)) US,(11)（13）S(2,5)S(2,0) US,(12)（14）S(2,0) T,(10),(13),I（15）(x)(y)(z)(S(x,y)S(0,z)) P（16）(y)(z)(S(2,y)S(0,z)) US,(15)（17）(z)(S(2,0)S(0,z)) US,(16)2023/2/6證明（續(xù)）（18）(S(2,0)S(0,2)) ES,(17)（19）S(0,2) T,(14),(18),I（20）(x)(y)(S(x,y)S(7,y)) P（21）(y)(S(0,y)S(7,y)) US,(20)（22）(S(0,2)S(7,2)) US,(21)（23）S(7,2) T,(19),(22),I（24）(x)(y)(z)(S(x,y)S(z,5)) P（25）(y)(z)(S(7,y)S(z,5)) US,(24)（26）(z)(S(7,2)S(z,5)) US,(25)2023/2/6證明（續(xù)）（27）S(7,2)S(4,5) ES,(26)（28）S(4,5) T,(23),(27),I（29）(x)(y)(S(x,y)S(x,0)) P（30）(y)(S(4,y)S(4,0)) US,(29)（31）S(4,5)S(4,0) US,(30)（32）S(4,0) T,(30),(33),I2023/2/65.4數(shù)學(xué)歸納法5.4.1數(shù)學(xué)歸納法原理假設(shè)要證明的命題能寫(xiě)成形式:

n≥n0，有P(n)其中n0是某個(gè)固定的整數(shù)，即：希望證明對(duì)所有的整數(shù)n≥n0都有P(n)為真。2023/2/6數(shù)學(xué)歸納法原理假設(shè)

1）驗(yàn)證n＝n0，有P(n0)為真；(歸納基礎(chǔ))2）假設(shè)對(duì)于n＝k(k≥n0)，有P(k)為真；(歸納假設(shè))3）證明n＝k＋1，有P(k+1)為真。(歸納結(jié)論)結(jié)論

對(duì)所有的整數(shù)n≥n0，都有P(n)為真。謂詞表示：

(n0)(P(n0)∧(n)((n＝k)∧P(k)→P(k+1))＝1

2023/2/6強(qiáng)形式數(shù)學(xué)歸納法原理假設(shè)

1）

驗(yàn)證n＝n0、n0+1，有P(n0)、P(n0+1)為真； (歸納基礎(chǔ))2）假設(shè)對(duì)于n≤k(k≥n0)，有P(n)為真；(歸納假設(shè))3）證明n＝k＋1，有P(k+1)為真。 (歸納結(jié)論)結(jié)論

對(duì)所有的整數(shù)n≥n0，都有P(n)為真。謂詞表示：

(n0)(P(n0)∧P(n0+1)∧(n)((n≤k)∧P(n)→P(k+1))＝1

2023/2/6例5.4.1用數(shù)學(xué)歸納法證明：對(duì)所有n≥1，有1+2+3+…+n=證明

歸納基礎(chǔ)驗(yàn)證1=顯然P(1)真值為1；

歸納假設(shè)假定對(duì)于n=k(k≥1)，有P(k)為真，即有1+2+3+…+k=；2023/2/6例5.4.1證明歸納結(jié)論證明對(duì)于n＝k＋1，有P(k+1)為真1+2+3+…+k+(k+1) =+(k+1) =由數(shù)學(xué)歸納法原理得到，P(n)對(duì)所有n≥1為真。2023/2/6例5.4.2對(duì)每個(gè)正整數(shù)n≥1，能惟一地寫(xiě)成，其中Pi是素?cái)?shù)且滿足P1<P2<…<Ps。分析設(shè)P(n)：n＝；由于素?cái)?shù)一定是大于等于2的正整數(shù)，因此，n0＝2。2023/2/6例5.4.2證明

歸納基礎(chǔ)驗(yàn)證

因?yàn)?=21，3=31，所以P(2)、P(3)為真；歸納假設(shè)假定

對(duì)n≤k的所有正整數(shù)，都有P(n)為真，即n＝2023/2/6例5.4.2(續(xù))歸納結(jié)論證明對(duì)n＝k＋1，需分兩種情況討論：（1）如果n本身就是一個(gè)素?cái)?shù)，則k＋1＝(k+1)1，即P(k+1)為真；（2）如果n不是一個(gè)素?cái)?shù)，則k＋1＝lm，其中2≤l≤k，2≤m≤k，此時(shí)由歸納假設(shè)有

l＝，m＝其中，P1,P2,…,Ps是素?cái)?shù)，且是包含l、m中全部分解因子，bi、ci≥0的自然數(shù)，2023/2/6例5.4.2(續(xù))為此有

k＋1＝lm＝＝＝ 由于P1,P2,…,Ps是素?cái)?shù)，所以k+1能分解成素?cái)?shù)的積，又因?yàn)閘和m的因子分解是惟一的，所以k＋1的因子分解也是惟一的，所以P(k+1)是真的。由數(shù)學(xué)歸納法原理得到，P(n)對(duì)所有n≥1為真。2023/2/65.4.2數(shù)學(xué)歸納法應(yīng)用例5.4.3

用數(shù)學(xué)歸納法證明下列偽碼程序的計(jì)算結(jié)果是兩個(gè)正整數(shù)的最大公因子。其中偽碼程序?yàn)椋?/p>

FUNCTIONGCD(X,Y)1.WH