第一部分 第三章 命题逻辑的推理理论

1、第三章第三章 命题逻辑的推理理论命题逻辑的推理理论3.1 3.1 推理的形式结构推理的形式结构3.2 3.2 自然推理系统自然推理系统 P P 推理的例子推理的例子止楚攻宋的故事止楚攻宋的故事 如果一个人放着自己的豪华马车不坐，却想偷如果一个人放着自己的豪华马车不坐，却想偷邻居的破车；放着自己的锦绣衣裳不穿，却想邻居的破车；放着自己的锦绣衣裳不穿，却想偷邻居的黑粗布褂，他必定患了偷窃病。偷邻居的黑粗布褂，他必定患了偷窃病。 楚王就是这样的人；楚王就是这样的人； 所以楚王有偷窃病。所以楚王有偷窃病。 墨经墨经、墨辨墨辨3.1 3.1 推理的形式结构推理的形式结构 定义：定义： 推理推理就是从就是

2、从前提前提出发推出出发推出结论结论的思维的思维过程。过程。前提与结论都是一组命题公式前提与结论都是一组命题公式。 推理的推理的形式结构形式结构： AA1 1,A,A2 2,A,Ak k B B 从从形式形式的角度研究推理的规律。的角度研究推理的规律。有效有效( (正确）的推理正确）的推理定义定义3.13.1对于任意一组赋值，对于任意一组赋值， 或者或者A A1 1 A A2 2 A Ak k为假，为假，B B任意任意 或者或者A A1 1 A A2 2 A Ak k为真，为真，B B也为真也为真则推理则推理AA1 1,A,A2 2,A,Ak k B B 为为有效的、正确的有效的、正确的 称称B

3、 B是是有效的结论有效的结论, ,记为记为 AA1 1,A,A2 2,A,Ak k B B 注意：注意：有效的结论并不能保证一定为真有效的结论并不能保证一定为真。例题例题【例【例3.13.1】 判断推理是否正确判断推理是否正确 （1 1）p,pq qp,pq q （2 2）p,qp qp,qp q推理的蕴涵式结构推理的蕴涵式结构定理定理3.13.1 推理推理AA1 1,A,A2 2,A,Ak k B B 为有效的、正确的为有效的、正确的，当且仅当当且仅当 （A A1 1AA2 2AAk k）BB 为重言式。为重言式。 推理的形式结构推理的形式结构 （A A1 1AA2 2AAk k） B B

4、若（若（A A1 1AA2 2AAk k）BB）1 1，即推理是有，即推理是有效（正确）的，记为：效（正确）的，记为： A A1 1AA2 2AAk k B B判断推理正确的方法判断推理正确的方法 前提：前提： A A1 1，A A2 2，A Ak k 结论：结论： B B 形式结构形式结构 （A A1 1AA2 2AAk k） B B四种方法四种方法 1.1. 真值表法真值表法 2. 2. 等值演算法等值演算法 3. 3. 主析取范式法主析取范式法 4. 4. 推理定律法（蕴涵演算法）推理定律法（蕴涵演算法）例题例题: :判断推理是否正确判断推理是否正确【例】【例】“如果我有时间，那么我就去

5、上街；如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。有去书店买书，所以我没有时间。” 令令 p p：我有时间。：我有时间。 q q：我去上街。：我去上街。 r r：我去书店买书。：我去书店买书。 前提：前提：pqpq，qrqr，rr 结论：结论：pp 结论结论例题例题pqrpq qrrp00011110011101010101101111011000110101010011010101111100 (p(pq)q)(q(qr)r)r r p p推理的形式结构：推理的形式结构： （(pq)(qr)r ） p

6、真值表真值表形式上有效的推形式上有效的推理理九条推理定律九条推理定律重言蕴涵式：重言蕴涵式：1.1.附加律附加律 A AABAB， B BABAB2.2.化简律化简律 ABABA A， ABABB B3.3.假言推理假言推理 A(AB)A(AB)B B4.4.拒取式拒取式 B(AB)B(AB)A A联言推理联言推理ABABA A， ABABB B或或 A,BA,B ABAB 一个旅行家到欧洲旅行，要坐船回英国。一个旅行家到欧洲旅行，要坐船回英国。但仅有买船票的钱了，准备饿着肚子乘但仅有买船票的钱了，准备饿着肚子乘船了。船了。 挨了一天，实在受不了了。到餐厅吃完挨了一天，实在受不了了。到餐厅吃完

7、饭，要帐单。饭，要帐单。 侍者告诉他：饭费含在船票里了。侍者告诉他：饭费含在船票里了。充分条件假言推理充分条件假言推理A(AB)A(AB)B B 史密斯先生看到一群小孩围着一只小狗。史密斯先生看到一群小孩围着一只小狗。问问: :你们干什么呢？你们干什么呢？ “我们在比赛说谎。谁的谎话最大，谁我们在比赛说谎。谁的谎话最大，谁就能得到这只小狗。就能得到这只小狗。” 史密斯：胡闹！我在你们这个年龄，可史密斯：胡闹！我在你们这个年龄，可从来不说谎话。从来不说谎话。 “史密斯先生，你赢了，小狗归你。史密斯先生，你赢了，小狗归你。”必要条件假言推理必要条件假言推理B(AB)B(AB)AA 一班文武官员在看

8、一班文武官员在看七擒孟获七擒孟获的川剧。的川剧。 一个武官：真想不到，孟子的后代孟获居一个武官：真想不到，孟子的后代孟获居然如此野蛮。众人听后，不禁掩口而笑。然如此野蛮。众人听后，不禁掩口而笑。 哪知一个文官接口道：仁兄所见极是，还哪知一个文官接口道：仁兄所见极是，还是孔夫子的后代孔明强一些。是孔夫子的后代孔明强一些。 推理推理：如果孟获是孟子的后代，那么孔明：如果孟获是孟子的后代，那么孔明就是孔子的后代了；孔明不是孔子的后代。就是孔子的后代了；孔明不是孔子的后代。所以，所以，九条推理定律九条推理定律重言蕴涵式：重言蕴涵式：5.5.析取三段论析取三段论 A(AB)A(AB)B B B(AB)B

9、(AB)A A6.6.假言三段论假言三段论 (AB)(BC)(AB)(BC)(AC)(AC)7.7.等价三段论等价三段论 (A(AB)(BB)(BC)C)(A(AC)C)选言推理选言推理析取三段论析取三段论 (AB)A(AB)AB B 有一个议员为了竞选州长请海明威为其写一篇颂扬有一个议员为了竞选州长请海明威为其写一篇颂扬的文章。的文章。 第二天，议员收到海明威送来的一封信，却是一封第二天，议员收到海明威送来的一封信，却是一封情书。情书。 议员以为海明威弄错了，还是要求帮忙。议员以为海明威弄错了，还是要求帮忙。 议员又收到海明威送来的一封信，却是一封遗嘱。议员又收到海明威送来的一封信，却是一封

10、遗嘱。 海明威：我家除了情书，就是遗嘱，你还要什么呢？海明威：我家除了情书，就是遗嘱，你还要什么呢？ 选言推理选言推理析取三段论析取三段论 (AB)A(AB)AB B 莎莎替爸爸到邮局买邮票，不知该怎么称呼莎莎替爸爸到邮局买邮票，不知该怎么称呼柜台里的阿姨，想到人们常称呼爸爸柜台里的阿姨，想到人们常称呼爸爸“老老板板”，就说：，就说：“老板，我买邮票。老板，我买邮票。”。 “我不是老板，以后别这么喊，好吗？我不是老板，以后别这么喊，好吗？” 过了几天，莎莎又来买邮票：老板娘，我买过了几天，莎莎又来买邮票：老板娘，我买邮票。邮票。九条推理定律九条推理定律重言蕴涵式：重言蕴涵式：8.8.构造性二难

11、构造性二难 (AB)(CD)(AC) (AB)(CD)(AC) BDBD (AB)(AB)(AB)AB)(A(AA)A) B B9.9.破坏性二难破坏性二难 (AB)(CD)(AB)(CD)(BBD) D) ( (AAC)C)上帝不是全能的上帝不是全能的上帝能否创造一块连他自己也举不起的石头？上帝能否创造一块连他自己也举不起的石头？ 如果能，则上帝不是全能的；如果能，则上帝不是全能的； 如果不能，上帝也不是全能的；如果不能，上帝也不是全能的； 或者上帝能创造一块连他自己也举不起的石或者上帝能创造一块连他自己也举不起的石头，或者不能，总之上帝不是全能的。头，或者不能，总之上帝不是全能的。苏格拉底

