1、離 散 數(shù) 學(xué),電子科技大學(xué),計算機科學(xué)與工程學(xué)院 示 范 性 軟 件 學(xué) 院,2020年7月30日星期四,2020/7/30,第5章 推理與證明技術(shù),2020/7/30,5.1 本章學(xué)習(xí)要求,2020/7/30,5.2 命題邏輯的推理理論,2020/7/30,推理的有效性和結(jié)論的真實性,有效的推理不一定產(chǎn)生真實的結(jié)論； 而產(chǎn)生真實結(jié)論的推理過程未必是有效的。 有效的推理中可能包含為“假”的前提， 而無效的推理卻可能得到為“真”的結(jié)論 。,2020/7/30,推理的有效性和結(jié)論的真實性,所謂推理有效， 指的是它的結(jié)論是它的前提的合乎邏輯的結(jié)果。 即，如果它的前提都為真，那么所得的結(jié)論也必然為真

2、，而并不是要求前提或結(jié)論一定為真或為假； 如果推理是有效的話，那么不可能它的前提都為真時，而它的結(jié)論為假。,2020/7/30,5.2.1 推理的基本概念和推理形式,定義5.2.1 設(shè)G1, G2, ,Gn,是公式，稱H是G1, G2, ,Gn的邏輯結(jié)果(G1, G2, ,Gn共同蘊涵H)，當且僅當H 是G1G2Gn的邏輯結(jié)果(logic conclusion)。 記G1, G2, ,Gn ，此時稱G1, G2, ,Gn 為有效的(efficacious)，否則稱為無效的（inefficacious）。 G1, G2, ,Gn稱為一組前提(Premise)，有時用集合來表示，記 = G1, G

3、2, ,Gn。H稱為結(jié)論(conclusion)。又稱H是前提集合的邏輯結(jié)果。記為 H。,2020/7/30,判定定理,定理5.2.1 公式H是前提集合=G1, G2, , Gn的邏輯結(jié)果當且僅當G1G2Gn為永真公式。,證明：“”若G1, G2, ,Gn ，但G1G2GnH不是永真式。 于是，必存在G1, G2, ,Gn，H的一個解釋I，使得G1G2Gn為真，而H為假，因此對于該解釋I，有G1, G2, ,Gn都為真，而H為假，這就與推理形式G1, G2, ,Gn 是有效的相矛盾. 故：G1G2GnH是永真公式。,2020/7/30,判定定理（續(xù)）,“”若G1G2GnH是永真式，但G1, G

4、2, ,Gn 不是有效的推理形式， 故存在G1, G2, ,Gn, H的一個解釋I，使得G1, G2, ,Gn都為真，而H為假，故G1G2Gn為真，而H為假，即是說G1G2Gn H為假，這 就與G1G2GnH是永真式相矛盾， 所以G1, G2, ,Gn 是有效的推理形式。,2020/7/30,“”與“”的不同,1.“”僅是一般的蘊涵聯(lián)結(jié)詞，GH的結(jié)果仍是一個公式， 而“”卻描述了兩個公式G，H之間的一種邏輯蘊涵關(guān)系，G H的“結(jié)果”，是非命題公式；,2. 用計算機來判斷G H是辦不到的。 然而計算機卻可“計算”公式GH是否為永真公式。,2020/7/30,5.2.2 判斷有效結(jié)論的常用方法,2

5、020/7/30,1、真值表技術(shù),設(shè)P1,P2,Pn是出現(xiàn)在前提G1,G2,Gn和結(jié)論H中的一切命題變元， 如果將P1,P2,Pn中所有可能的解釋及G1,G2,Gn，H的對應(yīng)真值結(jié)果都列在一個表中，根據(jù)“”的定義，則有判斷方法如下：,對所有G1,G2,Gn都具有真值T的行(表示前提為真的行)，如果在每一個這樣的行中，H也具有真值T，則H是G1,G2,Gn的邏輯結(jié)果。 對所有H具有真值為F的行(表示結(jié)論為假的行),如果在每一個這樣的行中，G1,G2,Gn中至少有一個公式的真值為F(前提也為假)，則H是G1,G2,Gn的邏輯結(jié)果.,2020/7/30,例5.2.1,判斷下列H是否是前提G1,G2的

