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

1、1主要内容主要内容l 一阶逻辑等值式与基本的等值式一阶逻辑等值式与基本的等值式l 置换规则、换名规则、代替规则置换规则、换名规则、代替规则l 前束范式前束范式l 自然推理系统自然推理系统NL 及其推理规则及其推理规则第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理25.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则定义定义5.1 设设A, B是两个谓词公式是两个谓词公式, 如果如果AB是永真式是永真式, 则则 称称A与与B等值等值, 记作记作AB, 并称并称AB是是等值式等值式公式公式A、B它们有共同的个体域它们有共同的个体域E，若对于，若对于A和和B的任的任意一组指派，两公式

2、都具有相同的真值，则称公式意一组指派，两公式都具有相同的真值，则称公式A和和B在在E上等值，记作上等值，记作A B。对于公式对于公式A和和B，若，若A B 1，则称公式，则称公式A蕴含公式蕴含公式B，记作，记作A B。35.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则基本等值式基本等值式第一组第一组 命题逻辑中命题逻辑中16组基本等值式的代换实例组基本等值式的代换实例 在命题演算中，任一等值式或蕴涵式，其中同一命题变元，当用在命题演算中，任一等值式或蕴涵式，其中同一命题变元，当用同一命题公式取代时，其结果仍是等值式或蕴涵式。同一命题公式取代时，其结果仍是等值式或蕴涵式。 将此情况推广到

