第3章基于謂詞邏輯的機器推理詳解課件

第3章基于謂詞邏輯的機器推理7/24/20231內(nèi)容3.1機器推理概述3.2謂詞邏輯簡介3.3自然演繹推理3.4歸結演繹推理3.5歸結原理與PROLOG程序3.6

基于規(guī)則的演繹推理7/24/202323.1機器推理概述（1）機器推理推理是人腦的一個基本功能和重要功能，幾乎所有的人工智能領域都與推理有關。因此，要實現(xiàn)人工智能，就必須將推理的功能賦予機器，實現(xiàn)機器推理。機器推理也稱為是計算機推理，或自動推理，它也是人工智能的核心課題之一。自動定理證明：是機器推理的一種重要應用，它是利用計算機證明非數(shù)值性的結果，很多非數(shù)值領域的任務如醫(yī)療診斷、信息檢索、規(guī)劃制定和難題求解等方法都可以轉化一個定理證明問題。7/24/20233自動定理證明的基本方法：3.1機器推理概述（2）定理證明器：它是研究一切可判定問題的證明方法。魯濱遜的歸結原理。自然演繹法：該方法依據(jù)推理規(guī)則從前提和公理中可以推出許多定理，如果待證明的定理在其中則定理得證。LT程序、證明平面幾何的程序。7/24/20234基于歸結原理的自動定理證明過程：3.1機器推理概述（3）定理的自然語言描述定理的謂詞公式描述子句集生成子句集定理得證應用歸結規(guī)則和歸結策略自然語言處理生成謂詞公式已知前提：F1：自然數(shù)都是大于零的整數(shù)。F2：所有整數(shù)不是偶數(shù)就是奇數(shù)。F3：偶數(shù)除以2是整數(shù)。結論G：所有自然數(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(s(x)))G:x(N(x)(I(s(x))O(x)))7/24/20235基于規(guī)則的演繹推理

：把已知判斷中的知識表示成規(guī)則的形式（包括F-規(guī)則和B-規(guī)則），運用規(guī)則從已知判斷的事實或待證明的結論出發(fā)進行推理的過程.3.1機器推理概述（4）7/24/202363.2謂詞邏輯簡介3.2.1基于命題邏輯的知識表示3.2.2謂詞邏輯3.2.3

基于謂詞邏輯的知識表示7/24/202373.2.1基于命題邏輯的知識表示（1）命題（proposition）：是具有真假意義的語句。命題代表人們進行思維時的一種判斷，或者是否定，或者是肯定。命題可以用命題符號表示。用命題符號可以表示簡單的邏輯關系和推理。

P:今天天氣好Q:去旅游S1：我有名字S2：你有名字PQ表示：如果今天天氣好，就去旅游。此時，如果P（今天天氣好）成立，則可以得到結論Q（去旅游）7/24/202383.2.1基于命題邏輯的知識表示（2）對于復雜的知識，命題符號能力不夠。無法把所描述的客觀事物的結構及邏輯特征反映出來。無法把不同事物間的共同特征表達出來。F：老李是小李的父親。S1：我有名字S2：你有名字所有的人都有名字：SIS2S3…

7/24/202393.2.2謂詞邏輯（1）謂詞(predicate)：一般形式為P（x1,x2,…,

xn

）

P為謂詞名，用于刻畫個體的性質、狀態(tài)或個體間的關系。

x1，x2，…，

xn是個體，表示某個獨立存在的事物或者某個抽象的概念。S(x):x是學生；P(x,y):x是y的父親。個體變元的變化范圍稱為個體域。包攬一切事物的集合稱為全總個體域。7/24/2023103.2.2謂詞邏輯（2）函數(shù)：為了表達個體之間的對應關系，引入數(shù)學中函數(shù)概念和記法。用形如f(x1，x2，…，xn)來表示個體變元對應的個體y，并稱之為n元個體函數(shù)，簡稱函數(shù)。函數(shù)father(x):值為x的父親。謂詞D(father(Li)):表示x的父親是醫(yī)生，值為真或假。7/24/2023113.2.2謂詞邏輯（3）為了表示命題中出現(xiàn)的“全部”、“所有”、“一切”、“任一”或“凡是”等意義，引入全稱量詞，記為x

。為了表示命題中出現(xiàn)的“存在”、“某些”、“有一個”等意義，引入存在量詞，記為x

。如：“某些學生對某些課外活動感興趣”

S(x)表示x是學生，L(y)表示y是課外活動，

I(x,y)表示x對y感興趣。

7/24/2023123.2.2謂詞邏輯（4）定義3.2：項（1）個體常元和變元都是項。（2）f是n元函數(shù)符號，若t1，t2，…，tn是項，則f（t1，t2，…，tn）是項。（3）只有有限次使用（1），（2）得到的符號串才是項。7/24/2023133.2.2謂詞邏輯（5）定義3.3：原子公式設P為n元謂詞符號，t1，t2，…，tn為項，P（t1，t2，…，tn）稱為原子謂詞公式，簡稱原子或原子公式。7/24/2023143.2.2謂詞邏輯（6）定義3.4：謂詞公式（1）原子公式是謂詞公式。（2）若A、B是謂詞公式，則?A，AB，AB，AB，A←→B，xA，xA也是謂詞公式。（3）只有有限步應用（1）（2）生成的公式才是謂詞公式。謂詞公式亦稱為謂詞邏輯中的合適（式）公式，記為Wff。符號約定：謂詞－大寫字母；P(x,y)函數(shù)－小寫字母；f(x)變量－x、y、z、u、v……；常量－a、b、c…….。P(a,y)7/24/2023153.2.2謂詞邏輯（7）轄域：緊接于量詞之后被量詞作用（即說明）的謂詞公式稱為該量詞的轄域。指導變量：量詞后的變量為指導變量。約束變量：在一個量詞轄域中與該量詞的指導變元相同的變量稱為約束變量。自由變量：謂詞公式中除了約束變量之外的變量。

