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

第4章

確定性推理本章介紹：

自然演繹推理

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

推理規(guī)則：P規(guī)則：在推理的任何步驟上都可引入前提T規(guī)則：推理時(shí)，如果前面步驟中有一個(gè)或多個(gè)公式永真蘊(yùn)涵公式S，則可把S引入推理過程中。CP規(guī)則：如果能從R和前提集合中推出S來，則可從前提集合推出來。反證法：，當(dāng)且僅當(dāng)。即：Q為P的邏輯結(jié)論，當(dāng)且僅當(dāng)是不可滿足的。7/28/20237假言推理表示：由及P為真，可推出Q為真

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

7/28/20238避免產(chǎn)生兩類錯(cuò)誤：肯定后件(Q)的錯(cuò)誤：希望通過肯定后件Q推出前件P為真否定前件(P)的錯(cuò)誤：希望通過否定前件P推出后件Q為假7/28/20239例：

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

一、合式公式7/28/202312

一、合式公式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)]7/28/202313

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

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

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

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

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

一、合式公式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)7/28/202319

一、合式公式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)7/28/202320

一、合式公式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)7/28/202321

二、合式公式的標(biāo)準(zhǔn)化1、標(biāo)準(zhǔn)化需求常見的基于謂詞演算的推理：歸結(jié)反演、(正向/逆向)演繹推理要求以量詞前束范式來表示合式公式量詞前束范式形式如下：(Q1x1)(Q2x2)…(Qkxk)M，其中M——母式，不包括任何量詞；Qixi——Qi可以是量詞符號(hào)或；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或其取反7/28/202322

二、合式公式的標(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或其取反7/28/202323定義

設(shè)F為一謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公式的最前面，而它們的轄域?yàn)檎麄€(gè)公式，則稱F為前束范式(prenexnormalform)。一般地，前束范式可以寫成:其中

為前綴，是一個(gè)由全稱量詞或存在量詞組成的量詞串，為母式，它是一個(gè)不含任何量詞的謂詞公式。前束標(biāo)準(zhǔn)型在一階邏輯中，為了簡(jiǎn)化定理證明程序需要引入所謂的“前束標(biāo)準(zhǔn)型”。7/28/202324

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

為了把一個(gè)公式化為前束范式，首先看一下包含一階邏輯特有的等價(jià)式對(duì)，如下所示。

前束標(biāo)準(zhǔn)型7/28/202325在上述等價(jià)公式對(duì)中，F(xiàn)(x)和H(x)都表示含未量化變量x的公式，G表示不含未量化變量x的公式，Q1,Q2

或?yàn)榛驗(yàn)椤?duì)(3)和(4)，要求z不出現(xiàn)在F(x)中，并且符合約束變量的換名原則。

前束標(biāo)準(zhǔn)型7/28/202326

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

(1)使用等價(jià)式中的連接詞轉(zhuǎn)化規(guī)律消去公式中的連接詞→,←→

。

(2)反復(fù)使用雙重否定律和德·摩根律將“┓(或～)”移到原子之前。

(3)必要時(shí)重新命名量化的變量。

(4)使用量詞分配律和等價(jià)式，把所有量詞都移到整個(gè)公式的最左邊以得出一個(gè)范式。前束標(biāo)準(zhǔn)型7/28/202327

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

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

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程③內(nèi)移否定符號(hào)使否定只出現(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ū)分，所以為避免差錯(cuò)，必須換名；約束變量的虛元性進(jìn)行變換；(x)P(x)(y)P(y)(x)P(x)(y)P(y)7/28/202330⑤消去存在量詞Skolem標(biāo)準(zhǔn)化過程Step1:

化成前束范式:Step2:

使用下述方法可以消去前綴中存在的所有量詞：令是中出現(xiàn)的存在量詞。Case1:若在之前不出現(xiàn)全稱量詞，則選擇一個(gè)與M中出現(xiàn)的所有常量都不相同的新常量c，用c代替M中出現(xiàn)的所有xr，并且由前綴中刪去(Qrxr)。Case2:若在之前出現(xiàn)全稱量詞，則選擇一個(gè)與M中出現(xiàn)的任一函數(shù)符號(hào)都不相同的新m元函數(shù)符號(hào)f，用代替M中的所有xr

，并且由前綴中刪去(Qrxr)。

按上述方法刪去前綴中的所有存在量詞之后得出的公式稱為合式公式的Skolem標(biāo)準(zhǔn)型。替代存在量化變量的常量c(視為0元函數(shù))和函數(shù)f稱為Skolem函數(shù)。7/28/202331在公式中，的前面沒有全稱量詞，的前面有全稱量詞和

,在

的前面有全稱量詞，和。所以，在

中，用常數(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)型。7/28/202332

