人工智能-知识表示方法-谓词逻辑法

人工智能及其应用第四讲知识表示法----谓词逻辑法一.谓词演算1.语法与语义谓词符号变量符号谓词逻辑组成:函数符号常量符号分隔符号例如:机器人在1号房间.Inroom(Robot,Room1)

李明的父亲和母亲结婚.

Married(father(li),mother(li))第四讲知识表示法----谓词逻辑法2.连接词合取Λ:只有当每项均为真时,其合取值才为真,否则为假.例如:我喜欢音乐和绘画

Like(I,music)∧like(I,painting)

李明住在一幢黄色的房子里

Lives(li,house1)∧Color(house,yellow)析取∨:至少有一项为真时,析取值才为真,否则为假.例如:李明打篮球或踢足球

Plays(li,Basketball)∨plays(li,foolball)第四讲知识表示法----谓词逻辑法蕴涵=>:如果----那么如果后项取值为T或者前项取值为F(不管其它项如何),则蕴涵值取值为T,否则为F.例如:如果这本书是小李的,那么它是蓝色的.Owns(li,book1)=>color(book1,blue)否定~:例如:机器人不在2号房间内.

~Inroom(robot1,room2)第四讲知识表示法----谓词逻辑法全称量词∀:一个原子公式,对所有可能的变量x都具有T.例如:所有的机器人都是灰色的.(∀x){robot(x)→color(x,gray)存在量词∃:至少有一个x值可使原子公式具有T.例如:1号房间有一个物体.(∃X)Inroom(x,room1)第四讲知识表示法----谓词逻辑法二.谓词公式1.谓词公式定义:用P(x1,x2,…,xn)表示一个n元谓词公式,其中P为n元谓词,x1,x2,…,xn为客体变量,称P(x1,x2,…xn)为谓词演算的原子谓词公式.

用连接词把原子谓词公式组成复合谓词公式,称分子谓词公式.2.合适公式定义:

原子谓词公式是合适公式;

任何复合谓词公式都是合适公式.第四讲知识表示法----谓词逻辑法3.合适公式的性质(1)否定之否定

~(~P)⇔P(2)P∨Q⇔~P→Q(3)摩根定律

~(P∨Q)⇔~P∧~Q~(P∧Q)⇔~P∨~Q第四讲知识表示法----谓词逻辑法(4)分配律

P∧(Q∨R)⇔(P∧Q)∨(P∧R)P∨(Q∧R)⇔(P∨Q)∧(P∨R)(5)交换律

P∧Q⇔Q∧PP∨Q⇔Q∨P(6)结合律

(P∧Q)∧R⇔P∧(Q∧R)(P∨Q)∨R⇔P∨(Q∨R)第四讲知识表示法----谓词逻辑法(7)逆否律

P→Q⇔

~Q→~P(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)第四讲知识表示法----谓词逻辑法三.置换与合一1.置换

是形如{t1/x1,t2/x2,…,tn/xn}的有限集合,其中,t1,…,tn是项;x1,…,xn是互不相同的变元;ti/xi表示用ti代换xi,不允许ti与xi相同,也不允许变元xi循环地出现在另一个tj中。例如：有四个置换s1={z/x,w/y}s2={A/y}s3={q(z)/x,A/y}s4={C/x,A/y}作用于合适表达式P[x,f(y),B]第四讲知识表示法----谓词逻辑法三.置换与合一

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]

置换可结合，但不可交换。2.合一

设有公式集E={E1，E2，…，En}，若存在一个置换λ使得：

E1λ=E2λ=…=Enλ则称λ为公式集的一个合一,且称Ei是可合一的。第四讲知识表示法----谓词逻辑法设σ是公式集E的一个合一，如果对任一合一θ都存在一个置换，使得θ

=σ•λ则称σ是一个最一般合一者。例如：表达式集{P[x,f(y),B],P[x,f(B),B]}的一个合一者为:

θ={A/x,B/y}P[x,f(y),B]θ=P[x,f(B),B]θ=P[A,f(B),B]

其中：σ={B/y}为最一般合一者。第四讲知识表示法----谓词逻辑法三.置换与合一3.求取最一般合一者的算法

(1)令k=0,Ek=E,σk={}(2)若Ek只含一个表达式，则算法停止，σk就是最一般合一者。

(3)找出Ek

的歧义集Dk。

(4)若Dk中存在元素xk和tk，其中xk是变元，tk是项，则置：

σ

k+1=σk。{tk/xk}Ek+1=Ek{tk/xk}K=k+1,goto(2)(5)算法终止，E不存在最一般合一者。第四讲知识表示法----谓词逻辑法例如:求公式集E={P[a,x,f(g(y))],P[z,h(z,u),f(u)]}的最一般合一者。解：k=0,E0=E,σ0={},D0={a/z}σ1=σ0。{a/z}={a/z}E1=E0{a/z}={P[a,x,f(g(y))],P[a,h(a,u),f(u)]}k=1,D1={x,h(a,u)},σ2=σ1。{h(a,u)/x}={a/z}。{h(a,u)/x}={a/z，h(a,u)/x}E2=E1

{h(a,u)/x}={P[a,h(a,u),f(g(y))],[a,h(a,u),f(u)]}k=2,D2={g(y),u)}σ3=σ2。{g(y)/u)}={a/z，h(a,u)/x}。{g(y)/u)}={a/z，h(a,