5.1 一阶逻辑等值式与置换规则.ppt

1、1，第5章，一阶逻辑等价演算与推理5.1，一阶逻辑等价公式与替换规则，2，定义5.1(等价公式)，设A和B是一阶逻辑中的任意两个公式，如果AB是永恒真理公式，那么A和B是等价的，这叫做AB。以下是一阶逻辑中一些基本而重要的等价表达式：由于命题逻辑中重言式的替换例子都是一阶逻辑的永恒真实表达式，所以命题逻辑中24个等价模式(第24页)给出的替换例子都是一阶逻辑的等价模式。例如，xF(x)xF(x) xy(F(x，y)G(x，y) xy(F(x，y)G(x，y)都是AA的替代例子。这里有一些一阶逻辑的固有等价物，它们都与量词相关。1.消除量词等价。如果单个域是有限集合D=a1，a2和an，那么有(

2、1)xa(x)a(a1)a(a2)a(an)(2)xa(x)a(a1)a(a2)a(an)2。量词否定任何公式a. 3的等价性。量词范围收缩和扩张等价公式设A(x)是一个任意公式，有自由出现的单个变量x，B是一个没有x的公式，那么(1)x(A(x)B)xa(x)B x(A(x)B)xa(x)B x(B A(x)bxa(x)(2)x(A(x)B 4。量词分配等价公式对于任何公式A(x)和B(x):(1)x(A(x)B(x)xa(x)x B(x)(2)x(A(x)B(x)xa(x)x B(x)，请解释：但是配对和配对没有分配定律。6，5。任何公式A(x，y) (1)xyA(x，y) yxA(x，y

3、) (2)xyA(x，y) yxA(x，y)，7的等价公式。一阶逻辑等价演算一阶逻辑等价演算的三个重要规则：1 .例如，让单个字段为D=a，b，c，并在下面的公式中消除量词。(1)x(F(x)G(x)(2)x(F(x)Yg(y)(3)XyF(x，y)，(1)x(F(x)G(x)(F(a)G(a)(F(b)G(b)(F(c)G(c)(2)x(F(x)Yg(y)Xf(x)。A)F(a，b)F(a，c) (F(b，a)F(b，b)F(b，c) (F(c，a)F(c，b)F(c，c)10，给出了一个例子，并作了如下解释I:在(b)D中，特定函数f(x)是：f(2)=3，特定谓词G(x，y)是：g (2

4、，2)=g (2，3)=g (3，3) L(x，y)F(x)为：F(2)=0，F(3)=1。在“我”下，找到以下真实值。(1)x(F(x) G(x，a) (2) x (f (f) g (x，f (x) (3) x y l (x，y) (4)y x L(x，y)，11，解决方案：2)(01)(11)0(2)x(F(x)G(x，F(x)(F(2)G(2，f(2) (F(f(3)G(3，f(3) (F(3)G)(1)X(M(X)F(X)X(M(X)F(X)(2)X(F(X)G(X)X(F(X)G(X)(3)X y(F(X)G(y)H(X，y) x y(F(x)G(y)H(x，y) (4)x y(F(

5、x)G(y)L(x，y) x y(F(x)G(y)L(x，y)、14(1)y)x y(F(x)G(y)H(x，y)A) (B4)x y(F(x)G(y)L(x，y) x y(F(x)G(y)L(x，y)和(3) 2。名称更改规则将A设置为公式，并将限定变量在量词域中的所有出现以及相应的引导变量更改为从未在量词域中出现过的单个变量符号，公式的其余部分保持不变。如果得到的公式是A，那么是AA。17，解决方案：xF(x，y，z)yG(x，y，z) sF(s，y，z)yG(x，y，z)(重命名规则)sF(s，y，z)tG(x，t，z)(重命名规则)XF(x，y，z)yG(x，y，z)，18，一阶逻辑等

6、价演算中的三个重要规则：1。替换规则是(A)是包含公式A的公式，(B)是通过用公式B替换(A)中的所有A而获得的公式，如果是a B，则(A) (B 2)。名称更改规则将A设置为公式，并将限定变量在量词域中的所有出现以及相应的引导变量更改为从未在量词域中出现过的单个变量符号，公式的其余部分保持不变。如果得到的公式是A，那么是AA。3.替换规则：假设A是一个公式，用A中从未出现过的单个变量符号替换A中所有出现的自由单个变量，公式的其余部分保持不变。让得到的公式为，然后为。19，解：(1)xF(x，y，z)yG(x，y，z) sF(s，y，z)yG(x，y，z)(重命名规则)sF(s，y，z)tG(

7、x，t，z)(.(1)xF(x，y，z)yG(x，y，z) (2)x(F(x，y)yG(x，y，z)，20，(2)x(F(x，y)yG(x，y，z)第5章一阶逻辑等价计算和推理5.2一阶逻辑Toe范式，22，定义5.2 (Toe范式)设A为一阶逻辑公式。如果A有以下形式：Q1x1Q2x2QkxkB，那么A是toe范式，Qi(1ik)是or，而B是无字公式。例如：x y(F(x)G(y)H(x，y) x y z(F(x)G(y)H(z)L(x，y，z)和其他公式都是前束范式。X F(x)x G(x) x(F(x)y(G(y)H(x，y)和其他公式不是标准形式。注意：在前束范式中，没有单独的变量是

8、自由和限制性的。23，定理5.1(toe范式的存在定理)一阶逻辑中的任何公式都有其等价的toe范式。说明：(1)定理表明任何公式的toe范式都存在，但它不是唯一的。(2)利用前一节中的等价公式和三个变换规则，可以得到公式的toe范式。24，示例5.6找到以下公式的前束范式。(1)x F(x)x G(x)(2)x F(x)x G(x)(3)x F(x)x G(x)(4)x F(x)x G(x)(5)x F(x，y)y G(x，y) (6)(x F(x，y)y G(y)x H(x，y，z)，25，(1)x F(x)x G(x)方法1: x f (x) XG (x)(等效替代)x F(x)！因为没有分配法！正确的解决方案如下：Xf(x)XG(x)XF(x)XG(x)XF(x)yg(y)Xy(F(x)G(y)、27、(3)xF(x)xG(x)方法1:YF(y)XG(x)y(F(y)XG(x)yx(F(y)G(x)方法2: xf (x) XG (x) xf (x) XG (4)x F(x)x方法1的30，(6)(x F(x，y)y G(y