二、合式公式的標(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))]在多個(gè)的轄域內(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)]7/28/202333

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

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

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

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

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

(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)]}}7/28/202338

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

(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))]}}7/28/202339

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡(jiǎn)合式公式{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))]}}7/28/202340

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡(jiǎn)合式公式(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))]}}7/28/202341

二、合式公式的標(biāo)準(zhǔn)化2、合取范式的標(biāo)準(zhǔn)化過程例3、化簡(jiǎn)合式公式{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)化過程！7/28/2023424.4歸結(jié)演繹推理自動(dòng)定理證明一般表示形式為：F1∧F2∧…∧FnWF1,F2,…,Fn都是合式公式，表示公理或事實(shí)；W是合式公式，表示待證明的定理，稱為目標(biāo)公式；證明的方法可分兩大類：演繹法直接證明F1∧F2∧…∧FnW為永真；反證法間接證明(F1∧F2∧…∧FnW)為永假；證明F1∧F2∧…∧Fn∧W的永假即{F1,F2,…,Fn}∪{W}是一個(gè)矛盾集。4.4歸結(jié)演繹推理7/28/2023434.4歸結(jié)演繹推理海伯倫（Herbrand）提出的H域（海伯倫域）和海伯倫定理；為自動(dòng)定理證明奠定了理論基礎(chǔ)；魯賓遜（Robinson）提出的歸結(jié)原理；使自動(dòng)定理證明成為可能。7/28/2023444.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}7/28/2023454.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))}7/28/2023464.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))]7/28/2023474.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))]}為了消除子句間不必要的交互作用，保持子句的獨(dú)立性，需要做變量換名{P(A),P(y1)∨Q(A,z1)∨P(z1,g(z1)),P(f(A,y2))∨Q(A,z2)∨P(z2,g(z2))}7/28/202348例4.2

將合式公式化為子句形。解：（1）消去蘊(yùn)涵符號(hào)：這可以利用等價(jià)式：得到：x[(~P(x)[y[~P(y)P(f(x,y))]~y[~Q(x,y)P(y)]]]（2）減少否定符號(hào)的轄域，把“”移到緊靠謂詞的位置上：這可以利用下述等價(jià)式：例題7/28/202349得到：

x[(~P(x)[y[~P(y)P(f(x,y))]y[Q(x,y)~P(y)]]]（3）變量標(biāo)準(zhǔn)化：重新命名變?cè)共煌吭~約束的變?cè)胁煌拿郑簒[~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))]]]7/28/202350（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))]

7/28/202351（8）更改變量名，有時(shí)稱為變量分離標(biāo)準(zhǔn)化。于是有：

必須指出:一個(gè)子句內(nèi)的文字可以含有變量，但這些變量總是被理解為全稱量詞量化了的變量。7/28/2023524.4歸結(jié)演繹推理

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

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

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

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

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

2）歸結(jié)原理1、歸結(jié)方法(1)歸結(jié)式（消解式*）設(shè)有兩個(gè)子句C1=L∨C1’、C2=L∨C2’①從C1和C2中消去互補(bǔ)文字L和L；②C1’和C2’通過∨組成新的子句C=C1’∨C2’；稱C為C1和C2的歸結(jié)式（消解式*）；例4、兩個(gè)子句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’7/28/2023584.4歸結(jié)演繹推理

2）歸結(jié)原理1、歸結(jié)方法(2)歸結(jié)式性質(zhì)定理：兩個(gè)子句C1和C2的歸結(jié)式C是C1和C2的邏輯推論任一使子句C1和C2為真的解釋I，必使歸結(jié)式C為真；歸結(jié)式C為假的解釋I，子句C1或者C2為假；推論：設(shè)C1

和C2

是子句集S中的兩個(gè)子句，并以C作為它們的歸結(jié)式；通過往S中加入C而產(chǎn)生的擴(kuò)展子句集S’與子句集S在不可滿足的意義上是等價(jià)的！擴(kuò)展子句集S’子句集S不可滿足性等價(jià)7/28/2023594.4歸結(jié)演繹推理

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

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

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

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

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

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

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ǔ)性。7/28/2023654.4歸結(jié)演繹推理

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

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

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

，取其置換項(xiàng)t’，檢查是否與另一參數(shù)t合一；若不合一，則處理失??；參數(shù)對(duì)中沒有變量，則必須相同，否則合一處理失敗。7/28/2023684.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程匹配過程的例子P(x,y,x,g(x)),P(A,B,A,z)①兩個(gè)原子謂詞公式必須具有相同的謂詞和參數(shù)項(xiàng)個(gè)數(shù)；②從左到右逐個(gè)檢查每對(duì)參數(shù)項(xiàng)的可合一性；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；③若每對(duì)參數(shù)項(xiàng)都可合一，則合一處理成功。建立置換S1={A/x,B/y,g(x)/z}

