第二章基于謂詞邏輯的機(jī)器推理

1、1李偉生李偉生信科大廈信科大廈19樓樓Tel：2內(nèi)容提要內(nèi)容提要: : 2.1 .1 命題邏輯命題邏輯 2.2 2.2 一階謂詞邏輯一階謂詞邏輯 2.3 2.3 歸結(jié)演繹推理歸結(jié)演繹推理 2.4 2.4 應(yīng)用歸結(jié)原理求取問題答案應(yīng)用歸結(jié)原理求取問題答案3 邏輯學(xué)是研究人如何正確地思維以達(dá)到認(rèn)識客觀真理的科學(xué)，它包括形式邏輯和辨證邏輯兩部分。形式邏輯又名靜態(tài)邏輯或初等邏輯，它著重研究思維形式的結(jié)構(gòu)及其規(guī)律。辯證邏輯又名動態(tài)邏輯或高等邏輯，它是全面研究思維的形式和內(nèi)容，研究思維的辨證發(fā)展規(guī)律的科學(xué)。形式邏輯反映的是認(rèn)識過程處在量變階段的規(guī)律，它完成的是已知規(guī)律的邏輯推理。辯證邏輯反映的是認(rèn)識過程處

2、在質(zhì)變階段的規(guī)律，它研究的是人的認(rèn)識的發(fā)生、發(fā)展和完善的全過程。4 數(shù)理邏輯是用數(shù)學(xué)方法研究邏輯學(xué)的科學(xué)，目前僅局限在形式邏輯范圍內(nèi)。數(shù)理邏輯以命題演算和一階謂詞演算為基礎(chǔ)。在數(shù)理邏輯中，僅關(guān)心推理在形式上的有效性，而不涉及推理的內(nèi)容本身。命題邏輯與謂詞邏輯是最先應(yīng)用于人工智能的兩種邏輯，對于知識的形式化表示，特別是定理的自動證明發(fā)揮了重要作用，在人工智能的發(fā)展史中占有重要地位。本節(jié)主要介紹命題邏輯，在下一節(jié)介紹謂詞邏輯。52.1.1 命題2.1.2 命題定律2.1.3 范式2.1.4 命題邏輯的局限性6定義定義2.1 命題（命題（Proposition）：命題是具有真假意義的語句。命題代表人

3、們進(jìn)行思維時的一種判斷，或者是肯定，或者是否定，只有這兩種情況。如果命題的意義為真，稱它的真值為真，記作T；如果命題的意義為假，稱它的真值為假，記作F。一個命題不能同時既為真又為假，但可以在一定條件下為真，在另一種條件下為假。沒有真假意義的語句(如感嘆句、疑問句等)不是命題。例如，“北京是中華人民共和國的首都”、“33”這個不等式可用謂詞表示為Greater（5，3），這里Greater刻畫了5與3之間的“大于”關(guān)系。 36看幾個命題：1. 3是質(zhì)數(shù)2. 王二生于武漢市3. 7=23 x是質(zhì)數(shù)x生于武漢市x=y zF(x)G(x,y)H(x,y,z)稱“3”、“王二”、“武漢市”、“7”、“2

