第三章：命题逻辑的推理理论

1、1第三章第三章:命题逻辑的推理理论命题逻辑的推理理论q主要内容主要内容l推理的形式结构推理的形式结构l自然推理系统自然推理系统pq本章与其他各章的联系本章与其他各章的联系l本章是第五章的特殊情况和先行准备本章是第五章的特殊情况和先行准备2 第一节：推理的形式结构第一节：推理的形式结构33.1 推理形式结构推理形式结构q何为推理？何为证明？何为推理？何为证明？ 例子：例子： （1）若）若a b且且c d，则，则a c b d （2）若今天是星期一，则明天是星期二）若今天是星期一，则明天是星期二 （3）若）若a c b d，则，则a b且且c dq推理推理 从前提出发推出结论的思维过程从前提出发推

2、出结论的思维过程 上例中，（上例中，（1），（），（2）是正确的推理，而）是正确的推理，而（3）是错误的推理）是错误的推理q证明证明 描述推理正确或错误的过程描述推理正确或错误的过程 43.1 推理形式结构推理形式结构q逻辑逻辑(语义语义)蕴涵：给定蕴涵：给定a1,ak和和bv对任意赋值对任意赋值v: 如果如果v(ai)=t,则则v(b)=t 或者存在或者存在aj，使得使得v(aj)=fv称由前提称由前提a1,ak 推出结论推出结论b的推理是有效的的推理是有效的vb为有效结论为有效结论v符号：符号：a1,ak bq讨论讨论v蕴涵跟蕴涵式的关系？蕴涵跟蕴涵式的关系？v注意注意: 推理正确不能保证

3、结论一定正确推理正确不能保证结论一定正确5q 例子例子vp, p q qvp, q p qpqp(pq)qp(q p)qffffffftftfttffftftttttt3.1 推理形式结构推理形式结构6q定理：定理：a1,ak b 当且仅当当且仅当 a1 ak b 为重言式为重言式证明证明 必要性必要性：任意：任意v, 不会出现不会出现a1 ak 为真且为真且 b为假的情况，所以为假的情况，所以v(a1 ak b)=t 充分性充分性：任意：任意v, v(a1 ak b)=t 则或者：则或者： a1 ak 和和b同时为同时为t 或者：或者： a1 ak 为假为假 所以所以a1,ak b 3.1

4、推理形式结构推理形式结构7q蕴涵元符号：蕴涵元符号：qa1 ak b 代表代表 a1,ak bq推理的形式结构推理的形式结构v前提：前提：a1,akv结论：结论：bv推理的形式结构：推理的形式结构： a1 ak b3.1 推理形式结构推理形式结构8q 判断推理是否正确方法判断推理是否正确方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法3.1 推理形式结构推理形式结构99推理实例推理实例例例 判断下面推理是否正确判断下面推理是否正确(1) 若今天是若今天是1号，则明天是号，则明天是5号号. 今天是今天是1号号. 所以所以, 明天是明天是5号号. (2) 若今天是若今天是1号

5、，则明天是号，则明天是5号号. 明天是明天是5号号. 所以所以, 今天是今天是1号号. 解解 设设 p：今天是：今天是1号，号，q：明天是：明天是5号号. (1) 推理的形式结构推理的形式结构: (pq) pq用等值演算法用等值演算法 (pq) pq ( p q) p) q pq q 1 由定理由定理3.1可知推理正确可知推理正确1010推理实例推理实例(2) 推理的形式结构推理的形式结构:(pq) qp 用主析取范式法用主析取范式法 (pq) qp ( p q) qp ( p q) q) p q p ( pq) (pq) (pq) (p q) m0 m2 m3 结果不含结果不含m1, 故故0

6、1是成假赋值，所以推理不正确是成假赋值，所以推理不正确113.1 推理形式结构推理形式结构q推理定律推理定律l推理定律推理定律重言蕴涵式重言蕴涵式l重要的推理定律：重要的推理定律： a (a b) 附加律附加律 (a b) a 化简律化简律例例1： 如果谁骄傲自满，那么他就要落后；小张骄傲自满，如果谁骄傲自满，那么他就要落后；小张骄傲自满， 所以，小张必定要落后所以，小张必定要落后 (ab) a b 假言推理假言推理例例2： 如果谁得了肺炎，他就一定要发烧；小李没发烧，如果谁得了肺炎，他就一定要发烧；小李没发烧， 所以，小李没患肺炎所以，小李没患肺炎 (ab)b a 拒取式拒取式123.1 推