7/28/2023694.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))變量的置換必須在整個(gè)子句范圍內(nèi)進(jìn)行7/28/2023704.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))7/28/2023714.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ǔ)文字兩個(gè)子句可以有多于一對(duì)的互補(bǔ)文字7/28/2023724.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程7/28/2023734.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程7/28/2023744.4歸結(jié)演繹推理

2）歸結(jié)原理2、歸結(jié)推理過程(2)謂詞邏輯中的歸結(jié)推理過程7/28/2023754.4歸結(jié)演繹推理

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

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

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

3）歸結(jié)反演——?dú)w結(jié)反演系統(tǒng)歸結(jié)反演的基本思路：要從作為事實(shí)的公式集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é)演繹推理，控制定理證明的全過程。7/28/2023794.4歸結(jié)演繹推理

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

3）歸結(jié)反演——?dú)w結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題①形式化——把以自然語言表示的事實(shí)和要證明的目標(biāo)形式化地表示為合式公式。王(Wang)喜歡(Like)所有種類的食物(Food)。(x)[Food(x)Like(Wang,x)]蘋果(Apples)是食物。Food(Apples)任何一個(gè)東西，若任何人吃了(Eat)它都不會(huì)被害死(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ù)7/28/2023814.4歸結(jié)演繹推理

3）歸結(jié)反演——?dú)w結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題②標(biāo)準(zhǔn)化——將事實(shí)公式和取反后的目標(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)任何一個(gè)東西，若任何人吃了(Eat)它都不會(huì)被害死(Killed)，則該東西是食物。(x)(y)[Eat(y,x)∧Alive(y)Food(x)]Eat(y,x2)∨

Alive(y)∨Food(x2)7/28/2023824.4歸結(jié)演繹推理

3）歸結(jié)反演——?dú)w結(jié)反演系統(tǒng)例6、歸結(jié)反演的應(yīng)用——食物問題②標(biāo)準(zhǔn)化——將事實(shí)公式和取反后的目標(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)取反7/28/2023834.4歸結(jié)演繹推理

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

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

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

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

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

3）歸結(jié)反演——?dú)w結(jié)策略歸結(jié)反演面臨大子句集S引起演繹效率問題選擇有利于導(dǎo)致快速產(chǎn)生空子句□的子句對(duì)進(jìn)行歸結(jié)支持集；線性輸入；單文字子句優(yōu)先；祖先過濾；歸結(jié)反演技術(shù)并未在定理自動(dòng)證明以外的領(lǐng)域得到廣泛應(yīng)用。7/28/2023894.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)7/28/2023904.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))7/28/2023914.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))7/28/2023924.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）7/28/2023934.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)7/28/2023944.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)④7/28/2023954.4歸結(jié)演繹推理

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

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

3）歸結(jié)反演——提取問題回答例7、提取問題回答的應(yīng)用——食物問題(1)形式化王(Wang)喜歡(Like)所有種類的食物(Food)。(x)[Food(x)Like(Wang,x)]蘋果(Apples)是食物。Food(Apples)任何一個(gè)東西，若任何人吃了(Eat)它都不會(huì)被害死(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)]7/28/2023984.4歸結(jié)演繹推理

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

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

3）歸結(jié)反演——提取問題回答例7、提取問題回答的應(yīng)用——食物問題②回答提取——(1)建立重言式G∨G目標(biāo)子句G目標(biāo)公式G目標(biāo)子句G建立重言式G∨G取反7/28/20231014.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)的變量置換而同時(shí)得到置換。7/28/2023102修改證明樹7/28/20231034.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)的變量置換而同時(shí)得到置換。3、①歸結(jié)反演和②回答提取可以合為一體進(jìn)行，一次性生成修改證明樹。避免誤用G參與歸結(jié)，可以用特定的符號(hào)替代G。例如、ANSWER(x1,x2,…,xn)，xi是G中的變量。7/28/2023104修改證明樹7/28/20231054.4歸結(jié)演繹推理

3）歸結(jié)反演——提取問題回答從實(shí)用的角度，目標(biāo)公式或許會(huì)取更為復(fù)雜的形式①目標(biāo)公式取反后的化簡(jiǎn)結(jié)果是多個(gè)子句的合取(x)(y){[A(x)∧B(x)]

∨[C(y)∧D(y)]}取反化簡(jiǎn)后[A(x)∨

B(x)]

∧

[C(y)∨

D(y)]建立2個(gè)重言式A(x)∨

B(x)∨[A(x)∧B(x)]

C(y)∨