12、苏格拉底 如果你娶到一个好老婆，你会获得人生的如果你娶到一个好老婆，你会获得人生的幸福；幸福； 如果你娶到一个坏老婆，你会成为一个哲如果你娶到一个坏老婆，你会成为一个哲学家；学家； 或者娶到好老婆，或者娶到坏老婆；或者娶到好老婆，或者娶到坏老婆； 所以，你或者获得幸福，或者成为哲学家。所以，你或者获得幸福，或者成为哲学家。不死酒不死酒 有人向汉武帝献不死酒，被东方朔偷去喝有人向汉武帝献不死酒，被东方朔偷去喝掉了。掉了。 汉武帝大怒，要杀东方朔。汉武帝大怒，要杀东方朔。 东方朔说：东方朔说： 我喝的是不死酒，你杀不死我；我喝的是不死酒，你杀不死我； 如果我被杀了，不死酒就是假的。如果我被杀了，不

13、死酒就是假的。竹竿进城竹竿进城 一个人进城，横着、竖着都进不一个人进城，横着、竖着都进不了城门。了城门。 一个智者告诉他：为什么不锯成一个智者告诉他：为什么不锯成两截呢？两截呢？ 顺着拿顺着拿P P先生是哪个岛上的人？先生是哪个岛上的人？ 两个岛，两个岛，A A岛上的人说真话、岛上的人说真话、B B岛上的人说假岛上的人说假话。两个岛上的人相互往来。话。两个岛上的人相互往来。 航海家来到一个岛上，碰到航海家来到一个岛上，碰到P P先生。不知他先生。不知他是哪个岛上的人，也不知道这是哪个岛。是哪个岛上的人，也不知道这是哪个岛。 P P先生回答问题只能用先生回答问题只能用“是是”或或“不是不是”。

