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

1、1练习练习44. 在自然推理系统在自然推理系统NL 中，构造推理的证明中，构造推理的证明 人都喜欢吃蔬菜但不是所有的人都喜欢吃鱼所以人都喜欢吃蔬菜但不是所有的人都喜欢吃鱼所以, 存在喜欢吃蔬菜而不喜欢吃鱼的人存在喜欢吃蔬菜而不喜欢吃鱼的人解解 令令F(x): x为人，为人，G(x): x喜欢吃蔬菜，喜欢吃蔬菜，H(x): x喜欢吃鱼喜欢吃鱼前提：前提： x(F(x)G(x), x(F(x)H(x) 结论：结论： x(F(x) G(x)H(x)证明：用归谬法证明：用归谬法(1) x(F(x) G(x)H(x) 结论否定引入结论否定引入(2) x (F(x) G(x)H(x) (1)置换置换(3)

2、 (F(y) G(y)H(y) (2)(4) G(y) F(y) H(y) (3)置换置换(5) x(F(x)G(x) 前提引入前提引入2练习练习4(续续)(6) F(y)G(y) (5)(7) F(y) F(y) H(y) (4)(6)假言三段论假言三段论(8) F(y) H(y) (7)置换置换(9) y(F(y) H(y) (8) +(10) x(F(x) H(x) (9)置换置换(11) x(F(x) H(x) 前提引入前提引入(12) 0 (10)(11)合取合取 3第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则一阶逻辑前束

3、范式一阶逻辑前束范式一阶逻辑的推理理论一阶逻辑的推理理论知知 识识 点：谓词演算的等价式与蕴涵式、前束范式、谓词点：谓词演算的等价式与蕴涵式、前束范式、谓词 演算的推理理论演算的推理理论 教学要求：深刻理解和掌握谓词逻辑的基本推理方法教学要求：深刻理解和掌握谓词逻辑的基本推理方法 教学重点：谓词逻辑中的基本推理方法教学重点：谓词逻辑中的基本推理方法 学时学时: 545.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则在一阶逻辑中，有些命题可以有不同的符号化形式。在一阶逻辑中，有些命题可以有不同的符号化形式。例如：没有不犯错误的人例如：没有不犯错误的人令令 M(x):x是人。是人。 F(x)

4、:x犯错误。犯错误。则将上述命题的符号化有以下两种正确形式：则将上述命题的符号化有以下两种正确形式：(1) x(M(x)F(x)(2) x(M(x)F(x)q我们称我们称(1)和和(2)是等值的。是等值的。说说明明5定义定义5.1 设设A，B是一阶逻辑中任意两个公式，若是一阶逻辑中任意两个公式，若 AB是永真式，则称是永真式，则称A与与B是等值的。记做是等值的。记做AB，称称 AB 是等值式。是等值式。G(x)G(x)x(F(x)x(F(x)G G( (x x) ) )x x( (F F( (x x) ) 例如：例如：q 判断公式判断公式A与与B是否等值，等价于判断公式是否等值，等价于判断公式

5、AB是否为永真式。是否为永真式。q 谓词逻辑中关于联结词的等值式与命题逻谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。辑中相关等值式类似。 说说明明等值式的定义等值式的定义6一阶逻辑中的一些基本而重要等值式一阶逻辑中的一些基本而重要等值式代换实例代换实例消去量词等值式消去量词等值式 量词否定等值式量词否定等值式 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 量词分配等值式量词分配等值式 7代换实例代换实例命题逻辑中的等值式都是谓词逻辑中的等值式命题逻辑中的等值式都是谓词逻辑中的等值式; 命命题逻辑的等值式中的命题符号用谓词公式代入后题逻辑的等值式中的命题符号用谓词公式代入后所得的

6、公式也是谓词逻辑中的等值式所得的公式也是谓词逻辑中的等值式例如：例如：(1) xF(x) xF(x)（双重否定律）（双重否定律）(2)F(x)G(y) F(x)G(y) （蕴涵等值式）（蕴涵等值式）(3) x(F(x)G(y) zH(z) x(F(x)G(y) zH(z) （蕴涵等值式）（蕴涵等值式）8消去量词等值式消去量词等值式设个体域为有限集设个体域为有限集D=a1,a2,an,则有则有（1） xA(x) A(a1)A(a2)A(an) （2） xA(x) A(a1)A(a2)A(an) （5.15.1）9量词否定等值式量词否定等值式设设A(x)是任意的含自由出现个体变项是任意的含自由出现

7、个体变项x的公式，则的公式，则（1） xA(x) xA(x)（2） xA(x) xA(x)说明说明q “并不是所有的并不是所有的x都有性质都有性质A”与与“存在存在x没有性质没有性质A”是一回事。是一回事。q ”不存在有性质不存在有性质A的的x”与与”所有所有x都没有性质都没有性质A”是一是一回事。回事。（5.25.2）10量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式设设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(

8、BA(x) B xA(x)（2） x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(A(x)B) xA(x)B x(BA(x) B xA(x)（5.35.3）（5.45.4）11证明证明: xA(x)B x(A(x)B) xA(x)B xA(x)B x(A(x)B) xA(x)B x(A(x)B)12量词分配等值式量词分配等值式设设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.55.5）q 例如，例如，“联欢会上所有人既唱

9、歌又跳舞联欢会上所有人既唱歌又跳舞”和和“联欢会上所联欢会上所有人唱歌且所有人跳舞有人唱歌且所有人跳舞” ” ，这两个语句意义相同。故有，这两个语句意义相同。故有(1)(1)式。式。q 由由(1)(1)式推导式推导(2)(2)式式 x(A(x)x(A(x)B(x) B(x) xA(x)xA(x) xB(x)xB(x) x(x(A(x)A(x)B(x) B(x) x xA(x)A(x) x xB(x)B(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)13一阶

10、逻辑等值演算的三条原则一阶逻辑等值演算的三条原则置换规则置换规则：设设(A)是含公式是含公式A的公式，的公式，(B)是用公式是用公式B取代取代(A)中所有的中所有的A之后所得到的公式，那么之后所得到的公式，那么,若若AB，则，则(A)(B)。 换名规则换名规则：设设A为一公式，将为一公式，将A中某量词辖域中某约束变项中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式过的某个体变项符号，公式的其余部分不变，设所得公式为为A，则，则AA。代替规则代替规则：设：设A为一公式，将

11、为一公式，将A中某个自由出现的个体变项中某个自由出现的个体变项的所有出现用的所有出现用A中未曾出现过的个体变项符号代替，中未曾出现过的个体变项符号代替，A中其中其余部分不变，设所得公式为余部分不变，设所得公式为A，则，则AA。说明说明q 一阶逻辑中的置换规则与命题逻辑中的置换一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里规则形式上完全相同，只是在这里A，B是一是一阶逻辑公式。阶逻辑公式。14例例5.1 将下面公式化成与之等值的公式，使其将下面公式化成与之等值的公式，使其没有既是约没有既是约束出现又是自由出现的个体变项束出现又是自由出现的个体变项。(1) xF(x,y,z)

12、 yG(x,y,z)(2) x(F(x,y) yG(x,y,z)(1)(1) x xF(F(x x,y,z),y,z) yG(x,y,z)yG(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,z)wG(x,w,z)( (换名规则换名规则) )或或 xF(x,xF(x,y y,z),z) yG(x,y,z)yG(x,y,z) xF(x,t,z)xF(x,t,z) yG(yG(x x,y,z),y,z)( (代替规则代替规则) ) x xF(x,t,z)F(x,t,z) y

13、 yG(w,y,z)G(w,y,z)( (代替规则代替规则) )解答解答15(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,z)yG(x,y,z)( (代替规则代替规则) )或或 x(F(x,y)x(F(x,y) y yG(x,y,z)G(x,y,z) x(F(x,y)x(F(x,y) tG(x,t,z)tG(x,t,z)( (换名规则换名规则) )解答解答16例例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

14、(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(x)xG(x)为假命题。为假命题。两边不等值。两边不等值。证明证明17(2)(2) x(A(x)B(x)x(A(x)B(x) xA(x)xA(x) xB(x)

15、xB(x) x(F(x)G(x)x(F(x)G(x)：有些：有些x x既是奇数又是偶数为假命题；既是奇数又是偶数为假命题；而而 xF(x)xF(x) xG(x)xG(x)：有些：有些x x是奇数并且有些是奇数并且有些x x是偶数为真是偶数为真命题。命题。 两边不等值。两边不等值。证明证明说明说明q 全称量词全称量词“ ”对对“”无分配律。无分配律。q 存在量词存在量词“ ”对对“”无分配律。无分配律。q 当当B(x)换成没有换成没有x出现的出现的B时，则有时，则有 x(A(x)B) xA(x)B x(A(x)B) xA(x)B18例例5.3 设个体域为设个体域为Da,b,c，将下面各公式的量词

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

17、式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) 19(3) x yF(x,y) x yF(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(c,a)F(c,b)F(c,c) 在演算中先消去存在量词也可以，得到结果是等值的。在演算中先消去存在量词也可以，得到结果是等值的。yF(a,y) yF(b,y) yF(c,y) (F(a,a)F(a,b)F(a,c) (F(b,a)F(b,b)F(b,c) (F(c,a)F(c,b)F(c,

18、c)20例例5.4 给定解释给定解释I如下：如下：（a）个体域）个体域 D2,3（b）D中特定元素中特定元素（c）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 2, ,3 3) )( (3 3, ,3 3) )( (2 2, ,2 2) )y y) )( (x x, ,L LL

19、LL LL LL L。，为：10( (3 3) )( (2 2) )( (x x) )F FF FF F在解释在解释I I下求下列各式的值：下求下列各式的值：（1） x(F(x)G(x,a) （2） x(F(f(x)G(x,f(x)（3） x yL(x,y) （4） y xL(x,y)(x)f f21（1） x(F(x)G(x,a) (F(2)G(2,2) (F(3)G(3,2) (01) (11) 0 （2） x(F(f(x)G(x,f(x) (F(f(2)G(2,f(2) (F(f(3)G(3,f(3) (F(3)G(2,3) (F(2)G(3,2) (11) (01) 122（3） x

20、yL(x,y) (L(2,2)L(2,3) (L(3,2)L(3,3) (10) (01) 1（4） y xL(x,y) y(L(2,y)L(3,y) (L(2,2)L(3,2) (L(2,3)L(3,3) (10) (01) 0说明说明q 由由(3)(3)，(4)(4)的结果进一步可以说明量词的次的结果进一步可以说明量词的次序不能随意颠倒。序不能随意颠倒。 23例例5.5 证明下列等值式。证明下列等值式。 （1） x(M(x)F(x) x(M(x)F(x) （2） x(F(x)G(x) x(F(x)G(x) （3） x y(F(x)G(y)H(x，y) x y(F(x)G(y)H(x,y)

21、（4） x y(F(x)G(y)L(x，y) x y(F(x)G(y)L(x,y) 24（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) （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) 25（3） x y(F(x)G(y)H(x，y) x y(F(x)G(y)H(x,y) x y(F(x)G(y)H(x，y) x(y(F(x)G(y)H(x，y) x y(F(x)G(y)H(x，y) x y(F(x)G(y)H(x

22、,y) 26（4） x y(F(x)G(y)L(x，y) x y(F(x)G(y)L(x,y) x y(F(x)G(y)L(x，y) x ( y(F(x)G(y)L(x，y) x y(F(x)G(y)L(x，y) x y(F(x)G(y)L(x,y) x y(F(x)G(y)L(x,y) 275.2 一阶逻辑前束范式一阶逻辑前束范式定义定义5.2 设设A为一个一阶逻辑公式，若为一个一阶逻辑公式，若A具有如下形式具有如下形式Q1x1Q2x2 QkxkB则称则称A为为前束范式前束范式，其中，其中Qi(1ik)为为 或或 ，B为不含量词为不含量词的公式。的公式。如果前束范式中如果前束范式中B是析是析

23、(合合)取范式取范式, 则称为前束析则称为前束析(合合)取范取范式式.例如例如 ( x)( y)(P(x) Q(y), ( x)( y)( z)(A(x, y)B(z)都都是某公式的前束范式是某公式的前束范式 , 前一个还是合取范式前一个还是合取范式 ( x)P(x) ( y)Q(y)则不是前束公式则不是前束公式定理定理5.1 (前束范式存在定理前束范式存在定理)一阶逻辑中的任何公式都存一阶逻辑中的任何公式都存在等值的前束范式在等值的前束范式285.2 一阶逻辑前束范式一阶逻辑前束范式按如下步骤可求得谓词公式的前束析按如下步骤可求得谓词公式的前束析(合合)取范式取范式: 对约束变元进行换名对约

24、束变元进行换名, 使其互不相同使其互不相同 将谓词公式中的其它联词转化为将谓词公式中的其它联词转化为 , , 将否定词置于量词之后将否定词置于量词之后 xA(x) xA(x) xA(x) xA(x) 将所有量词的辖域扩张到整个公式将所有量词的辖域扩张到整个公式 x(A(x)B)xA(x)B x(A(x)B)xA(x)B 将不含量词部分化为析取范式或合取范式将不含量词部分化为析取范式或合取范式295.2 一阶逻辑前束范式一阶逻辑前束范式例例1 求求 ( x)P(x)( x)Q(x)的前束范式的前束范式 解解: ( x)P(x)( x)Q(x) ( x)P(x)( y)Q(y) 换名换名 ( (

25、x)P(x) ( y)Q(y) 消去消去 ( x)P(x)( y)Q(y) 后移后移 ( x)P(x) ( y)( Q(y) 后移后移 ( x)( y)(P(x)Q(y) 前移量词前移量词30说明说明q 求前束范式的过程，就是制造量词辖域可以求前束范式的过程，就是制造量词辖域可以扩大的条件，进行量词辖域扩大。扩大的条件，进行量词辖域扩大。q 任何公式的前束范式都是存在的，但一般说任何公式的前束范式都是存在的，但一般说来，并不唯一。来，并不唯一。q 利用一阶逻辑等值式以及三条变换规则（置利用一阶逻辑等值式以及三条变换规则（置换规则、换名规则、代替规则）就可以求出换规则、换名规则、代替规则）就可以

26、求出与公式等值的前束范式，或所谓公式的前束与公式等值的前束范式，或所谓公式的前束范式。范式。31例例5.6 求公式的前束范式求公式的前束范式（1） xF(x) xG(x) xF(x) yG(y) (换名规则换名规则) xF(x) yG(y) (5.2)第二式第二式) x(F(x) yG(y) (5.3)第二式第二式) x y(F(x)G(y) (5.3)第二式第二式) （ y x(F(x)G(y) ）或者或者 xF(x) xG(x) xF(x) xG(x) (5.2)第二式第二式) x(F(x)G(x) (5.5)第一式第一式) 说明说明q 公式的前束范式是不唯一的。公式的前束范式是不唯一的。

27、32（2） xF(x) xG(x) xF(x) xG(x) (5.2)第二式第二式) xF(x) yG(y) (换名规则换名规则) x(F(x) yG(y) (5.3)第一式第一式) x y(F(x)G(y) (5.3)第一式第一式) 33例例5.7 求前束范式求前束范式(1) xF(x) xG(x) yF(y) xG(x) y x(F(y)G(x)(2) xF(x) xG(x) yF(y) xG(x) y x(F(y)G(x)(3) xF(x) xG(x) yF(y) xG(x) y x(F(y)G(x)(4) xF(x) yG(y) x y(F(x)G(y)34例例5.8 求公式的前束范式

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

29、 x2G(x2) x1H(x1,x2,x3) ( x4F(x4,x2) x5G(x5) x1H(x1,x2,x3) x4 x5(F(x4,x2) G(x5) x1H(x1,x2,x3) x4 x5 x1(F(x4,x2) G(x5) H(x1,x2,x3) 365.3 一阶逻辑的推理理论一阶逻辑的推理理论在一阶逻辑中，从前提在一阶逻辑中，从前提A1,A2,Ak出发推结论出发推结论B的推理形的推理形式结构，依然采用如下的蕴涵式形式式结构，依然采用如下的蕴涵式形式A1A2 Ak B （5.6）若式（若式（5.6）为永真式，则称）为永真式，则称推理正确推理正确，否则称推理不正，否则称推理不正确。确。

30、于是，在一阶逻辑中判断推理是否正确也归结为判断于是，在一阶逻辑中判断推理是否正确也归结为判断（5.6）式是否为永真式了。）式是否为永真式了。在一阶逻辑中称永真式的蕴涵式为在一阶逻辑中称永真式的蕴涵式为推理定律推理定律，若一个推，若一个推理的形式结构正是某条推理定律，则这个推理显然是正理的形式结构正是某条推理定律，则这个推理显然是正确的。确的。在一阶逻辑的推理中，某些前提与结论可能是受量词限在一阶逻辑的推理中，某些前提与结论可能是受量词限制，为了使用命题逻辑中的等值式和推理定律，制，为了使用命题逻辑中的等值式和推理定律，必须在必须在推理过程中有消去和添加量词的规则推理过程中有消去和添加量词的规则

31、，以便使谓词演算以便使谓词演算公式的推理过程可类似于命题演算中推理理论那样进行。公式的推理过程可类似于命题演算中推理理论那样进行。37推理定律的来源推理定律的来源命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例由基本等值式生成的推理定律由基本等值式生成的推理定律一些重要的推理定律一些重要的推理定律推理规则推理规则量词消去和引入规则量词消去和引入规则38命题逻辑推理定律的代换实例命题逻辑推理定律的代换实例 xF(x) yG(y) xF(x) （化简律的代换实例）（化简律的代换实例） xF(x) xF(x) yG(y) （附加律的代换实例）（附加律的代换实例） 39由基本等值式生成的推理定律由

32、基本等值式生成的推理定律 xF(x) xF(x) xF(x) xF(x) xF(x) xF(x) xF(x) xF(x) 40其他推理定律其他推理定律 xA(x) xB(x) x(A(x)B(x) x(A(x)B(x) xA(x) xB(x) x(A(x)B(x) xA(x) xB(x) xA(x) xB(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)的讨论的讨论若若 x(A(x)B(x)x(A(x)B(x)为真，则有一个客体为真，则有一个客体c c，使得，使得A(c)B(c)A(c)B(c)为真，即为真，即A(c)

33、A(c)和和B(c)B(c)都为真，所以都为真，所以 xA(x)xA(x) xB(x)xB(x)也为真。也为真。 41推理规则推理规则为了构造推理系统，还要给出为了构造推理系统，还要给出4条重要的推理规则条重要的推理规则,即消去量词和引入量词的规则：即消去量词和引入量词的规则：1全称量词消去规则全称量词消去规则(简记为简记为-)2全称量词引入规则全称量词引入规则(简记为简记为+)3存在量词引入规则存在量词引入规则(简称为简称为+)4存在量词消去规则存在量词消去规则(简记为简记为-)42全称量词消去规则全称量词消去规则(简记为简记为-)含义含义：如果个体域的所有元素都具有性质：如果个体域的所有元

34、素都具有性质A，则个体域中的任，则个体域中的任一元素具有性质一元素具有性质A。 两式成立的条件两式成立的条件： 其中其中x,y是个体变项符号是个体变项符号,c是个体常项符号是个体常项符号,且在且在A中中x不在不在y和和y的辖域内自由出现的辖域内自由出现A A( (c c) )x xA A( (x x) )或或A A( (y y) )x xA A( (x x) )举例举例考虑个体域为实数集合，公式考虑个体域为实数集合，公式A(x)=A(x)= yF(x,y), yF(x,y), F(x,y)为为xyxy。当对公式当对公式 xA(x)=xA(x)= x x yF(x,y)yF(x,y)使用使用-时

35、时，用，用y y取代取代x x，就，就会得到会得到A(y)=A(y)= yF(y,y)yF(y,y)，即，即 y(yy)y(yy)，这显然是假命题。，这显然是假命题。原因是违背了公式成立的条件。原因是违背了公式成立的条件。43全称量词引入规则全称量词引入规则(简记为简记为+)该式成立的条件是：该式成立的条件是： x是个体变项符号是个体变项符号,且不在前提且不在前提的任何公式中自由出现的任何公式中自由出现x xA A( (x x) )A A( (x x) )举例举例由前提由前提: :P(x)Q(x), ,P(x)推出结论推出结论: xQ(x) 取解释取解释I:I:个体域为整数集合个体域为整数集合

36、, P(x):x是偶数，是偶数，Q(x):x被被2整整除，在除，在I下，下，P(x)Q(x)为真，为真，P(x)的真值不定，的真值不定， xQ(x)为假，故这个推理是错误的。为假，故这个推理是错误的。错误的原因是应用错误的原因是应用+时，时，x在前提的公式中自由出现。在前提的公式中自由出现。 44存在量词引入规则存在量词引入规则(简称简称+) 该式成立的条件是：该式成立的条件是： x,y是个体变项符号是个体变项符号,c是个体常项是个体常项符号符号,并且在并且在A中中y和和c分别不在分别不在x和和x的辖域内自由出现和出现的辖域内自由出现和出现)()()()(xxAByABxxAyA或)()()(

37、)(xxABcABxxAcA或举例举例取个体域为实数集，取个体域为实数集，F(x,y)F(x,y)为为xyxy，取，取A(5)=A(5)= xF(x,5)xF(x,5)。显然显然A(5)A(5)是真命题。是真命题。在应用在应用+时，得时，得 x x xF(x,x)=xF(x,x)= x(xx)x(xx)，这是假命题。，这是假命题。产生这种错误的原因是违背了公式成立的条件。产生这种错误的原因是违背了公式成立的条件。45存在量词消去规则存在量词消去规则(简记为简记为-)BxxABxA)()(其中其中x是个体变项符号是个体变项符号,且不在前提且不在前提的任何公式和的任何公式和B中中自由出现自由出现4

38、6定义定义5.3 自然推理系统自然推理系统N 定义定义1.字母表。同一阶语言字母表。同一阶语言 的字母表。的字母表。2.合式公式。同合式公式。同 的的合式公式的定义。合式公式的定义。3.推理规则：推理规则：(1)前提引入规则。前提引入规则。(2)结论引入规则。结论引入规则。(3)置换规则。置换规则。(4)假言推理规则。假言推理规则。(5)附加规则。附加规则。(6)化简规则。化简规则。(7)拒取式规则。拒取式规则。(8)假言三段论规则。假言三段论规则。(9)(9)析取三段论规则。析取三段论规则。(10)(10)构造性二难推理规则。构造性二难推理规则。(11)(11)合取引入规则。合取引入规则。(

39、12)(12)-规则。规则。(13)(13)+规则。规则。(14)(14)-规则。规则。(15)(15)+规则。规则。47例题例题例题例题 在自然推理系统中，构造下面推理的证明在自然推理系统中，构造下面推理的证明所有的人都是要死的，苏格拉底是人，所以苏格拉底是所有的人都是要死的，苏格拉底是人，所以苏格拉底是要要死的。死的。 解解：先将原子命题符号化。：先将原子命题符号化。 设设 F(x):x是人，是人，G(x):x是要死的，是要死的，s：苏格拉底。：苏格拉底。 前提：前提： x(F(x)G(x), F(s) 结论：结论：G(s)证明：证明： x(F(x)G(x)前提引入前提引入 F(s)G(s

40、) -规则规则 F(s) 前提引入前提引入 G(s) 假言推理假言推理485.3 一阶逻辑的推理理论一阶逻辑的推理理论例例5.9. 在自然推理系统在自然推理系统N 中，构造下面推理的证明中，构造下面推理的证明 任何任何自然数都是整数自然数都是整数; 存在着自然数存在着自然数; 所以存在着整数。所以存在着整数。 个体域为实数集合个体域为实数集合R。 解解:设设 F(x):x为自然数，为自然数，G(x):x为整数为整数 前提前提: x(F(x)G(x), xF(x) 结论结论:xG(x) 证明证明； x(F(x)G(x) 前提引入前提引入 F(x)G(x) - F(x)xG(x) + xF(x)x

41、G(x) - xF(x) 前提引入前提引入 xG(x) 假言推理假言推理49例例5.10例例5.10 在在自然推理系统自然推理系统N 中中,构造下面推理的证明。构造下面推理的证明。前提：前提： x(F(x)G(x), x(F(x)H(x)结论：结论： x(G(x)H(x) x(F(x)G(x) 前提引入前提引入 F(x)G(x) - F(x)H(x) F(x) 化简规则化简规则 F(x)H(x) G(x) 假言三段论假言三段论 F(x)H(x) H(x) 化简规则化简规则 (F(x)H(x)G(x) 置换置换 (F(x)H(x)H(x) 置换置换 (F(x)H(x)G(x)(F(x)H(x)H

42、(x) 合取引入合取引入 50(F(x)H(x)(G(x)H(x) 置换置换F(x)H(x) G(x)H(x) 置换置换 F(x)H(x) x(G(x)H(x) + x(F(x)H(x) x(G(x)H(x) - x(F(x)H(x) 前提引入前提引入 x(G(x)H(x) 假言推理假言推理51例例5.11例例5.11 在自然推理系统在自然推理系统N 中，构造下面推理的证明：中，构造下面推理的证明：不存在能表示成分数的无理数不存在能表示成分数的无理数.有理数都能表示成分数。有理数都能表示成分数。因此，有理数都不是无理数。因此，有理数都不是无理数。个体域为实数集合。个体域为实数集合。设设 F(x

43、):x为无理数，为无理数， G(x):x为有理数，为有理数， H(x):x能表示成分数。能表示成分数。前提：前提： x(F(x)H(x)， x(G(x)H(x)结论：结论： x(G(x) F(x)解答解答525.3 一阶逻辑的推理理论一阶逻辑的推理理论前提：前提： x(F(x)H(x)， x(G(x)H(x)结论：结论： x(G(x) F(x)证明证明: x(F(x)H(x) 前提引入前提引入 x(F(x)H(x) 置换置换 x(H(x)F(x) 置换置换 H(x)F(x) - x(G(x)H(x) 前提引入前提引入 G(x)H(x) - G(x)F(x) 假言三段论假言三段论 x(G(x)F(x) +53第五章第五章 习题