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