基于谓词逻辑的机器.ppt

3.1 一阶谓词逻辑 3.1.1 谓词、函数、量词 谓词 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)) 例3.1 不存在最大的整数，我们可以把它翻译为 乛 x (G(x)∧ y(G(y)→D(x,y)) 或 x (G(x)→ y(G(y)∧D(y,x)) 例3.2 对于所有的自然数，均有x+yx x y(N(x)∧N(y)→S(x+y,x)) 例3.3 某些人对某些食物过敏 x y(M(x)∧F(y)∧G(x,y)) 3.1.2 谓词公式 定义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为谓词公式，对于任何个体域：