人工智能第2章(知識(shí)表示方法3-謂詞邏輯)74

1、人人 工工 智智 能能Artificial Intelligence (AI)許建華許建華南京師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院南京師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2011年秋季年秋季第第2章章 知識(shí)表示方法知識(shí)表示方法2.1 狀態(tài)空間法狀態(tài)空間法2.2 問題歸約法問題歸約法2.3 謂詞邏輯法謂詞邏輯法2.3 謂詞邏輯法謂詞邏輯法數(shù)理邏輯數(shù)理邏輯（符號(hào)邏輯）是用數(shù)學(xué)方法研究形式邏（符號(hào)邏輯）是用數(shù)學(xué)方法研究形式邏輯的一個(gè)分支。輯的一個(gè)分支。它它通過符號(hào)系統(tǒng)來表達(dá)客觀對(duì)象通過符號(hào)系統(tǒng)來表達(dá)客觀對(duì)象以及相關(guān)的邏輯推理。常用的是以及相關(guān)的邏輯推理。常用的是命題邏輯命題邏輯和和謂謂詞邏輯詞邏輯謂詞邏輯謂詞邏輯是

2、數(shù)理邏輯的基本形式，是基于謂詞是數(shù)理邏輯的基本形式，是基于謂詞分析的一種形式化（數(shù)學(xué)）語言分析的一種形式化（數(shù)學(xué)）語言人工智能中的謂詞邏輯法人工智能中的謂詞邏輯法是指用一階謂詞是指用一階謂詞來描述問題求解和定理證明（來描述問題求解和定理證明（限于本課程限于本課程）2.3.0 命題邏輯的復(fù)習(xí)命題邏輯的復(fù)習(xí) 1、命題邏輯的基本概念命題邏輯的基本概念命題命題 是能夠判斷是能夠判斷真真或或假假的的陳述句陳述句通常用通常用大寫字母大寫字母來表示，如來表示，如A, B, P, Q等等命題的真假值一般用命題的真假值一般用 T 或或 F 來表示來表示 例例：雪是白的。（陳述句，雪是白的。（陳述句，T）雪是藍(lán)的

3、。（陳述句，雪是藍(lán)的。（陳述句，F(xiàn)）雪是黑的。（陳述句，雪是黑的。（陳述句，F(xiàn)）他他是學(xué)生。（陳述句，他泛指，無法判斷真假）是學(xué)生。（陳述句，他泛指，無法判斷真假）你今天上課沒有？（疑問句）你今天上課沒有？（疑問句）去北校區(qū)，請(qǐng)坐校車?。ㄆ硎咕洌┤ケ毙^(qū)，請(qǐng)坐校車?。ㄆ硎咕洌?命題邏輯命題邏輯是研究是研究命題命題及及命題之間命題之間關(guān)系的符關(guān)系的符號(hào)邏輯系統(tǒng)。號(hào)邏輯系統(tǒng)。在命題邏輯中，表示單一意義的命題，稱之為在命題邏輯中，表示單一意義的命題，稱之為原原子命題子命題。原子命題通過原子命題通過 “ “聯(lián)結(jié)詞聯(lián)結(jié)詞” ” 構(gòu)成構(gòu)成 復(fù)合命題復(fù)合命題。五個(gè)聯(lián)結(jié)詞五個(gè)聯(lián)結(jié)詞： “” ” 表示表示 “

4、“非非”復(fù)合命題復(fù)合命題P為真，當(dāng)且僅當(dāng)為真，當(dāng)且僅當(dāng)P為假。為假。 “” “” 表示表示 “ “合取合取”復(fù)合命題復(fù)合命題“PQ”為真，當(dāng)且僅當(dāng)為真，當(dāng)且僅當(dāng)P和和Q都為真。都為真。 “” ” 表示表示 “ “蘊(yùn)含蘊(yùn)含”復(fù)合命題復(fù)合命題“PQ”為假，當(dāng)且僅當(dāng)為假，當(dāng)且僅當(dāng)P為真且為真且Q為為假。假。 “” “” 表示表示 “ “析取析取”復(fù)合命題復(fù)合命題“PQ”為真，當(dāng)且僅當(dāng)為真，當(dāng)且僅當(dāng)P、Q兩者之兩者之一為真。一為真。 “” ” 表示表示 “ “等價(jià)等價(jià)”復(fù)合命題復(fù)合命題“PQ”為真，當(dāng)且僅當(dāng)為真，當(dāng)且僅當(dāng)P、Q同時(shí)為真、同時(shí)為真、或者同時(shí)為假?；蛘咄瑫r(shí)為假。 聯(lián)接詞的聯(lián)接詞的優(yōu)先順序優(yōu)

