人工智能謂詞邏輯

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

小王是個(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ǔ)謂詞邏輯基礎(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活到一百歲以上。

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

,謂詞邏輯基礎(chǔ)量詞否定等值式：～(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ǔ)量詞轄域收縮與擴(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ǔ)謂詞邏輯基礎(chǔ)SKOLEM標(biāo)準(zhǔn)形前束范式

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

(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é)原理

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

謂詞邏輯歸結(jié)原理Skolem定理：謂詞邏輯的的任意公式式都可以化化為與之等等價(jià)的前束束范式，但但其前束范范式不唯一一。SKOLEM標(biāo)準(zhǔn)形定義義：消去量詞后后的謂詞公公式。注意：謂詞公式式G的SKOLEM標(biāo)準(zhǔn)形同G并不等值。謂詞邏輯歸歸結(jié)原理例：將下式化為為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))第三步，變變元易名，，得(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))由此得到前前述范式第五步，消消去“”（存在量量詞），略略去“”全稱量詞詞消去(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))子句與子句句集文字：不含含任何連接接詞的謂詞詞公式。子句：一些些文字的析析?。ㄖ^詞詞的和）。。子句集S的求?。篏→SKOLEM標(biāo)準(zhǔn)形→消去存存在變量→以“，”取代“∧”，并表示為為集合形式式。謂詞邏輯歸歸結(jié)原理G是不可滿足足的<=>S是不可滿足足的G與S不等價(jià)，但但在不可滿滿足得意義義下是一致致的。定理：若G是給定的公公式，而S是相應(yīng)的子子句集，則則G是不可滿足足的<=>S是不可滿足足的。注意：G真不一定S真，而S真必有G真。即：S=>G謂詞邏輯歸歸結(jié)原理G=G1ΛG2ΛG3Λ…ΛGn的子句形G的字句集可可以分解成成幾個(gè)單獨(dú)獨(dú)處理。有SG=S1US2US3U…USn則SG與S1US2US3U…USn在不可滿足足得意義上上是一致的的。即SG不可滿足<=>S1US2US3U…USn不可滿足3.3謂詞邏輯歸歸結(jié)原理例：對所有有的x,y,z來說，如果果y是x的父親，z又是y的父親，則則z是x的祖父。又又知每個(gè)人人都有父親親，試問對對某個(gè)人來來說誰是它它的祖父？？求：用一階階邏輯表示示這個(gè)問題題，并建立立子句集。。解：這里我我們首先引引入謂詞：：P(x,y)表示x是y的父親Q(x,y)表示x是y的祖父ANS(x)表示問題的的解答謂詞邏輯歸歸結(jié)原理對于第一個(gè)個(gè)條件，““如果x是y的父親，y又是z的父親，則則x是z的祖父”，，一階邏輯輯表達(dá)式如如下：A1：(x)(y)(z)(P(x,y)∧P(y,z)→Q(x,z))SA1：～P(x,y)∨～P(y,z)∨Q(x,z)對于第二個(gè)個(gè)條件：““每個(gè)人都都有父親””，一階邏邏輯表達(dá)式式：A2：(y)(x)P(x,y)SA2：P(f(y),y)對于結(jié)論：：某個(gè)人是是它的祖父父B：(x)(y)Q(x,y)否定后得到到子句：～～（(x)(y)Q(x,y)）∨ANS(x)S～B：～Q(x,y)∨ANS(x)則得到的相相應(yīng)的子句句集為：{SA1，SA2，S～B}謂詞邏輯歸歸結(jié)原理歸結(jié)原理正正確性的根根本在于，，找到矛盾盾可以肯定定不真。方法：和命題邏輯輯一樣。但由于有函函數(shù)，所以以要考慮合一和置換。謂詞邏輯歸歸結(jié)原理置換：可以以簡單的理理解為是在在一個(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é)原理置換置換的合成成設(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)最后剩下的的元素所構(gòu)構(gòu)成的集合合。合成即是對對ti先做置換然后再再做置換，置換換xi謂詞邏輯歸歸結(jié)原理例：設(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é)結(jié)原原理理合一一合一一可可以以簡簡單單地地理理解解為為““尋尋找找相相對對變變量量的的置置換換，，使使兩兩個(gè)個(gè)謂謂詞詞公公式式一一致致””。。定義義：：設(shè)設(shè)有有公公式式集集F＝{F1，F(xiàn)2，…，F(xiàn)n}，若若存存在在一一個(gè)個(gè)置置換換，可可使使F1＝F2＝…=Fn，則則稱稱是F的一一個(gè)個(gè)合合一一。。同同時(shí)時(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è)合合一一。。注意意：：一一般般說說來來，，一一個(gè)個(gè)公公式式集集的的合合一一不不是是唯唯一一的的。。謂詞詞邏邏輯輯歸歸結(jié)結(jié)原原理理謂詞詞邏邏輯輯歸歸結(jié)結(jié)原原理理謂詞詞邏邏輯輯歸歸結(jié)結(jié)原原理理謂詞詞邏邏輯輯歸歸結(jié)結(jié)原原理理歸結(jié)結(jié)原原理理歸結(jié)結(jié)的的注注意意事事項(xiàng)項(xiàng)：：謂詞詞的的一一致致性性，P()與Q()，不不可可以以常量量的的一一致致性性，，P(a,…)與P(b,….)，不不可可以以變量量，，P(a,….)與P(x,…)，可可以以變量量與與函函數(shù)數(shù)，，P(a,x,….)與P(x,f(x),…)，不不可可以以；；是不不能能同同時(shí)時(shí)消消去去兩兩個(gè)個(gè)互互補(bǔ)補(bǔ)對對，，P∨∨Q與～P∨∨～Q的空空，，不不可可以以先進(jìn)進(jìn)行行內(nèi)內(nèi)部部簡簡化化（（置置換換、、合合并并））謂詞詞邏邏輯輯歸歸結(jié)結(jié)原原理理歸結(jié)結(jié)的的過過程程寫出出謂謂詞詞關(guān)關(guān)系系公公式式→→用反反演演法法寫寫出出謂謂詞詞表表達(dá)達(dá)式式→→SKOLEM標(biāo)準(zhǔn)準(zhǔn)形形→→子句句集集S→對S中可可歸歸結(jié)結(jié)的的子子句句做做歸歸結(jié)結(jié)→→歸結(jié)結(jié)式式仍仍放放入入S中，，反反復(fù)復(fù)歸歸結(jié)結(jié)過過程程→→得到到空空子子句句?得證證謂詞詞邏邏輯輯歸歸結(jié)結(jié)原原理理例題題“快快樂樂學(xué)學(xué)生生””問問題題假設(shè)設(shè)任任何何通通過過計(jì)計(jì)算算機(jī)機(jī)考考試試并并獲獲獎(jiǎng)獎(jiǎng)的的人人都都是是快快樂樂的的，，任任何何肯肯學(xué)學(xué)習(xí)習(xí)或或幸幸運(yùn)運(yùn)的的人人都都可可以以通通過過所所有有的的考考試試，，張張不不肯肯學(xué)學(xué)習(xí)習(xí)但但他他是是幸幸運(yùn)運(yùn)的的，，任任何何幸幸運(yùn)運(yùn)的的人人都都能能獲獲獎(jiǎng)獎(jiǎng)。。求求證證：：張張是是快快樂樂的的。。解：：先先將將問問題題用用謂謂詞詞表表示示如如下下：：R1:““任何何通通過過計(jì)計(jì)算算機(jī)機(jī)考考試試并并獲獲獎(jiǎng)獎(jiǎng)的的人人都都是是快快樂樂的的””(x)((Pass(x,computer)∧∧Win(x,prize))→→Happy(x))R2:““任何何肯肯學(xué)學(xué)習(xí)習(xí)或或幸幸運(yùn)運(yùn)的的人人都都可可以以通通過過所所有有考考試試””(x)(y)(Study(x)∨∨Lucky(x)→→Pass(x,y))R3:““張不不肯肯學(xué)學(xué)習(xí)習(xí)但但他他是是幸幸運(yùn)運(yùn)的的””～Study(zhang)∧∧Lucky(zhang)R4:““任何何幸幸運(yùn)運(yùn)的的人人都都能能獲獲獎(jiǎng)獎(jiǎng)””(x)(Luck(x)→→Win(x,prize))結(jié)論論：：““張張是是快快樂樂的的””的的否否定定～Happy(zhang)例題題“快快樂樂學(xué)學(xué)生生””問問題題由R1及邏邏輯輯轉(zhuǎn)轉(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é)結(jié)論論：：(7)～Happy(zhang)（結(jié)結(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)歸結(jié)結(jié)法法的的實(shí)實(shí)質(zhì)質(zhì)：：歸結(jié)結(jié)法法是是僅僅有有一一條條推推理理規(guī)規(guī)則則的的推推理理方方法法。。歸結(jié)結(jié)的的過過程程是是一一個(gè)個(gè)語語義義樹樹倒倒塌塌的的過過程程。。歸結(jié)結(jié)法法的的問問題題子句句中中有有等等號(hào)號(hào)或或不不等等號(hào)號(hào)時(shí)時(shí)，，完完備備性性不不成成立立。?！鵋erbrand定理理的的不不實(shí)實(shí)用用性性引引出出了了可可實(shí)實(shí)用用的的歸歸結(jié)結(jié)法法。。謂詞詞邏邏輯輯歸歸結(jié)結(jié)原原理理歸結(jié)結(jié)過過程程的的控控制制策策略略要解解決決的的問問題題：：歸結(jié)結(jié)方方法法的的知知識(shí)識(shí)爆爆炸炸。?？刂浦撇卟呗月缘牡哪磕康牡臍w結(jié)結(jié)點(diǎn)點(diǎn)盡盡量量少少控制制策策略略的的原原則則給出出控控制制策策略略，，以以使使僅僅對對選選擇擇合合適適的的子子句句間間方方可可做做歸歸結(jié)結(jié)。。避避免免多多余余的的、、不不必必要要的的歸歸結(jié)結(jié)式式出出現(xiàn)現(xiàn)。?；蚧蛘哒哒f說，，少少做做些些歸歸結(jié)結(jié)仍仍能能導(dǎo)導(dǎo)出出空空子子句句。。謂詞詞邏邏輯輯歸歸結(jié)結(jié)原原理理刪除除策策略略=>完備備名詞詞解解釋釋：：歸歸類類：：設(shè)設(shè)有有兩兩個(gè)個(gè)子子句句C和D，若若有有置置換換使得得CD成立立，，則則稱稱子子句句C把子子句句D歸類類。。由于于小小的的可可以以代代表表大大的的，，所所以以小小的的吃吃掉掉大大的的了了。。若對對S使用用歸歸結(jié)結(jié)推推理理過過程程中中，，當(dāng)當(dāng)歸歸結(jié)結(jié)式式Cj是重重言言式式（（永永真真式式））和和Cj被S中子子句句和和子子句句集集的的歸歸結(jié)結(jié)式式Ci(i<j)所歸類類時(shí)，，便將將Cj刪除。。這樣樣的推推理過過程便便稱做做使用用了刪刪除策策略的的歸結(jié)結(jié)過程程。謂詞邏邏輯歸歸結(jié)原原理主要思思想：：歸結(jié)結(jié)過程程在尋尋找可可歸結(jié)結(jié)子句句時(shí)，，子句句集中中的子子句越越多，，需要要付出出的代代價(jià)就就會(huì)越越大。。如果果在歸歸結(jié)時(shí)時(shí)能把把子句句集中中無用用的子子句刪刪除掉掉，就就會(huì)縮縮小搜搜索范范圍，，減少少比較較次數(shù)數(shù)，從從而提提高歸歸結(jié)效效率。。刪除除策略略對阻阻止不不必要要的歸歸結(jié)式式的產(chǎn)產(chǎn)生來來縮短短歸結(jié)結(jié)過程程是有有效的的。然然而要要在歸歸結(jié)式式Cj產(chǎn)生后后方能能判別別它是是否可可被刪刪除，，這部部分計(jì)計(jì)算量量是要要花費(fèi)費(fèi)的，，只是是節(jié)省省了被被刪除除的子子句又又生成成的歸歸結(jié)式式。盡盡管使使用刪刪除策策略的的歸結(jié)結(jié)，少少做了了歸結(jié)結(jié)但不不影響響產(chǎn)生生空子子句，，就是是說刪刪除策策略的的歸結(jié)結(jié)推理理是完完備的的。謂詞邏邏輯歸歸結(jié)原原理采用支支撐集集<=>完備支撐集集：設(shè)設(shè)有不不可滿滿足子子句集集S的子集集T，如果果S-T是可滿滿足的的，則則T是支持持集。。采用支支撐集集策略略時(shí)，，從開開始到到得到到的整個(gè)個(gè)歸結(jié)結(jié)過程程中，，只選選取不不同時(shí)時(shí)屬于于S-T的子句句，在在其間間進(jìn)行行歸結(jié)結(jié)。就就是說說，至至少有有一個(gè)個(gè)子句句來自自于支支撐集集T或由T導(dǎo)出的的歸結(jié)結(jié)式。。謂詞邏邏輯歸歸結(jié)原原理例如：：A1ΛA2ΛA3Λ～B中的～～B可以作作為支支撐集集使用用。要要求每每一次次參加加歸結(jié)結(jié)的親親本子子句中中，只只要應(yīng)應(yīng)該有有一個(gè)個(gè)是有有目標(biāo)標(biāo)公式式的否否定（（～B）所得得到的的子句句或者者它們們的后后裔。。支撐集集策略略的歸歸結(jié)是是完備備的，，同樣樣，所所有可可歸結(jié)結(jié)的謂謂詞公公式都都可以以用采采用支支撐集集策略略達(dá)到到加快快歸結(jié)結(jié)速度度的目目的。。問題題是如如何尋尋找合合適的的支撐撐集。。一個(gè)個(gè)最容容易找找到的的支撐撐集是是目標(biāo)標(biāo)子句句的非非，即即S～B。謂詞邏邏輯歸歸結(jié)原原理ST可滿足支撐集示意圖謂詞邏邏輯歸歸結(jié)原原理語義歸歸結(jié)<=>完備語義歸歸結(jié)策策略是是將子子句S按照一一定的的語義義分成成兩部部分，，約定定每部部分內(nèi)內(nèi)的子子句間間不允允許作作歸結(jié)結(jié)。同同時(shí)還還引入入了文文字次次序，，約定定歸結(jié)結(jié)時(shí)其其中的的一個(gè)個(gè)子句句的被被歸結(jié)結(jié)文字字只能能是該該子句句中“最大”的文字字。語義歸歸結(jié)策策略的的歸結(jié)結(jié)是完完備的的，同同樣，，所有有可歸歸結(jié)的的謂詞詞公式式都可可以用用采用用語義義歸結(jié)結(jié)策略略達(dá)到到加快快歸結(jié)結(jié)速度度的目目的。。問題題是如如何尋尋找合合適的的語義義分類類方法法，并并根據(jù)據(jù)其含含義將將子句句集兩兩個(gè)部部分中中的子子句進(jìn)進(jìn)行排排序。。謂詞邏邏輯歸歸結(jié)原原理線性歸歸結(jié)<=>完備線性歸歸結(jié)策策略首首先從從子句句集中中選取取一個(gè)個(gè)稱作作頂子子句的的子句句C0開始作作歸結(jié)結(jié)。歸歸結(jié)過過程中中所得得到的的歸結(jié)結(jié)式Ci立即