3、谓词公式中，用谓词公式去取代命题演算中等将此情况推广到谓词公式中，用谓词公式去取代命题演算中等值式或蕴涵式的命题变元时，便得到谓词演算的等值式或蕴涵值式或蕴涵式的命题变元时，便得到谓词演算的等值式或蕴涵式。式。例如，例如， pp xF(x)xF(x), pq p q xF(x)yG(y) xF(x)yG(y)4( )( )( )pppxP xxP xxP x 又例如又例如()( ( )( , )( )( , )pqpqA xB x yA xB x y 例如例如55.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则第二组第二组 (1) 消去量词等值式消去量词等值式 设设D =a1, a2,

4、, an xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an)6 (2) 量词否定等值式量词否定等值式（全称量词和存在量词间转化的等值式）（全称量词和存在量词间转化的等值式）)(.)()()(21naAaAaAxxA )(.)()(21naAaAaA )(xAx )(.)()()(21naAaAaAxxA )(.)()(21naAaAaA )(xAx 对个体域是有限时，给出其证明。对个体域是有限时，给出其证明。 证明证明 设个体域设个体域D=a1,a2,an ,则则 xA(x) x A(x) xA(x) x A(x)7基本等值式基本等值式(3) 量词辖

5、域收缩与扩张等值式量词辖域收缩与扩张等值式. 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) 8基本等值式基本等值式 x(A(x)B) x( A(x) B) x A(x) B xA(x) B xA(x)B设设个体域个体域D=a1, a2, , an , 则则 x(A(x) B) (A(a1) B) (A(a2) B) (A(an) B) (A(a1) A(a2) A(an) B

6、 xA(x) B9基本等值式基本等值式 关于存在量词的：关于存在量词的： 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)(4) 量词分配等值式量词分配等值式 x(A(x) B(x) xA(x)xB(x) x(A(x) B(x) xA(x)xB(x) “个体域中每一个体个体域中每一个体x，使得，使得A(x)与与B(x)均为真均为真”与与 “个体域中每一个体个体域中每一个体x，使得使得A(x)为真且每一个体为真且每一个体x使得使得B(x)为真为真”具有相同的含义具有相同的含义.10注意：注意：P70例例5.2 对

7、对 ， 对对 无分配律无分配律 xB(x)xA(x)B(x)x(A(x)()()()(xxBxxAxBxAx请举例请举例?A(x) x是偶数，是偶数，B(x) x是奇数，是奇数，x是整数。是整数。从左到右不成立从左到右不成立 从右到左不成立从右到左不成立 11置换规则、换名规则、代替规则置换规则、换名规则、代替规则1. 置换规则置换规则 设设 (A)是含是含A的公式的公式, 那么那么, 若若AB, 则则 (A) (B).2. 换名规则换名规则 设设A为一公式，将为一公式，将A中某量词辖域中个体变项的所有约束中某量词辖域中个体变项的所有约束 出现及相应的指导变元换成该量词辖域中未曾出现过的个出现

8、及相应的指导变元换成该量词辖域中未曾出现过的个 体变项符号，其余部分不变，设所得公式为体变项符号，其余部分不变，设所得公式为A ，则，则AA.3. 代替规则代替规则 设设A为一公式，将为一公式，将A中某个个体变项的所有自由出现用中某个个体变项的所有自由出现用A中中 未曾出现过的个体变项符号代替，其余部分不变，设所得未曾出现过的个体变项符号代替，其余部分不变，设所得 公式为公式为A ，则，则AA.12实例实例例例1 将下面命题用两种形式符号化将下面命题用两种形式符号化, 并证明两者等值并证明两者等值: (1) 没有不犯错误的人没有不犯错误的人解解 令令F(x)：x是人，是人，G(x)：x犯错误犯

9、错误. 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) 置换置换13实例实例(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) 置换置换14实例实例例例2 将公式化成等值的不含既有约束出现、又有自将公式化成等值

10、的不含既有约束出现、又有自由出现的个体变项由出现的个体变项: x(F(x,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) 辖域扩张等值式辖域扩张等值式15实例实例例例3 设个体域设个体域D=a,b,c, 消去下述公式中的量词消去下述公式中的量词: (1) x y(F(x)G(y)解解 x y(F(

11、x)G(y) ( y(F(a)G(y) ( 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) 16实例实例解法二解法二 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)17实例实例(2) x yF(x,y) x yF(x,y) x(

12、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)185.2 一阶逻辑前束范式一阶逻辑前束范式定义定义5.2 设设A为一个一阶逻辑公式，若为一个一阶逻辑公式，若A具有如下形式具有如下形式 Q1x1Q2x2QkxkB则称则称A为为前束范式前束范式，其中，其中Qi (1 i k)为为 或或 ，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

13、(y) H(x,y) 不是前束范式，不是前束范式，19前束范式存在定理前束范式存在定理定理定理5.1（前束范式存在定理）（前束范式存在定理） 一阶逻辑中的任何公式都存在与之等值的前束范式一阶逻辑中的任何公式都存在与之等值的前束范式例例4 求下列公式的前束范式求下列公式的前束范式 (1) x(M(x) F(x)解解 x(M(x) F(x) x( M(x)F(x) （量词否定等值式）（量词否定等值式） x(M(x)F(x) 后两步结果都是前束范式，说明公式的前束范式不惟一后两步结果都是前束范式，说明公式的前束范式不惟一.20求前束范式的实例求前束范式的实例 (2) xF(x)xG(x)解解 xF(

14、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) 换名规则换名规则 x y(F(x)G(y) 辖域收缩扩张规则辖域收缩扩张规则21求前束范式的实例求前束范式的实例(3) 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(

15、F(z)(G(x,y)H(y) 辖域收缩扩张规则辖域收缩扩张规则225.3 一阶逻辑的推论理论一阶逻辑的推论理论推理的形式结构推理的形式结构1. A1 A2Ak B 若该式是永真式若该式是永真式, 则称推理正确则称推理正确, 记作记作A1 A2Ak B2. 前提前提: A1, A2, Ak 结论结论: B推理定理推理定理: 永真式的蕴涵式永真式的蕴涵式23推理定理推理定理第一组第一组 命题逻辑推理定理的代换实例命题逻辑推理定理的代换实例 如如, xF(x)yG(y) xF(x) 第二组第二组 基本等值式生成的推理定理基本等值式生成的推理定理 如如, xF(x) xF(x), xF(x) xF(

16、x) xF(x)x F(x), x F(x) xF(x)第三组第三组 其他常用推理定律其他常用推理定律 (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)24量词消去引入规则量词消去引入规则1. 全称量词消去规则全称量词消去规则( -) 或或 xA(x)A(y) xA(x)A(c)(2) c为论域中的某个任意个体常元为论域中的某个任意个体常元(1) y为不在为不在A(x)中约束出现的任意的个体变项中约束出现的任意的个体变项25重要提示重要

17、提示 例例1. 对对A= x yF(x,y)使用使用 -规则规则, 推得推得B= yF(y,y). 设设 个体域为个体域为R, F(x,y)=xy 对于对于 x y(xy)是是真命题。真命题。 设设A(x)= yF(x,y),x在在A(x)中是自由出现，但中是自由出现，但y在在A(x)中是约束出现的。若取中是约束出现的。若取y代替代替x得得 x yF(x,y) = y(yy), 假假 原因原因: 在在A中中x自由出现在自由出现在 y的辖域的辖域F(x,y)内内在第一式，在第一式，y应为不在应为不在A(x)中约束出现的任意的个体变项中约束出现的任意的个体变项26量词消去引入规则量词消去引入规则2

18、. 全称量词引入规则全称量词引入规则( +) 其中其中x是个体变项符号是个体变项符号, 且不在前提的任何公式中自由出现且不在前提的任何公式中自由出现 A(x)xA(x) 规则成立的条件：规则成立的条件：（1）能够证明）能够证明A(x)对论域中的每一个可能对论域中的每一个可能x都为真。都为真。27量词消去引入规则量词消去引入规则3. 存在量词消去规则存在量词消去规则( -) 其中其中x是个体变项符号是个体变项符号, 且不在前提的任何公式和且不在前提的任何公式和B中自由出现中自由出现 xA(x) A(c)规则成立的条件：规则成立的条件： c是使是使A为真的某个个体常项，为真的某个个体常项，c不是任

19、意的。不是任意的。 例如，例如， xP(x)和和 xQ(x)都为真，则对于某些都为真，则对于某些c和和d，可以断言，可以断言P(c) Q(d)必定为真，但不能断定必定为真，但不能断定P(c) Q(c)是真。是真。28量词消去引入规则量词消去引入规则4. 存在量词引入规则存在量词引入规则( +) 其中其中x是个体变项符号是个体变项符号 A(c)xA(x)规则成立的条件：规则成立的条件： c是论域中的一个个体；是论域中的一个个体； 29自然推理系统自然推理系统NL定义定义5.3 自然推理系统自然推理系统NL 定义如下定义如下:1. 字母表字母表. 同一阶语言同一阶语言L 的字母表的字母表2. 合式

20、公式合式公式. 同同L 的合式公式的合式公式3. 推理规则推理规则:(1) 前提引入规则前提引入规则(2) 结论引入规则结论引入规则(3) 置换规则置换规则(4) 假言推理规则假言推理规则(5) 附加规则附加规则(6) 化简规则化简规则(7) 拒取式规则拒取式规则30自然推理系统自然推理系统NL(8) 假言三段论规则假言三段论规则(9) 析取三段论规则析取三段论规则(10) 构造性二难推理规则构造性二难推理规则(11) 合取引入规则合取引入规则(12) -规则规则(13) +规则规则(14) -规则规则(15) +规则规则推理的证明推理的证明31 例例1 1 证明苏格拉底的三段论。证明苏格拉底

21、的三段论。 解解 令令M(x):x是人是人; D(x):x是要死的是要死的; c:苏格拉底。苏格拉底。 于是苏格拉底三段论可表示为：于是苏格拉底三段论可表示为： 证明证明（1）M(c) 前提前提D(x)x(M(x) （2） (M(x) D(x) 前提前提D(c)M(c) （3） M(c) D(c) （1）；）； - （4）D(c) (1),(3); 假言推理假言推理 x (M(x) D(x) M(c) D(c)32 （3） C(a) Q(a) （2）; - 证明证明 （1） x(C(x) W(x) R(x) 前提前提 （2） x(C(x) Q(x) 前提前提 （4） （1）；）；UI （4）

22、Q(a) （3）；化简）；化简例例2 x(C(x) W(x) R(x) x(C(x) Q(x) = x(Q(x) R(x) （4） C(a) W(a) R(a) （1）; - （5） C(a) （3）; 化简规则化简规则 （6） W(a) R(a) （1）; 假言推理假言推理 （7） Q(a) （3）;化简规则化简规则 （8） R(a) （6）;化简规则化简规则 （9） Q(a) R(a) (7)(8); 合取引入合取引入 （10） x Q(x) R(x) (9); +33 例例3 指出下面推理的错误指出下面推理的错误. 设设D(x,y)表示表示“x可被可被y 整除整除” ,个体域个体域 为为

23、 5,7 ,10 ,11 . 因为因为D(5,5)和和D(10,5)为真，所以为真，所以 xD(x,5)为真为真. 因为因为D(7,5)和和D(11,5)为假，所以为假，所以 xD(x,5)为假为假. 但有下面的推理过程：但有下面的推理过程： (1) xD(x,5) 前提前提 (2) D(z,5) (1); - (3) xD(x,5) (2); + 因此，因此， xD(x,5) = xD(x,5).342.对于同一个体变元，先指定对于同一个体变元，先指定 量词，后指定量词，后指定 量词量词推理过程的注意事项：推理过程的注意事项：1.先将量词前置在先将量词前置在“非非”联接词前，再指定。联接词前

24、，再指定。同一个体变元的两个存在量词，存在的可能是不同个体同一个体变元的两个存在量词，存在的可能是不同个体！ 3.对于不同的个体变元，按量词的前后进行指定（消除对于不同的个体变元，按量词的前后进行指定（消除量词），引入量词），引入 量词按相反顺序。量词按相反顺序。35第五章第五章 习题课习题课主要内容主要内容l 一阶逻辑等值式一阶逻辑等值式 基本等值式，置换规则、换名规则、代替规则基本等值式，置换规则、换名规则、代替规则l 前束范式前束范式l 推理的形式结构推理的形式结构l 自然推理系统自然推理系统NL 推理定律、推理规则推理定律、推理规则36基本要求基本要求l 深刻理解并牢记一阶逻辑中的重要

25、等值式深刻理解并牢记一阶逻辑中的重要等值式, 并能准确而熟并能准确而熟练地应用它们练地应用它们l 熟练正确地使用置换规则、换名规则、代替规则熟练正确地使用置换规则、换名规则、代替规则l 熟练地求出给定公式的前束范式熟练地求出给定公式的前束范式l 深刻理解自然推理系统深刻理解自然推理系统NL 的定义，牢记的定义，牢记NL 中的各条推理中的各条推理规则，特别是注意使用规则，特别是注意使用、 +、 +、 4条推理规则的条推理规则的条件条件l 能正确地给出有效推理的证明能正确地给出有效推理的证明 37练习练习12 a1. 给定解释给定解释I如下如下:(1) 个体域个体域D=2,3(2) (3)(4)求

26、下述在求下述在I下的解释及其真值下的解释及其真值: x y(F(f(x) G(y,f(a)2)3(, 3)2(:)( ffxf0)3 , 3(, 1)2 , 3()3 , 2()2 , 2(:),(1)3(, 0)2(:)( GGGGyxGFFxF解解 xF(f(x)yG(y,f(a) F(f(2) F(f(3) (G(2,f(2) G(3,f(2) 1 0 (1 0)038练习练习22.求下述公式的前束范式求下述公式的前束范式: xF(x)y(G(x,y) H(x,y)解解 使用换名规则使用换名规则, xF(x)y(G(x,y) H(x,y) zF(z)y(G(x,y) H(x,y) z(F

27、(z)y(G(x,y) H(x,y) z y(F(z)(G(x,y) H(x,y) 使用代替规则使用代替规则 xF(x)y(G(x,y) H(x,y) xF(x)y(G(z,y) H(z,y) x(F(x)y(G(z,y) H(z,y) x y(F(x)(G(z,y) H(z,y) 39练习练习33.构造下面推理的证明构造下面推理的证明:(1) 前提：前提： x(F(x)G(x), xF(x) 结论：结论： xG(x)证明：证明： xF(x) 前提引入前提引入 F(c) x(F(x)G(x) 前提引入前提引入 F(c)G(c) G(c) 假言推理假言推理 xG(x) + 40练习练习3(续续)

28、(2) 前提：前提： x(F(x) G(x), xG(x)结论：结论： xF(x) 证明：用归谬法证明：用归谬法 xF(x) 结论否定引入结论否定引入 x F(x) 置换置换 xG(x) 前提引入前提引入 x G(x) 置换置换 F(c) G(c) x(F(x) G(x), 前提引入前提引入 F(c) G(c) G(c) 析取三段论析取三段论 G(c) G(c) 合取引入合取引入 41练习练习3(续续)(2) 前提：前提： x(F(x) G(x), xG(x)结论：结论： xF(x) 证明：直接法证明：直接法 xG(x) 前提引入前提引入 x G(x) 置换置换 x(F(x) G(x) 前提引

29、入前提引入 F(c) G(c) G(c) F(c) 析取三段论析取三段论 xF(x)42练习练习3(续续)(3)前提：前提： x(F(x)G(x), x(G(x)H(x)结论：结论： xF(x)xH(x)证明证明: 用附加前提法用附加前提法 xF(x) 附加前提引入附加前提引入 F(x) x(F(x)G(x) 前提引入前提引入 F(x)G(x) x(G(x)H(x) 前提引入前提引入 G(x)H(x) F(x)H(x) 假言三段论假言三段论 H(x) 假言推理假言推理 xH(x) + 43练习练习44. 在自然推理系统在自然推理系统NL 中，构造推理的证明中，构造推理的证明 人都喜欢吃蔬菜但不

30、是所有的人都喜欢吃鱼所以人都喜欢吃蔬菜但不是所有的人都喜欢吃鱼所以, 存存在喜欢吃蔬菜而不喜欢吃鱼的人在喜欢吃蔬菜而不喜欢吃鱼的人解解 令令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) H(x) 前提引入前提引入(2) x (F(x) H(x) (1)置换置换(3) (F(c) H(c) (2) (4) x(F(x) G(x)H(x) 结论否定引入结论否定引入(5) x (F(x) G(x)H(x) (4)置换置换44练习练习4(续续)(6) (F(c) G(c)H(c) (5)(7)