5、先順序：非非 、合取合取 、析取析取 、蘊(yùn)含蘊(yùn)含 、等價(jià)等價(jià)注注：可以用括號(hào)表示優(yōu)先級(jí)：可以用括號(hào)表示優(yōu)先級(jí)真值表真值表 PQPPQPQPQPQFFTFFTTFTTFTTFTFFFTFFTTFTTTT命題變?cè)}變?cè)河梅?hào)：用符號(hào)P、Q等表示的不具有固定、具等表示的不具有固定、具體含義的命題。它可以表示具有體含義的命題。它可以表示具有“真真”、“假假”含含義的各種命題。義的各種命題。命題變?cè)梢岳寐?lián)結(jié)詞構(gòu)成所謂的命題變?cè)梢岳寐?lián)結(jié)詞構(gòu)成所謂的合適公式合適公式。 合適公式的定義合適公式的定義若若P為原子命題，則為原子命題，則P為合適公式，稱為原子公為合適公式，稱為原子公式。式。若若P是合適

6、公式，則是合適公式，則P也是一個(gè)合適公式。也是一個(gè)合適公式。若若P和和Q是合適公式，則是合適公式，則PQ、 PQ 、PQ 、PQ都是合適公式。都是合適公式。經(jīng)過經(jīng)過有限次使用有限次使用規(guī)則規(guī)則1、2、3，得到的由原子公，得到的由原子公式、聯(lián)結(jié)詞和園括號(hào)所組成的符號(hào)串，也是合適式、聯(lián)結(jié)詞和園括號(hào)所組成的符號(hào)串，也是合適公式。公式。對(duì)于合適公式，規(guī)定下列對(duì)于合適公式，規(guī)定下列運(yùn)算優(yōu)先級(jí)運(yùn)算優(yōu)先級(jí)： 邏輯聯(lián)結(jié)詞的運(yùn)算優(yōu)先次序?yàn)椋哼壿嬄?lián)結(jié)詞的運(yùn)算優(yōu)先次序?yàn)椋?、 、 、 同級(jí)聯(lián)結(jié)詞按出現(xiàn)順序優(yōu)先運(yùn)算同級(jí)聯(lián)結(jié)詞按出現(xiàn)順序優(yōu)先運(yùn)算 在命題邏輯中，主要研究推理的有效性。在命題邏輯中，主要研究推理的有效性。即

7、：能否根據(jù)一些合適公式（即：能否根據(jù)一些合適公式（前提前提）推導(dǎo)出新的）推導(dǎo)出新的合適公式（合適公式（結(jié)論結(jié)論）。）。 一些合適公式一些合適公式（前提條件）（前提條件）合適公式合適公式（結(jié)論）（結(jié)論）？在命題邏輯中，最基本的單元是命題，它是在命題邏輯中，最基本的單元是命題，它是作為一個(gè)不可分割的整體。作為一個(gè)不可分割的整體。例如：例如：雪是黑的雪是黑的命題邏輯具有較大的局限性，不合適于表達(dá)命題邏輯具有較大的局限性，不合適于表達(dá)比較復(fù)雜的問題。比較復(fù)雜的問題。例例：所有科學(xué)都是有用的所有科學(xué)都是有用的（假設(shè)（假設(shè)1）。數(shù)理邏輯是科學(xué)數(shù)理邏輯是科學(xué)（假設(shè)（假設(shè)2）。所以，數(shù)理邏輯是有用的所以，數(shù)理

