一阶逻辑等值演算与推理

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

2、.1 5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则 q 在一阶逻辑中，有些命题可以有不同的符号化形式。在一阶逻辑中，有些命题可以有不同的符号化形式。 q 例如：没有不犯错误的人例如：没有不犯错误的人 令令 M(x):xM(x):x是人。是人。 F(x):xF(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)是等值的。是等值的。 5 等值式的定义等值式的定义 定义定义5.

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

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

5、xF(x) xF(x)xF(x)（双重否定律）（双重否定律） (2)F(x)G(y) (2)F(x)G(y) F(x)G(y) F(x)G(y) （蕴涵等值式）（蕴涵等值式） (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) （蕴涵等值式）（蕴涵等值式） 8 消去量词等值式消去量词等值式 设个体域为有限集设个体域为有限集D=aD=a1 1,a,a2 2, ,a,an n,则有则有 （1 1） xA(x) xA(x) A(aA(a1 1)A(a)A(a2 2)A(aA(an n) ) （2 2） xA(

6、x) xA(x) A(aA(a1 1)A(a)A(a2 2)A(aA(an n) ) （5.15.1） 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”是一回事。是一回事。

7、 （5.25.2） 10 量词否定等值式(举例) q N N n ( nN n ( nN |a |an n-a|-a|N n ( nN |a |an n-a|-a|N n ( nN |a |an n-a|-a|N n ( nN |a |an n-a|-a|N ( nN |a |an n-a|-a|NnN |a |an n-a|-a|N n ( nN |a|an n-a|-a|N n ( nN |a|an n-a|-a| ) ) aa n n lim aa n n lim 12 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 设设A(x)A(x)是任意的含自由出现个体变项是任意的含自由出现个体

8、变项x x的公式，的公式，B B中不含中不含x x 的出现，则的出现，则 （1 1） x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(A(x)B) x(A(x)B) xA(x)BxA(x)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)B) x(A(x)B) xA(x)BxA(x)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.

9、35.3） （5.45.4） 13 量词辖域收缩与扩张(、续) q x(A(x)x(A(x)B) B) xA(x)xA(x)B B 证明证明: : x(A(x)x(A(x)B) B) x(x( A(x)A(x)B) B) x x A(x)A(x)B B xA(x)xA(x)B B xA(x)xA(x)B B q x(Bx(BA(x) A(x) B B xA(x) xA(x) 证明证明: : x(Bx(BA(x)A(x) x(x( B BA(x)A(x) ) B B x xA(x)A(x) B B x xA(x) A(x) B B xA(x)xA(x) 14 量词辖域收缩与扩张(、续) q x(

10、A(x)x(A(x)B) B) xA(x)xA(x)B B 证明证明: : x(A(x)x(A(x)B)B) x(x( A(x)A(x)B) B) x x A(x)A(x)B B xA(x)xA(x)B B xA(x)xA(x)B B q x(Bx(BA(x) A(x) B B xA(x)xA(x) 证明证明: : x(Bx(BA(x) A(x) x(x( B BA(x)A(x) ) B B x xA(x)A(x) B B x xA(x) A(x) B B xA(x)xA(x) 15 量词分配等值式量词分配等值式 设设A(x)A(x)，B(x)B(x)是任意的含自由出现个体变项是任意的含自由出

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

12、x)xB(x) x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(x)xB(x) x(A(x)B(x) x(A(x)B(x) ( xA(x)xA(x) xB(x)xB(x) x(A(x)B(x) x(A(x)B(x) xA(x) xA(x) xB(x)xB(x) 16 q 量词分配等值式量词分配等值式 x(A(x) B(x) xA(x)xB(x) x(A(x) B(x) xA(x)xB(x) q 注意注意: 对对 无分配律无分配律, 对对 无分配律无分配律 17 量词分配(反例) q x(A(x)x(A(x)B(x) B(x) xA(x)xA(x) xB(x)xB(x)

13、q x(A(x)x(A(x)B(x) B(x) xA(x)xA(x) xB(x)xB(x) 个体域为全体自然数个体域为全体自然数; A(x): x; A(x): x是偶数是偶数 B(x): xB(x): x是奇数是奇数; ; 左左1, 1, 右右0 0 q x(A(x)x(A(x)B(x) B(x) xA(x)xA(x) xB(x)xB(x) q x(A(x)x(A(x)B(x) B(x) xA(x)xA(x) xB(x)xB(x) 个体域为全体自然数个体域为全体自然数; A(x): x; A(x): x是偶数是偶数 B(x): xB(x): x是奇数是奇数; ; 左左0, 0, 右右1 1

14、18 量词的次序 q x x yA(x, y) yA(x, y) y y x A(x, y)x A(x, y) q x x yA(x, y) yA(x, y) y y x A(x, y)x A(x, y) q y y xA(x, y) xA(x, y) x x y A(x, y) y A(x, y) q x x yA(x, y) yA(x, y) y y x A(x, y) x A(x, y) q x x yA(x, y) yA(x, y) y y x A(x, y) x A(x, y) 相邻的同名量词的次序无关紧要相邻的同名量词的次序无关紧要, , 不同名量词的次不同名量词的次 序是不可随意

15、变更的序是不可随意变更的 19 一阶逻辑等值演算的三条原则一阶逻辑等值演算的三条原则 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中某量词辖域中某约束变项的中某量词辖域中某约束变项的 所有出现及相应的指导变元改成该量词辖域中未曾出现过的所有出现及相应的指导变元改成该量词辖域中未曾出现过的 某个体变项符号，公式的其余部分不变，设所得公式为某个体变项

16、符号，公式的其余部分不变，设所得公式为AA， 则则AAA A。 q 代替规则：代替规则：设设A A为一公式，将为一公式，将A A中某个自由出现的个体变项的中某个自由出现的个体变项的 所有出现用所有出现用A A中未曾出现过的个体变项符号代替，中未曾出现过的个体变项符号代替，A A中其余部中其余部 分不变，设所得公式为分不变，设所得公式为AA，则，则AAA A。 q 一阶逻辑中的置换规则与命题逻辑中的置换一阶逻辑中的置换规则与命题逻辑中的置换 规则形式上完全相同，只是在这里规则形式上完全相同，只是在这里A A，B B是一是一 阶逻辑公式。阶逻辑公式。 20 例例5.15.1 例例5.1 5.1 将

17、下面公式化成与之等值的公式，使其没有既是约束将下面公式化成与之等值的公式，使其没有既是约束 出现又是自由出现的个体变项。出现又是自由出现的个体变项。 (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) xF(x,y,z) xF(x,y,z) yG(x,y,z)yG(x,y,z) tF(t,y,z)tF(t,y,z) yG(x,y,z)yG(x,y,z)( (换名规则换名规则) ) tF(t,y,z)tF(t,y,z) wG(x,w,z)wG(x,w,z)(

18、(换名规则换名规则) ) 或或 xF(x,y,z)xF(x,y,z) yG(x,y,z)yG(x,y,z) xF(x,t,z)xF(x,t,z) yG(x,y,z)yG(x,y,z)( (代替规则代替规则) ) x xF(x,t,z)F(x,t,z) y yG(w,y,z)G(w,y,z)( (代替规则代替规则) ) 解答解答 21 例例5.15.1的解答的解答 (2)(2) x(F(x,y)x(F(x,y) yG(x,y,z)yG(x,y,z) x(F(x,t)x(F(x,t) yG(x,y,z)yG(x,y,z)( (代替规则代替规则) ) 或或 x(F(x,y)x(F(x,y) yG(x

19、,y,z)yG(x,y,z) x(F(x,y)x(F(x,y) tG(x,t,z)tG(x,t,z)( (换名规则换名规则) ) 解答解答 22 例例5.25.2 例例5.2 5.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)xA(x) xB(x)xB(x) 其中其中A(x)A(x)，B(x)B(x)为含为含x x自由出现的公式。自由出现的公式。 只要证明在某个解释下两边的式子不等值。只要证明在某个解释下两边的式子不等值。 取解释取解释I I：个体域为自然数集

20、合：个体域为自然数集合N N； (1)(1)取取F(x)F(x)：x x是奇数，代替是奇数，代替A(x)A(x)； 取取G(x)G(x)：x x是偶数，代替是偶数，代替B(x)B(x)。 则则 x(F(x)G(x)x(F(x)G(x)为真命题，为真命题， 而而 xF(x)xF(x) xG(x) xG(x)为假命题。为假命题。 两边不等值。两边不等值。 证明证明 23 例例5.25.2 (2)(2) x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(x)xB(x) x(F(x)G(x)x(F(x)G(x)：有些：有些x x既是奇数又是偶数为假命题；既是奇数又是偶数为假命题；

21、 而而 xF(x)xF(x) xG(x)xG(x)：有些：有些x x是奇数并且有些是奇数并且有些x x是偶数为真是偶数为真 命题。命题。 两边不等值。两边不等值。 证明证明 q 全称量词全称量词“ ”对对“”无分配律。无分配律。 q 存在量词存在量词“ ”对对“”无分配律。无分配律。 q 当当B(x)B(x)换成没有换成没有x x出现的出现的B B时，则有时，则有 x(A(x)B) x(A(x)B) xA(x)BxA(x)B x(A(x)B) x(A(x)B) xA(x)BxA(x)B 24 例例5.35.3消去量词消去量词 例例5.3 5.3 设个体域为设个体域为D Da,b,ca,b,c，

22、将下面各公式的量词消去：，将下面各公式的量词消去： (1) (1) x(F(x)G(x)x(F(x)G(x) (2) (2) x(F(x) x(F(x) yG(y)yG(y) (3) (3) x x yF(x,y)yF(x,y) q 如果不用公式如果不用公式(5.3)(5.3)将量词的辖域缩小，演算过程较将量词的辖域缩小，演算过程较 长。注意，此时长。注意，此时 yG(y)yG(y)是与是与x x无关的公式无关的公式B B。 解答解答(1)(1) 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

23、)G(c) (2)(2) x(F(x) x(F(x) yG(y) yG(y) xF(x)xF(x) yG(y) yG(y) ( (公式公式5.3) 5.3) (F(a)F(b)F(c)(G(a)G(b)G(c) (F(a)F(b)F(c)(G(a)G(b)G(c) 25 例例5.35.3消去量词消去量词 (3) (3) 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 )

24、) ( 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(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

25、,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) 26 例例5.45.4 例例5.4 5.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) )( (2 2, ,2 2) )y y) )( (x x, ,G G

26、G 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,a) x(F(x)G(x,a) （2 2） x(F(f(x)G(x,f(x)x(F(f(x)G(x,f(x) （3 3） x x yL(x,y) yL(x,y) （4 4） y y xL(x,y)xL(x,

27、y) 27 例例5.45.4的解答的解答 （1 1） x(F(x)G(x,a)x(F(x)G(x,a) (F(2)G(2,2) (F(3)G(3,2) (F(2)G(2,2) (F(3)G(3,2) (01) (11)(01) (11) 0 0 （2 2） x(F(f(x)G(x,f(x)x(F(f(x)G(x,f(x) (F(f(2)G(2,f(2) (F(f(3)G(3,f(3) (F(f(2)G(2,f(2) (F(f(3)G(3,f(3) (F(3)G(2,3) (F(2)G(3,2) (F(3)G(2,3) (F(2)G(3,2) (11) (01)(11) (01) 1 1 28

28、例例5.45.4的解答的解答 （3 3） x x yL(x,y)yL(x,y) (L(2,2)L(2,3) (L(3,2)L(3,3) (L(2,2)L(2,3) (L(3,2)L(3,3) (10) (01) (10) (01) 1 1 （4 4） y y xL(x,y)xL(x,y) y(L(2,y)L(3,y) y(L(2,y)L(3,y) (L(2,2)L(3,2) (L(2,3)L(3,3) (L(2,2)L(3,2) (L(2,3)L(3,3) (10) (01)(10) (01) 0 0 q 由由(3)(3)，(4)(4)的结果进一步可以说明量词的次的结果进一步可以说明量词的次

29、序不能随意颠倒。序不能随意颠倒。 29 例例5.55.5 例例5.5 5.5 证明下列等值式。证明下列等值式。 （1 1） x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) （2 2） x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) （3 3） x x y(F(x)G(y)H(xy(F(x)G(y)H(x，y)y) x x y(F(x)G(y)H(x,y) y(F(x)G(y)H(x,y) （4 4） x x y(F(x)G(y)L(xy(F(x)G(y)L(x，y)y) x x y(F(x)G(y)L(x,y) y

30、(F(x)G(y)L(x,y) 30 例例5.55.5的证明的证明 （1 1） x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) x(M(x)F(x)x(M(x)F(x) x(M(x)F(x)x(M(x)F(x) x(M(x)F(x)x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) （2 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)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) x(F(x)G(x) x(F(x)G

31、(x) 31 例例5.55.5的证明的证明 （3 3） x x y(F(x)G(y)H(xy(F(x)G(y)H(x，y)y) x x y(F(x)G(y)H(x,y) y(F(x)G(y)H(x,y) x x y(F(x)G(y)H(xy(F(x)G(y)H(x，y)y) x(x(y(F(x)G(y)H(xy(F(x)G(y)H(x，y)y) x x y(F(x)G(y)H(xy(F(x)G(y)H(x，y)y) x x y(F(x)G(y)H(x,y) y(F(x)G(y)H(x,y) 32 例例5.55.5的证明的证明 （4 4） x x y(F(x)G(y)L(xy(F(x)G(y)L

32、(x，y)y) x x y(F(x)G(y)L(x,y) y(F(x)G(y)L(x,y) x x y(F(x)G(y)L(xy(F(x)G(y)L(x，y)y) x x ( y(F(x)G(y)L(xy(F(x)G(y)L(x，y)y) x x y(F(x)G(y)L(xy(F(x)G(y)L(x，y)y) x x y(F(x)G(y)L(x,y) y(F(x)G(y)L(x,y) x x y(F(x)G(y)L(x,y) y(F(x)G(y)L(x,y) 33 5.2 5.2 一阶逻辑前束范式一阶逻辑前束范式 定义定义5.2 5.2 设设A A为一个一阶逻辑公式，若为一个一阶逻辑公式，若A

33、 A具有如下形式具有如下形式 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(F(x)x(F(x) y(G(y)H(xy(G(y)H(x，y) y) x(F(x

34、)x(F(x) y(G(y)H(xy(G(y)H(x，y)y) 34 前束范式存在定理前束范式存在定理 定理定理5.1 5.1 一阶逻辑中的任何公式都存在与之等值的前束范式。一阶逻辑中的任何公式都存在与之等值的前束范式。 q 求前束范式的过程，就是制造量词辖域可以扩大的求前束范式的过程，就是制造量词辖域可以扩大的 条件，进行量词辖域扩大。条件，进行量词辖域扩大。 q 任何公式的前束范式都是存在的，但一般说来，并任何公式的前束范式都是存在的，但一般说来，并 不唯一。不唯一。 q 利用一阶逻辑等值式以及三条变换规则（置换规则利用一阶逻辑等值式以及三条变换规则（置换规则 、换名规则、代替规则）就可以

35、求出与公式等值的、换名规则、代替规则）就可以求出与公式等值的 前束范式，或所谓公式的前束范式。前束范式，或所谓公式的前束范式。 (1)(1)利用量词转化公式，把否定深入到指导变元的后面。利用量词转化公式，把否定深入到指导变元的后面。 xA(x) xA(x) xA(x)xA(x) xA(x) xA(x) xA(x)xA(x) (2)(2)利用利用 x(A(x)B)x(A(x)B)xA(x)BxA(x)B和和 x(A(x)B)x(A(x)B)xA(x)BxA(x)B 把量词移到全式的最前面，这样便得到前束范式。把量词移到全式的最前面，这样便得到前束范式。 35 例例5.6 5.6 求公式的前束范式

36、求公式的前束范式 （1 1） xF(x)xF(x) xG(x)xG(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)第二式第二式) ) （ y y x(F(x)G(y) x(F(x)G(y) ） 或者或者 xF(x)xF(x) xG(x) xG(x) xF(x)xF(x) xG(x)xG(x) (5.2)(5.2)第

37、二式第二式) ) x(F(x)G(x) x(F(x)G(x) (5.5)(5.5)第一式第一式) ) 36 例例5.6 5.6 求公式的前束范式求公式的前束范式 （2 2） xF(x)xF(x) xG(x)xG(x) xF(x)xF(x) xG(x) xG(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 y(F(x)G(y) y(F(x)G(y) (5.3)(5.3)第一式第一式) ) q 公式的前束范式是不唯一的。公式的前

38、束范式是不唯一的。 37 例例5.7 5.7 求前束范式求前束范式 (1)(1) xF(x) xF(x) xG(x)xG(x) yF(y) yF(y) xG(x)xG(x) y y x(F(y)G(x)x(F(y)G(x) (2) (2) xF(x) xF(x) xG(x)xG(x) y yF(y) F(y) xG(x)xG(x) y y x(x(F(y)G(x)F(y)G(x) (3) (3) xF(x) xF(x) xG(x)xG(x) y yF(y) F(y) xG(x)xG(x) y y x(x(F(y)G(x)F(y)G(x) (4) (4) xF(x) xF(x) y yG(y)G

39、(y) x x y(y(F(x)G(x)F(x)G(x) 38 例例5.8 5.8 求公式的前束范式求公式的前束范式 (1)(1) xF(x,y)xF(x,y) yG(x,y) yG(x,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) (5.3),(5.4) 或者或者 xF(x,y)xF(x,y) yG(x,y) yG(x,y) xF(x,t)xF(x,t) yG(w,y) (yG(w,y) (代替规则代替规则) ) x x y(F(x,t)G(w,y)

40、(5.3),(5.4)y(F(x,t)G(w,y) (5.3),(5.4) q 解本题时一定注意，哪些个体变项是约束出现解本题时一定注意，哪些个体变项是约束出现 ，哪些是自由出现，特别要注意那些既是约束，哪些是自由出现，特别要注意那些既是约束 出现又是自由出现的个体变项。不能混淆出现又是自由出现的个体变项。不能混淆。 39 例例5.8 5.8 求公式的前束范式求公式的前束范式 (2)(2)( x x1 1F(xF(x1 1,x,x2 2) ) x x2 2G(xG(x2 2) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) ( ( x x4 4F(xF(x4 4,x,x2

41、 2) ) x x5 5G(xG(x5 5) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) x x4 4 x x5 5(F(x(F(x4 4,x,x2 2) G(x) G(x5 5) ) x x1 1H(xH(x1 1,x,x2 2,x,x3 3) ) x x4 4 x x5 5 x x1 1(F(x(F(x4 4,x,x2 2) G(x) G(x5 5) H(x) H(x1 1,x,x2 2,x,x3 3) ) 40 5.3 5.3 一阶逻辑的推理理论一阶逻辑的推理理论 q 在一阶逻辑中，从前提在一阶逻辑中，从前提A A1 1,A,A2 2, ,A Ak k出发推结论

42、出发推结论B B的推理形式结的推理形式结 构，依然采用如下的蕴涵式形式构，依然采用如下的蕴涵式形式 A A1 1 ,A ,A2 2 , , ,A ,Ak k B B （5.65.6） 若式（若式（5.65.6）为永真式，则称推理正确，否则称推理不正确。）为永真式，则称推理正确，否则称推理不正确。 q 于是，在一阶逻辑中判断推理是否正确也归结为判断（于是，在一阶逻辑中判断推理是否正确也归结为判断（5.65.6） 式是否为永真式了。式是否为永真式了。 q 在一阶逻辑中称永真式的蕴涵式为推理定律，若一个推理的在一阶逻辑中称永真式的蕴涵式为推理定律，若一个推理的 形式结构正是某条推理定律，则这个推理显

43、然是正确的。形式结构正是某条推理定律，则这个推理显然是正确的。 q 在一阶逻辑的推理中，某些前提与结论可能是受量词限制，在一阶逻辑的推理中，某些前提与结论可能是受量词限制， 为了使用命题逻辑中的等值式和推理定律，必须在推理过程为了使用命题逻辑中的等值式和推理定律，必须在推理过程 中有消去和添加量词的规则，以便使谓词演算公式的推理过中有消去和添加量词的规则，以便使谓词演算公式的推理过 程可类似于命题演算中推理理论那样进行。程可类似于命题演算中推理理论那样进行。 41 推理定律的来源推理定律的来源 q 命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例 q 由基本等值式生成的推理定律由基本等值式

44、生成的推理定律 q 量词分配等值式量词分配等值式 q 推理规则推理规则量词消去和引入规则量词消去和引入规则 42 命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例 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 43 由基本等值式生成的推理定律由基本等值式生成的推理定律 q xF(x) xF(x) xF(x) xF(x) q xF(x) xF(x) xF(x)xF(x) q xF(x) xF(x) xF(x

45、)xF(x) q xF(x) xF(x) xF(x) xF(x) q 44 其他推理定律其他推理定律 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 q 对对 x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(x)xB(x)的讨论的讨论 若若

46、x(A(x)B(x)x(A(x)B(x)为真，则有一个客体为真，则有一个客体c c，使得，使得A(c)B(c)A(c)B(c) 为真，即为真，即A(c)A(c)和和B(c)B(c)都为真，所以都为真，所以 xA(x)xA(x) xB(x)xB(x)也为真。也为真。 45 推理规则推理规则 q 为了构造推理系统，还要给出为了构造推理系统，还要给出4 4条重要的推理规则条重要的推理规则, , 即消去量词和引入量词的规则：即消去量词和引入量词的规则： 1 1全称量词消去规则全称量词消去规则( (简记为简记为UIUI规则或规则或UI)UI) Universal instantiation Univer

47、sal instantiation 2 2全称量词引入规则全称量词引入规则( (简记为简记为UGUG规则或规则或UG)UG) Universal Generalize Universal Generalize 3 3存在量词引入规则存在量词引入规则( (简称简称EGEG规则或规则或EG)EG) Existential Generalize Existential Generalize 4 4存在量词消去规则存在量词消去规则( (简记为简记为EIEI规则或规则或EI)EI) Existential instantiation Existential instantiation 46 全称量词消去

48、规则全称量词消去规则( (简记为简记为UIUI规则或规则或UI)UI) 含义：如果个体域的所有元素都具有性质含义：如果个体域的所有元素都具有性质A A，则个体域中的任，则个体域中的任 一元素具有性质一元素具有性质A A。 两式成立的条件：两式成立的条件： (1)(1)在第一式中，取代在第一式中，取代x x的的y y应为任意的不在应为任意的不在A(x)A(x)中约束出现的中约束出现的 个体变项。个体变项。 (2)(2)在第二式中，在第二式中，c c为任意个体变项。为任意个体变项。 (3)(3)用用y y或或c c去取代去取代A(x)A(x)中自由出现的中自由出现的x x时，一定要在时，一定要在x

49、 x自由出现自由出现 的一切地方进行取代。的一切地方进行取代。 A A( (c c) ) x xA A( (x x) ) 或或 A A( (y y) ) x xA A( (x x) ) 47 全称量词消去规则全称量词消去规则( (简记为简记为UIUI规则或规则或UI)UI) 举例举例 当当A(x)A(x)为原子公式时，比如为原子公式时，比如A(x)=F(x)A(x)=F(x)，则当，则当 xA(x)xA(x)为为 真时，对于个体域中任意的个体变项真时，对于个体域中任意的个体变项y y，不会出现，不会出现F(y)F(y)为为 假的情况。假的情况。 当当A(x)A(x)不是原子公式时，如不是原子公

50、式时，如y y已在已在A(x)A(x)中约束出现了，就中约束出现了，就 不能用不能用y y取代取代x x，否则会出现，否则会出现 xA(x)xA(x)为真而为真而A(y)A(y)为假的情为假的情 况。况。 考虑个体域为实数集合，公式考虑个体域为实数集合，公式A(x)=A(x)= yF(x,y)yF(x,y)为为xyxy。 当对公式当对公式 xA(x)=xA(x)= x x yF(x,y)yF(x,y)使用使用UIUI规则时，用规则时，用y y取代取代x x ，就会得到，就会得到A(y)=A(y)= yF(y,y)yF(y,y)，即，即 y(yy)y(yy)，这显然是假命，这显然是假命 题。原因

51、是违背了条件题。原因是违背了条件(1)(1)。 若用若用z z取代取代x x，得，得A(z)=A(z)= yF(z,y)=yF(z,y)= y(zy)y(zy)就不会产生这就不会产生这 种错误。种错误。 48 全称量词引入规则全称量词引入规则( (简记为简记为UGUG规则或规则或UG)UG) 该式成立的条件是：该式成立的条件是： (1)(1)无论无论A(y)A(y)中自由出现的个体变项中自由出现的个体变项y y取何值，取何值，A(y)A(y)应该均为真。应该均为真。 (2)(2)取代自由出现的取代自由出现的y y的的x x也不能在也不能在A(y)A(y)中约束出现。中约束出现。 x xA A(

52、 (x x) ) A A( (y y) ) 举例举例 取个体域为实数集，取个体域为实数集，F(x,y)F(x,y)为为xyxy，A(y)=A(y)= xF(x,y)xF(x,y)。 显然显然A(y)A(y)满足条件满足条件(1)(1)。 对对A(y)A(y)应用应用UGUG规则时，若取已约束出现的规则时，若取已约束出现的x x取代取代y y，会得，会得 到到 xA(x)=xA(x)= x x x(xx)x(xx)，这是假命题。，这是假命题。 产生这种错误的原因是违背了条件产生这种错误的原因是违背了条件(2)(2)。 若取若取z z取代取代y y，得，得 zA(z)=zA(z)= z z x(x

53、z)x(xz)为真命题。为真命题。 49 存在量词引入规则存在量词引入规则( (简称简称EGEG规则或规则或EG) EG) 该式成立的条件是：该式成立的条件是： (1)c(1)c是特定的个体常项。是特定的个体常项。 (2)(2)取代取代c c的的x x不能在不能在A(c)A(c)中出现过。中出现过。 x xA A( (x x) ) A A( (c c) ) 举例举例 取个体域为实数集，取个体域为实数集，F(x,y)F(x,y)为为xyxy，取，取A(5)=A(5)= xF(x,5)xF(x,5)。 显然显然A(5)A(5)是真命题。是真命题。 在应用在应用EGEG规则时，若用规则时，若用A(5

54、)A(5)中已出现的中已出现的x x取代取代5 5，得，得 x x xF(x,x)=xF(x,x)= x(xx)x(xx)，这是假命题。，这是假命题。 产生这种错误的原因是违背了条件产生这种错误的原因是违背了条件(2)(2)。 若用若用A(5)A(5)中未出现过的个体变项中未出现过的个体变项y y取代取代5 5，得，得 yA(y)=yA(y)= y y xF(xy)xF(xy)，这为真命题。，这为真命题。 50 存在量词消去规则存在量词消去规则( (简记为简记为EIEI规则或规则或EI) EI) 该式成立的条件是：该式成立的条件是： (1)c(1)c是使是使A A为真的特定的个体常项。为真的特

55、定的个体常项。 (2)c(2)c不在不在A(x)A(x)中出现。中出现。 (3)(3)若若A(x)A(x)中除自由出现的中除自由出现的x x外，还有其它自外，还有其它自 由出现的个体变项，此规则不能使用。由出现的个体变项，此规则不能使用。 A A( (c c) ) x xA A( (x x) ) 举例举例 取个体域为自然数集合，取个体域为自然数集合，F(x)F(x)为为x x是奇数，是奇数，G(x)G(x)为为x x是偶数是偶数 。 xF(x)xF(x)与与 xG(x)xG(x)都是真命题，则对于某些都是真命题，则对于某些c c和和d d，可以断，可以断 定定P(c)Q(d)P(c)Q(d)必

56、定为真，但不能断定必定为真，但不能断定P(c)Q(c)P(c)Q(c)是真。是真。 对对 xF(x)xF(x)使用使用EIEI规则时，取代规则时，取代x x的的c c一定是特定的个体常项一定是特定的个体常项 1,3,51,3,5等奇数。等奇数。 对对 xG(x)xG(x)使用使用EIEI规则时，取代规则时，取代x x的的c c一定是特定的个体常项一定是特定的个体常项 2,4,62,4,6等偶数。等偶数。 51 定义定义5.3 5.3 自然推理系统定义自然推理系统定义 1.1.字母表。同一阶语言的字母表。字母表。同一阶语言的字母表。 2.2.合式公式。同合式公式的定义。合式公式。同合式公式的定义

57、。 3.3.推理规则：推理规则： (1)(1)前提引入规则。前提引入规则。 (2)(2)结论引入规则。结论引入规则。 (3)(3)置换规则。置换规则。 52 (4)假言推理规则假言推理规则 AB A B (5)附加规则附加规则: A A B (6)化简规则化简规则: A B A (7)拒取式规则拒取式规则: AB B A (8)假言三段论规则假言三段论规则: AB BC AC 53 (9)析取三段论规则析取三段论规则: A B B A (10)构造性二难推理规构造性二难推理规 则则: AB CD A C B D (11)合取引入规则合取引入规则: A B A B 54 (12)UI(12)UI

58、规则。规则。 (13)UG(13)UG规则。规则。 (14)EG(14)EG规则。规则。 (15)EI(15)EI规则。规则。 55 例题例题 例题例题 在自然推理系统中，构造下面推理的证明在自然推理系统中，构造下面推理的证明 所有的人都是要死的，苏格拉底是人，所以苏格拉底是要所有的人都是要死的，苏格拉底是人，所以苏格拉底是要 死的。死的。 解：先将原子命题符号化。解：先将原子命题符号化。 设设 F(x):xF(x):x是一个人，是一个人，G(x):xG(x):x是要死的，是要死的，a a：苏格拉底。：苏格拉底。 前提：前提： x(F(x)G(x), F(a)x(F(x)G(x), F(a)

59、结论：结论：G(a)G(a) 证明：证明： x(F(x)G(x)x(F(x)G(x)前提引入前提引入 F(a)G(a) F(a)G(a) UIUI规则规则 F(a)F(a) 前提引入前提引入 G(a) G(a) 假言推理假言推理 56 例例5.95.9 例例5.9 5.9 设个体域为实数集合，设个体域为实数集合，F(x,y)F(x,y)为为xyxy。指出在推理系统。指出在推理系统F F 中，以中，以 x x yF(xyF(x，y)(y)(真命题真命题) )为前提，推出为前提，推出 xF(x,c)(xF(x,c)(假命假命 题题) )的下述推理证明中的错误。的下述推理证明中的错误。 x x yF

60、(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)为为 假命题。如果按假命题。如果按F F中推理规则进行推理，不会从真命题推出中推理规则进行推理，不会从真命题推出 假命题。假命题。 在以上推理证明中，第三步错了，由于在以上推理证明中，第三步错了，由于F(z,y)F(z,y)中除有自由出中除有自由出 现的现的y y，还有自由出现的