第3章 基于谓词逻辑的机器.ppt

第3章基于谓词逻辑的机器推理
一阶谓词逻辑
归结演绎推理
应用归结原理求取问题答案
归结策略
归结反演程序举例
Horn子句归结与逻辑程序
一阶谓词逻辑
谓词、函数、量词
谓词 A(x1,x2,…,xn):
个体域 Di 个体变元xi 设i=1,2,…n
个体常元 ai ∈ Di 论述域D1,×D2 ×…×Dn
原子命题 A(a1,a2,…,an)
量词
命题常元(0元原子命题):表示基本事实
例如 A: AI是一门专业基础课程
1元谓词:表示特定对象是否具有某种属性
例如 P(x): x是素数 P(2)
n元谓词:表示n个对象之间是否具有某种关系
例如 F(x,y):x和y是朋友 F(张三,李四)
“凡是人都有名字”:
x (M(x)→N(x))
不存在最大的整数,我们可以把它翻译为
乛 x (G(x)∧ y(G(y)→D(x,y))
或 x (G(x)→ y(G(y)∧D(y,x))
对于所有的自然数,均有x+y>x
x y(N(x)∧N(y)→S(x+y,x))
某些人对某些食物过敏
x y(M(x)∧F(y)∧G(x,y))
谓词公式
定义1
(1)个体常元和个体变元都是项。
(2)设f是n元函数符号,若t1,t2,…,tn是项,则函词f(t1,t2,…,tn)是项。
(3)只有有限次使用(1),(2)得到的符号串才是项。
定义2 设P为n元谓词符号,t1,t2,…,tn为项,则P(t1,t2,…,tn)称为原子谓词公式,简称原子公式或者原子。
定义3
(1)原子公式是谓词公式。
(2)若A,B是谓词公式,则也是谓词公式。

则上式左端也是谓词公式。
(3)只有有限步应用(1),(2)生成的公式才是谓词公式。
谓词公式亦称为谓词逻辑中的合适(式)公式,记为Wff。
量词的辖域。
(1) xP(x)
(2) x(H(x)→G(x,y))
(3) x A(x)∧B(x)
其中(1)中的P(x)为 x的辖域,(2)中的H(x)→G(x,y)为 x的辖域,(3)中的A(x)为 x的辖域
指导变元(或作用变元)
约束变元
自由变元
变元公式中可约束出现,自由出现
改名规则
定义4 设A为如下形式的谓词公式:
B1∧B2∧…∧Bn
其中Bi(i=1,2,…,n)形如L1∨L2∨…∨Lm,Lj(j=1,2,…,m)为原子公式或其否定,则A称为合取范式。
例如:
(P(x)∨Q(y))∧(乛P(x)∨Q(y)∨R(x,y))
∧(乛Q(y)∨乛R(x,y))
是一个合取范式。
定义5 设A为如下形式的命题公式:
B1∨B2∨…∨Bn
其中Bi(i=1,2,…,n)形如L1∧L2∧…∧Lm,Lj(j=1,2,…,m)为原子公式或其否定,则A称为析取范式。
例如:
(P(x)∧乛Q(y)∧R(x,y))∨(乛P(x)∧
Q(y))∨(乛P(x)∧R(x,y))
  是一个析取范式。
定义6 设P为谓词公式,D为其个体域,对于D中的任一解释I:
(1)若P恒为真,则称P在D上永真(或有效)或是D上的永真式。
(2)若P恒为假,则称P在D上永假(或不可满足)或是D上的永假式。
(3)若至少有一个解释,可使P为真,则称P在D上可满足或是D上的可满足式。
定义7 设P为谓词公式,对于任何个体域:
(1)若P都永真,则称P为永真式。
(2)若P都永假,则称P为永假式。
(3)若P都可满足,则称P为可满足式。
常用逻辑等价式
谓词逻辑中的形式演绎推理