4、”、“3”為個體;代表個體的變元稱為個體變元；刻畫個體性質(zhì)或個體之間關(guān)系的詞叫謂詞?！笆琴|(zhì)數(shù)”、“生于”、“=. .”都是謂詞。37謂詞的一般形式是： P (x1, x2, ., xn)其中，P是謂詞名，x1, x2, ., xn是個體。謂詞名通常用大寫的英文字母表示，個體通常用小寫的英文字母表示,個體可以是常量，也可以是變元，還可以是一個函數(shù)。 例如，對于“x5，可表示為Less (x , 5 )，其中x是變元。又如，對于“小王的父親是教師”，可表示為Teacher (father(Wang)，其中father (Wang)是一個函數(shù)。 在用謂詞表示客觀事物時，謂詞的語義是由使用者根據(jù)需要人

5、為地定義的。例如對于謂詞S(x)，既可以定義它表示“x是一個學(xué)生”，也可以定義它表示“x是一只船”或者別的什么。 當(dāng)謂詞中的變元都用特定的個體取代時，謂詞就具有一個確定的真值：T或F。38 謂詞中包含的個體數(shù)目稱為謂詞的元數(shù)。例如P (x)是一元謂詞，P (x, y)是二元謂詞，P (x1, x2, ., xn)是n元謂詞。 在謂詞P (x1, x2, ., xn)中，若xi (i = 1, ., n)都是個體常量、變元或函數(shù)，稱它為一階謂詞。如果某個xi本身又是一個一階謂詞，則稱它為二階謂詞。余者類推。 個體變元的取值范圍稱為個體域。個體域可以是有限的，也可以是無限的。例，若用I (x)表示

6、“x是整數(shù)”，則個體域是所有整數(shù)，是無限的。 謂詞與函數(shù)表面上很相似，容易混淆，其實這是兩個完全不同的概念。謂詞的真值是“真”或“假”，而函數(shù)的值是個體域中的某個個體，函數(shù)無真值可言，它只是在個體域中從一個個體到另一個個體的映射。 個體常量、個體變元、函數(shù)統(tǒng)稱為“項”。 39 怎樣來刻畫謂詞與個體之間的這兩種不同的關(guān)系呢？為此我們引入了一個新的概念量詞。量詞有兩種：全稱量詞和存在量詞。 全稱量詞( x) ，讀作“對于所有的x”，它表示“對個體域中的所有(或任一個)個體x；另一個是存在量詞( x) ，讀作“存在x”，它表示“在個體域中存在個體x”。 符號“( x)P(x)”表示命題：“對于個體域

7、中所有的個體x，謂詞P(x)均為T”。謂詞P(x)稱為的轄域或作用范圍。 符號“( x)Q(x)”表示命題：“對于個體域中存在某些個體使謂詞Q(x)為T”。謂詞Q(x)稱為的轄域或存在范圍。再看前面的三段論法：P:“所有的人都會犯錯誤”Q:“張三是人”R:“張三會犯錯誤”x(M(x) R(x)M(“張三”)R(“張三”)40 將謂詞轉(zhuǎn)化成命題的方法有二： 將謂詞中的個體變元全部換成確定的個體； 使謂詞量化。注意： 量詞本身并不是一個獨立的邏輯概念，可以用，聯(lián)結(jié)詞代替。設(shè)某個體域是有限集合S： S=a1, a2, ., an,對任意謂詞A(x)有 由量詞所確定的命題的真值與個體域有關(guān)。)()()

8、()()(21naAaAaAxAx)()()()()(21naAaAaAxAx41可按下述規(guī)則得到謂詞邏輯的合式公式：(1) 單個謂詞是合式公式，稱為原子謂詞公式；(2) 若A是合式公式，則A也是合式公式；(3) 若A、B都是合式公式，則AB，AB，AB，AB也都是合式公式；(4) 若A是合式公式，x是任一個體變元，則( x)A和( x)A也都是合式公式。 在合式公式中，連接詞的優(yōu)先級別是, , , , 42 位于量詞后面的單個謂詞或者用括弧括起來的合式公式稱為量詞的轄域，那么，轄域內(nèi)與量詞中同名的變元稱為約束變元，不受約束的變元稱為自由變元。 例如: 其中，（P(x,y) Q(x,y)）是(

9、 x)的轄域，轄域內(nèi)的變元x是受( x)約束的變元，而R(x,y)中的x是自由變元，公式中的所有y都是自由變元。 在謂詞公式中，變元的名字是無關(guān)緊要的，可以把一個名字換成另一個名字。但必須注意，當(dāng)對量詞轄域內(nèi)的約束變元更名時，必須把同名的約束變元都統(tǒng)一改成相同的名字，且不能與轄域內(nèi)的自由變元同名；當(dāng)對轄域內(nèi)的自由變元改名時，不能改成與約束變元相同的名字。 ），（），（），（yxRyxQyxPx )(43 在命題邏輯中，對命題公式中各個命題變元的一次真值指派稱為命題公式的一個解釋。一旦解釋確定后，根據(jù)各連接詞的定義就可求出命題公式的真值(T或F)。在謂詞邏輯中，由于公式中可能有個體常量、個體變元

10、以及函數(shù)，因此不能像命題公式那樣直接通過真值指派給出解釋，必須首先考慮個體常量和函數(shù)在個體域中的取值，然后才能針對常量與函數(shù)的具體取值為謂詞分別指派真值。由于存在多種組合情況，所以一個謂詞公式的解釋可能有很多個。對于每一個解釋，謂詞公式都可求出一個真值(T或F)。 下面首先給出解釋的定義，然后用例子說明如何構(gòu)造一個解釋以及如何根據(jù)解釋求出謂詞公式的真值。 44定義2.7：設(shè)D為謂詞公式P的個體域，若對P中的個體常量、函數(shù)和謂詞按如下規(guī)定賦值：(1) 為每個個體常量指派D中的一個元素；(2) 為每個n元函數(shù)指派一個從Dn到D的映射，其中 Dn=(x1, x2,., xn) | x1, x2,.,

11、 xnD (3) 為每個n元謂詞指派一個從Dn到F，T的映射。則稱這些指派為公式P在D上的一個解釋。 45例1：設(shè)個體域D=1,2，求公式 在D上的解釋，并指出在每一種解釋下公式A的真值。解：在公式A中沒有包括個體常量和函數(shù)，所以可直接為謂詞指派真值，設(shè)為 P(1,1)=T, P(1,2)=F , P(2,1)=T , P(2,2)=F 這就是公式A在D上的一個解釋。在此解釋下，因為x1時有y1使P(x,y)的真值為T；x=2時也有y1使F(x,y)的真值為T，即對于D中的所有x都有y1使P(x,y)的真值為T，所以在此解釋下公式A的真值為T。還可以對公式A中的謂詞指派另外一組真值，設(shè)為 P(

12、1,1)=F, P(1,2)=F , P(2,1)=F , P(2,2)=F 這是對公式A的另一個解釋。在此解釋下，對D中的所有x (x1與x2)不存在一個y，使得公式A的真值為T，所以在此解釋下公式A的真值為F。公式A在D上共有16種解釋，這里不再一一列出，可自行列出其中的幾個，并求出公式A的真值。 ),()(yxPyxA46例2：設(shè)個體域D=1,2，求公式 在D上的某一個解釋，并指出公式B在此解釋下的真值。解：設(shè)對個體常量b，函數(shù)f (x)指派的值分別為： b=1，f (1)=2，f (2)=1 對謂詞指派的真值為： P(1)=F，P(2)=T ，Q(1,1)=T，Q(2,1)=F 這里，

13、由于已指派b=1，所以Q(1,2)與Q(2,2)不可能出現(xiàn)，故沒有給它們指派真值。上述指派就是對公式B的一個解釋。在此解釋下，由于當(dāng)x1時，有 P(1)=F ，Q(f (1),1)= Q(2,1)=F 所以P(1) Q(f (1),1)的真值為T。2時 P(2)=T，Q(f (2),1)= Q(1,1)=T 所以P(2) Q(f (2),1)的真值也為T。即對個體域D中的所有x均有 (P(x) Q(f (x),b) 的真值為T。所以公式B在此解釋下的真值為T。 ),()()(bxfQxPx47 僅個體變元被量化的謂詞稱為一階謂詞一階謂詞，如果不僅個體變元被量化，而且函數(shù)符號和謂詞符號也被量化，

14、這樣的謂詞稱為二階謂詞二階謂詞。 我們只討論一階謂詞。 用謂詞公式表示知識的步驟： 可以用合取符號和析取符號聯(lián)結(jié)形成的謂詞公式表示事實性知識，也可以用蘊含符號聯(lián)結(jié)形成的謂詞公式表示規(guī)則性知識。(1)定義謂詞及個體，確定每個謂詞及個體的確切含義；(2)根據(jù)所要表達(dá)的事物或概念，為每個謂詞中的變元賦以特定的值；(3)根據(jù)所要表達(dá)的知識的語義，用適當(dāng)?shù)穆?lián)結(jié)符號將各個謂詞聯(lián)結(jié)起來，形成謂詞公式。48例3：設(shè)有下列事實性知識： 張輝是一名計算機(jī)系的學(xué)生，但他不喜歡編程序。 李曉比他姐姐長得高。用謂詞公式表示這些知識。解：首先定義謂詞如下： Compuer(x): x是計算機(jī)系的學(xué)生。 Like(x, y

15、): x喜歡y。 Higher(x, y): x比y長得高。 將個體帶入謂詞中，得到 Computer(zhang), Like(zhang, programming), Higher(li, sister(li) 根據(jù)語義，用邏輯聯(lián)結(jié)詞進(jìn)行聯(lián)結(jié)，就得到了謂詞公式： Computer(zhang) Like(zhang, programming) Higher(li, sister(li)49練習(xí)1：用謂詞公式表示下列規(guī)則性知識： 人人愛勞動。 所有整數(shù)要么是偶數(shù)要么是奇數(shù)。 自然數(shù)都是大于零的整數(shù)。 偶數(shù)除以2是整數(shù)。(提示：用函數(shù)S(x)表示x除以2) 解：首先定義謂詞如下： Man(x)

16、: x是人。 Love(x, y): x愛y。 N(x): x是自然數(shù)。 I(x): x是整數(shù)。 E(x): x是偶數(shù)。 O(x): x是奇數(shù)。 GZ(x): x大于零?？梢缘玫街^詞公式表示： (x) (Man(x) Love(x, labour) (x) (I(x) E(x)O(x) (x) (N(x) GZ(x)I(x) (x) (E(x) I(S(x) 50 2.3.1 子句集2.3.2 命題邏輯中的歸結(jié)原理 2.3.3 替換與合一2.3.4 謂詞邏輯中的歸結(jié)原理511.前束范式2.Skolem范式3.子句和子句集52一個謂詞公式，如果量詞非否定地放在全式的開頭，而量詞的轄域都延伸到整個

17、謂詞公式，則稱這樣的公式為前束范式。一般地，謂詞邏輯中的公式G如果有如下形狀：Q1x1,Qn xn M(x1,xn)則稱G為前束范式。其中Qi是xi或xi, i =1,n，M(x1,xn)是不含量詞的公式。 Q1x1,Qn xn稱為首標(biāo)，M稱為母式。如：xyz(P(x,y ) Q(x,z)xyzP(x,y,z)都是前束范式。53 利用改名規(guī)則、量詞否定公式和量詞轄域擴(kuò)張公式等，可把任一謂詞公式化成前束范式。例如：x(P(x) xQ(x)=x(P(x) xQ(x)=x(P(x) xQ(x)= x(P(x) xQ(x)= x(P(x) yQ(y) xy(P(x) Q(y)例2.2將公式xy(z (

18、P(x,z) P(y,z) uQ(x,y,u)化為前束范式：解： xy(z (P(x,z) P(y,z) uQ(x,y,u)= xy(z (P(x,z) P(y,z) uQ(x,y,u)= xy(z (P(x,z) P(y,z) uQ(x,y,u)=xyzu (P(x,z) P(y,z) Q(x,y,u)54步驟1：使用以下基本等價公式，將G中的和刪去：F H=(F H) (H F)F H=F H步驟2：使用(F)=F，摩根定律及以下等價公式，將謂詞公式中的所有 否定號放在原子之前：xG(x)=xG(x)xG(x)=xG(x)步驟3：如果需要，則將約束變量改名。步驟4：利用等價公式將所有量詞提

19、到公式的最前面。將任意謂詞公式化為前束范式的四個步驟：55Skolem范式是謂詞邏輯中公式的又一種標(biāo)準(zhǔn)形式。設(shè)公式G的形式如下：Q1x1,Qn xn M(x1,xn)其中Qi是xi或xi, i =1,n，M(x1,xn)是不含量詞的公式。將上式中的M(x1,xn)化為等值的合取范式，然后將所有的存在量詞消去，便可得到公式G的Skolem范式。消去G中的存在量詞的方法如下：設(shè)Qrxr (1 r n )是第一個出現(xiàn)在Q1x1, Qrxr ,Qn xn M(x1,xn)中的存在量詞，即Q1x1, Qr-1xr-1 均為全稱量詞。若r=1，即Qrxr 左邊沒有全稱量詞，則取異于M(x1,xn)中所有常

20、量符號的常量符號C,并用C代表M(x1,xn)中的xr，然后在首標(biāo)中刪除Qrxr。若1r n，即Qrxr左邊有全稱量詞Qs1 xs1 ,Qsm xsm而m1，1 s1s2.s mr，則取異于出現(xiàn)在M中的所有函數(shù)符號的m元函數(shù)符號f(xs1,xsm)，用f(xs1,xsm)代表出現(xiàn)在M中的所有xr,然后在首標(biāo)中刪除存在量詞Qrxr。56例將公式G=xyz(P(x,y)Q(x,z) R(x,y,z)化成Skolem范式。解：先將M(x,y,z)化成合取范式：M(x,y,z)= (P(x,y) Q(x,z) R(x,y,z)= (P(x,y) R(x,y,z) (Q(x,z) R(x,y,z) G=

21、 xyz(P(x,y) R(x,y,z) (Q(x,z) R(x,y,z) 消去y得到：xz(P(x,f(x) R(x,f(x),z) (Q(x,z) R(x,f(x),z) 消去z得到：x (P(x,f(x) R(x,f(x),g(x) (Q(x,g(x) R(x,f(x),g(x)此式就是公式G的Skolem范式。 57例將公式G=xyzuvwP(x,y,z,u,v,w)化成Skolem標(biāo)準(zhǔn)型。解：消去x,因為其左邊沒有全稱量詞，于是引入常量a代替P(x,y,z,u,v,w) 中的所有x,得： yzuvwP(a,y,z,u,v,w)消去u，因為其左邊有全稱量詞yz，于是引入一個二元函數(shù)f(

22、y,z)代替P(a,y,z,u,v,w)中的所有u，得： yzvwP(a,y,z,f(y,z),v,w)消去w ，因為其左邊有全稱量詞 yzv，于是引入一個三元函數(shù)g(y,z,v)，代替P(a,y,z,f(y,z),v,w)中的所有w。最后得到的Skolem 標(biāo)準(zhǔn)型為：yzvP(a,y,z,f(y,z),v,g(y,z,v)注意：1.公式的Skolem 標(biāo)準(zhǔn)型與原公式并不等值；2.公式的Skolem 標(biāo)準(zhǔn)型與原公式在不可滿足的意義上相等。58總結(jié)：得到謂詞公式Skolem標(biāo)準(zhǔn)型的步驟1)消去蘊含詞和等值詞。2)縮小否定詞的范圍，直到其只作用于原子公式。3)利用等價公式將所有量詞提到公式的最前面

23、，并適當(dāng)改名，使量詞間不含同名指導(dǎo)變元和約束變元。(得到前束范式)4)消去存在量詞 4.1 若存在量詞在某些全稱量詞轄域內(nèi)，則用這些全稱量詞指導(dǎo)變元的一個函數(shù)代替該存在量詞轄域中的相應(yīng)約束變元(Skloem函數(shù))。 4.2若存在量詞不在任何全稱量詞轄域內(nèi)，則用一個常量符號代替該存在量詞轄域中的相應(yīng)約束變元(Skolem常量)。5)消去所有全稱量詞。6)化公式為合取范式。7)適當(dāng)改名，使子句間無同名變元。不含第5)步得到的結(jié)果即為Skolem范式，由Skolem范式得到子句集：8)消去合取詞，以子句為元素組成一個集合S。59練習(xí)3：求下列謂詞公式的前束范式、Skolem標(biāo)準(zhǔn)型及子句集xyP(x,

24、y)yQ(x,y) R(x,y)60若干文字的一個析取式成為子句。如：P(x,y) Q(x,y,z) R(u)沒有文字的子句成為空子句。只有一個文字的子句成為單元子句。 原子謂詞公式及其否定稱為文字，若干個文字的一個析取式稱為一個子句。由r個文字組成的子句叫r-文字子句，1-文字子句叫單元子句，不含任何文字的子句稱為空子句，計為或NIL。61將公式G化為Skolem 標(biāo)準(zhǔn)型，其母式M已為合取范式，M中的每一個合取項都是一個子句，M中這些子句的集合用S表示，稱為公式G的子句集。從公式G得到子句集S的方法是：先從公式G得到Skolem 標(biāo)準(zhǔn)型，然后去掉全稱量詞，最后用符號“，”代替符號“”。外層括

25、號用。如公式：G=xyz(P(x,y) R(x,y,z) (Q(x,z) R(x,y,z)G的Skolem標(biāo)準(zhǔn)型為：x (P(x,f(x) R(x,f(x),g(x) (Q(x,g(x) R(x,f(x),g(x)G的子句集S為： (P(x,f(x) R(x,f(x),g(x)，(Q(x,g(x) R(x,f(x),g(x)子句集中S中的每一個子句中的變量都是由全稱量詞約束著。62 對任一公式G都可以建立其對應(yīng)的S子句集。這樣對公式的討論就可以用對集合的討論來代替。引進(jìn)子句集S的目的就是要簡化對A1 A2 A3B的證明，而證明A1 A2 A3B只需證明G= A1 A2 A3 B的子句集不可滿足

26、即可。定理設(shè)S是公式G的子句集。于是，G是不可滿足的，當(dāng)且僅當(dāng)S是不可滿足的。子句集概念的推廣：設(shè)G= G1 . Gn ，Si是Gi化為Skolem范式后其公式給出的子句集，i=1,2,n。令S=S1. S n。于是G是不可滿足的，當(dāng)且僅當(dāng)S是不可滿足的。也稱S是G的子句集。63子句集的海伯倫域定義：H0是出現(xiàn)于子句集S的常量符號集合。如果S中無常量符號出現(xiàn)，則H0由一個常量符號a組成。對于 i =1,2,n 令Hi=Hi-1 所有型如fn(t1,t2,tn)的項的集合 其中fn(t1,t2,tn)是出現(xiàn)在S中的n元函數(shù)符號，tj Hi-1 j=1,2,n。于是稱Hi為S的i級常量集，H 稱為

27、S的海伯倫（Herbrand）域,簡稱S的H域。例子句集S為：S=P(f(x),a,g(y),b)求子句集S的H域。解：根據(jù)定義H0=a,bH1=H0 f(a), f(b), g(a), g(b)=a,b, f(a), f(b), g(a),g(b)H2=H1 f(a), f(b), g(a),g(b),f(f(a), f(f(b), g(f(a),g(f(b), f(g(a), f(g(b), g(g(a),g(g(b)= a,b, f(a), f(b), g(a),g(b),f(f(a), f(f(b), g(f(a),g(f(b), f(g(a), f(g(b), g(g(a),g(g(

28、b).64見2.3.465練習(xí)2已知：張某被盜，公安局派出五個偵察員去調(diào)查。研究案情時，偵察員A說“趙與錢中至少有一個作案”；偵察員B說“錢與孫中至少有一人作案”；偵察員C說“孫與李中至少有一人作案”；偵察員D說“趙與孫中至少有一人與此案無關(guān)”；偵察員E說“錢與李中至少有一人與此案無關(guān)”。如果這五個偵察員的話都可信，請求出誰是盜竊犯。661.替換與最一般合一替換一個替換是型如t1/v1 ,t n/vn 的一個有限集其中vi是變量，而ti是不同于vi 的項（常量、變量、函數(shù)），且vi vj (i j ) ，i,j=1,2,n。稱ti為替換分子， vi為替換分母。當(dāng)t1,tn是基項（不含變元的項）

29、時，稱此替換為基替換。不含任何元素的替換為空替換，以表示。例如a/x,b/y,f(x)/z就是一個替換。替換可作用與某個謂詞公式上，也可作用于某個項上。令替換= t1/v1 ,t n/vn ，作用于E，而E是一謂詞公式。就是將E中出現(xiàn)的vi均以ti代入(i=1,2,n), 作用的結(jié)果用E表示，并稱E為E的一個例。若t是項， 作用于項t也是將t中出現(xiàn)的vi均以ti代入，作用的結(jié)果用t表示。67例令= a/x,f(b)/y,c/z E=P(x,y,z)t=g(x,y)于是E的例為 E =P(a,f(b),c) 而 t=g(a,f(b)當(dāng)E是子句集S的一個子句，用作用于E，當(dāng)中的v1,vn含有E的所

30、有變量， t1,tn又是H的元素時， E 便是S的子句E的基例。例子句集S=P(x,y),Q(x,a) R(y,b)此子句集的H域：H=a,bP(x,y)是S的一個子句，以= a/x,b/y作用于P(x,y)，得到P(a,b)。P(a,b)就是S子句P(x,y)的基例。68定義：設(shè)= t1/x1 ,t n/xn， =u1/y1 ,u m/ym是兩個替換。將下面集合t1 /x1 ,t n /xn，u1/y1 ,u m/ym中符合下面條件的元素刪除1. ui/yi ，當(dāng) yi x1,x n時；2. ti /xi ，當(dāng)ti =xi 時。如此得到一個替換，稱為與的乘積，記作例令=f(y)/x,z/y

31、=a/x,b/y,y/z解：先作替換f(y) /x,z/y,a/x,b/y,y/z = f(b)/x,y/y,a/x,b/y,y/z其中a/x,b/y符合條件1，應(yīng)刪除。y/y符合條件2，也應(yīng)刪除，所以得： = f(b)/x,y/z當(dāng)子句 E=P(x,y,z)時E() =P(f(b),y,y)如果先用作用于E,則E=P(f(y),z,z)再用作用于E得(E) = P(f(b),y,y)與用= f(b)/x,y/z直接作用于E的結(jié)果一樣。即：E() = (E) 求： 69引理設(shè)，是三個替換，于是： ()= ()設(shè)E是任一表達(dá)式E() ) =(E() ) =( (E) E( ) =(E)()=(

32、(E) 所以 E() ) = E( ) 由于E的任意性，故 ()= () 注意，在，中，交換律是不成立的。70 為了在兩個文字中找出互補文字，常常需要去統(tǒng)一兩個或多個表達(dá)式。即需要找一個替換，使得在此替換下，一些本來不同的表達(dá)式會一致起來。定義 替換稱為表達(dá)式集合E1,E k的合一，當(dāng)且僅當(dāng)E1 = E2 =.= Ek 。表達(dá)式集合E1,E k稱為可合一的，如果存在關(guān)于此集合的一個合一。定義 表達(dá)式集合E1,E k的合一稱為是最一般合一（most general unifier）記作mgu，當(dāng)且僅當(dāng)對此集合的每一個合一，都存在替換，使得= 。例 表達(dá)式集合P(a,y),P(x,f(b)是可合一

33、的，其合一為：=a/x,f(b)/y例 表達(dá)式集合P(x),P(f(y)是可合一的,其最一般合一為：=f(y)/x因為對此表達(dá)式集合的任一合一=f(a)/x, a/y 都有替換=a/y，使= =f(a)/x, a/y71定義 設(shè)W是非空表達(dá)式集合，W的差異集合是如下一個集合：首先找出W的所有表達(dá)式中不相同的第一個符號，然后從W的每個表達(dá)式中抽出占有這個位置的子表達(dá)式。所有這些子表達(dá)式的集合就是W 的差異集合。 例求表達(dá)式集合W=P(x,f(x,z),z),P(x,a),P(x,g(h(k(x),z)的差異集合解： 從P(x,f(x,z),z)中抽出f(x,z) 從P(x,a)中抽出a 從P(x

34、,g(h(k(x),z)中抽出g(h(k(x)得到W的差異集合=f(x,z),a,g(h(k(x)。2.合一算法72若W是非空表達(dá)式集合，D是W的差異集合，則有下面的結(jié)論：1.若D中無變量符號，則W是不可合一的，例如W=P(f(x),P(g(x)D=f(x),g(x)只有函數(shù)符號2.若D中只有一個元素，則W是不可合一的，例如W=P(x),P(x,y) D=y3.若D中有變量符號x和項t，且x出現(xiàn)在t中，則W是不可合一的，例如W=P(x),P(f(x) D=x,f(x)x出現(xiàn)在項f(x)中73求公式E1，E2的最一般合一算法（mgu算法）：步驟1：令W=E1,E2步驟2：令k=0, Wk=W,

35、k=步驟3：如果Wk只有一個元素，則停止， k是W的最一般合一；否則，找出Wk的差異集合Dk。步驟4：若D k中存在元素vk、t k，其中vk是變量符號，并且不出現(xiàn)在t k中，則轉(zhuǎn)到步驟5；否則，W是不可合一的，算法停止。步驟5：令k+1= k t k /vk， Wk+1=Wk+1 步驟6：K+1K,轉(zhuǎn)到步驟3。若E1,E2可合一，算法必停于步驟3。74例有公式E1=P(a,x,f(g(y) , E2=P(z,f(a),f(u) 求E1,E2的最一般合一mgu。解：根據(jù)算法1.W=E1 , E2=P(a,x,f(g(y) , P(z,f(a),f(u) 2.W0=W, 0= 3. W0未合一，

36、找出W0的差異集合D0=a,z4.取v0=z，t0=a5.令1= 0t0 /v0=a/zW1= W0 1 =P(a,x,f(g(y) , P(a,f(a),f(u) 3. W1未合一，找出W1的差異集合D1=x,f(a)4.取v1=x，t1=f(a)5.令2= 1t1 /v1=a/z,f(a)/xW2= W12 =P(a,f(a),f(g(y) , P(a,f(a),f(u) 3. W2未合一，找出W1的差異集合D2=g(y),u4.取v2=u，t2=g(y)5.令3= 2t2 /v2=a/z,f(a)/x,g(y)/u W3= W23=P(a,f(a),f(g(y) , P(a,f(a),f

37、(g(y) 3. W3已合一，此時3= a/z,f(a)/x,g(y)/u 是E1,E2的最一般合一mgu。75例有公式E1=Q(f(a),g(x) , E2=Q(y,y) 求E1,E2的最一般合一mgu。解：根據(jù)算法1.令W=E1 , E2=Q(f(a),g(x) , Q(y,y)2.W0=W, 0= 3. W0未合一，找出W0的差異集合D0=f(a),y4.取v0=y，t0=f(a)5.令1= 0t0 /v0=f(a)/yW1= W0 1 =Q(f(a),g(x) , Q(f(a),f(a)3. W1未合一，找出W1的差異集合D1=g(x),f(a)4. D1中無變量符號，算法停止，W不可

38、合一。76 歸結(jié)原理也稱消解原理，它可直接應(yīng)用到任意子句集S上，去檢驗S的不可滿足性。 歸結(jié)原理的本質(zhì)思想是去檢查子句集S是否包含一個空子句，如果S包含，則S是不可滿足的。如果S不包含 ，則去檢查是否可由S推導(dǎo)出來。當(dāng)然這個推理規(guī)則必須保證推出的子句是原親本子句的邏輯結(jié)果。歸結(jié)原理就是這樣一種推理規(guī)則。771. 命題邏輯中的歸結(jié)原理 定義：設(shè)C1與C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么從C1和C2中分別消去L1和L2,并將兩個子句中的余下部分析取，構(gòu)成一個新的子句C12，則稱這一過程為歸結(jié)。稱C12是C1和C2的歸結(jié)式。稱C1和C2是C12的親本子句。例

39、設(shè)C1=PQRC2=Q S可見C1中的文字L1=Q與C2中的文字L2=Q互補。因此可通過歸結(jié)得：C12=PR S例設(shè) C1=P， C2=P文字P與文字P互補，通過歸結(jié)可得：C12= 例設(shè)C1=PQ C2=Q R C3=P首先對C1，C2進(jìn)行歸結(jié)，得到 C12=PR 再對C12，C3進(jìn)行歸結(jié)，得 C123=R 78定理：歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。證明 設(shè)C1=LC1， C2=LC2，通過歸結(jié)可得到C12=C1C2C1和C2是C12的親本子句。 C1L= C1LL C2 =LC2 C1C2 = ( C1L) (LC2 )由假言三段論得到：( C1L) (LC2 ) ( C1C2

40、 ) C1C2= C1C2 = C12 C1C2 C1279由以上定理可得到如下兩個推論： 1.設(shè)C1與C2是子句集S中的兩個子句，C12是它們的歸結(jié)式，若用C12代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性。即：S1不可滿足S不可滿足 2.設(shè)C1與C2是子句集S中的兩個子句，C12是它們的歸結(jié)式，若把C12加入到S中，得到新子句集S2，則S與S2在不可滿足的意義上是等價的。即： S2不可滿足=S不可滿足 為了證明子句集S的不可滿足，只要對S中可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入子句集S，或用歸結(jié)式代替它的親本子句，然后證明新子句集不可滿足就可以了。如

41、果經(jīng)過歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，立即得到原子句集不可滿足的結(jié)論。 在命題邏輯中，對不可滿足的子句集S，歸結(jié)原理是完備的。這就是說：若子句集S不可滿足，則必然存在一個從S到空子句的歸結(jié)演繹；若存在一個從S到空子句的歸結(jié)演繹，則S一定是不可滿足的。 對于可滿足的子句集S，用歸結(jié)原理得不到任何結(jié)論。802. 謂詞邏輯中的歸結(jié)原理 在謂詞邏輯中，由于子句中含有變元，所以不能直接消去互補文字，需要用最一般合一對變元進(jìn)行代換，然后才能進(jìn)行歸結(jié)。例如：有子句 C1=P(x)Q(x) C2=P(a)R(y)C1的P(x)與C2的P(a)不同，所以不能直接將C1與C2進(jìn)行歸結(jié)?？上扔米钜话愫弦?

42、a/x分別對C1，C2進(jìn)行代換：C1 =P(a)Q(a) C2 =P(a)R(y)再對C1 ，C2 進(jìn)行歸結(jié)，消去P(a) 、P(a)得到C1與C2的歸結(jié)式 Q(a) R(y)。 定義 如果子句C中，兩個或兩個以上的文字有一個最一般合一，則C稱為C的因子；如果C是單元子句，則稱C是C的單因子。如：C=P(x) P(f(y) Q(x)令=f(y)/x，則 C = P(f(y) Q(x) C是C的因子。81 定義 設(shè)C1，C2是兩個無公共變量的子句，L1，L2分別是C1，C2中的兩個文字。如果L1和 L2有最一般合一，則稱子句：C12=(C1 L1) (C2 L2)為C1和C2的歸結(jié)式，L1，L2

43、稱為歸結(jié)文字。例設(shè)C1=P(a)Q(x)R(x)C2=P(y)Q(b)若取L1=P(a),L2=P(y), =a/y 有L1=P(a) L2=P(a)由定義可得：C12=(C1 L1) (C2 L2)=(P(a),Q(x),R(x)P(a) (P(a),Q(b)P(a)有時將子句寫成文字的集合，要理解文字之間是合取關(guān)系=Q(x),R(x), Q(b)=Q(x) R(x) Q(b)82例 設(shè)C1=P(x) Q(x)C2=P(a) R(x)在子句C1C2中有相同的變元x，與定義的要求不符。為進(jìn)行歸結(jié)，先將C2中的x改名為y，令C2=P(a) R(y)并取L1=P(x),L2=P(a), =a/x,

44、則C12=(C1 L1) (C2 L2)=(P(a) , Q(a) P(a) (P(a) ,R(y) P(a)=Q(a),R(y)= Q(a) R(y)例設(shè)C1=P(x) P(f(y) R(g(y) C2=P(f(g(a) Q(b)1=f(y)/x,則C1的因子C11 = P(f(y) R(g(y)。于是C11和C2的歸結(jié)式，也是C1和C2的歸結(jié)式： R(g(g(a) Q(b)83 對于謂詞邏輯，歸結(jié)式是它的親本子句的邏輯結(jié)論。用歸結(jié)式取代它在子句集S中的親本子句所得的新子句集仍然保持著原子句集S的不可滿足性。 對于一階謂詞邏輯，從不可滿足的意義上說，歸結(jié)原理也是完備的，即：若子句集是不可滿足

45、的，則必然存在一個從該子句集到空子句的歸結(jié)演繹；若存在一個從子句集到空子句的演繹，則子句集是不可滿足的。84 從子句集出發(fā)，通過歸結(jié)原理可得到一個向下的演繹樹，其每個初始結(jié)點代表著S的一個子句，每一個非初始結(jié)點代表著一個其前任結(jié)點上的子句歸結(jié)式。例S=P Q,P Q,P Q,P Q歸結(jié)演繹過程用演繹樹表示如下：12345672 PQ1 PQ3 PQ4 PQ5 Q 由1 , 2歸結(jié)6 Q 由3 , 4歸結(jié)7 由5 , 6歸結(jié)初始節(jié)點：非初始節(jié)點：123485 歸結(jié)原理顯然是一個很好的推理規(guī)則，但我們一般不使用它直接從前提推導(dǎo)結(jié)論，而是通過推導(dǎo)空子句來作間接證明。具體地將，就是先求出要證的命題公式

46、（或謂詞公式）的否定式的子句集S，然后對子句集S（一次或多次）使用消解原理，若在某一步推出了空子句，即說明子句集S是不可滿足的，從而原否定式也是不滿足的，進(jìn)而說明原公式是永真的。 即，對于那些由前提推結(jié)論的問題，并不需要先求出其整個謂詞公式，然后再求其否定式，而只需把求證結(jié)論的否定式加入前提公式即可。例 用歸結(jié)原理證明R是P，(P Q)R，(S U) Q，U的邏輯結(jié)果。證 先把諸前提條件化為子句形式，再把結(jié)論的否定也化為子句，然后對該子句集實施歸結(jié)。86例 求證明G是A1和A2的邏輯結(jié)果。A1: x(P(x) (Q(x) R(x)A2: x(P(x) S(x)G: x(S(x) R(x)證 用

47、反證法。例 設(shè)已知：(1)能閱讀者是識字的； (2)海豚不識字； (3)有些海豚是很聰明的。 求證：有些聰明者并不能閱讀。證 首先定義謂詞：R(x):x能閱讀；L(x):x能識字；I(x):x是聰明的；D(x):x是海豚。然后將上述各語句翻譯為謂詞公式 87例 已知：。(1)如果x和y是同班同學(xué)，則x的老師也是y的老師。(2)王先生是小李的老師(3)小李和小張是同班同學(xué)。問？小張的老師是誰？解解 設(shè)謂詞T(x,y)表示x是y的老師，C(x,y)表示x和y是同班同學(xué)，則已知可表示為下面的謂詞公式： 為了得到問題的答案，先證明小張的老師是存在的。88已知一串香蕉掛在天花板上，猴子直接去拿是夠不到的

48、，但猴子可以走動且可以搬著梯子走動，也可以爬上梯子來達(dá)到吃香蕉的目的。對這個問題的描述，不可忽視動作的先后次序，需體現(xiàn)出時間概念。常用的方法是引入狀態(tài)S來區(qū)分動作的先后，以不同的狀態(tài)表現(xiàn)不同的時間，而狀態(tài)間的轉(zhuǎn)換由一些算子(函數(shù))來實現(xiàn)。89l首先引入謂詞 P(x,y,z,s)表示猴子位于x處，香蕉位于y 處，梯子位于z處，相應(yīng)的狀態(tài)為s?；蛘f猴子在x 處，香蕉在y 處，梯子在z處，而狀態(tài)又為s時，謂詞P(x,y,z,s)方為真。R(s)表示s狀態(tài)下猴子吃到香蕉。ANS(s)表示形式謂詞 ，只是為求得回答的動作序列而虛設(shè)的。 90l其次引入狀態(tài)轉(zhuǎn)移函數(shù)。Walk (y,z,s)表示原狀態(tài)s下，

49、在walk作用下猴子從y走到z 處所建立的一個新狀態(tài)。lCarry(y,z,s)表示原狀態(tài)s 下，在Carry 作用下猴子搬著梯子從y走到z 處建立的一個新狀態(tài)。lClimb(s) 表示原狀態(tài)s下，在Climb作用下猴子爬上梯子所建立的一個新狀態(tài)。l設(shè)初始狀態(tài)為S0,猴子位于a,香蕉位于b ,梯子位于c。919293l（1）P(x,y,z,s) P(z,y,z,walk(x,z,s)（2）P(x,y,x,s) P(y,y,y,Carry(x,y,s)（3）P(b,b,b,s) R(Climb (s)（4）P(a,b,c,s)（5）R(s) ANS(s)（6）P(b,b,b,s) ANS(Cli

50、mb(s)(3)(5)歸結(jié)（7）P(x,b,x,s) ANS(Climb(Carry(x,b,s) (2)(6)歸結(jié)（8）P(x,b,z,s) ANS(Climb(Carry(z,b,walk(x,z,s) (1)(7)歸結(jié)（9）ANS(Climb(Carry(c,b,walk(a,c,s) (4)(8)歸結(jié)于是猴子吃香蕉的問題的答案是Climb (Carry(c,b,walk(a,c,s) 943.4 用歸結(jié)原理證明定理的過程成為歸結(jié)反演。歸結(jié)反演的步驟：設(shè)已知前提的公式集F,目標(biāo)公式為Q。1.否定Q，得到Q。2.把Q并入到公式集F中，得到F,Q。3.把公式集F,Q化為子句集S。4.應(yīng)用歸結(jié)

51、原理對子句集S中的子句進(jìn)行歸結(jié)，并把每次得到的歸結(jié)式再并入S中，如此反復(fù)進(jìn)行，若出現(xiàn)空子句則停止，此時就證明了定理。95例 已知某些病人喜歡所有的醫(yī)生，沒有一個病人喜歡任意一個騙子。證明：任意一個醫(yī)生都不是騙子。證明：令：P(x):x是病人 D(x):x是醫(yī)生Q(x):x是騙子L(x,y):x喜歡yA1:x(P(x)y(D(y)L(x,y)某些病人喜歡所有的醫(yī)生A2:x(P(x)y(Q(y)L(x,y)沒有一個病人喜歡任意一個騙子B: x(D(x) Q(x)任意一個醫(yī)生都不是騙子為證明公式A1 A2 B是不可滿足的，先求出A1 A2 B的子句集。A1 =x(P(x)y(D(y)L(x,y) =

52、x(P(x)y(D(y) L(x,y) =xy(P(x) (D(y) L(x,y) =y(P(a) (D(y) L(a,y)A2 =x(P(x)y(Q(y)L(x,y) =x(P(x)y(Q(y) L(x,y) =x(P(x) y(Q(y) L(x,y) =xy(P(x) Q(y) L(x,y)B= x(D(x) Q(x) = x (D(x) Q(x) = x (D(x) Q(x) = x (D(x) Q(x) = D(b) Q(b)得到公式A1 A2 B的子句集：S=P(a), D(y) L(a,y), P(x) Q(y) L(x,y), D(b) , Q(b)96對子句集 S=P(a),

53、D(y) L(a,y), P(x) Q(y) L(x,y), D(b) , Q(b)應(yīng)用歸結(jié)原理：1. P(a)2. D(y) L(a,y)3. P(x) Q(y) L(x,y) 4.D(b)5.Q(b)6.L(a,b) 由2,4歸結(jié)7. Q(y) L(a,y) 由1,3歸結(jié)8. L(a,b) 由5,7歸結(jié)9. 由6,8歸結(jié)對應(yīng)的演繹樹：D(y) L(x,y) D(b)P(a)P(x) Q(y) L(x,y)Q(b)L(a,b)Q(y) L(a,y)L(a,b)97例 若A1= x(A(x)B(x)C(x) A2=x(A(x)D(x) B= x(D(x)C(x)求證B是A1 A2的邏輯結(jié)論。證

54、明求證A1 A2 B，就是證明公式A1 A2 B是不可滿足的。將A1 ， A2 ， B分別化成Skolem標(biāo)準(zhǔn)型，求子句集S。A1= x(A(x)B(x)C(x)= x(A(x) (B(x)C(x)= x(A(x) B(x)(A(x) C(x) )A2=x(A(x)D(x)Skolem范式：A(a) D(a)B= x(D(x)C(x)= x(D(x) C(x)公式A1 A2 B對應(yīng)的子句集為：S=A(x) B(x), A(x) C(x) , A(a) ,D(a), D(x) C(x)98對S=A(x) B(x), A(x) C(x) , A(a) ,D(a), D(x) C(x)應(yīng)用歸結(jié)原理：1. A(x) B(x),2. A(x) C(x) 3. A(a) 4. D(a)5. D(x) C(x)7. C(a)由4、56.C(a)由2、38. 由6、7993.5 計算機(jī)在對子句集進(jìn)行歸結(jié)時，由于事先不知道哪兩個子句可以進(jìn)行歸結(jié)，更不知道通過哪些子句的歸結(jié)可以盡快得到空子句，因而必須對子句集中的所有子句逐對地進(jìn)行比較，對任何一對可以歸結(jié)的子句都進(jìn)行歸結(jié)。 這樣不僅耗費時間，而且會導(dǎo)致大量不必要的無用的歸結(jié)式產(chǎn)生。為提高歸結(jié)效率，就需要給出歸結(jié)控制策略，使歸結(jié)過程中避免多余的不必要的歸結(jié)式出