人工智能課件第四章確定性推理

第4章確定性推理本章介紹：

自然演繹推理

歸結(jié)演繹推理推理就是按某種策略由已知判斷推出另一判斷的思維過程已知判斷：包括已掌握的與求解問題有關(guān)的知識及關(guān)于問題的已知事實推理的結(jié)論：由已知判斷推出新判斷推理由程序程序?qū)崿F(xiàn)，稱為推理機(jī)12/16/20221第4章確定性推理本章介紹：推理就是按某種策略由已知判斷推出1、演繹推理、歸納推理、默認(rèn)推理推理的基本任務(wù)是從一種判斷推出另一種判斷按判斷推出的途徑來劃分，可分為演繹推理、歸結(jié)推理及默認(rèn)推理（1）演繹推理演繹推理是從全稱判斷推導(dǎo)出特稱判斷或單稱判斷的過程演繹推理有多種形式，經(jīng)常用的是三段論式三段論式包括大前提：已知的一般性知識或假設(shè)小前提：關(guān)于所研究的具體情況或個別事實的判斷結(jié)論：由大前提推出的適合于小前提所示情況的新判斷4.1推理技術(shù)概述12/16/202221、演繹推理、歸納推理、默認(rèn)推理4.1推理技術(shù)概述12/1在任何情況下，由演繹推導(dǎo)出的結(jié)論都是蘊(yùn)涵在大前提的一般性知識中只要大前提和小前提是正確的，則由它們推出的結(jié)論必然是正確的(2)歸納推理歸納推理是從足夠多的事例中歸納出一般性結(jié)論的推理過程，是一種從個別到一般的推理歸納推理：完全歸納推理、不完全歸納推理完全歸納推理是在進(jìn)行歸納時考察了相應(yīng)事物的全部對象，并根據(jù)這些對象是否都具有某種屬性，從而推出這個事物是否具有這個屬性不完全歸納推理是指只考察了相應(yīng)事物的部分對象就得出了結(jié)論12/16/20223在任何情況下，由演繹推導(dǎo)出的結(jié)論都是蘊(yùn)涵在大前提的一般性知識枚舉歸納推理：若已知某類事物的有限可數(shù)個具體事物都具有某種屬性，則可推出該類事物都具有此屬性類比推理：在兩個或兩類事物有許多屬性都相同或相似的基礎(chǔ)上，推出它們在其他屬性上也相同或相似的一種推理(3)默認(rèn)推理又稱缺省推理，它是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理擺脫了需要知道全部事實才能進(jìn)行推理的需求，使得在知識不完全的情況下也能進(jìn)行推理12/16/20224枚舉歸納推理：若已知某類事物的有限可數(shù)個具體事物都具有某種屬2、確定性推理、不確定性推理按推理時所用知識的確定性來劃分，推理可分為確定性推理、不確定性推理確定性推理：推理時所用的知識都是精確的，推出的結(jié)論也是確定的，其真值或者為真，或為假，沒有第三種情況出現(xiàn)不確定性推理：推理時所用的知識不都是精確的，推出的結(jié)論也不完全是肯定的，真值位于真與假之間，命題的外延模糊不清12/16/202252、確定性推理、不確定性推理12/10/202253、單調(diào)推理、非單調(diào)推理按推理過程中推出的結(jié)論是否單調(diào)地增加，或推出的結(jié)論是否越來越接近目標(biāo)，可分為單調(diào)推理和非單調(diào)推理單調(diào)推理：在推理過程中隨著推理的向前及新知識的加入，推出的結(jié)論是呈單調(diào)增加的趨勢，并且越來越接近最終目標(biāo)，在推理過程中不出現(xiàn)反復(fù)的情況非單調(diào)推理：在推理過程中由于新知識的加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新開始12/16/202263、單調(diào)推理、非單調(diào)推理12/10/202264.2自然演繹推理定義：自然演繹推理是指從一組已知的事實出發(fā)，直接運(yùn)用命題邏輯或謂詞邏輯中的推理規(guī)則推出結(jié)論的過程。

推理規(guī)則：P規(guī)則：在推理的任何步驟上都可引入前提T規(guī)則：推理時，如果前面步驟中有一個或多個公式永真蘊(yùn)涵公式S，則可把S引入推理過程中。CP規(guī)則：如果能從R和前提集合中推出S來，則可從前提集合推出來。反證法：，當(dāng)且僅當(dāng)。即：Q為P的邏輯結(jié)論，當(dāng)且僅當(dāng)是不可滿足的。12/16/202274.2自然演繹推理定義：自然演繹推理是指從一組已知的事實出假言推理表示：由及P為真，可推出Q為真

拒取式推理表示：由為真及Q為假，可推出P為假

12/16/20228假言推理12/10/20228避免產(chǎn)生兩類錯誤：肯定后件(Q)的錯誤：希望通過肯定后件Q推出前件P為真否定前件(P)的錯誤：希望通過否定前件P推出后件Q為假12/16/20229避免產(chǎn)生兩類錯誤：12/10/20229例：設(shè)已知事實（1）只要不怕困難的人，就會獲得勝利。（2）運(yùn)動員都是不怕困難的人。（3）王力是運(yùn)動員。求證：王力會獲得勝利。12/16/202210例：設(shè)已知事實12/10/202210自然演繹推理的優(yōu)缺點優(yōu)點：定理證明過程自然，容易理解，而且它擁有豐富的推理規(guī)則，推理過程靈活，便于在它的推理規(guī)則中嵌入領(lǐng)域啟發(fā)式知識。缺點：容易產(chǎn)生組合爆炸，推理過程中得到的中間結(jié)論一般呈指數(shù)形式遞增。12/16/202211自然演繹推理的優(yōu)缺點12/10/2022111、合式公式的定義合式公式適合于一階謂詞邏輯遵從以下遞歸方式定義的邏輯語句稱為合式公式①單一謂詞公式是合式公式；②若A是合式公式，則A也是合式公式；③若A和B都是合式公式，則A∧B、A∨B、AB和AB也都是合式公式；④若A是合式公式，x是約束變量，則(x)A和(x)A也都是合式公式；⑤只有按上述規(guī)則①-④求得的公式，才是合式公式。連詞優(yōu)先級別是，∧、∨，、，但可通過括號改變優(yōu)先級。4.3合式公式

一、合式公式12/16/2022121、合式公式的定義4.3合式公式

一、合式公式12/1

一、合式公式1、合式公式的定義例2、“所有人(Person)都喜歡(Like)一種游戲(Game)”①謂詞公式Person(x)Like(x,y)Game(y)②量詞(x)Person(x)表示所有人；(y)Game(y)表示一種游戲；③合式公式(x)(y)[Person(x)∧Game(y)∧Like(x,y)]12/16/202213

