人工智能知識表示方法謂詞邏輯

人工智能ArtificialIntelligence(AI)曲維光wgqu@南京師范大學計算機學院第2章知識表示方法2.1謂詞邏輯法2.2形狀空間法2.3問題歸約法2.1謂詞邏輯法數(shù)理邏輯〔符號邏輯〕是用數(shù)學方法研討方式邏輯的一個分支。它經(jīng)過符號系統(tǒng)來表達客觀對象以及相關的邏輯推理。常用的是命題邏輯和謂詞邏輯謂詞邏輯是數(shù)理邏輯的根本方式，是基于謂詞分析的一種方式化〔數(shù)學〕言語人工智能中的謂詞邏輯法是指用一階謂詞來描畫問題求解和定理證明〔限于本課程〕2.1.0命題邏輯的復習1、命題邏輯的根本概念命題是可以判別真或假的陳說句通常用大寫字母來表示，如A,B,P,Q等命題的真假值普通用T或F來表示例：雪是白的。〔陳說句，T〕雪是可藍的?！碴愓f句，F(xiàn)〕雪是黑的。〔陳說句，F(xiàn)〕他是學生?！碴愓f句，他泛指，無法判別真假〕他今天上課沒有？〔疑問句〕請坐校車！〔祈使句〕命題邏輯是研討命題及命題之間關系的符號邏輯系統(tǒng)。在命題邏輯中，表示單一意義的命題，稱之為原子命題。原子命題經(jīng)過“結合詞〞構成復合命題。五個結合詞：①“～〞表示“非〞復合命題～P為真，當且僅當P為假。②“∧〞表示“合取〞復合命題“P∧Q〞為真，當且僅當P和Q都為真。④“〞表示“蘊含〞復合命題“PQ〞為假，當且僅當P為真且Q為假。③“∨〞表示“析取〞復合命題“P∨Q〞為真，當且僅當P、Q兩者之一為真。⑤“〞表示“等價〞復合命題“PQ〞為真，當且僅當P、Q同時為真、或者同時為假。聯(lián)接詞的優(yōu)先順序：非～、合取∧、析取∨、蘊含、等價注：可以用括號表示優(yōu)先級真值表PQ～PP∧QP∨QPQPQFFTFFTTFTTFTTFTFFFTFFTTFTTTT命題變元：用符號P、Q等表示的不具有固定、詳細含義的命題。它可以表示具有“真〞、“假〞含義的各種命題。命題變元可以利用結合詞構成所謂的適宜公式。適宜公式的定義①假設P為原子命題，那么P為適宜公式，稱為原子公式。②假設P是適宜公式，那么～P也是一個適宜公式。③假設P和Q是適宜公式，那么P∧Q、P∨Q、PQ、PQ都是適宜公式。④經(jīng)過有限次運用規(guī)那么1、2、3，得到的由原子公式、結合詞和園括號所組成的符號串，也是適宜公式。對于適宜公式，規(guī)定以下運算優(yōu)先級：①邏輯結合詞的運算優(yōu)先次序為：～、∧、∨、、②同級結合詞按出現(xiàn)順序優(yōu)先運算在命題邏輯中，主要研討推理的有效性。即：能否根據(jù)一些適宜公式〔前提〕推導出新的適宜公式〔結論〕。一些適宜公式〔前提條件〕適宜公式〔結論〕？在命題邏輯中，最根本的單元是命題，它是作為一個不可分割的整體。例如：雪是黑的命題邏輯具有較大的局限性，不適宜于表達比較復雜的問題。例：一切科學都是有用的〔假設1〕。數(shù)理邏輯是科學〔假設2〕。所以，數(shù)理邏輯是有用的〔結論〕。很明顯，我們無法用兩個假設推斷出結論。謂詞邏輯是命題邏輯的擴展和開展。它將一個原子命題分解成客體和謂詞兩個組成部分。例如：雪是黑的客體謂詞本課程主要引見一階謂詞邏輯。2.1.1謂詞演算1、語法與語義謂詞邏輯的根本組成部分謂詞變量函數(shù)常量圓括號、方括號、花括號和逗號例“機器人〔Robot〕在第一個房間〔r1〕內〞，可以表示為：INROOM〔ROBOT，r1〕其中INROOM是謂詞ROBOT和r1是常量謂詞是指個體〔客體〕所具有的性質或者假設干個體之間的關系。用大寫字母來表示。個體是可以詳細的〔如，小張、3、5〕也可以是籠統(tǒng)的〔如，x,y〕。例：小明是學生，A表示是“是學生〞，x表示“小明〞，記作A(x)。x大于y，G表示“大于〞，記作G〔x,y〕。論域：由個體組成的集合。〔個體〕變量：定義在某一個論域上的變量。用x,y,z來表示。函數(shù)〔或函詞〕：以個體為變量，以個體為值的函數(shù)。普通用小寫字母來表示，例如f(x),f(x,a)。