（1）（2）（3）7/24/2023163.2.2謂詞邏輯（8）一個變元在一個公式中既可以約束出現(xiàn)，也可以自由出現(xiàn)，為了避免混淆，通過改名規(guī)則改名：對需要改名的變元，應同時更改該變元在量詞及其轄域中的所有出現(xiàn)。新變元符號必須是量詞轄域內(nèi)原先沒有的，最好是公式中也未出現(xiàn)過的。xG(x)P（x）

xG(x)P（y）7/24/2023173.2.2謂詞邏輯（9）謂詞公式與命題的區(qū)別與聯(lián)系謂詞公式是命題函數(shù)。一個謂詞公式中所有個體變元被量化，謂詞公式就變成了一個命題。從謂詞公式得到命題的兩種方法：給謂詞中的個體變元代入個體常元；把謂詞中的個體變元全部量化。例：P（x）表示“x是素數(shù)”

xP（x），xP（x），P（a）都是命題7/24/2023183.2.2謂詞邏輯（10）全稱命題：

xP(x)等價于P(a1)P(a2)…P(an)

特稱命題

xG(x)等價于P(a1)P(a2)…P(an)一階謂詞：僅個體變元被量化的謂詞。二階謂詞：個體變元被量化，函數(shù)符號和謂詞符號也被量化。

P

xP（x）7/24/2023193.2.2謂詞邏輯（11）定義3.5：合取范式（ConjunctiveNormalForm）

設A為如下形式的謂詞公式：B1

B2

…

Bn其中Bi（i=1,2,…，n）形如L1

L2…

Lm，Lj（j=1，2,…，m）為原子公式或其否定，則A稱為合取范式。例就是一個合取范式7/24/2023203.2.2謂詞邏輯（12）定義3.6：析取范式（DisjunctiveNormalForm）設A為如下形式的謂詞公式：B1

B2…

Bn其中Bi（i=1,2,…，n）形如L1

L2

…

Lm，Lj（j=1，2,…，m）為原子公式或其否定，則A稱為析取范式。例如就是一個析取范式7/24/2023213.2.2謂詞邏輯（13）定義3.7謂詞公式的解釋

設D為謂詞公式P的個體域，若對P中的個體常量、函數(shù)和謂詞按如下規(guī)定賦值：（1）為每個個體常量指派D中的一個元素；（2）為每個n元函數(shù)指派一個從Dn到D的映射，其中

Dn＝{(x1,x2,…,xn)/x1,x2,…,xn∈

D}

（3）為每個n元謂詞指派一個從Dn到{F,T}的映射。則稱這些指派為公式P在D上的一個解釋。7/24/2023223.2.2謂詞邏輯（14）例：設個體域D＝{1,2},

求公式在D上的解釋，并指出在每一種解釋下公式A的真值。解：設公式A中對個體常量b、函數(shù)f（x）指派的真值分別為：

對謂詞指派的真值為：

7/24/2023233.2.2謂詞邏輯（15）在此解釋下，由于當x=1時，有y=2，使得：：所以為T。當x＝2時，有y=2，使得所以為T。所以公式A在此解釋下真值為T。

7/24/2023243.2.2謂詞邏輯（16）定義3.8：謂詞公式的永真如果謂詞公式P對個體域D上的任何一個解釋都取得真值T，則稱P在D上是永真的；如果P在全總個體域上永真，則稱P永真。7/24/2023253.2.2謂詞邏輯（17）定義3.9：謂詞公式的可滿足性對于謂詞公式P，如果在個體域D上至少存在一個解釋使得公式P在此解釋下的真值為，則稱公式P在D上是可滿足的。7/24/2023263.2.2謂詞邏輯（18）定義3.9：謂詞公式的永假如果謂詞公式P對于個體域D上的任何一個解釋都取得真值F，則稱P在D上是永假的；如果P在全總個體域上永假，則稱P永假。7/24/2023273.2.3基于謂詞邏輯的知識表示（1）知識表示的步驟：分析定理中的對象、對象的屬性及對象之間的關系，定義謂詞和函數(shù)。定理中的事實通常用謂詞公式的與或型表示，規(guī)則用蘊含式表示，據(jù)此定義謂詞公式。注意：用謂詞表示命題時，一般取全總個體域，再采用使用限定謂詞的方法來指出每個個體變元的個體域。對量詞的處理按下述原則：(2)對存在量詞，把限定詞作為一個合取項加入。即x(P(x)…)(1)對全稱量詞，把限定詞作為蘊含式之前件加入。即x（P（x）…）7/24/2023283.2.3基于謂詞邏輯的知識表示（2）表示“對個體域中所有的（或任一個）個體”。記為x全稱量詞表示“在個體域中存在個體”。記為x存在量詞如：“凡是人都有名字”

用M（x）表示“x是人”，N（x）表示“x有名字”x（M（x）N（x））如：“存在不是偶數(shù)的整數(shù)”用G（x）表示“x是整數(shù)”，E（x）表示“x是偶數(shù)”x（G（x）?E（x））7/24/2023293.2.3基于謂詞邏輯的知識表示（2）例3.2設有如下命題：（1）小明比他的哥哥學習努力。

定義謂詞：

：x比y學習努力定義函數(shù)：：x的哥哥謂詞公式表示為：

7/24/2023303.2.3基于謂詞邏輯的知識表示（3）（2）對于所有的自然數(shù)，均有。定義謂詞：

：x是自然數(shù)：x大于等于y

定義函數(shù)：：x與y的和

謂詞公式表示為：

7/24/2023313.2.3基于謂詞邏輯的知識表示（4）（3）某些人對某些食物過敏。定義謂詞：