一、合式公式1、合式公式的定義12/10/202213

一、合式公式2、合式公式的解釋命題邏輯——不存在變量給命題中包含的各個原子公式指派真值（T或F），稱這種指派為命題的一個解釋；解釋確定后，可依據(jù)連接原子公式的連詞的作用求出命題的真值（T或F）。謂詞邏輯——涉及變量不可能直接給原子公式指派真值；①定義一個擬觀察個體的可能論域；②確定原子公式中變量項和函數(shù)項在論域中的取值；③給原子公式指派真值。解釋確定后，可依據(jù)連接原子公式的連詞的作用求出合式公式的真值（T或F）。12/16/202214

一、合式公式2、合式公式的解釋12/10/202214

一、合式公式2、合式公式的解釋例3、合式公式(x)(y)[P(x)Q(f(x),y)]一個解釋的建立。①設(shè)定論域D={1,2};x∈D,y∈D②對于x的每個取值函數(shù)f(x)：f(1)=2,f(2)=2;③對于x的每個取值原子公式P(x)：P(1)=T,P(2)=T；④對于f(x)和y的每個取值組合(只有2個：2、1；2、2)原子公式Q(f(x),y)：Q(2,1)=T,Q(2,2)=F；上述指派就確定了該合式公式的一個解釋；在這個解釋下，合式公式有真值T；12/16/202215

一、合式公式2、合式公式的解釋12/10/202215

一、合式公式3、合式公式的永真性和可滿足性(1)合式公式的永真性若P在某個論域D上的所有可能的解釋都有真值T，則稱P在D上是永真的；若P在每個可能的非空論域D上均永真，則稱P是永真的。(2)合式公式的可滿足性若P在某個論域D上的至少可以建立一個解釋，使P有真值T，則稱P在D上是可滿足的；若至少有一個非空論域D使P可滿足，則稱P是可滿足的。(3)合式公式的永假性若P在某個論域D上的所有可能的解釋都有真值F，則稱P在D上是永假的；若P在每個可能的非空論域D上均永假，則稱P是永假的。12/16/202216

一、合式公式3、合式公式的永真性和可滿足性12/10/

一、合式公式3、合式公式的永真性和可滿足性①論域個數(shù)較少，每個論域較小易判斷合式公式的永真性和可滿足性；②論域個數(shù)較多，每個論域較大，解釋個數(shù)有限永真性和可滿足性總是可判斷的；③解釋個數(shù)無限不能確?？膳袛?；不能確保在有限的時間內(nèi)判斷。12/16/202217

一、合式公式3、合式公式的永真性和可滿足性12/10/

一、合式公式4、合式公式的性質(zhì)合式公式優(yōu)點：具有強(qiáng)大的形式化表示功能；合式公式缺點：包括了多種連詞和量詞以及它們的嵌套應(yīng)用，表示形式過于復(fù)雜；不利于演繹推理系統(tǒng)的設(shè)計和高效運(yùn)作?；喓鲜焦降侥承┘s定的標(biāo)準(zhǔn)形式是很有意義。合取范式析取范式合式公式的性質(zhì)則為化簡工作提供了依據(jù)。12/16/202218

一、合式公式4、合式公式的性質(zhì)12/10/202218

一、合式公式4、合式公式的性質(zhì)十種常用性質(zhì)(1)雙重否定：(P)P(2)蘊(yùn)涵式轉(zhuǎn)化：PQP∨Q(3)狄.摩根定律：(P∨Q)P∧Q(P∧Q)P∨Q(4)分配律P∧(Q∨R)(P∧Q)∨(P∧R)P∨(Q∧R)(P∨Q)∧(P∨R)(5)交換律P∧QQ∧PP∨QQ∨P(6)結(jié)合律(P∧Q)∧RP∧(Q∧R)(P∨Q)∨RP∨(Q∨R)12/16/202219

一、合式公式4、合式公式的性質(zhì)12/10/202219

一、合式公式4、合式公式的性質(zhì)十種常用性質(zhì)(7)逆否律PQQP(8)量詞否定(x)P(x)(x)(P(x))(x)P(x)(x)(P(x))(9)量詞分配(x)[P(x)∧Q(x)](x)P(x)∧(x)Q(x)(x)[P(x)∨Q(x)](x)P(x)∨(x)Q(x)(10)約束變量的虛元化約束變量名的變換不影響合式公式的真值(x)P(x)(y)P(y)(x)P(x)(y)P(y)12/16/202220

一、合式公式4、合式公式的性質(zhì)12/10/202220

一、合式公式4、合式公式的性質(zhì)(9)量詞分配(x)[P(x)∧Q(x)](x)P(x)∧(y)Q(y)(x)[P(x)∨Q(x)](x)P(x)∨(y)Q(y)(10)約束變量的虛元化約束變量名的變換不影響合式公式的真值(x)P(x)(y)P(y)(x)P(x)(y)P(y)12/16/202221

一、合式公式4、合式公式的性質(zhì)12/10/202221

二、合式公式的標(biāo)準(zhǔn)化1、標(biāo)準(zhǔn)化需求常見的基于謂詞演算的推理：歸結(jié)反演、(正向/逆向)演繹推理要求以量詞前束范式來表示合式公式量詞前束范式形式如下：(Q1x1)(Q2x2)…(Qkxk)M，其中M——母式，不包括任何量詞；Qixi——Qi可以是量詞符號或；xi是量詞的約束變量(i=1,2,…,k)歸結(jié)反演（4.5.5，2.3.3）——要求M標(biāo)準(zhǔn)化為合取范式，定義如下：M=W1∧W2∧…∧WnWi=Li1∨Li2∨…∨Lim(i=1,2,…,n)Lij=Pij|Pij:文字（Literal），是謂詞公式Pij或其取反12/16/202222

二、合式公式的標(biāo)準(zhǔn)化1、標(biāo)準(zhǔn)化需求12/10/2022

二、合式公式的標(biāo)準(zhǔn)化1、標(biāo)準(zhǔn)化需求常見的基于謂詞演算的推理：歸結(jié)反演、規(guī)則演繹要求以量詞前束范式來表示合式公式量詞前束范式形式如下：(Q1x1)(Q2x2)…(Qkxk)M歸結(jié)反演——要求M標(biāo)準(zhǔn)化為合取范式，定義如下：M=W1∧W2∧…∧WnWi=Li1∨Li2∨…∨Lim(i=1,2,…,n)Lij=Pij|Pij:文字（Literal），是原子謂詞公式Pij或其取反析取范式定義：M=W1∨W2∨…∨WnWi=Li1∧Li2∧…∧Lim(i=1,2,…,n)Lij=Pij|Pij:文字（Literal），是原子謂詞公式Pij或其取反12/16/202223

