人工智能知識(shí)表示方法謂詞邏輯

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

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