假設謂詞有n個變量，稱之為n元謂詞，并商定0元謂詞就是命題〔謂詞的特例〕。假設函數(shù)有n個個體，稱之為n元函數(shù)，并商定0元函數(shù)就是常量。常量習慣上用小寫字母來表示，如a,b,c。項的定義：①常量是項②變量是項③假設f是n元函數(shù)，且t1,…,tn(n≥1)是項，那么f(t1,…,tn)也是項④一切的項都必需是有限次運用上述規(guī)那么產生的項的例子：常量：a變量：x函數(shù)：f(x,a)g(f(x,a))原子〔謂詞〕公式的〔遞歸〕定義：①原子命題是原子公式②假設t1,…,tn(n≥1)是項，P是謂詞，那么P(t1,…,tn)是原子公式③其它表達式都不是原子公式原子公式的例子1、原子公式：P〔原子命題〕2、項：x,a,f(x,a)，謂詞：P原子公式：P(x,a,f(x,a))2、連詞和量詞結合詞〔連詞〕就是命題邏輯中的五個，它們的含義也是一樣的。兩個量詞：①全稱量詞，記作“x〞,含義是“對每一個x〞或“對一切x〞。②存在量詞，記作“x〞，含義是“存在某個x〞、“有一個x〞或者“某些x〞。例1：“一切的機器人都是灰色的〞，用謂詞邏輯可以表示成：〔x〕[ROBOT(x)COLOR(x，gray)]例2：“一號房間里有一個物體〞，可以表示成〔x〕INROOM〔x,r1〕我們稱x是被量化了的變量，稱為約束變量。否那么稱之為自在變量。一階謂詞：只允許對變量施加量詞，不允許對謂詞和函數(shù)施加量詞。2.1.2謂詞公式1、謂詞公式的定義利用連詞和量詞可以將原子〔謂詞〕公式組成復合謂詞公式，稱之為分子謂詞公式、謂詞適宜公式、謂詞公式、適宜公式?！仓^詞〕適宜公式的〔遞歸〕定義：①原子〔謂詞〕公式是適宜公式。②假設A是適宜公式，那么～A也是適宜公式。③假設A和B是適宜公式，那么A∧B、A∨B、AB、AB也是適宜公式。④假設A是適宜公式，x為A的自在變元〔變量〕，那么〔x〕A和〔x〕A都是適宜公式。⑤只需按上述規(guī)那么求得的公式才是適宜公式。例：任何整數(shù)或者為正或者為負。數(shù)學表達：對于一切的x，假設x是整數(shù)，那么x或者為正、或者為負。記作：I(x)：“x是整數(shù)〞。P(x)：“x是正數(shù)〞。N(x)：“x是負數(shù)〞。謂詞公式：〔x〕〔I(x)(P(x)∨N(x))〕2、適宜公式的性質假設P和Q是適宜公式，那么由這兩個適宜公式構成的適宜公式的真值表與前面引見的真值表一樣。假設兩個適宜公式的真值表一樣，那么我們稱這兩個適宜公式是等價的，可以用“〞來表示。對于命題適宜公式和謂詞適宜公式有以下等價關系：①否認之否認：～〔～P〕等價于P②P∨Q等價于～PQ③狄.摩根定律～〔P∨Q〕等價于～P∧～Q～〔P∧Q〕等價于～P∨～Q④分配律P∧(Q∨R)等價于(P∧Q)∨(P∧R)P∨(Q∧R)等價于(P∨Q)∧(P∨R)⑤交換律P∧Q等價于Q∧PP∨Q等價于Q∨P⑥結合律(P∧Q)∧R等價于P∧(Q∧R)(P∨Q)∨R等價于P∨(Q∨R)⑦逆否律PQ等價于～Q～P闡明：上述等價關系對命題適宜公式、謂詞適宜公式都成立。對于謂詞適宜公式有以下等價關系：⑧～(x)P(x)等價于(x)[～P(x)]～(x)P(x)等價于(x)[～P(x)]⑨(x)[P(x)∧Q(x)]等價于(x)P(x)∧(x)Q(x)(x)[P(x)∨Q(x)]等價于(x)P(x)∨(x)Q(x)⑩(x)P(x)等價于(y)P(y)(x)P(x)等價于(y)P(y)注釋：這兩個關系闡明，在一個量化的表達式中的約束變量是一類虛元，它們可以用任何不在表達式中出現(xiàn)的其它變量來替代。2.1.3置換與合一1、置換置換的定義：形如{t1/v1,…,tn/vn}的集合，稱為一個置換，其中vi是不同的變量，ti是與vi不同的項。例或例子的定義：設θ＝{t1/v1,…,tn/vn}為一個置換，E是一個原子謂詞公式。那么Eθ表示將E中的vi同時用ti〔i=1,…,n〕代入后所得到的結果，Eθ稱為E的一個例子。例：表達式〔原子謂詞公式〕P[x,f(y),B]的四個置換及其對應的四個例子〔B是常量〕s1={z/x,w/y}s2={A/y}s3={q(z)/x,A/y}s4={c/x,A/y}P[x,f(y),B]s1=P[z,f(w),B]P[x,f(y),B]s2=P[x,f(A),B]P[x,f(y),B]s3=P[q(z),f(A),B]P[x,f(y),B]s4=P[c,f(A),B]P[x,f(y),B]置換的合成：設θ＝{t1/x1,…,tn/xn}和λ＝{s1/y1,…,sm/ym}是兩個置換，那么θ和λ的合成是如下置換：{t1λ/x1,…,tiλ/xi,…,tnλ/xn,s1/y1,…,sn/ym}其中，yj是{x1,…,xn}之一者消去，對于任何tjλ=xj者消去，并記成θλ。如何求tiλ:λ＝{s1/y1,…,sm/ym}假設ti出現(xiàn){y1,….,ym}中的變量yi，那么用其對應的項si來替代。例：θ={t1/x1,t2/x2}＝{f(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,y/y,a/x,b/y,y/z}={f(b)/x,y/z}留意：置換的合成滿足結合律，不滿足交換律。(s1s2)s3=s1(s2s3)(滿足結合律〕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/x}2、合一當某一個置換s作用于表達式集合{Ei}的每一個元素，此時我們用{Ei}s來表示置換例子的集合。假設存在一個置換s，使得E1s=E2s=…=Eis=…那么我們稱表達式集合{Ei}是可合一的，并稱s為{Ei}的合一者。緣由是它的作用是使集合{Ei}成為單一方式。其中，Ei是原子謂詞公式。例：表達式集合{P[x,f(y),B],P[x,f(B),B]}的合一者為是s={A/x,B/y}P[x,f(y),B]s=P[A,f(B),B]P[x,f(B),B]s=P[A,f(B),B]假設s是{Ei}的恣意一個合一者，又存在某一個s’，使得s=gs’或者{Ei}s={Ei}gs’那么稱g是{Ei}的最通用〔最普通〕的合一者，記作mgu。例：s={A/x,B/y}是表達式集合{P[x,f(y),B],P[x,f(B),B]}的一個合一者，該集合的最普通的合一者是：g={B/y}3、合一算法分歧集〔或不一致集合〕的定義。設有一非空有限公式集合F={F1,…,Fn}，從F中各個公式的第一個符號同時向右比較，直到發(fā)現(xiàn)第一個彼此不盡一樣的符號為止，從F中的各個公式中取出那些以第一個不一致符號開場的最大的子表達式為元素，組成一個集合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)}有的可以合一，有的那么不能。設F為非空有限表達式集合，那么可以按以下步驟求出mgu：①置k=0，F(xiàn)k=F,σk=ε(空置換，即不含元素的置換)。②假設Fk只需一個表達式，那么算法終止，其中σk就是要求的mgu。③找出Fk的分歧集Dk。合一算法：④假設Dk中存在元素ak和tk，其中ak是變元，tk是項，且ak不在tk中出現(xiàn)，那么置：σk+1=σk{tk/ak}Fk+1=Fk{tk/ak}k=k+1然后轉向②。否那么，繼續(xù)。⑤算法終止，F(xiàn)的mgu不存在。合一算法的流程圖k=0,Fk=F,σk=ε|Fk|＝1？求得mgu、終了求出不一致集合有置換？求出新置換；更新公式集合與舊置換，k++無解、終了闡明：1、合一算法是消解原理的根底。2、合一算法中的公式集就是從謂詞適宜公式化成的子句集。例：求F={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的最普通的合一者。解：我們根據(jù)合一算法一步一步地求出mgu。第一步：k=0,F0=F,σ0=εF0的分歧集合D0={a,z}置換：{a/z}σ1=σ0{a/z}={a/z}F1=F0{a/z}={P(a,x,f(g(y))),P(a,h(a,u),f(u))}k=1F1不是單一表達式F={P(a,x,f(g(y)))，P(z,h(z,u),f(u))}}第二步：D1＝{x,h(a,u)}置換：{h(a,u)/x}σ2＝σ1{h(a,u)/x}={a/z,h(a,u)/x}F2=F1{h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}