6、邏輯結(jié)果 (1)H：Q；G1：P；G2：PQ； (2)H：P； G1：PQ；G2：Q； (3)H：Q；G1：P；G2：PQ。,解,2020/7/30,2 推理定律,設(shè)G，H，I，J是任意的命題公式，則有：,I1：GH G(簡化規(guī)則) I2：GH H I3：G GH(添加規(guī)則) I4：H GH I5：G GH I6：H GH I7：(GH) G I8：(GH) H I9：G,H GH,2020/7/30,2 推理定律(續(xù)),6）I10：G, GH H (選言/析取三段論) I11：G, G H H 7）I12：G, GH H(分離規(guī)則) 8）I13：H, GH G (否定后件式) 9）I14：G

7、H, HI GI (假言三段論) 10）I15：GH, GI, HI I (二難推論),2020/7/30,例子,1)、前提： 1. 如果明天天晴，我們準備外出旅游。PQ 2明天的確天晴。P 結(jié)論：我們外出旅游。 Q 可描述為：PQ，P Q(分離規(guī)則) 2)、前提： 1.如果一個人是單身漢，則他不幸福。PQ 2.如果一個人不幸福，則他死得早。QR 結(jié)論：單身漢死得早。 PR 可描述為：PQ，QR PR(假言三段論),2020/7/30,例子(續(xù)1),3)、某人在某日晚歸家途中被殺害，據(jù)多方調(diào)查確證，兇手必為王某或陳某，但后又查證，作案之晚王某在工廠值夜班，沒有外出，根據(jù)上述案情可得： 前提：1

8、.兇手為王某或陳某。PQ 2.如果王某是兇手，則他在作案當晚必外出 PR 3.王某案發(fā)之晚并未外出。 R 結(jié)論：陳某是兇手。Q 則可描述為：PR,R P(否定后件式) PQ，P Q(選言三段論),2020/7/30,例子(續(xù)2),4)、前提： 1.如果某同學(xué)為省二級以上運動員，則他將被大學(xué)錄取。PR 2.如果某同學(xué)高考總分在560分以上，則將被大學(xué)錄取。QR 3.某同學(xué)高考總分在560分以上或者是省二級運動員。PQ 結(jié)論：該同學(xué)被大學(xué)錄取。R 則上述例子可描述為： PQ，PR，QR R(二難推論),2020/7/30,3 演繹法,演繹法是從前提(假設(shè))出發(fā)，依據(jù)公認的推理規(guī)則和推理定律，推導(dǎo)出

9、一個結(jié)論來。,引入事實,2020/7/30,引入推理規(guī)則,在數(shù)理邏輯中，主要的推理規(guī)則有： P規(guī)則（稱為前提引用規(guī)則）：在推導(dǎo)的過程中，可隨時引入前提集合中的任意一個前提； 規(guī)則（邏輯結(jié)果引用規(guī)則）：在推導(dǎo)的過程中，可以隨時引入公式S，該公式S是由其前的一個或多個公式推導(dǎo)出來的邏輯結(jié)果。 規(guī)則（附加前提規(guī)則）：如果能從給定的前提集合與公式P推導(dǎo)出S，則能從此前提集合推導(dǎo)出PS。,2020/7/30,演繹的定義,定義5.2.2 從前提集合推出結(jié)論H的一個演繹是指構(gòu)造命題公式的一個有限序列： H1，H2，Hn 其中，Hi或者是中的某個前提，或者是前面的某些Hj（ji）的有效結(jié)論，并且Hn就是H，則

