知识的一阶谓词逻辑表示法.ppt

人工智能中的谓词演算及应用 人工智能中的谓词演算及应用 1学习目标 了解一阶谓词演算的基本体系 掌握命题逻辑和谓词逻辑的归结方法 以及基于归结的提取问题回答的方法 掌握基于规则的正向演绎方法和逆向演绎方法 2学习指南 本章内容是在一阶谓词逻辑的基础上介绍有关的方法 假定读者已经学习过一阶谓词逻辑的有关内容 在学习的同时 自己尝试重新做一遍例题 将有助于你的学习 在有条件的情况下 可以尝试用程序实现本章介绍的一些主要方法 不过有一定的难度 人工智能中的谓词演算及应用 3难重点 命题逻辑的归结方法 谓词逻辑的归结方法 基于归结的问题回答方法 基于规则的正向演绎方法和基于规则的逆向演绎方法 4 1一阶谓词逻辑基本理论 一 命题与联结词定义4 1具有确定真值的陈述句 称为命题 命题若是简单的陈述句 不能分解成更简单的句子 我们称这样的命题为简单命题或原子命题 可以用英文字母P Q R 或是带有下标的大写英文字母Pi等表示简单命题 将命题用合适的符号表示 称为命题符号化 对于简单命题来说 它的真值是确定的 因而又称为命题常项或命题常元 真值可以变化的简单陈述句称为命题变项或命题变元 2 联结词 1 否定 联结词 当命题P为真时 则 P为假 反之为真 2 析取 联结词 它表示两个命题存在 或 的关系 3 合取 联结词 它表示两个命题之间具有 与 关系 4 蕴含 单条件 P Q表示 如果P 则Q 其中P为前件 Q为后件 5 等价 双条件 PQ表示 P当且仅当Q 4 1一阶谓词逻辑基本理论 续 4 1一阶谓词逻辑基本理论 续 二 个体词与谓词1 个体词定义4 2个体 个体词 是指所研究对象中可以独立存在的具体事物 状态或个体之间的关系 在谓词逻辑中 个体可以是常量也可以是变量 变元 个体常量 表示具体的或特定的个体 用a b c d表示 个体变量 表示抽象的或泛指的个体 用x y z表示 个体域 论域 个体变量的 取值范围 值域 常用D表示 个体域可以是有限的也可以是无限的 4 1一阶谓词逻辑基本理论 续 2 谓词定义4 3用于刻画个体的性质 状态或个体之间的关系 称为谓词 谓词一般也用P Q R等大写字母表示 3 函数符号函数符号 又称函词 是从若干个思维对象到某个思维对象的映射的符号 n元函数f x1 x2 xn 规定为一个映射 f Dn D 4 1一阶谓词逻辑基本理论 续 谓词与函数的区别 1 谓词的真值是真和假 而函数无真值可言 其值是个体域中的某个个体 2 谓词实现的是从个体域中的个体到T或F的映射 而函数实现的是同一个个体域中从一个个体到另一个个体的映射 3 在谓词逻辑中 函数本身不能单独使用 它必须嵌入到谓词中 4 1一阶谓词逻辑基本理论 续 4 谓词 谓词填式 定义4 4将表示谓词的符号和表示个体的符号组合成一个函词 就称谓词填式 简称谓词 如果没有特殊说明 以后我们提到的谓词均指谓词填式 与命题逻辑相似 谓词逻辑中也有谓词常项和谓词变项之分 含有个体变元的谓词没有真值 但当谓词中的变元都用指定的个体取代时 谓词就有了特定的值T或F 4 1一阶谓词逻辑基本理论 续 n元谓词 含有n个个体符号的谓词P x1 x2 xn 它表示一个映射 P Dn T F 或是 D1 D2 Dn T F 谓词的语义是由使用者根据需要人为定义的 谓词中包含的个体数目称为谓词的元数 如 Q x 是一元谓词 P x a 是二元谓词 A x1 x2 xn 是n元谓词 若X是个体常元 变元或函数 谓词称为一阶谓词 如果某个X本身又是一个一阶谓词 则谓词称为二阶谓词 依次类推 与谓词联系着的n个个体的出现顺序不是任意的 同一谓词的个体变元取值于不同个体域时 所得命题真假值可以不同 4 1一阶谓词逻辑基本理论 续 三 量词设谓词P x 表示x是正数 F x y 表示x与y是好朋友 则 x P x 表示个体域中所有个体x都是正数 x y F x y 表示在个体域中所有个体x 都存在个体y x与y是好朋友 4 1一阶谓词逻辑基本理论 续 四 谓词公式项 单独一个个体符号 包括常量和变量 是项 若t1 tn是项 则f t1 tn 是项 所有项由上述两规则生成 原子公式 若t1 tn是项 P是n元谓词符号 则单独一个谓词P t1 tn 称为原子谓词公式 n 0时退化为原子命题公式 简称原子 4 1一阶谓词逻辑基本理论 续 定义4 5下述规则得到谓词演算的合式公式 1 单个谓词是合式公式 称为原子谓词公式 2 若A是谓词公式 则A也是合式公式 3 若A B都是合式公式 则A B A B A B AB也都是合式公式 4 若A是合式公式 x是任一个体变元 则 x A x A也都是合式公式 4 1一阶谓词逻辑基本理论 续 2 公式的解释在命题逻辑中 对命题公式中各个命题变元的一次真值指派称为命题公式的一个解释 一旦解释确定 根据各联结词的定义就可求出命题公式中真值 T或F 定义4 6解释I有四个要素 1 给出非空论域D 2 对公式G 对每个常量指派D中的一个元素 3 对公式G 对每个n元谓词指派一个Dn T F 的映射 4 对公式G 对每个n元函数指派一个Dn D的映射 4 1一阶谓词逻辑基本理论 续 5谓词公式的永真性与可满足性定义4 7如果谓词公式P对于个体域上的任何一个解释都取得真值 则称P在D上是永真的 换句话说 P在每一个非空个体域上均永真 则称P永真 定义4 8对于谓词公式P 在个体域D中 至少存在一个解释使得公式P在此解释下真值为T 则公式P是可满足的或相容的 定义4 9如果谓词公式P对个体域D上任何一个解释都取得真值F 则称P在D上永假的 又称为不可满足性或不相容性的 4 1一阶谓词逻辑基本理论 续 定义4 10若公式G在解释I下为T 即取值为真 则称解释I满足公式G 或称解释I是G的一个模型 对于公式集 可以看成是其中的每个公式G的合取 即 G1 G2 Gn 若G1 G2 Gn皆为真 则其合取亦为真 故定义在公式G上的定义都可推广到公式集 也是适用的 4 1一阶谓词逻辑基本理论 续 6谓词公式的等价性与永真蕴含性推理规则 1 P规则 在推理的任何步骤上都可以引入前提 2 T规则 推理时 如果前面步骤中有一个或多个公式永真蕴含公式S 则可以把S引入推理过程中 3 CP规则 如果能从R和前提集合中推出S来 则可以从前提集合推出R S来 4 反证法 PQ 当且仅当 P QF 即Q为P的逻辑结论 当且仅当P Q是不可满足的 定理4 1 为P1 P2 Pn的逻辑结论 当且仅当 P1 P2 P3 Pn 是不可满足的 4 1一阶谓词逻辑基本理论 续 定义1 谓词公式X是谓词公式A的一部分 则称X为A的子公式 若子公式为 X P X 或 X P X 则称X为指导变元 P X 为相应量词的作用域或辖域 在辖域中X的所有出现称为X在公式A中的约束出现 即X为相应量词的指导变元所约束 A中不是约束出现的其它变元称为自由变元 定义2 设X是谓词合式公式A的一个个体变元 若以y代替x后不产生变元的新的约束出现 则称A X 关于y是自由的 4 1一阶谓词逻辑基本理论 续 定理1 设X是谓词公式A的一个个体变元 A的论域为D A x 关于y是自由的 则 x P x P y 特例 x P x P X 上述公式称为全称固化 定理2 设X是谓词公式A的一个个体变元 A的论域为D A x 关于y是自由的 则 x P x P y 其中y是个体域中某一个可使P y 为真的个体 4 1一阶谓词逻辑基本理论 续 6谓词公式的等价性与永真蕴含性定义4 11设P与Q是两个谓词公式 D是它们共同的个体域 若对于D上的任何解释 P和Q都有相同的真值 则称P与Q在个体域D上是等价的 如果D是任意个体域 则称P和Q是等价的 记作PQ 定义4 12对于谓词公式P和Q 如果P Q永真 则称P永真蕴含Q 且称Q为P的逻辑结论 称P为Q的前提 记作PQ 4 1一阶谓词逻辑基本理论 续 例 证明 P Q R R P S P T 4 1一阶谓词逻辑基本理论 续 7谓词公式的范式 1 前束范式定义4 13设F为一谓词公式 如果其中的所有量词均非否定地出现在公式的最前面 且它们的辖域为整个公式 则称F为前述范式 一般地 前束范式可写成 Q1x1 Qnxn M x1 xn 其中 Qi i 1 2 n 为前缀 它是一个由全称量词或存在量词组成的量词串 M x1 xn 为母式 它是一个不含任何量词的谓词公式 4 1一阶谓词逻辑基本理论 续 2 Skolem范式定义4 14如果前束范式中所有的存在量词都在全称量词之前 则称这种形式的谓词公式为Skolem范式 求该范式方法 把公式变换成等价的前束范式 把不含量词的母式变换成等价的合取范式 消去所有存在量词 若不受全称量词约束 用母式中没有的常量符号代换 若受全称量词约束 用母式中没有的函数来代换 4 1一阶谓词逻辑基本理论 续 3 范式的求解对任一合式公式可通过以下步骤化成前束范式 1 消去多余的前束 量词 这在化简过程都要随时注意到 因为可能出现母式中没有其前束中相对应的约束变元 因而这个前束是多余的 应及时消去 2 消去蕴涵符号 联结词 反复使用具有 联结词的等值公式 把公式中所有的 都消去 3 内移否定词 的辖域范围 反复使用摩根定律和量词互换式 把否定词标到只作用于原子公式为止 4 变量标准化 对变量作必要的换名 使每一量词只约束一个唯一的变量名 由于变量名可任意设定 因而该过程不影响合式公式的真值 5 把所有量词都集中到公式左面 移动时不要改变其相对顺序 4 1一阶谓词逻辑基本理论 续 置换 substitution 一个有序对的集合s ti vi i 1 2 n 称为代换 其中vi i 1 2 n 是互不相同的变量 ti i 1 2 n 是不同于vi的项 可以是常量 函数 或者其他的变量 当ti都是基项时 代换称为基代换 不含任何元素的代换称为空代换 它是一个空集 记作 置换s表示将公式 表达式 中的所有变量vi用项ti代替 对公式E施以置换s 记作Es Es称作公式E的代换实例 一个公式的任何代换实例都是原公式的逻辑结论 例 设有置换s z x a y 则 P x f y b s P z f a b 这里x被换成了z y被换成了a 定义 设 t1 x1 t2 x2 tn xn u1 y1 u2 y2 um ym 是两个代换 与 的复合代换 记作 是由下列集合 t1 x1 t2 x2 tn xn u1 y1 u2 y2 um ym 删除所有满足ti xi的元素以及所有yi出现在 x1 x2 xn 中的元素得到的集合 例 设 f y x z y a x b y y z 复合代换一般不满足交换律 合一 Unify 设有公式的集合 Ei i 1 2 m 如果存在一个置换s 使得这m个公式被施以s以后 变得完全一样了 则称这m个公式是可合一的 置换s是它们的合一者 例 设有公式集 P x f y b P z f b b 和置换s1 a x b y a z 由于 P x f y b s P a f b b P z f b b s P a f b b 所以公式集 P x f y b P z f b b 是可合一的 置换s1 a x b y a z 是它们的合一者 最一般合一者 mgu 一般来说 一个公式集的合一者不是唯一的 如s2 z x b y 和s3 x z b y 都是公式集 P x f y b P z f b b 的合一者 对于一个公式集来说 如果存在几个合一者 则其中置换数最少 限制最少 产生的例最具一般性的置换称为最一般合一者 mgu 如在上例中 置换s1 a x b y a z 产生的例为P a f b b 置换s2 z x b y 产生的例为P z f b b 对于置换s1 置换数为3 而置换s2的置换数为2 相对于例P a f b b 来说 例P z f b b 含有一个变量 因此更具一般性 实际上置换s2就是上例公式集的最一般合一者 即mgu 置换s3 x z b y 也是该公式集的mgu 可见mgu也同样不是唯一的 一致化算法 定义 设E E1 E2 Ek 是非空表达式的集合 从E中的各表达式的第一个符号起同时向右比较 直至发现第一个彼此不尽相同的符号止 再从各表达式的这一符号开始 取出相应表达式的最大子表达式 以这些不尽相同的最大子表达式为元素组成的集合称为E的分歧集 例 计算E P x f y z P x f g a h b 的分歧集 一致化算法 设E是需要一致化的表达式集合 W是用来记录E或E的代换实例集 D用来记录W的分歧集 用来记录代换 1 置W E 2 若W中只有一个表达式 则算法终止 就是E的最广通代 否则求出W的分歧集D 3 若D中存在两个元素v和t 其中v是变量 t是项且t中不出现v 则转第4步 否则算法终止 E的通代不存在 即不可一致化 4 置 t v 置W W t v 转第2步 4 2确定性推理 推理是指按照某种策略从已知事实出发去推出结论的过程 推理所用的事实可分为两种情况 一种是与求解问题有关的初始证据 另一种是推理过程中所得到的中间结论 通常 智能系统的推理过程是通过推理机来完成的 所谓推理机就是智能系统中用来实现推理的那些程序 二推理方法及分类1 按推理的逻辑基础分类 1 演绎推理演绎推理是从已知的一般性知识出发 去推出蕴含在这些已知知识中的适合于某种个别情况的结论 它是一种由一般到个别的推理方法 其核心是三段论 即假言推理 拒取式和假言三段论 4 2确定性推理 续 常用的三段论是由一个大前提 一个小前提和一个结论三部分组成的 其中 大前提是已知的一般性知识或推理过程得到的判断 小前提是关于某种具体情况或某个具体实例的判断 结论是由大前提推出的 并且适合于小前提的判断 4 2确定性推理 续 2 归纳推理归纳推理是从一类事物的大量特殊事例出发 去推出该类事物的一般性结论 它是一种由个别到一般的推理方法 归纳推理的基本思想是 先从已知事实中猜测出一个结论 然后对这个结论的正确性加以证明确认 数学归纳法就是归纳推理的一种典型例子 对于归纳推理 如果按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理 如果按照推理所使用的方法可分为枚举归纳推理 类比归纳推理 统计归纳推理和差异归纳推理等 4 2确定性推理 续 所谓完全归纳推理是指在进行归纳时需要考察相应事物的全部对象 并根据这些对象是否都具有某种属性 来推出该类事物是否具有此属性 所谓不完全归纳推理是指在进行归纳时只考察了相应事物的部分对象 就得出了关于该事物的结论 所谓枚举归纳推理是指在进行归纳时 如果已知某类事物的有限可数个具体事物都具有某种属性 则可推出该类事物都具有此种属性 所谓类比推理是指在两个或两类事物有许多属性都相同或相似的基础上 其它属性上也相同或相似的一种归纳推理 4 2确定性推理 续 3 默认推理默认推理是在知识不完全的情况下假设某些条件已经具备所进行的推理 因此也称为缺省推理 在推理过程中 如果发现原先的假设不正确 就撤销原来的假设以及由此假设所推出的所有结论 重新按新情况进行推理 4 2确定性推理 续 4 演绎推理与归纳推理的区别演绎推理与归纳推理是两种完全不同的推理 演绎推理是在已知领城内的一般性知识的前提下 通过演绎求解一个具体问题或来证明一个结论的正确性 它所得出的结论实际上早已蕴含在一般性知识的前提中 演绎推理只不过是将已有事实揭示出来 因此它不能增殖新知识 在归纳推理中 所推出的结论是没有包含在前提内容中的 这种由个别事物或现象推出一般性知识的过程 是增殖新知识的过程 4 2确定性推理 续 2 按所用知识的确定性分类按所用知识的确定性 推理可分为确定性推理和不确定性推理 所谓确定性推理是指推理所使用的知识和推出的结论都是可以精确表示的 其真值要么为真 要么为假 不会有第三种情况出现 所谓不确定性推理是指推理时所用的知识不都是确定的 推出的结论也不完全是确定的 其真值会位于真与假之间 4 2确定性推理 续 三 推理的控制策略及分类推理的控制策略又可分为推理策略和搜索策略 其中 推理策略主要解决推理方向 冲突消解等问题 搜索策略主要解决推理线路 推理效果 推理效率等问题 4 2确定性推理 续 四 推理的冲突消解策略在推理的某一步 如果知识库中有多条知识可用 则称发生了冲突 此时 需要按照某种策略从这多条知识中选择一条最佳知识用于推理 称这种解决冲突的过程为冲突消解 冲突消解所用的策略则称为冲突消解策略 4 2确定性推理 续 常用的冲突消解策略有以下 1 特殊知识优先2 新鲜知识优先3 差异性大的知识优先4 领域特点优先5 上下文关系优先6 前提条件少者优先 4 2确定性推理 续 4 3自然演绎推理 从一组已知为真的事实出发 直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理 在这种推理中 最基本的推理规则是三段论推理 它包括假言推理 拒取式推理 假言三段论等 例 设已知下述事实和规则ABA CB C DD Q求证 Q为真 4 3自然演绎推理 例 设已知如下事实 1 凡是容易的课程小王 wang 都喜欢2 C班的课程都是容易的3 ds是C班的一门课程证明 小王喜欢ds这门课程 4 3自然演绎推理 续 4 4归结演绎推理 归结演绎推理是一种基于鲁宾逊 Robinson 归结原理的机器推理技术 鲁宾逊归结原理亦称为消解原理 是鲁宾逊于1965年在海伯伦 Herbrand 理论的基础上提出的一种基于逻辑的 反证法 1 子句定义4 15单个谓词公式或其否定式称为原子谓词公式 如A x A x 等 定义4 16在谓词逻辑中把原子谓词公式及其否定式统称为文字 原子称正文字 原子之非称负文字 定义4 17任何文字的析取式称为子句 如B x K x P x f x Q x g x 等 一文字子句称为单位子句 定义4 18不包括任何文字的子句称为空子句 因为空子句不含有文字 它不能被任何解释满足 所以空子句永假的 是不可满足的 空子句一般被记为 或NIL 定义4 19由子句或空子句所构成的集合称为子句集 它表示由集合中的子句的合取构成的范式 空子句集永真 4 4归结演绎推理 续 化子句集的方法 利用等价关系消去谓词公式中的 利用等价关系把 移到紧靠谓词的位置上 重新命名变元名 使不同量词约束的变元有不同的名字 把量词全部移到公式的左边 利用等价关系把公式化成斯格林标准形 消去存在量词 隐去全称量词 对变元更名 使不同子句中的变元不同名 消去合取词 判断子句集的不可满足性 需对个体域上的一切解释逐个地进行判断 任何一个解释都是不可满足时 才能判定该子句是不可满足的 这在实际中难以实现 如果实际中选取个体中域的某一有限部分 在此个体域中处处不可满足 则认为子句集处处不可满足成立 则就简单多了 海伯伦构造了一个特殊的域 并证明只要对这个特殊的域上的一切解释进行判定 就可知子集是否不可满足 这个特殊的域就是海伯伦域 4 4归结演绎推理 续 海伯伦理论 海伯伦全域基表达式基例H基H解释海伯伦定理语义树海伯伦定理及其实现 海伯伦全域H S 海伯伦域是一个论域的子集 在此特殊域上讨论子句集的不可满足性与在所有论域上讨论具有相同的效果 由以下方法构造而成 例 例1求子句集的海伯伦域 例2求子句集的海伯伦域 例3求子句集的海伯伦域 定义4 22如果用H域中的元素代换子句中的变元 则所得的子句称为基子句 其中的谓词称为基原子 由基子句构成的集合称为基子句集S 另一种讲法 设S是子句集 子句C S 用H S 中的元素代替C中的变元而得到的基子句称为子句C的一个基例 也可以说成S的一个基例 定义4 23子句集中所有基原子构成的集合称为基原子集 基例 用H S 中的元素代换子句中的变元而得到的基子句称为原子句的一个基例 海伯伦基 H基 记B S 由S的谓词符号和H域中的基项组成的全体基原子的集合 B S P t1 tn P是 中出现的谓词符号 t1 tn属于 例 设S P x Q y f y a 求S的海伯伦全域H S H基B S 和第一个子句的基例 依定义有 H0 a H1 a f a a H S a f a a f a f a a f f a a a f f a a f a a B S P a Q a a P f a a Q a f a a Q f a a a Q f a a f a a 第一个子句的基例有 P a P f a a P f a f a a P f f a a a P f f a a f a a 解释 在海伯伦全域 上 对子句集 中出现的常量 函数和谓词符号按下述方法进行赋值 对每个常量指派常量本身 对每个n元函数指派一个从 n到 的映射 对每个n元谓词指派一个从 n到真值 的映射 对谓词的所有指派等同于对B S 的每个基原子指派一个真值 则一个H 解释I 可以表示成I P u1 um Q v1 vm P u1 um B S Q v1 vm B S 且P u1 um 在该H 解释下取T Q v1 vm 在该H 解释下取F 引理 若存在某一论域D上的解释I满足子句集S 则一定存在一个H 解释I 也满足S 证明 对S在D上的任一解释I 都可以找到与之对应的一个H 解释I I P u1 um Q v1 vm P u1 um B S Q v1 vm B S 且P u1 um 在该H 解释下取T Q v1 vm 在该H 解释下取F 因为在D上的解释I满足S 即S取真值T 所以在H 解释I 下S也取T 即I 满足S 得证 定理 子句集S是不可满足的 当且仅当S在海伯伦全域H的所有解释下都取真值F 证明 必要性 设子句集S是不可满足的 由定义 所有论域上的所有解释都不能满足S 所以S在H域的所有解释下都取值F 充分性 若在某个论域D上的解释I满足子句集S 则由引理 一定存在I所对应H 解释I 也满足S 即S取值T 得证 语义树 定义 设B s 是子句集S的H基 S的一棵语义树是一棵向下倒长的二叉树 每一非终结点向下生长的两条边上分别附着B s 中的某个基原子和该基原子之非 但从根结点到任一结点的路径上不存在这样的互补对 语义树是一棵完全语义树 当且仅当从根节点至每一终结点的路径上出现B s 中每一个基原子所对应的正文字或负文字 基原子代表 真 基原子之非代表 假 每一分支都代表了一个 解释 定义 子句集S的语义树中 若节点N对应的部分解释使S的某个子句的某个基例为假 而对N的前辈节点不能 则称N为失败节点 若语义树的每一条分支的终点都是失败节点 则称该语义树为封闭语义树 海伯伦定理 型 一个子句集S是不可满足的 当且仅当从 的完全语义树中能导出一棵有限的封闭语义树 证明 必要性 若S是不可满足的 则对任一H 解释存在S的某个字句的基例取假 因S的完全语义树的每一条分支相当于S的一个H 解释 且基例是由析取关系的基文字组成的有限集合 所以每一分支比存在失败结点 也就是从S的完全语义树必能导出一棵有限的封闭语义树 充分性 若能导出有限的封闭语义树 则每一条分支上都有使S的某个子句基例取假的失败结点 也就是任一H 解释都不能满足S 所以S是不可满足的 得证 II型 一个子句集S是不可满足的 当且仅当存在 的有限基例集是不可满足的 证明必要性 若子句集S是不可满足的 由定理I型 一定存在封闭语义树 由其所有失败结点所对应的S子句的基例构成的集合是有限的 而且是不可满足的 充分性 设子句集S有一个不可满足的基例集S 因为S的每一个H 解释I1总包含S 的某个H 解释I2 而I2不满足S 所以I1也不满足S S 是S的基例集 故I1一定不满足S 即S不可满足 得证 海伯伦定理的实现方法 1 重言式规则 从S中删除所有含有互补文字的子句 称为重言式 得到的子句集S 不可满足 当且仅当S不可满足 2 单文字规则若S中含有单位基子句L 则从S中删除包含L的所有基子句 若得到的子句集S 为空 则S是可满足的 否则 再从S 的子句中删除L而得到基子句集S 若S 不可满足 当且仅当S不可满足 3 纯文字规则基子句集S中的一个文字L称为纯文字 当且仅当文字L不出现在S中 从S中删除所有包含纯文字的基子句而得到子句集S S 不可满足当且仅当S不可满足 4 分裂规则 例 证明S P a Q a P f a Q a P f a 是不可满足的 对P a 使用纯文字规则 得S1 Q a P f a Q a P f a 对Q a 使用单文字规则 得S2 P f a P f a 对P f a 使用单文字规则 得S3 空 这些理论是归结原理的理论依据 希望能理解 重点掌握H S B S 子句的基例的求法 归结原理 归结原理是一种定理证明方法 1965年由Robinson提出 由于该方法简单 容易在计算机上程序实现 因此一经提出 就得到了人们的广泛关注 对自动定理证明的研究起到了很大的推动作用 用归结原理证明定理有些类似于 反证法 的思想 在归结法中首先对结论求反 然后将已知条件和结论的否定合在一起用子句集表达 如果该子句集存在矛盾 则证明了结论的正确性 如何证明子句集存在矛盾呢 其思路如下 设S是已知条件和结论的否定合并后所对应的子句集 假定有一种变换方法 可以对S实施一系列的变换 而且该变换能够保证变换前后的子句集 在不可满足的意义下是等价的 这样 如果最终得到的子句集是不可满足的 就证明了子句集S是不可满足的 从而证明结论成立 命题逻辑的归结原理 例 设两个子句C1 L C1 C2 L C2 则归结式C C1 C2 当C1 C2 时 C 子句集S C1 C2 Cn 与子句集S1 C C1 C2 Cn 的不可满足性是等价的 S1中C是C1和C2的归结式 即S1是对S应用归结法后导出的子句集 命题逻辑中 若给定公理集F和命题P 则归结证明过程可归纳如下 把F转化成子句集表示 得子句集S0 把命题P的否定式 P也转化成子句集表示 并将其加到S0中 得S S0 S p 对子句集S反复应用归结推理规则 直至导出含有空子句的扩大子句集为止 即出现归结式为空子句的情况时 表明已找到了矛盾 证明过程结束 例子 设已知公理集为P 1 P Q R 2 S T Q 3 T 4 求证R 化成子句集表示后得S P P Q R S Q T Q T R 命题逻辑的归结演绎树 谓词逻辑的归结原理 对于子句C1 L1和C2 L2 如果L1与 L2可合一 且s是其合一者 则 C1 C2 s是其归结式 其中L1 L2是单文字 事实上L1 L2中有一个含有否定符 所以对另一个加上否定符后 才能判断它们是否可合一 应用归结原理求取问题答案的步骤 1 把已知前提用谓词公式表示出来 并化为子句集 2 把待求问题也用谓词公式表示出来 然后否定并与谓词ANSWER构成析取式 3 把此析取式化为子句集 并把该子句集并入到原子句集中 4 对子句集应用归结原理进行归结 5 若得到ANSWER 则答案就在ANSWER中 例 已知1 王 wang 先生是小李 Li 的老师2 小张 zhang 与小李是同班同学3 如果X与Y是同班同学 则X的老师也是Y的老师 求 小张的老师是谁 例子 已知 会朗读的人是识字的 海豚都不识字 有些海豚是很机灵的 证明 有些很机灵的东西不会朗读 首先把问题用谓词逻辑描述如下 已知 x R x L x x D x L x x D x I x 求证 x I x R x 化成子句集 由已知条件 1 得到 1 R x L x 由已知条件 2 得到 2 D y L y 由已知条件 3 得到 两个子句 3a D A 3b I A 由结论的否定得到 4 I z R z 归结反演树 补充举例 试用归结原理作下述题 1 王 Wang 喜欢 Like 所有种类的食物 Food 2 苹果 Apples 是食物 3 任何一个东西 若任何人吃了 Eat 它都不会被害死 Killed 则该东西是食物 4 李 Li 吃花生且仍然活着 Alike 5 张 Zhang 吃任何李吃的东西 求证 王喜欢花生 解 用谓表示知识 1 x Food x Like Wang x 2 Food Apples 3 x y Eat y x Alive y Food x 4 Eat Li Peanuts Alive Li 5 x Eat Li x Eat Zhang x 目标 6 Like Wang peanuts 上述知识化为子句集为 1 Food x1 Like Wang x 2 Food Apples 3 Eat y x2 Alike y Food x2 4 Eat Li Peanuts 5 Alive Li 6 Eat Li x3 Eat Zhang x3 目标取非后得 7 Like Wang peanuts 将上述子句进行归结 8 Food Peanuts 1 和 7 归结 9 Eat y Peanuts Alive y 3 和 8 归结 10 Alive Li 4 和 9 归结 11 nil 5 和 10 归结由上归结出空子句可知 命题成立 例2 用归结原理作下述题某村农民张某被害 有四个嫌疑犯A B C D 公安局派出五个侦察员 他们的侦察结果分别是 A B之中至少有一人作案 B C中至少有一人作案 C D中至少有一人作案 A C中至少有一人与此案无关 B D中至少有一人与此案无关 所有侦察结果都是可靠的 求出谁是罪犯 解 设谓词C D 表示D为罪犯对于第一个侦察员 C A C B 1 对于第一个侦察员 C B C C 2 对于第一个侦察员 C C C D 3 对于第一个侦察员 C A C C 4 对于第一个侦察员 C B C D 5 结论 C U ANSWER U 6 1 与 4 归结 C B C C 7 2 与 7 归结 C B 8 6 与 8 归结 ANSWER B B是罪犯 3 与 5 归结 C C C B 7 2 与 7 归结 C C 8 6 与 8 归结 ANSWER C C是罪犯所以B C是罪犯 搜索策略 归结方法很简单 但是即便是对于一个比较简单的问题 往往可以进行归结的子句也比较多 如何从众多的可归结的子句中选择两个子句 即为搜索策略问题 不同的搜索策略 会影响到系统的效率和开销 同时也会涉及到完备性问题 当给定的问题在已知条件下成立时 如果某种归结策略一定可以在有限步内证明问题是成立的 则该策略是完备的 否则则是不完备的 这里介绍的是几种在归结过程中常用的搜索策略 这些策略中有些是完备的 有些是非完备的 应该注意每种策略的完备性 在系统实现时 我们当然希望选择完备的搜索策略 但一些非完备的搜索策略往往具有较高的求解效率 因此也有使用的必要性 搜索策略 1 宽度优先策略 2 支持集策略 3 单元子句优先策略 4 线性输入形策略 5 祖先过滤形策略 1 宽度优先策略 宽度优先策略首先归结出基本集S中可能生成的所有归结式 称第一级归结式 然后生成第二级归结式等等 直到出现空子句 宽度优先策略是完备的 但效率低 2 支持集策略 支持集策略是指在每一次归结时 其母子句中 至少有一个是与目标公式否定式有关的子句 即目标公式否定式本身或与该否定式有关的后裔 可以证明支持集策略是完备的 即当矛盾存在时 一定能找到由支持集策略产生的一棵反演树 也可以把支持集策略看成是在宽度优先策略中引进某种约束条件 它代表一种启发信息 因而有较高的效率 3 单元子句优先策略 这种策略是支持集策略的进一步改进 每次归结时优先选取单文字的子句 称单元子句 为母子句进行归结 显然归结式的文字数会比其他情况归结的结果要少 这有利于向空子句的方向搜索 实际上会提高效率 4 线性输入形策略 这种策略每次归结时 至少有一个母子句是从基本集中挑选 该策略可限制生成归结式的数目 具有简单和效率高的优点 但它不是一个完备的策略 5 祖先过滤形策略 祖先过滤形策略在每次归结时 有一个母子句或者是从基本集中挑选 或者是从另一个母子句的先辈子句中挑选 这和线性输入形策略有点相似 但比它降低了挑选的限制 可以证明这种策略也是完备的 基于归结法的问答系统 通过前面的介绍 我们已经知道 当一个结论成立时 归结法可以证明该结论成立 对于一个类似于这样的结论 x W x 证明 x W x 成立固然重要 但有时我们可能更关心的是使得W x 成立的那个x是什么 也就是说 我们希望得到问题的答案 基于归结的问答就是利用归结方法获得问题答案的方法 基本方法是先用归结法证明问题的正确性 给出归结树 然后再根据该归结树构造一个修改证明树 构造的方法是 将结论的否定对应的子句S1 再次求反得到一个新子句S2 用S1与S2构造一个重言式S1 S2 用该重言式代替归结树中的子句S1 并参予有关的置换 最后在归结树得到空子句的地方得到的子句就是问题的回答 基于归结法的问答系统 例 IfFidogoeswhereverJohngoesandifJohnisatschool whereisFido 这个问题给出两个已知事实和一个询问 这个询问的答案应从事实出发演绎得到 先把问题用谓词逻辑公式表示 前提公式集 x AT John x AT Fido x AT John School 目标公式 x AT Fido x 归结树 改为修改证明树 1 用一个重言式来取代目标公式的否定式这个子句 该重言式为 AT Fido x AT Fido x 2 按反演树的构造进行归结 给出重言式替代目标否定式子句后的证明树 这时根子句不为空 称这个证明树为修改证明树 3 用根部的子句作为回答语句 修改证明树 提取回答的一般过程 1 使用某种搜索策略求出一个归结反演树 树中对合一集加一标记 2 目标公式否定式化简得到的子句中 对出现的任一Skolem函数均以新变量置换 3 根据目标公式否定式的子句 构造重言式 4 按照已找到的归结反演树的结构 将目标否定式子句用永真式替代 且每次归结合一文字集不变 生成出修改证明树 5 根部子句就作为所要提取的回答语句 猴子摘香蕉问题 初始状态的公式集表示为 ONBOX s0 AT box b s0 AT monkey a s0 HB s0 公式组 1 ONBOX S0 2 x s ONBOX s AT box x pushbox x s 3 s ONBOX climbbox s 4 s ONBOX s AT box c s HB grasp s 5 x s AT box x s AT box x climbbox s 6 s HB s 子句集 1 ONBOX S0 2 ONBOX s1 AT box x1 push x1 s1 3 ONBOX climbbox s2 4 ONBOX s3 AT box c s3 HB grasp s3 5 AT box x4 s4 AT box x4 climbbox s4 6 HB S5 归结方法小结 求子句集进行归结 方法简单通过修改证明树的方法 提取回答方法通用求解效率低 不宜引入启发信息不宜理解推理过程 基于规则的正向演绎系统 问题 归结方法不自然可能丢失包含在蕴涵形中有用的控制信息例如下面几个蕴涵式 A B C A C B B C A A B C B A C C A B都与子句 A B C 等价但显然上面的蕴涵形所带有的信息更丰富 一般情况下 表述有关问题的知识分两类 规则 由蕴涵形给出的若干语句组成 是表示某一特定领域中的一般知识 并可以当作产生式规则来使用 事实 不以蕴涵形给出 是表示该问题领域的专门知识 演绎系统就是根据这些事实和规则来证明一个目标公式 这种定理证明系统是直接法的证明系统而不是反演系统 一个直接系统不一定比反演系统更有效 但其演绎过程容易为人们所理解 这类系统主要强调使用规则进行演绎 故称为基于规则的演绎系统 解题步骤 1 事实表达式的与或形式及其表示2 应用规则对与或图作变换 把事实表达式化与或形的步骤 1 消去蕴含 等价符号 2 把否定词移到紧跟谓词的位置上 直到每个否定符号的辖域最多只含一个谓词为止 3 对所有表达式进行前束化 4 对全称量词辖域内的变元进行改名和标准化 使不同量词约束不同的名字 5 消去存在量词 6 消去全称量词 7 对变元进行 使得各主合取式之间的变元名互不相同 将规则转换成要求的形式 1 暂时消去蕴含符号 2 把否定符号移到紧跟谓词的位置上 使其作用域仅限于单个谓词 3 消去存在量词 4 化成前束范式 消去全称量词 5 恢复蕴含式表示 例 有事实表达式 u v Q v u R v P v S u v 去量词Q v A R v P v S A v 变量进行换名Q w A R v P v S A v 事实的与或树表示 其 与 和 或 的关系是刚好相反的 在与或形中的 号在与或图中表达为 或 的关系 而与或形中的 号 在与或图中表达为 与 的关系 2 应用F规则对与或图作变换 F规则的表示形式 L W 1 其中L是单文字 W是任一化成与或形的公式 2 这个蕴涵式中的所有变量都假定有全称量词的约束 3 变量已经换名 使之与事实公式或其他规则公式中的变量区别开来 例 x y z P x y z u Q x u 1 暂时消去蕴涵符号 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 恢复蕴涵式表示P x y f x y Q x u 命题逻辑的情况 例 事实 P Q R S T U 规则 S X Y Z规则化成子句为 S X Z S Y Z 原先子句集 S P Q S R T U P Q T U R 新子句集 X Z P Q X Z R Y Z P Q Y Z R T U P Q T U R 一个基于规则的正向演绎系统 其演绎过程就是不断地调用匹配上的规则对与或图进行变换 直到生成的与或图含有目标表达式为止 也就是要用目标公式作为系统的结束条件 正向系统的目标表达式要限制为文字析取形 子句形 的一类公式 当目标公式中有一个文字同与或图中某一个端节点所标记的文字匹配上时 和规则匹配时做法一样 通过匹配弧把目标文字添加到图上 这个匹配弧的后裔节点称为目标节点 这样当产生式系统演绎得到的与或图包含有目标节点的解图时 系统结束演绎 这时便推出了一个与目标有关的子句 简例说明系统的推理过程 事实表达式 A B规则集 A C DB E G目标公式 C G 谓词逻辑的情况 事实表达式化成与或形规则化成L W目标用对偶形式进行Skolem化 即 消去全称量词 对受全称量词约束的变量用Skolem函数或者常量代替省略存在量词 所有变量默认为受存在量词约束进行变量换名 使得目标公式的主析取元之间具有不同的变量名 规则每使用一次 都要进行换名 对偶形式进行Skolem化举例 例如 设目标公式为 y x P x y Q x y 用Skolem函数消去全称量词后有 y P f y y Q f y y 和命题逻辑的情况一样 目标公式也限制为文字的析取式 这时要进行变量改名 使每个析取元具有不同的变量符号 于是有 y P f y y y1 Q f y1 y1 以后目标公式中的变量都假定受存在量词的束约 例 事实与或形表示P A y Q x A R B y 规则蕴涵式P z B S z X B 施以规则后的与或图 前边用合一置换时的问题 会不会在合一置换过程中有矛盾的地方 可能有 怎么办 求一致解图 一致解图 只有当解图所涉及的置换集是一致的时 解图才是一致的 置换集一致的充分必要条件是该置换集存在合一复合 置换集的合一复合也是一个置换 表示的是置换集中所有置换 综合 以后的结果 合一复合 求一个置换集的合一复合 首先构造U1 U2两个表达式 其中U1由置换集中的所有被置换的变量组成 U2由与U1中的变量所对应的置换项组成 当U1 U2可以合一时 则所对应的置换集是一致的 一致置换 它们的mgu就是该置换集的合一复合 合一复合是可结合 可交换的 这是一个很好的性质 说明在用基于规则的正向演绎方法求解问题时 与使用规则的次序无关 一致置换举例 例 猎犬问题 设事实和规则描述如下 事实 Fidobarksandbites orFidoisnotadog F DOG FIDO BARKS FIDO BITES FIDO 规则 Allterriersaredogs R1 DOG x TERRIER x Anyonewhobarksisnoisy R2 BARKS y NOISY y 要证明的目标是Thereexistssomeonewhoisnotaterriersorwhoisnoisy 目标公式 TERRIER z NOISY z NOISY z R1 DOG x TERRIER x R2 BARKS y NOISY y 置换集 FIDO x FIDO y FIDO z 它的合一复合u FIDO x FIDO y FIDO z 根据这个一致解图 目标公式 TERRIER z NOISY z 是事实和规则的逻辑推论 因而得到了证明 如果用这个合一复合u应用于这个目标公式 可得 TERRIER FIDO NOISY FIDO 它是已证目标公式的例 可作为一个回答语句 正向演绎系统小结 事实表达式为与或形规则化成L W目标公式为文字析取对事实和规则进行Skolem化 消去存在量词 对主合取元进行变量换名目标用对偶形式进行Skolem化 消去全称量词 对主析取元进行变量换名 事实表达成与或树 对应 或 的关系 而 对应 与 的关系 从事实出发 正向应用规则 直到得到目标结点为结束的一致解图为止 存在合一复合时 解图才有效 基于规则的逆向演绎系统 逆向演绎系统中 是从目标表达式出发 反方向使用规则 B规则 对目标表达式的与或图进行变换 最后得到含有事实节点的一致解图 1 目标表达式的与或形表示 目标用对偶形式进行Skolem化 即 消去全称量词 对受全称量词约束的变量用Skolem函数或者常量代替省略存在量词 所有变量默认为受存在量词约束进行变量换名 使得目标公式的主析取元之间具有不同的变量名 与或图表示 其 与 和 或 的关系是刚好一致的 在与或形中的 号在与或图中表达为 与 的关系 而与或形中的 号 在与或图中表达为 或 的关系 例 目标公式 y x P x Q x y R x S y Skolem化后 P f y Q f y y R f y S y 变量标准化 P f z Q f y y R f y S y 目标公式的与或图表示 一致 2 规则的应用 在一个逆向演绎系统中 规则具有形式 W L 其中W是任意形式的与或形 L是单文字 它表示L可以由W推导出 其中的变量受全称量词约束 如果有存在量词 则将其Skolem化 消去存在量词 如果在与或图中有一个叶节点刚好与L可以合一 则可以使用规则对与或图进行变换 其方法是 求出该叶节点与L的mgug 将该叶节点与L用一个匹配弧连接起来 用g对W进行置换 然后将W添加到与或图中 例 设事实有F1 DOG FIDO F2 BARKS FIDO F3 WAGS TAIL FIDO F4 MEOWS MYRTLE 规则集 R1 WAGS TAIL x1 DOG x1 FRIENDLY x1 R2 FRIENDLY x2 BARKS x2 AFRAID y2 x2 R3 DOG x3 ANIMAL x3 R4 CAT x4 ANIMAL x4 R5 MEOWS x5 CAT x5 询问 Ifthereareacatandadogsuchthatthecatisunafraidofthedog 目标公式 x y CAT x DOG y AFRAID x y 其逆向一致解图如下 R1 WAGS TAIL x1 DOG x1 FRIENDLY x1 R2 FRIENDLY x2 BARKS x2 AFRAID y2 x2 R5 MEOWS x5 CAT x5 F1 DOG FIDO F2 BARKS FIDO F3 WAGS TAIL FIDO F4 MEOWS MYRTLE R1 WAGS TAIL x1 DOG x1 FRIENDLY x1 R2 FRIENDLY x2 BARKS x2 AFRAID y2 x2 R3 DOG x3 ANIMAL x3 R4 CAT x4 ANIMAL x4 R5 MEOWS x5 CAT x5 置换集是 x x5 MYRTLE x FIDO y x y2 y x2 FIDO y y x1 FIDO y FIDO y 由此求得的合一复合是 MYRTLE x5 MYRTLE x FIDO y MYRTLE y2 FIDO x2 FIDO x1 解图是一个一致解图 目标公式得到证明 把这个合一复合置换应用到目标公式得到的例 其回答语句为 CAT MYRTLE DOG FIDO AFRAID MYRTLE FIDO 正向系统和逆向系统特点对比 正逆向系统特点对比 续 正逆向系统特点对比 续