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

1、复习复习 q 变元的约束(Bound of variable在x和x的辖域中，x的所有出现都称为约束出现，相应的x称为约束变元; P(x)中除约束变元以外出现的变元称为是自由变元。例1： 1、x( H(x,y)y(W(y) L(x,y,z) 2、 x( H(x)W(y) y( F(x) L(x,y,z)q 注意：(1)n元谓词公式A(x1，x2.xn) 中有n个自由变元,若对其中的k(kn)个进行约束,则构成了n-k元谓词;如果一个公式中没有自由变元出现,则该公式就变成了一个命题(2)一个公式的约束变元所使用的名称符号是无关紧要的,如(x)M(x)与(y)M(y)意义相同.约束变元的换名与自由

2、变元的代入规则换名规则: (对约束变元而言）对约束变元进行换名,使得一个变元在一个公式中只呈一种形式出现.(1)约束变元可以换名,其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的该变元,公式的其余部分不变.(2)换名时一定要更改为作用域中没有出现的变元名称.q 例1: x( P(x)R(x,y) L(x,y)换名为t( P(t)R(t,y) L(x,y)q x( H(x,y)y(W(y) L(x,y,z)换名为x( H(x,y)s(W(s) L(x,s,z)q 代入规则（对自由变元而言）对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入,代入时需要对公式中出

3、现该自由变元的每一处进行;(2)用以代入的变元与原公式中所有变元的名称不能相同.例如对例1中的公式x( P(x)R(x,y) L(x,y) 自由变元y用z来代入,得 x( P(x)R(x,z) L(x,z)习题习题1、 在一阶逻辑中将下列命题符号化。在一阶逻辑中将下列命题符号化。（1） 大熊猫都可爱。大熊猫都可爱。（2） 有人爱发脾气。有人爱发脾气。（3） 说所有人都爱吃面包是不对的。说所有人都爱吃面包是不对的。（4） 没有不爱吃糖的人。没有不爱吃糖的人。（5） 一切人都不一样高。一切人都不一样高。（6） 并不是所有的汽车都比火车快。并不是所有的汽车都比火车快。解：由于没指出个体域，故用全总个

4、体域解：由于没指出个体域，故用全总个体域（1）大熊猫都可爱。）大熊猫都可爱。 设设F(x): x为大熊猫，为大熊猫，G(x): x可爱，命题符号化为可爱，命题符号化为 x(F(x)G(x)（2）有人爱发脾气。）有人爱发脾气。 设设F(x): x是人，是人，G(x): x爱发脾气，命题符号化为爱发脾气，命题符号化为 x(F(x) G(x)（3）说所有人都爱吃面包是不对的。）说所有人都爱吃面包是不对的。 设设F(x): x是人，是人，G(x):x爱吃面包，命题符号化为爱吃面包，命题符号化为 x(F(x)G(x) 或或 x(F(x)G(x)（4）没有不爱吃糖的人。）没有不爱吃糖的人。 设设F(x):

5、 x是人，是人，G(x): x爱吃糖，命题符号化为爱吃糖，命题符号化为 x(F(x)G(x) 或或 x(F(x)G(x)（5）一切人都不一样高。）一切人都不一样高。 设设 F(x):x是人是人, H(x,y)：x与与y相同相同, L(x,y): x与与y一样高，命题一样高，命题符号化为符号化为 x y(F(x) F(y)H(x,y)L(x,y) 或或 x(F(x)y(F(y)H(x,y)L(x,y)（6）并不是所有的汽车都比火车快。）并不是所有的汽车都比火车快。 设设F(x):x是汽车是汽车, G(y):y是火车是火车, H(x,y):x比比y快，命题符号化为快，命题符号化为 x y(F(x)

6、 G(y)H(x,y) 或或 x y(F(x) G(y)H(x,y)2、在一阶逻辑中将下列命题符号化。、在一阶逻辑中将下列命题符号化。（1） 没有一个自然数大于等于任何自然数。没有一个自然数大于等于任何自然数。（2） 有唯一的偶素数。有唯一的偶素数。解：解：（1）N(x):x是自然数，是自然数，G(x,y):x y x(N(x)y(N(y) G(x,y)（2）Q(x):x是偶数，是偶数，P(x):x是素数，是素数， E(x,y):xy x(Q(x) P(x)y(Q(y) P(y) E(x,y)3、判断公式是否为永真公式。判断公式是否为永真公式。 ( x A(x) x B(x) x (A(x)

7、B(x) 解：解： 不是永真公式。不是永真公式。 设个体域为设个体域为a,b，令令A(a)=1,B(a)=0, A(b)=0,B(b)=1。小节结束小节结束第5章 一阶逻辑等值演算与推理离离 散散 数数 学学山东师范大学本科生课程山东师范大学本科生课程信息科学与工程学院信息科学与工程学院2008专升本专升本本章说明本章说明q 本章的主要内容本章的主要内容一阶逻辑等值式与基本等值式一阶逻辑等值式与基本等值式置换规则、换名规则、代替规则置换规则、换名规则、代替规则前束范式前束范式一阶逻辑推理理论一阶逻辑推理理论q 本章与其他各章的关系本章与其他各章的关系本章先行基础是前四章本章先行基础是前四章本章

8、是集合论各章的先行基础本章是集合论各章的先行基础本章主要内容本章主要内容 5.1 5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则5.2 5.2 一阶逻辑前束范式一阶逻辑前束范式5.3 5.3 一阶逻辑的推理理论一阶逻辑的推理理论 主要内容主要内容 作作 业业5.1 5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则在一阶逻辑中，有些命题可以有不同的符号化形式。在一阶逻辑中，有些命题可以有不同的符号化形式。例如：例如：没有不犯错误的人没有不犯错误的人令令 M(x):xM(x):x是人。是人。 F(x):xF(x):x犯错误。犯错误。则将上述命题的符号化有以下两种正确形式：则将上述

9、命题的符号化有以下两种正确形式：(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.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 判断公式

10、判断公式A A与与B B是否等值，等价于判断公式是否等值，等价于判断公式A AB B是否是否为永真式。为永真式。q 谓词逻辑中关于联结词的等值式与命题逻辑中相关谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。等值式类似。 说说明明一阶逻辑中的一些基本而重要等值式一阶逻辑中的一些基本而重要等值式q 代换实例代换实例q 消去量词等值式消去量词等值式 q 量词否定等值式量词否定等值式 q 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 q 量词分配等值式量词分配等值式 代换实例代换实例-命题公式的推广命题公式的推广 由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永由于命题逻辑中的重言式的

11、代换实例都是一阶逻辑中的永真式，因而真式，因而第二章的第二章的1616组等值式组等值式模式给出的代换实例都是模式给出的代换实例都是一阶逻辑的等值式的模式。一阶逻辑的等值式的模式。例如：例如：(1)(1) xF(xxF(x) ) xF(xxF(x) )（双重否定律）双重否定律）(2)(2)F(x)G(y) 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(zzH(z) ) x(F(x)G(y)x(F(x)G(y) zH(zzH(z) ) （蕴涵等值式）蕴涵等值式）消去量词等值式消去量词等值式设个体域为有

12、限集设个体域为有限集D=aD=a1 1,a,a2 2, ,a,an n,则有则有（1 1） xA(xxA(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(xxA(x) ) xA(x)xA(x)（2 2） xA(x) xA(x) xA(x)xA(x)说明说明q “并不是所有的并不是所有的x x都

13、有性质都有性质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(x)B) xA(x)BxA(x)

14、B x(BA(x) x(BA(x) BB xA(xxA(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) BB xA(xxA(x) )（5.35.3）（5.45.4）量词辖域中如果有合取或量词辖域中如果有合取或析析取项，且其中有一个是命取项，且其中有一个是命题题，则可将该命题移至量词，则可将该命题移至量词辖辖域之外域之外证明证明: : xA(x)BxA(x)B x(A(x)B)x(A(x)B) xA(x)B

15、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)量词分配等值式量词分配等值式设设A(x)A(x)，B(x)B(x)是任意的含自由出现个体变项是任意的含自由出现个体变项x x的公式，则的公式，则（1 1） x(A(x)x(A(x)B(x) B(x) xA(x)xA(x) xB(xxB(x) )（2 2） x(A(x)B(x) x(A(x)B(x) xA(xxA(x) ) xB(xxB(x) )（5.55.5） 例如例如，“联欢会上所有人既唱歌又跳舞联欢会上所有人既唱歌又跳舞”和和“联欢会上所联欢会上所有人唱歌且

16、所有人跳舞有人唱歌且所有人跳舞” ” ，这两个语句意义相同。故有，这两个语句意义相同。故有(1)(1)式。以下两式式。以下两式注意注意 x(A(x)B(x) x A(x) x B(x) x(A(x)B(x)x A(x) x B(x)谓词演算蕴含式谓词演算蕴含式 xA(x)xA(x) xB(x) xB(x) x(A(x)B(x)x(A(x)B(x) x(A(x)B(x) x(A(x)B(x) x A(x) x A(x) x B(x)x B(x)多个量词间的次序排列等值式。多个量词间的次序排列等值式。q 多个量词同时出现时,其顺序是至关重要的.(1) ( , )( , )x yA x yy xA

17、x y (2) ( , )( , )x yA x yy xA x y x y P(x,y) y x P(x,y) y x P(x,y) x y P(x,y) x y P(x,y) y x P(x,y) y x P(x,y) x y P(x,y) 多个量词间的次序排列等值式。多个量词间的次序排列等值式。一阶逻辑等值演算的三条原则一阶逻辑等值演算的三条原则q 置换规则置换规则：设设(A)(A)是含公式是含公式A A的公式，的公式，(B)(B)是用公式是用公式B B取代取代(A)(A)中所有的中所有的A A之后的公式，若之后的公式，若A AB B，则则(A)(A)(B)(B)。 一阶逻辑中的置换规则

18、与命题逻辑中的置换规则形式一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里上完全相同，只是在这里A A，B B是一阶逻辑公式。是一阶逻辑公式。q 换名规则换名规则：设设A A为一公式，将为一公式，将A A中某量词辖域中某中某量词辖域中某约束变项约束变项的的所有出现及所有出现及相应的指导变元相应的指导变元改成该量词辖域中改成该量词辖域中未曾出现过的未曾出现过的某个体变项符号，某个体变项符号，公式的其余部分不变，设所得公式为公式的其余部分不变，设所得公式为AA，则则AAA A。q 代替规则代替规则：设设A A为一公式，将为一公式，将A A中某个中某个自由出现的个体变项自由出现的

19、个体变项的的所有出现，用所有出现，用A A中中未曾出现过的个体变项符号代替未曾出现过的个体变项符号代替，A A中其余中其余部分不变，设所得公式为部分不变，设所得公式为AA，则则AAA A。例例5.15.1例例5.15.1 将下面公式化成与之等值的公式，使其将下面公式化成与之等值的公式，使其没有既是约束没有既是约束出现又是自由出现的个体变项出现又是自由出现的个体变项。(1)(1) xF(x,y,z)xF(x,y,z) yG(x,y,zyG(x,y,z) )(2)(2) x(F(x,y)x(F(x,y) yG(x,y,zyG(x,y,z)(1)(1) x xF(F(x x,y,z,y,z) ) y

20、G(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.15.1的解答的解答(2

21、)(2) x x（F(x,F(x,y y) ) yG(x,y,zyG(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(xxB(x) ) （2 2） x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x

22、) )其中其中A(x)A(x)，B(x)B(x)为含为含x x自由出现的公式。自由出现的公式。只要证明在某个解释下两边的式子不等值。只要证明在某个解释下两边的式子不等值。取解释取解释I I：个体域为自然数集合个体域为自然数集合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(xxG(x) )为假命题。为假命题。两边不等值。两边不等值。证明证明例例5.25.2(2)(2) x(A(x)B(

23、x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x) ) x(F(x)G(x)x(F(x)G(x)：有些有些x x既是奇数又是偶数为假命题；既是奇数又是偶数为假命题；而而 xF(x)xF(x) xG(xxG(x) )：有些有些x x是奇数并且有些是奇数并且有些x x是偶数为真是偶数为真命题。命题。 两边不等值。两边不等值。证明证明说明说明q 全称量词全称量词“ ”对对“”“”无分配律。无分配律。q 存在量词存在量词“ ”对对“”“”无分配律。无分配律。例例5.35.3消去量词消去量词例例5.35.3 设个体域为设个体域为D Da,b,ca,b,c，将下面各公式的量词消去：将下面

24、各公式的量词消去： (1) (1) x(F(x)G(x)x(F(x)G(x)(2) (2) x(F(x) x(F(x) yG(yyG(y)(3) (3) x x yF(x,yyF(x,y) )说明说明q 如果不用公式如果不用公式(5.3)(5.3)将量词的辖域缩小，演算过程较将量词的辖域缩小，演算过程较长。注意，此时长。注意，此时 yG(yyG(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)G(c)(2)(2) x(F(x) x

25、(F(x) yG(yyG(y) ) xF(x)xF(x) yG(yyG(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) 例例5.35.3消去量词消去量词(3) (3) x x yF(x,yyF(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 ,

26、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,yyF(x,y) ) yF(a,y)yF(a,y) yF(b,yyF(b,y) ) yF(c,yyF(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,

27、b)F(c,c) (F(c,a)F(c,b)F(c,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) )( (2 2, ,2 2) )y y) )( (x x, ,G GG GG GG GG G。，为：01( (3 3, ,2 2) )( (2

28、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,y)例例5.45.4的解答的解答（1 1） x(F(x)G(x,a)x(F(x)G(x

29、,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(x)x(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(11)1)(0(01)1) 1 1例例5.4的解答的解答（3 3） x x yL(x,yyL(x,y) ) (L(2,2)(L(2,2)L(2,3)L(2,3

30、)(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)的结果进一步可以说明量词的次序不能的结果进一步可以说明量词的次序不能随意颠倒。随意颠倒。 例例5.55.5例例5.55.5 证明下列等值式。证明下列等值式。 （1 1） x(M(x)x(M(x)F(

31、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 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(

32、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(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(

33、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 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(

34、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) 小节结束小节结束小 结q 本节介绍了谓词公式的概念及谓词演算的等值式与蕴涵式，重点掌握谓词演算的等值式与蕴涵式5.2 5.2 一阶逻辑前束范式一阶逻辑前束范式定义定义5.25.2 设设A A为一个一阶逻辑公式，若为一个一阶逻辑公式，若A A具有如下形式具有如下形式Q Q1 1x

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

36、,y)(G(y)H(x,y) )前束范式存在定理前束范式存在定理定理定理5.15.1 一阶逻辑中的任何公式都存在与之等值的前束范式。一阶逻辑中的任何公式都存在与之等值的前束范式。任何公式的前束范式都是存在的，但一般说来，并不唯一。任何公式的前束范式都是存在的，但一般说来，并不唯一。利用一阶逻辑等值式以及三条变换规则（置换规则、换名规则、代替利用一阶逻辑等值式以及三条变换规则（置换规则、换名规则、代替规则）就可以求出与公式等值的前束范式。规则）就可以求出与公式等值的前束范式。第一步：第一步：否定深入。否定深入。利用量词转化公式，把利用量词转化公式，把否定深入否定深入到指导变元的后到指导变元的后面

37、。面。 xA(xxA(x) ) xxA(x) A(x) xA(xxA(x) ) xxA(x)A(x)第二步：第二步：改名。改名。即利用换名规则、代入规则更换一些变元的名称，以即利用换名规则、代入规则更换一些变元的名称，以便消除混乱。便消除混乱。第三步：第三步：量词前移量词前移 利用利用 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把量词移到全式的最前面，这样得到前把量词移到全式的最前面，这样得到前束范式。束范式。 ),(),()(),()(),()()6(),()()()(),()()5()()()()()4()(

38、)()()() 3()()()()()2()()()()() 1 (yxBxyAyyxByxyxAyxyxHxyGyyxFxxGxxFxxGxxFxxGxxFxxGxxFx例求下列公式的前束范式。q 解:)()()()()()()()()()()() 1 (量词分配量词转换律xGxFxxGxxFxxGxxFx)()()()()()()()()()()()()()()()()()()()()2(辖域扩张辖域扩张换名量词转换律yGxFyxyGyxFxyGyxFxxGxxFxxGxxFx )(,()(),()()()()(,()()(),()()()(,()()(),()()()(,()()()()

39、,()()(,()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()()5(辖域扩张辖域扩张辖域扩张换名代入ztHyGzxFtyxztHtyGzxFyxztHtyGzxFyxztHtyGyzxFxzxHxyGyzxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxq (6)()() ( , )()() ( , )()( ( , )( , )() () ( , )()() ( , )()( , )( , )()() ( , )()()( , )()( ( , )( , )xy

40、 A x yxy B x yy A y xB x yxy A x yxy B x yyA y xB x yxy A x yxyB x yy A y xB x y ),(),(),(),()()()()()(,(),()(),()(),()(),(),()(),()(),()()6(zuBuzAvuByxAzvuyxzuBuzAzvuBvuyxAyxyxBxyAyyxByxyxAyx换名续例例5.6 5.6 求公式的前束范式求公式的前束范式（1 1） xF(x)xF(x) x xG(G(x x) ) xF(x)xF(x) yG(yyG(y) ) ( (换名规则换名规则) ) xF(x)xF(x)

41、 yG(yyG(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)第二式第二式) ) 或者或者 xF(x)xF(x) xG(xxG(x) ) xF(x)xF(x) xG(xxG(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(xxG(x) ) xF(x)xF(

42、x) xG(xG(x x) ) (5.2)(5.2)第二式第二式) ) xF(x)xF(x) yG(yyG(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 公式的前束范式是不唯一的。公式的前束范式是不唯一的。例例5.7 5.7 求前束范式求前束范式(1)(1) xF(xF(x x) ) xG(xxG(x) ) yF(yyF(y) ) xG(xxG(x) ) y y x(F(y)G(x)x(F(y)G(x)(2)

43、 (2) xF(xF(x x) ) xG(xxG(x) ) y yF(yF(y) ) xG(xxG(x) ) y y x(x(F(y)G(x)F(y)G(x)(3) (3) xF(xF(x x) ) xG(xxG(x) ) y yF(yF(y) ) xG(xxG(x) ) y y x(x(F(y)G(x)F(y)G(x)(4) (4) xF(xxF(x) ) y yG(yG(y) ) x x y(y(F(x)G(x)F(x)G(x)例例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

44、(x,wwG(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,xF(x,y y) yG(yG(x x,y,y) ) xF(x,t)xF(x,t) yG(w,yyG(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 解题时一定注意，哪些个体变项是约束出现，哪些是解题时一定注意，哪些个体变项是约束出现，哪些是自由出现，特别要注意那些既是约束出现又是自由出自

45、由出现，特别要注意那些既是约束出现又是自由出现的个体变项。不能混淆现的个体变项。不能混淆。例例5.8 5.8 求公式的前束范式求公式的前束范式(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(

46、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) ) G(G(x x5 5) ) ) H(xH(x1 1,x,x2 2,x,x3 3) ) ) 小节结束小节结束5.3 5.3 一阶逻辑的推理理论一阶逻辑的推理理论 在一阶逻辑中，从前提在一阶逻辑中，从前提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）

47、为永真式，则称）为永真式，则称推理正确推理正确，否则称推理不正确。，否则称推理不正确。q 在一阶逻辑中称永真式的蕴涵式为在一阶逻辑中称永真式的蕴涵式为推理定律推理定律，若一个推理的，若一个推理的形式结构正是某条推理定律，则这个推理显然是正确的。形式结构正是某条推理定律，则这个推理显然是正确的。q 在一阶逻辑的推理中，在一阶逻辑的推理中，某些前提与结论可能是受量词限制，某些前提与结论可能是受量词限制，为了使用命题逻辑中的为了使用命题逻辑中的等值式和推理定律等值式和推理定律，必须在推理过程必须在推理过程中有消去和添加量词的规则中有消去和添加量词的规则，以便使谓词演算公式的推理过，以便使谓词演算公式

48、的推理过程可类似于命题演算中推理理论那样进行。程可类似于命题演算中推理理论那样进行。推理定律的来源推理定律的来源q 命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例q 由基本等值式生成的推理定律由基本等值式生成的推理定律q 推理规则推理规则量词消去和引入规则量词消去和引入规则命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例q A (AB) 附加律附加律q (AB) A 化简律化简律q (AB)A B 假言推理假言推理q (AB)B A 拒取式拒取式q (AB)B A 析取三段论析取三段论 q (AB)(BC) (AC) 假言三段论假言三段论q (A B)(B C) (A C) 等价三段

49、论等价三段论q (AB)(CD)(AC) (BD) 构造性二难构造性二难 (AB)(AB)(AA) B 构造性二难构造性二难 (特殊形式特殊形式)q (AB)(CD)(BD) (AC) 破坏性二难破坏性二难 xF(x)xF(x) yG(yyG(y) ) xF(xxF(x) )（化简律的代换实例）化简律的代换实例） xF(xxF(x) ) xF(xxF(x) ) yG(yyG(y) ) （附加律的代换实例）附加律的代换实例）由基本等值式生成的推理定律由基本等值式生成的推理定律 xF(xxF(x) ) xF(xxF(x) ) xF(xxF(x) ) xF(xxF(x) ) xF(xxF(x) )

50、xF(x)xF(x) xF(x) xF(x) xF(xxF(x) ) 量词推理定律量词推理定律 xA(x)xA(x) xB(xxB(x) ) x(A(x)B(x) x(A(x)B(x) x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x) ) x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x) ) x(A(x)B(x) x(A(x)B(x) xA(xxA(x) ) xB(xxB(x) ) q 对对 x(A(x)B(x) x(A(x)B(x) xA(x)xA(x) xB(xxB(x) )的讨论：的讨论： 若若 x(A(x)B(x)

51、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(xxB(x) )也为真。也为真。 说明说明推理规则推理规则 为了构造推理系统，还要给出为了构造推理系统，还要给出4 4条重要的推理规则条重要的推理规则, ,即消去量词和引入量词的规则：即消去量词和引入量词的规则：1 1全称量词消去规则全称量词消去规则( (简记为简记为UIUI规则或规则或UI)UI)2 2全称量词引入规则全称量词引入规则( (简记为简记为UGUG规则或规则或UG)UG)3

52、 3存在量词引入规则存在量词引入规则( (简称简称EGEG规则或规则或EG)EG)4 4存在量词消去规则存在量词消去规则( (简记为简记为EIEI规则或规则或EI)EI)说明说明q 这四条规则只能使用在前束范式中。这四条规则只能使用在前束范式中。全称量词消去规则全称量词消去规则( (简记为简记为UIUI规则或规则或UI)UI)含义含义：如果个体域的所有元素都具有性质：如果个体域的所有元素都具有性质A A，则个体域中的任一则个体域中的任一元素具有性质元素具有性质A A。 两式成立的条件两式成立的条件： (1)(1)在第一式中，取代在第一式中，取代x x的的y y应为任意的不在应为任意的不在A(x

53、)A(x)中约束出现的个中约束出现的个体变项。体变项。 (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) )全称量词消去规则全称量词消去规则( (简记为简记为UIUI规则或规则或UI)UI)例如例如：个体域为实数集合，公式：个体域为实数集合，公式A(x)=A(x)= yF(x,yyF(

54、x,y) )为为xyxy。 当对公式当对公式 xA(xxA(x)=)= x x yF(x,yyF(x,y) )使用使用UIUI规则时，用规则时，用y y取代取代x x，就会得到就会得到A(y)=A(y)= yF(y,yyF(y,y) )，即即 y(yy)y(yy)，这显然是假命题。这显然是假命题。原因是违背了条件原因是违背了条件(1)(1)。 若用若用z z取代取代x x，得得A(z)=A(z)= yF(z,yyF(z,y)=)= y(zy)y(zy)就不会产生这种就不会产生这种错误。错误。全称量词引入规则全称量词引入规则( (简记为简记为UGUG规则或规则或UG)UG)该式成立的条件该式成立

55、的条件是：是： (1)(1)无论无论A(y)A(y)中自由出现的个体变项中自由出现的个体变项y y取何值，取何值，A(y)A(y)应该均为真。应该均为真。 (2)(2)取代自由出现的取代自由出现的y y的的x x也不能在也不能在A(y)A(y)中约束出现。中约束出现。例如例如：取个体域为实数集，：取个体域为实数集，F(x,y)F(x,y)为为xyxy，A(y)=A(y)= xF(x,yxF(x,y) )。 显然显然A(y)A(y)满足条件满足条件(1)(1)。 对对A(y)A(y)应用应用UGUG规则时，若取已约束出现的规则时，若取已约束出现的x x取代取代y y，会得到会得到 xA(xxA(

56、x)=)= x x x(xx)x(xx)，这是假命题。这是假命题。 产生这种错误的原因是违背了条件产生这种错误的原因是违背了条件(2)(2)。 若取若取z z取代取代y y，得得 zA(zzA(z)=)= z z x(xz)x(xz)为真命题。为真命题。 x xA A( (x x) )A A( (y y) )存在量词引入规则存在量词引入规则( (简称简称EGEG规则或规则或EG) EG) 该式成立的条件该式成立的条件是：是： (1)(1)c c是特定的个体常项。是特定的个体常项。(2)(2)取代取代c c的的x x不能在不能在A(c)A(c)中出现过。中出现过。 x xA A( (x x) )

57、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)A(5)中已出现的中已出现的x x取代取代5 5，得，得 xF(x,xxF(x,x)=)= x(xx)x(xx)，这是假命题。这是假命题。 产生这种错误的原因是违背了条件产生这种错误的原因是违背了条件(2)(2)。 若用若用A(5)A(5)中未出现过的个体变项中未出现过的个体变项y y取代取代5 5，得，得 yA(yyA(y)=)= y

58、 y xF(xxF(xy)y)，这为真命题。这为真命题。 存在量词消去规则存在量词消去规则( (简记为简记为EIEI规则或规则或EI) EI) 该式成立的条件该式成立的条件是：是： (1)(1)c c是使是使A A为真的特定的个体常项。为真的特定的个体常项。 (2)(2)c c不在不在A(x)A(x)中出现。中出现。 (3)(3)若若A(x)A(x)中除自由出现的中除自由出现的x x外，还有其它自外，还有其它自由出现的个体变项，此规则不能使用。由出现的个体变项，此规则不能使用。 A A( (c c) )x xA A( (x x) )例如例如：取个体域为自然数集合，：取个体域为自然数集合，F(x

59、)F(x)为为x x是奇数，是奇数，G(x)G(x)为为x x是偶是偶数数。 xF(xxF(x) )与与 xG(xxG(x) )都是真命题，则对于某些都是真命题，则对于某些c c和和d d，可以断定可以断定P(c)Q(d)P(c)Q(d)必定为真，但不能断定必定为真，但不能断定P(c)Q(c)P(c)Q(c)是真。是真。 对对 xF(xxF(x) )使用使用EIEI规则时，取代规则时，取代x x的的c c一定是特定的个体常项一定是特定的个体常项1,3,51,3,5等奇数。等奇数。对对 xG(xxG(x) )使用使用EIEI规则时，取代规则时，取代x x的的c c一定是特定的个体常项一定是特定的

60、个体常项2,4,62,4,6等偶数。等偶数。定义定义5.3 5.3 自然推理系统定义自然推理系统定义1.1.字母表。同一阶语言的字母表。字母表。同一阶语言的字母表。2.2.合式公式。同合式公式的定义。合式公式。同合式公式的定义。3.3.推理规则：推理规则：(1)(1)前提引入规则。前提引入规则。(2)(2)结论引入规则。结论引入规则。(3)(3)置换规则。置换规则。(4)(4)假言推理规则。假言推理规则。(5)(5)附加规则。附加规则。(6)(6)化简规则。化简规则。(7)(7)拒取式规则。拒取式规则。(8)(8)假言三段论规则。假言三段论规则。(9)(9)析取三段论规则。析取三段论规则。(1