命题逻辑的推理理论[稻谷文苑]

1、第三章第三章 命题逻辑的推理理论命题逻辑的推理理论 推理的形式结构推理的形式结构 自然推理系统自然推理系统P 1应用分析 关于“推理” n推理：指从推理：指从前提前提出发推出出发推出结论结论的思维过程的思维过程， 前提前提是已知命题公式集合，是已知命题公式集合， 结论结论是从前提出发应用推理规则推出的命题是从前提出发应用推理规则推出的命题 公式。公式。 数理逻辑的主要任务是用数学的方法来研究数数理逻辑的主要任务是用数学的方法来研究数 学中的推理。学中的推理。 2应用分析 推理的形式结构推理的形式结构问题的引入问题的引入 推理举例推理举例: (1) 正项级数收敛当且仅当部分和上有界正项级数收敛当

2、且仅当部分和上有界. (2) 若若A C B D，则，则A B且且C D. 推理推理: 从前提出发推出结论的思维过程从前提出发推出结论的思维过程 上面上面(1)是正确的推理，而是正确的推理，而(2)是错误的推理是错误的推理. 证明证明: 描述推理正确或错误的过程描述推理正确或错误的过程. 3应用分析 推理的形式结构 定义定义 设设A1，A2 ，Ak，B都是命题公式都是命题公式, 若对于若对于A1，A2 ，Ak，B中出现的命题变中出现的命题变 项的任意一组赋值，项的任意一组赋值，A1 A2 Ak 均为假，均为假， 或当或当A1 A2 Ak为真时为真时, B也为真也为真, 则称由则称由 A1,A2

3、, Ak推推B的的推理正确推理正确 ,并称并称B是有效的是有效的 结论；结论； 否则否则推理不正确（错误）推理不正确（错误）. 4应用分析 说明（1）： n由前提由前提A1，A2 ，Ak推结论推结论B的推理是否正确的推理是否正确 与诸前提的排列次序无关。与诸前提的排列次序无关。 n因而前提中的公式不一定是序列，而是一个有限因而前提中的公式不一定是序列，而是一个有限 公式集合，记为公式集合，记为 。 n可将由可将由推推B的推理记为的推理记为B B，若推理是正，若推理是正 确的，则记为确的，则记为|=B|=B，否则记为，否则记为 | | B B。 n这里可以称这里可以称BB 和和 A1，A2 ，A

4、k B B 为推理的形式结构。为推理的形式结构。 5应用分析 说明（2） n设设A1，A2 ，Ak，B中共出现中共出现n个命题变项，对于任个命题变项，对于任 一组赋值一组赋值 a1a2an （ai0或或1， i1，2，n），前），前 提和结论的取值情况有以下四种：提和结论的取值情况有以下四种： （1） A1 A2 Ak 为为0，B为为0； （2） A1 A2 Ak 为为0，B为为1； （3） A1 A2 Ak 为为1，B为为0； （4） A1 A2 Ak 为为1，B为为1。 由定义可知，只要不出现（由定义可知，只要不出现（3）中的情况，推理就）中的情况，推理就 是正确的，因而判断推理正确与否，

5、就是判断是否会是正确的，因而判断推理正确与否，就是判断是否会 出现（出现（3）中的情况。）中的情况。 6应用分析 例3.1 判断下列推理是否正确 n（1） p， p q q n（2） p， q p q 解：只要写出前提的合取式与结论的真值表，看是解：只要写出前提的合取式与结论的真值表，看是 否出现前提为真，而结论为假的情况即可。否出现前提为真，而结论为假的情况即可。 由下面真值表可看出，（由下面真值表可看出，（1）推理正确，（）推理正确，（2） 推理不正确。推理不正确。 7应用分析 p q p （ p q ） q 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 p q p （

6、q p ） q 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 8应用分析 定理定理3.1 命题公式A1，A2 ，Ak推B的推 理正确当且仅当： （A1 A2 Ak ） B B 为重言式。为重言式。 证明：必要性 若命题公式A1，A2 ，Ak推B的推 理正确，则不会出现A1 A2 Ak为真， 而B为假的情况，因而在任何赋值下， 蕴涵式（A1 A2 Ak ） B B 均为真，故 为重言式。 9应用分析 证明：充分性 若蕴涵式（A1 A2 Ak ） B B 为 重言式，则对于任何赋值此重言式均为真， 因而不会出现前件为真后件为假的情况。即 在任何赋值下，或者A1 A2 Ak为假，