14、提一个问题，判断提一个问题，判断P P先生是哪个岛的；先生是哪个岛的； 再提一个问题，判断所到的是哪一个岛。再提一个问题，判断所到的是哪一个岛。只提一个问题，判别所到的只提一个问题，判别所到的是哪一个岛。是哪一个岛。3.2 3.2 自然推理系统自然推理系统P P【例】用推理定理证明【例】用推理定理证明 (pq)(qr)p(pq)(qr)pr r 证明：证明： pq pq p p q q 假言推理假言推理 qr qr r r 假言推理假言推理公式序列公式序列前提前提结论结论自然推理系统自然推理系统P P中的证明过程中的证明过程 证明的过程是构造一个证明的过程是构造一个命题公式序列命题公式序列 每

15、个公式或者是已知的前提，或者是中每个公式或者是已知的前提，或者是中间结果间结果。 换言之，证明的过程是换言之，证明的过程是真值真值1 1传递传递的过程。的过程。 证明需要在证明需要在形式系统形式系统中进行。中进行。形式系统形式系统定义定义3.23.2 一个形式系统一个形式系统 I I 由四部分组成：由四部分组成：（1 1）非空的）非空的字母表字母表 A A；（2 2）合式公式集合式公式集 E E，每个公式仅含字母表中的符号；，每个公式仅含字母表中的符号；（3 3）公理集公理集 A AX X，每个公理来自于公式集，每个公理来自于公式集E E；（4 4）推理规则集推理规则集 R R。 记为记为 I

16、=A,E,AI= ,R 四元组（四元组（4 tuple)4 tuple)的形式。的形式。 形式系统分为形式系统分为自然推理系统自然推理系统与与公理推理系统公理推理系统。自然推理系统自然推理系统P P定义定义3.33.3 一个自然推理系统一个自然推理系统 P P 由三部分组成：由三部分组成： 1.1.字母表字母表 （1 1）命题变元符号：）命题变元符号：p,q,r, p,q,r, （2 2）联结词符号：）联结词符号：， （3 3）逗号，与括号（）逗号，与括号（） 2.2.合式公式合式公式 3.3.推理规则推理规则推理规则推理规则（1 1）前提引入规则前提引入规则 在证明的任何步骤上，都可以引入前

