定理的前提.ppt

* * * * * * * * 平凡证明 定理的特殊情形 结论已为真，蕴涵式自动为真?无需前提为真 例6 已知命题函数P(n)：若a, b 整数且 a≥b, 则an≥bn 求证：命题P(0)为真 a0=1≥1=b0 归谬法(反证法) 要求证明 p 为真 假设 ?p 为真 在上述假设下，若能推导出命题：?r ? r 说明：从 ?p 为真出发，一定会推出矛盾结果 故，p为真 矛盾式 例 9, 10, 11 等价性证明 定理本身是个双蕴涵式 前提与结论构成 2 个方向相反的蕴涵 定理本身是个双蕴涵链 前提与结论构成由多个蕴涵组成的 1 个圈 例 12 例 13 1.6.8 证明中的错误 例 15~18 证明过程中的某次推理不正确 肯定结论 否定前提 分情形证明时，情况分析不完整 循环论证 1.7 证明方法：分情形证明法 推理规则 (p1?p2?…?pn)?q 前提不一定都为真 等价于 (p1?q)?(p2?q)?…?(pn?q) 每个子前提与结论构成一种情形 “穷举”证明：枚举所有可能情况 例 1, 2 1.7 证明方法：分情形证明法 分情形证明 注意：一定要覆盖所有可能情况 例 3, 4 证明中利用分情形 例 5, 6 不失一般性 例 7 分情形证明的常见错误 例 9 1.7 证明方法 定理中包含量词 存在性证明：?x P(x) 构造性：找到一个 a，使 P(a) 为真 例 10 非构造性：反证 例 11 1.7 证明方法 定理中包含量词 唯一性证明：存在性＋唯一性 例 13 1.7 证明策略 如何构造证明？ 正确使用证明方法 如何发现证明？ 正确选择证明方法 1.7 证明策略 证明方法的选择思路 准确掌握命题含义 用定义替换术语 仔细分析假设、结论的含义 尝试不同证明方法 前推/回溯、修改、反例 etc. 1.7 证明策略 前推 直接由前提(公理、定理)推导出结论，P1, P2, ….,Pn?Q 回溯/后推 由结论出发寻找命题R(满足R?Q或R?Q)，再证明P1,P2,….,Pn?R 修改 利用已有证明的过程或思想，进行修改适应目前的前提 回溯/后推 例14：算术平均大于几何平均 (x-y)20 成立吗？ 例15：二人的“零和”博弈 后推 修改 证明　是无理数(例16) 若是有理数，则有 3d2=c2，c、d是互质的整数 3是c2的因子，则3是c的因子，令c=3k 为什么？ 3d2=9k2，d2=3k2，3是d2的因子 3是d2的因子，则3是d的因子 则3是c、d的公因子，与前面的互质要求矛盾！ 反例 反例和前推：在寻找证明的过程中，提供规律和信心的手段 例 17 证明小结 证明方法：使用推理规则的技巧 直接证明法：正向推导(从前提到结论) 间接证明法：反向推导(由结论分析前提) 空证明/平凡证明：解决特殊情况 反证法：先否定结论，再看是否矛盾 等价性、存在性、唯一性：特定的定理类型 综合实例－填充问题 术语：标准棋盘、镶板、骨牌 例 18：直接证明 例 19：反证 例 20、22：方格颜色—填充状态 补充 右三格板能否填充去掉一个角的标准棋盘？ 作业 3 P45 5. 14. 15. * * * * * * * * * * * * * * * 第1章 基础：逻辑和证明 1.5 推理规则 1.6 证明导论 1.7 证明策略 证明 论证(argument)/证明(proof)：一个命题序列 最后一个命题：结论 其它命题：前提 论证是有效的 若所有前提为真，则结论必真 若所有前提为真，结论却为假，这是不可能的！！ ∵如果你有正确密码，则你可登录网络 ∵你有正确密码 ∴你可登录网络 证明 1.5.2 有效(valid)论证 论证对应的形式结构永真 论证的形式结构：联接前提和结论的蕴涵式 一般的，某个论证有效是指其论证形式 (p1?p2?…?pn)?q 永真 ∵p?q ∵p ∴q ((p?q)?p)?q 1.5 推理规则 推理规则 (典型)有效论证的形式模板 命题逻辑的推理规则(表1-25) 格式：纵向书写 只要满足规则要求：前提都为真，结论就一定正确 用法：符号替换 用实际命题替换规则中的符号 1.5 推理规则 假言推理(分离规则) ∵若今天下雪，则去滑雪 今天下雪 ∴去滑雪 p?q p ∴q 肯定前提 例 1, 2 1.5 推理规则 取拒式规则 ∵若今天下雪，则去滑雪 没去滑雪 ∴今天没下雪 p?q ?q ∴?p 否定结论 1.5 推理规则 假言三段论规则 ∵若今天下雨，则今天不野餐 若今天不野餐，则明天野餐