：x是人：x是食物：x對y過敏定義函數(shù)：謂詞公式表示為：7/24/2023323.2.3基于謂詞邏輯的知識表示（5）例3.3用謂詞公式表示下述命題。已知前提：F1：自然數(shù)都是大于零的整數(shù)。F2：所有整數(shù)不是偶數(shù)就是奇數(shù)。F3：偶數(shù)除以2是整數(shù)。結論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。首先定義如下謂詞：

N(x):x是自然數(shù)。I(x):x是整數(shù)。E(x):x是偶數(shù)。

O(x):x是奇數(shù)。GZ(x):x大于零。定義函數(shù)s(x):x除以2。7/24/2023333.2.3基于謂詞邏輯的知識表示（6）將上述各語句翻譯成謂詞公式：F1：自然數(shù)都是大于零的整數(shù)。x(N(x)GZ(x)I(x))F2：所有整數(shù)不是偶數(shù)就是奇數(shù)。x(I(x)(E(x)O(x)))F3：偶數(shù)除以2是整數(shù)。

x(E(x)I(s(x)))所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。

G:x(N(x)(I(s(x))O(x)))

7/24/2023343.2.3基于謂詞邏輯的知識表示（7）例3.4設在一個房間里，a和b是兩張桌子，a處桌子上放有一個盒子box，c處有一個機器人Robot，為了讓機器人從c處出發(fā)把盒子從a處拿到b處的桌子上，然后再回到c處，用謂詞邏輯描述從初始狀態(tài)到目標狀態(tài)的機器人操作過程。解：定義謂詞：表示x是桌子：表示機器人Robot手是空的：表示機器人Robot在x處：機器人Robot拿著Box

：積木塊在x上7/24/2023353.2.3基于謂詞邏輯的知識表示（8）初始狀態(tài)為：目標狀態(tài)為：7/24/2023363.2.3基于謂詞邏輯的知識表示（9）以機器人的操作PICKUP(a)為例來說明操作進行的條件和動作：條件：刪除：增加：

7/24/2023373.3自然演繹推理（1）自然演繹推理

利用一階謂詞推理規(guī)則的符號表示形式，可以把關于自然語言的邏輯推理問題，轉化為符號表達式的推演變換。這種推理十分類似于人們用自然語言推理的思維過程，因而稱為自然演繹推理。常用邏輯等價式常用推理定律

7/24/202338常用邏輯等價式（1）7/24/202339常用邏輯等價式（2）7/24/202340常用推理定律7/24/2023413.3自然演繹推理（2）例

設有前提：（1）凡是大學生都學過計算機；（2）小王是大學生。試問：小王學過計算機嗎？解：令S（x）：x是大學生M（x）：x學過計算機；a：小王上面命題用謂詞公式表示為：[前提][(1),US][前提][(2),(3),I3]我們進行形式推理：M(a)，即小王學過計算機。xA(x)=>A(y)y是個體域中任一確定元素(AB)A=>B7/24/2023423.3自然演繹推理（3）例3.5設有前提：（1）有些病人相信所有的醫(yī)生。（2）病人都不相信騙子。求證：所有的醫(yī)生都不是騙子。證明：定義謂詞：：x是病人：x是醫(yī)生：x是騙子：x相信y將前提和要證明的結論轉化為謂詞公式：前提：（1）（2）結論：7/24/2023433.3自然演繹推理（4）（2）[（1），存在指定規(guī)則]（3）[（2），簡化律]（4）[前提引入]（5）[（4），全稱指定規(guī)則]（6）[（3）（5），假言推理]（7）（1）[前提引入][（6），全稱指定規(guī)則]7/24/2023443.3自然演繹推理（5）（8）[（7），逆反律]（9）[（2），化簡規(guī)則]（10）[（9），全稱指定規(guī)則]（11）[（8）（10），假言三段論]（12）[（11），全稱推廣規(guī)則]7/24/2023453.4歸結演繹推理3.4.1子句集3.4.2命題邏輯中的歸結原理3.4.3替換與合一3.4.4謂詞邏輯中的歸結原理3.4.5利用歸結原理求解問題7/24/2023463.4.1子句集(1)原子謂詞公式及其否定稱為文字定義3.11任何文字的析取稱為一個子句。

由n個文字組成的子句叫n文字子句；1-文字子句叫單元子句；不含任何文字的子句稱為空子句，記為□或NIL。由子句構成的集合稱為子句集。子句集中子句和子句之間的關系是合取關系，所以，子句集就是一個合取范式。7/24/2023473.4.1子句集(2)謂詞公式例

x{yP(x,y)?y[Q(x,y)R(x,y)]}子句集例

{?P(x,f(x))Q(x,g(x)),?P(y,f(y))?R(y,g(y))}謂詞公式與子句集有哪些區(qū)別？“?”作用原子謂詞沒有量詞(、)合取范式元素之間變元不同定義3.12：對一個謂詞公式G，通過以下步驟所得的子句集S，稱為G的子句集（clauses）。

集合形式?jīng)]有蘊含詞、等值詞7/24/2023483.4.1子句集(3)例3.6：x{yP(x，y)?y[Q(x,y)R(x,y)]}由第一步可得：x{?yP(x，y)?y[?Q(x,y)R(x,y)]}1、消蘊含詞和等值詞

理論根據(jù)：AB?ABAB(?AB)(?BA)蘊含等價式問題:蘊含式y(tǒng)P(x，y)?y[Q(x,y)R(x,y)]的前件是？1：yP(x，y)2：P(x，y)

7/24/2023493.4.1子句集(4)子句集的特征“?”作用原子謂詞沒有量詞(、)合取范式元素之間變元不同集合形式?jīng)]有蘊含詞、等值詞7/24/2023503.4.1子句集(5)x{?yP(x，y)?y[?Q(x,y)R(x,y)]}

2、移動否定詞作用范圍，使其僅作用于原子公式

理論根據(jù)：?(?A)A?(AB)?A?B ?(AB)?A?B ?xP(x)x?P(x) ?xP(x)x?P

