--一阶逻辑公式及解释.ppt

4.2 4.2 一阶逻辑公式及解释一阶逻辑公式及解释 上节学习了 一阶逻辑的基本概念：个体词、谓词、量词 一阶逻辑符号化的有关概念和方法本节学习 一阶逻辑公式的概念：字母表、项、原子公式、公式、指导变元、辖域、闭式等 一阶逻辑公式的解释及公式类型的判断。1.定义定义4.14.1（字母表）（字母表）以下是字母表的成员：(1)个体常项:a，b，c，ai，bi，ci，i1(2)个体变项:x，y，z，xi，yi，zi，i1(3)函数符号:f，g，h，fi，gi，hi，i1(4)谓词符号:F，G，H，,Fi，Gi，Hi，i1(5)量词符号:，(6)联结词符号:，(7)括号和逗号:（）（），2.定义定义4.2（项）（项）项的递归定义如下：（1）个体常项和个体变项是项。（2）如果(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)仍然是项。（3）只有有限次使用(1)，(2)生成的符号串才是项。定义定义4.34.3（原子公式）（原子公式）设R(x1,x2,xn)是任意的n元谓词，t1,t2,tn是任意的n个项，则称R（t1,t2,tn）为原子公式原子公式。原子公式是谓词逻辑公式的最小单位，最小的句子单位在谓词逻辑中，项起的是名词的作用，不是句子。3.例：例：D D是个体名称的集合，x,yx,y（DD）为个体变项，a a：张三，b b：李四 所以x x，y y，a a，b b是项 假设f(x):xf(x):x的父亲，F(x,y):xF(x,y):x是y y的父亲 f(a),f(f(a)f(a),f(f(a),F(a,b)F(a,b),F(f(f(a),b)F(f(f(a),b)则f(a)f(a):张三的父亲，是项项 f(f(a)f(f(a):张三的祖父，是项项 而F(a,b)F(a,b):张三是李四的父亲，是原子公式原子公式 F(f(f(a),b)F(f(f(a),b):张三的祖父是李四的父亲，是原子公式原子公式4.定义定义4.4（谓词公式）（谓词公式）谓词公式也称为合式公式，其递归定义如下：（1）原子公式是谓词公式 （2）若A谓词公式，则A也是谓词公式 （3）若A，B是谓词公式，则AB，AB，AB，AB也是谓词公式 （4）若A是公式，则 xA，xA也是谓词公式 （5）只有有限次使用（1）-（4）生成的符号串才是谓词公式简单起见，谓词公式简称为公式公式。5.定义定义4.5（量词的辖域）（量词的辖域）在公式 xA和 xA中，称x是指导变元，A为相应量词的辖域。在 x和 x的辖域中，x的所有出现都称为约束出现 A中不是约束出现的变项均称为是自由出现的 说明：说明：量词的辖域以量词后第一个括号的范围为准6.解：解：（1 1）x x（F F（x x，y y）GG（x x，z z）x x是指导变元 量词 的辖域为F F（x x，y y）GG（x x，z z）x x是约束出现的，约束出现2 2次 y y和z z是自由出现的，各出现1 1次 例例4.64.6 指出下列公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项：（1 1）x x（F F（x x，y y）GG（x x，z z）（2 2）x x（F F（x x）GG（y y）y y（H H（x x）LL（x x，y y，z z）7.前 件：x是 指 导 变 元，量 词 的 辖 域 为F(x)G(y)，其中x是约束出现的，y是自由出现的 后 件：y是 指 导 变 元，量 词 的 辖 域 为H(x)L(x,y,z)，其中y是约束出现的，x和z是自由出现的。在整个公式中，x约束出现1次，自由出现2次 y约束出现1次，自由出现1次 z自由出现1次。（2 2）x（F（x）G（y）y（H（x）L（x，y，z）8.定义定义2.62.6（闭式）（闭式）设A A为任意的公式，若A A中无自由出现的个体变项，则称A A是封闭的公式，简称闭式。例如：（1）x（F（x）G（x）（2）x（F（x）G（x，y）显然（1）是闭式，（2）不是闭式9.定义定义2.72.7（解释）（解释）一个解释I有下面4个部分组成：（1）非空个体域D：指定个体词的取值范围（2）D中特定元素的集合：指定个体常项的值（3）D上特定函数的集合：指定函数符号的含义（4）D上特定谓词的集合：指定谓词的含义 说明说明：在使用一个解释I解释一个公式A时，将A中的个体常项、函数和谓词分别用I中指定的个体常项、函数和谓词代替。10.（1）F(f(x,y),g(x,y)（2）F(f(x,a),y)F(g(x,y),z)（3）xF(g(x,y),z)（4）xF(g(x,a),x)F(x,y)（5）xF(g(x,a),x)（6）x y(F(f(x,a),y)F(f(y,a),x)（7）x y zF(f(x,y),z)例例4.8 给定解释I：（a）个体域D=N（自然数集合）；（b）a=0；（c）f(x,y)=x+y、g(x,y)=x*y；（d）F(x,y)：x=y。在I下，判断下列公式的真值？11.（1）F(f(x,y),g(x,y)公式被解释成：x+y=x*y 在解释I下，该公式不是命题（2）F(f(x,a),y)F(g(x,y),z)公式被解释成：(x+0=y)(x*y=z)在解释I下，该公式不是命题（3）xF(g(x,y),z)公式被解释成：x(x*y=z)在解释I下，该公式不是命题12.（4）xF(g(x,a),x)F(x,y)公式被解释成：x(x*0=x)(x=y)由于蕴涵式的前件为假，所以在解释I下公式为真命题（5）xF(g(x,a),x)公式被解释成：x(x*0=x)在解释I下公式为假命题（6）x y(F(f(x,a),y)F(f(y,a),x)公式被解释成：x y(x+0=y)(y+0=x)在解释I下公式为真命题（7）x y z F(f(x,y),z)公式被解释成：x y z(x*y=z)，在解释I下公式为真命题13.（1）F(f(x,y),g(x,y)不是命题不是命题（2）F(f(x,a),y)F(g(x,y),z)不是命题不是命题（3）xF(g(x,y),z)不是命题不是命题（4）xF(g(x,a),x)F(x,y)真命题真命题（5）xF(g(x,a),x)假命题假命题（6）x y(F(f(x,a),y)F(f(y,a),x)真命题真命题（7）x y zF(f(x,y),z)真命题真命题例例4.8 给定解释I：（a）个体域D=N（自然数集合）；（b）a=0；（c）f(x,y)=x+y、g(x,y)=x*y；（d）F(x,y)：x=y。在I下，判断下列公式的真值？14.说明：说明：(1)(1)有的公式在具体的解释中真值确定，即为命题；有的公式在具体的解释中真值不确定，即不是命题。(2)(2)闭式在任意的解释下都变成可命题(定理4.1)，但在不同的解释下，可能有不同的真值。(3)(3)非闭式的公式就不一定具有这种性质，它可能在有的解释中是命题，有的解释中不是命题。15.说明：说明：（1 1）永真式是可满足式，反之不然。（2 2）由于公式的复杂性和解释的多样性，到目前为止，还没有一个可行的算法判断某一公式是否是可满足的。（3 3）但可以利用代换实例的相关性质来判断某些特殊的公式。而对于一般的公式只能通过构造解释的方法来判断。定义定义4.84.8（一阶公式的分类）（一阶公式的分类）设A为一公式，若A在任何解释下均为真，则称A是永真式永真式（或称逻辑有效式逻辑有效式）。若A在任何解释下均为假，则称A是矛盾式矛盾式（或永假式永假式）。若至少存在一个解释使A为真，则称A是可满足式可满足式。16.定义定义4.9（代换实例）（代换实例）设A0是含命题变项p1，p2，pn的命题公式，A1，A2，An是n个谓词公式，用Ai（1in）处处代替A0中的pi，所得公式A称为A0的代换实例代换实例。例如例如 F(x)G(x)，xF(x)yG(y)都是pqpq的代换实例定理定理4.2 4.2 永真式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。问 x(F(x)G(x)是pq的代换实例么？17.例例 判断下列公式的类型。（1）xF(x)(x yG(x,y)xF(x)（2）(x F(x)yG(y)yG(y)解：解：（1）xF(x)(x yG(x,y)xF(x)公式是p(qp)的代换实例，而p(qp)是永真式，所以公式（1）是永真式 （2）(x F(x)yG(y)yG(y)公式是（pq）q的代换实例，而（pq）q是矛盾式，所以公式（2）是矛盾式说明：对于这些类型的公式完全可以采用等值演算的 方法加以判断。18.例例 判断下列公式的类型？（1）x(F(x)G(x)（2）x(F(x)G(x)（3）x yF(x,y)x yF(x,y)（4）xF(x)xF(x)判断方法：如果公式不是命题逻辑永真式或矛盾式的代换实例，则只能通过构造解释的方法来进行判断。（1）对于非永真的可满足式，需要分别具体构造一个成真解释和一个成假解释来说明。（2）对于永真式（矛盾式），则必须证明该公式在任意的解释下都是真（假）的。19.（1）x(F(x)G(x)取解释I1：个体域为实数集合R，F(x):x是整数，G(x):x是有理数。在解释I1下，公式为真，所以不是矛盾式。取解释I2：个体域为实数集合R，F(x):x是有理数，G(x):x是整数。在解释I2下，公式为假，所以不是永真式。所以（1）式为非永真的可满足式。20.（2 2）x(F(x)G(x)x(F(x)G(x)取解释I I1 1：个体域为实数集合R R，F(x):xF(x):x是整数，G(x):xG(x):x是有理数。在解释I I1 1下，公式为真，所以不是矛盾式。取解释I I2 2：个体域为实数集合R R，F(x):xF(x):x是整数，G(x):xG(x):x是无理数。在解释I I2 2下，公式为假，所以不是永真式。所以（2 2）为非永真的可满足式。21.（3）x yF(x,y)x yF(x,y)取解释I1为：个体域为自然数集合N，F(x,y):x=y。在解释I1下，公式的前件 x y(x=y)是真的，而后件 x y(x=y)是假的，所以公式为假。取解释I2为：个体域为自然数集合N，F(x,y):xy。在解释I2下，公式的前件和后件都为真，所以公式为真。所以（3）为非永真的可满足式。22.（4）xF(x)xF(x)设I为任意的解释，个体域为D。按 xF(x)是否为真分两种情况进行讨论：若 xF(x)为真，则 xF(x)为真，因此公式为真。若 xF(x)为假，则公式为真。由以上讨论及解释I的任意性，所以（4）为永真式。23.