东南大学：《离散数学》课程教学资源（PPT课件讲稿）第三章 命题逻辑的推理理论

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

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

9第三章:命题逻辑的推理理论 口主要内容 推理的形式结构 ●推理的正确与错误 ●推理的形式结构 判断推理正确的方法 ●推理定律 自然推理系统P ●形式系统的定义与分类 ●自然推理系统P ●在P中构造证明:直接证明法、附加前提证明法、归谬法 2

2 第三章:命题逻辑的推理理论 ❑ 主要内容 推理的形式结构 ⚫ 推理的正确与错误 ⚫ 推理的形式结构 ⚫ 判断推理正确的方法 ⚫ 推理定律 自然推理系统P ⚫ 形式系统的定义与分类 ⚫ 自然推理系统P ⚫ 在P中构造证明:直接证明法、附加前提证明法、归谬法

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

3 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 Pqp^(P→>q)qp^(q→p) FF FT F TF T F F TTT TT T

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

3.1推理形式结构 豪 口定理:{A,A}卡B当且仅当 A∧…A→>B为重言式 证明必要性:任意vv(A)=T则vB)=T 所以v(A…,∧A→B)=T 充分性:任意vV(AAA→B)=T 如果v(A)=T则v(B)=T 5

5 ❑定理：{A1,…,Ak} ⊨ B 当且仅当 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 推理形式结构

3.1推理形式结构 豪 口蕴涵元符号:→ A∧.A→B代表{A,A}B 口推理形式结构 令前提A,Ak ◆结论:B 6

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

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

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

推理实例 豪 例1判断下面推理是否正确 (1)若今天是1号,则明天是5号今天是1号所以,明天是5号 (2)若今天是1号,则明天是5号明天是5号所以,今天是1号 解设p:今天是1号,q:明天是5号 (1)推理的形式结构:(p→q)入P→一 用等值演算法 (→q)P-入q 分-(yVq)p)q 分平VqVq<1 由定理31可知推理正确

8 8 推理实例 例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可知推理正确

推理实例 豪 (2)推理的形式结构:(p→q)∧4→ 用主析取范式法 (P→>q)入q-少p 分(-pVq)^q→少D 分-(yVq)入q)P 分(-∧-qV入q(P-q)V(∧q 台 movvm3 结果不含m,故01是成假赋值,所以推理不正确 9

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

3.1推理形式结构 豪 口推理定律 A→(AvB) 附加律 (A∧B)→A 化简律 (A→B)∧A→B 假言推理 (A→B)∧-B→-A 拒取式 AvB)∧B→A 析取三段论 (A→B)∧(B→C)→(A→C) 假言三段论 (A4B)∧(BC→(Ac) 等价三段论 (A→B(C→D)∧AvC→(BD) 构造性二难 (A→B∧(A→B)→B 构造性二难(特殊形式) (A→B(C→D∧(BV-D)→(Ay-C破坏性二难 10

10 ❑推理定律 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 推理形式结构