人工智能推理技术PPT课件012

第 7章 、 基 本 的 推 理 技 术 推 理 技 术 概 述 基 于 规 则 的 演 绎 推 理 正 向 演 绎 推 理 逆 向 演 绎 推 理 双 向 演 绎 推 理 不 确 定 性 推 理 概 率 推 理 人 工 智 能 是 用 计 算 机 来 模 拟 人 的 智 能 ， 就是 用 能 在 计 算 机 上 实 现 的 技 术 和 方 法 来 模 拟 人的 思 维 规 律 和 过 程 。 1) 在 确 定 知 识 表 达 方 法 后 ， 就 可 以 把 知 识 表 示出 来 并 存 储 到 计 算 机 中 。 2) 然 后 , 利 用 知 识 进 行 推 理 以 求 得 问 题 的 解 . 利 用 知 识 进 行 推 理 是 知 识 利 用 的 基 础 。 各 种人 工 智 能 应 用 领 域 如 专 家 系 统 、 智 能 机 器 人 、模 式 识 别 、 自 然 语 言 理 解 等 都 是 利 用 知 识 进 行广 义 问 题 求 解 的 智 能 系 统 . 7 .1 推 理 技 术 概 述 -1 . 推 理 的 概 念 与 类 型 推 理 是 人 类 求 解 问 题 的 主 要 思 维 方 法 . 所 谓 推 理 就 是 按 照 某 种 策 略 从 已 有 事 实 和 知 识 推 出 结论 的 过 程 。 推 理 是 由 程 序 实 现 的 ， 称 为 推 理 机 。 人 类 的 智 能 活 动 有 多 种 思 维 方 式 ， 人 工 智 能 作 为对 人 类 智 能 的 模 拟 ， 相 应 地 也 有 多 种 推 理 方 式 。 1. 演 绎 推 理 、 归 纳 推 理 、 默 认 推 理 (1). 演 绎 推 理 ： 演 绎 推 理 是 从 全 称 判 断 推 出 特称 判 断 或 单 称 判 断 的 过 程 ， 即 从 一 般 到 个 别 的 推理 。 最 常 用 的 形 式 是 三 段 论 法 。 例 如 ： 1） 所 有 的 推 理 系 统 都 是 智 能 系 统 ； 2） 专 家 系 统 是 推 理 系 统 ； 3） 所 以 ， 专 家 系 统 是 智 能 系 统 。 (2).归 纳 推 理 : 是 从 足 够 多 的 事 例 中 归 纳 出 一 般性 结 论 的 推 理 过 程 ， 是 一 种 从 个 别 到 一 般 的 推 理过 程 。 (3). 默 认 推 理 ： 默 认 推 理 又 称 缺 省 推 理 ， 它 是在 知 识 不 完 全 的 情 况 下 假 设 某 些 条 件 已 经 具 备 所进 行 的 推 理 。 2、 确 定 性 推 理 、 不 确 定 性 推 理 如 果 按 推 理 时 所 用 的 知 识 的 确 定 性 来 分 ， 推 理 可 分为 确 定 性 推 理 与 不 确 定 性 推 理 。 （ 1） 确 定 性 推 理 （ 精 确 推 理 ） 。 如 果 在 推 理 中 所用 的 知 识 都 是 精 确 的 ， 即 可 以 把 知 识 表 示 成 必 然 的因 果 关 系 ， 然 后 进 行 逻 辑 推 理 ， 推 理 的 结 论 或 者 为真 ， 或 者 为 假 ， 这 种 推 理 就 称 为 确 定 性 推 理 。 （ 如归 结 反 演 、 基 于 规 则 的 演 绎 系 统 等 ） （ 2） 不 确 定 性 推 理 (不 精 确 推 理 )。 在 人 类 知 识 中， 有 相 当 一 部 分 属 于 人 们 的 主 观 判 断 ， 是 不 精 确 的和 含 糊 的 。 由 这 些 知 识 归 纳 出 来 的 推 理 规 则 往 往 是不 确 定 的 。 基 于 这 种 不 确 定 的 推 理 规 则 进 行 推 理 ，形 成 的 结 论 也 是 不 确 定 的 ， 这 种 推 理 称 为 不 确 定 推理 。 (在 专 家 系 统 中 主 要 使 用 的 方 法 )。 3、 单 调 推 理 、 非 单 调 推 理 如 果 按 推 理 过 程 中 推 出 的 结 论 是 否 单 调 增 加 ， 或者 说 推 出 的 结 论 是 否 越 来 越 接 近 最 终 目 标 来 划 分， 推 理 又 可 分 为 单 调 推 理 与 非 单 调 推 理 。 （ 1） 单 调 推 理 。 是 指 在 推 理 过 程 中 随 着 推 理 的 向前 推 进 及 新 知 识 的 加 入 ， 推 出 的 结 论 呈 单 调 增 加的 趋 势 ， 并 且 越 来 越 接 近 最 终 目 标 。 (演 绎 推 理 是单 调 推 理 。 ) （ 2） 非 单 调 推 理 。 是 指 在 推 理 过 程 中 随 着 推 理 的向 前 推 进 及 新 知 识 的 加 入 ， 不 仅 没 有 加 强 已 推 出的 结 论 ， 反 而 要 否 定 它 ， 使 得 推 理 退 回 到 前 面 的某 一 步 ， 重 新 开 始 。 (一 般 是 在 知 识 不 完 全 的 情 况下 进 行 的 ) 4、 启 发 式 推 理 、 非 启 发 式 推 理 如 果 按 推 理 中 是 否 运 用 与 问 题 有 关 的 启 发 性 知 识， 推 理 可 分 为 启 发 式 推 理 和 非 启 发 式 推 理 。 （ 1） 启 发 式 推 理 ： 如 果 在 推 理 过 程 中 ， 运 用 与 问题 有 关 的 启 发 性 知 识 ， 如 解 决 问 题 的 策 略 、 技 巧及 经 验 等 ， 以 加 快 推 理 过 程 ， 提 高 搜 索 效 率 ， 这种 推 理 过 程 称 为 启 发 式 推 理 。 如 A、 A*等 算 法 。 （ 2） 非 启 发 式 推 理 。 如 果 在 推 理 过 程 中 ， 不 运 用启 发 性 知 识 ， 只 按 照 一 般 的 控 制 逻 辑 进 行 推 理 ，这 种 推 理 过 程 称 为 非 启 发 式 推 理 。 (推 理 效 率 较 低， 容 易 出 现 “ 组 合 爆 炸 ” 问 题 。 ) - 推 理 的 控 制 策 略 主 要 是 指 推 理 方 向 的 选 择 、 推 理 时 所 用 的 搜 索 策略 及 冲 突 解 决 策 略 等 。 一 般 推 理 的 控 制 策 略 与 知识 表 达 方 法 有 关 (产 生 式 系 统 ) . 1、 推 理 方 向 ： 用 于 确 定 推 理 的 驱 动 方 式 。 分 为 正向 推 理 (由 已 知 事 实 出 发 )、 反 向 推 理 (以 某 个 假 设目 标 作 为 出 发 点 )和 正 反 向 混 合 推 理 (正 向 推 理 和反 向 推 理 相 结 合 ).系 统 组 成 : 知 识 库 （ KB） +初 始事 实 和 中 间 结 果 的 数 据 库 （ DB） + 推 理 机 2、 搜 索 策 略 :推 理 时 要 反 复 用 到 知 识 库 中 的 规 则， 而 知 识 库 中 的 规 则 又 很 多 ， 这 样 就 存 在 着 如 何在 知 识 库 中 寻 找 可 用 规 则 的 问 题 (代 价 小 ,解 好 ). 可 以 采 用 各 种 搜 索 策 略 有 效 地 控 制 规 则 的 选 取 . 3、 冲 突 解 决 策 略 在 推 理 过 程 中 ， 系 统 要 不 断 地 用 数 据 库 中 的 事 实 与知 识 库 中 的 规 则 进 行 匹 配 ， 当 有 一 个 以 上 规 则 的 条件 部 分 和 当 前 数 据 库 相 匹 配 时 ， 就 需 要 有 一 种 策 略来 决 定 首 先 使 用 哪 一 条 规 则 ， 这 就 是 冲 突 解 决 策 略。 冲 突 解 决 策 略 实 际 上 就 是 确 定 规 则 的 启 用 顺 序 。 （ 1） 专 一 性 排 序 (条 件 部 分 更 具 体 的 规 则 ) （ 2） 规 则 排 序 (规 则 编 排 顺 序 ) （ 3） 数 据 排 序 (所 有 条 件 按 优 先 级 次 序 编 排 起 来 ) （ 4） 就 近 排 序 (最 近 使 用 的 规 则 优 先 ) （ 5） 上 下 文 限 制 (在 某 种 上 下 文 条 件 下 ) （ 6） 按 匹 配 度 排 序 (计 算 这 两 个 模 式 的 相 似 程 度 ) （ 7） 按 条 件 个 数 排 序 (条 件 少 的 优 先 ) 7 2 基 于 规 则 的 演 绎 推 理 许 多 AI系 统 中 所 用 到 的 知 识 一 般 是 由 蕴 含 式 直 接 表 示 的 ，但 在 归 结 反 演 中 ， 必 须 首 先 将 它 们 转 化 为 子 句 的 形 式 ， 所以 这 种 推 理 是 比 较 低 效 的 。 基 于 规 则 的 演 绎 推 理 则 是 直 接 的 推 理 方 法 。 它 把 有 关 问 题的 知 识 和 信 息 划 分 为 规 则 与 事 实 两 种 类 型 。 规 则 由 包 含 蕴含 形 式 的 表 达 式 表 示 ， 事 实 由 无 蕴 含 形 式 的 表 达 式 表 示 ，并 画 出 相 应 的 与 或 图 ， 然 后 通 过 规 则 进 行 演 绎 推 理 。 可 分 为 正 向 、 反 向 和 正 反 向 演 绎 推 理 。 在 正 向 推 理 中 ， 作为 F规 则 用 的 蕴 含 式 对 事 实 的 总 数 据 库 进 行 操 作 运 算 ， 直 至得 到 该 目 标 公 式 的 一 个 终 止 条 件 为 止 ； 在 反 向 推 理 中 ， 作为 B规 则 用 的 蕴 含 式 对 目 标 的 总 数 据 库 进 行 操 作 运 算 ， 直 至得 到 包 含 这 些 事 实 的 一 个 终 止 条 件 为 止 ； 在 双 向 推 理 中 ，分 别 从 两 个 方 向 应 用 不 同 的 规 则 （ F和 B） 进 行 操 作 运 算 。 7 2 1 正 向 演 绎 推 理 正 向 演 绎 推 理 属 于 正 向 推 理 ， 它 是 从 已 知 事 实 出 发 ， 反 复尝 试 所 有 可 利 用 的 规 则 （ F规 则 ） 进 行 演 绎 推 理 ， 直 到 得 到某 个 目 标 公 式 的 一 个 终 止 条 件 为 止 。 1、 事 实 表 达 式 及 其 与 或 图 表 示 正 向 演 绎 要 求 事 实 用 不 包 含 蕴 含 符 号 “ ” 的 与 或 形表 示 。 把 一 个 表 达 式 转 化 为 标 准 的 与 或 形 的 步 骤 如 下 ： （ 1） 利 用 等 价 式 PQ与 PQ消 去 蕴 含 符 “ ” 。 （ 2） 把 否 定 符 号 “ ” 移 到 每 个 谓 词 符 号 的 前 面 。 （ 3） 变 量 标 准 化 ， 即 重 新 命 名 变 量 ， 使 不 同 量 词 约 束 的变 量 有 不 同 的 名 字 。 （ 4） 引 入 Skolem函 数 消 去 存 在 量 词 。 （ 5） 将 公 式 化 为 前 束 形 。 （ 6） 略 去 全 称 量 词 （ 默 认 变 量 是 全 称 量 词 量 化 的 ） 。 （ 7） 重 新 命 名 变 量 ， 使 同 一 变 量 不 出 现 在 不 同 的 主 要 合取 式 中 。 例 如 ： 有 如 下 的 表 达 式 （ x） （ y） Q（ y， x） （ R（ y） P（ y） ）S（ x， y） 可 将 其 转 化 为 下 面 标 准 的 与 或 形 ： Q（ z， A） R（ y） P（ y） S（ A， y） 于 是 ,它 的 标 准 与 或 形 可 用 一 棵 与 或 树 表 示 出 来 。 在 与 或 图 中 ， 节 点 表 示 事 实 表 达 式 及 其 子 表 达 式 。根 节 点 表 示 整 个 表 达 式 ， 叶 节 点 表 示 其 中 的 单 文 字. 规 定 : 对 于 一 个 表 示 析 取 表 达 式 （ E1E2En）的 节 点 ， 用 一 个 n连 接 符 （ 含 半 圆 的 弧 ） 与 连 接 它的 n个 子 表 达 式 节 点 相 连 。 对 于 一 个 表 示 合 取 表 达式 （ E1E2En） 的 节 点 ， 用 n个 1连 接 符 与 连 接它 的 n个 子 表 达 式 节 点 相 连 。 重 要 性 质 :就 是 由 变 换 表 达 式 得 到 的 一 组 子 句 ， 可以 从 与 或 图 中 读 出 ， 每 个 子 句 相 当 于 与 或 图 的 一 个解 图 ， 每 个 子 句 是 由 叶 节 点 组 合 成 的 公 式 。 上 例 的3个 子 句 是 ： Q（ z， A） ； S（ A， y） R（ y） ； S（ A， y） P（ y） 这 三 个 子 句 正 是 原 表 达 式 化 成 的 子 句 集 。 因 此 ， 与或 树 可 以 看 成 是 一 组 子 句 的 一 个 简 洁 的 表 达 式 。 2、 F规 则 的 表 示 形 式 基 于 规 则 的 正 向 推 理 中 ， 要 求 F规 则 具 有 以 下 形 式： LW。 具 体 要 求 如 下 ：1. L是 单 文 字 ， W是 任 意 的 与 或 形 表 达 式 。2. L和 W中 的 所 有 变 量 都 是 全 称 量 词 量 化 的 ， 默 认 的全 称 量 词 作 用 于 整 个 蕴 含 式 。3. 各 条 规 则 的 变 量 各 不 相 同 ， 而 且 规 则 中 的 变 量 与事 实 表 达 式 中 的 变 量 也 不 相 同 。 将 F规 则 的 左 部 限 制 为 单 文 字 ， 是 因 为 与 或 图 的 叶节 点 都 是 单 文 字 ， 这 样 就 可 用 F规 则 的 左 部 与 叶 节点 进 行 匹 配 ， 大 大 简 化 了 规 则 的 应 用 过 程 。 如 果 所 给 知 识 的 表 示 形 式 不 是 所 要 求 的 形 式 ， 则 可 用 如 下步 骤 将 其 变 换 成 标 准 形 式 ：（ 1） 暂 时 消 去 蕴 含 符 号 “ ” 。 例 如 公 式 （ x） （ y） （ z） P（ x， y， z） （ u） Q（ x， u） 消 去 蕴 含 符 号 “ ” 变 为 ： （ x） （ y） （ z） P（ x， y， z） （ u） Q（ x， u） （ 2） 把 否 定 号 “ ” 移 到 每 个 谓 词 的 前 面 ,可 变 为 （ x） （ y） （ z） P（ x， y， z） （ u） Q（ x， u） （ 3） 引 入 skolem函 数 消 去 存 在 量 词 。 消 去 存 在 量 词 后 ， 为 （ x） （ y） P（ x， y， f（ x， y） ） （ u） Q（ x， u） （ 4） 将 公 式 化 为 前 束 式 ， 并 略 去 全 称 量 词 ,可 变 为 P（ x， y， f（ x， y） ） Q（ x， u）（ 5） 恢 复 为 蕴 含 式 。 利 用 等 价 关 系 PQ 与 PQ 将 上 式 变 为 P（ x， y， f（ x， y） ） Q（ x， u） 3、 目 标 公 式 的 表 示 形 式 要 求 目 标 公 式 用 文 字 的 析 取 式 (子 句 )表 示 ， 否 则 就 要 化为 子 句 形 式 。4、 推 理 过 程 应 用 F规 则 作 用 于 表 示 事 实 的 与 或 图 ， 改 变 与 或 图 的 结构 ， 从 而 产 生 新 事 实 ， 直 至 推 出 了 目 标 公 式 。 过 程 为 ： 首 先 用 与 或 图 把 已 知 事 实 表 示 出 来 。 用 F规 则 的 左 部 和 与 或 图 的 叶 节 点 进 行 匹 配 ， 并 将 匹 配成 功 的 F规 则 结 论 加 入 到 与 或 图 中 ， 即 利 用 F规 则 转 换 与或 图 。 重 复 第 （ 2） 步 ， 直 到 产 生 一 个 含 有 以 目 标 节 点 作 为 终止 节 点 的 解 图 为 止 ， 当 一 个 目 标 文 字 和 与 或 图 中 的 一 个文 字 匹 配 时 ， 可 以 将 表 示 该 目 标 文 字 的 节 点 (目 标 节 点 )通 过 匹 配 连 接 到 与 或 图 中 相 应 的 文 字 节 点 上 。 当 演 绎 产生 的 与 或 图 包 括 一 个 目 标 节 点 上 结 束 的 解 图 时 ， 推 理 便成 功 结 束 。 1)、 命 题 逻 辑 的 情 况 应 用 规 则 的 匹 配 过 程 比 较 简 单 。 设 已 知 事 实 的 与或 形 表 达 式 为 ： （ （ PQ） R） （ S （ TU） ） 规 则 为 S（ XY） Z 把 已 知 事 实 用 与 或 图 表 示 ， 图 中 有 一 个 叶 节 点 是文 字 S， 它 正 好 与 规 则 的 前 项 的 文 字 S完 全 匹 配 ，由 此 可 直 接 用 这 条 规 则 对 与 或 图 进 行 变 换 ， 即 把规 则 后 项 的 与 或 形 公 式 用 与 或 图 表 示 后 添 加 到 已知 事 实 的 与 或 图 上 ， 并 用 一 个 匹 配 弧 连 接 起 来 ，规 则 匹 配 后 演 绎 的 结 果 如 下 图 所 示 。 图 中 匹 配 弧后 面 是 规 则 部 分 。 例 ： 事 实 表 达 式 ： AB； 规 则 集 合 ： ACD，BEG； 目 标 公 式 ： C G 应 用 完 这 两 条 规 则 后， 得 到 的 与 或 图 如 图所 示 ， 其 中 有 一 个 解图 满 足 目 标 公 式 （ C G） 所 建 立 的 结 束条 件 。 2)、 谓 词 逻 辑 的 情 况 需 要 讨 论 对 含 有 变 量 的 目 标 公 式 的 处 理 (匹 配 问 题 )。 对 具 有 量 词 量 化 变 量 的 目 标 公 式 来 说 ， 化 简 时 要 使 用Skolem化 过 程 的 对 偶 形 式 。 即 目 标 中 属 于 存 在 量 词 辖 域内 的 全 称 量 化 变 量 要 用 存 在 量 化 变 量 的 Skolem函 数 来 替代 ， 经 过 Skolem化 的 公 式 只 剩 下 存 在 量 词 ， 然 后 对 析 取元 作 变 量 改 名 ， 最 后 再 把 存 在 量 词 省 略 掉 。 例 如 ， 设 目 标 公 式 为 （ y） （ x） （ P（ x， y） Q（ x， y） ） 用 函 数 消 去 全 称 量 词 后 有 （ y） （ P（ f（ y） ， y） Q（ f（ y） ， y） ） ； 然 后 进 行 变 量 改 名 ， 使每 个 析 取 元 具 有 不 同 的 变 量 符 号 ， 于 是 有 （ y） （ P（ f（ y） ， y） （ y 1） Q（ f（ y1） ， y1） ） 最 后 省 去 存 在 量 词 （ P（ f（ y） ， y） Q（ f（ y1） ， y1） ） 以 后 目 标 公 式 中 的 变 量 都 假 定 受 存 在 量 词 的 约 束 。 下 面 举 例 说 明 应 用 一 条 规 则 LW对 与 或 图 进 行 变 换的 过 程 。 设 与 或 图 中 有 一 个 端 节 点 的 文 字 L和 L可 合一 ， mgu是 u， 则 这 条 规 则 可 应 用 ， 这 时 用 匹 配 弧 连接 的 后 裔 节 点 是 L， 它 是 规 则 后 项 Wu对 应 的 与 或 图表 示 的 根 节 点 ， 在 匹 配 弧 上 标 记 有 u， 表 示 用 u置 换后 可 与 规 则 匹 配 。 例 、 事 实 与 或 形 表 示 P（ x， y） （ Q（ x， A） R（ B， y） ） 规 则 蕴 涵 式 P（ A， B） (S(A) X(B) 下 图 是 应 用 规 则 变 换 后 得 到 的 与 或 图 ， 它 有 两 个 解图 ， 对 应 的 两 个 子 句 是 S(A) X(B) Q（ A， A）； S(A) X(B) R（ B， B） 它 们 正 是 事 实 和 规 则 公式 组 成 的 子 句 集 对 文 字 P进 行 归 结 时 得 到 的 归 结 式。 图 7-7、 应 用 一 条 含 有 变 量 的 规 则 后 得 到 的 与 或 图 当 一 个 与 或 图 含 有 多 个 的 匹 配 弧 (应 用 了 多 条 规 则时 )， 任 一 解 图 可 能 含 多 个 匹 配 弧 （ 对 应 的 置 换 是u1,u2,un） ， 故 在 列 写 解 图 的 子 句 集 合 时 ， 只 考虑 具 有 一 致 的 匹 配 弧 置 换 的 那 些 解 图 （ 一 致 解 图 ）。 一 个 一 致 解 图 表 示 的 子 句 是 对 得 到 的 文 字 析 取 式应 用 一 个 合 一 复 合 的 置 换 之 后 所 得 到 的 子 句 。 设 有 一 个 置 换 集 U=u1,u2,un,其 中 u i =t i 1/v i 1, t i 2/v i 2,tim(i)/vim(i)是 置 换 对 集 合， t是 项 ， v是 变 量 。 根 据 这 个 置 换 集 ， 定 义 变 量 集 和 项 集 ： U1=( v11, v1m(1) , v21, v2m(2) , vn1, vnm(n) ,) (由 每 个 置 换 ui中 的 变 量 vi构 成 ) U 2=( t11, t1m(1) , t21, t2m(2) , tn1, tnm(n) ,) (由 每 个 置 换 ui中 的 项 ti构 成 ) 则 置 换 U一 致 的 充 要 条 件 是 U1 和 U2是 可 合 一 的 。 而 U的 合 一 复 合 u=mgu(U1, U2)。 可 以 验 证 对 一 个 置 换 集 合 求 合 一 复 合 的 运 算 是 可 结 合 和 可 交换 的 （ 求 置 换 的 合 成 是 不 可 交 换 的 ） ， 因 此 一 个 解 图 对 应 的合 一 复 合 不 依 赖 于 构 造 这 个 解 图 时 所 产 生 的 匹 配 弧 的 次 序 。 例 ： 设 事 实 和 规 则 描 述 如 下 ： Fido barks and bites, or Fido is not a dog. F: DOG(FIDO) (BARKS(FIDO) BITES(FIDO) All terriers are dogs. R1: （ x） DOG(x)TERRIER(x)(原 规 则 的 逆 否) Anyone who barks is noisy. R2: （ y） BARKS(y) NOISY(y) 要 证 明 的 目 标 是 There exists someone who is not a terriers or who is noisy. 目 标 公 式 ： （ z） TERRIER(z) NOISY(z) 上 图 给 出 了 演 绎 得 到 的 与 或 图 ， 图 中 结 束 在 目 标节 点 的 一 个 一 致 解 图 ， 有 置 换 集 合 FIDO/x,FIDO/y,FIDO/z， 它 的 合 一 复 合是 u=FIDO/x, FIDO/y, FIDO/z。 根 据 这 个 一 致解 图 ， 目 标 公 式 是 事 实 和 规 则 的 逻 辑 推 论 ， 因 而得 到 了 证 明 。 如 果 用 这 个 合 一 复 合 u应 用 于 这 个 目 标 公 式 ， 可 得 TERRIER(FIDO) NOISY(FIDO)， 它 是 已 证 目 标公 式 的 例 ， 可 作 为 一 个 回 答 语 句 。 7 2 2 反 向 演 绎 推 理 它 从 目 标 表 达 式 出 发 ， 通 过 反 向 运 用 规 则 进 行 演绎 推 理 ， 直 到 得 到 包 含 已 知 事 实 的 终 止 条 件 为 止 .1、 目 标 表 达 式 及 其 与 或 图 表 示 首 先 ,要 将 目 标 表 达 式 转 化 为 无 蕴 涵 符 “ ” 的 与或 形 式 ， 并 用 与 或 图 表 示 。 要 采 用 正 向 演 绎 中 对事 实 表 达 式 的 变 换 的 对 偶 形 式 : 即 skolem化 全 称量 词 量 化 的 变 量 ， 略 去 存 在 量 词 （ 与 正 向 演 绎 中对 目 标 表 达 式 的 处 理 一 致 ） 。 例 如 、 有 如 下 的 目 标 表 达 式 ： (y)(x) P(x) Q(x,y)(R(x)S(y) 可 转 化 为 如 下 与 或 形 式 ： P(f(y) Q(f(y),y) R(f(y) S(y) 为 使 析 取 式 具 有 不 同 的 变 量 名 ， 重 命 名 变 量 ， 得 P(f(z) Q(f(y),y) R(f(y) S(y) 与 或 形 式 的 目 标 表 达 式 可 以 用 与 或 图 表 示 ， 但其 表 示 方 式 与 正 向 演 绎 中 事 实 表 达 式 的 与 或 图 不 同。 它 的 n连 接 符 用 来 把 具 有 合 取 关 系 的 子 表 达 式 连接 起 来 ， 而 在 正 向 演 绎 中 是 把 事 实 表 达 式 具 有 析 取关 系 的 子 表 达 式 连 接 起 来 。 上 例 的 目 标 表 达 式 的 与或 图 如 下 图 所 示 。 图 中 根 节 点 为 目 标 表 达 式 ， 称 为 目 标 节 点 ， 叶 节 点表 示 单 个 文 字 。 若 把 叶 节 点 用 它 们 之 间 的 合 取 及 析取 关 系 连 接 起 来 ， 就 可 得 到 原 目 标 表 达 式 的 三 个 子目 标 ： P(f(z) ； Q(f(y),y) R(f(y)；Q(f(y),y) S(y) 可 以 看 出 ， 子 目 标 是 文 字 的合 取 式 ， 其 中 的 变 量 是 存 在 量 词 量 化 的 。 2、 B规 则 的 表 示 形 式 反 向 演 绎 推 理 中 的 规 则 称 为 B规 则 ， 其 表 示 形 式为 WL， 其 中 W为 任 一 与 或 形 式 表 达 式 ， L为 单一 文 字 (为 了 方 便 匹 配 ) 。 如 果 规 则 不 符 合 这 一要 求 ， 则 要 变 换 成 这 种 形 式 。 如 规 则 WL1 L2， 可 以 转 换 为 两 个 B规 则 ， 即 WL1， WL2。 规 则 中 应 Skolem化 存 在 量 词 量 化 的 变 量 ， 并 略 去全 称 量 词 。3、 已 知 事 实 的 表 示 形 式 在 反 向 演 绎 推 理 中 ， 要 求 已 知 事 实 表 达 式 是 文 字的 合 取 式 ， 可 表 示 为 文 字 的 集 合 。 对 任 意 事 实 表达 式 ， 应 当 用 Skolem函 数 代 替 事 实 表 达 式 中 存 在量 词 量 化 的 变 量 ， 并 略 去 全 称 量 词 量 化 的 变 量 ，将 表 达 式 转 化 为 标 准 的 文 字 的 合 取 式 。 4、 推 理 过 程具 体 过 程 如 下 ：1. 用 与 或 图 将 目 标 表 达 式 表 示 出 来 。2. 在 目 标 与 或 图 中 ， 如 果 有 一 个 文 字 L能 够 与 L合 一， 则 可 应 用 B规 则 WL， 并 将 L节 点 通 过 一 个 标 有L和 L的 最 简 单 合 一 者 的 匹 配 弧 与 L相 连 ， 再 将 匹配 成 功 的 B规 则 加 入 与 或 图 中 。 一 条 规 则 可 用 多次 ， 每 次 应 使 用 不 同 的 变 量 。 当 一 个 事 实 文 字 和与 或 图 中 的 一 个 文 字 可 以 合 一 时 ， 可 将 该 事 实 文字 通 过 匹 配 弧 连 接 到 与 或 图 中 相 应 的 文 字 上 ， 匹配 弧 应 标 明 两 个 文 字 的 最 简 单 的 合 一 者 。3. 重 复 进 行 第 2步 ， 直 到 与 或 图 中 包 括 一 个 结 束 在事 实 节 点 上 的 一 致 解 图 ， 该 解 图 的 合 一 复 合 作 用于 目 标 表 达 式 就 是 解 答 语 句 。 例 、 设 有 事 实 ： F1： DOG（ FIDO） FIDO是 一 只 狗 F2： BARKS（ FIDO） FIDO不 叫 F3： WAGS-TAIL（ FIDO） FIDO摆 尾 巴 F4： MEOWS（ MYRTLE） MYRTLE喵 喵 叫 规 则 如 下 ： R1： WAGS-TAIL（ x1） DOG（ x1） FRIENDLY（ x1） 摆 尾 巴 的 狗 是 友 好 的 R2： FRIENDLY（ x2） BARKS（ x2） AFRAID（ y2， x2） 友 好 且 不 叫 的 是 不 令 对 方 害 怕 的 R 3： DOG（ x3） ANIMAL（ x3） 狗 是 动 物 R4： CAT（ x4） ANIMAL（ x4） 猫 是 动 物 R5： MEOWS（ x5） CAT（ x5） 喵 喵 叫 的 是 猫 问 题 是 ： 是 否 存 在 一 只 猫 和 一 条 狗 ， 这 只 猫 不 怕 这 条 狗 ？ 该 问 题 的 目 标 公 式 是 ： （ x） （ y） CAT（ x） DOG（ y） AFRAID（ x， y） ， 求 解 该 问 题 的 过 程 如 下 图 . CAT（ x） DOG（ y） AFRAID（ x， y） AFRAID（ x， y） DOG(y)CAT(x) DOG(FIDO)CAT(x5) AFRAID（ y2， x2） MEOWS(x) MEOWS(MYRTLE) BARKS（ y） FRIENDLY(y) BARKS（ FIDO） FRIENDLY(x1)WAGS-TAIL(y) DOG(y) WAGS-TAIL(FIDO) DOG(FIDO) x/x5R5MYRTLE/x FIDO/y x/y2,y/x2R2 FIDO/y y/x1R1 FIDO/y FIDO/y 从 上 图 可 看 出 ， 最 后 得 到 的 是 一 个 一 致 解 图 。图 中 共 有 8条 匹 配 弧 ， 每 条 匹 配 弧 上 都 标 有 置 换 ，分 别 为 x/x5、 MYRTLE/x、 FIDO/y、x/y2,y/x2、 FIDO/y、 y/x1、 FIDO/y和FIDO/y。 这 些 置 换 的 合 一 复 合 为 MYRTLE/x 5， MYRTLE/x ， FIDO/y ， MYRTLE/ y2， FIDO/ x2，FIDO/ x1 ， 将 合 一 复 合 作 用 于 目 标 表 达 式 就 得 到解 答 语 句 ： CAT（ MYRTLE） DOG（ FIDO） AFRAID（MYRTLE， FIDO） 它 表 示 有 一 只 名 叫 MYRTLE的 猫 和 一 条 名 叫 FIDO的狗 ， 这 只 猫 不 怕 那 条 狗 。 使 用 条 件正 向 系 统 事 实 表 达 式 是 任 意 形 式 规 则 形 式 为 LW或L1L2W（ (L为 单 文 字， W为 任 意 形 式 ） 目 标 公 式 为 文 字 析 取 形 逆 向 系 统 事 实 表 达 式 是 文 字 合 取形 规 则 形 式 为 WL或 W L1L2（ (L为 单 文 字 ，W为 任 意 形 式 ） 目 标 公 式 为 任 意 形 式 化 简 过 程正 向 系 统 用 skolem函 数 消 去 事 实表 达 式 中 的 存 在 量 词 ，化 简 的 公 式 受 全 称 量 词的 约 束 ; 对 规 则 的 处 理 同 上 ; 用 skolem函 数 （ 对 偶 形） 消 去 目 标 公 式 中 的 全称 量 词 ， 化 简 的 公 式 受存 在 量 词 约 束 . 逆 向 系 统 skolem函 数 （ 对 偶 形 ）消 去 目 标 公 式 中 的 全 称量 词 ， 化 简 的 公 式 受 存在 量 词 约 束 。 对 规 则 的 处 理 同 下 ; 用 skolem函 数 消 去 事 实表 达 式 中 的 存 在 量 词 ，化 简 的 公 式 受 全 称 量 词的 约 束 . 正 向 系 统 逆 向 系 统初 始 数 据 库 事 实 表 达 式 的 与 或 树（ 对 应 为 与 关 系 ，对 应 为 或 关 系 ） . 目 标 公 式 的 与 或 树 （ 对 应 为 或 关 系 ， 对 应为 与 关 系 ） .推 理 过 程 从 事 实 出 发 ， 正 向 应用 规 则 （ 变 量 改 名 ，前 项 与 事 实 文 字 匹 配 ，后 项 代 替 前 项 ） ， 直至 得 到 目 标 节 点 为 结束 条 件 的 一 致 解 为 止 . 从 目 标 出 发 ， 逆 向 应 用规 则 （ 变 量 改 名 ， 后 项与 子 目 标 文 字 匹 配 ， 前项 代 替 后 项 ） ， 直 至 得到 事 实 节 点 为 结 束 条 件的 一 致 解 图 为 止 .子 句 形 式 的 子集 形 式 文 字 的 析 取 式 ; 子 句 的 合 取 式 （ 合 取范 式 ） . 文 字 的 合 取 式 ;子 句 的 析 取 式 （ 析 取 范式 ） . 7 2 3 双 向 演 绎 推 理 正 向 演 绎 推 理 要 求 目 标 表 达 式 是 文 字 的 析 取 式 ， 而反 向 演 绎 推 理 要 求 事 实 公 式 为 文 字 的 合 取 式 。 为 充分 发 挥 正 向 演 绎 和 反 向 演 绎 的 优 点 ， 克 服 各 自 的 局限 性 ， 可 将 两 种 演 绎 推 理 相 结 合 ， 这 就 是 双 向 演 绎推 理 。 在 双 向 演 绎 推 理 中 ， 已 知 事 实 用 与 或 图 表 示 ， 目 标表 达 式 用 另 一 个 与 或 图 表 示 。 这 两 个 与 或 图 分 别 由正 向 演 绎 的 F规 则 和 反 向 演 绎 的 B规 则 进 行 操 作 ， 并且 仍 限 制 F规 则 的 左 部 为 单 文 字 ， 而 B规 则 的 右 部 为单 文 字 。 双 向 演 绎 推 理 分 别 从 正 反 两 个 方 向 进 行 推 理 ， 两 个与 或 图 分 别 扩 展 ， 最 关 键 也 是 最 复 杂 的 是 如 何 判 断推 理 是 否 结 束 。 推 理 的 终 止 处 位 于 两 个 与 或 图 分 别扩 展 后 的 某 个 交 接 处 ， 当 正 反 两 个 方 向 的 与 或 图 对应 的 叶 节 点 都 可 合 一 时 ， 推 理 就 结 束 。 P(f(y) Q(f(y),y) R(f(y) S(y) P(f(y) Q(f(y),y) R(f(y) S(y) Q(f(y),y) R(f(y) S(y) R(f(y) S(y) S(A) R(x) Q(x,A) R(x) S(A) Q(x,A) R(x) S(A) f(A)/x,A/y f(A)/x A/y 匹 配 目 标 表 达 式 与或 图 （ B规 则 ） 事 实 表 达 式 与或 图 （ F规 则 ） 上 图 说 明 了 双 向 演 绎 推 理 的 过 程 。 图 中 对 应 的 已 知 事实 表 达 式 和 目 标 表 达 式 分 别 为 ： Q(x,A) R(x) S(A); P(f(y) Q(f(y),y) R(f(y)S(y) 图 中 ， 共 有 3个 匹 配 弧 ， 并 标 有 各 自 的 置 换 。 这 些 置 换是 一 致 的 ， 其 合 一 复 合 为 f（ A） /x， A/y。 在 推 理 过程 中 ， 没 有 使 用 B规 则 和 F规 则 ， 这 里 主 要 说 明 双 向 推理 是 如 何 在 交 接 处 终 止 的 。 7.3 不 确 定 性 推 理 逻 辑 推 理 是 一 种 运 用 确 定 性 知 识 进 行 的 精 确 推理 。 但 是 ， 现 实 世 界 中 的 事 物 以 及 事 物 之 间 的关 系 是 极 其 复 杂 的 ， 在 人 类 知 识 中 ， 有 相 当 一部 分 是 不 精 确 的 、 模 糊 的 ， 因 此 不 精 确 的 推 理模 型 是 人 工 智 能 和 专 家 系 统 的 一 个 核 心 研 究 问题 . 实 际 上 ， AI系 统 的 智 能 主 要 反 映 在 求 解 不 精 确性 问 题 的 能 力 上 。 不 确 定 性 推 理 就 是 从 不 确 定 性 初 始 事 实 （ 证 据） 出 发 ， 通 过 运 用 不 确 定 性 的 知 识 ， 最 终 推 出具 有 一 定 程 度 的 不 确 定 性 是 合 理 或 者 近 乎 合 理的 结 论 的 思 维 过 程 。 一 概 率 方 法 )( )()|( BP BAPBAP 1) 条 件 概 率 : 设 A和 B是 某 随 机 试 验 中 的 两 个 事 件 ，如 果 在 事 件 B发 生 的 条 件 下 考 虑 事 件 A发 生 的 概 率 ， 就称 它 为 事 件 A的 条 件 概 论 ， 记 做 P（ A|B） 。 若 P（ B） 0，则2) 全 概 率 公 式 ： 设 事 件 A1 ， A2， ， An满 足 : 两 两 互 不 相 容 ， 即 当 ij， AiAj=； P（ Ai） 0 D为 必 然 事 件 ； 则 对 任 何 事 件 B有 下 式 成 立 ： ni iAD 1该 公 式 称 为 全 概 率 公 式 ， 它 提 供 了 一 种 计 算 P（ B） 的 方 法 。 3） Bayes公 式 ： 设 事 件 A1 ， A2， ， An满 足 上 述 全概 率 公 式 的 条 件 ， 则 对 任 何 事 件 B有 下 式 成 立 niABPAP ABPAPBAP nj jj iii ,.2.1)|()( )|()()|( 1 该 式 称 为 Bayes公 式 。 如 果 把 全 概 率 公 式 代 入 Bayes公 式 中 ， 就 得 到 niBP ABPAPBAP iii ,.2.1)( )|()()|( 这 是 Bayes公 式 的 另 外 一 种 表 示 形 式 。 二 概 率 推 理 概 率 推 理 就 是 由 给 定 的 变 量 信 息 来 计 算 其 它 变 量的 概 率 信 息 的 过 程 。 假 设 给 定 证 据 集 合 E为 变 量 集合 Y的 子 集 ， 其 中 变 量 取 值 用 e表 示 ， 即 E=e， 此 时若 希 望 计 算 条 件 概 率 的 值 ， 即 在 给定 证 据 变 量 取 值 后 求 变 量 的 概 率 ， 这 个 过程 被 称 为 概 率 推 理 。 在 基 于 概 率 的 不 确 定 推 理 中 ， 概 率 一 般 解 释 为 专家 对 证 据 和 规 则 的 主 观 信 任 度 。 对 概 率 推 理 起 着支 撑 作 用 的 是 Bayes公 式 。 Bayes公 式 用 于 不 确 定 推 理 的 一 个 原 始 条 件 是 ： 已知 前 提 E的 概 率 P（ E） 和 H的 先 验 概 率 P（ H） ， 并已 知 H成 立 时 E出 现 的 条 件 概 率 P（ E|H） 。 推 理 的目 的 是 推 出 H的 后 验 概 率 P（ H|E） 。 )|( eEyYp ii ii yY 如 果 有 多 个 证 据 E1， E2， ， Em和 多 个 结 论 H1， H2， ， Hn， 并 且 每 个 证 据 都 以 一 定 程 度 支 持 结 论 ， 则 nj jjmjj iimiimi HPHEPHEPHEP HPHEPHEPHEPEEEHP 1 21 2121 )()|()|()|( )()|()|()|()|( 此 时 ， 只 要 已 知 Hj的 先 验 概 率 P（ Hj） 及 Hi成 立 时 证 据 E1， E2， Em出 现 的 条 件 概 率 P（ E1|Hj） ， P（ E2|Hj） ， ， P（ Em|Hj） ， 就 可 利 用 上 述 计 算 出 在 E1 ， E2， ， Em出 现 的情 况 下 的 条 件 概 率 P（ Hi|E1， E2， ， Em） 。 例 ： 设 H 1表 示 足 球 水 平 低 ; H2表 示 足 球 水 平 中 ;H3表 示 足 球水 平 高 ; E1 赢 日 本 ; E2赢 中 国 ;E3赢 香 港 ; 并 且 已 知 P（ H1）=0.4， P（ H2） =0.3， P（ H3） =0.3 解 : 利 用 公 式 ,可 得 152.0)()|()|()()|()|()()|()|( )()|()|()|( 332312222111211 11211211 HPHEPHEPHPHEPHEPHPHEPHEP HPHEPHEPEEHP 同 理 可 得 : P（ H2|E1E2） =0.333, P（ H3|E1E2） =0.515. 从 上 可 见 ,由 于 证 据 E1E2的 出 现 , H3 和 H2成 立 的 可 能 性 有 不同 程 度 的 增 加 , H1成 立 的 可 能 性 下 降 了 . 588.0)()|()|()|( )()|()|()|( )|( 2619.0 1539.032131 3333231 3213 jjjjj HPHEPHEPHEP HPHEPHEPHEP EEEHP P（ E1|H1） =0.3， P（ E1|H2） =0.5， P（ E1|H3） =0.6 P（ E2|H1） =0.4， P（ E2|H2） =0.7， P（ E2|H3） =0.9 P（ E3|H1） =0.5， P（ E3|H2） =0.8， P（ E3|H3） =0.95 求 P（ H1|E1E2） 、 P（ H2|E1E2） 及 P（ H3|E1E2） 的 值 各 是 多 少 .