人工智能-2知識表示-謂詞邏輯產(chǎn)生式表示法

人工智能及其應(yīng)用知識表示之謂詞邏輯/產(chǎn)生式表示11/8/20231知識的表示方法狀態(tài)空間法問題歸約法謂詞邏輯法語義網(wǎng)絡(luò)法框架表示法面向?qū)ο蟊硎緞”?script)表示過程(procedure)表示11/8/202322.3謂詞邏輯（predicatelogic）法命題邏輯能夠把客觀世界的各種事實表示為邏輯命題，但是它不適合于表示比較復(fù)雜的問題。謂詞邏輯允許表達(dá)那些無法用命題邏輯表達(dá)的事情。一階謂詞演算是一種形式語言，其根本目的在于把數(shù)學(xué)中的邏輯論證符號化。11/8/202332.3.1謂詞演算1.語法和語義(Syntax&Semantics)11/8/20234謂詞邏輯的基本組成：謂詞符號、變量符號、函數(shù)符號和常量符號，并用圓括弧、方括弧、花括弧和逗號隔開，以表示論域內(nèi)的關(guān)系。謂詞符號：表示個體所具有的性質(zhì)，或者若干個體之間的關(guān)系的符號。習(xí)慣用大寫字母P，Q，R或GREATER，LOVE表示。常量符號：用來表示論域內(nèi)的物體或?qū)嶓w，它可以是實際的物體和人，也可以是概念或具有名字的任何事情。一般用英文字母表中前幾個帶下標(biāo)或不帶下標(biāo)的小寫字母表示。如a，b，...，a1，b2，c3，...。11/8/20235變量符號：不必明確涉及是哪一個實體。習(xí)慣上用帶下標(biāo)或不帶下標(biāo)的小寫字母表示。如x，y，...，x1，y2，。函數(shù)符號：表示論域內(nèi)的函數(shù)。習(xí)慣用小寫字母f，g，h表示。11/8/20236原子公式(atomicformulas)由若干謂詞符號和項組成的謂詞演算。原子公式是謂詞演算基本積木塊。11/8/20237例如，要表示＂機器人(ROBOT)在１號房間(r1)內(nèi)＂，如圖2.19所示，可以應(yīng)用原子公式:當(dāng)機器人ROBOT移到房間r2時，原子公式可以表示為：

INROOM(ROBOT,r2)

這兩個原子公式的通用形式就是

11/8/20238又如,“李的母親和他的父親結(jié)婚”這句話的原子公式表示如下：

11/8/202392.連詞和量詞(Connective&Quantifiers)(1)連詞與·合?。╟onjunction）

合取就是用連詞∧把幾個公式連接起來而構(gòu)成的公式。合取項是合取式的每個組成部分。

例：LIKE(I，MUSIC)∧LIKE(I，PAINTING)(我喜愛音樂和繪畫。)或·析?。╠isjunction）

析取就是用連詞∨把幾個公式連接起來而構(gòu)成的公式。析取項是析取式的每個組成部分。例：PLAYS(LILI，BASKETBALL)∨PLAYS(LILI，F(xiàn)OOTBALL)(李力打籃球或踢足球。)11/8/202310蘊涵（Implication）

蘊涵“=>”表示“如果-那么”的語句。用連詞=>連接兩個公式所構(gòu)成的公式叫做蘊涵。

IF

=>

THEN

前項后項

(左式)

(右式)例：如果劉華跑得最快，那么他取得冠軍RUNS(LIUHUA，F(xiàn)ASTEST)TWINS(LIUHUA，CHAMPION)11/8/202311非（NOT）表示否定，～、┑均可表示。例：機器人不在2號房間內(nèi)。～I(xiàn)NROOM(ROBOT，r2)11/8/202312量詞全稱量詞(UniversalQuantifier)若一個原子公式P(x)，對于所有可能變量x都具有T值，則用(x)P(x)表示。例１：所有的機器人都是灰色的(

x)[ROBOT(x)=>COLOR(x,GRAY)]例２：所有學(xué)生都穿彩色制服(

x)[Student(x)=>Uniform(x,Color)]11/8/202313存在量詞(ExistentialQuantifier)

若一個原子公式P(x)，至少有一個變元X，可使P(X)為T值，則用(

x)P(x)表示。

例：1號房間內(nèi)有個物體

(

x)INROOM(x,r1)量化變元(QuantifiedVariables)被量化了的變元x-約束變量11/8/2023142.3.2謂詞公式（PredicateFormulas）1.謂詞公式的定義原子謂詞公式：用P(x1,x2,…,xn)表示一個n元謂詞公式其中P為n元謂詞，x1,x2,…xn為客體變量或變元。通常把P(x1,x2,…,xn)叫做謂詞演算的原子公式，或原子謂詞公式。分子謂詞公式：可以用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它叫做分子謂詞公式。

11/8/202315合式公式(WFF,well-formedformulas)的遞歸定義：

(1)原子謂詞公式是合式公式。

(2)若A為合式公式，則～A也是一個合式公式。

(3)若A和B都是合式公式，則(A∧B),(A∨B),(A=>B),(A←→B)也都是合式公式。

(4)若A是合式公式，x為A中的自由變元，則(“

x)A,(

x)A都是合式公式。

(5)只有按上述規(guī)則(1)至(4)求得的那些公式，才是合式公式。11/8/202316例題："對于所有的x，如果x是整數(shù)，則x或為正的或者為負(fù)的?！?

x)(I(x)=>(P(x)∨N(x)))I(x)表示"x是整數(shù)"，P(x)表示"x是正數(shù)"，N(x)表示"x是負(fù)數(shù)"。11/8/202317

