人工智能搜索推理技术消解原理

《人工智能搜索推理技术消解原理》由会员分享，可在线阅读，更多相关《人工智能搜索推理技术消解原理（147页珍藏版）》请在装配图网上搜索。

1、人 工 智 能Artificial Intelligence (AI) 第 3章 搜 索 推 理 技 术 3.1 图 的 搜 索 策 略3.2 盲 目 搜 索3.3 启 发 式 搜 索3.4 与 或 树 搜 索 （补充）3.5 博 弈 树 搜 索 （补充）3.6 消 解 原 理 3.6 消 解 原 理3.6.1 子 句 集 的 求 取3.6.2 消 解 原 理 （ 补 充 ）3.6.3 消 解 推 理 规 则3.6.4 含 有 变 量 的 消 解 式3.6.5 消 解 反 演 求 解 过 程3.6.6 Horn子 句 集 消 解 （ 补 充 ）3.6.7 Prolog 语 言 简 介 （ 补

2、充 ） 3.6 消 解 原 理 第2章中介绍： 谓 词 逻 辑 的 基 本 知 识 合 一 算 法 （ 求 最 一 般 的 一 致 置 换 或 合 一 者mgu）本节：消 解 原 理 （ 或 者 归 结 原 理 ） 3.6.1 子 句 集 的 求 取如何将谓词公式转化为子句集，作为合一算法的输入（公式集） 3.6.1.1 若 干 基 本 概 念3.6.1.2 子 句 集 的 求 取 3.6.1.1 若 干 基 本 概 念1 自 由 变 元 与 约 束 变 元 2 前 束 范 式 与 前 束 合 取 范 式3 斯 科 伦 （ Skolem） 范 式4 子 句 集 设 ， 是 一 个 谓 词 公

3、式 ， 将量词记 作 （ 即 或 ）1 自 由 变 元 与 约 束 变 元 如 果 中 包 含 部 分 公 式 (x)， 则 中 变 元 x 的 一切 出 现 都 称 为 x 在 中 的 约 束 出 现 ， 相 应 地 称 x 为约束变元（ 哑 元 、 虚 构 变 量 、 约 束 变 量 ）约束变元 中 不 在 任 何 量 词 作 用 域 内 的 变 元 x ， 称 为 变元 x 在 中 的 自 由 出 现 ， 相 应 地 称 x 为自由变元（ 自 由 变 量 ）自由变元： 量 词 的 作 用 域 （ 辖 域 ） 是 直 接 跟 在 它 后 面 的 公式 如 果 有 括 号 ， 则 是 括 号

