第五章一阶逻辑等值演算及推理

1、“凡人都呼吸”。第五章 一阶逻辑等值演算与推理 可以符号化为两种形式：x (F(x) G(x)和x (F(x) G(x)它们都是正确的，所以同命题逻辑中一样，它们是等值的。定义定义5.1 设A，B是一阶逻辑中任意两个公式，若A B是永真式，则称A与B是等值等值的。记做AB，称A B是等值式等值式。 即：x (F(x) G(x) x (F(x) G(x)5.1 一阶逻辑等值式与置换规则 一、几组基本等值式 第一组 代换实例 由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。例如： xy(F(x,y) G(x,y)xF(x)

2、xF(x) xy(F(x,y)G(x,y) xy(F(x,y)G(x,y)第二组 消去量词等值式 (2)xA(x) A(a1)A(a2)A(an) 设个体域为有限域D=a1,a2,an，则有(1)xA(x) A(a1)A(a2)A(an)第三组 量词否定等值式 设A(x)是任意的含有自由出现个体变项x的公式，则 1)xA(x) xA(x)2)xA(x) xA(x) 第四组 量词辖域收缩与扩张等值式 设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则 x(BA(x) B xA(x) 1) x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)B2

3、) x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(BA(x) B xA(x) 第五组 量词分配等值式 设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) 二、基本规则 一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B是一阶逻辑公式。 1置换规则 设(A)是含公式A的公式，(B)是用公式B取代(A)中所有的A之后的公式，若AB，则(A) (B).2换名规则 设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应

4、的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为A，则AA. 3代替规则 设A为一公式，将A中某个自由出现的个体变项的所有出现用A中未曾出现过的个体变项符号代替，A中其余部分不变，设所得公式为A，则AA. 三、等值演算 例例5.1 将下面公式化成与之等值的公式，使其没有既是约束出现又是自由出现的个体变项。(1) xF(x,y,z)yG(x,y,z)解解： xF(x,y,z)yG(x,y,z) tF(t,y,z) yG(x,y,z) (换名规则) tF(t,y,z) wG(x,w,z) (换名规则) 或 xF(x,y,z)yG(x,y,z) xF(x,t,z

5、) yG(x,y,z) (代替规则) xF(x,t,z) yG(w,y,z) (代替规则)(2) 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是偶数，代替B(x). 则x(F(

6、x)G(x)为真命题，而xF(x)xG(x)为假命题。两边不等值。在同样的解释I下，下， x(A(x)B(x) 为假命题， xA(x)xB(x)为真命题，两边不等值。全称量词对无分配律存在量词对无分配律例例5.3 设个体域为Da,b,c，将下面各公式的量词消去：1) x(F(x)G(x) 2) x(F(x)yG(y) xF(x)yG(y) (F(a)F(b)F(c)(G(a)G(b)G(c) (F(a)G(a)(F(b)G(b)(F(c)G(c) 3) xyF(x,y) x(F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c) (F

7、(c,a)F(c,b)F(c,c) 例5.4 给定解释I如下：(a) 个体域D=3,4。(b) (x)为 (3)=4， (4)=3。(c) (x,y)为 (3,3)= (4,4)=0， (3,4)= (4,3)=1。 fffFFFFF试求下列公式在I下的真值： (1) xyF(x,y) (F(3,3)F(3,4)(F(4,3)F(4,4) (01)(10) 1(2) xyF(x,y)(F(3,3)F(3,4)(F(4,3)F(4,4)(01)(10)0(3) xy(F(x,y)F(f(x),f(y) (F(3,3)F(f(3),f(3) (F(4,3)F(f(4),f(3) (F(3,4)F(

8、f(3),f(4)(F(4,4)F(f(4),f(4) (00)(11)(11)(00) 1例5.5 证明下列等值式 1）x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) （德.摩根律） x(F(x)G(x) （量词否定等值式） x(F(x)G(x) （蕴涵等值式）2） x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) （蕴涵等值式） x(F(x)G(x) （量词否定等值式） x(F(x)G(x) （德.摩根律）3） x(F(x)y(F(y)H(x,y)L(x,y) xy(F(x)F(y)H(x,y)L(x,y) x y(F(x)F(y)H(x,y)L(x,y)

9、 （蕴涵等值式） x(F(x) y(F(y)H(x,y)L(x,y)xy(F(x)(F(y)H(x,y)L(x,y) （辖域扩张等值式）xy(F(x)（(F(y)H(x,y)）L(x,y) （蕴涵等值式） x y(F(x)F(y)H(x,y)L(x,y) （德.摩根律）5.2 一阶逻辑的前束范式 定义定义5.2 设A为一个一阶逻辑公式，若A具有如下形式Q1x1Q2x2QkxkB 则称A为前束范式前束范式，其中Qi(1ik)为 或，B为不含量词的公式。例如，xy(F(x)G(y)H(x，y) xyz(F(x)G(y)H(z)L(x，y，z)都是前束范式 而：x(F(x)y(G(y)H(x，y)

10、x(F(x)y(G(y)H(x，y) 都不是前束范式 定理定理5.1 (前束范式存在定理)一阶逻辑中的任何公式都存在与之等值的前束范式。 例例5.6 求下面公式的前束范式： (1) xF(x)xG(x)解：解： xF(x)yG(y) xF(x)yG(y) x(F(x)yG(y) xy(F(x)G(y) x(F(x)G(x) 或者 xF(x)xG(x) xF(x)xG(x) 由此可知，前束范式是不唯一的。 (2) xF(x)xG(x) xF(x) xG(x) xF(x) yG(y) (换名规则) x(F(x) yG(y) xy(F(x) G(x)？ x(F(x)G(y) 说明：1、一个公式的前束

11、范式的各指导变元应是各个不同的。2、原公式中自由出现的个体变项在前束范式中还应是自由出现的。例5.7 求下列公式的前束范式 （1） xF(x) yG(x,y) （2） xF(x,y) xG(x,y) （3） x1(F(x1,x2) x2G(x2) x2H(x1,x2) 5.3 一阶逻辑推理理论 推理的形式结构依然采用蕴含式的的形式：A1A2Ak BA1A2Ak B若该式为永真式，则称推理正确，称B是前提A1A2Ak的有效结论。记为：同样也可以写成如下形式：前提： A1，A2，Ak结论： B在一阶逻辑中，称永真式的蕴涵式为推理定律。推理定律的主要来源有：第一组 命题逻辑推理定律的代换实例。例如：

12、xF(x)yG(y) xF(x)xF(x)xF(x)yG(y)第二组 由基本等值式生成的推理定律。 xF(x)xF(x) xF(x) xF(x) xF(x)xF(x) xF(x) xF(x) 和每个等值式可生成两个推理定律 第三组 关于量词分配的推理定律。(1) xA(x)xB(x) x(A(x) B(x)）(2) x(A(x) B(x)） xA(x) xB(x)(3) x(A(x) B(x) ) xA(x)xB(x)(4) x(A(x) B(x) ) xA(x) xB(x)(5) x(A(x) B(x) ) xA(x) xB(x)在命题逻辑中判断推理的方法很多，可以通过等值演算，真值表，构造

13、证明法。但在一阶逻辑中很困难，主要是通过构造证明法。为了构造推理系统，给出四条推理规则：1全称量词消去规则(简记为UI规则或UI)()(yAxxA或)()(cAxxA两式成立的条件是：1）在第一式中，取代x的y应为任意的不在A(x)中约束出现的个体变项。2）在第二式中，c为任意个体常项。3）用y或c去取代A(x)中自由出现的x时，一定要在x自由出现的一切地方进行取代。2全称量词引入规则(简记为UG规则或UG)()(xxAyA该式成立的条件是：1）无论A(y)中自由出现的个体变项y取何值，A(y)应该均为真。2）取代自由出现的y的x也不能在A(y)中约束出现。 3存在量词引入规则(简称EG规则或

14、EG)()(xxAcA该式成立的条件是：1）c是特定的个体常项。2）取代c的x不能在A(c)中出现过。 该式成立的条件是： 4存在量词消去规则(简记为EI规则或EI) )()(cAxxA（1）c是使A为真的特定的个体常项。（2）c不在A(x)中出现。（3）若A(x)中除自由出现的x外，还有其它自由出现的个体变项，此规则不能使用。 只能对前束范式使用UI，UG，EI，EG规则。例例5.8 设个体域为实数集合，F(x,y):xy。G(X):X是偶数，指出下面使用规则的错误。),(),(yyyFyxyFxUI规则),(),(xxxFxyxxFUG规则),()5 ,(xxxFxxxFEG规则)3()(

15、GxxGEI规则定义定义5.3 一阶逻辑自然推理系统自然推理系统F定义如下：1、 字母表。同一阶语言L的字母表2、合式公式。同L合式公式的定义3 、推理规则： （1） 前提引入规则。 （2） 结论引入规则。 （3） 置换规则。 （4） 假言推理规则。 （5） 附加规则。 （6） 化简规则。 （7） 拒取式规则。 （8） 假言三段论规则。 （9） 析取三段论规则。 （10）构造性二难推理规则。 （11）合取引入规则。 （12）UI规则。 （13）UG规则。 （14）EI规则。 （15）EG规则。 例例5.9 设个体域为实数集合，设个体域为实数集合，F(x,y)为为xy. 指出在推指出在推理系统理

16、系统F中，以中，以 x yF(x，y)(真命题真命题)为前提，推出为前提，推出 xF(x,c)(假命题假命题)的下述推理证明中的错误。的下述推理证明中的错误。 x yF(x,y) 前提引入前提引入 yF(z,y) UI规则规则 F(z,c) EI规则规则 xF(x,c) UG规则规则 Z也是自由出现，同时有多个自由出现不能用EI规则。错！错！例例5.10 在自然推理系统F中，构造下面推理的证明：任何自然数都是整数；存在着自然数。所以存在着整数。个体域为实数集合R。 解解 先将原子命题符号化。设 F(x):x为自然数，G(x):x为整数。 前提： x(F(x)G(x), xF(x)结论： xG(

17、x)证明： xF(x) 前提引入 F(c) EI规则 x(F(x)G(x) 前提引入 F(c)G(c) UI规则 G(c) 假言推理 xG(x)EG规则 x(F(x)G(x) 前提引入 F(c)G(c) UI规则 xF(x) 前提引入 F(c) E1规则如果证明如下：在中取c=2,则F(2)G(2)为真（前件假）,于是中F(2)为假，这样从前件真推出了假的中间结果。注意：在证明序列中先引进带存在量词的前提。前提： x(F(x)(G(a)R(x), xF(x)结论： x(F(x)R(x) 证明： x(F(x)R(x) EG xF(x) 前提引入 F(c) EI x(F(x)(G(a)R(x) 前提引入 F(c)(G(a)R(c) UI G(a)R(c) 假言推理 R(c) 化简 F(c)R(c) 合取所有的人或者是吃素的或者是吃荤的，吃素的常吃豆制品，因而不吃豆制品的人是吃荤的。（个体域为人的集合）。 个体域为人类集合，所以不用引入特性谓词， 令F(x)：x是吃素的，G(x)：x是吃荤的，H(x)：x吃豆制品。 前提： x(F(x)G(x)， x(F(x)H(x) 结论： x(H(x)G(x) x(F(x)G(x) 前提引入 F(y)G(y) UI F(y)G(y) 置换证明： x(H(x)G(x) UG F(y)H(y) 置换 H(y)F(y) 置换 H(y)G(y) 假言三段论