人工智能-謂詞邏輯

謂詞邏輯基礎(chǔ)一階邏輯基本概念個(gè)體詞：表示主語詞謂詞：刻畫個(gè)體性質(zhì)或個(gè)體之間關(guān)系詞量詞：表示數(shù)量詞人工智能-謂詞邏輯第1頁

小王是個(gè)工程師。

8是個(gè)自然數(shù)。 我去買花。 小麗和小華是朋友。其中，“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”都是個(gè)體詞，而“是個(gè)工程師”、“是個(gè)自然數(shù)”、“去買”、“是朋友”都是謂詞。顯然前兩個(gè)謂詞表示是事物性質(zhì)，第三個(gè)謂詞“去買”表示一個(gè)動(dòng)作也表示了主、賓兩個(gè)個(gè)體詞關(guān)系，最終一個(gè)謂詞“是朋友”表示兩個(gè)個(gè)體詞之間關(guān)系。謂詞邏輯基礎(chǔ)人工智能-謂詞邏輯第2頁謂詞邏輯基礎(chǔ)比如：（1）全部人都是要死。（2）

有人活到一百歲以上。在個(gè)體域D為人類集合時(shí)，可符號(hào)化為：（1）

xP(x)，其中P(x)表示x是要死。（2）

xQ(x),其中Q(x)表示x活到一百歲以上。在個(gè)體域D是全總個(gè)體域時(shí)，引入特殊謂詞R(x)表示x是人，可符號(hào)化為：（1）

x（R(x)→P(x)）,

其中，R(x)表示x是人；P(x)表示x是要死。（2）

x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。

人工智能-謂詞邏輯第3頁一階邏輯公式及其解釋個(gè)體常量：a,b,c個(gè)體變量：x,y,z謂詞符號(hào)：P,Q,R量詞符號(hào)：

,