(x)雙重否定律摩根定律量詞轉換定律=>x{y?P(x，y)y?[?Q(x,y)R(x,y)]}

=>

x{y?P(x，y)y[?(?

Q(x,y))?R(x,y)]}=>

x{y?P(x，y)y[Q(x,y)?R(x,y)]}7/24/2023513.4.1子句集(6)子句集的特征“?”作用原子謂詞沒有量詞(、)合取范式元素之間變元不同集合形式?jīng)]有蘊含詞、等值詞7/24/2023523.4.1子句集(7)=>x{y?P(x，y)z[Q(x,z)?R(x,z)]}3、適當改名，使變量標準化即：對于不同的約束，對應于不同的變量x{y?P(x，y)y[Q(x,y)?R(x,y)]}問題:不同轄域的相同變元對應的約束相同嗎?7/24/2023533.4.1子句集(8)4、

消去存在量詞(Skolem化）,同時進行變元替換

原則：

①若該存在量詞不在任何全稱量詞的轄域內(nèi)，則用一個常量符號代替該存在量詞轄域內(nèi)的相應約束變元，

這個常量叫Skolem常量；②若該存在量詞在全稱量詞的轄域內(nèi)，則用這些全稱量詞指導變元的一個函數(shù)代替該存在量詞轄域內(nèi)的相應約束變元，這樣的函數(shù)稱為Skolem函數(shù)。理論依據(jù)：

xA（x）=>A（y）y是個體域中某一確定的元素。

存在指定規(guī)則7/24/2023543.4.1子句集(9)問題:為什么受全稱量詞約束的要用Skolem函數(shù)替換?而不能用常量替換？xyM（y，x）：對任意一個人x，都存在一個y，y是x的媽媽。若去掉存在量詞用常量a代替y，則變?yōu)椋簒M（a，x）：a是所有人的媽媽。實際上，引入Skolem函數(shù)，是由于存在量詞在全稱量詞的轄域之內(nèi)，其約束變元的取值完全依賴于全稱變量的取值。而Skolem函數(shù)反映了這種依賴關系。7/24/2023553.4.1子句集(10)x{y?P(x，y)z[Q(x,z)?R(x,z)]}=>x{?P(x，f(x))[Q(x，g(x))?R(x，g(x))]}=>

?P(x，f(x))[Q(x,g(x))?R(x,g(x))]5、消去所有全稱量詞。理論依據(jù)：

xA（x）=>A（y）y是個體域中任一確定的元素。

全稱指定規(guī)則7/24/2023563.4.1子句集(11)子句集的特征“?”作用原子謂詞沒有量詞(、)合取范式元素之間變元不同集合形式?jīng)]有蘊含詞、等值詞7/24/2023573.4.1子句集(12)=>[?P(x，f(x))Q(x,g(x))][?P(x，f(x))?R(x,g(x))]6、化公式為合取范式理論依據(jù)：A（BC）（AB）（AC）（AB）C（AC）（BC）?P(x，f(x))[Q(x,g(x))?R(x,g(x))]

分配律7/24/2023583.4.1子句集(13)子句集的特征“?”作用原子謂詞沒有量詞(、)合取范式元素之間變元不同集合形式?jīng)]有蘊含詞、等值詞7/24/2023593.4.1子句集(14)=>[?P(x，f(x))Q(x,g(x))][?P(y，f(y))?R(y,g(y))]7、適當改名，使子句間無同名變元=>{?P(x，f(x))Q(x,g(x)),?P(y，f(y))?R(y,g(y))}8、消去合取詞，以子句為元素組成一個集合S=>

?P(x，f(x))[Q(x,g(x))?R(x,g(x))]7/24/2023603.4.1子句集(15)消去蘊含詞和等值詞使否定詞僅作用于原子公式使量詞間不含同名指導變元消去存在量詞消去全稱量詞化公式為合取范式子句間無同名變元組成一個集合“?”作用原子謂詞沒有量詞(、)合取范式元素之間變元不同集合形式?jīng)]有蘊含詞、等值詞蘊含等價式雙重否定律、摩根定律、量詞轉換律存在指定、依賴關系全稱指定分配律7/24/2023613.4.1子句集(16)Skolem標準型在求子句集的過程中，消去存在量詞之后，把所有全稱量詞都依次移到式子的最左邊（或者把所有的量詞都依次移到式子最左邊，再消去存在量詞），再將右部的式子化為合取范式，這樣得到的式子就是Skolem標準型。x{y?P(x，y)z[Q(x,z)?R(x,z)]}=>x{?P(x，f(x))[Q(x,g(x))?R(x,g(x))]}=>x{[?P(x，f(x))Q(x,g(x))][?P(x，f(x))?R(x,g(x))]}{?P(x，f(x))Q(x,g(x)),?P(y，f(y))?R(y,g(y))}消去合取詞和全稱量詞，就得到了原公式的子句集7/24/2023623.4.1子句集(17)

引入Skolem函數(shù)，是由于存在量詞在全稱量詞的轄域內(nèi)，其約束變元的取值完全依賴于全稱量詞的取值。Skolem反映了這種依賴關系。但Skolem標準型與原公式一般并不等價。

有公式：

它的Skolem標準型是我們給出如下的解釋I：

D={0，1}，f(0)=1，f(1)=1，P(0，0)=T，P(0，1)=F，P(1，0)=T，P(1，1)=F

在此解釋下，G＝T,G’＝F7/24/2023633.4.1子句集(18)定理3.1謂詞公式G不可滿足當且僅當其子句集S不可滿足。定義3.13

公式G是公式F1、F2

、…

、Fn的邏輯結論（推論），當且僅當對每一個解釋I，如果F1、F2

、…

、Fn都為真，則G也為真。這時稱F1、F2

、…

、Fn為G的前提。

定理3.2