二、合式公式的標(biāo)準(zhǔn)化1、標(biāo)準(zhǔn)化需求12/10/2022定義

設(shè)F為一謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公式的最前面，而它們的轄域為整個公式，則稱F為前束范式(prenexnormalform)。一般地，前束范式可以寫成:其中為前綴，是一個由全稱量詞或存在量詞組成的量詞串，為母式，它是一個不含任何量詞的謂詞公式。前束標(biāo)準(zhǔn)型在一階邏輯中，為了簡化定理證明程序需要引入所謂的“前束標(biāo)準(zhǔn)型”。12/16/202224定義設(shè)F為一謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公

下面是一些前束范式的例子：

為了把一個公式化為前束范式，首先看一下包含一階邏輯特有的等價式對，如下所示。

前束標(biāo)準(zhǔn)型12/16/202225下面是一些前束范式的例子：前束標(biāo)準(zhǔn)型12/在上述等價公式對中，F(xiàn)(x)和H(x)都表示含未量化變量x的公式，G表示不含未量化變量x的公式，Q1,Q2

或為或為。對(3)和(4)，要求z不出現(xiàn)在F(x)中，并且符合約束變量的換名原則。前束標(biāo)準(zhǔn)型12/16/202226在上述等價公式對中，F(xiàn)(x)和H(x)都表

使用前面定義的等價式，總可以把一個公式化為前束標(biāo)準(zhǔn)型。變換過程如下：

(1)使用等價式中的連接詞轉(zhuǎn)化規(guī)律消去公式中的連接詞→,←→。(2)反復(fù)使用雙重否定律和德·摩根律將“┓(或～)”移到原子之前。(3)必要時重新命名量化的變量。(4)使用量詞分配律和等價式，把所有量詞都移到整個公式的最左邊以得出一個范式。前束標(biāo)準(zhǔn)型12/16/202227使用前面定義的等價式，總可以把一個公式化

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程應(yīng)用合式公式性質(zhì)將公式逐步轉(zhuǎn)化的過程。轉(zhuǎn)化步驟沒有嚴(yán)格的規(guī)定較合理的化簡過程，分為8步：①消去多余的量詞（很少出現(xiàn)）；②消去蘊(yùn)涵符號；③內(nèi)移否定符號；④變量換名；⑤消去存在量詞；⑥全稱量詞前束化；⑦消去全稱量詞；⑧把母式轉(zhuǎn)化為合取范式。12/16/202228

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程①消去多余的量詞（很少出現(xiàn)）若一個量詞的轄域內(nèi)并未出現(xiàn)量詞的約束變量，則該量詞是多余的，應(yīng)該刪除；例，(x)P(y)，則(x)可以消去，得到P(y)；正常情況下，合式公式中不應(yīng)出現(xiàn)多余的量詞。②消去蘊(yùn)涵符號蘊(yùn)涵式轉(zhuǎn)化：PQP∨Q；例，Q(x,y)P(y)Q(x,y)∨P(y)。12/16/202229

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程③內(nèi)移否定符號使否定只出現(xiàn)在原子謂詞公式前，構(gòu)成否定文字；狄.摩根定律：(P∨Q)P∧Q(P∧Q)P∨Q雙重否定：(P)P量詞否定：(x)P(x)(x)(P(x))(x)P(x)(x)(P(x))例，(y)[P(y)∨P(f(x,y))](y)[P(y)∧P(f(x,y))]④變量換名“⑥全稱量詞前束化”后，同名變量的轄域無法區(qū)分，所以為避免差錯，必須換名；約束變量的虛元性進(jìn)行變換；(x)P(x)(y)P(y)(x)P(x)(y)P(y)12/16/202230

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10⑤消去存在量詞Skolem標(biāo)準(zhǔn)化過程Step1:化成前束范式:Step2:使用下述方法可以消去前綴中存在的所有量詞：令是中出現(xiàn)的存在量詞。Case1:若在之前不出現(xiàn)全稱量詞，則選擇一個與M中出現(xiàn)的所有常量都不相同的新常量c，用c代替M中出現(xiàn)的所有xr，并且由前綴中刪去(Qrxr)。Case2:若在之前出現(xiàn)全稱量詞，則選擇一個與M中出現(xiàn)的任一函數(shù)符號都不相同的新m元函數(shù)符號f，用代替M中的所有xr，并且由前綴中刪去(Qrxr)。

按上述方法刪去前綴中的所有存在量詞之后得出的公式稱為合式公式的Skolem標(biāo)準(zhǔn)型。替代存在量化變量的常量c(視為0元函數(shù))和函數(shù)f稱為Skolem函數(shù)。12/16/202231⑤消去存在量詞Skolem標(biāo)準(zhǔn)化過程Step1:化成前束范在公式中，的前面沒有全稱量詞，的前面有全稱量詞和,在的前面有全稱量詞，和。所以，在中，用常數(shù)a代替x,用二元函數(shù)f(y,z)代替u,用三元函數(shù)g(y,z,v)代替w,去掉前綴中的所有存在量詞之后得出Skolem標(biāo)準(zhǔn)型：例題分析例4.1

化公式為Skolem標(biāo)準(zhǔn)型。12/16/202232在公式中，的前面沒有全稱量詞，的前面

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程⑤消去存在量詞在的轄域內(nèi)(z)(w)[Q(x,z)∨P(z,w)]w依賴于z，由函數(shù)w=g(z)來定義這種依賴關(guān)系；用g(z)來取代約束變量w，消去存在量詞w；(z)[Q(x,z)∨P(z,g(z))]在多個的轄域內(nèi)(x)(y)(z)(w)P(x,y,z,w)用多元函數(shù)g(x,y,z)來取代約束變量w，消去存在量詞w；(x)(y)(z)P(x,y,z,g(x,y,z))在的轄域外(w)(z)[Q(x,z)∨P(z,w)]用任意常量A取代約束變量w，消去存在量詞w(z)[Q(x,z)∨P(z,A)]12/16/202233

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程⑥全稱量詞前束化經(jīng)過“④變量換名”后，所有量詞的約束變量均有不同的名字；只要簡單地將移到合式公式的最前面；約束變量的作用范圍不會變化。⑦消去全稱量詞經(jīng)過“⑤消去存在量詞”后，所有變量均受的約束；簡單地刪除，只留下母式。⑧把母式轉(zhuǎn)化為合取范式分配律：P∨(Q∧R)(P∨Q)∧(P∨R)12/16/202234

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡合式公式(x){P(x){(y)[P(y)P(f(x,y))]∧(y)(w)[Q(x,y)P(y,w)]}}12/16/202235

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡合式公式(x){P(x){(y)[P(y)P(f(x,y))]∧(y)(w)[Q(x,y)P(y,w)]}}②消去蘊(yùn)涵符號(x){P(x)∨{(y)[P(y)∨P(f(x,y))]∧(y)(w)[Q(x,y)∨P(y,w)]}}12/16/202236

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡合式公式(x){P(x)∨{(y)[P(y)∨P(f(x,y))]∧(y)(w)[Q(x,y)∨P(y,w)]}} ③內(nèi)移否定符號(x){P(x)∧{(y)[P(y)∧P(f(x,y))]∨(y)(w)[Q(x,y)∨P(y,w)]}}12/16/202237

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡合式公式