7、或者A1 A2 Ak和B同时为真，这正符合 定义3.1中推理正确的定义。 10应用分析 分析： 由定理3.1可知，可以将由前提A1, A2, , Ak 推B的推理的形式结构 A1 A2 Ak B 转换成蕴涵式 （A1 A2 Ak ） B B 推理前提的合取式成了蕴涵式的前件，结论成了蕴 涵式的后件，并将推理正确 A1 A2 Ak | B 转换成 A1 A2 Ak B 其中是一种元语言符号，表示蕴涵式为重言式。 11应用分析 判断推理是否正确的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法 构造证明法构造证明法 说明：当命题变项比较少时，用前说明：当命题变项比较少时，用前

8、3 3个方法比较个方法比较 方方 便便, , 此时采用此时采用形式结构形式结构“ A1 A2 AkB” . 而在而在 构造证明时，构造证明时，采用采用“前提前提: A1, A2, , Ak, 结论结论: B”. 12应用分析 例3.2 判断下面推理是否正确 解上述类型的推理问题，首先应将简 单命题符号化。然后分别写出前提、结论、 推理的形式结构，接着进行判断。 13应用分析 （1）设 p：a能被4整除 q：a能被2整除 前提：p q，p 结论：q 推理的形式结构：（p q） p q 可知此推理正确，即 （p q） p q 。 （1）若）若a能被能被4整除，则整除，则a能被能被2整除。整除。a能

9、被能被4整除，整除， 所以所以a能被能被2整除。整除。 14应用分析 （2）若）若a能被能被4整除，则整除，则a能被能被2整除。整除。a能被能被2整除，整除， 所以所以a能被能被4整除。整除。 n（2）设 p：a能被4整除 q：a能被2整除 前提：p q，q 结论：p 推理的形式结构：（p q） q p 可知上式不为重言式，所以此推理不正确， 即 （p q） p q 。 15应用分析 （3）下午马芳或去看电影或去游泳。她没去看电）下午马芳或去看电影或去游泳。她没去看电 影。所以，她去游泳了。影。所以，她去游泳了。 n（3）设）设 p：马芳下午去看电影：马芳下午去看电影 q：马芳下午去游泳：马芳

10、下午去游泳 前提：前提：p q， p 结论：结论： q 推理的形式结构推理的形式结构：（：（p q） p ） q 用等值演算法可知上市为重言式，所以，推理正用等值演算法可知上市为重言式，所以，推理正 确。确。 16应用分析 （4）若下午气温超过）若下午气温超过30度，则王小燕必去游泳。度，则王小燕必去游泳。 若她去游泳，她就不去看电影。所以，若王小燕没若她去游泳，她就不去看电影。所以，若王小燕没 去看电影，下午气温必超过了去看电影，下午气温必超过了30度。度。 n（4）设）设 p：下午气温超过：下午气温超过30度度 q： 王小燕去游泳王小燕去游泳 r： 王小燕去看电影王小燕去看电影 前提：前提

11、： p q， q r 结论：结论： r p 推理的形式结构：推理的形式结构： （ p q ） （q r） （ r p） 用主析取范式法可知上式不是重言式，所以用主析取范式法可知上式不是重言式，所以 推理不正确。推理不正确。 17应用分析 重要的推理定律（重要的推理定律（重言蕴涵式重言蕴涵式 ） A (A B) 附加律附加律 (A B) A 化简律化简律 (AB) A B 假言推理假言推理 (AB)B A 拒取式拒取式 (A B)B A 析取三段论析取三段论 (AB) (BC) (AC) 假言三段论假言三段论 (AB) (BC) (AC) 等价三段论等价三段论 (AB) (CD) (A C) (

12、B D) 构造性二难构造性二难 18应用分析 推理定律推理定律 (续续) (AB) ( AB) (AA) B 构造性二难（特殊形式）构造性二难（特殊形式） (AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难 说明：说明： (1)A, B, C为元语言符号，代表任意的命题公式。为元语言符号，代表任意的命题公式。 (2)若某推理符合某条推理定律，则它自然是正确的若某推理符合某条推理定律，则它自然是正确的. (3)AB产生两条推理定律产生两条推理定律: A B, B A. 19应用分析 20应用分析 实例实例 例例 判断下面推理是否正确判断下面推理是否正确 (1) 若今天是若今天是1号

13、，则明天是号，则明天是5号号. 今天是今天是1号号. 所所 以明天是以明天是5号号. 解解 设设 p：今天是：今天是1号，号，q：明天是：明天是5号号. 证明的形式结构为证明的形式结构为: (pq) pq 证明（用等值演算法）证明（用等值演算法） (pq) pq ( p q) p) q pq q 1 得证推理正确得证推理正确 21应用分析 实例实例 (续续) (2) 若今天是若今天是1号，则明天是号，则明天是5号号. 明天是明天是5号号. 所以今天是所以今天是1 号号. 解解 设设p：今天是：今天是1号，号，q：明天是：明天是5号号. 证明的形式结构为证明的形式结构为: (pq) qp 证明（