謂詞邏輯基礎(chǔ)人工智能-謂詞邏輯第4頁量詞否定等值式：～(

x

）

P（x）<=>（

y

）～

P（y）～(

x

）

P（x）<=>（

y

）～

P（y）量詞分配等值式：(

x

）(

P（x）∧

Q（x）)<=>(

x

）

P（x）∧

(

x

）

Q（x）(

x

）(

P（x）∨

Q（x）)<=>(

x

）

P（x）∨

(

x

）

Q（x）消去量詞等值式：設(shè)個(gè)體域?yàn)橛懈F集合（a1,a2,…an）(

x

）

P（x）<=>P（a1

）∧

P（a2

）∧

…

∧

P（an

）(

x

）P（x）<=>P（a1

）∨

P（a2

）∨

…

∨

P（an

）謂詞邏輯基礎(chǔ)人工智能-謂詞邏輯第5頁量詞轄域收縮與擴(kuò)張等值式：(

x

）(

P（x）∨Q)<=>(

x

）

P（x）∨Q(

x

）(

P（x）∧

Q)<=>(

x

）

P（x）∧

Q

(

x

）(

P（x）→Q)<=>(

x

）

P（x）→Q

(

x

）(Q

→P（x）)<=>Q

→(

x

）

P（x）(

x

）(

P（x）∨Q)<=>(

x

）

P（x）∨Q(

x

）(

P（x）∧

Q)<=>(

x

）

P（x）∧

Q

(

x

）(

P（x）→Q)<=>(

x

）

P（x）→Q

(

x

）(Q

→P（x）)<=>Q

→(

x

）

P（x）謂詞邏輯基礎(chǔ)人工智能-謂詞邏輯第6頁謂詞邏輯基礎(chǔ)人工智能-謂詞邏輯第7頁SKOLEM標(biāo)準(zhǔn)形前束范式

定義：說公式A是一個(gè)前束范式，假如A中一切量詞都位于該公式最左邊（不含否定詞），且這些量詞轄域都延伸到公式末端。謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第8頁即：把全部量詞都提到前面去，然后消掉全部量詞

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)約束變項(xiàng)換名規(guī)則：(Qx

）

M（x）<=>（Qy

）

M（y）(Qx

）

M（x,z）<=>（Qy

）

M（y,z）謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第9頁

量詞消去標(biāo)準(zhǔn)： 消去存在量詞“

”，略去全程量詞“

”。 注意：左邊有全程量詞存在量詞，消去時(shí)該變量改寫成為全程量詞函數(shù)；如沒有，改寫成為常量。

謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第10頁

Skolem定理： 謂詞邏輯任意公式都能夠化為與之等價(jià)前束范式，但其前束范式不唯一。SKOLEM標(biāo)準(zhǔn)形定義： 消去量詞后謂詞公式。注意：謂詞公式GSKOLEM標(biāo)準(zhǔn)形同G并不等值。謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第11頁例：將下式化為Skolem標(biāo)準(zhǔn)形：

～(

x)(

y)P(a,x,y)→(

x)(～(

y)Q(y,b)→R(x))解：第一步，消去→號(hào)，得：～(～(

x)(

y)P(a,x,y))∨(

x)(～～(

y)Q(y,b)∨R(x))第二步，～深入到量詞內(nèi)部，得：

(

x)(

y)P(a,x,y)∨(

x)((

y)Q(y,b)∨R(x))第三步，變?cè)酌?，?/p>

(

x)(

y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))第四步，存在量詞左移，直至全部量詞移到前面， (

x)(

y)(u)(v)(P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式人工智能-謂詞邏輯第12頁第五步，消去“

”（存在量詞），略去“

”全稱量詞 消去(

y)，因?yàn)樗筮呏挥?

x)，所以使用x函數(shù)f(x)代替之，這么得到：

(

x)(

u)(v)(P(a,x,f(x))∨Q(v,b)∨R(u))

消去(

u)，同理使用g(x)代替之，這么得到：

(

x)(v)(P(a,x,f(x))∨

Q(v,b)∨

R(g(x)))

則，略去全稱變量，原式Skolem標(biāo)準(zhǔn)形為：

P(a,x,f(x))∨

Q(v,b)∨

R(g(x))

人工智能-謂詞邏輯第13頁子句與子句集文字：不含任何連接詞謂詞公式。子句：一些文字析?。ㄖ^詞和）。子句集S求取：

G→SKOLEM標(biāo)準(zhǔn)形 →消去存在變量 →以“，”取代“∧”，并表示為集合形式。謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第14頁

G是不可滿足<=>S是不可滿足G與S不等價(jià)，但在不可滿足得意義下是一致。

定理： 若G是給定公式，而S是對(duì)應(yīng)子句集，則G是不可滿足<=>S是不可滿足。

注意：G真不一定S真，而S真必有G真。 即：S=>G謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第15頁G=G1ΛG2ΛG3Λ…ΛGn

子句形G字句集能夠分解成幾個(gè)單獨(dú)處理。

有SG=S1US2US3U…USn

則SG

與S1US2US3U…USn在不可滿足得意義上是一致。 即SG

不可滿足<=>S1US2US3U…USn不可滿足3.3謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第16頁例：對(duì)全部x,y,z來說，假如y是x父親，z又是y父親，則z是x祖父。又知每個(gè)人都有父親，試問對(duì)某個(gè)人來說誰是它祖父？求：用一階邏輯表示這個(gè)問題，并建立子句集。解：這里我們首先引入謂詞：

P(x,y)表示x是y父親

Q(x,y)表示x是y祖父

ANS(x)表示問題解答謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第17頁對(duì)于第一個(gè)條件，“假如x是y父親，y又是z父親，則x是z祖父”，一階邏輯表示式以下：

A1：(

x)(

y)(

z)(P(x,y)∧P(y,z)→Q(x,z)) SA1：～P(x,y)∨～P(y,z)∨Q(x,z)對(duì)于第二個(gè)條件：“每個(gè)人都有父親”，一階邏輯表示式：

A2：(

y)(

x)P(x,y) SA2：P(f(y),y)對(duì)于結(jié)論：某個(gè)人是它祖父

B：(

x)(

y)Q(x,y)

否定后得到子句：～（(

x)(

y)Q(x,y)）∨ANS(x) S～B：～Q(x,y)∨ANS(x)則得到對(duì)應(yīng)子句集為：{SA1，SA2，S～B}謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第18頁歸結(jié)原理正確性根本在于，找到矛盾能夠必定不真。方法：和命題邏輯一樣。但因?yàn)橛泻瘮?shù)，所以要考慮合一和置換。

謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第19頁置換：能夠簡(jiǎn)單了解為是在一個(gè)謂詞公式中用置換項(xiàng)去置換變量。定義： 置換是形如{t1/x1,t2/x2,…,tn/xn}有限集合。其中，x1,x2,…,xn是互不相同變量，t1,t2,…,tn是不一樣于xi項(xiàng)（常量、變量、函數(shù)）；ti/xi表示用ti置換xi，而且要求ti與xi不能相同，而且xi不能循環(huán)地出現(xiàn)在另一個(gè)ti中。比如

{a/x，c/y，f(b)/z}是一個(gè)置換。

{g(y)/x，f(x)/y}不是一個(gè)置換，

謂詞邏輯歸結(jié)原理置換人工智能-謂詞邏輯第20頁置換合成設(shè)

＝{t1/x1,t2/x2,…,tn/xn}，

＝{u1/y1,u2/y2,…,un/yn}，是兩個(gè)置換。 則

與

合成也是一個(gè)置換，記作

·

。它是從集合

{t1·

/x1,t2·

/x2,…,tn·

/xn,u1/y1,u2/y2,…,un/yn}

中刪去以下兩種元素：i.

當(dāng)ti

=xi時(shí)，刪去ti

/xi(i=1,2,…,n);Ii.

當(dāng)yi

{x1,x2,…,xn}時(shí)，刪去uj/yj(j=1,2,…,m)

最終剩下元素所組成集合。合成即是對(duì)ti先做

置換然后再做

置換，置換xi謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第21頁例：設(shè)：

＝{f(y)/x,z/y}，

＝{a/x,b/y,y/z}，求

與

合成。解：先求出集合

{f(b/y)/x,(y/z)/y,a/x,b/y,y/z}＝{f(b)/x,y/y,a/x,b/y,y/z}

其中，f(b)/x中f(b)是置換

作用于f(y)結(jié)果；y/y中y是置換

作用于z結(jié)果。在該集合中，y/y滿足定義中條件i，需要?jiǎng)h除；a/x，b/y滿足定義中條件ii，也需要?jiǎng)h除。最終得

·

＝{f(b)/x，y/z}謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第22頁合一合一能夠簡(jiǎn)單地了解為“尋找相對(duì)變量置換，使兩個(gè)謂詞公式一致”。定義：設(shè)有公式集F＝{F1，F(xiàn)2，…，F(xiàn)n}，若存在一個(gè)置換

，可使F1

＝F2

＝…=Fn

，則稱

是F一個(gè)合一。同時(shí)稱F1，F(xiàn)2，...，F(xiàn)n是可合一。

例： 設(shè)有公式集F＝{P(x,y,f(y)),P(a,g(x),z)}，則

＝{a/x,g(a)/y,f(g(a))/z}是它一個(gè)合一。注意：普通說來，一個(gè)公式集合一不是唯一。

謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第23頁謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第24頁謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第25頁謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第26頁歸結(jié)原理歸結(jié)注意事項(xiàng)：謂詞一致性，P()與Q()，不能夠常量一致性，P(a,…)與P(b,….)，不能夠 變量，P(a,….)與P(x,…)，能夠變量與函數(shù)，P(a,x,….)與P(x,f(x),…)，不能夠；是不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)，P∨Q與～P∨～Q空，不能夠先進(jìn)行內(nèi)部簡(jiǎn)化（置換、合并）

謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第27頁歸結(jié)過程寫出謂詞關(guān)系公式→用反演法寫出謂詞表示式→SKOLEM標(biāo)準(zhǔn)形→子句集S→對(duì)S中可歸結(jié)子句做歸結(jié)→歸結(jié)式仍放入S中，重復(fù)歸結(jié)過程→得到空子句

?得證謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第28頁例題“高興學(xué)生”問題假設(shè)任何經(jīng)過計(jì)算機(jī)考試并獲獎(jiǎng)人都是高興，任何肯學(xué)習(xí)或幸運(yùn)人都能夠經(jīng)過全部考試，張不愿學(xué)習(xí)但他是幸運(yùn)，任何幸運(yùn)人都能獲獎(jiǎng)。求證：張是高興。

解：先將問題用謂詞表示以下：R1:“任何經(jīng)過計(jì)算機(jī)考試并獲獎(jiǎng)人都是高興”

(

x)((Pass(x,computer)∧Win(x,prize))→Happy(x))R2:“任何肯學(xué)習(xí)或幸運(yùn)人都能夠經(jīng)過全部考試”

(

x)(

y)(Study(x)∨Lucky(x)→Pass(x,y))R3:“張不愿學(xué)習(xí)但他是幸運(yùn)” ～Study(zhang)∧Lucky(zhang)R4:“任何幸運(yùn)人都能獲獎(jiǎng)”

(

x)(Luck(x)→Win(x,prize))結(jié)論：“張是高興”否定～Happy(zhang)人工智能-謂詞邏輯第29頁例題“高興學(xué)生”問題由R1及邏輯轉(zhuǎn)換公式:P∧W→H=～（P∧W）∨H，可得

(1)～Pass(x,computer)∨～Win(x,prize)∨Happy(x)由R2：(2)～Study(y)∨Pass(y,z)(3)～Lucky(u)∨Pass(u,v)由R3：(4)～Study(zhang)(5)Lucky(zhang)由R4：(6)～Lucky(w)∨Win(w，prize)由結(jié)論：(7)～Happy(zhang) （結(jié)論否定）(8)～Pass(w,computer)∨Happy(w)∨～Luck(w)(1)(6)，{w/x}(9)～Pass(zhang,computer)∨～Lucky(zhang)(8)(7)，{zhang/w}(10)

～Pass(zhang,computer) (9)(5)(11)

～Lucky(zhang) (10)(3)，{zhang/u,computer/v}(12)

?

(11)(5)

人工智能-謂詞邏輯第30頁歸結(jié)法實(shí)質(zhì)：歸結(jié)法是僅有一條推理規(guī)則推理方法。歸結(jié)過程是一個(gè)語義樹坍毀過程。歸結(jié)法問題子句中有等號(hào)或不等號(hào)時(shí)，完備性不成立?！鵋erbrand定理不實(shí)用性引出了可實(shí)用歸結(jié)法。謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第31頁歸結(jié)過程控制策略要處理問題：歸結(jié)方法知識(shí)爆炸?？刂撇呗阅繕?biāo)歸結(jié)點(diǎn)盡可能少控制策略標(biāo)準(zhǔn)給出控制策略，以使僅對(duì)選擇適當(dāng)子句間方可做歸結(jié)。防止多出、無須要?dú)w結(jié)式出現(xiàn)。或者說，少做些歸結(jié)仍能導(dǎo)出空子句。謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第32頁

刪除策略 => 完備名詞解釋：歸類：設(shè)有兩個(gè)子句C和D，若有置換

使得C

D成立，則稱子句C把子句D歸類。 因?yàn)樾∧軌虼泶?，所以小吃掉大了。若?duì)S使用歸結(jié)推理過程中，當(dāng)歸結(jié)式Cj是重言式（永真式）和Cj被S中子句和子句集歸結(jié)式Ci(i<j)所歸類時(shí)，便將Cj刪除。這么推理過程便稱做使用了刪除策略歸結(jié)過程。謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第33頁主要思想：歸結(jié)過程在尋找可歸結(jié)子句時(shí)，子句集中子句越多，需要付出代價(jià)就會(huì)越大。假如在歸結(jié)時(shí)能把子句集中無用子句刪除掉，就會(huì)縮小搜索范圍，降低比較次數(shù)，從而提升歸結(jié)效率。刪除策略對(duì)阻止無須要?dú)w結(jié)式產(chǎn)生來縮短歸結(jié)過程是有效。然而要在歸結(jié)式Cj產(chǎn)生后方能判別它是否可被刪除，這部分計(jì)算量是要花費(fèi)，只是節(jié)約了被刪除子句又生成歸結(jié)式。盡管使用刪除策略歸結(jié)，少做了歸結(jié)但不影響產(chǎn)生空子句，就是說刪除策略歸結(jié)推理是完備。謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第34頁采取支撐集 <=>完備

支撐集：設(shè)有不可滿足子句集S子集T，假如S-T是可滿足，則T是支持集。

采取支撐集策略時(shí)，從開始到得到

整個(gè)歸結(jié)過程中，只選取不一樣時(shí)屬于S-T子句，在其間進(jìn)行歸結(jié)。就是說，最少有一個(gè)子句來自于支撐集T或由T導(dǎo)出歸結(jié)式。

謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第35頁比如：A1ΛA2ΛA3Λ～B中～B能夠作為支撐集使用。要求每一次參加歸結(jié)親本子句中，只要應(yīng)該有一個(gè)是有目標(biāo)公式否定（～B）所得到子句或者它們后代。支撐集策略歸結(jié)是完備，一樣，全部可歸結(jié)謂詞公式都能夠用采取支撐集策略到達(dá)加緊歸結(jié)速度目標(biāo)。問題是怎樣尋找適當(dāng)支撐集。一個(gè)最輕易找到支撐集是目標(biāo)子句非，即S～B。謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第36頁ST可滿足支撐集示意圖謂詞邏輯歸結(jié)原理人工智能-謂詞邏輯第37頁

語義歸結(jié) <=> 完備 語義歸結(jié)策略是將子句S按照一定語義分成兩部分，約定每部分內(nèi)子句間不允許作歸結(jié)。同時(shí)還引入了文字次序，約定歸結(jié)