第三章:命题逻辑的推理理论 主要内容 推理的形式结构 自然推理系统P 本章与其他各章的联系 本章是第五章的特殊情况和先行准备

第一节：推理的形式结构

3.1 推理形式结构 何为推理？何为证明？ 例子： （1）若AB且CD，则ACBD （2）若今天是星期一，则明天是星期二 （3）若ACBD，则AB且CD 推理 —— 从前提出发推出结论的思维过程 上例中，（1），（2）是正确的推理，而（3）是错误的推理 证明 —— 描述推理正确或错误的过程

3.1 推理形式结构 逻辑(语义)蕴涵：给定A1,…,Ak和B 讨论 对任意赋值v: 称由前提A1,…,Ak 推出结论B的推理是有效的 如果v(Ai)=T,则v(B)=T 或者存在Aj，使得v(Aj)=F 称由前提A1,…,Ak 推出结论B的推理是有效的 B为有效结论 符号：{A1,…,Ak} ⊨ B 讨论 蕴涵跟蕴涵式的关系？ 注意: 推理正确不能保证结论一定正确

3.1 推理形式结构 例子 {p, p  q} ⊨ q {p, q  p} ⊨ q p q p(pq) p(q  p) F T

3.1 推理形式结构 定理：{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 推理形式结构 蕴涵元符号： A1…Ak  B 代表 {A1,…,Ak} ⊨ B 推理的形式结构 前提：A1,…,Ak

3.1 推理形式结构 判断推理是否正确方法 真值表法 等值演算法 主析取范式法

推理实例 例 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. 例 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号，则明天是5号. 明天是5号. 所以, 今天是1号. 解 设 p：今天是1号，q：明天是5号. (1) 推理的形式结构: (pq)pq 用等值演算法 (pq)pq  ((pq)p)q  pqq  1 由定理3.1可知推理正确

推理实例 (pq)qp (2) 推理的形式结构: 用主析取范式法 (pq)qp  (pq)qp  (pq)(pq) (pq)(pq)  m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确

3.1 推理形式结构 推理定律 推理定律——重言蕴涵式 重要的推理定律： A  (AB) 附加律 (AB)  A 化简律 例1： 如果谁骄傲自满，那么他就要落后；小张骄傲自满， 所以，小张必定要落后 (AB)A  B 假言推理 例2： 如果谁得了肺炎，他就一定要发烧；小李没发烧， 所以，小李没患肺炎 (AB)B  A 拒取式

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

3.1 推理形式结构 例5： 我要么选择汤要么选择色拉；我不选择汤。 所以，我选择色拉 (AB)B  A 析取三段论 例6： 如果我不能起床，则我不能上班。 如果我不能上班，则我不能得到报酬。 所以，如果我不能起床，则我不能得到报酬 (AB)(BC)  (AC) 假言三段论 (AB)(BC)  (AC) 等价三段论

3.1 推理形式结构 例7： 东方朔偷饮了汉武帝求得的据说饮了能够不死的酒，汉武帝要杀他，他说：“如果这酒真能使人不死，那么你就杀不死我；如果这酒不能使人不死(你能杀得死我)，那么它就没有什么用处（不必杀我）；这酒或者能使人不死，或者不能使人不死；所以你或者杀不死我，或者不必杀我。” (AB)(CD)(AC)  (BD) 构造性二难 (AB)(AB)  B 构造性二难 （特殊形式）

3.1 推理形式结构 例8： If it rains, we will stay inside. If it is sunny, 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. (AB)(CD)( BD)  (AC) 破坏性二难

3.1 推理形式结构 普罗泰戈拉收了一名学生叫欧提勒士。普氏与他签订了这样一份合同：前者向后者传授辩论技巧，教他帮人打官司；后者入学时交一半学费，另一半学费则在他毕业后帮人打官司赢了之后再交。时光荏苒，欧氏从普氏那里毕业了。但他总不帮人打官司，普氏于是就总得不到那另一半学费。 普氏为了要那另一半学费，他去与欧氏打官司，并打着这样的如意算盘： 如果欧氏打赢了这场官司，按照合同的规定，他应该给我另一半学费。 如果欧氏打输了这场官司，按照法庭的裁决，他应该给我另一半学费。 欧氏或者打赢这场官司，或者打输这场官司。 总之，他应该付给我另一半学费。 但欧氏却对普氏说： 如果这场官司我打赢了，按照法庭的裁决，我不应该给您另一半学费。 如果这场官司我打输了，按照合同的规定，我不应该给您另一半学费。 我或者打赢这场官司，或者打输这场官司。 总之，我不应该付另一半学费 究竟谁的说法对呢？

3.1 推理形式结构 推理定律 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 推理形式结构 证明：(A  B)  (B  C)  (A  C) ((A  B)  A )  ((B  C)  C) (B  A )  (B  C) 1

第二节：自然推理系统P

3.2 自然推理系统P 自然演绎推理：从一组已知为真的事实出发，直接运用经典逻辑推理规则推出结论的过程 为什么要自然演绎(Natural Deduction)？ 给出验证 的推理过程 需要引入证明的概念 一个描述推理过程的命题公式序列，其中的每个公式或者是已知前提，或者是由前面的公式应用到推理规则得到的结论 自然演绎模拟人类的推理 A1…Ak  B

3.2 自然推理系统P 定义3.2 一个形式系统 I 由下面四个部分组成： (1) 非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I). (4) 推理规则集，记作 R(I). 记I=<A(I),E(I),AX(I),R(I)>, 其中<A(I),E(I)>是 I 的形式语言系统, <AX(I),R(I)> 是 I 的形式演算系统. 自然推理系统: 无公理, 即AX(I)= 公理推理系统 推出的结论是系统中的重言式, 称作定理

