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

1、1主要内容主要内容l 一阶逻辑等值式与基本的等值式一阶逻辑等值式与基本的等值式l 置换规则、换名规则、代替规则置换规则、换名规则、代替规则l 前束范式前束范式l 自然推理系统自然推理系统NL 及其推理规则及其推理规则第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理25.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则在一阶逻辑中，有些命题可以有不同的形式在一阶逻辑中，有些命题可以有不同的形式例如命题：没有不犯错误的人。例如命题：没有不犯错误的人。 设设F(x): x是人，是人，G(x): x犯错误犯错误 (1) x(F(x)G(x) 或或 (2) x(F(x)G(x)定义定义5.

2、1 设设A, B是两个谓词公式是两个谓词公式, 如果如果AB是永真式是永真式, 则称则称A与与B等值等值, 记作记作AB, 并称并称AB是是等值式等值式 显然，A B当且仅当在任何解释I和I中的任意赋值下，A与B有相同的真值。即在I和下,A为真当且仅当B为真，或者，A为假当且仅当B为假。 同时，要证明两个公式不等值，只需找到一个解释I和I中的一个赋值，使得两个公式在I和下，一个为真，另一个为假。35.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则由定义由定义5.1 可知，判断公式可知，判断公式A与与 B是否是否等值等值，等价于，等价于判断公式判断公式AB是否为永真式是否为永真式, 同命题

3、逻辑中一样，证明了一些常同命题逻辑中一样，证明了一些常用的重要等值式，并用这些等值式推演出更多的等值式用的重要等值式，并用这些等值式推演出更多的等值式基本等值式基本等值式第一组第一组 命题逻辑中命题逻辑中16组基本等值式的代换实例组基本等值式的代换实例 例如，例如，AA (2.1) xF(x)xF(x), AB A B (2.12) xF(x)yG(y) xF(x)yG(y) 等等第二组第二组 (1) 消去量词等值式消去量词等值式 设个体为有限集设个体为有限集D =a1, a2, , an xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an)4基本等值

4、式基本等值式(2) 量词否定等值式量词否定等值式 xA(x) x A(x) xA(x) x A(x)证明证明(1) 在任何解释在任何解释I下，下， xA(x) 表示表示“在个体域在个体域D中，并非所有的中，并非所有的x都具有性质都具有性质A”， 而而 x A(x) 表示表示“在个体域在个体域D中，至少有一个中，至少有一个x不具有不具有性质性质A”， 两个命题的含义是一样的，因此它们同真或同假，它两个命题的含义是一样的，因此它们同真或同假，它们是等值的。们是等值的。(2)在个体域在个体域D中，中，”不存在有性质不存在有性质A的的x”与与“所有的所有的x都没有性质都没有性质A”是同一回事。是同一回

5、事。5基本等值式基本等值式(3) 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式. 设设A(x) 是含是含 x 自由出现的公式，自由出现的公式，B 中不含中不含 x 的自的自由出现。则：由出现。则： 关于全称量词的：关于全称量词的： x(A(x) B) xA(x) B x(A(x) B) xA(x) B x(A(x)B) xA(x)B x(BA(x) BxA(x) 6证明证明证明(1) x(A(x) B) xA(x) B在任何解释在任何解释I和和I中的任意赋值中的任意赋值下，下， xA(x) B = 0 （ 表示取大）表示取大） 当且仅当当且仅当 xA(x)=0 且且 B=0 （只能每项都取

6、（只能每项都取0） 当且仅当当且仅当B=0 且且 对于对于DI中的每一个元素中的每一个元素c，有，有 A(c)=0当且仅当对于当且仅当对于DI中的每一个元素中的每一个元素c，有，有 A(c)B=0当且仅当当且仅当 x(A(x)B)=0 (2) x(A(x) B) xA(x) B 在任何解释在任何解释I和和I中的任意赋值中的任意赋值下，下， xA(x)B=1 （ 表示取小）表示取小） 当且仅当当且仅当 xA(x)=1 且且 B=1 （只能每项都取（只能每项都取1）当且仅当当且仅当B=1 且且 对于对于DI中的每一个元素中的每一个元素c，A(c)=1当且仅当对于当且仅当对于DI中的每一个元素中的每

7、一个元素c，A(c)B=1当且仅当当且仅当 x(A(x) B)=17证明证明证明第第(3)式式: x(A(x)B) xA(x)B x(A(x)B) x( A(x)B) x A(x)B (5.3) xA(x)B (5.2) xA(x)B 第第(4)式式: x(BA(x) BxA(x) x(BA(x) x( B A(x) B xA(x) (5.3) BxA(x)8基本等值式基本等值式 关于存在量词的：关于存在量词的： x(A(x) B) xA(x) B x(A(x) B) xA(x) B x(A(x)B) xA(x)B x(BA(x) BxA(x)证明：方法一：证明：方法一：(2) x(A(x)

8、B) xA(x) B xA(x) B ( ( xA(x) B) (xA(x)B ) ( x A(x)B) ( x( A(x)B) ( x (A(x) B) x(A(x) B)9证明证明证明 方法二：方法二：(1) x(A(x) B) xA(x) B在任何解释在任何解释I和和I中的任意赋值中的任意赋值下，下， xA(x) B= 0 （ 表示取大）表示取大） 当且仅当当且仅当 xA(x)=0 且且 B=0 （只能每项都取（只能每项都取0） 当且仅当当且仅当B=0 且且 存在存在DI中的元素中的元素c，使得，使得A(c)=0当且仅当存在当且仅当存在DI中的元素中的元素c，使得，使得A(c)B=0当且

9、仅当当且仅当 x(A(x) B) =0 (2) x(A(x) B) xA(x) B 在任何解释在任何解释I和和I中的任意赋值中的任意赋值下，下， xA(x) B=1 （ 表示取小）表示取小） 当且仅当当且仅当 xA(x)=1 且且 B=1 （只能每项都取（只能每项都取1）当且仅当当且仅当 B=1 且且 存在存在DI中的元素中的元素c，A(c)=1当且仅当当且仅当 存在存在DI中的元素中的元素c，A(c)B=1当且仅当当且仅当 x(A(x) B)=110基本等值式基本等值式 (4) 量词分配等值式量词分配等值式 x(A(x) B(x) xA(x)xB(x) x(A(x) B(x) xA(x)xB

10、(x)证明证明(1) 在任何解释I和I中的任意赋值下， x(A(x)B(x)=1 当且仅当对于DI中的每一个元素c，A(c)B(c)=1当且仅当对于DI中的每一个元素c，A(c)=1 且 B(c)=1当且仅当 xA(x)=1 且 xB(x)=1当且仅当 xA(x) xB(x)=1注意：注意： 对对 ， 对对 无分配律，见例无分配律，见例5.211证明证明例例5.2 证明证明（1）x(A(x)B(x)不等值于xA(x)xB(x)（2）x(A(x)B(x)不等值于xA(x)xB(x)证明证明给定解释I： DI为自然数集，A(x)为x是奇数，B(x)为x是偶数。在DI下， x(A(x)B(x)意为“

11、所有的自然数，或是奇数，或是偶数”，是真命题，而 xA(x) xB(x)意为“所有的自然数是奇数，或者所有的自然数是偶数”，是假命题。 因此，x(A(x)B(x)与 xA(x)xB(x)不等值。 (2) x(A(x)B(x)意为“存在着自然数x，x既是奇数又是偶数”，显然这是一个假命题， 而xA(x)xB(x)意为“有自然数是奇数并且也有自然数是偶数”，是真命题， 因此，xA(x)xB(x)与x(A(x)B(x)不等值。12置换规则、换名规则、代替规则置换规则、换名规则、代替规则1. 置换规则置换规则 设设 (A)是含是含A的公式的公式, 那么那么, 若若AB, 则则 (A) (B).2. 换

12、名规则换名规则 设设A为一公式，将为一公式，将A中某量词辖域中个体变项的所有中某量词辖域中个体变项的所有约束约束 出现出现及相应的指导变元换成该量词辖域中未曾出现过的个及相应的指导变元换成该量词辖域中未曾出现过的个 体变项符号，其余部分不变，设所得公式为体变项符号，其余部分不变，设所得公式为A ，则，则AA.3. 代替规则代替规则 设设A为一公式，将为一公式，将A中某个个体变项的所有中某个个体变项的所有自由出现自由出现用用A中中 未曾出现过的个体变项符号代替，其余部分不变，设所得未曾出现过的个体变项符号代替，其余部分不变，设所得 公式为公式为A ，则，则AA.13实例实例例例5.1 将公式化成

13、等值的不含既有约束出现、又有自由出现将公式化成等值的不含既有约束出现、又有自由出现的个体变项的个体变项: (1) xF(x,y,z)yG(x,y,z)解解 : 公式中x,y都是既有约束出现、又有自由出现的个体变项 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)yG(x,y,z) 代替规则代替规则 xF(x,t,z)yG(w,y,z) 代替规则代替规则14实例实例例例5.1 将公式化成等值的不含既有约束出现、又有自由出现将公式化成

14、等值的不含既有约束出现、又有自由出现的个体变项的个体变项: (2) x(F(x,y)yG(x,y,z)解解 公式中y都是既有约束出现 yG(x,y,z)、又有自由出现 F(x,y)的个体变项，需要处理。x只有约束出现 ，z只有自由出现，保持不变。 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) 换名规则换名规则 15实例实例例例5.1 将公式化成等值的不含既有约束出现、又有自由出现将公式化成等值的不含既有约束出现、又有自由出现的个体变项的个体变项: (3) x(F(x,

15、y,z)yG(x,y,z)解解 x(F(x,y,z)yG(x,y,z) x(F(x,y,z) tG(x,t,z) 换名规则换名规则 x t(F(x,y,z)G(x,t,z) 辖域扩张等值式辖域扩张等值式或者或者 x(F(x,y,z)yG(x,y,z) x(F(x,u,z)yG(x,y,z) 代替规则代替规则 x y(F(x,u,z)G(x,y,z) 辖域扩张等值式辖域扩张等值式16实例实例例例3 设个体域设个体域D=a,b,c, 消去下述公式中的量词消去下述公式中的量词: (1) x y(F(x)G(y)(2) x yF(x,y)解法一解法一 x y(F(x)G(y) ( y(F(a)G(y)

16、 ( y(F(b)G(y) ( y(F(c)G(y) (F(a)G(a) (F(a)G(b) (F(a)G(c) (F(b)G(a) (F(b)G(b) (F(b)G(c) (F(c)G(a) (F(c)G(b) (F(c)G(c) 17实例实例解法二解法二 x y(F(x)G(y) x(F(x)yG(y) 辖域缩小等值式辖域缩小等值式 x(F(x)G(a) G(b) G(c) (F(a)G(a) G(b) G(c) (F(b)G(a) G(b) G(c) (F(c)G(a) G(b) G(c)18实例实例(2) x yF(x,y) x yF(x,y) x(F(x,a) F(x,b) F(x,

17、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)19实例实例例5.4 给定解释I如下（1）个体域D=2、3（2）D中特定元素a=2（3） D中特定函数f(x): f(2)=3、f(3)=2（4）D上的特定谓词G（x、y)为：G（2、2）=G（2、3）=G（3、2）=1，G（3、3）=0L（2、2）=L（3、3）=1、L（2、3）=L（3、2）=0F（x）为: F（2）=0、F（3）=1在I下求下列各式的真值(1)x(F(x)G(x、a)(2)x(F(f(x)G(x、f(x)(3)xyL(x、y)(4)xyL

18、(x、y)20实例实例(类似例类似例5.4 )设解释设解释I为：为：DI=2，3，f(2)=3，f(3)=2， F(2，2)=F(2，3)=0，F(3，2)=F(3，3)=1。 在在I下消去下列公式的量词并求真值。下消去下列公式的量词并求真值。(1) F(2，f(2)F(3，f(3)(2)xyF(y，x)(3)x(F(x,f(x)yF(f(x),f(y)解(1) 式中不含量词，所以直接求真值。式中不含量词，所以直接求真值。F(2，f(2)F(3，f(3) F(2，3)F(3，2) 01 021(2) xyF(y,x) x(F(2，x)F(3，x) (F(2，2)F(3，2)(F(2，3)F(3

19、，3) (01)(01) 11 1(类似例类似例5.4 )设解释设解释I为：为：DI=2，3，f(2)=3，f(3)=2， F(2，2)=F(2，3)=0，F(3，2)=F(3，3)=1。22(3) x( F(x，f(x)yF(f(x)，f(y) ) (F(2,f(2)yF(f(2), f(y)(F(3, f(3)yF(f(3), f(y)(F(2,f(2)(F(f(2), f(2)F(f(2), f(3)(F(3, f(3)(F(f(3), f(2)F(f(3), f(3) (F(2,3)(F(3,3)F(3,2)(F(3,2)(F(2, 3)F(2, 2) (0(11)(1(00) (01

20、)(10) 10 0(类似例类似例5.4 )设解释设解释I为：为：DI=2，3，f(2)=3，f(3)=2， F(2，2)=F(2，3)=0，F(3，2)=F(3，3)=1。23实例实例例例1 (例例5.5)将下面命题用两种形式符号化将下面命题用两种形式符号化, 并证明两者等值并证明两者等值: (1) 没有不犯错误的人没有不犯错误的人解解 令令F(x)：x是人，是人，G(x)：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) 置换置换24实例

21、实例(2) 不是所有的人都爱看电影不是所有的人都爱看电影解解 令令F(x)：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) 置换置换25实例实例例5.5证明下列各等值式。（1）x(M(x)F(x)x(Mx)F(x)（2）x(F(x)G(x)x(F(x)G(x)（3）xy(F(x)G(y)H(x,y)xy(F(x)G(y)H(x,y)（4）xy(F(x)G(y)L(x,y)xy(F(x)G(y)L(x,y)证明（3

22、）xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y) x(y(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y)（4）xy(F(x)G(y)L(x,y) x(y(F(x)G(y)L(x,y) xy(F(x)G(y)L(x,y) xy(F(x)G(y)L(x,y) xy(F(x)G(y)L(x,y)265.2 一阶逻辑前束范式一阶逻辑前束范式定义定义5.2 设设A为一个一阶逻辑公式，若为一个一阶逻辑公式，若A具有如下形式具有如下形式 Q1x1Q2x2QkxkB则称则称A为为前束范式前束范式，其中，其中Qi (1 i k)为为

23、或或 ，B为不含量词为不含量词的公式的公式. 例如，例如， x (F(x) G(x) x y(F(x)(G(y) H(x,y) 是前束范式是前束范式而而 x(F(x) G(x) x(F(x)y(G(y) H(x,y) 不是前束范式，不是前束范式， 在命题逻辑中，我们介绍过析取范式和合取范式，利用它们可将命题公式表示为统一的形式，为我们讨论问题提供了方便。下面我们介绍一阶逻辑中的范式概念前束范式。27前束范式存在定理前束范式存在定理定理定理5.1（前束范式存在定理）（前束范式存在定理） 一阶逻辑中的任何公式都存在与之等值的前束范式一阶逻辑中的任何公式都存在与之等值的前束范式例例4 求下列公式的前

24、束范式求下列公式的前束范式 (1) x(M(x) F(x)解解 x(M(x) F(x) x( M(x)F(x) （量词否定等值式）（量词否定等值式） x(M(x)F(x) 后两步结果都是前束范式，说明公式的前束范式不惟一后两步结果都是前束范式，说明公式的前束范式不惟一.28求前束范式的实例求前束范式的实例 (2) xF(x)xG(x)解解 xF(x)xG(x) xF(x)x G(x) （量词否定等值式）（量词否定等值式） x(F(x)G(x) （量词分配等值式）（量词分配等值式）或或 xF(x)xG(x) xF(x)x G(x) 量词否定等值式量词否定等值式 xF(x)y G(y) 换名规则换

25、名规则 x y(F(x)G(y) 辖域收缩扩张规则辖域收缩扩张规则29求前束范式的实例求前束范式的实例(3) xF(x)y(G(x,y)H(y)或或 xF(x)y(G(x,y)H(y) xF(x)y(G(z,y)H(y) 代替规则代替规则 x y(F(x)(G(z,y)H(y) 解解 xF(x)y(G(x,y)H(y) zF(z)y(G(x,y)H(y) 换名规则换名规则 z y(F(z)(G(x,y)H(y) 辖域收缩扩张规则辖域收缩扩张规则30化为前束范式的过程化为前束范式的过程 在一阶逻辑推理中，需要将公式化成前束范式形式，这总在一阶逻辑推理中，需要将公式化成前束范式形式，这总是可以办到

26、的。是可以办到的。 即任何一个一阶公式均可等值演算成前即任何一个一阶公式均可等值演算成前束范式，化归过程如下：束范式，化归过程如下： (1) 消去除消去除 、之外的联结词；之外的联结词；(2) 将否定符将否定符 移到量词符后；移到量词符后；(3) 换名使各变元不同名；换名使各变元不同名；(4) 扩大辖域使所有量词处在最前面。扩大辖域使所有量词处在最前面。说明说明1 化归过程需遵守置换规则和换名规则化归过程需遵守置换规则和换名规则(也可用代替规也可用代替规则则)。说明说明2 过程过程(1)是为了方便地使用量词辖域扩缩律是为了方便地使用量词辖域扩缩律(5.3)(5.4)。由此可知，公式的前束范式形

27、式并不唯一。由此可知，公式的前束范式形式并不唯一。31实例书本实例书本例5.6求下面公式的前束泛式（1） xF(x)xG(x)（2） xF(x)xG(x)例5.7求下面公式的前束泛式,填出每一步的依据（1） xF(x)xG(x) （3） xF(x)xG(x)例5.8 求下面公式的前束泛式(1) xF(x,y)yG(x,y)(2)( x1F(x1,x2)x2G(x2)x1H(x1,x2,x3)32实例书本实例书本例例5.7求下面公式的前束泛式,填出每一步的依据（1） xF(x)xG(x) （2） xF(x)xG(x)（3） xF(x)xG(x)解: (1) xF(x)xG(x) yF(y)xG(

28、x) 换名规则换名规则 y(F(y)xG(x) (5.4式二式二) y x(F(y) G(x) (5.4式二式二)（3） xF(x)xG(x) yF(y)xG(x) 换名规则换名规则 y(F(y)xG(x) y x(F(y)G(x)33实例书本实例书本例例5.8 求下面公式的前束泛式(1) xF(x,y)yG(x,y)(2)( x1 F(x1, x2 )x2G(x2)x1H(x1,x2,x3)解：解：（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,

29、t)yG(w,y) 代替规则代替规则 x y(F(x,t)G(w,y) (5.3),(5.4)34实例书本实例书本例例5.8 求下面公式的前束泛式(1) xF(x,y)yG(x,y)(2)( x1F(x1, x2)x2G(x2)x1H(x1,x2,x3)解：解：（2） ( x1F(x1, x2)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) (5.3),(5.4) x4 x5 x1(F(x4, x2)G(x5)H(x1,x2,x3) (5.3),(

30、5.4) 355.3 一阶逻辑的推论理论一阶逻辑的推论理论由于谓词演算是在命题演算的基础上，进一步扩大了谓词与由于谓词演算是在命题演算的基础上，进一步扩大了谓词与量词的功能，因此容易想到，命题演算中有关推理演绎的量词的功能，因此容易想到，命题演算中有关推理演绎的规则基本上适用于谓词演算，即在命题逻辑中的各项推理规则基本上适用于谓词演算，即在命题逻辑中的各项推理规则在一阶逻辑推理中仍然适用，当然也会有不少只适用规则在一阶逻辑推理中仍然适用，当然也会有不少只适用于谓词演算的概念与规则。于谓词演算的概念与规则。在一阶逻辑中，由前提A1, A2, Ak 出发推出结论B的形式结构仍然是A1A2Ak B。

31、如果此式是永真式永真式，则称由前提A1, A2, Ak 推出结论B的推理推理正确正确， 记作A1A2Ak B 或者A1, A2, Ak B，否则称推理不正确。365.3 一阶逻辑的推论理论一阶逻辑的推论理论推理的形式结构推理的形式结构1. A1 A2Ak B 若此式是永真式若此式是永真式, 则称推理正确则称推理正确, 记作记作A1 A2Ak B2. 前提前提: A1, A2, Ak 结论结论: B推理定理推理定理: 永真式的蕴涵式永真式的蕴涵式37推理定理推理定理第一组第一组 命题逻辑推理定理的代换实例命题逻辑推理定理的代换实例 如如, xF(x)yG(y) xF(x) xF(x) yG(y)

32、 xF(x) xF(x) xF(x) yG(y) 第二组第二组 基本等值式生成的推理定理基本等值式生成的推理定理 如如, xF(x) xF(x), xF(x) xF(x) xF(x)x F(x), x F(x) xF(x)38推理定理推理定理第三组第三组 其他常用推理定律其他常用推理定律 (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)39量词消去引入规则量词消去引入规则1. 全称量词消去规则全称量词消去规则( -，UI) 或或 其中其

33、中(1)x,y是个体变项符号是个体变项符号, c是个体常项符号是个体常项符号, 且在且在A中中x不在不在 y和和 y的辖域内自由出现的辖域内自由出现.(2)A(y)(或A(c)中约束变元个数与A(x)中约束变元个数相同。2. 全称量词引入规则全称量词引入规则( +，UG) 其中其中x是个体变项符号是个体变项符号, 且不在前提的任何公式中自由出现且不在前提的任何公式中自由出现 xA(x)A(y) xA(x)A(c) A(x)xA(x)40量词消去引入规则量词消去引入规则3. 存在量词消去规则存在量词消去规则( -，EI) 其中其中x是个体变项符号是个体变项符号, 且不在前提的任何公式和且不在前提

34、的任何公式和B中自由中自由出现出现,其中（其中（1）c是特定的个体常项符号是特定的个体常项符号, （2）xA(x)是闭式且且c不不A(x)中出现中出现. A(x)BxA(x)B xA(x) A(c)41量词消去引入规则量词消去引入规则4. 存在量词引入消去规则存在量词引入消去规则( +，EG) 或或 或或其中其中x,y是个体变项符号是个体变项符号, c是个体常项符号是个体常项符号, 且在且在A中中y和和c不在不在 x和和 x的辖域内自由出现的辖域内自由出现. BA(y)BxA(x) BA(c)BxA(x) A(y)xA(x) A(c)xA(x)42【例A】设前提为设前提为xyF(x,y) ，下

35、面推理是否正确？，下面推理是否正确？(1) xyF(x,y) 前提引入前提引入(2) yF(y,y) (1)UI解： xyF(x,y) yF(y,y) 的推理并不正确。的推理并不正确。如果给定解释如果给定解释I： 个体域为实数集，个体域为实数集，F(x，y)：xy，则则xyF(x,y) 意为意为“对于每个实数对于每个实数x， 均存在着比之更小均存在着比之更小的实数的实数y”，这是一个真命题。，这是一个真命题。而而yF(y,y) 意为意为“存在着比自己小的实数存在着比自己小的实数”，是假命题。，是假命题。之所以出现这样的错误，是违反了之所以出现这样的错误，是违反了UI规则成立的条件规则成立的条件

36、(2)。43实例解析实例解析例例B 设个体域为实数集合，设个体域为实数集合，F(x,y)为为 x y, 指出在推理系统指出在推理系统F中，以中，以xyF(x,y)(真命题）为前提，推真命题）为前提，推出出xF(x,c)（假命题）（假命题）,或或yxF(x,y)的原因的原因. (1) xyF(x,y) 前提引入前提引入 (2) yF(z,y) UI规则规则 (3) F(z,c) EI规则规则 (4)xF(x,c) UG规则规则 (5)yxF(x,y) EG规则规则解：xyF(x,y) yx F(x,y)的推理并不正确。取与例的推理并不正确。取与例A相同的解释，则由相同的解释，则由xyF(x,y)

37、 为真，而为真，而yxF(x,y) 意为意为“存在着最小实数存在着最小实数”，是假命题，知推理不正确。之所以出，是假命题，知推理不正确。之所以出现这样的错误，是第现这样的错误，是第(3)步违反了步违反了EI规则成立的条件规则成立的条件(2)。44自然推理系统自然推理系统NL定义定义5.3 自然推理系统自然推理系统NL 定义如下定义如下:1. 字母表字母表. 同一阶语言同一阶语言L 的字母表的字母表2. 合式公式合式公式. 同同L 的合式公式的合式公式3. 推理规则推理规则:(1) 前提引入规则前提引入规则(2) 结论引入规则结论引入规则(3) 置换规则置换规则(4) 假言推理规则假言推理规则(

38、5) 附加规则附加规则(6) 化简规则化简规则(7) 拒取式规则拒取式规则45自然推理系统自然推理系统NL(8) 假言三段论规则假言三段论规则(9) 析取三段论规则析取三段论规则(10) 构造性二难推理规则构造性二难推理规则(11) 合取引入规则合取引入规则(12) -规则规则(13) +规则规则(14) -规则规则(15) +规则规则 设前提设前提A1, A2, Ak,结论结论B及公式序列及公式序列C1, C2, Cl. 如果每如果每一个一个Ci(1 i l)是某个是某个Aj, 或者可由序列中前面的公式应用推或者可由序列中前面的公式应用推理规则得到理规则得到, 并且并且Cl =B, 则称这个

39、公式序列则称这个公式序列C1, C2, Cl是是由由A1, A2, Ak推出推出B的的证明证明46重要提示重要提示yxyxF :),(要特别注意使用要特别注意使用 -、 +、 -、 +规则的条件规则的条件.反例反例1. 对对A= x yF(x,y)使用使用 -规则规则, 推得推得B= yF(y,y). 取解释取解释I: 个体域为个体域为R, 在在I下下A被解释为被解释为 x y(xy), 真真; 而而B被解释为被解释为 y(yy), 假假 原因原因: 在在A中中x自由出现自由出现在在 y的辖域的辖域F(x,y)内内反例反例2. 前提前提: P(x)Q(x), P(x) 结论结论: xQ(x)

40、取解释取解释I: 个体域为个体域为Z, 在在I下前提为下前提为真真, 结论为假结论为假, 从而推理不正确从而推理不正确整整除除被被是是偶偶数数2:)(,:)(xxQxxP47反例反例2(续续)“证明证明”: P(x)Q(x) 前提引入前提引入 P(x) 前提引入前提引入 Q(x) 假言推理假言推理 xQ(x) +错误原因错误原因: 在使用在使用 +规则规则, 而而x在前提的公式中自由出现在前提的公式中自由出现.48构造推理证明的实例构造推理证明的实例例例5 .9 在自然推理系统在自然推理系统NL 中构造下面推理的证明中构造下面推理的证明, 取个体域取个体域R: 任何自然数都是整数任何自然数都是

41、整数. 存在自然数存在自然数. 所以所以, 存在整数存在整数.解解 设设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)xG(x) - xF(x) 前提引入前提引入 xG(x) 假言推理假言推理 49构造推理证明的实例构造推理证明的实例例例5 .10 在自然推理系统在自然推理系统NL 中构造下面推理的证明中构造下面推理的证明.前提: x(F(x)G(x), x(F(x) H(x) ，结论: xG(x) x(F(

42、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(x) 合取合取引入引入 (F(x)H(x) (G(x)H(x) 置换置换F(x)H(x)G(x)H(x) 置换置换(11) F(x)H(x)x(G(x)H(x) + (12) x(F(x)H(x)x(G(x)H(x) (11) - (13) x(F(x)H(x) 前提引入

43、前提引入 (14) x(G(x)H(x) (12)(13)假言推理假言推理 50构造推理证明的实例构造推理证明的实例例例5.11 在自然推理系统在自然推理系统NL 中构造下面推理的证明中构造下面推理的证明, 取个体域取个体域R: 不存在能表示成分数的无理数不存在能表示成分数的无理数. 有理数都能表示成分数有理数都能表示成分数. 所以所以, 有理数都不是无理数有理数都不是无理数.解解 设设F(x):x是无理数是无理数, G(x):x是有理数是有理数, H(x):x能表示成分数能表示成分数.前提前提: x(F(x) H(x), x(G(x)H(x)结论结论: x(G(x)F(x) 证明证明: x(

44、F(x) H(x) 前提引入前提引入 x( F(x)H(x) 置换置换 x(F(x)H(x) 置换置换 F(x)H(x) -51构造推理证明的实例构造推理证明的实例 x(G(x)H(x) 前提引入前提引入 G(x)H(x) - H(x)F(x) 置换置换 G(x)F(x) 假言三段论假言三段论 x(G(x)F(x) +52附加前提证明法附加前提证明法例例 构造下面推理的证明：构造下面推理的证明：前提：前提： x(F(x)G(x)结论：结论： xF(x) xG(x)分析本题直接证明很困难，注意到结论部分是蕴含式，分析本题直接证明很困难，注意到结论部分是蕴含式，应考虑用应考虑用附加前提证明法附加前

45、提证明法。证明(1) x(F(x)G(x) 前提引入前提引入(2) xF(x) 附加前提引入附加前提引入 (3) F(t) (2)UI(4) F(t)G(t) (1)UI (5) G(t) (3)(4)假言推理假言推理(6) xG(x)(5)UG(7) xF(x) xG(x) CP53归缪法归缪法例例 构造下面推理的证明：构造下面推理的证明：前提：前提： x(F(x)G(x)结论：结论： x( y(F(y)H(x,y) z(G(z)H(x,z)分析本题直接证明会感到无从下手，而由于结论并非蕴含式分析本题直接证明会感到无从下手，而由于结论并非蕴含式( x的辖域是其后整个公式的辖域是其后整个公式)

46、，附加前提证明法也不适用，此，附加前提证明法也不适用，此时我们应考虑时我们应考虑归缪法归缪法。证明(1) x( y(F(y)H(x,y) z(G(z)H(x,z) 否定结论引入否定结论引入(2) x ( y(F(y)H(x,y) z(G(z)H(x,z) (1)置换置换(3) ( y(F(y)H(a,y) z(G(z)H(a,z) (2)EI, x改改a(4) ( y(F(y)H(a,y) z(G(z)H(a,z) 即即 y(F(y)H(a,y) z(G(z)H(a,z) (3)置换置换54(4) y(F(y)H(a，y) z(G(z)H(a，z) (5) y(F(y)H(a,y) (4)化简

47、化简(6) F(b)H(a,b) (5)EI(7) F(b) (6)化简化简(8) x(F(x)G(x) 前提引入前提引入(9) F(b)G(b) (8)UI(10) G(b) (7)(9)假言推理假言推理(11) z(G(z)H(a,z) (4)化简化简(12) z( G(z) H(a, z) (11)置换置换(13) G(b) H(a,b) (12)UI(14) H(a,b) (6)化简化简(15) H(a,b) (14)置换置换(16) G(b) (13)(15)析取三段论析取三段论(17) G(b) G(b) (10)(16)合取引入合取引入55补充总结补充总结要正确使用要正确使用UI

48、，UG，EG，EI 4条推理规则，使用时要注意条推理规则，使用时要注意以下几点：以下几点：（1）一定要对前束范式才能使用）一定要对前束范式才能使用UI，UG，EG，EI 规则，规则，对不是前束范式的公式要使用它们，一定先求出公式的前对不是前束范式的公式要使用它们，一定先求出公式的前束范式。束范式。（2）记住）记住UI，UG，EG，EI 各自使用的条件。各自使用的条件。（3）在同一推理的证明中，如果既要使用）在同一推理的证明中，如果既要使用UI规则，又在使规则，又在使用用EI规则，一定要先使用规则，一定要先使用EI规则，后使用规则，后使用UI规则，而且规则，而且UI规则使用的个体项一定是规则使用

49、的个体项一定是EI规则中使用过的；规则中使用过的；（4）对）对A(c)不能使用不能使用UG规则，其中规则，其中c为特定的个体常项。为特定的个体常项。56第五章第五章 习题课习题课主要内容主要内容l 一阶逻辑等值式一阶逻辑等值式 基本等值式，置换规则、换名规则、代替规则基本等值式，置换规则、换名规则、代替规则l 前束范式前束范式l 推理的形式结构推理的形式结构l 自然推理系统自然推理系统NL 推理定律、推理规则推理定律、推理规则57基本要求基本要求l 深刻理解并牢记一阶逻辑中的重要等值式深刻理解并牢记一阶逻辑中的重要等值式, 并能准确而熟并能准确而熟练地应用它们练地应用它们l 熟练正确地使用置换规则、换名规则、代替规则熟练正确地使用置换规则、换名规则、代替规则l 熟练地求出给定公式的前束范式熟练地求出给定公式的前束范式l 深刻理解自然推理系统深刻理解自然推理系统NL 的定义，牢记的定义，牢记NL 中的各条推理中的各条推理规则，特别是注意使用规则，特别是注意使用、 +、 +