一阶逻辑等值演算与推理

《一阶逻辑等值演算与推理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章一阶逻辑等值演算与推理5.1一阶逻辑等值式与置换规则定义5.1设A，B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B是等值的。记做AB，称AB是等值式。谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。下面主要讨论关于量词的等值式。一、基本等值式第一组代换实例由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。例如xF(x)┐┐xF(x)与xy(F(x,y)→G(x,y))┐┐xy(F(x,y)→G(x,y))都是(2.1)式（

2、双重否定律）的代换实例。又如：F(x)→G(y)┐F(x)∨G(y)与x(F(x)→G(y))→zH(z)┐x(F(x)→G(y))∨zH(z))等都是(2.12)式（蕴涵等值式）的代换实例。第二组消去量词等值式设个体域为有限域D={a1,a2,…,an}，则有(1)xA(x)A(a1)∧A(a2)∧…∧A(an)(2)xA(x)A(a1)∨A(a2)∨…∨A(an)  (5.1)第三组量词否定等值式设A(x)是任意的含有自由出现个体变项x的公式，则(1)┐xA(x)x┐A(x)    (2)┐xA(x)

3、x┐A(x)  (5.2)直观解释：对于(1)式，“并不是所有的x都有性质A”与“存在x没有性质A”是一回事。对于(2)式，“不存在有性质A的x”与“所有x都没有性质A”是一回事。第四组量词辖域收缩与扩张等值式设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则：(1)x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧Bx(A(x)→B)xA(x)→Bx(B→A(x))B→xA(x)      (5.3)(2)x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧

4、Bx(A(x)→B)xA(x)→Bx(B→A(x))B→xA(x)       (5.4)注意：这些等值式的条件第五组量词分配等值式设A(x)，B(x)是任意的含自由出现个体变项x的公式，则(1)x(A(x)∧B(x)）xA(x)∧xB(x)(2)x(A(x)∨B(x))xA(x)∨xB(x) (5.5)二、基本规则1．置换规则设Φ(A)是含公式A的公式，Φ(B)是用公式B取代Φ(A)中所有的A之后的公式，若AB，则Φ(A)Φ(B).一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A

5、，B是一阶逻辑公式。2．换名规则设A为公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为A'，则A'A.3．代替规则设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替，A中其余部分不变，设所得公式为A'，则A'A.三、等值演算例5.1将下面公式化成与之等值的公式，使其没有既是约束出现又是自由出现的个体变项。(1)xF(x,y,z)→yG(x,y,z)(2)x(F(x,y)→yG(x,y,z))解(1)

6、xF(x,y,z)→yG(x,y,z)   tF(t,y,z)→yG(x,y,z)   (换名规则)tF(t,y,z)→wG(x,w,z) (换名规则)原公式中，x，y都是既约束出现又有自由出现的个体变项，只有z仅自由出现。而在最后得到的公式中，x，y，z，t，w中再无既是约束出现又有自由出现个体变项了。还可以如下演算，也可以达到要求。xF(x,y,z)→yG(x,y,z)   xF(x,t,z)→yG(x,y,z)    (代替规则)   xF(x,t,z)→yG(w,y,z)    (代替规则)

7、x(F(x,y)→yG(x,y,z))x(F(x,t)→yG(x,y,z))   (代替规则)或者    x(F(x,y)→yG(x,y,z))x(F(x,y)→tG(x,t,z))    (换名规则)例5.2证明(1)x(A(x)∨B(x))xA(x)∨xB(x)    (2)x(A(x)∧B(x))xA(x)∧xB(x)其中A(x)，B(x)为含x自由出现的公式。证(1)只要证明在某个解释下两边的式子不等值。取解释I：个体域为自然数集合N；取F(x)：x是奇数，代替A(x)；取G(x)：x是偶数，代

8、替B(x).则x(F(x)∨G(x))为真命题，而xF(x)∨xG(x)为假命题。两边不等值。对于(2)可以类似证明。取解释I：个体域为实数集合R；取F(x)：x是奇数，代替A(x)；取G(x)：x