推理的形式结构课件.ppt

第 三 章 命 题 逻 辑 的 推 理 理 论 数 理 逻 辑 的 主 要 任 务 是 推 理 ， 即 提 供 一 套 推 理规 则 ， 从 给 定 的 前 提 出 发 ， 推 导 出 一 个 结 论 来 。 前 提 是 指 已 知 的 公 式 的 集 合 。 结 论 是 对 前 提 应 用 推 理 规 则 推 出 的 公 式 。 3.1 推 理 的 形 式 结 构 定 义 （ 推 理 的 形 式 结 构 ） 设 A 1 ， A 2 ， ， A k ， B 都 是 命 题 公 式 ， 若 （ A1 A2 Ak） B为 重 言 式 ， 则 称 由 前 提 A1， A2， ， Ak推 出 B的 推 理 是 有 效 的 或 正 确 的 ， 称 B是 A1，A2， ， Ak的 有 效 结 论 或 正 确 结 论 。 称 （ A1 A2 Ak） B为 由 前 提 A1， A2， ， Ak推出 结 论 B的 推 理 的 形 式 结 构 。 说 明 ： （ 1） 用 （ A1 A2 Ak） B来 表 示 A1， A2， ， Ak推 出 B的 推 理 是 有 效 的 ， 即 （ A 1 A2 Ak） B为 重 言 式 。 （ 2） 判 断 推 理 是 否 正 确 的 方 法 就 是 判 断 重 言 蕴 涵 式 的 方 法 ： 真 值 表 法 ， 等 值 演 算 法 ， 主 析 取 范 式 法 例 ： 判 断 下 面 各 推 理 是 否 正 确 。 （ 1） 马 芳 或 去 看 电 影 或 去 游 泳 。 她 没 去 看 电 影 。 所 以她 去 游 泳 了 。 （ 2） 若 下 午 气 温 超 过 30度 ， 则 王 燕 必 去 游 泳 。 若 她 去游 泳 ， 她 就 不 去 看 电 影 了 。 所 以 ， 若 王 燕 没 去 看 电 影 ， 下午 气 温 必 超 过 30度 。解 推 理 问 题 的 步 骤 ：（ 1） 将 简 单 命 题 符 号 化（ 2） 以 下 述 形 式 写 出 前 提 、 结 论 和 推 理 的 形 式 结 构 前 提 ： A 1， A2， ， Ak 结 论 ： B 推 理 的 形 式 结 构 ： （ A1 A2 Ak） B（ 3） 进 行 判 断 (真 值 表 法 ， 等 值 演 算 法 ， 主 析 取 范 式 法 ) （ 1） 马 芳 或 去 看 电 影 或 去 游 泳 。 她 没 去 看 电 影 。所 以 她 去 游 泳 了 。 解 ： 设 ： p： 马 芳 去 看 电 影 ， q： 马 芳 去 游 泳 前 提 ： p q， p 结 论 ： q 推 理 的 形 式 结 构 ： （ （ p q） p） ） q 判 断 方 法 一 ： 真 值 表 法 真 值 表 的 最 后 一 列 全 为 1， 所 以 （ （ p q） p） q为 重 言 式 。 因 而 推 理 正 确 。 判 断 方 法 二 ： 等 值 演 算 法 （ （ p q） p） q （ （ p p） （ q p） ） q （ q p ） q q p q 1 因 为 （ （ p q） p） q为 重 言 式 ， 所以 推 理 正 确 。 判 断 方 法 三 ： 主 析 取 范 式 法 （ （ p q） p） q m0 m1 m2 m3 所 以 （ （ p q） p） q为 重 言 式 ， 推 理 正 确 。 （ 2） 若 下 午 气 温 超 过 30度 ， 则 王 燕 必 去 游 泳 。 若她 去 游 泳 ， 她 就 不 去 看 电 影 了 。 所 以 ， 若 王 燕 没 去 看电 影 ， 下 午 气 温 必 超 过 30度 。 解 ： 设 p： 下 午 气 温 超 过 30度 ； q： 王 燕 去 游 泳 ； r： 王 燕 去 看 电 影 前 提 ： pq， qr 结 论 ： rp 推 理 的 形 式 结 构 ： （ pq） （ qr） （ rp） （ *） m1 m3 m4 m5 m6 m7可 见 （ *） 不 是 重 言 式 ， 所 以 推 理 不 正 确 。 如 果 AB成 立 ， 则 推 理 AB是 正 确 的 ； 同 时 推 理 BA也 是 正 确 的 。思 考 ： AB和 AB的 关 系 ？ 推 理 定 律 （ 重 言 蕴 涵 式 ）（ 1） A A B 附 加 律（ 2） A B A 化 简 律（ 3） （ A B） A B 假 言 推 理（ 4） （ A B） B A 拒 取 式（ 5） （ A B） B A 析 取 三 段 论（ 6） （ A B） （ B C） （ A C） 假 言 三 段 论（ 7） （ AB） （ BC） （ AC） 等 价 三 段 论 （ 8） （ A B） （ C D） （ A C） （ B D） 构 造 性 二 难（ 9） （ A B） （ C D） （ B D） （ A C） 破 坏 性 二 难 说 明 ： 第 2.1节 等 值 式 中 给 出 的 24个 等 值 式 ， 每 个 等 值 式 可 以 派 生 出 两 条 推 理 定 律 。例 如 ： A B A B产 生 两 条 推 理 定 律 A B A B和 A B A B 在 解 推 理 问 题 的 过 程 中 ， 如 果 命 题 变 项 较 多 ，则 采 用 真 值 表 法 ， 等 值 演 算 法 ， 主 析 取 范 式 法 这 三 种方 法 来 判 断 推 理 的 形 式 结 构 的 公 式 类 型 都 不 方 便 。 解 推 理 问 题 的 构 造 证 明 法 。 构 造 证 明 是 一 个 描 述 推 理 过 程 的 命 题 公 式 的 序 列 ，其 中 每 个 公 式 或 者 是 已 知 前 提 ， 或 者 是 由 某 些 前 提 应用 推 理 规 则 得 到 的 结 论 。 构 造 证 明 法 的 证 明 形 式 前 提 ： p q， q r， p s， s 结 论 ： r （ p q） 证 明 ： p s 前 提 引 入 s 前 提 引 入 p 拒 取 式 p q 前 提 引 入 q 析 取 三 段 论 q r 前 提 引 入 r 假 言 推 理 r （ p q） 合 取 引 入 3.2 自 然 推 理 系 统 P 定 义 （ 自 然 推 理 系 统 P）自 然 推 理 系 统 P由 以 下 三 个 部 分 组 成 ：1、 字 母 表 （ 1） 命 题 变 项 符 号 ： p， q， r， ， pi， qi， ri， （ 2） 联 结 词 符 号 ： ， ， ， ， （ 3） 括 号 与 逗 号 ： （ ） ，2、 公 式 参 见 命 题 公 式 的 定 义 3、 推 理 规 则 （ 12个 ） （ 1） 前 提 引 入 规 则 ： 在 证 明 的 任 何 步 骤 上 都 可以 引 入 前 提 。 （ 2） （ 中 间 ） 结 论 引 入 规 则 ： 在 证 明 的 任 何 步 骤上 所 得 到 的 中 间 结 论 都 可 以 作 为 后 继 证 明 的 前 提 。（ 这 是 12个 推 理 规 则 中 唯 一 的 一 个 隐 规 则 。 ） （ 3） 置 换 规 则 ： 在 证 明 的 任 何 步 骤 上 ， 命 题 公 式中 的 子 公 式 都 可 以 用 与 之 等 值 的 公 式 置 换 ， 得 到 公 式序 列 中 的 又 一 个 公 式 。 由 九 条 推 理 定 律 和 结 论 引 入 规 则 可 以 导 出 以 下各 条 推 理 定 律 。 （ 4） 假 言 推 理 规 则 （ 分 离 推 理 规 则 ） ： 若 证 明 的公 式 序 列 中 出 现 过 A B和 A， 则 由 假 言 推 理 定 律（ A B） AB可 知 ， B是 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） 析 取 三 段 论 规 则 ： （ A B） BA （ 10） 构 造 性 二 难 推 理 规 则 ： （ A B） （ C D） （ A C） （ B D） （ 11） 破 坏 性 二 难 推 理 规 则 ： （ A B） （ C D） （ B D） （ A C） （ 12） 合 取 引 入 规 则 ： 若 证 明 的 公 式 序 列 中 出 现 过A和 B， 则 A B是 A和 B的 有 效 结 论 。 推 理 规 则 （ 12个 ）（ 1） 前 提 引 入 规 则（ 2） 结 论 引 入 规 则 （ 隐 规 则 ）（ 3） 置 换 规 则 ： 等 值 置 换（ 4） 假 言 推 理 规 则 ： （ AB） AB（ 5） 附 加 规 则 ： A（ A B）（ 6） 化 简 规 则 ： A B A（ 7） 拒 取 式 规 则 ： （ AB） BA（ 8） 假 言 三 段 论 规 则 ： （ AB） （ BC） （ AC）（ 9） 析 取 三 段 论 规 则 ： （ A B） BA（ 10） 构 造 性 二 难 推 理 规 则（ 11） 破 坏 性 二 难 推 理 规 则（ 12） 合 取 引 入 规 则 利 用 构 造 证 明 来 证 明 形 式 结 构 为（ A1 A2 Ak） B的 推 理 时 首 先 写 出 ： 前 提 ： A1， A2， ， Ak 结 论 ： B 证 明 ： 注 意 ： 不 用 写 出 推 理 的形 式 结 构 ： （ A1 A2 Ak） B 例 在 自 然 推 理 系 统 P中 构 造 下 面 推 理 的 证 明 ：（ 1） 前 提 ： p q， q r， p s， s 结 论 ： r （ p q） 证 明 ： p s 前 提 引 入 s 前 提 引 入 p 拒 取 式 （ A B） B A p q 前 提 引 入 q 析 取 三 段 论 （ A B） BA q r 前 提 引 入 r 假 言 推 理 （ A B） AB r （ p q） 合 取 引 入 （ 2） 前 提 ： p q， r q， r s 结 论 ： p s 证 明 ： p q 前 提 引 入 p q 置 换 r q 前 提 引 入 q r 置 换 p r 假 言 三 段 论 r s 前 提 引 入 p s 假 言 三 段 论 规 则 例 在 自 然 推 理 系 统 P中 构 造 下 面 的 推 理 的 证 明 ： 若 数 a是 实 数 ， 则 它 不 是 无 理 数 就 是 有 理 数 。 若 a不能 表 示 成 分 数 ， 则 它 不 是 有 理 数 。 a是 实 数 且 它 不 能 表 示成 分 数 。 所 以 a是 无 理 数 。解 ： 首 先 将 简 单 命 题 符 号 化 ： 令 p： a是 实 数 ； q： a是 有 理 数 ； r： a是 无 理 数 ； s： a能 表 示 成 分 数 解 题 步 骤 ： （ 1） 简 单 命 题 的 符 号 化 （ 2） 写 出 前 提 和 结 论 （ 3） 证 明前 提 ： p （ q r） ， s q， p s结 论 ： r 证 明 ： p s 前 提 引 入 p 化 简 （ A B） A s 化 简 s q 前 提 引 入 q 假 言 推 理 （ A B） AB p （ q r） 前 提 引 入 q r 假 言 推 理 r 析 取 三 段 论 （ A B） BA前 提 ： p （ q r） ， s q， p s结 论 ： r 使 用 构 造 证 明 法 进 行 推 理 时 的 证 明 技 巧 （ 1） 附 加 前 提 证 明 法 有 时 要 证 明 的 结 论 以 蕴 涵 式 的 形 式 出 现 ， 即 推 理的 形 式 结 构 为 （ A1 A2 Ak） （ A B） 对 该 式 进 行 等 值 演 算 ： （ A1 A2 Ak） （ A B） （ A1 A2 Ak） （ A B） （ （ A1 A2 Ak） A） B （ A 1 A2 Ak A） B （ A1 A2 Ak A） B 可 见 ， 如 果 能 证 明 是 重 言 式 ， 则 也 是 重 言 式 。在 中 ， 原 来 的 结 论 中 的 前 件 A已 经 变 成 前 提 了 ， 称 A为附 加 前 提 。 称 这 种 将 结 论 中 的 前 件 作 为 前 提 的 证 明 方 法 为附 加 前 提 法 。 例 ： 在 自 然 推 理 系 统 P中 构 造 下 面 推 理 的 证 明 如 果 小 张 和 小 王 去 看 电 影 ， 则 小 李 也 去 看 电 影 。 小赵 不 去 看 电 影 或 小 张 去 看 电 影 。 小 王 去 看 电 影 。 所 以 ，当 小 赵 去 看 电 影 时 ， 小 李 也 去 。解 ： 将 简 单 命 题 符 号 化 令 p： 小 张 去 看 电 影 ； q： 小 王 去 看 电 影 ； r： 小 李 去 看 电 影 ； s： 小 赵 去 看 电 影前 提 ： （ p q） r， s p， q结 论 ： s r前 提 ： （ p q） r， s p， q， s结 论 ： r 证 明 ： s 附 加 前 提 引 入 s p 前 提 引 入 p 析 取 三 段 论 （ A B） BA q 前 提 引 入 p q 合 取 引 入 （ p q） r 前 提 引 入 r 假 言 推 理 （ A B） AB 前 提 ： （ p q） r， s p， q， s 结 论 ： r证 明 方 法 一 ： 附 加 前 提 法前 提 ： （ p q） r， s p， q结 论 ： s r 证 明 方 法 二 ： 直 接 证 明 前 提 ： （ p q） r， s p， q 结 论 ： s r证 明 ： s p 前 提 引 入 s p 置 换 （ p q） r 前 提 引 入 p r 化 简 s r 假 言 三 段 论 证 明 ： s p 前 提 引 入 s p 置 换 （ p q） r 前 提 引 入 p q r 置 换 q 前 提 引 入 p r 析 取 三 段 论 p r 置 换 s r 假 言 三 段 论证 明 方 法 二 ： 直 接 证 明 前 提 ： （ p q） r， s p， q 结 论 ： s r （ 2） 归 谬 法 在 构 造 形 式 结 构 为 （ A1 A2 Ak） B的 推 理 证 明 中 ， 若 将 B作 为 前 提 能 推 出 形 如（ A A） 的 矛 盾 来 ， 则 说 明 推 理 正 确 ， 这 种方 法 称 为 归 谬 法 。 例 ： 在 自 然 推 理 系 统 P中 构 造 下 面 推 理 的 证 明 如 果 小 张 守 第 一 垒 并 且 小 李 向 B队 投 球 ， 则 A队 将 取胜 。 或 者 A队 未 取 胜 ， 或 者 A队 成 为 联 赛 第 一 名 。 A对 没 有成 为 联 赛 的 第 一 名 。 小 张 守 第 一 垒 。 因 此 ， 小 李 没 向 B队投 球 。解 ： 将 简 单 命 题 符 号 化 ： 令 p： 小 张 守 第 一 垒 ； q： 小 李 向 B队 投 球 ； r： A队 取 胜 ； s： A队 成 为 联 赛 第 一 名 前 提 ： （ p q） r， r s， s， p 结 论 ： q前 提 ： （ p q） r， r s， s， p， q结 论 ： 0 证 明 ： q 结 论 的 否 定 引 入 p 前 提 引 入 p q 合 取 （ p q） r 前 提 引 入 r 假 言 推 理 r s 前 提 引 入 s 前 提 引 入 r 析 取 三 段 论 r r 合 取前 提 ： （ p q） r， r s， s， p， q结 论 ： 0前 提 ： （ p q） r， r s， s， p结 论 ： q 证 明 ： r s 前 提 引 入 s 前 提 引 入 r 析 取 三 段 论 （ p q） r 前 提 引 入 p q 拒 取 式 p 前 提 引 入 q 析 取 三 段 论前 提 ： （ p q） r， r s， s， p结 论 ： q 思 考 题 尝 试 在 自 然 推 理 系 统 P中 利 用 构 造 证 明 法 证 明著 名 的 “ 苏 格 拉 底 三 段 论 ” 的 正 确 性 。 苏 格 拉 底 三 段 论 ： “ 凡 人 要 死 。 苏 格 拉 底 是人 。 所 以 苏 格 拉 底 要 死 。 ” 显 然 在 命 题 逻 辑 中 就 根 本 无 法 判 断 “ 苏 格 拉 底三 段 论 ” 的 正 确 性 。 苏 格 拉 底 三 段 论 ： “ 凡 人 要 死 。 苏 格 拉 底 是 人 。所 以 苏 格 拉 底 要 死 。 ” p： 凡 人 要 死 q： 苏 格 拉 底 是 人 r： 苏 格 拉 底 要 死 则 此 三 段 论 表 示 为 （ p q） r 苏 格 拉 底 三 段 论 是 正 确 的 ， 但 （ p q） r却 不是 重 言 式 。 命 题 逻 辑 是 有 缺 陷 的 。 例 如 ： 张 三 和 李 四 是 兄 弟 。 李 四 和 王 五 是 兄弟 。 所 以 张 三 和 王 五 也 是 兄 弟 。 很 显 然 ， 在 命 题 逻 辑 中 也 无 法 证 明 这 个 推 理的 正 确 性 。 而 这 个 推 理 是 正 确 的 。 命 题 逻 辑 是 有 缺 陷 的 。 命 题 逻 辑 的 特 点 和 局 限 性 ： 命 题 是 命 题 演 算 的 基 本 单 位 ， 不 再 对 简 单 命 题进 行 分 解 。 这 样 的 方 法 太 粗 略 ， 无 法 研 究 命 题 的 内 部 结 构及 命 题 之 间 内 在 的 联 系 。 因 而 命 题 逻 辑 在 推 理 方 面 存 在 局 限 性 。 要 反 映 这 种 内 在 联 系 ， 就 要 对 简 单 命 题 做 进 一步 的 分 析 分 析 出 其 中 的 个 体 词 、 谓 词 、 量 词 等 ， 研 究 它们 的 形 式 结 构 和 逻 辑 关 系 ， 总 结 出 正 确 的 推 理 形 式和 规 则 ， 这 就 是 一 阶 逻 辑 （ 谓 词 逻 辑 ） 的 研 究 内 容 。