10、稱公式H為該演繹的有效結(jié)論，或者稱從前提能夠演繹出結(jié)論H來。,2020/7/30,例5.2.2,證明1 PQP PQT(1) QSP PST SPT PRP (PR)(RP) PR SR T SRT(9),設(shè)前提=PQ,PR,QS,G=SR。證明G。,2020/7/30,設(shè)前提=PQ,PR,QS,G=SR。證明G。,證明2SP(附加前提) QSP QT,I PQP PT,I PR P (PR)(RP) ,E PR,I R T,I SR CP, SR T, ,E,2020/7/30,例5.2.3,證 RP(附加前提) RPP PT,I P(QS)P QST,I QP ST,I RSCP,設(shè)=P(

11、QS),RP,Q,G=RS。證明：G。,2020/7/30,4 間接證明法（反證法）,前面使用過的一些證明方法都是正向推理。但在數(shù)學(xué)領(lǐng)域中，經(jīng)常會遇到一些問題，當采用正向推理時很難從前提為真推出結(jié)論為真。,PQ等價于QP，因此，為了間接地證明PQ，可以假設(shè)Q為假(Q)，然后證明P為假(P)。,2020/7/30,例5.2.4,設(shè)n是一個整數(shù)，證明：如果n2是奇數(shù)，那么n是奇數(shù)。,證明 設(shè)n是偶數(shù)，則n2k，這里k是一個整數(shù)。于是有： n2(2k)2=4k2=2(2k2) 所以n2是偶數(shù)。 因而證明了若n是偶數(shù)，則n2是偶數(shù)，它是已知命題的逆否式。因此，證明了所給的命題。,2020/7/30,定

12、義5.2.3, 假設(shè)G1,G2,Gn是一組命題公式，P1,P2,Pn是出現(xiàn)在中的一切命題變元，I是它的任意解釋，若有解釋I使G1G2Gn取值為“真”，則稱公式G1,G2,Gn是一致的，或者說是相容的。 如對任意的解釋I，都有G1G2Gn取值為“假”,則稱公式G1,G2,Gn是不一致的。或者說G1G2Gn是一個矛盾式。,2020/7/30,定義5.2.3,G1G2Gn是矛盾式當且僅當 G1G2Gn, 其中，R可為任意公式，RR為一矛盾式。,2020/7/30,間接證明方法,將結(jié)論的否定加入到前提集合中，構(gòu)成一組新的前提，然后證明這組新的前提集合是不相容的，即蘊涵一個矛盾式。 G1,G2,Gn,H

13、 RR,定理5.2.2 設(shè)命題公式集合G1,G2,Gn是一致的，于是從前提集合出發(fā)可以邏輯地推出公式H的充要條件是從前提集合G1,G2,Gn ，H出發(fā)，可以邏輯地推出一個矛盾（永假）式來。,2020/7/30,例5.2.5,證明不存在有理數(shù)p/q其平方為2，即，證明 是無理數(shù)。,證明 對某兩個整數(shù)p和q，假設(shè)(p/q)2=2成立，并且p和q沒有公因子。如果原來選擇的p/q不是最小項，則可以用它等價的最小項形式來取代它。 于是p2=2q2，所以p2是偶數(shù)，這就推出p是偶數(shù)，因為一個奇數(shù)的平方是奇數(shù)。,2020/7/30,例5.2.5 證明（續(xù)）,因此存在某個整數(shù)n使得p2n成立。因此 2q2p2

14、(2n)2=4n2， 即有q2=2n2，所以q2是偶數(shù)，從而q是偶數(shù)，于是得到p和q都是偶數(shù)，故它們有一個公因子2，這與假設(shè)相矛盾。 因此假設(shè)一定為假。,2020/7/30,例5.2.6,用反證法證明二難推論 PQ，PR，QR R,證明 R P(附加前提) PR P P T,I QR P Q T,(1),I PQ P ,I PP ,I,2020/7/30,三種證明方法之間的關(guān)系,G1,G2,Gn, G1,G2,Gn () G1,G2,Gn() G1,G2,Gn,反證法 CP規(guī)則證明法 直接證明法,2020/7/30,5.2.3 命題邏輯推理的難點,1、弄清楚蘊涵式PQ的邏輯關(guān)系及其真值，這里Q

15、是P的必要條件。無論蘊涵關(guān)系如何表述，都要仔細地區(qū)分出蘊涵式的前件和后件。 2、推理過程中推理規(guī)則、基本等值式和邏輯蘊涵式的引用要適當，邏輯思維要清晰。,2020/7/30,5.2.3 命題邏輯推理的難點,3、弄清楚幾種推理方法的區(qū)別與聯(lián)系，對于命題邏輯推理而言，任何一個問題的推理，都可以采取三種推理方法中的任何一種來證明，針對不同的問題選用不同的推理方法。 一般而言，對于結(jié)論是蘊涵式或析取式的，大多可以采取帶CP規(guī)則的直接證明方法。,2020/7/30,5.2.4 命題邏輯推理的應(yīng)用,例5.2.7 符號化下面的語句，并用演繹法證明結(jié)論是否有效。 或者明天下午是天晴，或者是下雨；如果明天下午是

