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

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

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

豪 口第一节:推理的形式结构 2

2 第一节：推理的形式结构

3.1推理形式结构 豪 口何为推理?何为证明? 例子: (1)若AcB且CD,则 AUCCBu∪D (2)若今天是星期一,则明天是星期二 (3)若AC∈B∪D,则AcB且CD 口推理—一从前提出发推出结论的思维过程 上例中,(1),(2)是正确的推理,而 (3)是错误的推理 口证明—描述推理正确或错误的过程

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

4 3.1 推理形式结构 ❑逻辑(语义)蕴涵：给定A1,…,Ak和B ❖对任意赋值v: • 如果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 Pqp^(P→>q)qp^(q→p) FF FT F TF T F F TTT TT T 5

5 ❑ 例子 ❖ {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为重言式 证明必要性:任意v不会出现A∧A为真且 B为假的情况,所以v(A…A→B)=T 充分性:任意vV(A^/A→B)=T 则或者:A∧.A和B同时为T 或者:A∧A为假 所以{A,A}B 6

6 ❑定理：{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 推理形式结构

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

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

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

8 ❑ 判断推理是否正确方法 ① 真值表法 ② 等值演算法 ③ 主析取范式法 3.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可知推理正确

9 9 推理实例 例 判断下面推理是否正确 (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是成假赋值,所以推理不正确 10 10

10 10 推理实例 (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是成假赋值，所以推理不正确