离散数学 清华大学出版社1.6

离散数学 全面教程3

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

构造证明法

离散数学 全面教程3

推理的形式结构—问题的引入推理: 从前提出发推出结论的思维过程前提是指已知的命题公式，结论是推出的命题公式

例

如果天气凉快,小王就不去游泳. 天气凉快,所以小王 没有去游泳. p:天气凉快，q:小王去游泳 前提： (p q) p 结论： q

问题：如何判断推理是否正确？

离散数学 全面教程3

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

离散数学 全面教程3

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

离散数学 全面教程3

实例例 判断下面推理是否正确 (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 得证推理正确5

离散数学 全面教程3

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

离散数学 全面教程3

推理定律——重言蕴涵式重要的推理定律 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) 附加律 化简律 假言推理 拒取式 析取三段论 假言三段论 等价三段论 构造性二难7

离散数学 全面教程3

推理定律 (续)(A B) ( A B) (A A) B 构造性二难(特殊形式) (A B) (C D) ( B D) ( A C) 破坏性二难说明： 若某推理符合某条推理定律，则它自然是正确的 A B产生两条推理定律: A B, B A8

离散数学 全面教程3

推理规则(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

离散数学 全面教程3

推理规

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

离散数学 全面教程3

构造证明——直接证明法例 构造下面推理的证明： 若明天是星期一或星期三，我就有课. 若有课， 今天必备课. 我今天没备课. 所以， 明天不是星期一和星期三. 解 设 p:明天是星期一，q:明天是星期三， r:我有课，s:我备课 形式结构为 前提：(p q) r, r s, s 结论： p q11

离散数学 全面教程3

直接证明法 (续)证明 ① r s ② s ③ r ④ (p q) r ⑤ (p q) ⑥ p q前提引入 前提引入 ①②拒取式 前提引入 ③④拒取式 ⑤置换

离散数学 全面教程3

构造证明——附加前提证明法欲证明 前提：A1, A2, …, Ak 结论：C B 等价地证明 前提：A1, A2, …, Ak, C 结论：B 理由： (A1 A2 … Ak) (C B) ( A1 A2 … Ak) ( C B) ( A1 A2 … Ak C) B (A1 A2 … Ak C) B

离散数学 全面教程3

附加前提证明法 (续)例 构造下面推理的证明: 2是素数或合数. 若2是素数，则 2是无理数. 若 2是无理数，则4不是素数. 所以，如果4是 素数，则2是合数. 用附加前提证明法构造证明 解 设 p:2是素数，q:2是合数， r: 2 是无理数，s:4是素数 2 形式结构 前提：p q, p r, r s 结论：s q14

离散数学 全面教程3

附加前提证明法 (续)证明 ①s 附加前提引入 ② p r 前提引入 ③ r s 前提引入 ④ p s ②③假言三段论 ⑤ p ①④拒取式 ⑥ p q 前提引入 ⑦q ⑤⑥析取三段论 请用直接证明法证明之15

离散数学 全面教程3

构造证明——归谬法(反证法)欲证明 前提：A1, A2, … , Ak 结论：B 将 B加入前提，若推出矛盾，则得证推理正确. 理由: A1 A2 … Ak B (A1 A2 … Ak) B (A1 A2 … Ak B) 括号内部为矛盾式当且仅当 (A1 A2 … Ak B)为 重言式16