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

第三章命题逻辑推理理论 1

1 第三章 命题逻辑推理理论

命题逻辑的推理理论 ■推理的形式结构 ■自然推理系统P 2

2 命题逻辑的推理理论  推理的形式结构  自然推理系统P

§3.1推理的形式结构一问题的引入 推理举例： ()下午马芳或去看电影或去游泳。她没去看电影。 所以，她去游泳了。 (2)若下午气温超过30℃，则小王必去游泳。若她 去游泳，她就不去看电影了。所以，若小王没去 看电影，下午气温必超过30℃ 推理：从前提出发推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理。 证明：描述推理正确或错误的过程， 3

3 §3.1推理的形式结构—问题的引入 推理举例: (1)下午马芳或去看电影或去游泳。她没去看电影。 所以,她去游泳了。 (2) 若下午气温超过30℃，则小王必去游泳。若她 去游泳，她就不去看电影了。所以，若小王没去 看电影，下午气温必超过30℃ 推理: 从前提出发推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理. 证明: 描述推理正确或错误的过程

推理的形式结构 定义若对于每组赋值，A142人.ΛAk均为假，或 当A1A2A.AA为真时，B也为真，则称由A1,A2,A 推B的推理正确，否则推理不正确（错误）. “A1,A2,Ak推B”的推理正确 当且仅当A1M2人Ak→B为重言式 推理的形式结构：A1A2人Ak→B或 前提：A1,A2.,Ak 结论：B 若推理正确，则记作：A1A2Λ.入A→B. 4

4 推理的形式结构 定义 若对于每组赋值，A1A2. Ak 均为假，或 当A1A2.Ak为真时, B也为真, 则称由A1 ,A2 ,., Ak 推B的推理正确 , 否则推理不正确（错误）. “A1 , A2 , ., Ak 推B” 的推理正确 当且仅当 A1A2.AkB为重言式. 推理的形式结构: A1A2.AkB 或 前提： A1 , A2 , . , Ak 结论： B 若推理正确，则记作：A1A2.AkB

推理的形式结构（续） 几点说明： 1.将有限公式集合A,A,.,A记为T,则 有限公式集合T推B的推理，记为T一B. 若TB是正确的，记为T=B, 否则记为厂≠B. 2.推理正确并不能保证结论B一定为真，这与数 学中的推理是不同的 5

5 有限公式集合推B的推理 ,记为 B. 若 B是正确的,记为 B , 否则记为 B. 几点说明： 1. 将有限公式集合A1 , A2 , . , Ak记为,则 2. 推理正确并不能保证结论B一定为真,这与数 学中的推理是不同的. 推理的形式结构 (续)

判断推理是否正确的方法 ·真值表法 ·等值演算法 ·主析取范式法 ·构造证明法 说明：当命题变项比较少时，用前3个方法比较方 便，此时采用形式结构“A1A2入4→B”.而在 构 造证明时，采用“前提：A1,A2,.,Ak结论：B” 6

6 判断推理是否正确的方法 • 真值表法 • 等值演算法 • 主析取范式法 • 构造证明法 说明：当命题变项比较少时，用前3个方法比较方 便, 此时采用形式结构“ A1A2.AkB” . 而在 构 造证明时，采用“前提: A1 , A2 , . , Ak , 结论: B

实例 例判断下列推理是否正确： (1) {p,p-→q}-q (2){ D,q→p}-q

7 实例 例 判断下列推理是否正确: (1) {p , pq} q (2) {p ,qp } q

实例 例判断下面推理是否正确 ()若今天是1号，则明天是5号.今天是1号.所 以明天是5号 解设p:今天是1号，q:明天是5号. 证明的形式结构为：(p-→q)p→9 证明（用等值演算法） (p→q)p→q 台(-pVq)pVq 台VVg台1 得证推理正确

8 实例 例 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所 以明天是5号. 解 设 p：今天是1号，q：明天是5号. 证明的形式结构为: (pq)pq 证明（用等值演算法） (pq)pq  ((pq)p)q  pqq  1 得证推理正确

实例（续） (2)若今天是1号，则明天是2号.明天是2号.所以今天是1号 解设p:今天是1号，4：明天是2号 证明的形式结构为：p→q)人q-→P 证明（用主析取范式法） (p→q0Λq→P 台(-pVq)Nq→P 台(pVq)AqP 台IVp 台（一pAq)VPA一qV(PAqV(PAq) 台m,Vm2Vm 结果不含m,故不是重言式，所以推理不正确

9 实例 (续) (2) 若今天是1号，则明天是2号. 明天是2号. 所以今天是1号. 解 设p：今天是1号，q：明天是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, 故不是重言式，所以推理不正确

推理定律— 重言蕴涵式 重要的推理定律 A→(AVB) 附加律 (AB)→A 化简律 (A→B)A→B 假言推理 (A→B)AB→A 拒取式 (AVB)AB→A 析取三段论 (A→B)A(B-→C)→(A-→C) 假言三段论 (A>B)Λ(B→C)→(AK>C) 等价三段论 (A→B)A(C→D)AAVC)→(BVD) 构造性二难 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) 构造性二难