(x){P(x)∧{(y)[P(y)∧P(f(x,y))]∨(y)(w)[Q(x,y)∨P(y,w)]}}④變量換名 (x){P(x)∧{(y)[P(y)∧P(f(x,y))]∨(z)(w)[Q(x,z)∨P(z,w)]}}12/16/202238

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡合式公式 (x){P(x)∧{(y)[P(y)∧P(f(x,y))]∨(z)(w)[Q(x,z)∨P(z,w)]}}⑤消去存在量詞{P(A)∧{(y)[P(y)∧P(f(A,y))]∨(z)[Q(A,z)∨P(z,g(z))]}}12/16/202239

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡合式公式{P(A)∧{(y)[P(y)∧P(f(A,y))]∨(z)[Q(A,z)∨P(z,g(z))]}}⑥全稱量詞前束化(y)(z){P(A)∧{[P(y)∧P(f(A,y))]∨[Q(A,z)∨P(z,g(z))]}}12/16/202240

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡合式公式(y)(z){P(A)∧{[P(y)∧P(f(A,y))]∨[Q(A,z)∨P(z,g(z))]}}⑦消去全稱量詞{P(A)∧{[P(y)∧P(f(A,y))]∨[Q(A,z)∨P(z,g(z))]}}12/16/202241

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程12/10

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡合式公式{P(A)∧{[P(y)∧P(f(A,y))]∨[Q(A,z)∨P(z,g(z))]}}⑧把母式轉(zhuǎn)化為合取范式{P(A)∧{[P(y)∨Q(A,z)∨P(z,g(z))]∧[P(f(A,y))∨Q(A,z)∨P(z,g(z))]}}完成標(biāo)準(zhǔn)化過程！12/16/202242

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程完成標(biāo)準(zhǔn)化4.4歸結(jié)演繹推理自動定理證明一般表示形式為：F1∧F2∧…∧FnWF1,F2,…,Fn都是合式公式，表示公理或事實；W是合式公式，表示待證明的定理，稱為目標(biāo)公式；證明的方法可分兩大類：演繹法直接證明F1∧F2∧…∧FnW為永真；反證法間接證明(F1∧F2∧…∧FnW)為永假；證明F1∧F2∧…∧Fn∧W的永假即{F1,F2,…,Fn}∪{W}是一個矛盾集。4.4歸結(jié)演繹推理12/16/2022434.4歸結(jié)演繹推理自動定理證明一般表示形式為：4.4歸結(jié)4.4歸結(jié)演繹推理海伯倫（Herbrand）提出的H域（海伯倫域）和海伯倫定理；為自動定理證明奠定了理論基礎(chǔ)；魯賓遜（Robinson）提出的歸結(jié)原理；使自動定理證明成為可能。12/16/2022444.4歸結(jié)演繹推理海伯倫（Herbrand）12/10/24.4歸結(jié)演繹推理

1）H域和海伯倫定理（了解）1、子句和子句集子句——僅由文字的析取∨構(gòu)成的合式公式Wi=Li1∨Li2∨…∨Lim稱為子句；合取范式定義：M=W1∧W2∧…∧WnWi=Li1∨Li2∨…∨Lim(i=1,2,…,n)Lij=Pij|Pij:文字（Literal），是原子謂詞公式Pij或其取反合取范式可定義為子句的合取∧

；合取范式表示為子句集，子句間隱含合取∧關(guān)系子句集{W1,W2,…,Wn}12/16/2022454.4歸結(jié)演繹推理

1）H域和海伯倫定理（了解）1、子句和4.4歸結(jié)演繹推理

1）H域和海伯倫定理1、子句和子句集子句——僅由文字的析取∨構(gòu)成的合式公式合取范式表示為子句集，子句間隱含具有合取關(guān)系{P(A)∧[P(y)∨Q(A,z)∨P(z,g(z))]∧[P(f(A,y))∨Q(A,z)∨P(z,g(z))]}可進(jìn)一步表示為子句集{P(A),P(y)∨Q(A,z)∨P(z,g(z)),P(f(A,y))∨Q(A,z)∨P(z,g(z))}12/16/2022464.4歸結(jié)演繹推理

1）H域和海伯倫定理1、子句和子句集14.4歸結(jié)演繹推理

1）H域和海伯倫定理1、子句和子句集子句——僅由文字的析取∨構(gòu)成的合式公式合取范式表示為子句集，子句間隱含具有合取關(guān)系(y)(z){P(A)∧[P(y)∨Q(A,z)∨P(z,g(z))]∧[P(f(A,y))∨Q(A,z)∨P(z,g(z))]}量詞分配：

(x)[P(x)∧Q(x)](x)P(x)∧(x)Q(x)(y)(z)P(A)∧(y)(z)[P(y)∨Q(A,z)∨P(z,g(z))]∧(y)(z)[P(f(A,y))∨Q(A,z)∨P(z,g(z))]12/16/2022474.4歸結(jié)演繹推理

1）H域和海伯倫定理1、子句和子句集14.4歸結(jié)演繹推理

1）H域和海伯倫定理1、子句和子句集子句中的變量都是的約束變量{(y)(z)P(A),(y)(z)[P(y)∨Q(A,z)∨P(z,g(z))],(y)(z)[P(f(A,y))∨Q(A,z)∨P(z,g(z))]}為了消除子句間不必要的交互作用，保持子句的獨立性，需要做變量換名{P(A),P(y1)∨Q(A,z1)∨P(z1,g(z1)),P(f(A,y2))∨Q(A,z2)∨P(z2,g(z2))}12/16/2022484.4歸結(jié)演繹推理