4、 里 的 公 式 如 果 没 有 括 号 ， 则 是 最 短 的 完 整 公 式说明： 例 1： x ( P(x) ) x , y 都 是 约 束 变 元例 2： x ( P(x) (R(x, y) ) x 是 约 束 变 量 ， y 是 自 由 变 元 改名： 将 谓 词 公 式 中 一 个 变 元 名 改 成 另 一 个 变 元名 ， 但 是 要 求 改 名 后 的 公 式 与 原 公 式意义相同（ 真 假 值 相 同 ）原则： 改 成 的 新 的 变 元 名 一 定 是量词作用域中 没有 出 现 过 的 变 元 名 （ 包 括 约 束 变 元 和 自 由 变 元 ）约 束 变 元 的 改

5、 名 或 变 量 的 标 准 化 例 3： x ( P(x) (R(x, y) 除 了 y 外 ， 可 以 将 x 改 成 任 何 变 元 名例 4： x P(x) Q(y) 可 以 改 成 任 何 变 元 名 ， 包 括 y（ 建 议 不 要 用 ） 2 前 束 范 式 与 前 束 合 取 范 式 定义： 设 谓 词 公 式 具 有 形 式 ： (1x1)(nxn) M其 中 ： i ( i = 1 , , n ) 是 或 M 是 不 包 含 量 词 的 谓 词 公 式则 ， 称 是 前 束 范 式 称 ( 1x1)(nxn ) 为 前 束 称 M 为 母 式 定义： 设 谓 词 公 式 是

6、 一 个 前 束 范 式 ， 如 果 的 母 式具 有 形 式 ： （ M11 M12 M1 n1） （ M21 M22 M2 n2） (Mm1 Mm2 Mm nm）其 中 ， M i j 是 原 子 公 式 或 其 非 ， 则 称 是 前 束 合 取范 式 。 相 应 地 有 前 束 析 取 范 式 前束范式：(x) (y) (z)( P(x) Q(y) R(z) 前束合取范式（交换律、分配律）(x) (y) (z)(R(z) P(x) (R(z) Q(y)例： 3 斯 柯 伦 范 式 定义： 前 束 中不含存在量词的 前 束 范 式 称 为 斯柯 伦 范 式 若 xk (1 k n )左

7、边 没 有 全 称 量 词 ， 则 取 不在 母 式 中 出 现 的 常 量 替 代 母 式 中 的 所 有 xk ， 并删 除 前 束 中 的 xk消去存在量词的规则 或 前束范式化成斯柯伦的步 骤 是 ： 若 xk (1 k n )左 边 有 全 称 量 词 (xs1) (xs2)(xsr) ( 1 r， 1 s1s2srk , il )的 消 解 式消解演绎和反演的定义： 则 称 c1, , cn 是 从 子 句 集 S 到 子 句 c 的 一 个 消解 演 绎当 c= 时 的 消 解 演 绎 称 为 （ 消 解 ） 反 演 把 谓 词 公 式 转 化 为 子 句 集 S（ 所 有 子

8、句 的 变 量 名 不同 ） 如 空 子 句 成 为 子 句 集 的 子 句 ， 则 算 法 结 束 在 子 句 集 中 选 取 两 个 不 同 的 可 以 消 解 的 子 句 ci , cj注 ： 子 句 的 个 数 限 制反演的基本算法： 计 算 ci , cj 的 消 解 式 rij 把 rij 加 到 子 句 集 中 ， 形 成 新 的 子 句 集 S 转 到 反演的流程图将 谓 词 公 式 化 成 子 句 集有 空 子 句 ？ 成 功 结 束取 两 个 子 句有 消 解 式 ？ 无 解 结 束将 消 解 式送 到 子 句集 有 无 例 1： 设 子 句 集 为 S= P Q, P Q

9、, P Q, P Q求 S的 一 个 反 演 S的 一 个 反 演 为 ： P Q (S) P Q (S) P Q (S) P Q (S) Q Q P P S的 另 一 个 反 演 为 ： 例 2： 设 S= P(z1,a) P(z1,x1) P(x1,z1), P(z2,f(z2) P(a, z2), P(f(z3),z3) P(a, z3) 求 S的 一 个 反 演 P(z1,a) P(z1,x1) P(x1,z1) （ S） P(z2,f(z2) P(a ,z2) （ S） P(f(z3),z3) P(a ,z3) （ S） S的 一 个 反 演 为 ： 取 c1= ， c1= P(z2

10、,f(z2) 取 c2= ， c2= 公式集为 ： P(z1,a), P(z1,x1), P(x1,z1), P(a,z2) 最一般的合一者为 =a/x1, a/z1, a/z2 对 应 的消解式： P(a, f(a) P(z1,a) P(z1,x1) P(x1,z1) P(z2,f(z2) P(a ,z2) 取 c1= ， c1= P(f(z3),z3) 取 c2= ， c2= 公式集为 P(z1,a), P(z1,x1), P(x1,z1), P(a, z3) 最一般的合一者为 =a/x1,a/z1,a/z3 对 应 的消解式为 ： P(f(a), a) P(z1,a) P(z1,x1)

11、P(x1,z1) P(f(z3),z3) P(a ,z3) 取 c1= ， c1= 取 c2= ， c2= P(z1,a) P(z1,x1) 公式集 P(x1,z1), P(a, f(a) 最 一 般 的 合 一 者 为 =a/x1,f(a)/z1 对 应 的消解式为 ： P(f(a),a) P(z1,a) P(z1,x1) P(x1,z1) P(a, f(a) 取 c1= ， c1= 取 c2= ， c2= 公式集: P(f(a) , a) 最一般的合一者为 = 对 应 的消解式为 ： P(f(a), a) P(f(a),a) P(z1,a) P(z1,x1) P(x1,z1) （ S） P

12、(z2,f(z2) P(a ,z2) （ S） P(f(z3),z3) P(a ,z3) （ S） P(a, f(a) ( ) P(f(a), a) ( ) P(f(a),a) ( ) ( )反演过程： 3.6.3 消 解 推 理 规 则 （ 命 题 的 特 殊 情 况 ）从 父 子 句 求 消 解 式 的 若 干 例 子1、 假 言 推 理 2、 合 并3、 重 言 式 4、 空 子 句 （ 矛 盾 ）5、 链 式 （ 三 段 论 ） ( ) ( )B y C y( )B x3.6.4 含 有 变 量 的 消 解 式 （ 谓 词 情 况 ）先 求 最 一 般 的 合 一 者 mgu， 再 求

13、 消 解 式例 1 置 换 / x y ( )C x 例 2例 3 1 消 解 反 演 （ 数 学 定 理 的 证 明 ， 论 断 是 否 成 立 ，即 反 演 ）2 反 演 求 解 过 程 （ 回 答 问 题 ， 即 消 解 演 绎 ）3.6.5 消 解 反 演 求 解 过 程 1 消 解 反 演消 解 反 演 证 明 定 理 的 思 路 非 常 类 似 于 数 学 中 的反 证 法 给 定 一 个 公 式 集 S（ 前 提 条 件 ） 和 目 标 公 式 L（ 结论 ） ， 通 过 反 演 来 求 证 目 标 公 式 L， 其 证 明 过 程为 ： 否 定 L ， 得 到 L 把 L 加

14、到 S 中 把 新 形 成 的 集 合 S ， L 化 为 子 句 集 （ 简 化 化法 ） 应 用 消 解 原 理 ， 试 图 导 出 一 个 表 示 矛 盾 的空子句 设 S F1,Fn 是 前 提 条 件 ， L是 欲 求 证 的 结 论则 ， 从 前 提 条 件 推 出 结 论 的 问 题 ， 可 以 表 示 成 ： F1 Fn L （ F1 Fn ） L 并 证 明 其永真（ 永 远 成 立 ）反 演 证 明 过 程 的 正 确 性 ： 先 将 公 式 取 “ 非 ” ： （ （ F1 Fn ） L） （ F1 Fn ） L F1 Fn L利 用 消 解 原 理 来 证 明 它 是永

15、假的 （ 即 ， 构 造 一 个反 演 ） 实 际 中 ， 我 们 可 以 将 F1 Fn L中 的 每 一 个 部 分 化 成 子 句 集 （ 化 法 任 选 ） ， 合并 后 得 到 完 整 的 子 句 集 ， 然 后 利 用 消 解 原 理 导出 空 子 句 （ 反 演 ） 设 有 公 式 集 ：F1: (x)(C(x)(W(x) R(x)F2: (x)(C(x) O(x)L: (x)(O(x) R(x)试 证 ： L是 F 1， F2的 逻 辑 结 果 ， 即 F1 F2L 例 1： 利 用 消 解 原 理 来 构 造 F1 F2 L的 一 个 反 演 首 先 分 别 求 出 F1，

16、F2和 L 的 子 句 集证 明 ： (x)(C(x)(W(x) R(x)= (x)( C(x) (W(x) R(x)= (x)( C(x) W(x) ) ( C(x) R(x) 子 句 集 = C(x) W(x) , C(x) R(x) (未 改 名 )F1的 前 束 合 取 范 式 与 子 句 集 ： (x)(C(x) O(x) = (C(a) O(a)子 句 集 = C(a), O(a) F2的 前 束 合 取 范 式 和 子 句 集 ： (x)(O(x) R(x) = (x)( O(x) R(x)子 句 集 = O(x) R(x) L 的 前 束 范 式 和 子 句 集 ： 构 成 子

17、 句 集 （注意改名） C(x) W(x), C(y) R(y), C(a)， O(a), O(z) R(z) C(x) W(x) C(y) R(y) C(a) O(a) O(z) R(z) 证明过程： R(a) ， mgu=a/y R(a) mgu=a/z C(y) R(y) C(a) O(a) O(z) R(z) 前提： 每 一 个 储 蓄 钱 的 人 都 获 得 利 息结论： 如 果 没 有 利 息 ， 那 么 就 没 有 人 去 储 蓄 钱例 2： 用 消 解 反 演 证 明 S ( x , y )： 某 人 x 储 蓄 y（ 数 量 ）M ( x )： x（ 数 量 ） 是 钱I(

18、x )： x （ 数 量 ） 是 利 息E( x , y )： 某 人 x 获 得 y （ 数 量 ）证 明 ：设 前提：每一个储蓄钱的人都获得利息结论：如果没有利息，那么就没有人去储蓄钱任 何 人 x 将 y 数 量的 钱 存 入 银 行 任 何 人 x 得 到 y 数 量 的 利 息没 有 x 数量 的 利 息 任 何 人 x 就 不 会 将 任 何数 量 y 的 钱 存 入 银 行 将 前 提 条 件 化 成 子 句 集 前 束范 式前 束 合取 范 式 前 提 条 件 的子句集(1) ( , ) ( ) ( ( )S x y M y I f x (2) ( , ) ( ) ( , (

19、)S u v M v E u f u 结 论 取 非 ：化 成 子 句 集 改 名 、 消 除 “ 结 论 非 ” 的 子 句 集(3) ( )I z(4) ( , )S a b(5) ( )M b 完整的子句集(1) ( , ) ( ) ( ( )S x y M y I f x (2) ( , ) ( ) ( , ( )S u v M v E u f u (3) ( )I z(4) ( , )S a b(5) ( )M b 反 演 过 程 ( )(6) ( , ) ( ) (1)(3) f x zS x y M y mgu (7) ( ) (6)(4) ,a bx yM b mgu (8)

20、(5)(7) mgu (1) ( , ) ( ) ( ( )S x y M y I f x (2) ( , ) ( ) ( , ( )S u v M v E u f u (3) ( )I z(4) ( , )S a b(5) ( )M b 储 蓄 问 题 的 反 演 树 （ 简 单 情 况 下 使 用 ） 2 反演求解过程从 反 演 树 求 取 某 一 个 问 题 的 答 案 ， 其 过 程 为 ： 将 前 提 条 件 用 谓 词 表 示 出 来 ， 并 化 成 子 句 集 S 将 目 标 公 式 （ 问 题 ） 用 谓 词 表 示 出 来 ，把由目标公式的否定所产生的子句及 其非（ 目 标

21、公式 否 定 之 否 定 ） 用析取连接词相 连 组 成 一 个新子句（ 重 言 式 ） ， 加 到 S 构 成 新 的 子 句 集 S 对 子 句 集 S ， 进 行消解演绎， 直 到 得 到 某 一个子句为 止 将 此 子 句 作 为问题的答案 例 ： 已 知 三 个 前 提 条 件F1:： 王 (Wang)先 生 是 小 李 (Li)的 老 师F2： 小 李 与 小 张 (Zhang)是 同 班 同 学F3： 如 果 x与 y是 同 班 同 学 ， 则 x的 老 师 就 是 y的 老 师问 题 ： 小 张 的 老 师 是 谁 ？ 解 ：定义谓词T(x , y) : x 是 y 的 老 师

22、C(x , y) : x 与 y 是 同 班 同 学 前提：F1： T(Wang , Li)F2： C(Li , Zhang)F3： (x) (y) (z) (C(x,y) T(z,x) T(z,y)目标：G： (x)T(x,Zhang) G： (x)T(x,Zhang)=(x) ( T(x,Zhang)用 谓 词 表 示 前 提 条 件 与 目 标 （ 问 题 ） ： 前 提 的 子 句 集 ：(1) T(Wang, Li)(2) C(Li, Zhang)(3) C(x,y) T(z,x) T(z,y)目标的否定的子句及其非组 成 重 言 式 ：(4) T(x,Zhang) T(x,Zhan

23、g) 完 整 的 子 句 集 ：(1) T(Wang, Li)(2) C(Li, Zhang)(3) C(x,y) T(z,x) T(z,y)(4) T(u,Zhang) T(u,Zhang) (1) T(Wang, Li)(2) C(Li, Zhang)(3) C(x,y) T(z,x) T(z,y)(4) T(u,Zhang) T(u,Zhang)(5) C(Li ,y) T(Wang,y) (1)(3) mgu=Wang/z, Li/x)消解演绎过程 (6) C(Li ,Zhang) T(Wang, Zhang) (4)(5) mgu=Wang/u, Zhang/y(7) T(Wang,

24、 Zhang) (6)(2) 问 题 的 答 案 (4) T(u,Zhang) T(u,Zhang)(5) C(Li ,y) T(Wang,y)(2) C(Li, Zhang)mgu= 例： 如 果 无 论 约 翰 (John)去 哪 里 ， 菲 多 (Fido)也 就 去 哪 里 ， 那 么 如 果 约 翰 在 学 校 里 ， 则 菲 多在 哪 里 ？ 解 ：定 义 谓 词 AT(x , y)： 人 x 在 y 处 前 提 条 件 （ F1、 F2） 与 目 标 （ G） 为 ：前 提 条 件 的 子 句 集 ： 目标的 “ 非 ” 及 其 子句将 目 标 的 否 定 的 子 句 及 其 非

25、 构 成重言式： 子 句 集 ：(1) AT(JOHN, ) AT(FIDO, )(2) AT(JOHN, SCHOOL)(3) AT(FIDO, ) AT(FIDO, )y yx x (4) AT(JOHN, ) AT(FIDO, ) (3)(1) mgu=x / yx x(2) AT(JOHN, SCHOOL)(3) AT(FIDO, ) AT(FIDO, )x x(1) AT(JOHN, ) AT(FIDO, )y y消 解 过 程(5) AT(FIDO, SCHOOL) (4)(2) mgu=SCHOOL/ x (1) AT(JOHN, ) AT(FIDO, )y y (3) AT(F

26、IDO, ) AT(FIDO, )x x(4) AT(JOHN, ) AT(FIDO, ) x x mgu= / x y(2) AT(JOHN, SCHOOL)(5) AT(FIDO, SCHOOL)mgu=SCHOOL/ x反 演 树 3.6.6 Horn子 句 集 消 解 Horn子 句 集 是 一 阶 谓 词 公 式 的 真 子 集 与 一 阶 谓 词 逻 辑 具 有 同 样 的 表 达 能 力 Horn子句集的特点： 如 果 对 于 谓 词 公 式 的 任 意 一 组 指 派 （ 具 体 的 一组 值 ） ， 公 式 的 值 均 为 真 ， 则 称 为永真公式 ( x) ( ) ( )

27、 ( )P PP x y P y 如 果 对 于 谓 词 公 式 的 任 意 一 组 指 派 ， 公 式 的 值 均 为 假 ， 则 称 为不可满足（永假） 公 式 ，相 应 地 称 公 式 的 子 句 集 是不可满足的 ( x) ( ) ( ) ( )P PP x y P y 如 果 至 少 存 在 一 组 指 派 ， 使 公 式 为 真 ， 则 称 为可满足公式 一 个 非 Horn 子 句 集 S 可 以 通 过 变 换 化 成为 Horn 子 句 集 S， 两 者 在上 等 价 原子公式： 原 子 命 题 （ 0元 谓 词 ） 和 谓 词基本式： 原 子 公 式 或 原 子 公 式 的

28、 非 我们再将基本式细分：正基本式： 不 带 “ 非 号 ” 的 原 子 公 式负基本式： 带 “ 非 号 ” 的 原 子 公 式 ： 最 多 只 含 有 一 个 正 基 本 式 的 子 句 （）： 每 一 个 子 句 均 为 Horn子 句 的 子 句 集Horn子 句 及 Horn子 句 集 的 定 义 ： 例： 设 Pi 和 Qi 是 正 基 本 式 ， 有 谓 词 公 式 ：(P1 Pk)(Q1 Q2)=( P1 Pk) (Q1 Q2)=( P1 Pk Q1) ( P1 Pk Q2)子句集S： P 1 Pk Q1, P1 Pk Q2是 Horn子 句 集 消 解 原 理 部 分 的 书 面 作 业1、 求 公 式 集W=P(f(x),y), P(f(y),a)的 最 一 般 的 合 一 者 （ 一 致 置 换 ） 2化 成 子 句 集 ( x)P(x) ( y)P(y)P(f(x,y) ( y)Q(x,y)P(y) 3、 设 子 句 集 为 ：S= P(x) Q(x), P(f(a), Q(f(z)请 求 出 它 的 一 个 反 演 4、 设 前 提 条 件 为 F1: ( x)P(x)( y)Q(y) L(x,y) F2: ( x)P(x) ( y)R(y)L(x,y)试 用 消 解 原 理 证 明 下 列 结 论 成 立 ： G: ( x)R(x) Q(x)