7、理形式结构推理形式结构q例例3： 如果降落的物体不受外力的影响，那么，它不如果降落的物体不受外力的影响，那么，它不 会改变降落的方向；这个物体受到了外力的会改变降落的方向；这个物体受到了外力的 影响，影响， 所以，它会改变降落的方向所以，它会改变降落的方向 q例例4： 如果赵某是走私犯，那么，他应受法律制裁；如果赵某是走私犯，那么，他应受法律制裁； 经查明，赵某确实受到了法律制裁，经查明，赵某确实受到了法律制裁， 所以，赵某是走私犯所以，赵某是走私犯133.1 推理形式结构推理形式结构q例例5： 我要么选择汤要么选择色拉；我不选择汤。我要么选择汤要么选择色拉；我不选择汤。 所以，我选择色拉所以

8、，我选择色拉 (a b)b a 析取三段论析取三段论q例例6： 如果我不能起床，则我不能上班。如果我不能起床，则我不能上班。 如果我不能上班，则我不能得到报酬。如果我不能上班，则我不能得到报酬。 所以，如果我不能起床，则我不能得到报酬所以，如果我不能起床，则我不能得到报酬 (ab) (bc) (ac) 假言三段论假言三段论 (ab) (bc) (ac) 等价三段论等价三段论143.1 推理形式结构推理形式结构q 例例7： 东方朔偷饮了汉武帝求得的据说饮了能够不死的酒，东方朔偷饮了汉武帝求得的据说饮了能够不死的酒，汉武帝要杀他，他说：汉武帝要杀他，他说：“如果这酒真能使人不死，那么如果这酒真能使

9、人不死，那么你就杀不死我；如果这酒不能使人不死你就杀不死我；如果这酒不能使人不死(你能杀得死我你能杀得死我)，那么它就没有什么用处（不必杀我）；这酒或者能使人那么它就没有什么用处（不必杀我）；这酒或者能使人不死，或者不能使人不死；所以你或者杀不死我，或者不死，或者不能使人不死；所以你或者杀不死我，或者不必杀我。不必杀我。” (ab) (cd) (a c) (b d) 构造性二难构造性二难 (ab) ( ab) b 构造性二难构造性二难 （特殊形式）（特殊形式）153.1 推理形式结构推理形式结构q例例8： if it rains, we will stay inside. if it is s

10、unny, we will go for a walk. either we will not stay inside, or we will not go for a walk. therefore, either it will not rain, or it will not be sunny. (ab) (cd) ( bd) ( ac) 破坏性二难破坏性二难163.1 推理形式结构推理形式结构q普罗泰戈拉收了一名学生叫欧提勒士。普氏与他签订了这样一份合同：前者向后普罗泰戈拉收了一名学生叫欧提勒士。普氏与他签订了这样一份合同：前者向后者传授辩论技巧，教他帮人打官司；后者入学时交一半学费，

11、另一半学费则在他者传授辩论技巧，教他帮人打官司；后者入学时交一半学费，另一半学费则在他毕业后帮人打官司赢了之后再交。时光荏苒，欧氏从普氏那里毕业了。但他总不毕业后帮人打官司赢了之后再交。时光荏苒，欧氏从普氏那里毕业了。但他总不帮人打官司，普氏于是就总得不到那另一半学费。帮人打官司，普氏于是就总得不到那另一半学费。普氏为了要那另一半学费，他去与欧氏打官司，并打着这样的如意算盘：普氏为了要那另一半学费，他去与欧氏打官司，并打着这样的如意算盘： 如果欧氏打赢了这场官司，按照合同的规定，他应该给我另一半学费。如果欧氏打赢了这场官司，按照合同的规定，他应该给我另一半学费。 如果欧氏打输了这场官司，按照法

12、庭的裁决，他应该给我另一半学费。如果欧氏打输了这场官司，按照法庭的裁决，他应该给我另一半学费。 欧氏或者打赢这场官司，或者打输这场官司。欧氏或者打赢这场官司，或者打输这场官司。 总之，他应该付给我另一半学费。总之，他应该付给我另一半学费。 但欧氏却对普氏说：但欧氏却对普氏说： 如果这场官司我打赢了，按照法庭的裁决，我不应该给您另一半学费。如果这场官司我打赢了，按照法庭的裁决，我不应该给您另一半学费。 如果这场官司我打输了，按照合同的规定，我不应该给您另一半学费。如果这场官司我打输了，按照合同的规定，我不应该给您另一半学费。 我或者打赢这场官司，或者打输这场官司。我或者打赢这场官司，或者打输这场