1）H域和海伯倫定理1、子句和子句集1例4.2將合式公式化為子句形。解：（1）消去蘊(yùn)涵符號：這可以利用等價式：得到：x[(~P(x)[y[~P(y)P(f(x,y))]~y[~Q(x,y)P(y)]]]（2）減少否定符號的轄域，把“”移到緊靠謂詞的位置上：這可以利用下述等價式：例題12/16/202249例4.2將合式公式化為子句形。例題12/10/20224得到：

x[(~P(x)[y[~P(y)P(f(x,y))]y[Q(x,y)~P(y)]]]（3）變量標(biāo)準(zhǔn)化：重新命名變元名，使不同量詞約束的變元有不同的名字：x[~P(x)[y[~P(y)P(f(x,y))]w[Q(x,w)~P(w)]]]（4）消去存在量詞：

x[~P(x)[y[~P(y)P(f(x,y))][Q(x,g(x))~P(g(x))]]]12/16/202250得到：12/10/202250（5）化為前束形：

xy[~P(x)[[~P(y)P(f(x,y))][Q(x,g(x))~P(g(x))]]]（6）把母式化為合取范式：

xy[~P(x)~P(y)P(f(x,y))][~P(x)Q(x,g(x))][~P(x)~P(g(x))]（7）消去全稱量詞和合取連接詞：[~P(x)~P(y)P(f(x,y))]

[~P(x)Q(x,g(x))]

[~P(x)~P(g(x))]

12/16/202251（5）化為前束形：12/10/202251（8）更改變量名，有時稱為變量分離標(biāo)準(zhǔn)化。于是有：

必須指出:一個子句內(nèi)的文字可以含有變量，但這些變量總是被理解為全稱量詞量化了的變量。12/16/202252（8）更改變量名，有時稱為變量分離標(biāo)準(zhǔn)化。于是有：12/104.4歸結(jié)演繹推理

1）H域和海伯倫定理1、子句和子句集合式公式F合取范式子句集S合式公式F永假子句集S的不可滿足性充分必要條件重要性質(zhì)S的不可滿足性任意論域D上的任意解釋I,S中都至少有一個子句真值為F12/16/2022534.4歸結(jié)演繹推理

1）H域和海伯倫定理1、子句和子句集合4.4歸結(jié)演繹推理

1）H域和海伯倫定理1、子句和子句集合式公式F合取范式子句集S合式公式F永假子句集S的不可滿足性充分必要條件合式公式F子句集S不等價S是F的特例重要性質(zhì)S的不可滿足性任意論域D上的任意解釋I,S中都至少有一個子句真值為F12/16/2022544.4歸結(jié)演繹推理

1）H域和海伯倫定理1、子句和子句集合4.4歸結(jié)演繹推理

1）H域和海伯倫定理2、H域（了解）證明子句集S的不可滿足性與證明合式公式永真性類似由于個體論域的任意性和解釋個數(shù)的無限性，使得證明工作十分困難。若能建造一個較為簡單的特殊論域，使得只要證明子句集S在該域不可滿足，就可確保子句集在任何可能的論域上不可滿足，將是十分有意義的！海伯倫建立的特殊域H就具有這樣的性質(zhì)。H域性質(zhì)——對于子句集S的任一可能論域D上的任一解釋I，總能在S的H域上構(gòu)造一個相應(yīng)的解釋I*，使子句集S具有相同的真值。證明子句集S的不可滿足性確定子句集S在H域上的所有解釋都不可滿足。12/16/2022554.4歸結(jié)演繹推理

1）H域和海伯倫定理2、H域（了解）14.4歸結(jié)演繹推理

1）H域和海伯倫定理3、海伯倫定理（了解）子句集S中一子句包含的變量用H域中元素取代后，產(chǎn)生的子句稱為基子句。海伯倫定理：子句集S不可滿足的充要條件是存在一個有限的不可滿足的基子句集S’。有限的不可滿足的基子句集S’子句集S不可滿足性充分必要條件12/16/2022564.4歸結(jié)演繹推理

1）H域和海伯倫定理3、海伯倫定理（了4.4歸結(jié)演繹推理

2）歸結(jié)原理動機(jī)為提高判定子句集S不可滿足的有效性，魯賓遜于1965年提出了歸結(jié)(Resolution)原理，也稱為消解原理。歸結(jié)原理簡單易行，便于計算機(jī)實現(xiàn)和執(zhí)行，從而使定理的機(jī)器自動證明成為現(xiàn)實，也成為人工智能技術(shù)實用化的一次重要突破。12/16/2022574.4歸結(jié)演繹推理

2）歸結(jié)原理動機(jī)12/10/202254.4歸結(jié)演繹推理

2）歸結(jié)原理1、歸結(jié)方法(1)歸結(jié)式（消解式*）設(shè)有兩個子句C1=L∨C1’、C2=L∨C2’①從C1和C2中消去互補(bǔ)文字L和L；②C1’和C2’通過∨組成新的子句C=C1’∨C2’；稱C為C1和C2的歸結(jié)式（消解式*）；例4、兩個子句C1=P(A)∨Q(x)∨R(f(x))C2=P(A)∨Q(y)∨R(y)消去互補(bǔ)文字P(A)和P(A)后，生成歸結(jié)式：C12=Q(x)∨R(f(x))∨Q(y)∨R(y)C1’C2’12/16/2022584.4歸結(jié)演繹推理

2）歸結(jié)原理1、歸結(jié)方法C1’C2’14.4歸結(jié)演繹推理

2）歸結(jié)原理1、歸結(jié)方法(2)歸結(jié)式性質(zhì)定理：兩個子句C1和C2的歸結(jié)式C是C1和C2的邏輯推論任一使子句C1和C2為真的解釋I，必使歸結(jié)式C為真；歸結(jié)式C為假的解釋I，子句C1或者C2為假；推論：設(shè)C1和C2是子句集S中的兩個子句，并以C作為它們的歸結(jié)式；通過往S中加入C而產(chǎn)生的擴(kuò)展子句集S’與子句集S在不可滿足的意義上是等價的！擴(kuò)展子句集S’子句集S不可滿足性等價12/16/2022594.4歸結(jié)演繹推理

2）歸結(jié)原理1、歸結(jié)方法擴(kuò)展子句集S’4.4歸結(jié)演繹推理

2）歸結(jié)原理1、歸結(jié)方法(3)空子句設(shè)C1=L、C2=L，則歸結(jié)式C為空；以□表示為空的歸結(jié)式C，并稱C=□為空子句；因為C1和C2是一對矛盾子句，不可同時滿足，所以□是不可滿足的子句；通過往S中加入□而產(chǎn)生的擴(kuò)展子句集S’不可滿足；空子句□是用歸結(jié)原理判定子句集S不可滿足的成功標(biāo)志。擴(kuò)展子句集S’子句集S不可滿足性等價12/16/2022604.4歸結(jié)演繹推理

2）歸結(jié)原理1、歸結(jié)方法擴(kuò)展子句集S’4.4歸結(jié)演繹推理

2）歸結(jié)原理動機(jī)為提高判定子句集S不可滿足的有效性，魯賓遜于1965年提出了歸結(jié)(Resolution)原理，也稱為消解原理。歸結(jié)原理簡單易行，便于計算機(jī)實現(xiàn)和執(zhí)行，從而使定理的機(jī)器自動證明成為現(xiàn)實，也成為人工智能技術(shù)實用化的一次重要突破。基本思路通過歸結(jié)方法不斷擴(kuò)充待判定的子句集S，并設(shè)法使其包含進(jìn)指示矛盾的空子句?？兆泳涫遣豢蓾M足（即永假）的子句；12/16/2022614.4歸結(jié)演繹推理

2）歸結(jié)原理動機(jī)12/10/202264.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程——歸結(jié)演繹樹(1)命題邏輯中的歸結(jié)推理過程子句中文字只是原子命題公式或其取反，不帶變量；易于判別哪些子句對包含互補(bǔ)文字；例5、子句集S={P∨Q,P∨R,Q,R}的歸結(jié)演繹樹。12/16/2022624.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程——歸結(jié)演4.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(1)命題邏輯中的歸結(jié)推理過程例5、子句集S={P∨Q,P∨R,Q,R}的歸結(jié)演繹樹。擴(kuò)展子句集S’包含空子句子句集S不可滿足12/16/2022634.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程擴(kuò)展子句集4.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程子句中含有變量，不能直接發(fā)現(xiàn)和消去互補(bǔ)文字；需對潛在的互補(bǔ)文字先作變量置換和合一處理。變量置換：用置換項取代公式中的變量；置換項可以是變量、常量或函數(shù)。置換元素——t/v（置換項/變量）置換——若干置換元素的集合；合一處理：P(x,y,x,g(x)),P(A,B,A,z)12/16/2022644.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程P(x,

P(x,y,x,g(x)),P(A,B,A,z)我們可以為它們建立多個置換：

S1={A/x,B/y,g(x)/z}

S2={f(w)/x,z/y,C/z}

S3={B/x,f(w)/y,y/z}

置換結(jié)果為：

{P(x,y,x,g(x)),P(A,B,A,z)}S1

={P(A,B,A,g(A)),P(A,B,A,g(A))}

{P(x,y,x,g(x)),P(A,B,A,z)}S2

={P(f(w)),z,f(w),g(f(w)),P(A,B,A,C)}

{P(x,y,x,g(x)),P(A,B,A,z)}S3

={P(B,f(w),B,g(B)),P(A,B,A,y)}

S1使?jié)撛诘幕パa(bǔ)文字中的原子謂詞公式變?yōu)橥唬_認(rèn)互補(bǔ)性。12/16/202265P(x,y,x,g(x)),P(A,B,4.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程子句中含有變量，不能直接發(fā)現(xiàn)和消去互補(bǔ)文字；需對潛在的互補(bǔ)文字先作變量置換和合一處理。變量置換：用置換項取代公式中的變量；置換項可以是變量、常量或函數(shù)。置換元素——t/v（置換項/變量）置換——若干置換元素的集合；合一處理：通過多個變量置換，使相應(yīng)于潛在互補(bǔ)文字的原子謂詞公式同一化的過程。P(x,y,x,g(x)),P(A,B,A,z)12/16/2022664.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程P(x,4.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程通過一個匹配過程去檢查兩個原子謂詞公式的可合一性，并同時建立用于實現(xiàn)合一的置換。【匹配過程】①兩個原子謂詞公式必須具有相同的謂詞（符號)和參數(shù)項個數(shù)；②從左到右逐個檢查每對參數(shù)項的可合一性；③若每對參數(shù)項都可合一，則合一處理成功，并建立用于實現(xiàn)合一的置換。12/16/2022674.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程12/104.4歸結(jié)演繹推理

2）歸結(jié)原理【匹配過程】②從左到右逐個檢查每對參數(shù)項的可合一性；參數(shù)對中有一個是變量v（不關(guān)心另一個t是否是變量）v初次出現(xiàn)，參數(shù)對可合一，以另一參數(shù)t為置換項，構(gòu)成置換元素t/v;v出現(xiàn)過，則已建立相應(yīng)的置換元素t’/v，取其置換項t’，檢查是否與另一參數(shù)t合一；若不合一，則處理失敗；參數(shù)對中沒有變量，則必須相同，否則合一處理失敗。12/16/2022684.4歸結(jié)演繹推理

2）歸結(jié)原理【匹配過程】12/10/24.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程匹配過程的例子P(x,y,x,g(x)),P(A,B,A,z)①兩個原子謂詞公式必須具有相同的謂詞和參數(shù)項個數(shù)；②從左到右逐個檢查每對參數(shù)項的可合一性；x和A，x初次出現(xiàn)，可合一，建立置換元素A/x;y和B，y初次出現(xiàn)，可合一，建立置換元素B/y;x和A，x出現(xiàn)過，已經(jīng)建立置換元素A/x，可合一；g(x)和z，z初次出現(xiàn)，可合一，建立置換元素g(x)/z；③若每對參數(shù)項都可合一，則合一處理成功。建立置換S1={A/x,B/y,g(x)/z}

12/16/2022694.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程12/104.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程謂詞邏輯中子句歸結(jié)的例子：

C1=P(x,y)∨Q(x,f(x))∨R(x,f(y))C2=P(A,B)∨Q(z,f(z))∨R(z,f(z))L11=P(x,y)和L12=P(A,B)是潛在的互補(bǔ)文字L11和L12是可合一的；建立置換S1={A/x,B/y}消去互補(bǔ)文字L11和L12后，得歸結(jié)式：Q(A,f(A))∨R(A,f(B))∨Q(z,f(z))∨R(z,f(z))變量的置換必須在整個子句范圍內(nèi)進(jìn)行12/16/2022704.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程12/104.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程謂詞邏輯中子句歸結(jié)的例子：

C1=P(x,y)∨Q(x,f(x))∨R(x,f(y))C2=P(A,B)∨Q(z,f(z))∨R(z,f(z))L12=Q(x,f(x))和L22=Q(z,f(z))是潛在的互補(bǔ)文字L12和L22是可合一的；建立置換S2={z/x}消去互補(bǔ)文字L12和L22后，得歸結(jié)式：P(z,y)∨R(z,f(y))∨P(A,B)∨R(z,f(z))12/16/2022714.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程12/104.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程謂詞邏輯中子句歸結(jié)的例子：

C1=P(x,y)∨Q(x,f(x))∨R(x,f(y))C2=P(A,B)∨Q(z,f(z))∨R(z,f(z))L11=P(x,y)和L12=P(A,B)是互補(bǔ)文字L12=Q(x,f(x))和L22=Q(z,f(z))是互補(bǔ)文字兩個子句可以有多于一對的互補(bǔ)文字12/16/2022724.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程12/104.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程12/16/2022734.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程12/104.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程12/16/2022744.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程12/104.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程12/16/2022754.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程12/104.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程子句集S不可滿足12/16/2022764.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程子句集S不4.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(3)歸結(jié)演繹的完備性基于歸結(jié)的演繹推理是完備的若子句集S不可滿足，就必定存在一個從S到空子句□的歸結(jié)演繹；反之，若存在一個從S到空子句□的歸結(jié)演繹，則S必定是不可滿足的；子句集S是永真的和可滿足的，歸結(jié)原理判定過程將無休止地進(jìn)行下去，得不到任何結(jié)果。12/16/2022774.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程12/104.4歸結(jié)演繹推理

3）歸結(jié)反演歸結(jié)演繹推理為反證法證明定理提供了有效手段。應(yīng)用歸結(jié)演繹推理的定理證明為歸結(jié)反演。教學(xué)要求——掌握主要內(nèi)容掌握歸結(jié)反演方法和提取問題回答技術(shù)；學(xué)會建立歸結(jié)反演樹和修改證明樹。學(xué)習(xí)難點從以自然語言表示的事實集證明目標(biāo)公式（定理）并提取回答的綜合題。12/16/2022784.4歸結(jié)演繹推理

3）歸結(jié)反演歸結(jié)演繹推理為反證法證明4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)歸結(jié)反演的基本思路：要從作為事實的公式集F證明目標(biāo)公式W為真；①先將W取反W，加入公式集F；②標(biāo)準(zhǔn)化F∧W為子句集S；③通過歸結(jié)演繹證明S不可滿足，得出W為真的結(jié)論。歸結(jié)反演系統(tǒng)組成：標(biāo)準(zhǔn)化部件將F∧W標(biāo)準(zhǔn)化為子句，并合并為子句集S；歸結(jié)演繹部件按照歸結(jié)演繹推理，控制定理證明的全過程。12/16/2022794.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)歸結(jié)反演4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題已知下列事實為真T，王(Wang)喜歡(Like)所有種類的食物(Food)。蘋果(Apples)是食物。任何一個東西，若任何人吃了(Eat)它都不會被害死(Killed)，則該東西是食物。李(Li)吃花生(Peanuts)且仍然活著(Alive)。張(Zhang)吃任何李吃的東西。證明：王喜歡花生。12/16/2022804.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題①形式化——把以自然語言表示的事實和要證明的目標(biāo)形式化地表示為合式公式。王(Wang)喜歡(Like)所有種類的食物(Food)。(x)[Food(x)Like(Wang,x)]蘋果(Apples)是食物。Food(Apples)任何一個東西，若任何人吃了(Eat)它都不會被害死(Killed)，則該東西是食物。(x)(y)[Eat(y,x)∧Killed(y)Food(x)](x)(y)[Eat(y,x)∧Alive(y)Food(x)]李(Li)吃花生(Peanuts)且仍然活著(Alive)。Eat(Li,Peanuts)∧Alive(Li)張(Zhang)吃任何李吃的東西。(x)[Eat(Li,x)Eat(Zhang,x)]王喜歡花生。Like(Wang,Peanuts)減少謂詞數(shù)12/16/2022814.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題②標(biāo)準(zhǔn)化——將事實公式和取反后的目標(biāo)公式分別標(biāo)準(zhǔn)化為子句，并組成子句集S。王(Wang)喜歡(Like)所有種類的食物(Food)。(x)[Food(x)Like(Wang,x)]Food(x1)∨Like(Wang,x1)蘋果(Apples)是食物。Food(Apples)Food(Apples)任何一個東西，若任何人吃了(Eat)它都不會被害死(Killed)，則該東西是食物。(x)(y)[Eat(y,x)∧Alive(y)Food(x)]Eat(y,x2)∨