8、邏輯是有用的（結(jié)論）（結(jié)論）。很明顯，我們無法用很明顯，我們無法用兩個(gè)假設(shè)兩個(gè)假設(shè)推斷出推斷出結(jié)論結(jié)論。謂詞邏輯謂詞邏輯是命題邏輯的擴(kuò)充和發(fā)展。它將一個(gè)原是命題邏輯的擴(kuò)充和發(fā)展。它將一個(gè)原子命題分解成子命題分解成客體客體和和謂詞謂詞兩個(gè)組成部分。兩個(gè)組成部分。例如：例如： 雪雪 是黑的是黑的 客體客體 謂詞謂詞本課程主要介紹一階謂詞邏輯。本課程主要介紹一階謂詞邏輯。 2.3.1 謂詞演算謂詞演算 1 1、語法與語義、語法與語義謂詞邏輯的基本組成部分謂詞邏輯的基本組成部分 謂詞謂詞 變量變量 函數(shù)函數(shù) 常量常量 園括號(hào)園括號(hào)、方括號(hào)、花括號(hào)和逗號(hào)、方括號(hào)、花括號(hào)和逗號(hào)例例“機(jī)器人（機(jī)器人（Rob

9、ot）在第一個(gè)房間（在第一個(gè)房間（Room1）內(nèi)內(nèi)”，可以表示為：可以表示為： INROOM（ROBOT，r1）其中其中 INROOM是是謂詞謂詞 ROBOT和和r1是是常量常量謂詞謂詞是指個(gè)體（客體）所具有的是指個(gè)體（客體）所具有的性質(zhì)性質(zhì)或者若干個(gè)體或者若干個(gè)體之間的之間的關(guān)系關(guān)系。用。用大寫字母大寫字母來表示。來表示。 個(gè)體個(gè)體是可以具體的（如是可以具體的（如: : 小張、小張、3、5）也可以是抽）也可以是抽象的（如象的（如: : x, y）。）。例例：小明是學(xué)生，小明是學(xué)生，A表示是表示是“是學(xué)生是學(xué)生”，x表示表示“小小明明”，記作，記作A(x)。x大于大于y，G表示表示“大于大于”

10、，記作，記作G（x, y）。）。論域論域：由個(gè)體組成的集合。：由個(gè)體組成的集合。（個(gè)體個(gè)體）變量變量：定義在某一個(gè)論域上的變量。用：定義在某一個(gè)論域上的變量。用x, y, z 來表示。來表示。函數(shù)函數(shù)（或函詞）（或函詞）：以個(gè)體為變量，以個(gè)體為值的：以個(gè)體為變量，以個(gè)體為值的函數(shù)。一般用小寫字母來表示，例如函數(shù)。一般用小寫字母來表示，例如 f(x), f(x,a)。 如果謂詞有如果謂詞有 n 個(gè)變量，稱之為個(gè)變量，稱之為 n 元謂詞，并約定元謂詞，并約定 0 元謂詞就是命題（謂詞的特例）。元謂詞就是命題（謂詞的特例）。如果函數(shù)有如果函數(shù)有 n 個(gè)個(gè)體，稱之為個(gè)個(gè)體，稱之為 n 元函數(shù)，并約定元

