离散数学 命题逻辑的推理理论.ppt

1 1 6命题逻辑的推理理论 推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明法 2 推理的形式结构 问题的引入 推理 从前提出发推出结论的思维过程前提是指已知的命题公式 结论是推出的命题公式例如果天气凉快 小王就不去游泳 天气凉快 所以小王没有去游泳 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 4 判断推理是否正确的方法 真值表法等值演算法主析取范式法构造证明法说明 当命题变项比较少时 用前3个方法比较方便 此时采用形式结构 A1 A2 Ak B 当命题变项比较多时 用构造证明法 采用 前提 A1 A2 Ak 结论 B 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得证推理正确 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是成假赋值 所以推理不正确 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 构造性二难 8 推理定律 续 A B A B A A B构造性二难 特殊形式 A B C D B D A C 破坏性二难 说明 若某推理符合某条推理定律 则它自然是正确的A B产生两条推理定律 A B B A 9 推理规则 10 推理规则 续 11 构造证明 直接证明法 例构造下面推理的证明 若明天是星期一或星期三 我就有课 若有课 今天必备课 我今天下午没备课 所以 明天不是星期一和星期三 解设p 明天是星期一 q 明天是星期三 r 我有课 s 我备课形式结构为前提 p q r r s s结论 p q 12 直接证明法 续 证明 r s前提引入 s前提引入 r 拒取式 p q r前提引入 p q 拒取式 p q 置换 13 构造证明 附加前提证明法 欲证明前提 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 14 附加前提证明法 续 例构造下面推理的证明 2是素数或合数 若2是素数 则是无理数 若是无理数 则4不是素数 所以 如果4是素数 则2是合数 用附加前提证明法构造证明解设p 2是素数 q 2是合数 r 是无理数 s 4是素数形式结构前提 p q p r r s结论 s q 15 附加前提证明法 续 证明 s附加前提引入 p r前提引入 r s前提引入 p s 假言三段论 p 拒取式 p q前提引入 q 析取三段论请用直接证明法证明之 16 构造证明 归谬法 反证法 欲证明前提 A1 A2 Ak结论 B将 B加入前提 若推出矛盾 则得证推理正确 理由 A1 A2 Ak B A1 A2 Ak B A1 A2 Ak B 括号内部为矛盾式当且仅当 A1 A2 Ak B 为重言式 17 归谬法 续 例构造下面推理的证明前提 p q r r s s p结论 q证明 用归缪法 q结论否定引入 r s前提引入 s前提引入 r 拒取式 18 归谬法 续 p q r前提引入 p q 析取三段论 p q 置换 p 析取三段论 p前提引入 p p 合取请用直接证明法证明之