Alive(y)∨Food(x2)12/16/2022824.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題②標(biāo)準(zhǔn)化——將事實公式和取反后的目標(biāo)公式分別標(biāo)準(zhǔn)化為子句，并組成字句集S。李(Li)吃花生(Peanuts)且仍然活著(Alive)。Eat(Li,Peanuts)∧Alive(Li)Eat(Li,Peanuts)Alive(Li)張(Zhang)吃任何李吃的東西。(x)[Eat(Li,x)Eat(Zhang,x)]Eat(Li,x3)∨Eat(Zhang,x3)王喜歡花生。Like(Wang,Peanuts)Like(Wang,Peanuts)取反12/16/2022834.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題③歸結(jié)演繹——應(yīng)用歸結(jié)演繹推理不斷生成歸結(jié)式以擴(kuò)展子句集S，直到生成空子句□。12/16/2022844.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題③歸結(jié)演繹——應(yīng)用歸結(jié)演繹方法不斷生成歸結(jié)式以擴(kuò)展子句集S，直到生成空子句□。12/16/2022854.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題③歸結(jié)演繹——應(yīng)用歸結(jié)演繹方法不斷生成歸結(jié)式以擴(kuò)展子句集S，直到生成空子句□。12/16/2022864.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題③歸結(jié)演繹——應(yīng)用歸結(jié)演繹方法不斷生成歸結(jié)式以擴(kuò)展子句集S，直到生成空子句□。12/16/2022874.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題③歸結(jié)演繹——應(yīng)用歸結(jié)演繹方法不斷生成歸結(jié)式以擴(kuò)展子句集S，直到生成空子句□。目標(biāo)公式得證歸結(jié)反演樹12/16/2022884.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)反演系統(tǒng)例6、歸4.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)策略歸結(jié)反演面臨大子句集S引起演繹效率問題選擇有利于導(dǎo)致快速產(chǎn)生空子句□的子句對進(jìn)行歸結(jié)支持集；線性輸入；單文字子句優(yōu)先；祖先過濾；歸結(jié)反演技術(shù)并未在定理自動證明以外的領(lǐng)域得到廣泛應(yīng)用。12/16/2022894.4歸結(jié)演繹推理

