第4章谓词逻辑课件.ppt

内容提要 本章学习要求 谓词公式的类型 公式G称为可满足的，如果存在解释I，使G在I下取1值，简称I满足G。若I不满足G，则简称I弄假G。 公式G称为是恒假的(或不可满足的)，如果不存在解释I满足G。 公式G称为逻辑有效的，或永真的，恒真的，如果G在任何解释I下都满足G。 给定解释N如下： ⑴个体域为自然数集合DN； ⑵DN中的特定元素 a =0； ⑶DN上的函数f(x,y)=x+y,g(x,y)=x·y; ⑷DN上的谓词F(x,y)为x=y; 在解释N下,下面哪些公式为真？哪些公式为假？ ⑴?xF(g(x,a),x); ⑵?x?y(F(f(x,a),y)?F(f(y,a),x)) ； ⑶?x?y?zF(f(x,y),z); ⑴ ?xF(g(x,a),x) = ?x F(g(x,0),x) = ?x F(x?0,x) = ?x F(x?0=x) = ?x F(0=x) ⑵ ?y(F(f(x,a),y)?F(f(y,a),x)) =?x?y(F(x+0,y)?F(y+0,x)) =?x?y(x+0=y?y+0=x) =?x?y(x=y?y=x) ⑶ ?x?y?z(F(f(x,y),z) =?x?y?z(F(f(x,y),z) =?x?y?z(F(x+y,z) =?x?y?z(x+y=z) ⑷?x?yF(f(x,y),g(x,y)); ⑸F(f(x,y),f(y,z)); ⑷ ?x?yF(f(x,y),g(x,y)) =?x?yF(x+y,x?y) =?x?y(x+y=x?y) 该公式恒假 ⑸ F(f(x,y),f(y,z)) =F(x+y,y+z) =x+y=y+z 该公式是可满足式 改名规则——量词的辖域，约束变元，自由变元 ?x(P(x，y)?Q(x，z))?R(x) ?x(P(x，y)?Q(x，z))?R(x) 约束变量 自 由 变 量（元） ?x的作用域 x既是约束变元，又是自由变元。 指出下列公式的约束变量和自由变量 ⑴?xP（x,y）;⑵?xQ(y); ⑶? x (P(x)??yQ(x,y))；⑷?xP(x) ?Q(x) y y x x x x,y x ?xP（x,y） ?xQ(y); ? x (P(x)??yQ(x,y)) ?xP(x) ?Q(x) 自由变量 约束变量 谓词公式 约束变量改名规则 ⑴将在量词中的作用变量以及该量词辖域中全部约束变量都用新的个体变量替换； ⑵新变量在原谓词公式中不出现。 自由变量改名规则 ⑴将公式中所有自由变量用新的个体变量替换； ⑵新个体变量在原谓词公式中不出现。 代替规则 代替规则：设A是一公式，将A中某个自由出现的个体变项所有出现用A中未曾出现的个体变项符号代替，A中其它部分不变，设所得公式为A?，则A= A?。 ⑴约束出现改名规则，将量词辖域中某个约束出现的个体变量及相应约束变元，改成本辖域中未曾出现过的个体变量，其余不变。 ⑵自由变元代入规则，对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。 个体变元改名或代入遵循的规则： 改名规则与代入规则的关系 共同点是不能改变约束关系。 不同点： ⑴施行的对象不同。 ⑵施行的范围不同。 ⑶施行后的结果不同。 1为了避免同一个个体变元既是自由的又是约束的； 2为了方便后面的计算谓词公式范式. ?x F(x)∧G(x,y) =?z F(z)∧G(x,y) x 约束变元 改名规则 ?x F(x)∧G(x,y) =? xF(x)∧ G(z, y ) x 自由变元 代入规则 ?x?y(R(x,y)∨L(y,z))∧?x H(x,y) ?x?y(R(x,y)∨L(y,z))∧?x H(x,y) =?x?y(R(x,y)∨L(y,z))∧?tH(t,y) (换名规则t) =?x?y(R(x,y)∨L(y,z))∧?t H(t,w) (代替规则w) 4.4 逻辑等值的谓词公式 谓词公式等值：设A，B是谓词公式，若A，，在其任意解释I下的确取值都相同，则称A，B是逻辑等值的，记作 A=B。 公式A，B是等值的当且仅当A?B是恒真的。 命题逻辑中给出的基本等价式，在谓词逻辑中仍然成立。 ⑴ (G?H)=(G?H)?(H?G)； ⑵ (G?H)=(?G?H)； ⑶ G?G=G，G?G=G； (等幂律) ⑷ G?H=H?G，G?H=H?G；