16、天晴，則我將去看電影；如果我去看電影，我就不看書。如果我看書，則天在下雨。,設(shè)P：明天下午天晴； Q：明天下午下雨； R：明天下午去看電影；S：明天下午看書。 則上述命題可符號化為： P Q，PR，RS SQ。,2020/7/30,例5.2.7 證明,P Q，PR，RS SQ。 （1）S P (附加前提) （2）RS P （3）R （1）（2） （4）PR P （5）P （3）（4） （6）P Q （7）Q （5）（6）,2020/7/30,例5.2.8,一個公安人員審查一件盜竊案，已知的事實如下： A或B盜竊了x； 若A盜竊了x，則作案時間不能發(fā)生在午夜前； 若B證詞正確，則在午夜時屋里燈光

17、未滅； 若B證詞不正確，則作案時間發(fā)生在午夜前； 午夜時屋里燈光滅了。B盜竊了x。,2020/7/30,例5.2.8 證明,設(shè) P：A盜竊了x；Q：B盜竊了x； R：作案時間發(fā)生在午夜前； S：B證詞正確； T：在午夜時屋里燈光未滅。 則上述命題可符號化為： PQ，PR，ST，SR，T Q,2020/7/30,例5.2.8 證明（續(xù)）,證明1 采用直接證明方法（反證法請自行完成） （1）T （2）ST （3）S ，（1），（2），I （4）SR （5）R ，（3），（4），I （6）PR P （7）P ，（5），（6），I （8）PQ （9）Q ，（7），（8），I,2020/7/30,證明

18、令P：馬會飛；Q：羊吃草； R：母雞是飛鳥； S：烤熟的鴨子還會跑。 符號化上述語句為：=PQR,RS,S,G=Q。證明G。,如果馬會飛或羊吃草，則母雞就會是飛鳥；如果母雞是飛鳥，那么烤熟的鴨子還會跑；烤熟的鴨子不會跑。所以羊不吃草。,例5.2.8,2020/7/30,例5.2.8 證明 （續(xù)）,S P RS P R T,I PQR P (PQ) T,I PQ T,E Q T,I,2020/7/30,5.3 謂詞邏輯的推理理論,5.3.1 謂詞演算的演繹與推理,定義5.3.1 設(shè)G1, G2, ,Gn,是公式，稱H是G1, G2, ,Gn的邏輯結(jié)果(G1, G2, ,Gn共同蘊涵H)， 當且僅

19、當H是G1G2Gn的邏輯結(jié)果(logic conclusion)。記為G1, G2, ,Gn ，此時稱G1, G2, ,Gn 為有效的，否則稱為無效的。 G1, G2, ,Gn稱為一組前提(Premise)，有時用集合來表示，記 = G1, G2, ,Gn。H稱為結(jié)論(conclusion)。又稱H是前提集合的邏輯結(jié)果。記為 H。,2020/7/30,定理5.3.1,定理5.3.1 公式H是前提集合= G1, G2, ,Gn的邏輯結(jié)果 當且僅當 G1G2Gn為有效公式。,2020/7/30,一 推理定律(對比第4章PPT，第83頁),教材P129 130 （1）I16：(x)G(x) (x)G

20、(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),2020/7/30,推理定律（續(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

21、)(x)G(x,y)； I26：(y)(x)G(x,y) (x)(y)G(x,y)；,2020/7/30,二 推理規(guī)則,1、US（全稱特指規(guī)則，Universal Specify）： (x)G(x) G(y)，其中G(x)對y是自由的 推廣： (x)G(x) G(c)，其中c為任意個體常量,2、ES（存在特指規(guī)則， Existential Specify ）： (x)G(x) G(c)，其中c為特定個體常量,2020/7/30,推理規(guī)則（續(xù)）,3、UG（全稱推廣規(guī)則， Universal Generalize ）： G(y) (x) G(x)，其中G(y)對x是自由的,4、EG（存在推廣規(guī)則，

