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

1、1 主要内容主要内容 l 一阶逻辑等值式与基本的等值式一阶逻辑等值式与基本的等值式 l 置换规则、换名规则、代替规则置换规则、换名规则、代替规则 l 前束范式前束范式 l 自然推理系统自然推理系统NL 及其推理规则及其推理规则 第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理 2 5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则 定义定义5.1 设设A, B是两个谓词公式是两个谓词公式, 如果如果AB是永真式是永真式, 则称则称A与与B等值等值, 记作记作AB, 并称并称AB是是等值式等值式 基本等值式基本等值式 第一组第一组 命题逻辑中命题逻辑中16组基本等值式的代换实例组

2、基本等值式的代换实例 例如，例如，xF(x)xF(x), xF(x)yG(y) xF(x)yG(y) 等等 3 3 基本等值式基本等值式 双重否定律双重否定律 A(x)A(x) 幂等律幂等律 A(x) A(x)A(x), A(x) A(x)A(x) 交换律交换律 A(x) B(x)B(x) A(x), A(x) B(x)B(x) A(x) 结合律结合律 (A(x) B(x) C(x)A(x) (B(x) C(x), (A(x) B(x) C(x)A(x) (B(x) C(x) 分配律分配律 A(x) (B(x) C(x)(A(x) B(x) (A(x) C(x) A(x) (B(x) C(x)

3、(A(x) B(x) (A(x) C(x) 德摩根律德摩根律 (A(x) B(x)A(x)B(x) (A(x) B(x)A(x)B(x) 吸收律吸收律 A(x) (A(x) B(x)A(x) A(x) (A(x) B(x)A(x) 4 4 基本等值式基本等值式 零律零律 A(x) 11, A(x) 00 同一律同一律 A(x) 0A(x). A(x) 1A(x) 排中律排中律 A(x)A(x)1 矛盾律矛盾律 A(x)A(x)0 蕴涵等值式蕴涵等值式 A(x)B(x)A(x) B(x) 等价等值式等价等值式 A(x)B(x)(A(x)B(x) (B(x)A(x) 假言易位假言易位 A(x)B(

4、x)B(x)A(x) 等价否定等值式等价否定等值式 A(x)B(x)A(x)B(x) 归谬论归谬论 (A(x)B(x) (A(x)B(x) A(x) 5 第二组第二组 (1) 消去量词等值式消去量词等值式 设设D =a1, a2, , an xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an) 6 (2) 量词否定等值式量词否定等值式 xA(x) x A(x) xA(x) x A(x) 例例 不是所有的人都喜欢吃糖。不是所有的人都喜欢吃糖。 没有人喜欢吃糖。没有人喜欢吃糖。 设个体域设个体域D:人类集合人类集合 F(x): x是人是人, G(x): x

5、喜欢吃糖喜欢吃糖 7 ()( ( )()( ) ()( ( )()( ) x A xxA x x A xxA x 证明证明 设个体域设个体域 ,则则 1,2, , n Ea aa 12 ( )( ()().() n xA xA aA aA a 12 ()().() n A aA aA a ( )x A x 12 ( )( ()().() n xA xA aA aA a 12 ()().() n A aA aA a ( )x A x 8 基本等值式基本等值式 (3) 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式. A(x) 是含是含 x 自由出现的公式，自由出现的公式，B 中不含中不含 x

6、的自由的自由 出现出现 关于全称量词的：关于全称量词的： 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) 9 基本等值式基本等值式 关于存在量词的：关于存在量词的： 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) 10 基本等值式基本等值式 (4) 量词分配等值式量词分配等值式 x(A(x) B(x) xA(x)xB(x) x(A(x) B(x) xA(x)xB(x) 注意：注意： 对对 ， 对对 无分配律无分配律 1122

7、 1212 ()( ( )( ) ( ( )( )( ()().( ( )( ) ( ( )().( )( ( )().( ) () ( )() ( ) nn nn x A xB x A aB aA aB aA aB a A aA aA aB aB aB a x A xx B x 11 置换规则、换名规则、代替规则置换规则、换名规则、代替规则 1. 置换规则置换规则 设设 (A)是含是含A的公式的公式, 那么那么, 若若AB, 则则 (A) (B). 2. 换名规则换名规则 设设A为一公式，将为一公式，将A中某量词辖域中个体变项的所中某量词辖域中个体变项的所 有约束出现及相应的指导变元换成该量

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

9、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) 置换置换 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 实例实例 例例

10、2 将公式化成等值的不含既有约束出现、又有自将公式化成等值的不含既有约束出现、又有自 由出现的个体变项由出现的个体变项: 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, 消去下述公式中的量词消去

11、下述公式中的量词: (1) x y(F(x)G(y) 解解 x y(F(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(

12、b) G(c) 17 实例实例 (2) 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) 18 5.2 一阶逻辑前束范式一阶逻辑前束范式 定义定义5.2 设设A为一个一阶逻辑公式，若为一个一阶逻辑公式，若A具有如下形式具有如下形式 Q1x1Q2x2QkxkB 则称则称A为为前束范式前束范式，其中，其中Qi (1 i k)为为 或或 ，B为为 不含量词的公式。不含量词的公式。 例如，例如， x (F(x) G(x) x y(F(x

13、)(G(y) H(x,y) 是前束范式是前束范式 而而 x(F(x) G(x) x(F(x)y(G(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) 后两步结果都是前束范式，说明公式的前束范后两步结果都是前束范式，说明

14、公式的前束范 式不惟一。式不惟一。 20 求前束范式的实例求前束范式的实例 (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) 换名规则换名规则 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)

15、(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) 辖域收缩扩张规则辖域收缩扩张规则 22 5.3 一阶逻辑的推理理论一阶逻辑的推理理论 一、推理的形式结构一、推理的形式结构 1. A1 A2Ak B 若此式是永真式若此式是永真式, 则称推理正确则称推理正确, 记作记作 A1 A2Ak B 2. 前提前提: A1, A2, Ak 结论结论: B 推理定理推理定理: 永真式的蕴涵式永真式的蕴涵式 23 二、谓词逻辑推理定律二、谓词逻辑推理定律 第一组：第一组：命题逻辑推理定律的代换实例命题

16、逻辑推理定律的代换实例都是谓词逻都是谓词逻 辑的推理定律。辑的推理定律。 如：如： x F(x) y G(y)x F(x) x F(x) x F(x) y G(y) 24 第二组：由第二组：由基本等值式生成基本等值式生成的推理定律。每个等值式的推理定律。每个等值式 可生成两个推理定律。可生成两个推理定律。 如：由量词否定等值式如：由量词否定等值式 xA(x) xA(x)生成生成 两个定律：两个定律： x A(x) x A(x)， x A(x) x A(x) 25 由量词辖域扩张等值式由量词辖域扩张等值式 x(A(x)B) xA(x)B 生成：生成： x(A(x)B) x A(x)B , xA(

17、x)B x(A(x)B) 由量词分配等值式由量词分配等值式 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) 26 第三组：其它重要推理定律。如：第三组：其它重要推理定律。如： (1) x A(x) x B(x) x(A(x)B(x) (2) x(A(x)B(x) x A(x) x B(x) (3) x(A(x)B(x) x xA(x) x B(x) (4) x(A(x)B(x) x A(x) x B(x) 27 全称量词对全称量词对 ，存在量词对，存在量词对 不满足分配律。不满足分配律。

18、例：个体域是人的集合。例：个体域是人的集合。 A(x)：x是女人。是女人。 B(x)：x是男人。是男人。 为真；为真； 为假。为假。 为假；为假； 为真。为真。 仅满足：仅满足： ()( ( )( )() ( )() ( ) () ( )() ( )()( ( )( ) xA xB xx A xx B x x A xx B xxA xB x ()( ( )( )x A xB x () ( )() ( )x A xx B x ()( ( )( )x A xB x () ( )() ( )x A xx B x 28 在谓词逻辑中，除了在谓词逻辑中，除了命题逻辑中的推理规则命题逻辑中的推理规则继续继

19、续 有 效 外 ， 还 有 以 下 四 条 规 则 。 设 前 提有 效 外 ， 还 有 以 下 四 条 规 则 。 设 前 提 = A1,A2,Ak。（只对前束范式有用）。（只对前束范式有用） 1. 全称量词消去规则（记为全称量词消去规则（记为 -）： 三、谓词逻辑推理规则三、谓词逻辑推理规则 其中其中x,y是个体变项是个体变项符号符号，c是个体常项是个体常项符号符号； 或或 x A(x) A(y) x A(x) A(c) 且在且在A中中x不在不在 y和和 y的辖域内自由出现。的辖域内自由出现。 29 2 . 全称量词引入规则全称量词引入规则 (记为记为 +)： 三、谓词逻辑推理规则三、谓词

20、逻辑推理规则 其中其中x是个体变项符号，且不在是个体变项符号，且不在的任何公式中自的任何公式中自 由出现。由出现。 A(x) x A(x) 30 三、谓词逻辑推理规则三、谓词逻辑推理规则 3. 存在量词消去规则存在量词消去规则 (记为记为 -)： 其中其中c是使是使A为真的特定的个体常项。为真的特定的个体常项。 x是个体变项符号，且不在是个体变项符号，且不在的任何公式和的任何公式和B中自由出中自由出 现现。 xA(x)B xA(x) A(c) A(x)B 或或 31 4. 存在量词引入规则存在量词引入规则 (记为记为 + +)： 三、谓词逻辑推理规则三、谓词逻辑推理规则 其中其中x,y是个体变

21、项符号是个体变项符号, c是个体常项符号是个体常项符号, 并且在并且在A中中y和和 c分别不分别不在在 x 和和 x的辖的辖域内域内自由出现自由出现。 B A(y) B xA(x) A(y) xA(x) 或或 B A(c) B xA(x) A(c) xA(x) 或或 32 例例:设设D(x,y)表示表示“x可被可被y 整除整除” ,个体域为个体域为 6,10,34,42 . 因为因为 xD(x,2)为真，所以为真，所以D(y,2)为真为真 因为因为 xD(x,5)为真，所以为真，所以D(a,5)为真为真 例例:设设D(x,y)表示表示“x可被可被y 整除整除” ,个体域个体域 为为 5,7 ,

22、10 ,11 . 因为因为D(5,5)和和D(10,5)为真，所以为真，所以 xD(x,5)为真为真. 因为因为D(7,5)和和D(11,5)为假，所以为假，所以 xD(x,5)为假为假. 33 但有下面的推理过程：但有下面的推理过程： (1) xD(x,5) 前提前提 (2) D(z,5) (3) xD(x,5) 因此，因此， xD(x,5) xD(x,5). 34 定义定义5.3 自然推理系统自然推理系统N NL L 下由如下要素构成。下由如下要素构成。 1. 字母表：见定义字母表：见定义4.1 2. 合式公式：见定义合式公式：见定义4.4 3. 推理规则：推理规则： (1) 前提引入规则

23、前提引入规则 (2) 结论引入规则结论引入规则 (3) 置换规则置换规则 (4) 假言推理规则假言推理规则 (5) 附加规则附加规则 (6) 化简规则化简规则 (7) 拒取式规则拒取式规则 (8) 假言三段论规则假言三段论规则 (9) 析取三段论规则析取三段论规则 (10) 构造性二难推理规则构造性二难推理规则 (11) 合取引入规则合取引入规则 四、自然推理系统四、自然推理系统N NL L 35 (12) -规则规则 (13) +规则规则 (14) +规则规则 (15) -规则规则 其中规则其中规则 (1)(11) 与命题逻辑中的推理规则相同。与命题逻辑中的推理规则相同。 四、自然推理系统四

24、、自然推理系统N NL L 36 谓词逻辑求解实际问题谓词逻辑求解实际问题 步骤： 根据问题的需要定义一组谓词 将实际问题符号化 使用推理规则有效推理 注意： 符号化的原则：全称量词对应逻辑联结词， 存在量词对应逻辑联结词 推理时首先引入带存在量词的前提，以保证 “+”规则的有效性 37 例：证明苏格拉底的三段论。 所有的人都是要死的。苏格拉底是人。 所以苏格拉底是要死的。 解：M(x):x是人；D(x):x是要死的；c:苏格拉底。 苏格拉底三段论可以表示成： 证明： (1) M(c) P (2) P (3) M(c)D(c) US, (2) (4) D(c) T,1,3 x(M(x)D(x)

25、,M(c)D(c) x(M(x)D(x) 38 前提：前提： x (F(x)G(x), x(F(x)H(x) 结论：结论： x(G(x)H(x) 例例5.10 在自然推理系统在自然推理系统N NL L中，构造下面推理的证中，构造下面推理的证 明：明： x(F(x)H(x) F(a)H(a) x(F(x)G(x) ) F(a)G(a) F(a) H(a) G(a) 前提引入前提引入 - 前提引入前提引入 - - 化简规则化简规则 化简规则化简规则 置换假言推理置换假言推理 证明：证明： 39 G(a)H(a) 合取引入合取引入 x(G(x)H(x) + 40 不存在能表示出分数的无理数，有理数都

26、能表示成不存在能表示出分数的无理数，有理数都能表示成 分数，因此，有理数都不是无理数。分数，因此，有理数都不是无理数。 解：设解：设F(x): x为无理数；为无理数；G(x): x为有理数；为有理数；H(x)：x 能表示成分数。能表示成分数。 前提：前提： x(F(x)H(x), x(G(x)H(x) 结论：结论： x(G(x) F(x) 例例5.11 在在N NL L中构造下面推理的证明中构造下面推理的证明 (个体域为实数集个体域为实数集)： 41 证明：证明： x(F(x)H(x) x(F(x)H(x) x(F(x)H(x) F(x)H(x) x(G(x)H(x) G(x)H(x) H (

27、x)F (x) G(x)F(x) x(G(x)F(x) 前提引入前提引入 置换置换 置换置换 - - 前提引入前提引入 - - 置换置换 假言三段论假言三段论 + 42 反证法举例反证法举例 例：例： 证明：证明： ()( ( )( ),()( ( )( ),() ( ) () ( ) x A xB xx B xC xx C x x A x 给定前提 试推出结论： (1) () ( ) () (2) ()( ) ,(1) (3) ( ) x A xP xA xT A a 假设前提 ,(2) (4) ()( ( )( ) (5) ( )( ) ,(4) (6) ( ) ES x A xB xP

28、A aB aUS B a ,(3),(5) (7) ()(B( )C( ) (8) ( )( ) ,(7) (9) ( ) T xxxP B aC aUS C a ,(6),(8) (10) ()C( ) T xxP 43 反证法举例反证法举例 (11) ( ) ,(10) (12) ( )( ) ,(9),(11) (13) ()A( ) F,( C aUS C aC aT xx 1),(12) 44 例例6：使用：使用CP规则证明规则证明 证明：证明： 因此原来的证明转化为证明下式：因此原来的证明转化为证明下式： ()()( )( )()( )() ( )xyP xQ yxP xy Q y

29、 ()( )()() () ( )() ( )() ( )() ( ) xP xy Qy x P xy Q yx P xy Q y 由于 ()()( )( )() ( )() ( )xyP xQ yx P xy Q y 45 证明证明()()( )( )() ( )() ( )xyP xQ yx P xy Q y (1) () ( ) () (2) ( ) ,(1) (3) ()()( )( ) x P xP P aES xyP xQ y 附加前提 (4) ()( )( ) ,(3) (5) ( )( ) ,(4) (6) ( ) ,(2), P yP aQ yUS P aQ bUS Q bT

30、 (5) (7) () ( ) ,(6) (8) () ( )()Q(y) ,(1),(7) y Q yUG x P xyCP 46 第五章第五章 习题课习题课 主要内容主要内容 l 一阶逻辑等值式一阶逻辑等值式 基本等值式，置换规则、换名规则、代替规则基本等值式，置换规则、换名规则、代替规则 l 前束范式前束范式 l 推理的形式结构推理的形式结构 l 自然推理系统自然推理系统NL 推理定律、推理规则推理定律、推理规则 47 基本要求基本要求 l 深刻理解并牢记一阶逻辑中的重要等值式深刻理解并牢记一阶逻辑中的重要等值式, 并能并能 准确而熟练地应用它们准确而熟练地应用它们 l 熟练正确地使用置

31、换规则、换名规则、代替规熟练正确地使用置换规则、换名规则、代替规 则则 l 熟练地求出给定公式的前束范式熟练地求出给定公式的前束范式 l 深刻理解自然推理系统深刻理解自然推理系统NL 的定义，牢记的定义，牢记NL 中的中的 各条推理规则，特别是注意使用各条推理规则，特别是注意使用、 +、 +、 4条推理规则的条件条推理规则的条件 l 能正确地给出有效推理的证明能正确地给出有效推理的证明 48 练习练习1 2 a 1. 给定解释给定解释I如下如下: (1) 个体域个体域D=2,3 (2) (3) (4) 求下述在求下述在I下的解释及其真值下的解释及其真值: x y(F(f(x) G(y,f(a)

32、 2)3(, 3)2(:)( ffxf 0)3 , 3(, 1)2 , 3()3 , 2()2 , 2(:),( 1)3(, 0)2(:)( GGGGyxG FFxF 解解 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)0 49 练习练习2 2.求下述公式的前束范式求下述公式的前束范式: 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(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) 50 练习练习3 3.构造下面推理的证明构造下面推理的证明: (1) 前提：前提： x(F(x)G(x),