13、官司。 总之，我不应该付另一半学费总之，我不应该付另一半学费 究竟谁的说法对呢？究竟谁的说法对呢？17q推理定律推理定律a (a b)(a b) a(a b) a b(a b) b a(a b) b a(a b) (b c) (a c) (a b) (b c) (a c) (a b) (c d) (a c) (b d)(a b) ( a b) b(a b) (c d) ( b d) ( a c)附加律附加律破坏性二难破坏性二难构造性二难（特殊形式）构造性二难（特殊形式）构造性二难构造性二难等价三段论等价三段论假言三段论假言三段论析取三段论析取三段论拒取式拒取式假言推理假言推理化简律化简律3.1

14、 推理形式结构推理形式结构18证明：证明：(a b) (b c) (a c) (a b) (b c) (a c) ( a b) ( b c) (a c) ( a b) ( b c) (a c) (a b) (b c) (a c) (a b) (b c) ( a c) (a b) a ) (b c) c) ( b a ) (b c) 13.1 推理形式结构推理形式结构19 第二节：自然推理系统第二节：自然推理系统p203.2 自然推理系统自然推理系统pq自然演绎推理自然演绎推理：从一组已知为真的事实出发，：从一组已知为真的事实出发，直接运用经典逻辑推理规则推出结论的过程直接运用经典逻辑推理规则推

15、出结论的过程q为什么要自然演绎为什么要自然演绎(natural deduction)？给出验证给出验证的推理过程的推理过程q需要引入需要引入证明证明的概念的概念 一个描述推理过程的命题公式序列，其中的每个公一个描述推理过程的命题公式序列，其中的每个公式或者是已知前提，或者是由前面的公式应用到推理规式或者是已知前提，或者是由前面的公式应用到推理规则得到的结论则得到的结论q自然演绎模拟人类的推理自然演绎模拟人类的推理a1 ak b213.2 自然推理系统自然推理系统p定义定义3.2 一个一个形式系统形式系统 i 由下面四个部分组成：由下面四个部分组成： (1) 非空的字母表，记作非空的字母表，记作

16、 a(i). (2) a(i) 中符号构造的合式公式集，记作中符号构造的合式公式集，记作 e(i). (3) e(i) 中一些特殊的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作 ax(i). (4) 推理规则集，记作推理规则集，记作 r(i). 记记i=, 其中其中是是 i 的的形形式语言系统式语言系统, 是是 i 的的形式演算系统形式演算系统.自然推理系统自然推理系统: 无公理无公理, 即即ax(i)=公理推理系统公理推理系统 推出的结论是系统中的重言式推出的结论是系统中的重言式, 称作称作定理定理22自然推理系统自然推理系统p定义定义3.3 自然推理系统自然推理系统 p 定义如

17、下定义如下:1. 字母表字母表 (1) 命题变项符号：命题变项符号：p, q, r, , pi, qi, ri, (2) 联结词符号：联结词符号： , , , , (3) 括号与逗号：括号与逗号：(, ), ，2. 合式公式（同定义合式公式（同定义1.6）3. 推理规则推理规则 (1) 前提引入规则前提引入规则 (2) 结论引入规则结论引入规则 (3) 置换规则置换规则233.2 自然推理系统自然推理系统pq 假言推理规则假言推理规则 a b a 结论：结论：b(a b) a ball men are mortal socrates is a man therefore socrates is

18、 mortal 243.2 自然推理系统自然推理系统pq 附加规则附加规则 a 结论：结论：a ba (a b)253.2 自然推理系统自然推理系统pq 化简规则化简规则 a b 结论：结论：a q 合取引入规则合取引入规则 a b 结论：结论：a b(a b) a263.2 自然推理系统自然推理系统pq证明证明: p, q, p q r r273.2 自然推理系统自然推理系统pq 证明证明: p, q, p q r r p q p q p q r r推理过程可以写成证明树推理过程可以写成证明树283.2 自然推理系统自然推理系统pq 拒取式规则拒取式规则 a b b 结论：结论： a q 假

19、言三段式规则假言三段式规则 a b b c 结论：结论：a c(a b) b a(a b) (b c) (a c) 293.2 自然推理系统自然推理系统pq 析取三段式规则析取三段式规则 a b b 结论：结论： a q 构造二难推理规则构造二难推理规则 a b c d a c 结论：结论： b d(a b) b a(a b) (c d) (a c) (b d)303.2 自然推理系统自然推理系统pq 破坏性二难推理规则破坏性二难推理规则 a b c d b d 结论：结论： a c (a b) (c d) ( b d) ( a c)313.2 自然推理系统自然推理系统pq 形式推演形式推演(

20、语法蕴涵语法蕴涵)：给定给定a1,ak和和bv 符号：符号：a1,ak bv 存在公式序列存在公式序列c1, c2,cn，对每个，对每个i(i=1,n),ci是某个是某个aj或者或者ci是由序列中前面的公式应用推理规则得到是由序列中前面的公式应用推理规则得到cn=bv 称称c1,cn是由是由a1,ak推推b的证明的证明 323.2 自然推理系统自然推理系统p：考虑下述论证v如果这里有球赛，则通行是困难的如果这里有球赛，则通行是困难的v如果他们按时到达，则通行是不困难的如果他们按时到达，则通行是不困难的v他们按时到达了他们按时到达了 问：得到什么结论？问：得到什么结论？333.2 自然推理系统自