G是公式F1、F2、…、Fn的邏輯結論，當且僅當

F1

F2

…

Fn=>

G定理3.3

G是公式F1、F2、…、Fn的邏輯結論，當且僅當

F1

F2

…

Fn?

G

是不相容的。7/24/2023643.4.1子句集(19)例3.8化子句集已知前提：（1）自然數(shù)都是大于零的整數(shù)。（2）所有整數(shù)不是偶數(shù)就是奇數(shù)。（3）偶數(shù)除以2是整數(shù)。結論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)?；疐1

F2F3

?G的子句集。

F1:x(N(x)GZ(x)I(x))F2:x(I(x)(E(x)O(x)))F3:x(E(x)I(s(x)))G:x(N(x)(I(s(x))O(x)))7/24/2023653.4.1子句集(20)解：F1F2F3?G的子句集為（1）?N(x)GZ(x)（2）?N(y)I(y)（3）?I(z)E(z)O(z)（4）?E(u)I(s(u))（5）N(a)（6）?O(a)（7）?I(s(a))7/24/2023663.4.2命題邏輯中的歸結原理(1)歸結原理的提出歸結原理(principleofresolution)又稱消解原理,1965年魯濱遜（J.A.Robinson）提出，從理論上解決了定理證明問題。歸結原理提出的是一種證明子句集不可滿足性，從而實現(xiàn)定理證明的一種理論及方法。7/24/2023673.4.2命題邏輯中的歸結原理(2)定義3.14設L為一個文字，則L與?L為互補文字。

定義3.15設C1，

C2是命題邏輯中的兩個子句，C1中有文字L1，C2中有文字L2，且L1與L2互補，從C1、

C2中分別刪除L1、L2，再將剩余部分析取起來，構成的新子句為C12，則C12為C1、

C2的歸結式，C1、

C2稱為其歸結式的親本子句，稱L1、L2為消解基。例3.9設，則C1、

C2的歸結式為：

7/24/2023683.4.2命題邏輯中的歸結原理(3)定理3.4歸結式是其親本子句的邏輯結果。證明：設C1=LC1’，C2=?LC2’其中C1’、C2’都是文字的析取式。

C1

C2的歸結式為C1’C2’

C1C2的邏輯結果為：

C1=C1’L=?C1’→

LC2=?LC2’=L→

C2’由假言三段論可得：

C1∧

C2=（?C1’→L）∧（L→C2’）=>?C1’→

C2’=C1’C2’命題邏輯中的歸結原理：7/24/2023693.4.2命題邏輯中的歸結原理(4)推論設C1，

C2是子句集S的兩個子句，C12是它們的歸結式，則（1）若用C12來代替C1，

C2，得到新的子句集S1，則由S1不可滿足性可以推出原子句集S的不可滿足性。即（2）若用C12加入到S中，得到新的子句集S2，則S2與原S的同不可滿足。即S1的不可滿足性=>S不可滿足S2的不可滿足性<=>S不可滿足7/24/2023703.4.2命題邏輯中的歸結原理(5)利用歸結反演方法來證明定理的具體步驟為：步1否定目標公式G，得到?

G；步2將?

G并入到公式集中；步3將公式集化子句集，得到子句集S；步4對S進行歸結，每次歸結的結果并入到S中。如此反復，直到得到空子句為止。此時，就證明了在前提為真時，結論G為真。7/24/2023713.4.2命題邏輯中的歸結原理(6)例5.12設公理集：F1：

，F(xiàn)2：

求證G：解：求F1F2?G子句集： (1)PQ (2)?PR (3)?QS (4)?R (5)?S

歸結： (6)PS（1）、（3）歸結 (7)P（5）、（6）歸結

(8)?P（2）、（4）歸結

(9)Nil（7）、（8）歸結由此可證，G是F1和F2的邏輯結論。7/24/2023723.4.3替換與合一（1）問題在一階謂詞中應用消解原理，無法直接找到互否文字的子句對例如：P(x)Q(z)

?P(f(a))R(y)解決方法

對個體變元做適當替換例如：P(f(a))Q(z),

?P(f(a))R(y)

7/24/2023733.4.3替換與合一（2）定義3.16一個替換（Substitution）是形如{t1/x1,t2/x2,…,tn/xn}的有限集合，其中t1,t2,…,tn是項，稱為替換的分子；x1,x2,…,xn是互不相同的個體變元，稱為替換的分母；ti,xi不同，xi不循環(huán)出現(xiàn)在tj中；ti/xi表示用ti替換xi。若其中t1,t2,…,tn是不含變元的項（稱為基項）時，該替換為基替換；沒有元素的替換稱為空替換，記作ε，表示不作任何替換。{a/x,y/z,f(g(z))/u}就是一個替換{f(x)/y,g(y)/x}就不是一個替換，x與y出現(xiàn)了循環(huán)替換7/24/2023743.4.3替換與合一（3）