2.合式公式的性質(zhì)真值表11/8/202318等價(Equivalence)如果兩個合式公式，無論如何解釋，其真值表都是相同的,那么我們就稱此兩合式公式是等價的。(1)否定之否定～～Ｐ等價于Ｐ(2)P∨Q等價于～P=>Q(3)狄·摩根定律～(P∨Q)等價于～P∧～Q～(P∧Q)等價于～P∨～Q11/8/202319(4)分配律

P∧(Q∨R)等價于(P∧Q)∨(P∧R)

P∨(Q∧R)等價于(P∨Q)∧(P∨R)(5)交換律

P∧Q等價于Q∧P

P∨Q等價于Q∨P(6)結(jié)合律

(P∧Q)∧R等價于P∧(Q∧R)

(P∨Q)∨R等價于P∨(Q∨R)(7)逆否律

P=>Q等價于～Q=>～P11/8/202320此外，還可建立下列等價關(guān)系：(8)～(x)P(x)等價于(x)［～P(x)］～(x)P(x)等價于(x)［～P(x)］(9)(x)［P(x)∧Q(x)］等價于(x)P(x)∧(

x)Q(x)(x)［P(x)∨Q(x)］等價于(x)P(x)∨(

x)Q(x)(10)(x)P(x)等價于(y)P(y)

(x)P(x)等價于(y)P(y)11/8/2023212.3.3置換與合一（Substitution&Unification）1.置換

置換是形如{t1/v1，...，tn/vn}的一個有限集。其中vi是變量，而ti是不同于vi的項（常量、變量、函數(shù)），且vi≠vj（i≠j），i，j=1，2，...，n。11/8/202322推理規(guī)則假元推理：全稱化推理：

11/8/202323綜合推理(同時應(yīng)用假元推理和全稱化推理)：

11/8/202324一個表達(dá)式的置換就是在該表達(dá)式中用置換項置換變量。一般說來，置換是可結(jié)合的，但置換是不可交換的。11/8/202325例1:表達(dá)式P[x,f(y),B]的置換為

s1={z/x,w/y}我們用Es來表示一個表達(dá)式E用置換s所得到的表達(dá)式的置換。置換的例為：P[x,f(y),B]s1=P[z,f(w),B]

11/8/202326例1:表達(dá)式P[x,f(y),B]的置換為

s2={A/y}置換的例為：P[x,f(y),B]s2=P[x,f(A),B]11/8/202327例1:表達(dá)式P[x,f(y),B]的置換為

s3={q(z)/x,A/y}置換的例為：P[x,f(y),B]s3=P[q(z),f(A),B]11/8/202328例1:表達(dá)式P[x,f(y),B]的置換為

s4={c/x,A/y}置換的例為：

P[x,f(y),B]s4=P[c,f(A),B])11/8/2023292.置換性質(zhì)

可結(jié)合律(LS1)S2=L(S1S2)(S1S2)S3=S1(S2S3)

置換是可結(jié)合的。用s1s2表示兩個置換s1和s2的合成。L表示一表達(dá)式，則有

(Ls1)s2=L(s1s2)

以及(s1s2)s3=s1(s2s3)即用s1和s2相繼作用于表達(dá)式L是同用s1s2作用于L一樣的。一般說來，置換是不可交換的，即

s1s2≠s2s111/8/202330合一(unification)合一：尋找項對變量的置換，以使兩表達(dá)式一致。

可合一：如果一個置換s作用于表達(dá)式集{Ei}的每個元素，則我們用{Ei}s來表示置換例的集。我們稱表達(dá)式集{Ei}是可合一的。11/8/202331合一例2：表達(dá)式集{P[x,f（y），B]，P[x，f（B），B]}的合一者為

s={A/x，B/y}

因為

P[x，f（y），B]s=P[x，f（B），B]s

=P[A，f（B），B]11/8/202332如果s是的任一合一者，有存在某個s'，使得

{Ei}s={Ei}σs'

成立,則稱σ為的最通用(最一般)的合一者,記為mgu.

如上例s是的一個合一者，但不是最簡單的合一者，其最簡單的合一者為

σ={B/y}11/8/202333

例1有下列知識： 劉歡比他父親出名。 高揚是計算機系的一名學(xué)生，但他不喜歡編程序。 人人愛勞動。 為了用謂詞公式表示上述知識，首先需要定義謂詞：

Bigger(x,y):x比y出名。

Computer(x):x是計算機系的學(xué)生。

Like(x,y):x喜歡y。

Love(x,y):x熱愛y。

Man(x):x是人。 然后用謂詞公式把上述知識表示為：

Bigger（Liuhong,father(Liuhong))

Computer(Gaoyang)∧

Like(Gaoyang,programing) (

x)(Man(x)=>Love(x,labour)11/8/202334例2設(shè)有下列知識自然數(shù)都是大于零的整數(shù)所有整數(shù)不是偶數(shù)就是奇數(shù)偶數(shù)除以2是整數(shù)首先定義謂詞如下：n(x):x是自然數(shù)I(x):x是整數(shù)E(x):x是偶數(shù)O(x):x是奇數(shù)GZ(x):x大于零另外用函數(shù)S(x)表示x除以2.此時，上述知識可用謂詞公式分別表示為：(

x)（n(x)=>GZ(x)∧I(x)）(

x)(I(x)=>E(x)∨O(x))(

x)(E(x)=>I(s(x))11/8/202335練習(xí)：試用謂詞邏輯表達(dá)方法描述下述推理。如果張三比李四大，那么李四比張三小。11/8/202336解:(1)定義本問題涉及的個體為張三：Zhang,李四：Li(2)定義謂詞

OLDER(x,y):x比y大

YOUNGER(x,y):x比y小(3)將個體代入謂詞中并用連接詞將其連接起來得

OLDER(Zhang,Li)=>YO