自然推理系统P 定义3.3 自然推理系统 P 定义如下: 1. 字母表 (1) 命题变项符号：p, q, r, …, pi, qi, ri, … (2) 联结词符号：, , , ,  (3) 括号与逗号：(, ), ， 2. 合式公式（同定义1.6） 3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则

3.2 自然推理系统P 假言推理规则 (A  B)  A  B A  B A 结论：B All men are mortal Socrates is a man Therefore Socrates is mortal

3.2 自然推理系统P 附加规则 A 结论：A  B A  (A  B)

3.2 自然推理系统P 化简规则 A  B 结论：A 合取引入规则 A B 结论：A  B (A  B)  A

3.2 自然推理系统P 证明: p, q, p  q  r ⊨ r

3.2 自然推理系统P 证明: p, q, p  q  r ⊨ r p q p  q p  q  r r 推理过程可以写成证明树

3.2 自然推理系统P 拒取式规则 (A  B)   B   A 假言三段式规则 A  B  B 结论：A B  C 结论：A  C (A  B)   B   A (A  B)  (B  C)  (A  C)

(A  B)  (C  D)  (A  C)  (B  D) 3.2 自然推理系统P 析取三段式规则 A  B  B 结论： A 构造二难推理规则 A  B C  D A  C 结论： B  D (A  B)   B  A (A  B)  (C  D)  (A  C)  (B  D)

(A  B)  (C  D)  ( B   D)  ( A   C) 3.2 自然推理系统P 破坏性二难推理规则 A  B C  D B  D 结论：A  C (A  B)  (C  D)  ( B   D)  ( A   C)

3.2 自然推理系统P 形式推演(语法蕴涵)：给定A1,…,Ak和B 符号：{A1,…,Ak} ⊢ B 存在公式序列C1, C2,…,Cn，对每个i(i=1,…,n), Ci是某个Aj或者 Ci是由序列中前面的公式应用推理规则得到 Cn=B 称C1,…,Cn是由A1,…,Ak推B的证明

3.2 自然推理系统P 例：考虑下述论证 如果这里有球赛，则通行是困难的 如果他们按时到达，则通行是不困难的 他们按时到达了 问：得到什么结论？

3.2 自然推理系统P 例：考虑下述论证 设 p:这里有球赛 q:通行是困难的 r:他们按时到达 p  q r 如果这里有球赛，则通行是困难的 如果他们按时到达，则通行是不困难的 他们按时到达了 问：得到什么结论？ 设 p:这里有球赛 q:通行是困难的 r:他们按时到达 p  q r  q r  p