11、函數(shù)，并約定 0 元函數(shù)就是常量。常量習(xí)慣上用小寫字母來表元函數(shù)就是常量。常量習(xí)慣上用小寫字母來表示，如示，如a, b, c。項(xiàng)項(xiàng)的定義：的定義：常量是項(xiàng)常量是項(xiàng)變量是項(xiàng)變量是項(xiàng)如果如果 f 是是n元函數(shù)，且元函數(shù)，且t1 , tn(n1)是項(xiàng)，則是項(xiàng)，則 f (t1 , tn)也是項(xiàng)也是項(xiàng)所有的項(xiàng)都必須是有限次應(yīng)用上述規(guī)則產(chǎn)生的所有的項(xiàng)都必須是有限次應(yīng)用上述規(guī)則產(chǎn)生的項(xiàng)的例子項(xiàng)的例子：常量：常量：a變量：變量：x函數(shù)：函數(shù)：f(x,a) g(f(x,a)原子（謂詞）公式原子（謂詞）公式的（遞歸）定義：的（遞歸）定義：原子命題是原子公式原子命題是原子公式如果如果t1,tn(n1)是項(xiàng)，是項(xiàng)，P

12、是謂詞，則是謂詞，則P(t1,tn)是原子公式是原子公式其它表達(dá)式都不是原子公式其它表達(dá)式都不是原子公式 原子公式的例子原子公式的例子1、原子公式：、原子公式：P（原子命題）原子命題）2、項(xiàng)：、項(xiàng)：x, a, f(x, a)，謂詞：謂詞：P 原子公式：原子公式：P(x, a, f(x,a)2、連詞和量詞、連詞和量詞聯(lián)結(jié)詞（連詞）聯(lián)結(jié)詞（連詞）就是命題邏輯中的五個(gè)，它們的就是命題邏輯中的五個(gè)，它們的含義也是一樣的。含義也是一樣的。兩個(gè)量詞兩個(gè)量詞：全稱量詞全稱量詞，記作，記作“ x x”,”,含義是含義是 “對(duì)每一個(gè)對(duì)每一個(gè)x x” 或或“對(duì)一切對(duì)一切x x”。存在量詞存在量詞，記作，記作“ x

13、 x”，含義是含義是 “存在某個(gè)存在某個(gè)x x” 、“有一個(gè)有一個(gè)x x” 或者或者 “某些某些x x”。 AllAExistE例例1：“所有的機(jī)器人都是灰色的所有的機(jī)器人都是灰色的”，用謂詞邏輯，用謂詞邏輯可以表示成：可以表示成： （ x）ROBOT(x) COLOR(x，gray)例例2： “一號(hào)房間里有一個(gè)物體一號(hào)房間里有一個(gè)物體”，可以表示成，可以表示成 （ x）INROOM（x , r1） 我們稱我們稱 x 是被量化了的變量，稱為是被量化了的變量，稱為約束變量約束變量。否則稱之為否則稱之為自由變量自由變量。一階謂詞一階謂詞：只允許對(duì)：只允許對(duì)變量變量施加施加量詞量詞，不允許對(duì)，不允許

14、對(duì)謂詞和函數(shù)施加量詞。謂詞和函數(shù)施加量詞。2.3.2 謂詞公式謂詞公式1、謂詞公式的定義謂詞公式的定義 利用連詞和量詞可以將原子（謂詞）公式組成復(fù)利用連詞和量詞可以將原子（謂詞）公式組成復(fù)合謂詞公式，稱之為分子謂詞公式、謂詞合適公合謂詞公式，稱之為分子謂詞公式、謂詞合適公式、式、謂詞公式謂詞公式、合適公式、合適公式。 （謂詞）（謂詞）合適公式合適公式 的（遞歸）定義：的（遞歸）定義：原子（謂詞）公式是合適公式。原子（謂詞）公式是合適公式。若若 A 是合適公式，則是合適公式，則 A 也是合適公式。也是合適公式。若若 A 和和 B 是合適公式，則是合適公式，則 AB 、AB 、AB 、AB 也是合

15、適公式。也是合適公式。若若 A 是合適公式，是合適公式， x 為為 A 的自由變?cè)ㄗ兊淖杂勺冊(cè)ㄗ兞浚?，則量），則（ x）A 和和（ x）A 都是合適公式。都是合適公式。只有按上述規(guī)則求得的公式才是合適公式。只有按上述規(guī)則求得的公式才是合適公式。 例：任何整數(shù)或者為正或者為負(fù)。例：任何整數(shù)或者為正或者為負(fù)。數(shù)學(xué)表達(dá)數(shù)學(xué)表達(dá)：對(duì)于所有的：對(duì)于所有的 x，如果如果 x 是整數(shù)，則是整數(shù)，則 x 或或者為正、或者為負(fù)。者為正、或者為負(fù)。記作記作： I(x)：“ x 是整數(shù)是整數(shù)”。 P(x)：“ x 是正數(shù)是正數(shù)”。 N(x)：“ x 是負(fù)數(shù)是負(fù)數(shù)”。謂詞公式謂詞公式： （ x）（）（I(x) (

16、P(x) N(x)）2、合適公式的性質(zhì)、合適公式的性質(zhì) 如果如果 P 和和 Q 是合適公式，則由這兩個(gè)合適公是合適公式，則由這兩個(gè)合適公式構(gòu)成的合適公式的式構(gòu)成的合適公式的真值表真值表與前面介紹的與前面介紹的真值真值表表相同。相同。 如果兩個(gè)合適公式的真值表相同，則我們稱這如果兩個(gè)合適公式的真值表相同，則我們稱這兩個(gè)合適公式是等價(jià)的兩個(gè)合適公式是等價(jià)的，可以用，可以用“”來表示。來表示。 對(duì)于命題合適公式和謂詞合適公式有下列等價(jià)關(guān)系：對(duì)于命題合適公式和謂詞合適公式有下列等價(jià)關(guān)系： 否定之否定否定之否定： （P） 等價(jià)于等價(jià)于 P PQ 等價(jià)于等價(jià)于 PQ狄狄.摩根定律摩根定律 （PQ）等價(jià)于等

17、價(jià)于 PQ （PQ）等價(jià)于等價(jià)于 PQ分配律分配律 P(QR) 等價(jià)于等價(jià)于 (PQ)(PR) P(QR) 等價(jià)于等價(jià)于 (PQ)(PR)交換律交換律 PQ 等價(jià)于等價(jià)于 QP PQ 等價(jià)于等價(jià)于 QP結(jié)合律結(jié)合律 (PQ)R 等價(jià)于等價(jià)于 P(QR) (PQ)R 等價(jià)于等價(jià)于 P(QR)逆否律逆否律 PQ 等價(jià)于等價(jià)于 QP說明說明：上述等價(jià)關(guān)系對(duì)命題合適公式、謂詞合適上述等價(jià)關(guān)系對(duì)命題合適公式、謂詞合適公式都成立。公式都成立。對(duì)于謂詞合適公式有下列等價(jià)關(guān)系：對(duì)于謂詞合適公式有下列等價(jià)關(guān)系： ( x)P(x) 等價(jià)于等價(jià)于 ( x)P(x) ( x)P(x) 等價(jià)于等價(jià)于 ( x)P(x)

18、( x)P(x)Q(x) 等價(jià)于等價(jià)于 ( x)P(x)( x)Q(x) ( x)P(x)Q(x) 等價(jià)于等價(jià)于 ( x)P(x) ( x)Q(x) ( x)P(x) 等價(jià)于等價(jià)于 ( y)P(y) ( x)P(x) 等價(jià)于等價(jià)于 ( y)P(y)注釋注釋：這兩個(gè)關(guān)系說明，在一個(gè)量化的表達(dá)式中這兩個(gè)關(guān)系說明，在一個(gè)量化的表達(dá)式中的約束變量是一類虛元，它們可以用任何不在表的約束變量是一類虛元，它們可以用任何不在表達(dá)式中出現(xiàn)的其它變量來代替。達(dá)式中出現(xiàn)的其它變量來代替。 2.3.3 置換與合一置換與合一 1、置換、置換 置換的定義置換的定義：形如：形如 t1 / v1 , , tn / vn 的集

19、合，稱為一個(gè)置換，其中的集合，稱為一個(gè)置換，其中 vi 是不同的變量，是不同的變量，ti 是與是與 vi 不同的項(xiàng)。不同的項(xiàng)。 例或例子的定義例或例子的定義：設(shè)設(shè) t1/v1 , , tn/vn 為一個(gè)置換，為一個(gè)置換，E是一個(gè)原子謂詞公式。則是一個(gè)原子謂詞公式。則E表表示將示將E中的中的 vi 同時(shí)用同時(shí)用 ti（i=1,n）代入后所得代入后所得到的結(jié)果，到的結(jié)果，E稱為稱為E的一個(gè)的一個(gè)例子例子。 例例：表達(dá)式（原子謂詞公式）：表達(dá)式（原子謂詞公式）Px,f(y),B的四個(gè)置的四個(gè)置換及其對(duì)應(yīng)的四個(gè)例子換及其對(duì)應(yīng)的四個(gè)例子 （B是常量是常量） s1=z/x, w/ys2=A/y s3=q(

20、z)/x, A/ys4=c/x, A/y Px, f(y), Bs1=Pz, f(w), BPx, f(y), Bs2=Px, f(A), B Px, f(y), Bs3=Pq(z), f(A), BPx, f(y), Bs4=Pc, f(A), BPx,f(y),B置換的合成置換的合成：設(shè)：設(shè)t1/x1, ,tn/xn和和s1/y1, ,sm/ym是兩個(gè)置換，則是兩個(gè)置換，則和和的合成是如下置的合成是如下置換：換： t1/x1 , ti/xi , tn/xn, s1/y1, , sn/ym 其中，若其中，若yj 是是 x1,xn 之一者消去，對(duì)于任何之一者消去，對(duì)于任何 tj=xj 者消去，

21、并記成者消去，并記成。如何求如何求 ti :s1/y1 , , sm/ym如果如果 ti 出現(xiàn)出現(xiàn) y1, ., ym中的變量中的變量 yi ， 則用其對(duì)則用其對(duì)應(yīng)的項(xiàng)應(yīng)的項(xiàng) si 來代替。來代替。例：例： = t1/x1 , t2/x2f(y)/x , z/y = s1/y1 , s2/y2 , s3/y3 = a/x , b/y , y/z =t1/x1 , t2/x2 , s1/y1 , s2/y2 , s3/y3 =f(b)/x , , , b/ , y/z =f(b)/x , y/z注意注意：置換的合成滿足結(jié)合律，不滿足交換律。置換的合成滿足結(jié)合律，不滿足交換律。 (s1s2)s3

22、= s1(s2s3) ( (滿足滿足結(jié)合律結(jié)合律） s1s2 s2s1 （不不滿足滿足交換律交換律）例例： s1=z/x , w/y s2=A/y s1s2=z/x , w/y , A/y=z/x , w/y s2s1=A/y, z/x , w/y=A/y , z/x2、合一、合一 當(dāng)某一個(gè)置換當(dāng)某一個(gè)置換 s 作用于表達(dá)式集合作用于表達(dá)式集合 Ei 的每一個(gè)元的每一個(gè)元素，此時(shí)我們用素，此時(shí)我們用 Eis 來表示置換例子的集合。如來表示置換例子的集合。如果存在一個(gè)置換果存在一個(gè)置換 s ，使得使得 E1s = E2s = = Eis = 則我們稱表達(dá)式集合則我們稱表達(dá)式集合 Ei 是可合一的

23、，并稱是可合一的，并稱 s 為為Ei 的合一者。原因是它的作用是使集合的合一者。原因是它的作用是使集合 Ei 成成為單一形式。為單一形式。 其中，其中，Ei 是原子謂詞公式。是原子謂詞公式。例例：表達(dá)式集合表達(dá)式集合Px , f(y) , B , Px , f(B) , B的合一的合一者為是者為是 s = A/x , B/y Px , f(y) , Bs = PA , f(B) , B Px , f(B) , Bs = PA , f(B) , B如果如果 s 是是 Ei 的的任意任意一個(gè)合一者，又存在某一一個(gè)合一者，又存在某一個(gè)個(gè) s，使得使得 s = g s 或者或者 Ei s = Ei g

24、 s則則 稱稱 g 是是 Ei 的最通用（最一般）的合一者，的最通用（最一般）的合一者，記作記作mgu。 例例：s = A/x , B/y 是表達(dá)式集合是表達(dá)式集合 Px , f(y) , B , Px , f(B) , B的一個(gè)合一者，該集合的的一個(gè)合一者，該集合的最一般的合一者最一般的合一者是：是： g = B/y3、合一算法、合一算法 分歧集（或不一致集合）的定義分歧集（或不一致集合）的定義。設(shè)有一非空有限公式集合設(shè)有一非空有限公式集合 F = F1 , , Fn，從從 F中各個(gè)公式的第一個(gè)符號(hào)同時(shí)向右比較，直到發(fā)現(xiàn)中各個(gè)公式的第一個(gè)符號(hào)同時(shí)向右比較，直到發(fā)現(xiàn)第一個(gè)彼此不盡相同的符號(hào)為止

25、，從第一個(gè)彼此不盡相同的符號(hào)為止，從 F 中的各個(gè)中的各個(gè)公式中取出那些以第一個(gè)不一致符號(hào)開始的公式中取出那些以第一個(gè)不一致符號(hào)開始的為元素，組成一個(gè)集合為元素，組成一個(gè)集合 D ，稱為稱為 F 的分的分歧集（不一致集合）。歧集（不一致集合）。 其中，其中，F(xiàn) i ( i=1 , , n)是原是原子謂詞公式子謂詞公式例例：公式集：公式集：F=P(x , g( f(y , z) , x) , y), P(x , g( a , b) , b) , P(x , g( g(h(x) , a) , y) , h(x)分歧集為：分歧集為： D=f(y , z) , a , g(h(x) , a) 設(shè)設(shè) F

26、 為非空有限表達(dá)式集合，則可以按下列步驟為非空有限表達(dá)式集合，則可以按下列步驟求出求出 mgu： 置置 k=0 ，F(xiàn)k = F ,k=(空置換，即不含元素的空置換，即不含元素的置換置換)。 若若 Fk 只有一個(gè)表達(dá)式，則算法終止，其中只有一個(gè)表達(dá)式，則算法終止，其中k就是就是要求的要求的mgu。 找出找出 Fk 的分歧集的分歧集 Dk 。 合一算法合一算法：若若 Dk 中存在元素中存在元素 ak 和和 tk ，其中其中 ak 是變?cè)?，是變?cè)瑃k是項(xiàng)，且是項(xiàng)，且 ak 不在不在 tk 中出現(xiàn)，則置：中出現(xiàn)，則置： k+1 =k tk / ak Fk+1 = Fk tk / ak k = k+1

27、然后轉(zhuǎn)向然后轉(zhuǎn)向。否則，繼續(xù)。否則，繼續(xù)。算法終止，算法終止，F(xiàn)的的 mgu 不存在。不存在。 合一算法的流程圖合一算法的流程圖k=0, Fk=F,k=|Fk|1？求得求得mgu、結(jié)束結(jié)束求出不一致集合求出不一致集合有置換？有置換？求出新置換；更新公式集合與舊置換，求出新置換；更新公式集合與舊置換，k+無解、結(jié)束無解、結(jié)束說明說明：1、合一算法是消解原理的基礎(chǔ)。、合一算法是消解原理的基礎(chǔ)。2、合一算法中的公式集就是從謂詞合適公式合一算法中的公式集就是從謂詞合適公式化成的子句集?；傻淖泳浼?。例例：求：求F= P(a , x , f(g(y), P(z , h(z , u) , f(u)的最一般

28、的合一者。的最一般的合一者。解解：我們根據(jù)合一算法一步一步地求出：我們根據(jù)合一算法一步一步地求出mgu。第一步第一步：k = 0, F0= F, 0= F0的分歧集合的分歧集合D0=a , z 置換置換：a/z 1 =0a/z = a/z F1 = F0 a/z = P(a , x , f(g(y), P(a , h(a , u) , f(u) k=1 F1 不是單一表達(dá)式不是單一表達(dá)式F=P(a,x,f(g(y)， P(z,h(z,u),f(u)第二步第二步：D1x , h(a,u) 置換置換：h(a , u)/x 21h(a , u)/x=a/z , h(a , u)/x F2=F1h(a

29、 , u)/x =P(a , h(a , u) , f(g(y), P(a , h(a , u) , f(u) k=2F=P(a,x,f(g(y)， P(a,h(a,u),f(u)第三步第三步：D2g(y) , u 置換置換：g(y)/u 32g(y)/u=a/z , h(a,g(y)/x , g(y)/u F3=F2g(y)/u=P(a , h(a , g(y) , f(g(y) k=3F=P(a, h(a,u), f(g(y)， P(a, h(a,u), f(u) F3是單一表達(dá)式，所以是單一表達(dá)式，所以 3a/z , h(a , g(y)/x , g(y)/u是是 F 的最一般合一者的最一般合一者 例：例：F=Q(f(a) , g(x) , Q(y , y)是否可合一？是否可合一？第一步第一步：k=0, F0=F, 0= F0的分歧集合的分歧