D(y)∨[C(y)∧D(y)]②目標(biāo)公式含有全稱量詞(x)(y)(z)(w)P(x,y,z,w)取反后(x)(y)(z)(w)P(x,y,z,w)消去量詞P(A,y,z,g(y,z))如何處理函數(shù)g(y,z)？7/28/20231064.5基于規(guī)則的演繹推理歸結(jié)演繹推理優(yōu)點(diǎn)：簡(jiǎn)單易行——只要將問題求解的依據(jù)（事實(shí)或公式）和目標(biāo)以合式公式形式化描述，標(biāo)準(zhǔn)化為子句集S，就可交由歸結(jié)反演系統(tǒng)和問答系統(tǒng)執(zhí)行。缺點(diǎn)：①歸結(jié)演繹并非人類的自然思維方式；不利于人們從自然思維的角度提供問題求解所需的知識(shí)；難以建立高水平的問題求解系統(tǒng)，如專家系統(tǒng)；②丟失隱含于合式公式的啟發(fā)式知識(shí)；必須將合式公式標(biāo)準(zhǔn)化為高度統(tǒng)一的子句集，P∧QR簡(jiǎn)化為P∨Q∨R后，丟失了“P∧Q為真導(dǎo)致R為真”的啟發(fā)式知識(shí)；效率低下，難以適應(yīng)于復(fù)雜的應(yīng)用；子句演繹系統(tǒng)7/28/20231074.5基于規(guī)則的演繹推理歸結(jié)演繹推理優(yōu)點(diǎn)：簡(jiǎn)單易行——只要將問題求解的依據(jù)（事實(shí)或公式）和目標(biāo)以合式公式加以形式化描述，就可交由歸結(jié)反演系統(tǒng)和問答系統(tǒng)執(zhí)行。缺點(diǎn)：①歸結(jié)演繹并非人類的自然思維方式；②丟失隱含于合式公式的啟發(fā)式知識(shí)；基于規(guī)則的演繹推理保留蘊(yùn)涵式，將其作為推理規(guī)則，用于直接推導(dǎo)目標(biāo)公式；優(yōu)點(diǎn)：①符合人的自然思維方式；②通過規(guī)則（作為啟發(fā)式知識(shí)）更有效地引導(dǎo)演繹推理過程。子句演繹系統(tǒng)與或句演繹系統(tǒng)7/28/20231084.5基于規(guī)則的演繹推理基于規(guī)則的演繹推理將求解問題所需的知識(shí)分為2類：規(guī)則——表示為蘊(yùn)涵式，作為啟發(fā)式知識(shí)（表示應(yīng)用域中存在的規(guī)律和法則），引導(dǎo)演繹推理過程。事實(shí)——表示為文字與或形，作為應(yīng)用規(guī)則進(jìn)行推理時(shí)參考的有關(guān)問題狀態(tài)和環(huán)境。任務(wù)：從給定的事實(shí)和規(guī)則，證明某個(gè)目標(biāo)公式成立。分類：正向演繹——從事實(shí)出發(fā)，應(yīng)用規(guī)則不斷推導(dǎo)出中間結(jié)果作為新的事實(shí)，直至推導(dǎo)出目標(biāo)公式。逆向演繹——從目標(biāo)公式出發(fā)，逆向應(yīng)用規(guī)則不斷推導(dǎo)出子目標(biāo)，直至所有子目標(biāo)就是給定的事實(shí)為止。7/28/20231094.5基于規(guī)則的演繹推理主要內(nèi)容：基于規(guī)則的正向演繹推理（掌握）基于規(guī)則的逆向演繹推理（掌握）7/28/20231104.5.1基于規(guī)則的正向演繹推理

1）問題求解的規(guī)范表示正向演繹推理要求將問題求解的描述分為3個(gè)部分：事實(shí)規(guī)則集目標(biāo)為便于演繹推理，需將表示它們的合式公式簡(jiǎn)化為標(biāo)準(zhǔn)形式，并加以適當(dāng)限制。(1)事實(shí)不必化簡(jiǎn)為子句集，只需規(guī)范為不含蘊(yùn)涵符號(hào)的文字與或形?；?jiǎn)事實(shí)表達(dá)式7/28/20231114.5.1基于規(guī)則的正向演繹推理

1）問題求解的規(guī)范表示(1)事實(shí)表示為不含蘊(yùn)涵符號(hào)的文字與或形。量詞分配(x)[P(x)∧Q(x)](x)P(x)∧(x)

Q(x)變量換名w/y化簡(jiǎn)事實(shí)表達(dá)式7/28/20231124.5.1基于規(guī)則的正向演繹推理

1）問題求解的規(guī)范表示正向演繹推理要求將問題求解的描述分為3個(gè)部分：事實(shí)規(guī)則目標(biāo)為便于演繹推理，需將表示它們的合式公式簡(jiǎn)化為標(biāo)準(zhǔn)形式