3）歸結(jié)反演——歸結(jié)策略歸結(jié)反演面臨4.4歸結(jié)演繹推理

3）歸結(jié)反演例:自然數(shù)都是大于零的數(shù)；所有整數(shù)不是偶數(shù)就是奇數(shù)；偶數(shù)除以2是整數(shù)。求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。證明：前提：F1：x(N(x)GZ(x)I(x))F2：x(I(x)E(x)O(x))F3：x(E(x)I(h(x)))結(jié)論：G：x(N(x)O(x)I(h(x)))F1、F2、F3及G化為子句集：（1）N(x)GZ(x)（2）N(y)I(y)（3）I(z)E(z)O(z)12/16/2022904.4歸結(jié)演繹推理

3）歸結(jié)反演例:自然數(shù)都是大于零的數(shù)4.4歸結(jié)演繹推理

3）歸結(jié)反演（4）E(u)I(h(u))（5）N(c)（6）O(c)（7）I(h(c))歸結(jié)：（8）I(c)((2),(5),c/y)（9）I(c)E(c)((3),(6),c/z)（10）E(c)((8),(9))（11）I(h(c))((4),(10),c/u)（12）((7),(11))12/16/2022914.4歸結(jié)演繹推理

3）歸結(jié)反演（4）E4.4歸結(jié)演繹推理

