第三章:命题逻辑的推理理论 第一节：推理的形式结构 第二节：自然推理系统P

第三章:命题逻辑的推理理论 主要内容 推理的形式结构 推理的正确与错误 判断推理正确的方法 推理定律 自然推理系统P 形式系统的定义与分类

3.1 推理形式结构 逻辑(语义)蕴涵：给定A1,…,Ak和B 讨论 符号：{A1,…,Ak} ⊨ B 对任意赋值v: 如果v(Ai)=T,则v(B)=T 或者存在Ai使得v(Ai)=F 称由前提A1,…,Ak 推出结论B的推理是有效的 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, v(Ai)=T则v(B)=T 所以v(A1…Ak  B)=T 充分性：任意v, v(A1…Ak  B)=T 如果v(Ai)=T则v(B)=T

3.1 推理形式结构 蕴涵元符号： A1…Ak  B 代表 {A1,…,Ak} ⊨ B 推理形式结构 前提A1,…,Ak 结论：B

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

推理实例 例1 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. 例1 判断下面推理是否正确 (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 化简律 (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  (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) T

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)= 公理推理系统 推出的结论是系统中的重言式, 称作定理 感兴趣的可以阅读《GEB－－一条永恒的金带》

有一位理发师声称，他给所有不给自己理发的人理发 爱皮梅尼特是一个克里特岛人。他说：“所有的克里特岛人都撤谎。” 第一类集合不能以自己为元素，也就是说自己不能属于自己，我们称为r型。第二类集合可以以自己为元素，我们称为s型。 证明《数学原理》所定义的系统既是一致的(无矛盾)又是完备的(该系统的理论框架中容纳了每个正确的数论命题)。这就是数学史上著名的希尔伯特纲领。

自然推理系统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 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 例：考虑下述论证 设 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

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

练习P53, 14(6) P54 15 (2)

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

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

P54 16(2)

第三章 习题课 主要内容 推理的形式结构 判断推理是否正确的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系统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 解 推理的形式结构： (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：构造证明 2. 在系统P中构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和 园游人太多，就不去颐和园. 今天是周六，并且颐和园游 人太多. 所以, 我们去圆明园或动物园玩. 证明： (1) 设 p：今天是周六，q：到颐和园玩， r：到圆明园玩，s：颐和园游人太多 t：到动物园玩 (2) 前提：p(qr), sq, p, s 结论：rt

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

3.2 自然推理系统P 公理推理系统 命题变项符号，联接词符号，括号、逗号 合式公式 公理集合 推理规则 A  B A 结论：B

3.2 自然推理系统P 公理集合 A  (B  A) (A  (B  C))((A  B)  (A  C)) ( A  B)  ((A  B)  A)

3.2 自然推理系统P 形式推演(语法蕴涵)：给定A1,…,Ak和B 符号：{A1,…,Ak} ⊢ B 存在公式序列C1, C2,…,Cn，对每个i(i=1,…,n), Ci是某个Aj Ci是某个公理或者 存在k,ji, Cj= Ck  Ci Cn=B 称C1,…,Cn是有A1,…,Ak推B的证明

3.2 自然推理系统P 命题演算的可靠性 命题演算的完备性 {A1,…,Ak} ⊢ B iff {A1,…,Ak} ⊨ B