3.2 自然推理系统P 证明 解： 前提： p  q， r  q，r 结论： p r r  q q p  q p 前提引入 假言推理 前提引入 拒取式

3.2 自然推理系统P 证明 c  d, c  r, d  s ⊢ r  s 解： c  d c  d d  s 前提引入 c  s c  r r  c r  s r  s 前提引入 置换规则 前提引入 假言三段论 前提引入 置换规则 假言三段论 置换规则

3.2 自然推理系统P 构造证明的方法 附加前提证明法 归谬法

3.2 自然推理系统P 附加前提证明法 对形如 (A1…Ak)  (A  B)的证明 转化为： A1, …, Ak, A ⊢ B

3.2 自然推理系统P 证明 ((p(q s))(¬rp)q)  (r  s)

3.2 自然推理系统P 证明 ((p(q s))(¬rp)q)  (r  s) 解： r ¬rp r  p 前提引入 p 置换规则 假言推理 前提引入 假言推理 前提引入 假言推理

3.2 自然推理系统P 归谬法 对形如 (A1…Ak)  B的证明 转化为： A1 … Ak B为矛盾式

3.2 自然推理系统P 证明 ((r¬q)(r∨s)(sq)(pq))  p

3.2 自然推理系统P 证明 ((r¬q)(r∨s)(sq)(pq))  p 解： p p  q q s q

第三章 习题课 主要内容 推理的形式结构 判断推理是否正确的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系统P 构造推理证明的方法 直接证明法 附加前提证明法 归谬法(反证法)

基本要求 理解并记住推理形式结构的两种形式： 1. (A1A2…Ak)B 2. 前提：A1, A2, … , Ak 结论：B 熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等） 牢记 P 系统中各条推理规则 熟练掌握构造证明的直接证明法、附加前提证明法和归谬法 会解决实际中的简单推理问题

练习1：判断推理是否正确 1. 判断下面推理是否正确: (1) 前提：pq, q 结论：p 解 推理的形式结构: 解 推理的形式结构: (pq)qp 方法一：等值演算法 (pq)qp  ((pq)q)p  (pq)qp  ((pq)(qq))p  pq 易知10是成假赋值，不是重言式，所以推理不正确.

练习1解答 方法二：主析取范式法， (pq)qp ((pq)q)p pq M2 m0m1m3

练习1解答 方法三 真值表法 不是重言式, 推理不正确 1 (pq)qp q p pq (pq)q 方法三 真值表法 不是重言式, 推理不正确 1 (pq)qp q p pq (pq)q 方法四 直接观察出10是成假赋值

练习1：判断推理是否正确 (2) 前提：qr, pr 结论：qp

练习1解答 (2) 前提：qr, pr 结论：qp 解 推理的形式结构： (qr)(pr)(qp) 用等值演算法 解 推理的形式结构： (qr)(pr)(qp) 用等值演算法 (qr)(pr)(qp) (( qr)(pr) ) (qp) ((qr)(pr))(qp) ((qp)(qr)(rp))(qp)  ((qp)(qr)(rp))(qp) 1 推理正确

练习2：构造证明 (1) 前提：pq 结论：p(pq) (2)前提：p(qr), sp, q 结论：sr (3)前提：pq, rq, rs 结论：p

练习3：实际问题 3. 在系统P中构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和 园游人太多，就不去颐和园. 今天是周六，并且颐和园游 人太多. 所以, 我们去圆明园或动物园玩. 证明： (1) 设 p：今天是周六，q：到颐和园玩， r：到圆明园玩，s：颐和园游人太多 t：到动物园玩 (2) 前提：p(qr), sq, p, s 结论：rt

练习3解答 (3) 证明： ① p(qr) 前提引入 ② p 前提引入 ③ qr ①②假言推理 ④ sq 前提引入 ⑧ rt ⑦附加

作业 14（4），（6） 15（2） 16（2） 17 18（2）