21、然推理系统p：考虑下述论证v 如果这里有球赛，则通行是困难的如果这里有球赛，则通行是困难的v 如果他们按时到达，则通行是不困难的如果他们按时到达，则通行是不困难的v 他们按时到达了他们按时到达了 问：得到什么结论？问：得到什么结论？设设 p:这里有球赛这里有球赛 q:通行是困难的通行是困难的 r:他们按时到达他们按时到达 p q r q r p 343.2 自然推理系统自然推理系统pv 前提前提p q， r q，rv 结论：结论： p 解解： r r q q p q p 前提引入前提引入前提引入前提引入假言推理假言推理前提引入前提引入拒取式拒取式353.2 自然推理系统自然推理系统pc d,

22、c r, d s r s 解解： c d c d d s c s c r r c r s r s 前提引入前提引入前提引入前提引入假言三段论假言三段论前提引入前提引入 置换规则置换规则置换规则置换规则假言三段论假言三段论置换规则置换规则363.2 自然推理系统自然推理系统pq 构造证明的方法构造证明的方法v 附加前提证明法附加前提证明法v 归谬法归谬法 373.2 自然推理系统自然推理系统pq 附加前提证明法附加前提证明法v 对形如对形如 (a1 ak) (a b)的证明的证明 转化为：转化为： a1, , ak, a b383.2 自然推理系统自然推理系统p(p(q s)(rp)q) (r

23、s) 393.2 自然推理系统自然推理系统p(p(q s)(rp)q) (r s) 解解： r rp r p p p(q s) q s q s 前提引入前提引入前提引入前提引入假言推理假言推理前提引入前提引入置换规则置换规则假言推理假言推理假言推理假言推理前提引入前提引入403.2 自然推理系统自然推理系统pq 归谬法归谬法v 对形如对形如 (a1 ak) b的证明的证明 转化为：转化为： a1 ak b为矛盾式为矛盾式413.2 自然推理系统自然推理系统prq rs sq pq p423.2 自然推理系统自然推理系统prq rs sq pq p解解： p p q q s q q s s rs

24、 r rq q43第三章第三章 习题课习题课主要内容主要内容l 推理的形式结构推理的形式结构l 判断推理是否正确的方法判断推理是否正确的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法l 推理定律推理定律l 自然推理系统自然推理系统pl 构造推理证明的方法构造推理证明的方法 直接证明法直接证明法 附加前提证明法附加前提证明法 归谬法归谬法(反证法反证法)44基本要求基本要求l 理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式： 1. (a1 a2 ak)b 2. 前提：前提：a1, a2, , ak 结论：结论：bl 熟练掌握判断推理是否正确的不同方法（

25、如真值熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）表法、等值演算法、主析取范式法等）l 牢记牢记 p 系统中各条推理规则系统中各条推理规则l 熟练掌握构造证明的直接证明法、附加前提证明熟练掌握构造证明的直接证明法、附加前提证明法和归谬法法和归谬法l 会解决实际中的简单推理问题会解决实际中的简单推理问题45练习练习1：判断推理是否正确：判断推理是否正确1. 判断下面推理是否正确判断下面推理是否正确: (1) 前提：前提： pq, q 结论：结论： p 解解 推理的形式结构推理的形式结构: ( pq)qp 方法一：等值演算法方法一：等值演算法 ( pq)qp (p q)q)p ( pq) qp ( p q) ( q q)p p q易知易知10是成假赋值，不是重言式，所以推理不正确是成假赋值，不是重言式，所以推理不正确.46练习练习1解答解答方法二：主析取范式法，方法二：主析取范式法， ( pq)qp (p q)q)p p q m2 m0 m1 m3未含未含m2, 不是重言式不是重言式, 推理不正确推理不正确.47练习练习1解答解答方法三方法三 真值表法真值表法 不是重言式不是重言式, 推理不正确推理不正确111001110100( pq)qpqp pq 0 1 1 1(