22、 Existential Generalize ）： G(c) ( x) G(x)，其中c為特定個體常量 推廣： G(y) (x) G(x)，其中G(y)對x是自由的,2020/7/30,推理規(guī)則的正確使用(1),例5.3.1 設(shè)實數(shù)集中，語句“不存在最大的實數(shù)”可符號化為： (x)(y)G(x, y)。 其中：G(x, y)：yx。,推導(dǎo)1： （1）(x)(y)G(x, y) P （2）(y)G(y, y) US，（1）,分析：推導(dǎo)1是錯誤的。正確的推導(dǎo)如下： （1）(x)(y)G(x, y) P （2）(y)G(z, y) US，（1）,使用US規(guī)則消去量詞，“y”在公式中必須是自由的。,

23、2020/7/30,推理規(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是錯誤的。正確的推導(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ī)則消去量詞，若還有其它自由變元，則必須用關(guān)于自由變元的函數(shù)符號來取代常量符號.,2020/7/30,推理規(guī)則的正確使用（3）,推導(dǎo)3： （1）(y)G(z, y) P （2）(y)(y)G(y, y) UG，（1）,分析：推導(dǎo)3是錯誤的。正確的推導(dǎo)如下：

24、（1）(y)G(z, y) P （2）(z)(y)G(z, y) UG，（1）,注意：使用UG規(guī)則來添加量詞時， 所使用的變元符號不能與轄域內(nèi)的變元符號相同.,2020/7/30,推理規(guī)則的正確使用（4）,推導(dǎo)4： （1）G(x, c) P （2）(x)G(x, x) EG，（2）,分析：推導(dǎo)4是錯誤的。正確的推導(dǎo)如下： （1）G(x, c) P （2）(y)G(x, y) EG，（2）,注意：使用EG規(guī)則來添加量詞時，所使用的變元符號不能與轄域內(nèi)的變元符號相同.,2020/7/30,5.3.2 謂詞演算的綜合推理方法,（1）推導(dǎo)過程中可以引用命題演算中的規(guī)則P 和規(guī)則T 。 （2）如果結(jié)論是

25、以條件的形式(或析取形式)給出，我們還可以使用規(guī)則CP。 （3）若需消去量詞，可以引用規(guī)則US和規(guī)則ES。 （4）當所要求的結(jié)論可能被定量時，此時可引用規(guī)則UG和規(guī)則EG將其量詞加入。,2020/7/30,謂詞演算的綜合推理方法（續(xù)）,（5）證明時可采用如命題演算中的直接證明方法和間接證明方法。 （6）在推導(dǎo)過程中，對消去量詞的公式或公式中不含量詞的子公式，完全可以引用命題演算中的基本等價公式和基本蘊涵公式。 （7）在推導(dǎo)過程中，對含有量詞的公式可以引用謂詞中的基本等價公式和基本蘊涵公式。,2020/7/30,例5.3.1,解 設(shè)H(x)：x是人；M(x)：x是要死的；s：蘇格拉底。則符號化為

26、： (x)(H(x)M(x)，H(s) M(s),證明蘇格拉底三段論：“所有的人都是要死的；蘇格拉底是人。所以蘇格拉底是要死的?！?證明：(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,(4)錯了！,2020/7/30,例5.3.1,解 設(shè)H(x)：x是人；M(x)：x是要死的；s：蘇格拉底。則符號化為： (x)(H(x)M(x)，H(s) M(s),證明蘇格拉底三段論：“所有的人都是要死的；蘇格拉底是人。所以蘇格拉底是要死的。”,正確證明：(1)(x)(H(x)M(x)P (2)H(s)M(s)US,(1)

27、 (3)H(s)P (4)M(s)T,(2),(3)，I,2020/7/30,例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),(4)中的“c”未必能保證令(2)為真，推導(dǎo)錯誤！,2020/7/30,例5.3.2（),推導(dǎo)可修改為（正確與否？）： (1) (x)(P(x)Q(x) P (2) (P(c)Q(c)US,(1

28、) (3) (x)P(x)P (4) P(c)ES,(3) (5) Q(c)T,(2),(4),I (6) (x)Q(x)EG,(5),證明： (x)(P(x)Q(x)，(x)P(x)(x)Q(x),(2)中的“c”未必能保證令(4)為真，推導(dǎo)錯誤！,2020/7/30,例5.3.2(),正確推導(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),證明： (x)(P(x)Q(x)，(x)P(x)(x)Q(x),2020/7/30,

29、例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),2020/7/30,例5.3.3(續(xù)1),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(c)ES,4) 6) (P(c)Q(c) T,3),4),I 7) (x)(P(x)Q(x)EG,6)

30、,請看上述推論的逆推導(dǎo)（正確與否？） ：,證明： (x)(P(x)Q(x)(x)P(x)(x)Q(x),“c”未必能保證同時令(2)和(4)為真，推導(dǎo)錯誤！,2020/7/30,例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)(x)(y)(P(x)Q(y)EG,6),(x)(P(x)Q(x)(x)P(x)(x)Q(x) 的逆推導(dǎo)：,2020/7/30,例5.3.4,證明(采用反證法，CP規(guī)則的方法自己完成)： 1)

31、(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),2020/7/30,例5.3.4 證明（續(xù)）,6) P(c) ES,5) 7) (x)Q(x) T,4),E 8) Q(c) US,7) 9) P(c)Q(c) T,6),8),I 10)(P(c)Q(c) T,9),E 11)(x)(P(x)Q(x) P 12)(P(c)Q(c) US,11) 13) (P(c)Q

32、(c)(P(c)Q(c) T,10),12),證明(x)(P(x)Q(x) (x)P(x)(x)Q(x),2020/7/30,5.3.3 謂詞邏輯推理的難點,（1）在推導(dǎo)過程中，如既要使用規(guī)則US又要使用規(guī)則ES消去公式中的量詞，而且選用的個體是同一個符號，則必須先使用規(guī)則ES，再使用規(guī)則US。 然后再使用命題演算中的推理規(guī)則，最后使用規(guī)則UG或規(guī)則EG引入量詞，得到所要的結(jié)論。 （2）如一個變量是用規(guī)則ES消去量詞，對該變量再添加量詞時，則只能使用規(guī)則EG，而不能使用規(guī)則UG；如使用規(guī)則US消去量詞，對該變量在添加量詞時，則可使用規(guī)則EG和規(guī)則UG。,2020/7/30,謂詞邏輯推理的難點（

33、續(xù)）,（3）如有兩個含有存在量詞的公式，當用規(guī)則ES消去量詞時，不能選用同樣的一個常量符號來取代兩個公式中的變元，而應(yīng)用不同的常量符號來取代它們。 （4）在用規(guī)則US和規(guī)則ES消去量詞時，此量詞必須位于整個公式的最前端。,2020/7/30,謂詞邏輯推理的難點（續(xù)）,（5）在添加量詞(x)、(x)時，所選用的x不能在公式G(c)或G(y)中以任何約束出現(xiàn)。 （6）在使用EG規(guī)則引入存在量詞(x)，此x不得僅為G(c)或G(y)中的函數(shù)變元。在使用UG規(guī)則引入全稱量詞(x)時，此x不得為G(y)中的函數(shù)變元(因該函數(shù)變元不得作為自由變元)。,2020/7/30,5.3.4 謂詞邏輯推理的應(yīng)用,例

34、5.3.5 每個喜歡步行的人都不喜歡坐汽車；每個人或者喜歡坐汽車或者喜歡騎自行車；有的人不喜歡騎自行車。因而有的人不喜歡步行。,證明 設(shè)H(x)：x是人； P(x)：x喜歡坐汽車； Q(x)：x喜歡騎自行車；R(x)：x喜歡步行。 則上述語句可符號化為： (x)(H(x)R(x) P(x)， (x)(H(x)P(x)Q(x)， (x)(H(x)Q(x)(x)(H(x) R(x),2020/7/30,例5.3.5 證明（續(xù)）,證：(1)(x)(H(x) Q(x) P (2)H(c) Q(c) ES，(1) (3)H(c) T，(2) (4) Q(c) T，(2) (5)(x)( H(x)P(x)

35、Q(x) P (6)H(c)P(c)Q(c) US，(5) (7)P(c)Q(c) T，(3)，(6)，I (8)P(c) T，(4)，(7)，I,上述語句可符號化為： (x)(H(x)R(x)P(x),(x)(H(x)P(x)Q(x), (x)(H(x)Q(x) (x)(H(x)R(x),2020/7/30,例5.3.5 證明（續(xù)）,(3)H(c) T，(2) (8)P(c) T，(4)，(7)，I (9) (x)(H(x)R(x) P(x) P (10) H(c)R(c) P(c) US，(9) (11) (H(c)R(c) T，(8)，(10)，I (12) H(c) R(c) T，(1

36、1)，E (13) R(c) T，(3)，(12)，I (14) H(c) R(c) T，(3)，(13)，I (15) (x)(H(x) R(x) EG，(14),上述語句可符號化為： (x)(H(x)R(x)P(x),(x)(H(x)P(x)Q(x), (x)(H(x)Q(x) (x)(H(x)R(x),2020/7/30,例5.3.6,證明下述論斷的正確性： 所有的哺乳動物都是脊椎動物；并非所有的哺乳動物都是胎生動物；故有些脊椎動物不是胎生的。 證明 設(shè)謂詞如下： P(x)：x是哺乳動物； Q(x)：x是脊椎動物； R(x)：x是胎生動物。 則有： (x)(P(x)Q(x),(x)(P(

37、x)R(x) (x)(Q(x)R(x),2020/7/30,請看下面推導(dǎo)：,1) (x)(P(x)R(x)P 2) (P(x)R(x)US,1) 3) (P(x)R(x) T,2)，E 4) (P(x)R(x)T,3),E 5) P(x)T,4),I 6) R(x)T,4),I 7) (x)(P(x)Q(x) P 8) P(x)Q(x) US,7) 9) Q(x)T,(5),(8),I 10)Q(x)R(x)T,6),9),I 11)(x)(Q(x)R(x)EG,10) 12)(x)(Q(x)R(x)UG,10),(x)(P(x)Q(x),(x)(P(x)R(x) (x)(Q(x)R(x),錯

38、誤推導(dǎo),2020/7/30,例5.3.6 證明（續(xù)）,1) (x)(P(x)R(x)P 2) (x)(P(x)R(x)T,1),E 3) (P(c)R(c) ES,2) 4) (P(c)R(c)T,3),E 5) P(c)T,4),I 6) R(c)T,4),I 7) (x)(P(x)Q(x)P 8) P(c)Q(c)US,7) 9) Q(c)T,5),8),I 10)Q(c)R(c)T,6),9),I 11)(x)(Q(x)R(x)EG,10),(x)(P(x)Q(x),(x)(P(x)R(x) (x)(Q(x)R(x),正確推導(dǎo),2020/7/30,例5.3.7,證明下列論斷的正確性： 有

39、些信徒相信所有的神父；任何一個信徒都不相信騙子；所以，神父都不是騙子。 證明 設(shè)謂詞如下： S(x)：x是信徒T(x)：x是神父 P(x)：x是騙子L(x,y)：x相信y 則可符號化為： (x)(S(x)(y)(T(y)L(x,y)， (x)(y)(S(x)P(y)L(x,y) (x)(T(x)P(x),2020/7/30,例5.3.7 證明（續(xù)）,1) (x)(S(x)(y)(T(y)L(x,y) P 2) S(c)(y)(T(y)L(c,y) ES,1) 3) S(c) T,2),I 4) (y)(T(y)L(c,y) T,2),I 5) T(x)L(c,x) US,4) 6) (x)(y

40、)(S(x)P(y)L(x,y) P 7) (y)(S(c)P(y)L(c,y) US,6) 8) (S(c)P(x)L(c,x) US,7),(x)(S(x)(y)(T(y)L(x,y)， (x)(y)(S(x)P(y)L(x,y) (x)(T(x)P(x),2020/7/30,例5.3.7 證明（續(xù)）,3) S(c) T,2),I 8) (S(c)P(x)L(c,x) US,7) 9) S(c)(P(x)L(c,x) T,8),E 10) P(x)L(c,x) T,3),8),E 11) L(c,x)P(x) T,10),E 12) T(x)P(x) T,5),11),E 13) (x)(

41、T(x)P(x) US,12),(x)(S(x)(y)(T(y)L(x,y)， (x)(y)(S(x)P(y)L(x,y) (x)(T(x)P(x),2020/7/30,例5.3.8,現(xiàn)有一智力測驗題目(水容器問題)：設(shè)有兩個分別能盛7升與5升的水容器，開始時兩個容器均空，允許對容器做三種操作： （1）容器倒?jié)M水， （2）將容器中的水倒光， （3）從一個容器倒水至另一容器，使一個容器倒光而另一容器倒?jié)M。 最后要求能使大容器(能盛7升的容器)中有4升水，并求其操作過程。,2020/7/30,例5.3.8的解決方案,2020/7/30,例5.3.8 證明,（1）S(0, 0) P （2）(x)(y

42、)(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）,2020/7/30,例5.3.8 證明（續(xù)）,（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)

43、 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）,2020/7/30,例5.3.8 證明（續(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(

44、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）,2020/7/30,例5.3.8 證明（續(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,

45、0) T,(30),(33),I,2020/7/30,5.4 數(shù)學(xué)歸納法,5.4.1 數(shù)學(xué)歸納法原理,假設(shè)要證明的命題能寫成形式: nn0，有P(n) 其中n0是某個固定的整數(shù)， 即：希望證明對所有的整數(shù)nn0都有P(n)為真,2020/7/30,數(shù)學(xué)歸納法原理,假設(shè) 1）驗證nn0，有P(n0)為真； (歸納基礎(chǔ)) 2）假設(shè)對于nk(kn0)，有P(k)為真；(歸納假設(shè)) 3）證明nk1，有P(k+1)為真。 (歸納結(jié)論) 結(jié)論 對所有的整數(shù)nn0，都有P(n)為真。,謂詞表示： (n0)(P(n0)(n)(nk)P(k)P(k+1)1,2020/7/30,強形式數(shù)學(xué)歸納法原理,假設(shè) 1 ）

46、 驗證nn0 、n0 +1，有P(n0)、 P(n0+1)為真； (歸納基礎(chǔ)) 2）假設(shè)對于n k(kn0)，有P(n)為真；(歸納假設(shè)) 3）證明nk1，有P(k+1)為真。 (歸納結(jié)論) 結(jié)論 對所有的整數(shù)nn0，都有P(n)為真。,謂詞表示： (n0)(P(n0) P(n0+1) (n)(nk)P(n)P(k+1)1,2020/7/30,例5.4.1,用數(shù)學(xué)歸納法證明： 對所有n1，有1+2+3+n=,證明 歸納基礎(chǔ)驗證 1= 顯然P(1)真值為1； 歸納假設(shè)假定 對于n=k(k1)，有P(k)為真，即有 1+2+3+k= ；,2020/7/30,例5.4.1,歸納結(jié)論證明 對于nk1，

47、有P(k+1)為真 1+2+3+k+(k+1)= +(k+1) = 由數(shù)學(xué)歸納法原理得到，P(n)對所有n1為真。,2020/7/30,例5.4.2,對每個正整數(shù)n1，能惟一地寫成 ，其中pi是素數(shù)且滿足p1p2ps。,分析 設(shè)P(n) ：n ； 由于素數(shù)一定是大于等于2的正整數(shù)，因此，n02。,2020/7/30,例5.4.2,證明 歸納基礎(chǔ)驗證 因為2=21，3=31，所以P(2)、P(3)為真； 歸納假設(shè)假定 對nk的所有正整數(shù)，都有P(n)為真，即 n,2020/7/30,例5.4.2 證明 (續(xù)),歸納結(jié)論證明 對nk1，需分兩種情況討論： （1）如果n本身就是一個素數(shù)，則 k1(k+1)1，即P(k+1)為真； （2）如果n不是一個素數(shù)，則k1lm， 其中2lk，2mk，此時由歸納假設(shè)有 l ， m 其中，p1, p2, , ps是素數(shù)，且是包含l