3）歸結(jié)反演歸結(jié)演繹樹：N(y)I(y)N(c)I(z)E(z)O(z)O(c)I(c)I(c)E(c)

E(c)E(u)I(h(u))

I(h(c))I(h(c))12/16/2022924.4歸結(jié)演繹推理

3）歸結(jié)反演歸結(jié)演繹樹：12/10/4.4歸結(jié)演繹推理

3）歸結(jié)反演某公司招聘工作人員，A，B，C三人應(yīng)試，經(jīng)面試后，公司表示如下想法：（1）三人中至少錄取一人。（2）如果錄取A而不錄取B，則一定錄取C。（3）如果錄取B，則一定錄取C。用歸結(jié)反演法證明：公司一定錄取C。（提示：設(shè)用P(x)表示錄取x）12/16/2022934.4歸結(jié)演繹推理

3）歸結(jié)反演某公司招聘工作人員，A，4.4歸結(jié)演繹推理

3）歸結(jié)反演把公司的想法用謂詞公式表示如下：（1）三人中至少錄取一人。P(A)∨P(B)∨P(C)（2）如果錄取A而不錄取B，則一定錄取C。P(A)∧P(B)P(C)（3）如果錄取B，則一定錄取C。P(B)P(C)把要求證的問題否定，并用謂詞公式表示出來：公司一定錄取CP(C)12/16/2022944.4歸結(jié)演繹推理

3）歸結(jié)反演把公司的想法用謂詞公式表4.4歸結(jié)演繹推理

3）歸結(jié)反演把上述公式化成子句集①P(A)∨P(B)∨P(C)②P(A)∨P(B)∨

P(C)③P(B)∨P(C)④P(C)應(yīng)用歸結(jié)反演：①②P(B)∨P(C)③P(C)④12/16/2022954.4歸結(jié)演繹推理

3）歸結(jié)反演把上述公式化成子句集①②4.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答歸結(jié)反演可實現(xiàn)問題回答系統(tǒng)目標(biāo)公式往往受存在量詞約束，如(x)W(x)；不僅證明目標(biāo)公式為真T；回答提取——給出使W(x)為真T的x的某個取值。問題回答系統(tǒng)分為2個階段：①歸結(jié)反演——證明目標(biāo)公式為真T②回答提取對于標(biāo)準(zhǔn)化取反的目標(biāo)公式而產(chǎn)生的子句（稱為目標(biāo)子句）G,建立其重言式（永真式）G∨G；以G∨G取代G,重復(fù)已進(jìn)行過的歸結(jié)演繹過程，建立修改證明樹。結(jié)果——修改證明樹的樹根不再是空子句□，而是G，且G中的變量已為其置換項取代，實現(xiàn)了回答提取。12/16/2022964.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答歸結(jié)反演4.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提取問題回答的應(yīng)用——食物問題已知下列事實為真，王(Wang)喜歡(Like)所有種類的食物(Food)。蘋果(Apples)是食物。任何一個東西，若任何人吃了(Eat)它都不會被害死(Killed)，則該東西是食物。李(Li)吃花生(Peanuts)且仍然活著(Alive)。張(Zhang)吃任何李吃的東西。證明：王喜歡花生。問題：張吃什么食物？12/16/2022974.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提4.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提取問題回答的應(yīng)用——食物問題(1)形式化王(Wang)喜歡(Like)所有種類的食物(Food)。(x)[Food(x)Like(Wang,x)]蘋果(Apples)是食物。Food(Apples)任何一個東西，若任何人吃了(Eat)它都不會被害死(Killed)，則該東西是食物。(x)(y)[Eat(y,x)∧Alive(y)Food(x)]李(Li)吃花生(Peanuts)且仍然活著(Alive)。Eat(Li,Peanuts)∧Alive(Li)張(Zhang)吃任何李吃的東西。(x)[Eat(Li,x)Eat(Zhang,x)]問題“張吃什么食物？”形式化為目標(biāo)公式(x)[Food(x)∧Eat(Zhang,x)]12/16/2022984.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提4.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提取問題回答的應(yīng)用——食物問題(2)標(biāo)準(zhǔn)化目標(biāo)子句G目標(biāo)公式取反各個子句變量不要重名12/16/2022994.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提4.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提取問題回答的應(yīng)用——食物問題①歸結(jié)反演歸結(jié)反演樹(x)[Food(x)∧Eat(Zhang,x)]12/16/20221004.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提4.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提取問題回答的應(yīng)用——食物問題②回答提取——(1)建立重言式G∨G目標(biāo)子句G目標(biāo)公式G目標(biāo)子句G建立重言式G∨G取反12/16/20221014.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提4.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提取問題回答的應(yīng)用——食物問題②回答提取——(2)以G∨G取代G,重復(fù)已進(jìn)行過的歸結(jié)演繹過程，建立修改證明樹。建立修改證明樹過程中：1、重言式G∨G中的G并不真正參與歸結(jié)演繹；2、G∨G取代G重復(fù)歸結(jié)演繹過程，只是為了使G中的變量隨著G中出現(xiàn)的變量置換而同時得到置換。12/16/20221024.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提修改證明樹12/16/2022103修改證明樹12/10/20221034.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提取問題回答的應(yīng)用——食物問題②回答提取——(2)以G∨G取代G,重復(fù)已進(jìn)行過的歸結(jié)演繹過程，建立修改證明樹。建立修改證明樹過程中：1、重言式G∨G中的G并不真正參與歸結(jié)演繹；2、G∨G取代G重復(fù)歸結(jié)演繹過程，只是為了使G中的變量隨著G中出現(xiàn)的變量置換而同時得到置換。3、①歸結(jié)反演和②回答提取可以合為一體進(jìn)行，一次性生成修改證明樹。避免誤用G參與歸結(jié)，可以用特定的符號替代G。例如、ANSWER(x1,x2,…,xn)，xi是G中的變量。12/16/20221044.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答例7、提修改證明樹12/16/2022105修改證明樹12/10/20221054.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答從實用的角