17、提。在证明的任何步骤上，都可以引入前提。 （2 2）结论引入规则结论引入规则 在证明的任何步骤上，所得到的结论均可作在证明的任何步骤上，所得到的结论均可作后续证明的前提加以引用。后续证明的前提加以引用。 （3 3）置换规则置换规则 在证明的任何步骤上，命题公式中的任何子在证明的任何步骤上，命题公式中的任何子公式都可以用与之等值的公式置换。公式都可以用与之等值的公式置换。推理规则推理规则（4 4）假言推理规则（或分离规则）假言推理规则（或分离规则）： ABAB A A B B （5 5）附加规则附加规则： A A ABAB推理规则推理规则（6 6）化简规则化简规则： ABAB A A （7 7）

18、拒取式规则拒取式规则： ABAB B B A A （8 8，9 9）三段论规则三段论规则： AB ABAB AB BC B BC B AC AAC A 推理规则推理规则（1010）构造性二难推理规则构造性二难推理规则： ABAB CD CD ACAC BD BD（1111）破坏性二难推理规则破坏性二难推理规则： ABAB CD CD B DB D A A C C通过附加前提，通过附加前提，可由其它规则推可由其它规则推出出推理规则推理规则（1212）合取引入规则合取引入规则： 在证明的在证明的序列序列中出现公式中出现公式A A与与B B，则，则可以在任意步引入可以在任意步引入ABAB。 A A

19、B B ABAB 自然推理系统中的自然推理系统中的“证明证明” 有效的推理：有效的推理： 前提：前提： A A1 1，A A2 2，A Ak k 结论：结论： B B 记为：记为：A A1 1AA2 2AAk k B B它的它的证明证明就是构造就是构造“公式序列公式序列”： C C1 1，C C2 2，C Cl l满足：满足： 每个每个C Ci i要么是某个前提要么是某个前提A Aj j； 要么由推理规则得到；要么由推理规则得到； 且且C Cl lB B。 例题例题【例【例3.43.4】 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明： 若若a a是实数，则它不是

20、有理数就是无理数；是实数，则它不是有理数就是无理数； 若若a a不能表示成分数，则它不是有理数；不能表示成分数，则它不是有理数； a a是实数且不能表示成分数；是实数且不能表示成分数； 所以所以，a a是无理数。是无理数。 解：命题与推理的符号化解：命题与推理的符号化 p p：a a是实数；是实数； q q：a a是有理数；是有理数； r r：a a是无理数；是无理数； s s：a a能表示成分数。能表示成分数。形式化与规范化的形式化与规范化的“证明证明”前提：前提：p(qr), sq, psp(qr), sq, ps结论：结论：r r 证明证明：（1 1）ps ps 前提引入前提引入（2 2

21、）P P （1 1）化简）化简（3 3）s s （1 1）化简）化简（4 4）p(qr) p(qr) 前提引入前提引入（5 5）qr qr （2 2）（）（4 4）假言推理）假言推理 （6 6）sq sq 前提引入前提引入（7 7）q q （3 3）（）（6 6）假言推理）假言推理 （8 8）r r （5 5）（）（7 7）三段论）三段论例题例题【例【例3.33.3】 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明： 前提：前提：pq, qr, ps, pq, qr, ps, s s 结论：结论：r(pq) r(pq) 证明证明：（1 1）ps ps 前提引入前提

22、引入（2 2）s s 前提引入前提引入（3 3）p p （1 1）（）（2 2）拒取式）拒取式（4 4）pq pq 前提引入前提引入（5 5）q q （3 3）（）（4 4）三段论）三段论 （6 6）qr qr 前提引入前提引入（7 7）r r （5 5）（）（6 6）假言推理）假言推理 （8 8）r(pq) r(pq) （4 4）（）（7 7）合取引入）合取引入练习练习在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明：（1 1）前提：）前提：p(qr), pqp(qr), pq 结论：结论： r s r s （2 2）前提：）前提：(pq)r, r s, (pq)r, r s, sp sp 结论：结论： q q三种证明方法三种证明方法直接证明法直接证明法附加前提证明法附加前提证明法归谬法归谬法附加前提证明法附加前提证明法适用范围：结论为蕴涵式适用范围：结论为蕴涵式 A A1 1AA2 2AAn n(AB)(AB) 将推理形式转化为等值形式：将推理形式转化为等值形式： A A1 1AA2 2AAn n AAB B例题例题【例【例3.53.5】 在自然推理系统在自然推理系统P P中构造下面推理的证明：中构造下面推理的证明： 前提：前提：(pq)r, (pq)r, sp, qsp, q 结论：结论： sr sr 证明证明：（1 1）s s 附加前提引入