《离散数学》课程PPT教学课件（讲稿）第1章 命题逻辑（1.6）命题逻辑的推理理论

16命题逻辑的推理理论 推理的形式结构 判断推理是否正确的方法 推理定律与推理规则 构造证明法

1 1.6 命题逻辑的推理理论 ▪ 推理的形式结构 ▪ 判断推理是否正确的方法 ▪ 推理定律与推理规则 ▪ 构造证明法

推理的形式结构一问题的引入 推理举例: (1)正项级数收敛当且仅当部分和上有界 (2)若 AUCCB∪D,则B且CcD 推理:从前提出发推出结论的思维过程 上面(1)是正确的推理,而(2)是错误的推理 证明:描述推理正确或错误的过程

2 推理的形式结构—问题的引入 推理举例: (1) 正项级数收敛当且仅当部分和上有界. (2) 若ACBD，则AB且CD. 推理: 从前提出发推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理. 证明: 描述推理正确或错误的过程

推理的形式结构 定义若对于每组赋值,A1A2…入Ak均为假,或 当A1∧42^∧4为真时,B也为真,则称由A1,42,,Ak 推B的推理正确,否则推理不正确(错误) “A41,A2,…,4k推B”的推理正确 当且仅当A142^,,∧Ak-B为重言式 推理的形式结构:A142A…^4k→>B或 前提 1542 k 结论:B 若推理正确,则记作:A1A2,,4→B

3 推理的形式结构 定义 若对于每组赋值，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

判断推理是否正确的方法 °真值表法 等值演算法 °主析取范式法 构造证明法 说明:当命题变项比较少时,用前3个方法比较方 便,此时采用形式结构“A1∧42^4k→>B”.而在 构 造证明时,采用“前提:A1A2…,A,结论:B

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

实例 例判断下面推理是否正确 (1)若今天是1号,则明天是5号今天是1号所 以明天是5号 解设p:今天是1号,q:明天是5号 证明的形式结构为:(→q)>q 证明(用等值演算法) (P→>q)P→q 分>-(yVq))Vq 1vq分1 得证推理正确

5 实例 例 判断下面推理是否正确 (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号,则明天是5号.明天是5号所以今天是1号 解设p:今天是1号,q:明天是5号 证明的形式结构为:(→>q)∧→>p 证明(用主析取范式法) (P→q)∧q→p 分(ypVq)∧q→>P →-(yVq)qvp 分(一∧-q)VD入一q(DA-q)V{D入q) 8 movm2vm3 结果不含m1故01是成假赋值,所以推理不正确

6 实例 (续) (2) 若今天是1号，则明天是5号.明天是5号.所以今天是1号. 解 设p：今天是1号，q：明天是5号. 证明的形式结构为: (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是成假赋值，所以推理不正确

推理定律—重言蕴涵式 重要的推理定律 A→(AvB) 附加律 (4∧B)→A 化简律 (4->B)4→B 假言推理 (4→B)∧-B→-4 拒取式 (4ⅤB)入-B→A 析取三段论 (4→>B)∧(B→>C)→(4->C) 假言三段论 (4B)(B>C→(4)C 等价三段论 (A→>B)∧(C→>D)N(4O)→(BND)构造性二难

7 推理定律——重言蕴涵式 重要的推理定律 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) 构造性二难

推理定律(续) (4→>B)∧(-4→>B)入(4v4)→B 构造性二难(特殊形式) (4->B)∧C>D)∧(-ByD)→(4vC) 破坏性二难 说明: A,B,C为元语言符号 若某推理符合某条推理定律,则它自然是正确的 A<→B产生两条推理定律:A→B,B→A

8 推理定律 (续) (A→B)(A→B)(AA)  B 构造性二难（特殊形式） (A→B)(C→D)( BD)  (AC) 破坏性二难 说明： A, B, C为元语言符号 若某推理符合某条推理定律，则它自然是正确的 AB产生两条推理定律: A  B, B  A

推理规则 (1)前提引入规则 (6)化简规则 (2)结论引入规则 A入B (3)置换规则 (4)假言推理规则 (7)拒取式规则 A→>B A→B -B B (8)假言三段论规则 (5)附加规则 A→)B B→)C AVB ∴A→C

9 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 A→B A \ B (5) 附加规则 A \AB (6) 化简规则 AB \A (7) 拒取式规则 A→B B \A (8) 假言三段论规则 A→B B→C \A→C

推理规则(续) (9)析取三段论规则(1)破坏性二难推理 AvB 规则 -B A→>B C→>D (10)构造性二难推理 -By-D 规则 ,4v-C A→B (12)合取引入规则 C→>D Avc B BVD A入B 10

10 推理规则(续) (11) 破坏性二难推理 规则 A→B C→D BD \AC (12) 合取引入规则 A B \AB (9) 析取三段论规则 AB B \A (10)构造性二难推理 规则 A→B C→D AC \BD