表達式：項、原子公式、文字、子句的統(tǒng)稱?；磉_式：沒有變元的表達式。子表達式：出現(xiàn)在表達式E中的表達式稱為E的子表達式。定義3.17設θ={t1/x1,t2/x2,…,tn/xn}是一個替換，E是一個表達式，對公式E實施替換θ，即把E中出現(xiàn)的個體變元xj都是tj替換，記為Eθ，所得的結果稱為E在θ下的例或特例（instance）。例如：若θ={f(a/x,b/y,g(u)/z},Q=P(x,y,z)

Fθ=Q(f(a),b,g(u))7/24/2023753.4.3替換與合一（4）定義3.18設θ＝{t1/x1,t2/x2,…,tm/xm}，λ＝{u1/y1,u2/y2,…,un/yn}是兩個替換，則將{t1λ/x1,t2λ/x2,…,tmλ/xm,u1/y1,u2/y2,…,un/yn}中符合下列條件的元素刪除

（1）tiλ

/xi當tiλ

＝

xi

（2）ui/yi當yi∈

{x1,…,xn}這樣得到的集合為θ與λ的復合或乘積，記為θ?λ。7/24/2023763.4.3替換與合一（5）例3.11：設θ={a/x,f(u)/y

,y/z},

λ={b/u,z/y,g(x)/z}

從{a/x，f(b)/y

，z/z，b/u，z/y，g(x)/z},

中刪去

z/z，z/y，g(x)/z

從而得：

θ·λ={a/x，f(b)/y

，b/u}7/24/2023773.4.3替換與合一（6）定義3.19設有一個公式集F＝{F1,F2,…,Fn}

，若存在一個替換λ，可使F1λ

=F2λ=…=Fnλ，則稱λ為F的一個合一，稱F為可合一的。例：已知公式集S={P(x,f(y),b),P(z,f(b),b)}，則替換θ={a/x,b/y,a/z}是一個合一,因為：P(x,f(y),b)θ=P(a,f(b),b)P(z,f(b),b)θ=P(a,f(b),b)。一個公式的合一一般不唯一7/24/2023783.4.3替換與合一（7）定義3.20設σ是原子公式集F的一個合一，如果對S的任何一個合一θ都存在一個替換λ，使得θ＝σ?λ則稱σ為F的最一般合一(MostGeneralUnifier),簡稱MGU。一個公式集的MGU也是不唯一的。例：設S＝{P(u,y,g(y)),P(x,f(u),z)},S有一個最一般合一

σ＝{u/x，f(u)/y，g(f(u))/z}對S的任一合一，例如：

θ＝{a/x，f(a)/y，g(f(a))/z，a/u}存在一個替換

λ＝{a/u}使得θ＝σ

?λ7/24/202379定義3.21設S是一個非空的具有相同謂詞名的原子公式集，從S中各公式左邊的第一項開始，同時向右比較，直到發(fā)現(xiàn)第一個不都相同的項為止，用這些項的差異部分組成的集合就是S的一個差異集。例3.12：設F＝{P(x,y,z),P(x,f(u),h(a,v))}根據(jù)上述差異集定義我們可以看出S有兩個差異集：D1＝{y,f(u)}D2＝{z,h(a,y)}3.4.3替換與合一（8）7/24/2023803.4.3替換與合一（9）合一算法（Unificationalgorithm）Step1：置k＝0，F(xiàn)k＝F，σk＝ε；Step2：若Fk只含有一個謂詞公式，則算法停止，σk就是最一般合一；Step3：求Fk的差異集Dk；Step4：若Dk中存在元素xk和tk，其中xk是變元，tk是項且xk不在tk中出現(xiàn)，則置Sk＋1＝Fk{tk/

xk},σk+1=σk?{tk/xk}

k＝k+1然后轉Step2；Step5：算法停止，F(xiàn)的最一般合一不存在。7/24/2023813.4.3替換與合一（10）例3.13：求公式集F＝{Q(a,x,f(g(y))),Q(z,h(z,u),f(u))}的最一般合一。解k＝0；F0＝F，σ0＝ε，D0＝{a,z}σ1＝σ0·{a/z}={a/z}F1=F0{a/z}={Q(a,x,f(g(y))),Q(a,h(a,u),f(u))}k＝1；D1={x,h(a,u)}σ2=σ1·{h(a,u)/x}＝{a/z,h(a,u)/x}F2=F1{a/z,h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}k＝2；D2＝{g(y),u}σ3＝{a/z,h(a,g(y))/x,g(y)/u}F3=F2{g(y)/u}={P(a,h(a,g(y)),f(g(y)))}S3單元素集，σ3為MGU。7/24/2023823.4.3替換與合一（11）定理3.3(合一定理)F是非空有限可合一的公式集，則合一算法總在Step2停止，且最后的σk

一定是S的最一般合一（MGU）。對任一非空有限可合一的公式集，一定存在最一般合一，而且用合一算法一定能找到最一般合一。從合一算法可以看出，一個公式集F的最一般合一可能是不唯一的，因為如果差異集Dk=｛ak,bk｝，且ak和bk都是個體變元，則下面兩種選擇都是合適的：σk+1=σk·｛bk/ak｝或σk+1=σk·｛ak/bk｝7/24/2023833.4.4謂詞邏輯中的歸結原理(1)定義3.22C1，C2為無相同變元的子句；L1，L2為其中的兩個文字，L1和?L2有最一般合一σ；C1，C2的二元歸結式（二元消解式）為：

（C1σ－{L1σ}）∪（C2σ－{L2σ}）其中C1，C2稱作歸結式的親本子句；L1，L2稱作消解文字。

7/24/2023843.4.4謂詞邏輯中的歸結原理(2)例設C1=P(x)∨Q(x),C2=?

P(f(z))∨R(y)，求C1,C2的歸結式。解取L1=P(x),?L2=P(f(z)),L1與?L2的MGUσ={f(z)/x｝

C1σ-｛L1σ｝)∪(C2σ-｛L2σ｝)=(｛P(f(z),Q(f(z))｝-｛P(f(z))｝)∪(｛?P(f(z)),R(y)｝-｛?P(f(z))｝)

=｛Q(f(z)),R(y)｝=Q(f(z))∨R(y)所以，Q(f(z))∨R(y)是C1和C2的二元歸結式。7/24/2023853.4.4謂詞邏輯中的歸結原理(3)例C＝P(x)P(f(y))?Q(x),σ={f((y)/x}

Cσ＝P(f(y))?Q(x)是C的因子。定義3.23子句C中，兩個或兩個以上的文字有一個最一般合一σ，則稱Cσ為C的因子，若Cσ為單元子句，則Cσ稱為C的單因子。7/24/2023863.4.4謂詞邏輯中的歸結原理(4)定義14子句的C1，C2消解式，是下列二元消解式之一:

（1）C1和C2的二元消解式；（2）C1和C2的因子的二元消解式；（3）C1因子和C2的二元消解式；（4）C1的因子和C2的因子的二元消解式。7/24/2023873.4.4謂詞邏輯中的歸結原理(5)

例設C1=P(x,y)∨Q(a),C2=?

Q(x)∨R(y),求C1,C2的歸結式。解由于C1,C2中都含有變元x,y，所以需先對其中一個進行改名,方可歸結。2、如果在參加歸結的子句內(nèi)部含有可合一的文字，則在進行歸結之前，也應對這些文字進行合一，從而使子句達到最簡。歸結過程需要注意：1、兩個子句含有相同的變元，需要對其中一個進行改名7/24/2023883.4.4謂詞邏輯中的歸結原理(6)例3.14設C1=P(x)∨P(f(y))∨Q(a)C2=?P(y)∨R(y)求C1,C2的歸結式可見,在C1,C2中有可合一的文字P(x)與P(f(y))取替換θ={f(y)/x}現(xiàn)在再用C1θ與C2進行歸結，變元更名，從而得到C1與C2的歸結式

Q(a)∨R(f(x))則得C1θ=P(f(y))∨Q(a)7/24/2023893.4.4謂詞邏輯中的歸結原理(7)定理3.4謂詞邏輯中的消解（歸結）式是它的親本子句的邏輯結果。謂詞邏輯的推理規(guī)則：

C1

C2

＝>（C1

σ－{L1

σ}）∪（

C2σ－{L2σ}）

其中C1

，C2是兩個無相同變量的子句，L1，L2分別是C1

，C2中的文字,σ為L1和?L2的最一般合一。這個規(guī)則稱為謂詞邏輯中的消解原理（或歸結原理）。

7/24/2023903.4.4謂詞邏輯中的歸結原理(8)例3.15求證G是F1F2和F3的邏輯結果。

F1：

F2

：

F3：

G：證：利用歸結反演法，先證明F1F2F3

?G是不可滿足的。求子句集：

(1)?D(x)B(x)(2)?D(y)F(y)(3)?F(z)N(z)(4)?G(u)D(u)(5)G(a)(6)?N(a)(?G)F2F1SF37/24/2023913.4.4謂詞邏輯中的歸結原理(9)應用消解原理，得：

(7)B(a)（1）與（5）歸結，{a/x}(8)F(a)（2）與（5）歸結，{a/y}

(9）?

F(a)（3）與（6）歸結{a/z}(10)Nil(8),(9)所以S是不可滿足的，G是F1F2和F3的邏輯結果。7/24/2023923.4.4謂詞邏輯中的歸結原理(10)例3.16已知：F1：凡是清潔的東西就有人喜歡；F2：人們都不喜歡蒼蠅。用歸結原理證明結論G：蒼蠅是不清潔的。證首先定義如下謂詞：

C(x)：x是清潔的P(x)：x是人L(x,y)：x喜歡yF(x):x是蒼蠅將上述各語句翻譯成謂詞公式：F1:x(C(x)→y(P(y)∧L(y,x)))F2:xy(P(x)∧F(y)→?L(x,y)))G:x(F(x)?C(x))7/24/2023933.4.4謂詞邏輯中的歸結原理(11)求題設與結論否定的子句集，得:

(1)?C(x)∨P(f(x))(2)?C(y)∨L(f(y),y)(3)?P(u)∨?F(v)∨?L(u,v)(4)F(a)(5)C(a)歸結得：

(6)P(f(a))[(1)(5),{a/x}](7)L(f(a),a)[(2)(5){a/y}](8)?F(v)∨?L(f(a),v)[(3)(6){f(a)/u}](9)?L(f(a),a)[(4)(8),{a/v}](10)Nil[(7),(9)]7/24/2023943.4.4謂詞邏輯中的歸結原理(12)例3.17設已知：（1）自然數(shù)都是大于零的整數(shù)；（2）所有整數(shù)不是偶數(shù)就是奇數(shù)；（3）偶數(shù)除以2是整數(shù)。試證明：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。證首先定義如下謂詞：N(x):x是自然數(shù)。I(x):x是整數(shù)。E(x):x是偶數(shù)。O(x):x是奇數(shù)。GZ(x):x大于零。s(x):x除以2。將上述各語句翻譯成謂詞公式：

F1:x(N(x)GZ(x)I(x))

F2:x(I(x)(E(x)O(x)))

F3:x(E(x)I(s(x)))

G:x(N(x)(I(s(x))O(x)))7/24/2023953.4.4謂詞邏輯中的歸結原理(13)利用歸結反演法，先證明F1F2F3?G是不可滿足的。F1F2F3?G的子句集為（1）?N(x)GZ(x)（2）?N(y)I(y)（4）?E(u)I(s(u))（3）?I(z)E(z)O(z)（5）N(a)（6）?O(a)（7）?I(s(a))7/24/2023963.4.4謂詞邏輯中的歸結原理(14)定理5

如果子句集S是不可滿足的，那么必存在一個由S推出空子句的消解序列。7/24/2023973.4.5應用歸結原理求取問題答案(1)例3.18（1）Tom和Jerry是同班同學.（2）如果x和y是同班同學，則x的教室也是y的教室，（3）現(xiàn)在Tom在302教室上課。用歸結原理求：Jerry在哪里上課？解：首先定義謂詞及相應的符號表示：

M(x,y)：x和y是同班同學。

R(x,y)：x的教室是y

。a表示Tom，b表示Jerry，c表示302教室。

已知條件可以表示成如下謂詞公式：F1：xyz(M(x,y)R(z,x)R(z,y))F2:M(a,b)F3:R(a,c)

7/24/2023983.4.5應用歸結原理求取問題答案(2)為了得到問題的解，先證明Jerry上課的教室是存在的，即證明：G：xR(b,x)

(1)M(a,b)(2)?M(x,y)?R(z,x)R(z,y)(3)R(a,c)(4)?R(b,u)求F1F2F3?

G的子句集：

7/24/2023993.4.5應用歸結原理求取問題答案(3)歸結演繹得：(5)?R(a,z)R(b,z)[(1),(2),{a/z,b/y}](6)R(b,c)[(3),(5),{c/z}](7)Nil[(4),(6)，{c/u}]這說明Jerry上課的教室確實存在。

(1)M(a,b)(2)?M(x,y)?R(x,z)R(y,z)(3)R(a,c)(4)?R(b,u)7/24/20231003.4.5應用歸結原理求取問題答案(4)

為了求取答案，給原來的子句增加一個輔助謂詞ANS（u），得到：(4)'?R(b,u)ANS（u）

原來的子句集變?yōu)椋?/p>

(1)M(a,b)(2)?M(x,y)?R(x,z)R(y,z)(3)R(a,c)(4)?R(b,u)ANS（u）

重新歸結演繹得：(5)’?R(a,z)R(b,z)[(1),(2),{a/z,b/y}](6)’R(b,c)[(3),(5),{c/z}](7)’ANS（c）[(4),(6)，{c/u}]求得答案，即Jerry在302教室上課。7/24/20231013.4.5應用歸結原理求取問題答案(5)應用歸結原理求取問題答案（方法思路）步1把已知前提用謂詞公式表示出來，并且化為相應的子句集S。步2為待求解的問題找一個合適的求證目標謂詞，化為相應的子句，再對子句以析取的形式增配一個輔助謂詞構成新的子句，并入到子句集S中形成子句集S’。輔助謂詞的謂詞名沒有要求，但是它的變量必須要與對應目標謂詞中的變量完全一致。步3對子句集S’應用歸結原理進行歸結。步4當歸結式只剩下輔助謂詞時，歸結結束，輔助謂詞中原變量位置上的項就是所求的結果。7/24/20231023.4.5應用歸結原理求取問題答案(6)練習2：設A、B、C中有人從來不說真話，也有人從來不說謊話，某人向這三人分別同時提出一個問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個人說謊”。用歸結原理求誰是老實人，誰是說謊者？7/24/20231033.4.6歸結策略（1）研究歸結原理的目的是實現(xiàn)機器推理用歸結原理實現(xiàn)機器推理的一般性算法

步1將子句集S置入CLAUSES表中；步2若空子句Nil在CLAUSES中，則歸結成功，結束。步3若CLAUSES表中存在可歸結的子句對，則歸結之，并將歸結式并入CLAUSES表中，轉步2；步4歸結失敗，退出。Step3中子句對進行歸結的順序怎么確定廣度優(yōu)先搜索策略來進行歸結7/24/20231043.4.6歸結策略（2）廣度優(yōu)先搜索策略進行歸結

第一輪先讓0層歸結項（原子句集S）中的子句兩兩進行歸結，產(chǎn)生的歸結項集合即為1層歸結項；再一輪歸結時，讓2層歸結項分別與0層、1層、2層歸結項兩兩進行歸結，產(chǎn)生3層歸結項；如此進行，直到某層歸結項中出現(xiàn)空子句為止。下一輪讓1層歸結項與0層和1層的歸結項分別兩兩進行歸結，得到的歸結項集合為2層歸結項；7/24/20231053.4.6歸結策略（3）只要子句集是不可滿足的，采用廣度優(yōu)先搜索策略就一定能夠歸結出空子句，稱該策略是完備的。這種歸結方法也稱為水平浸透法。定義3-25一個歸結策略是完備的，如果對于不可滿足的子句集，使用該策略進行歸結，最終必導出空子句Nil。7/24/20231063.4.6歸結策略（4）例3.20設有子句集：{?P，?Q，P∨?R，R∨Q}歸結過程為：S：（1）?P

（2）?Q（3）P∨?R（4）R∨QS1：（5）?R（1）,（3）（6）R（2）,（4）（7）P∨Q（3）,（4）S2：（8）Q（1）,（7）（9）P（2）,（7）（10）P（3）,（6）（11）Q（4）,（5）（12）NIL（5）,（6）7/24/20231073.4.6歸結策略（5）歸結策略大致有以下幾個出發(fā)點：（1）簡化性策略。（2）限制性策略。（3）有序性策略（包含排序策略）7/24/20231083.4.6歸結策略（6）刪除策略支持集策略線性歸結策略單元歸結策略語義歸結策略祖先過濾型策略7/24/20231093.4.6歸結策略（7）刪除策略定義3.26類含若C1，C2是兩個子句，若存在替換θ，使得C1θC2，則稱子句C1類含C2。例如：P（x）類含P（a）

Q（y）（只需取θ

＝{a/x}）

P（a，x）P（y，b）類含P（a，b)（取θ

＝{a/x,b/y}

）定義3.27在子句集中無補的文字稱為純文字。7/24/20231103.4.6歸結策略（8）刪除策略在歸結過程中刪除以下子句：（1）含有純文字（子句集中無補的文字）的子句；（2）含有永真式的子句；（3）被子句集中別的子句類含的子句。刪除策略的特點刪除策略的思想是及早刪除無用子句，以避免無效歸結，縮小搜索規(guī)模；并盡量使歸結式朝“小”的方向發(fā)展。從而盡早導出空子句。刪除策略是完備的。即對于不可滿足的子句集，使用刪除策略進行歸結，最終必導出空子句。7/24/20231113.4.6歸結策略（9）例3.21S：（1）?P（2）?Q（3）P∨?R（4）R∨Q第一輪歸結：S1：（5）?R（1），（3）（6）R（2），（4）（7）P∨Q（3），（4）其中（5）類含（3），（6）類含（4），所以刪除（3）（4S2：（8）Q（1），（7）（9）P（2），（7）（10）Nil（5），（6）7/24/20231123