一阶逻辑等值演算与推理

1、第第5 5章章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理离离 散散 数数 学学大学本科生课程大学本科生课程本章说明本章说明q 本章的主要内容本章的主要内容 一阶逻辑等值式与基本等值式一阶逻辑等值式与基本等值式 置换规则、换名规则、代替规则置换规则、换名规则、代替规则 前束范式前束范式 一阶逻辑推理理论一阶逻辑推理理论q 本章与其他各章的关系本章与其他各章的关系 本章先行基础是前四章本章先行基础是前四章 本章是集合论各章的先行基础本章是集合论各章的先行基础本章主要内容本章主要内容 5.1 5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则5.2 5.2 一阶逻辑前束范式一阶逻辑前束范式

2、5.3 5.3 一阶逻辑的推理理论一阶逻辑的推理理论5.1 5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则q 在一阶逻辑中，有些命题可以有不同的符号化形式。在一阶逻辑中，有些命题可以有不同的符号化形式。q 例如：没有不犯错误的人例如：没有不犯错误的人令令 M(x):x M(x):x是人。是人。 F(x):x F(x):x犯错误。犯错误。则将上述命题的符号化有以下两种正确形式：则将上述命题的符号化有以下两种正确形式：(1) (1) x(M(x)x(M(x)F(x)F(x)(2)(2) x(M(x)F(x)x(M(x)F(x)q我们称我们称(1)(1)和和(2)(2)是等值的。是等值的。

3、说说明明等值式的定义等值式的定义定义定义5.15.1 设设A A，B B是一阶逻辑中任意两个公式，若是一阶逻辑中任意两个公式，若 A AB B是永是永真式，则称真式，则称A A与与B B是是等值等值的。的。记做记做A AB B，称，称 A AB B 是是等值式等值式。G(x)G(x)x(F(x)x(F(x)G G( (x x) ) )x x( (F F( (x x) ) 例如：例如：q 判断公式判断公式A A与与B B是否等值，等价于判断公式是否等值，等价于判断公式A AB B是否为永真式。是否为永真式。q 谓词逻辑中关于联结词的等值式与命题逻谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式

4、类似。辑中相关等值式类似。 说说明明一阶逻辑中的一些基本而重要等值式一阶逻辑中的一些基本而重要等值式q 代换实例代换实例q 消去量词等值式消去量词等值式 q 量词否定等值式量词否定等值式 q 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 q 量词分配等值式量词分配等值式 代换实例代换实例q由于命题逻辑中的重言式的代换实例都是一阶逻由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的辑中的永真式，因而第二章的1616组等值式模式给组等值式模式给出的代换实例都是一阶逻辑的等值式的模式。出的代换实例都是一阶逻辑的等值式的模式。q例如：例如：(1)(1) xF(x) xF(x) x

5、F(x) xF(x) （双重否定律（双重否定律A A A A）(2)F(x)G(y) (2)F(x)G(y) F(x)G(y) F(x)G(y) （蕴涵等值式（蕴涵等值式AB AB AB AB）(3)(3) x(F(x)G(y) x(F(x)G(y) zH(z)zH(z) x(F(x)G(y)x(F(x)G(y) zH(z)zH(z) 等值式等值式 ? ?消去量词等值式消去量词等值式设个体域为有限集设个体域为有限集D=aD=a1 1,a,a2 2, ,a,an n,则有则有（1 1） xA(x) xA(x) A(aA(a1 1) )A(aA(a2 2) )A(aA(an n) ) （2 2）

6、xA(x) xA(x) A(aA(a1 1) )A(aA(a2 2) )A(aA(an n) ) （5.15.1）例例消去量词消去量词例例 设个体域为设个体域为D Da,b,ca,b,c，将下面各公式的量词消去：，将下面各公式的量词消去： (1) (1) x(F(x)G(x)x(F(x)G(x)(2) (2) x x yF(x,y)yF(x,y) (3) (3) x(F(x)G(x)x(F(x)G(x)解答解答(1)(1) x(F(x)G(x)x(F(x)G(x) ( (F(a)G(aF(a)G(a) () (F(b)G(bF(b)G(b) () (F(c)G(cF(c)G(c)例例消去量词消

7、去量词(2) (2) x x yF(x,y) yF(x,y) x(F(x,a)F(x,b)F(x,c) x(F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c) (F(c,a)F(c,b)F(c,c) 在演算中先消去存在量词也可以，得到结果是等值的。在演算中先消去存在量词也可以，得到结果是等值的。 x x yF(x,y) yF(x,y) yF(a,y) yF(a,y) yF(b,y) yF(b,y) yF(c,y)yF(

8、c,y) (F(a,a)F(a,b)F(a,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c) (F(c,a)F(c,b)F(c,c) 例例消去量词消去量词例例 设个体域为设个体域为D Da,b,ca,b,c，将下面各公式的量词消去：，将下面各公式的量词消去： (3) (3) x(F(x)G(x)x(F(x)G(x)解答解答(3)(3)x(F(x)G(x)x(F(x)G(x) (F(a)G(a) (F(b)G(b) (F(c)G(c)(F(a)G(a) (F(b)G(b) (F(c)G(c

9、)量词否定等值式量词否定等值式设设A(x)A(x)是任意的含自由出现个体变项是任意的含自由出现个体变项x x的公式，则的公式，则（1 1） xA(x) xA(x) xA(x)xA(x)（2 2） xA(x) xA(x) xA(x)xA(x)说明说明q “并不是所有的并不是所有的x x都有性质都有性质A”A”与与“存在存在x x没有没有性质性质A”A”是一回事。是一回事。q ”不存在有性质不存在有性质A A的的x”x”与与”所有所有X X都没有性质都没有性质A”A”是一回事。是一回事。（5.25.2）量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式设设A(x)A(x)是任意的含自由出现个体变项是

10、任意的含自由出现个体变项x x的公式，的公式，B B中不含中不含x x的出现的出现，则，则（1 1） x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(A(x)x(A(x)B) B) xA(x)xA(x)B B x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(BA(x) x(BA(x) B B xA(x)xA(x)（2 2） x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(A(x)x(A(x)B) B) xA(x)xA(x)B B x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(BA(x) x(BA(x) B B xA(x)

11、xA(x)（5.35.3）（5.45.4）证明证明: : x(A(x)B) x(A(x)B) xA(x)BxA(x)B xA(x)B xA(x)B x(A(x)B)x(A(x)B) xA(x)B xA(x)B xA(x)BxA(x)B x xA(x)BA(x)B x(x(A(x)B)A(x)B) x(A(x)B)x(A(x)B) x x( (A(x)BA(x)B) ) x x( (A(x)BA(x)B) ) x xA(x)BA(x)B xA(x) BxA(x) B xA(x)xA(x) B B量词分配等值式量词分配等值式设设A(x)A(x)，B(x)B(x)是任意的含自由出现个体变项是任意的含

12、自由出现个体变项x x的公式，则的公式，则（1 1） x(A(x)x(A(x)B(x) B(x) xA(x)xA(x) xB(x)xB(x)（2 2） x(A(x)B(x) x(A(x)B(x) xA(x) xA(x) xB(x)xB(x)（5.55.5）q 例如，例如，“联欢会上所有人既唱歌又跳舞联欢会上所有人既唱歌又跳舞”和和“联欢会上所联欢会上所有人唱歌且所有人跳舞有人唱歌且所有人跳舞” ” ，这两个语句意义相同。故有，这两个语句意义相同。故有(1)(1)式。式。q 由由(1)(1)式推导式推导(2)(2)式式 x(A(x)x(A(x)B(xB(x) ) xA(x)xA(x) xB(xx

13、B(x) )则有则有 x(x(A(x)A(x)B(xB(x) ) x xA(x)A(x) x xB(xB(x) )则有则有 x(A(x)B(xx(A(x)B(x) ) ( xA(x)xA(x) xB(xxB(x)则有则有 x(A(x)B(xx(A(x)B(x) ) xA(xxA(x) ) xB(xxB(x) )一阶逻辑等值演算的三条原则一阶逻辑等值演算的三条原则q 置换规则置换规则：设：设(A)(A)是含公式是含公式A A的公式，的公式，(B)(B)是用公式是用公式B B取代取代(A)(A)中所有的中所有的A A之后的公式，若之后的公式，若A AB B，则，则(A)(A)(B)(B)。 q 换

14、名规则换名规则：设设A A为一公式，将为一公式，将A A中某量词辖域中某约束变项的中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为某个体变项符号，公式的其余部分不变，设所得公式为AA，则则AAA A。q 代替规则代替规则：设设A A为一公式，将为一公式，将A A中某个自由出现的个体变项的中某个自由出现的个体变项的所有出现用所有出现用A A中未曾出现过的个体变项符号代替，中未曾出现过的个体变项符号代替，A A中其余部中其余部分不变，设所得公式为分不变，设所得公式为AA

15、，则，则AAA A。说明说明q 一阶逻辑中的置换规则与命题逻辑中的置换一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里规则形式上完全相同，只是在这里A A，B B是一是一阶逻辑公式。阶逻辑公式。例例5.15.1例例5.15.1 将下面公式化成与之等值的公式，使其将下面公式化成与之等值的公式，使其没有既是约束没有既是约束出现又是自由出现的个体变项出现又是自由出现的个体变项。(1)(1) xF(x,y,z)xF(x,y,z) yG(x,y,z)yG(x,y,z)(2)(2) x(F(x,y)x(F(x,y) yG(x,y,z)yG(x,y,z)(1)(1) x xF(F(x x

16、,y,z) ,y,z) yG(x,y,zyG(x,y,z) ) tF(t,y,z)tF(t,y,z) y yG(x,G(x,y y,z,z) )( (换名规则换名规则) ) tF(t,y,z)tF(t,y,z) wG(x,w,zwG(x,w,z) )( (换名规则换名规则) )或或 xF(x,xF(x,y y,z),z) yG(x,y,zyG(x,y,z) ) xF(x,t,z)xF(x,t,z) y yG(G(x x, ,y y,z,z) )( (代替规则代替规则) ) x xF(x,t,z)F(x,t,z) y yG(w,y,zG(w,y,z) )( (代替规则代替规则) )解答解答例例5

17、.15.1的解答的解答(2)(2) x(F(x,x(F(x,y y) ) yG(x,y,z)yG(x,y,z) x(F(x,t)x(F(x,t) yG(x,y,zyG(x,y,z)( (代替规则代替规则) )或或 x(F(x,y)x(F(x,y) y yG(x,y,zG(x,y,z) x(F(x,y)x(F(x,y) tG(x,t,ztG(x,t,z)( (换名规则换名规则) )解答解答例例5.25.2例例5.25.2 证明证明（1 1） x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(x) xB(x) （2 2） x(A(x)B(x) x(A(x)B(x) xA(x)

18、xA(x) xB(x)xB(x)其中其中A(x)A(x)，B(x)B(x)为含为含x x自由出现的公式。自由出现的公式。只要证明在某个解释下两边的式子不等值。只要证明在某个解释下两边的式子不等值。取解释取解释I I：个体域为自然数集合：个体域为自然数集合N N；(1)(1)取取F(xF(x) )：x x是奇数，代替是奇数，代替A(xA(x) )；取取G(xG(x) )：x x是偶数，代替是偶数，代替B(xB(x) )。则则 x(F(x)G(xx(F(x)G(x)为真命题，为真命题，而而 xF(xxF(x) xG(xxG(x) )为假命题。为假命题。两边不等值。两边不等值。证明证明例例5.25.

19、2(2)(2) x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x) ) x(F(x)G(xx(F(x)G(x)：有些：有些x x既是奇数又是偶数为假命题；既是奇数又是偶数为假命题；而而 xF(x)xF(x) xG(xxG(x) )：有些：有些x x是奇数并且有些是奇数并且有些x x是偶数为真是偶数为真命题。命题。 两边不等值。两边不等值。证明证明说明说明q 全称量词全称量词“ ”对对“”“”无分配律。无分配律。q 存在量词存在量词“ ”对对“”“”无分配律。无分配律。q 当当B(xB(x) )换成没有换成没有x x出现的出现的B B时，则有时，则有 x(A(x

20、)Bx(A(x)B) ) xA(x)BxA(x)B x(A(x)x(A(x)B B) ) xA(x)xA(x)B B例例5.35.3消去量词消去量词例例5.3 5.3 设个体域为设个体域为D Da,b,ca,b,c，将下面各公式的量词消去：，将下面各公式的量词消去： (2) (2) x(F(x) x(F(x) yG(y)yG(y)说明说明q 如果不用公式如果不用公式(5.3)(5.3)将量词的辖域缩小，演算过程较将量词的辖域缩小，演算过程较长。注意，此时长。注意，此时 yG(yyG(y) )是与是与x x无关的公式无关的公式B B。解答解答(2)(2) x(F(x) x(F(x) yG(yyG

21、(y) ) xF(x)xF(x) yG(yyG(y) ) ( (公式公式5.3) 5.3) ( (F(a)F(b)F(c)(G(a)G(b)G(cF(a)F(b)F(c)(G(a)G(b)G(c) ) 例例5.45.4例例5.45.4 给定解释给定解释I I如下：如下：（a a）个体域）个体域 D D2,32,3（b b）D D中特定元素中特定元素（c c）D D上的特定函数上的特定函数(x)(x)为：为：（d d）D D的特定谓词的特定谓词2 2a a 。，23(3)(2)f ff f。，为：0 0( (3 3, ,3 3) )1 1( (3 3, ,2 2) )( (2 2, ,3 3)

22、)( (2 2, ,2 2) )y y) )( (x x, ,G GG GG GG GG G。，为：01( (3 3, ,2 2) )( (2 2, ,3 3) )( (3 3, ,3 3) )( (2 2, ,2 2) )y y) )( (x x, ,L LL LL LL LL L。，为：10( (3 3) )( (2 2) )( (x x) )F FF FF F在解释在解释I I下求下列各式的值：下求下列各式的值：（1 1） x(F(x)G(x,ax(F(x)G(x,a) ) （2 2） x(F(f(x)G(x,f(xx(F(f(x)G(x,f(x)（3 3） x x yL(x,yyL(x

23、,y) ) （4 4） y y xL(x,yxL(x,y) )例例5.45.4的解答的解答（1 1） x(F(x)G(x,ax(F(x)G(x,a) (F(2)(F(2)G(2,2) G(2,2) (F(3)(F(3)G(3,2) G(3,2) (0(01) 1) (1(11)1) 0 0 （2 2） x(F(f(x)G(x,f(xx(F(f(x)G(x,f(x) (F(f(2)(F(f(2)G(2,f(2) G(2,f(2) (F(f(3)(F(f(3)G(3,f(3) G(3,f(3) (F(3)(F(3)G(2,3) G(2,3) (F(2)(F(2)G(3,2) G(3,2) (1(1

24、1) 1) (0(01)1) 1 1解答解答例例5.45.4的解答的解答（3 3） x x yL(x,yyL(x,y) ) (L(2,2)(L(2,2)L(2,3) L(2,3) (L(3,2)(L(3,2)L(3,3) L(3,3) (1(10) 0) (0(01) 1) 1 1（4 4） y y xL(x,yxL(x,y) ) y(L(2,y)y(L(2,y)L(3,y) L(3,y) (L(2,2)(L(2,2)L(3,2) L(3,2) (L(2,3)(L(2,3)L(3,3) L(3,3) (1(10) 0) (0(01)1) 0 0说明说明q 由由(3)(3)，(4)(4)的结果进

25、一步可以说明量词的次的结果进一步可以说明量词的次序不能随意颠倒。序不能随意颠倒。 例例5.55.5例例5.55.5 证明下列等值式。证明下列等值式。 （1 1） x(M(x)x(M(x)F(x) F(x) x(M(x)x(M(x)F(x) F(x) （2 2） x(F(x)x(F(x)G(x) G(x) x(F(x)x(F(x)G(x) G(x) （3 3） x x y(F(x)y(F(x)G(y)G(y)H(xH(x，y)y) x x y(F(x)y(F(x)G(y)G(y)H(x,y) H(x,y) （4 4） x x y(F(x)y(F(x)G(y)G(y)L(xL(x，y)y) x x

26、 y(F(x)y(F(x)G(y)G(y)L(x,y) L(x,y) 例例5.55.5的证明的证明（1 1） x(M(x)x(M(x)F(x) F(x) x(M(x)x(M(x)F(x)F(x) x(M(x)x(M(x)F(x)F(x) x x(M(x)(M(x)F(x)F(x) x(x(M(x)M(x)F(x)F(x) x(M(x)x(M(x)F(x) F(x) （2 2） x(F(x)x(F(x)G(x) G(x) x(F(x)x(F(x)G(x)G(x) x(F(x)x(F(x)G(x)G(x) x x(F(x)(F(x)G(x)G(x) x x( (F(x)G(x)F(x)G(x) x

27、(F(x)x(F(x)G(x) G(x) 证明证明例例5.55.5的证明的证明（3 3） x x y(F(x)y(F(x)G(y)G(y)H(xH(x，y)y) x x y(F(x)y(F(x)G(y)G(y)H(x,y)H(x,y) x x y y( (F(x)F(x)G(y)G(y)H(xH(x，y)y) ) xx( (y y( (F(x)F(x)G(y)G(y)H(xH(x，y)y) ) ) x x y y( (F(x)F(x)G(y)H(xG(y)H(x，y)y) ) x x y(F(x)y(F(x)G(y)G(y)H(x,y) H(x,y) 例例5.55.5的证明的证明（4 4） x

28、 x y(F(x)y(F(x)G(y)G(y)L(xL(x，y)y) x x y(F(x)y(F(x)G(y)G(y)L(x,y)L(x,y) x x y(F(x)y(F(x)G(y)G(y)L(xL(x，y)y) x x ( y(F(x)y(F(x)G(y)G(y)L(xL(x，y)y) x x y y(F(x)(F(x)G(y)G(y)L(xL(x，y)y) x x y(y(F(x)G(y)F(x)G(y)L(x,y) L(x,y) x x y(F(x)y(F(x)G(y)G(y)L(x,y) L(x,y) 作业作业习题五习题五2(1)2(1)、5 5（1 1）（）（2 2）复习复习设个体

29、域为有限集设个体域为有限集D=aD=a1 1,a,a2 2, ,a,an n,则有则有（1 1） xA(x) xA(x) A(aA(a1 1) )A(aA(a2 2) )A(aA(an n) ) （2 2） xA(x) xA(x) A(aA(a1 1) )A(aA(a2 2) )A(aA(an n) ) （5.15.1）消去量词等值式消去量词等值式量词否定等值式量词否定等值式设设A(x)A(x)是任意的含自由出现个体变项是任意的含自由出现个体变项x x的公式，则的公式，则（1 1） xA(x) xA(x) xA(x)xA(x)（2 2） xA(x) xA(x) xA(x)xA(x)说明说明q

30、“并不是所有的并不是所有的x x都有性质都有性质A”A”与与“存在存在x x没有没有性质性质A”A”是一回事。是一回事。q ”不存在有性质不存在有性质A A的的x”x”与与”所有所有X X都没有性质都没有性质A”A”是一回事。是一回事。（5.25.2）量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式设设A(x)A(x)是任意的含自由出现个体变项是任意的含自由出现个体变项x x的公式，的公式，B B中不含中不含x x的出现的出现，则，则（1 1） x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(A(x)x(A(x)B) B) xA(x)xA(x)B B x(A(x)B) x(A

31、(x)B) xA(x)BxA(x)B x(BA(x) x(BA(x) B B xA(x)xA(x)（2 2） x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(A(x)x(A(x)B) B) xA(x)xA(x)B B x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(BA(x) x(BA(x) B B xA(x)xA(x)（5.35.3）（5.45.4）量词分配等值式量词分配等值式设设A(x)A(x)，B(x)B(x)是任意的含自由出现个体变项是任意的含自由出现个体变项x x的公式，则的公式，则（1 1） x(A(x)x(A(x)B(x) B(x) xA(x)

32、xA(x) xB(x)xB(x)（2 2） x(A(x)B(x) x(A(x)B(x) xA(x) xA(x) xB(x)xB(x)（5.55.5）一阶逻辑等值演算的三条原则一阶逻辑等值演算的三条原则q 置换规则置换规则：设：设(A)(A)是含公式是含公式A A的公式，的公式，(B)(B)是用公式是用公式B B取代取代(A)(A)中所有的中所有的A A之后的公式，若之后的公式，若A AB B，则，则(A)(A)(B)(B)。 q 换名规则换名规则：设设A A为一公式，将为一公式，将A A中某量词辖域中某中某量词辖域中某约束约束变项的变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的所有

33、出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为某个体变项符号，公式的其余部分不变，设所得公式为AA，则则AAA A。q 代替规则代替规则：设设A A为一公式，将为一公式，将A A中某个中某个自由自由出现的个体变项的出现的个体变项的所有出现用所有出现用A A中未曾出现过的个体变项符号代替，中未曾出现过的个体变项符号代替，A A中其余部中其余部分不变，设所得公式为分不变，设所得公式为AA，则，则AAA A。5.2 5.2 一阶逻辑前束范式一阶逻辑前束范式定义定义5.25.2 设设A A为一个一阶逻辑公式，若为一个一阶逻辑公式，若A A具有如下形式具

34、有如下形式Q Q1 1x x1 1Q Q2 2x x2 2 Q Qk kx xk kB B则称则称A A为为前束范式前束范式，其中，其中Q Qi i(1ik)(1ik)为为 或或 ，B B为不含量词为不含量词的公式。的公式。q 前束范式的例子：前束范式的例子： x x y(F(x)G(y)H(xy(F(x)G(y)H(x，y) y) x x y y z(F(x)G(y)H(z)L(xz(F(x)G(y)H(z)L(x，y y，z) z) q 不是前束范式的例子：不是前束范式的例子： x x( (F(x)F(x) y y(G(y)H(x(G(y)H(x，y)y) ) x x( (F(x)F(x)

35、 y y(G(y)H(x(G(y)H(x，y)y) )例例: :以下公式哪些是前束范式？以下公式哪些是前束范式？ （1 1） xF(x)xF(x) x xG(G(x x) )（2 2） x(F(x)x(F(x) y G(y) y G(y) （3 3） x x y(F(x)G(y) y(F(x)G(y) （4 4） y y x(F(x)G(y)x(F(x)G(y) 解：（解：（1 1）F F（2 2）F F（3 3）T T（4 4）T T前束范式存在定理前束范式存在定理定理定理5.1 5.1 一阶逻辑中的任何公式都存在与之等值的前束范式。一阶逻辑中的任何公式都存在与之等值的前束范式。求前束范式一

36、般过程求前束范式一般过程(1)(1)利用量词转化公式，把否定转入到指导变元的后面。利用量词转化公式，把否定转入到指导变元的后面。 xA(xxA(x) ) xA(xxA(x) ) xA(xxA(x) ) xA(xxA(x) )(2)(2)利用利用量词辖域收缩与扩张等值式，如量词辖域收缩与扩张等值式，如 B B xA(xxA(x) ) x(A(x)Bx(A(x)B) ) xA(x)xA(x)B B x(A(x)x(A(x)B B) ) 把量词移到全式的最前面，这样便得到前束范式。把量词移到全式的最前面，这样便得到前束范式。 例例5.6 5.6 求公式的前束范式求公式的前束范式（1 1） xF(x)

37、xF(x) x xG(G(x x) )（2 2） xF(x)xF(x) xG(x)xG(x)例例5.6 5.6 求公式的前束范式求公式的前束范式（1 1） xF(x)xF(x) x xG(G(x x) )法一法一 xF(x)xF(x) x xG(G(x x) ) xF(x)xF(x) yG(y) yG(y) ( (换名规则换名规则) ) xF(x)xF(x) yG(y) yG(y) (5.2)(5.2)第二式第二式) ) x(F(x)x(F(x) yG(y) yG(y) (5.3)(5.3)第二式第二式) ) x x y(F(x)G(y) y(F(x)G(y) (5.3)(5.3)第二式第二式

38、) ) 法二法二 xF(x)xF(x) xG(x) xG(x) xF(x)xF(x) xG(x)xG(x) (5.2)(5.2)第二式第二式) ) x(F(x)G(x) x(F(x)G(x) (5.5)(5.5)第一式第一式) ) 例例5.6 5.6 求公式的前束范式求公式的前束范式（2 2） xF(x)xF(x) xG(x)xG(x) xF(x)xF(x) xG(xG(x x) ) (5.2)(5.2)第二式第二式) ) xF(x)xF(x) yG(y) yG(y) ( (换名规则换名规则) ) x(F(x)x(F(x) yG(y) yG(y) (5.3)(5.3)第一式第一式) ) x x

39、 y(F(x)G(y) y(F(x)G(y) (5.3)(5.3)第一式第一式) ) 说明说明q 求前束范式的过程，就是制造量词辖域可以扩大的求前束范式的过程，就是制造量词辖域可以扩大的条件，进行量词辖域扩大。条件，进行量词辖域扩大。q 任何公式的前束范式都是存在的，但一般说来，并任何公式的前束范式都是存在的，但一般说来，并不唯一。不唯一。q 利用一阶逻辑等值式以及三条变换规则（置换规则利用一阶逻辑等值式以及三条变换规则（置换规则、换名规则、代替规则）就可以求出与公式等值的、换名规则、代替规则）就可以求出与公式等值的前束范式，或所谓公式的前束范式。前束范式，或所谓公式的前束范式。例例5.8 5

40、.8 求公式的前束范式求公式的前束范式(1)(1) xF(xF(x,x,y)y) yG(x,yG(x,y y) ) (2)(2)( x x1 1F(F(x x1 1,x,x2 2) ) x x2 2G(G(x x2 2) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) 例例5.8 5.8 求公式的前束范式求公式的前束范式(1)(1) xF(xF(x,x,y)y) yG(x,yG(x,y y) ) tF(t,y)tF(t,y) wG(x,w) (wG(x,w) (换名规则换名规则) ) t t w(F(t,y)G(x,w) (5.3),(5.4) w(F(t,y)G(x,w

41、) (5.3),(5.4) 或者或者 xF(x,xF(x,y y) yG(yG(x x,y) ,y) xF(x,t)xF(x,t) yG(w,y) (yG(w,y) (代替规则代替规则) ) x x y(F(x,t)G(w,y) (5.3),(5.4)y(F(x,t)G(w,y) (5.3),(5.4)说明说明q 解本题时一定注意，哪些个体变项是约束出现解本题时一定注意，哪些个体变项是约束出现，哪些是自由出现，特别要注意那些既是约束，哪些是自由出现，特别要注意那些既是约束出现又是自由出现的个体变项。不能混淆出现又是自由出现的个体变项。不能混淆。例例5.8 5.8 求公式的前束范式求公式的前束范

42、式(2)(2)( x x1 1F(F(x x1 1,x,x2 2) ) x x2 2G(G(x x2 2) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) ( ( x x4 4F(F(x x4 4,x,x2 2) ) x x5 5G(G(x x5 5) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) x x4 4 x x5 5(F(F(x x4 4,x,x2 2) ) G(G(x x5 5) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) x x4 4 x x5 5 x x1 1( ( (F(F(x x4 4,x,x2 2) )

43、 G(G(x x5 5) ) ) H(xH(x1 1,x,x2 2,x,x3 3) ) ) 5.3 5.3 一阶逻辑的推理理论一阶逻辑的推理理论q 在一阶逻辑中，从前提在一阶逻辑中，从前提A A1 1,A,A2 2, ,A Ak k出发推结论出发推结论B B的推理形式结的推理形式结构，依然采用如下的蕴涵式形式构，依然采用如下的蕴涵式形式A A1 1 A A2 2 A Ak k B B （5.65.6）若式（若式（5.65.6）为永真式，则称）为永真式，则称推理正确推理正确，否则称推理不正确。，否则称推理不正确。q 于是，在一阶逻辑中判断推理是否正确也归结为判断（于是，在一阶逻辑中判断推理是否正

44、确也归结为判断（5.65.6）式是否为永真式了。式是否为永真式了。q 在一阶逻辑中称永真式的蕴涵式为在一阶逻辑中称永真式的蕴涵式为推理定律推理定律，q 在一阶逻辑的推理中，在一阶逻辑的推理中，某些前提与结论可能是受量词限制，某些前提与结论可能是受量词限制，为了使用命题逻辑中的为了使用命题逻辑中的等值式和推理定律等值式和推理定律，必须在推理过程必须在推理过程中有消去和添加量词的规则中有消去和添加量词的规则，以便使谓词公式的推理过程可，以便使谓词公式的推理过程可类似于命题演算中推理理论那样进行。类似于命题演算中推理理论那样进行。定义定义5.3 5.3 自然推理系统自然推理系统N N定义定义1.1.

45、字母表。同一阶语言的字母表。字母表。同一阶语言的字母表。2.2.合式公式。同合式公式的定义。合式公式。同合式公式的定义。3.3.推理规则。推理规则。一阶语言中的字母表一阶语言中的字母表定义定义4.14.1 一阶语言一阶语言L L的的字母表字母表定义如下定义如下: :(1)(1)个体常项：个体常项：a , b , c , , ai , bi , ci , , i 1(2)(2)个体变项：个体变项：x , y , z, , xi , yi , zi , , i 1 (3)(3)函数符号：函数符号：f , g , h , , fi , gi , hi , , i 1(4)(4)谓词符号：谓词符号：F

46、 , G , H , , Fi , Gi , Hi , , i 1(5)(5)量词符号量词符号: : ， (6)(6)联结词符号联结词符号:, :, (7)(7)括号与逗号括号与逗号:(,),:(,),，定义定义4.3 设设R(x1,x2,xn)是一阶语言是一阶语言L L中的中的n元谓词符号元谓词符号。t1,t2,tn 是是L L 的的n个个项项，则称，则称 R(t1,t2,tn )是是L L 的的原子公式原子公式。例如例如 一元谓词一元谓词F(x)，G(y)；二元谓词二元谓词H(x,y)，L(x,y)都是原子公式都是原子公式合式公式合式公式定义定义4.4 一阶语言一阶语言L L 中的中的合式

47、公式合式公式 (也称为谓词公式或公式也称为谓词公式或公式) 定义如下：定义如下：(1) 原子公式是合式公式；原子公式是合式公式；(2) 若若A是合式公式，则是合式公式，则 (A)也是合式公式；也是合式公式；(3) 若若A, B 是合式公式，则是合式公式，则(AB), (AB), (AB), (AB)也是合也是合式公式；式公式；(4) 若若A是合式公式，则是合式公式，则 xA, xA也是合式公式；也是合式公式；(5) 只有有限次应用只有有限次应用 (1)(4) 构成的符号串才是合式公式。构成的符号串才是合式公式。例如例如 x(F(x,y)G(x,z)、x(F(x)G(y)y(H(x)L(x,y,

48、z) 推理规则的来源推理规则的来源q 命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例q 由基本等值式生成的推理规则由基本等值式生成的推理规则q 量词分配等值式量词分配等值式q 推理规则推理规则量词消去和引入规则量词消去和引入规则命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例q xF(x)xF(x) yG(y) yG(y) xF(x)xF(x)（化简律的代换实例）（化简律的代换实例）q xF(x) xF(x) xF(x) xF(x) yG(y) yG(y) （附加律的代换实例）（附加律的代换实例）q xF(x) xF(x) xF(x) xF(x) （双重否定律的代换实例） xF(x)

49、 xF(x) xF(x)xF(x)由基本等值式生成的推理定律由基本等值式生成的推理定律q xF(x) xF(x) xF(x)xF(x)q xF(x) xF(x) xF(x) xF(x) q 其他推理规则其他推理规则q xA(x)xA(x) xB(x) xB(x) x(A(x)B(x) x(A(x)B(x) q x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(x)xB(x) q x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(x) xB(x) q x(A(x)B(x) x(A(x)B(x) xA(x) xA(x) xB(x) xB(x) q 对对

50、x(A(x)B(xx(A(x)B(x) ) xA(x)xA(x) xB(xxB(x) )的讨论的讨论若若 x(A(x)B(xx(A(x)B(x)为真，则有一个客体为真，则有一个客体c c，使得，使得A(c)B(cA(c)B(c) )为真，即为真，即A(cA(c) )和和B(cB(c) )都为真，所以都为真，所以 xA(x)xA(x) xB(xxB(x) )也为真。也为真。 量词消去和引入规则量词消去和引入规则q 为了构造推理系统，还要给出为了构造推理系统，还要给出4 4条重要的推理规则条重要的推理规则, ,即消去量词和引入量词的规则：即消去量词和引入量词的规则：1 1全称量词消去规则全称量词消

51、去规则( (简记为简记为UIUI规则或规则或-规则规则) )2 2全称量词引入规则全称量词引入规则( (简记为简记为UGUG规则规则+规则规则) )3 3存在量词消去规则存在量词消去规则( (简记为简记为EIEI规则规则-规则规则) ) 4 4存在量词引入规则存在量词引入规则( (简称简称EGEG规则规则+规则规则) )全称量词消去规则全称量词消去规则( (简记为简记为UIUI规则或规则或-) )含义含义：如果个体域的所有元素都具有性质：如果个体域的所有元素都具有性质A A，则个体域中的任，则个体域中的任一元素具有性质一元素具有性质A A。 两式成立的条件两式成立的条件： (1)(1)在第一式

52、中，当在第一式中，当A(x)A(x)不是原子公式时，不是原子公式时，y y不在不在A(x)A(x)中约束中约束出现出现, ,或或x x应为不在应为不在A(y)A(y)中自由出现的个体变项。中自由出现的个体变项。 (2)(2)在第二式中，在第二式中，c c为任意个体常项。为任意个体常项。 (3)(3)用用y y或或c c去取代去取代A(x)A(x)中自由出现的中自由出现的x x时，一定要在时，一定要在x x自由出现自由出现的一切地方进行取代。的一切地方进行取代。 A A( (c c) )x xA A( (x x) )或或A A( (y y) )x xA A( (x x) )1 1 全称量词消去规

53、则全称量词消去规则( (简记为简记为UIUI规则或规则或UI)UI)举例举例当当A(xA(x) )为原子公式时，比如为原子公式时，比如A(xA(x)=)=F(xF(x) )，则当，则当 xA(xxA(x) )为为真时，对于个体域中任意的个体变项真时，对于个体域中任意的个体变项y y，不会出现，不会出现F(yF(y) )为为假的情况。假的情况。当当A(xA(x) )不是原子公式时，如不是原子公式时，如y y已在已在A(xA(x) )中约束出现了，就中约束出现了，就不能用不能用y y取代取代x x，否则会出现，否则会出现 xA(xxA(x) )为真而为真而A(yA(y) )为假的情为假的情况。况。

54、考虑个体域为实数集合，公式考虑个体域为实数集合，公式A(xA(x)=)= yF(x,yyF(x,y) )为为xyxy。当对公式当对公式 xA(xxA(x)=)= x x yF(x,yyF(x,y) )使用使用UIUI规则时，用规则时，用y y取代取代x x，就会得到，就会得到A(yA(y)=)= yF(y,yyF(y,y) )，即，即 y(yy(yy)y)，这显然是假命，这显然是假命题。原因是违背了条件题。原因是违背了条件(1)(1)。若用若用z z取代取代x x，得，得A(zA(z)=)= yF(z,yyF(z,y)=)= y(zy(zy)y)就不会产生这就不会产生这种错误。种错误。2 2

55、全称量词引入规则全称量词引入规则( (简记为简记为UGUG规则或规则或+) )该式成立的条件是：该式成立的条件是： （1 1）x x不能在前提任何公式中自由出现。不能在前提任何公式中自由出现。x xA A( (x x) )A A( (x x) )含义含义：如果个体域中的任一元素：如果个体域中的任一元素具有性质具有性质A，则个体域的所有元素，则个体域的所有元素都具有性质都具有性质A。 例例 设个体域设个体域I I为整数集合，为整数集合，P P(x)(x)：x x为偶数，为偶数，Q Q（x x）x x被被2 2整除整除。指出在推理系统中，以。指出在推理系统中，以P P(x)(x)Q Q（x x）(

56、 (真命题真命题) )，P P(x)(x)为前为前提，推出提，推出 x xQ Q(x)(x)(假命题假命题) )的下述推理证明中的错误。的下述推理证明中的错误。 P P(x)(x)Q Q（x x） 前提引入前提引入 P P（x x） 前提引入前提引入 Q Q（x x） 假言推理假言推理 x xQ Q(x) (x) +规则规则 解解 在以上推理证明中，第四步错了，由于在以上推理证明中，第四步错了，由于x x在在前提公式前提公式中中自由自由出现出现，用了，用了+规则，导致了从真命题推出假命题的错误。规则，导致了从真命题推出假命题的错误。3 3 存在量词消去规则存在量词消去规则( (简记为简记为EI

57、EI规则或规则或-) ) 该式成立的条件是：该式成立的条件是： (1)c(1)c是使是使A A为真的为真的特定特定的个体常项。的个体常项。 (2)x(2)x不在前提中自由出现。不在前提中自由出现。(3) (3) A(x)不含其它自由出现的个体变项。自由出现的个体变项。 A A( (c c) )x xA A( (x x) )举例举例取个体域为自然数集合，取个体域为自然数集合，F(xF(x) )为为x x是奇数，是奇数，G(xG(x) )为为x x是偶数是偶数。 xF(xxF(x) )与与 xG(xxG(x) )都是真命题，则对于某些都是真命题，则对于某些c c和和d d，可以断，可以断定定F(c

58、)G(dF(c)G(d) )必定为真，但不能断定必定为真，但不能断定F(c)G(cF(c)G(c) )是真。是真。 对对 xF(xxF(x) )使用使用 - -规则时，取代规则时，取代x x的的c c一定是特定的个体常项一定是特定的个体常项1,3,51,3,5等奇数。等奇数。对对 xG(xxG(x) )使用使用 - -规则时，取代规则时，取代x x的的c c一定是特定的个体常项一定是特定的个体常项2,4,62,4,6等偶数。等偶数。B BA(x)A(x)B BA(x)A(x)x例例例例 设个体域为实数集合，设个体域为实数集合，F(x,y)F(x,y)为为xyxy。指出在推理系统中，。指出在推理

59、系统中，以以 x x yF(xyF(x，y)(y)(真命题真命题) )为前提，推出为前提，推出 xF(x,c)(xF(x,c)(假命题假命题) )的的下述推理证明中的错误。下述推理证明中的错误。 x x yF(x,y) yF(x,y) 前提引入前提引入 yF(z,y) yF(z,y) UIUI规则规则 F(z,c) F(z,c) EIEI规则规则 xF(x,c) xF(x,c) UGUG规则规则 解解 由于由于c c为特定的个体常项，所以为特定的个体常项，所以 xF(x,c)(xF(x,c)(即为即为 x(xc)x(xc)为为假命题。如果按推理规则进行推理，不会从真命题推出假命假命题。如果按推

60、理规则进行推理，不会从真命题推出假命题。题。在以上推理证明中，第三步错了，由于在以上推理证明中，第三步错了，由于F(z,y)F(z,y)中有自由出现中有自由出现的的z z，按，按EIEI规则应该满足的条件规则应该满足的条件(3)(3)，此处不能用，此处不能用EIEI规则。用规则。用了了EIEI规则，导致了从真命题推出假命题的错误。规则，导致了从真命题推出假命题的错误。4 4 存在量词引入规则存在量词引入规则( (简称简称EGEG规则或规则或+) ) 该式成立的条件是：该式成立的条件是： (1)c(1)c是特定的个体常项。是特定的个体常项。(2)(2)取代取代c c的的x x不能在不能在A(c)