14、用主析取范式法）证明（用主析取范式法） (pq) qp ( p q) qp ( p q) q) p q p ( pq) (pq) (pq) (p q) m0 m2 m3 结果不含结果不含m1, 故故01是成假赋值，所以推理不正确是成假赋值，所以推理不正确. 22应用分析 重要的推理定律（重要的推理定律（重言蕴涵式重言蕴涵式 ） A (A B) 附加律附加律 (A B) A 化简律化简律 (AB) A B 假言推理假言推理 (AB)B A 拒取式拒取式 (A B)B A 析取三段论析取三段论 (AB) (BC) (AC) 假言三段论假言三段论 (AB) (BC) (AC) 等价三段论等价三段论

15、(AB) (CD) (A C) (B D) 构造性二难构造性二难 23应用分析 推理定律推理定律 (续续) (AB) ( AB) (AA) B 构造性二难（特殊形构造性二难（特殊形 式）式） (AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难 说明：说明： A, B, C为元语言符号为元语言符号 若某推理符合某条推理定律，则它自然是正确的若某推理符合某条推理定律，则它自然是正确的 AB产生两条推理定律产生两条推理定律: A B, B A 24应用分析 3.2 自然推理系统P n判断推理是否正确的三种常用方法：判断推理是否正确的三种常用方法： 1. 1.真值表技术真值表技术 2.

16、2.演绎法演绎法 3. 3.间接证明方法间接证明方法 当命题变项较多时，以上三种方法的演当命题变项较多时，以上三种方法的演 算量太大，此时可考虑推理证明的方法。算量太大，此时可考虑推理证明的方法。 而要构造严谨的证明必须要在形式系统中而要构造严谨的证明必须要在形式系统中 进行。进行。 25应用分析 形式系统的定义 n一个形式系统一个形式系统I由下面四个部分组成：由下面四个部分组成： （1）非空的字母表，记做）非空的字母表，记做A(I)。 （2） A(I)中符号构造的合式公式集，记做中符号构造的合式公式集，记做E(I)。 （3） E(I)中一些特殊的公式组成的公理集，记做中一些特殊的公式组成的公

17、理集，记做Ax(I) 。 （4）推理规则集，记做）推理规则集，记做R(I)。 可以将可以将I记为记为4元组元组。其中。其中 是是I的形式语言系统，而的形式语言系统，而为为I 的形式演算系统。的形式演算系统。 26应用分析 形式系统的分类 （1）自然推理系统自然推理系统 它的特点是从任意给 定的前提前提出发，应用系统中的推理规则进 行推理演算，得到的最后命题公式是推理 的结论（可能是重言式，也可能不是可能是重言式，也可能不是）。 （2）公理推理系统公理推理系统 它的特点是只能从若干 条给定的公理公理出发，应用系统中的推理规 则进行演算，得到的是系统中的定理（是是 重言式重言式）。 27应用分析

18、定义3.3 自然推理系统P定义如下： 1、字母表 （1）命题变项符号：p，q，r， （2）联结词符号： , , , , , , , , （3）括号与逗号 ： （ ） ， ， 2、合式公式 (参见定义1.6 P10） 3、 推理规则 28应用分析 推理规则推理规则 （1）前提引入规则 ：在证明的任何步骤上 都可以引入前提。 （2）结论引入规则：在证明的任何步骤上 所得到的结论都可以做为后续证明的前提。 （3）置换规则：在证明的任何步骤上所得 到的结论都可以作为后续证明的前提。 29应用分析 推理规则推理规则 （续）（续） (4) 假言推理规则假言推理规则 AB A B (5) 附加规则附加规则

19、A A B (6) 化简规则化简规则 A B A (7) 拒取式规则拒取式规则 AB B A (8) 假言三段论规则假言三段论规则 AB BC AC 30应用分析 推理规则推理规则( (续续) ) (11) 破坏性二难推理破坏性二难推理 规则规则 AB CD BD AC (12) 合取引入规则合取引入规则 A B A B (9) 析取三段论规则析取三段论规则 A B B A (10)构造性二难推理构造性二难推理 规则规则 AB CD A C B D 31应用分析 构造证明构造证明直接证明法直接证明法 n例例3.3 在自然推理系统在自然推理系统P中构造下面推理的证明；中构造下面推理的证明； （1

20、） 前提：前提：p q， q r， p s ， s 结论：结论：r （p q） （2）前提：）前提： p q， r q ，r s 结论：结论：p s 32应用分析 （1） 前提：前提：p q， q r， p s ， s 结论：结论：r （p q） 证明证明: (1) p s 前提引入前提引入 (2) s 前提引入前提引入 (3) p (1)(2)拒取式拒取式 (4) p q 前提引入前提引入 (5) q (3)(4)析取三段论析取三段论 (6) q r 前提引入前提引入 (7) r (5)(6)假言推理假言推理 (8) r （p q） (7)(4)合取合取 33应用分析 （2）前提：）前提：

21、p q， r q ，r s 结论：结论：p s 证明： (1) p q 前提引入前提引入 (2) p q (1)置换置换 (3) r q 前提引入前提引入 (4) q r (3)置换置换 (5) p r (2)(4)假言三段论假言三段论 (6) r s 前提引入前提引入 (7) p s (5)(6)假言三段论假言三段论 34应用分析 构造证明构造证明直接证明法直接证明法 n例例3.4 在自然推理系统在自然推理系统P中构造下面推理的证明；中构造下面推理的证明； 若若a是实数，则它不是无理数就是有理数。是实数，则它不是无理数就是有理数。 若若a不能表示成分数，则它不是有理数。不能表示成分数，则它不

22、是有理数。a是实数且是实数且 它不能表示成分数。所以它不能表示成分数。所以a是无理数。是无理数。 解：首先将简单命题符号化：解：首先将简单命题符号化： p：a是实数。是实数。 q ：a是有理数。是有理数。 r：a是无理数。是无理数。 S：a能表示成分数。能表示成分数。 则可知：则可知： 前提：前提： p (q r) ， s q ， p s 结论：结论：r 35应用分析 前提：前提： p (q r) ， s q ， p s 结论：结论：r 证明证明: (1) p s 前提引入前提引入 (2) p (1)化简 (3) s (1)化简 (4) p (q r) 前提引入前提引入 (5) q r (2)

23、(4)假言推理假言推理 (6) s q 前提引入前提引入 (7) q (3)(6)假言推理假言推理 (8) r (5)(7)析取三段论析取三段论 36应用分析 构造证明构造证明附加前提证明法附加前提证明法 欲证明欲证明 前提：前提：A1, A2, , Ak 结论：结论：CB 等价地证明等价地证明 前提：前提：A1, A2, , Ak, C 结论：结论：B 理由：理由： (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B 将 C 称 为 附 加 前 提 37应用分析 附加前提证明法附加前提证明法 n例例3.5 在自然推理

24、系统在自然推理系统P中构造下面推理的证明。中构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影。如果小张和小王去看电影，则小李也去看电影。 小赵不去看电影或小张去看电影。小王去看电影。小赵不去看电影或小张去看电影。小王去看电影。 所以，当小赵去看电影时，小李也去。所以，当小赵去看电影时，小李也去。 解：将简单命题符号化：解：将简单命题符号化： p：小张去看电影：小张去看电影 q：小王去看电影：小王去看电影 r：小李去看电影：小李去看电影 s：小赵去看电影：小赵去看电影 38应用分析 前提：（前提：（p q） r ， s p ，q 结论：结论：s r 证明：证明：(1) (1) s

25、附加前提引入附加前提引入 (2) (2) s p 前提引入前提引入 (3) (3) p (1)(2)析取三段论析取三段论 (4) (4) （p q） r 前提引入前提引入 (5) (5) q 前提引入前提引入 (6) (6) p q (3)(5)(3)(5)合取合取 (7) (7) r (4)(6) (4)(6)假言推理假言推理 39应用分析 附加前提证明法附加前提证明法 (续续) 2 2 2 例例 构造下面推理的证明构造下面推理的证明: 2是素数或合数是素数或合数. 若若2是素数，则是素数，则 是无理数是无理数. 若若 是无理数，则是无理数，则4不是素数不是素数. 所以，如果所以，如果4是是

26、 素数，则素数，则2是合数是合数. 用附加前提证明法构造证明用附加前提证明法构造证明 解解 设设 p：2是素数，是素数，q：2是合数，是合数， r： 是无理数，是无理数，s：4是素数是素数 形式结构形式结构 前提：前提：p q, pr, rs 结论：结论：sq 2 2 2 40应用分析 附加前提证明法附加前提证明法 (续续) 证明证明 s 附加前提引入附加前提引入 pr 前提引入前提引入 r s 前提引入前提引入 p s 假言三段论假言三段论 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 请用直接证明法证明之请用直接证明法证明之 41应用分析 构造证明构造证明归谬法（反证法）归谬法（反证法） 欲证明欲证明 前提：前提：A1, A2, , Ak 结论：结论：B 将将 B加入前提，若推出矛盾，则得证推理正确加入前提，若推出矛盾，则得证推理正确. 理由理由: A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB) 括号内部为矛盾式当且仅当括号内部为矛