第3章确定性推理.ppt

按照推理过程所用知识的确定性 推理可分为确定性推理和不确定性推理 自然演绎推理和归结推理是经典的确定性推理 它们以数理逻辑的有关理论 方法和技术为理论基础 是机械化的 可在计算机上加以实现的推理方法 本章在讨论有关推理的一般概念以及命题和谓词逻辑的基础上 介绍自然演绎推理方法和基于一阶谓词逻辑的归结推理方法 3 1推理概述3 2命题逻辑3 3谓词逻辑3 4自然演绎推理方法3 5归结推理方法3 6归结过程的控制策略 3 1推理概述 3 1 1推理的基本概念推理是指从已知事实出发 运用已掌握的知识 推导出其中蕴含的事实性结论或归纳出某些新的结论的过程 其中 推理所用的事实可分为两种情况 一种是与求解问题有关的初始证据 另一种是推理过程中所得到的中间结论 这些中间结论可以作为进一步推理的已知事实或证据 人工智能系统的构成 推理机 一些程序来完成的 综合数据库 存放有用于推理的事实或证据 知识库 存放有用于推理所必须的知识 3 1 2推理的方法及其分类1 按照推理的逻辑基础分类可分为演绎推理 归纳推理和默认推理 1 演绎推理演绎推理是从已知的一般性知识出发 推理出适合于某种个别情况的结论的过程 它是一种由一般到个别的推理方法 3 1推理概述 3 1推理概述 2 归纳推理归纳推理是从大量特殊事例出发 归纳出一般性结论的推理过程 是一种由个别到一般的推理方法 其基本思想是 首先从已知事实中猜测出一个结论 然后对这个结论的正确性加以证明确认 数学归纳法就是归纳推理的一种典型例子 归纳推理又可分为 从特殊事例考察范围看 完全归纳推理 不完全归纳推理 从使用的方法看 枚举归纳推理 类比归纳推理 3 默认推理默认推理又称缺省推理 是在知识不完全的情况下假设某些条件已经具备所进行的推理 也就是说 在进行推理时 如果对某些证据不能证明其不成立的情况下 先假设它是成立的 并将它作为推理的依据进行推理 但在推理过程中 当由于新知识的加入或由于所推出的中间结论与已有知识发生矛盾时 就说明前面的有关证据的假设是不正确 这时就要撤消原来的假设以及由此假设所推出的所有结论 重新按新情况进行推理 3 1推理概述 2 按所用知识的确定性分类按推理时所用知识的确定性来划分 推理可分为确定性推理 不确定性推理 3 按推理过程的单调性按照推理过程中所推出的结论是否单调地增加 或者说按照推理过程所得到的结论是否越来越接近最终目标来分类 推理可分为单调推理与非单调推理 3 1推理概述 3 1 3推理的控制策略推理过程不仅依赖于所用的推理方法 同时也依赖于推理的控制策略 控制策略包括推理方向 搜索策略 冲突消解策略等 而推理方法则是指在推理控制策略确定之后 在进行具体推理时所要采取的匹配方法或不确定性传递算法等方法 推理方向用来确定推理的驱动方式 即是数据 证据 驱动或是目标驱动 所谓数据驱动即指推理过程从初始证据开始直到目标结束 而目标驱动则是指推理过程从目标开始进行反向推理 直到出现与初始证据相吻合的结果 按照对推理方向的控制 推理可分为正向推理 反向推理 混合推理及双向推理四种情况 3 1推理概述 正向推理是一种从已知事实出发 正向使用推理规则的推理方式 它是一种数据 或证据 驱动的推理方式 又称前项链推理或自底向上推理 反向推理是一种以某个假设目标为出发点 反向运用推理规则的推理方式 它是一种目标驱动的推理方式 又称反向链推理或自顶向下推理 混合推理是把正向推理和反向推理结合起来所进行的推理 所谓双向混合推理是指正向推理和反向推理同时进行 使推理过程在中间的某一步骤相汇合而结束的一种推理方法 3 1推理概述 3 1 4推理的冲突消解策略推理过程中的冲突消解策略 就是确定如何从多条匹配规则中选出一条规则作为启用规则 将它用于当前的推理 目前已有的多种冲突消解策略的基本思想都是对匹配的知识或规则进行排序 以决定匹配规则的优先级别 优先级高的规则将作为启用规则 常用排序方法有如下几种 3 1推理概述 按就近原则排序按知识特殊性排序按上下文限制排序按知识的新鲜性排序按知识的差异性排序按领域问题的特点排序按规则的次序排序按前提条件的规模排序 3 1推理概述 3 2命题逻辑 3 2 1命题定义3 1能够分辨真假的语句称作命题 定义3 2一个语句如果不能再进一步分解成更简单的语句 并且又是一个命题 则称此命题为原子命题 原子命题是命题中最基本的单位 我们一般用P Q R 大写拉丁字母表示命题 而命题的真与假分别用 T 与 F 表示 用大写英文字母表示的命题既可以是一个特定的命题 也可以是一个抽象的命题 前者称为命题常量 后者称为命题变量 对于命题变量而言 只有把确定的命题代入后 它才可能有明确的逻辑值 T或F 3 2 2命题公式1 连接词 称为 非 或 否定 称为 析取 称为 合取 称为 条件 或者 蕴含 称为 双条件 P Q表示 P当且仅当Q 表3 1命题逻辑真值表 3 1推理概述 2 命题公式定义3 3以下面的递归形式给出命题公式的定义 1 原子命题是命题公式 2 A是命题公式 则 A也是命题公式 3 若A和B都是命题公式 则A B A B A B A B 4 只有按 1 3 所得的公式才是命题公式 3 1推理概述 命题公式的缺点 无法把所描述的客观事物的结构和逻辑特征反映出来不能把不同事物的共同特征反映出来P 张三是李四的老师 仅用字母P看不出张三和李四之间的师生关系 为了克服命题逻辑的局限性 引入了下面的谓词逻辑 3 1推理概述 3 3谓词逻辑 3 3 1谓词与个体在谓词逻辑中 将原子命题分解为谓词与个体两部分 个体是指可以独立存在的物体 可以是抽象的或具体的 谓词则是用于刻画个体的性质 状态或个体间的关系的 例如 李白是诗人 可表示为 poet LiBai poet称为谓词 用以刻画 是诗人 LiBai称为个体 3 3谓词逻辑 一个谓词可以与一个个体相关联 此种谓词称作一元谓词 它刻画了个体的性质 一个谓词也可以与多个个体相关联 此种谓词称为多元谓词 它刻画了个体间的 关系 谓词的一般形式 P x1 x2 xn 其中P是谓词 而x1 x2 xn是个体 谓词通常用大写字母表示 个体通常用小写字母表示 项 在谓词中 个体可以是常量 也可以是变量 还可以是一个函数 例如 小刘的哥哥是个工人 可以表示为worker brother Liu 其中brother Liu 是一个函数 个体常数 变量和函数统称为项 谓词的语义 由使用者根据需要人为地定义 3 3谓词逻辑 谓词的元数 谓词中包含的个体数目称为谓词的元数 谓词的阶数 在谓词P x1 x2 xn 中 若xi i 1 2 n 都是个体常量 变元或函数 则称它为一阶谓词 如果某个xi本身又是一个一阶谓词 则称它为二阶谓词 依次类推 3 3谓词逻辑 3 3 2谓词公式1 连接词 2 量词全称量词 x 和存在量词 x 3 谓词演算公式定义3 4谓词演算中 由单个谓词构成的不含任何连接词的公式 叫做原子谓词公式 3 3谓词逻辑 由原子公式的定义出发 可定义谓词演算的合式公式如下 定义3 5可按下述规则得到谓词演算的合式公式 1 原子谓词公式是合式公式 2 若A是合式公式 则 A也是合式公式 3 若A和B都是合式公式 则A B A B A B A B也都是合式公式 4 若A是合式公式 x是任一个体变元 则 x A和 x A也都是合式公式 5 只有按 1 4 所得的公式才是合式公式 3 3谓词逻辑 4 量词辖域与约束变元在一个公式中 如果有量词出现 位于量词后面的单个谓词或者用括弧括起来的合式公式称为量词的辖域 在辖域内与量词中同名的变元称为约束变元 3 3谓词逻辑 3 3 3谓词公式的永真性和可满足性1 谓词公式的解释定义3 6设D为谓词公式P的个体域 若对P中的个体常量 函数和谓词按照如下规定赋值 1 为每个个体常量指派D中的一个元素 2 为每个n元函数指派一个从Dn到D的映射 其中Dn x1 x2 xn x1 x2 xn D 3 为每个n元谓词指派一个从Dn到 F T 的映射 则称这些指派为公式P在D上的一个解释 3 3谓词逻辑 例3 1设个体域D 1 2 求公式A x P x Q f x b 在D上的某一个解释 并指出在此解释下公式A的真值 详细的求解过程参见教材 3 3谓词逻辑 2 谓词公式的永真性定义3 7如果谓词公式P 对个体域D上的任何一个解释都取得真值T 则称P在D上是永真的 如果P在每个非空个体域上均永真 则称P永真 定义3 8如果谓词公式P对于个体域D上的所有解释都取得假值F 则称P在D上是永假的 如果P在每个非空个体域上均永假 则称P永假 谓词公式的永假性又称为不可满足性或不相容性 3 3谓词逻辑 3 谓词公式的可满足性定义3 9对于谓词公式P 如果至少存在一个解释使得公式P在此解释下的真值为T 则称公式P是可满足的 按照定义3 9 对谓词公式P 如果不存在任何解释 使得P的取值为T 则称公式P是不可满足的 所以 谓词公式P永假与不可满足是等价的 若P永假 则也可称P是不可满足的 3 3谓词逻辑 3 3 4谓词公式的等价性与永真蕴含定义3 10设P与Q是两个谓词公式 D是它们共同的个体域 若对D上的任何一个解释 P与Q的取值都相同 则公式P和Q在域D上是等价的 如果D是任意个体域 则称P和Q是等价的 记作P Q 常用的一些等价式参见教材定义3 11对于谓词公式P和Q 如果P Q永真 则称P永真蕴含Q 且称Q为P的逻辑结论 称P为Q的前提 记作P Q 以后要用到的一些永真蕴含式参见教材 3 3谓词逻辑 谓词逻辑中还有如下一些推理规则 1 P规则 在推理的任何步骤上都可引入前提 2 T规则 推理时 如果前面步骤中有一个或多个永真蕴含公式S 则可把S引入推理过程中 3 CP规则 如果能从R和前提集合中推出S来 则可从前提集合推出R S来 4 反证法 P Q 当且仅当P Q F 即Q为P的逻辑结论 当且仅当P Q是不可满足的 推广之 可得如下定理 定理3 1Q为P1 P2 Pn的逻辑结论 当且仅当 P1 P2 Pn Q是不可满足的 3 3谓词逻辑 3 3 5置换与合一1 置换 置换的定义定义3 12置换是形如 t1 x1 t2 x2 tn xn 的一个有限集 其中xi是变量 ti是不同于xi的项 常量 变量 函数 且xi xj I j i j 1 2 n 3 3谓词逻辑 例如 a x b y f x z f z x y z 都是置换 不含任何元素的置换称为空置换 以 表示 置换乘法置换乘法作用是将两个置换合成为一个置换 定义3 13假设 t1 x1 t2 x2 tn xn u1 y1 u2 y2 um ym 是两个置换 则它们的乘积是一个新置换 其作用于公式E时 相当于先 后 对E的作用 它的定义如下 3 3谓词逻辑 先作置换 t1 x1 t2 x2 tn xn u1 y1 u2 y2 um ym 若yi x1 xn 时 先从上述集合中删除ui yi 若ti xi时 再从上述集合中删除ti xi 删除以后剩下元素所构成的集合称作 与 的乘积 记作 置换结合率一般地说 下列的置换结合律成立 但除了空置换外 置换的交换律不成立 即只有 3 3谓词逻辑 2 合一 合一的概念定义3 14设有公式集 E1 E2 En 和置换 使E1 E2 En 便称E1 E2 En是可合一的 且 称为合一置换 定义3 15若E1 E2 En有合一置换 且对E1 E2 En的任一置换都存在一个置换 使得 则称 是E1 E2 En的最一般合一置换 记为mgu 3 3谓词逻辑 最一般合一置换的求取算法设有两个谓词公式 E1 P x y z E2 P x f a g b 分别从E1与E2的第一个符号开始逐个向右比较 此时发现E1中的y与E2中的f a 不同 则它们构成了一个不一致集 D1 y f a 当继续向右比较时 又发现中E1中的z与E2中g b 不同 则又得到一个不一致集 D2 z g b 下面给出求公式 E1 E2 的最一般合一置换的算法 3 3谓词逻辑 1 令W E1 E2 2 令k 0 Wk W k 是空置换 它表示不作置换 3 如果Wk只有一个表达式 则算法停止 k就是所要求的mgu 4 找出Wk的不一致集Dk 5 若Dk中存在元素xk和tk 其中xk是变元 tk是项 且xk不在tk中出现 则置 k 1 k tk xk Wk 1 wk tk xk k k 1然后转 3 6 算法终止 W的mgu不存在 可以证明 如果E1和E2可合一 则算法必停止于第 3 步 3 3谓词逻辑 例3 5设E1 P a v f g y E2 P z f a f u 求E1和E2的mgu 解题请参见教材答案为 3 a z f a v g y u 3就是E1和E2的mgu 3 3谓词逻辑 3 4自然演绎推理方法 3 4 1自然演绎推理的概念自然演绎推理是指从一组已知为真的事实出发 直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程 假言三段论的基本形式为P Q Q R P R它表示如果谓词公式P Q和Q R均为真 则谓词公式P R也为真 假言推理可用下列形式表示P P Q Q它表示如果谓词公式P和P Q都为真 则可推得Q为真结论 拒取式的一般形式为P Q Q P它表示如果谓词公式P Q为真且Q为假 则可推得P为假的结论 P规则 在证明的任何步上 都可引入前提 T规则 在证明的任何步上 结论都可作为证明前提 置换规则 在证明的任何步上 命题公式的任何子命题公式都可以用与之等价的命题公式置换 3 4自然演绎推理方法 推理过程的证明形式 规范化的形式 序号公式理由 B1E或I或P或 的合取或cp B2 B3 注意 1 并非B1 B2 B32 Bi的获取 前提 中间结论 构造下列的推理的证明 前提 P Q P R S M S R M结论 Q MP S MP S 拒取式 S RP R 假言推理 P RP P 拒取式 P QP Q I析取三段式 一公安人员审查一件案件 一致的事实如下 1 张三或李四盗窃了录像机 2 如果张三盗窃了录像机 则作案时间不能在午夜前 3 如果李四证词正确 则午夜时屋内灯光未灭 4 如果李四证词不正确 则作案时间在午夜前 5 午夜时屋内灯灭了 MP S MP S 拒取式 S RP R 假言推理 P RP P 拒取式 P QP Q 析取三段式 解 将已知事实符号化 设P 张三盗窃录像机 Q 李四盗窃录像机 R 作案时间发生在午夜前 S 李四证词正确 M 午夜时灯光未灭 则前提为 1 P Q 2 P R 3 S M 4 S R 5 M 结论未定 所以 可以得出是李四盗了录像机 前提 p r s q p s结论 q 证明 pp规则 p r s q p规则 r s q sp规则 s r I r s E q I 推理证明的方法 前提的合取 结论是永真式 间接证明法 推理证明 演绎证明 归纳证明 直接证明法 附加前提证法 CP 归谬法 反证法 附加前提证法 CP 针对这种情况 前提 A1 A2 An结论 A B 前提 A1 A2 An A结论 B 例 前提 P P Q R S 结论 Q S 证明 1 Pcp规则 2 P Q R S cp规则 3 Q R S 1 2 I 4 Qcp规则 5 R S 3 4 I 6 S 5 I 课堂作业 前提 P Q R S P Q结论 S R 3 5归结推理方法 要证明这个谓词公式的永真性 必须对所有个体域上的每一个解释进行验证 这是极其困难的 为了化简问题 考虑反证法 即 先否定逻辑结论Q 再由否定后的逻辑结论 Q及前提条件P出发推出矛盾 即可证明原问题 3 5 1谓词公式与子句集1 范式 前束形范式一个谓词公式 如果它的所有量词均非否定地出现在公式的最前面 且它的辖域一直延伸到公式之末 同时公式中不出现连接词 及 这种形式的公式称作前束形范式 例如 公式 x y z P x F y z Q y z 即是一个前束形的公式 3 5归结推理方法 斯克林范式错 从前束形范式中消去全部存在量词所得到的公式即为Skolem范式 或称Skolem标准型 对 无存在量词 且无量词部分是合取范式的前束形范式 为Skolem范式 例如 如果用f x 代替上面前束形范式中的y即得到Skolem范式 x z P x F f x z Q f x z Skolem标准型的一般形式是 x1 x2 xn M x1 x2 xn 其中 M x1 x2 xn 是一个合取范式 称为Skolem标准型的母式 3 5归结推理方法 将谓词公式G化为Skolem标准型的步骤如下 1 消去谓词公式G中的蕴涵 和双条件符号 以 A B代替A B 以 A B A B 替换A B 2 减少否定符号 的辖域 使否定符号 最多只作用到一个谓词上 3 重新命名变元名 使所有的变元的名字均不同 并且自由变元及约束变元亦不同 3 5归结推理方法 4 消去存在量词 这里分两种情况 一种情况是存在量词不出现在全称量词的辖域内 此时 只要用一个新的个体常量替换该存在量词约束的变元 就可以消去存在量词 另一种情况是 存在量词位于一个或多个全称量词的辖域内 这时需要用一个Skolem函数替换存在量词而将其消去 5 把全称量词全部移到公式的左边 并使每个量词的辖域包括这个量词后面公式的整个部分 6 母式化为合取范式 任何母式都可以写成由一些谓词公式和谓词公式否定的析取的有限集组成的合取 需要指出的是 由于在化解过程中 消去存在量词时作了一些替换 一般情况下 G的Skolem标准型与G并不等值 3 5归结推理方法 2 子句与子句集定义3 16不含有任何连接词的谓词公式叫原子 而原子或原子的否定统称文字 原子与原子的否定称互补文字定义3 17子句就是由一些文字组成的析取式 定义3 18不包含任何文字的子句称为空子句 记为NIL 定义3 199由子句构成的集合称为子句集 3 5归结推理方法 3 不可满足意义下的一致性定理3 2设有谓词公式G 而其相应的子句集为S 则G是不可满足的充分必要条件是S是不可满足的 要再次强调 公式G与其子句集S并不等值 只是在不可满足意义下等价 3 5归结推理方法 4 P P1 P2 Pn的子句集当P P1 P2 Pn时 若设P的子句集为SP Pi的子句集为Si 则一般情况下 SP并不等于S1 S2 S3 Sn 而是要比S1 S2 S3 Sn复杂得多 但是 在不可满足的意义下 子句集SP与S1 S2 S3 Sn是一致的 即SP不可满足 S1 S2 S3 Sn不可满足 3 5归结推理方法 3 5 2Herbrand理论1 H域定义3 20设谓词公式G的子句集为S 则按下述方法构造的个体变元域H 称为公式G或子句集S的Herbrand域 简称H域 1 令H0是S中所出现的常量的集合 若S中没有常量出现 就任取一个常量a D 规定H0 a 2 令Hi 1 Hi S中所有的形如f t1 tn 的元素 其中f t1 tn 是出现于G中的任一函数符号 而t1 tn是Hi中的元素 i 0 1 2 3 5归结推理方法 例3 10求子句集S T x Q z R f y 的H域 解此例中没有个体常量 任意指定一个常量a作为个体常量 只有一个函数f y 有 H0 a H1 a f a H2 a f a f f a H a f a f f a f f f a 3 5归结推理方法 2 原子集定义3 21下列集合称为子句集S的原子集 A 所有形如P t1 t2 tn 的元素 其中 P t1 t2 tn 是出现在S中的任一谓词符号 而t1 t2 tn则是S的H域上的任意元素 3 5归结推理方法 定义3 22将没有变元出现的原子 文字 子句和子句集分别称作基原子 基文字 基子句和基子句集 定义3 23当子句集S中的某个子句C中的所有变元符号均以其H域中的元素替换时 所得到的基子句称作C的一个基例 例如 对于子句集S P a P x P f x 它的H域为 a f a f f a 对于子句P a 因为其中不含有变元 所以它已是基子句 而且a H 所以它也是基例 3 5归结推理方法 3 H域上的解释定义3 24如果子句集S的原子集为A 则对A中各元素的真假值的一个具体设定都是S的一个H解释 可以证明 在给定域D上的任一个解释I 总能在H域上构造一个解释I 与之对应 使得如果D域上的解释能满足子句集S 则在H域的解释I 也能满足S 即若S I T 就有S I T 3 5归结推理方法 定理3 3设I是子句集S在域D上的一个解释 则存在对应于I的H域解释I 使得若有S I T 就必有S I T 定理3 4子句集S不可满足的充要条件是S对H域上的一切解释都为假 证明充分性 若S在一般域D上是不可满足的 必然在H域上是不可满足的 从而对H域上的一切解释都为假 必要性 若S在任一H解释I 下均为假 必然会使S在D域上的每一个解释为假 否则 如果存在一个解释I0使S为真 那么依据定理3 3可知 一定可以在H域找到相对应的一个解释I 0使S为真 这与S在所有H解释下均为假矛盾 3 5归结推理方法 定理3 5子句集S不可满足的充分必要条件是存在一个有限的不可满足的基例集S 该定理称为Herbrand定理 下面给出它的简要证明 证明充分性 设子句集S有一个不可满足的基例集S 因为它不可满足 所以一定存在一个解释I 使S 为假 根据H域上的解释与D域上的解释的对应关系 可知在D域上一定存在一个解释使S不可满足 从而证明了子句集S是不可满足的 3 5归结推理方法 必要性 设子句集S不可满足 由定理3 4可知 S对H域上的所有解释均为假 这样 就至少会存在一个S中的某子句Ci的基例Ci 为假 既然至少有一个基例Ci 为假 因而S的基例集S 是不可满足的 另外 由于S中的子句是有限的 而每个子句又由有限的文字组成 因而S的不可满足的基例集也是有限的 3 5归结推理方法 3 5 3归结原理定义3 25若P是原子谓词公式或原子命题 则称P与 P为互补文字 1 命题逻辑中的归结原理归结与归结式定义3 26设C1与C2是子句集中的任意两个子句 如果C1中的文字L1与C2中的文字L2互补 则从C1和C2中可以分别消去L1和L2 并将二子句中余下的部分做析取构成一个新的子句C12 称这一过程为归结 所得到的子句C12称为C1和C2的归结式 而称C1和C2为C12的亲本子句 3 5归结推理方法 定理3 6归结式C12是其亲本子句C1和C2的逻辑结论 推论设C1和C2是子句集S上的子句 C12是C1和C2的归结式 如果把C12加入子句集S后得到新子句集S1 则S1和S在不可满足的意义下是等价的 即 S是不可满足的S1是不可满足的归结推理过程子句集S不可满足性的推理过程如下 1 对子句集S中的各子句间使用归结推理规则 2 将归结所得的归结式放入子句集S中 得新子句集S 3 检查子句集S 中是否有空子句 NIL 若有则停止推理 否则转 4 4 置S S 转步骤 1 3 5归结推理方法 2 一阶谓词逻辑中的归结原理下面是谓词逻辑关于归结的定义 定义3 27设C1和C2是两个没有相同变元的子句 L1和L2分别是C1和C2的文字 如果L1与 L2有mgu 则把C12 C1 L1 C2 L2 称作子句C1和C2的一个二元归结式 而L1和L2是被归结的文字 为了说明的方便 将Ci 和Li 写成集合形式 如P x Q y P x Q y 在集合的表示下做减法或做并运算 然后再写成子句形 如集合运算结果为 P x Q y 可改写为P x Q y 3 5归结推理方法 在谓词逻辑中 对子句进行归结推理时 要注意以下几个问题 1 若被归结的子句C1和C2中具有相同的变元时 需要将其中一个子句的变元更名 否则可能无法做合一置换 从而没有办法进行归结 2 在求归结式时 不能同时消去两个互补文字对 消去两个互补文字对所得的结果不是两个亲本子句的逻辑推论 3 如果在参加归结的子句内含有可合一的文字 则在进行归结之前 应对这些文字进行合一 以实现这些子句内部的化简 3 5归结推理方法 应用因子的概念 可对谓词逻辑中的归结原理定义如下 定义3 28设C1和C2是没有相同变元的子句 则下列四种二元归结式都叫做C1和C2的归结式 仍记作C12 1 C1与C2的二元归结式 2 C1的因子C1 1与C2的二元归结式 3 C1与C2的因子C2 2的二元归结式 4 C1的因子C1 1与C2的因子C2 2的二元归结式 3 5归结推理方法 例设C1 P a Q x R x C2 P y Q b 求其二元归结式 解若选L1 P a L2 P y 则L1和L2的mgu是 a y 于是由定义3 27得C1和C2的二元归结式为C12 C1 L1 C2 L2 P a Q x R x P a P a Q b P a Q x R x Q b Q x R x Q b 若选L1 Q x L2 Q b 则二者的mgu b x C12 P a R b P y 3 5归结推理方法 3 归结原理的完备性对于一阶谓词逻辑 从不可满足的意义上说 归结原理是完备的 即若子句集是不可满足的 则必存在一个从该子句集到空子句的归结推理过程 反之 若从子句集到空子句存在一个归结推理过程 则该子句集必是不可满足的 3 5归结推理方法 3 5 4利用归结原理进行定理证明应用归结原理进行定理证明的步骤如下 设要被证明的定理可用谓词公式表示为如下的形式 A1 A2 An B 1 首先否定结论B 并将否定后的公式 B与前提公式集组成如下形式的谓词公式 G A1 A2 An B 2 求谓词公式G的子句集S 3 应用归结原理 证明子句集S的不可满足性 从而证明谓词公式G的不可满足性 这就说明对结论B的否定是错误的 推断出定理的成立 3 5归结推理方法 例已知 A x y P x y Q y y R y T x y B x R x x y P x y Q y 求证 B是A的逻辑结论 证明首先将A和 B化为子句集 P x y Q y R f x P x y Q y T x f x 1 2 为A R z P a b Q b 3 4 5 为B 3 5归结推理方法 下面进行归结 6 P x y Q y 1 与 3 归结 f x z 7 Q b 4 与 6 归结 a x b y 8 NIL 空子句 5 与 7 归结所以B是A的逻辑结论 3 5归结推理方法 3 5 5应用归结原理进行问题求解下面是利用归结原理求取问题答案的步骤 1 把已知前提条件用谓词公式表示出来 并化成相应的子句集 设该子句集的名字为S1 2 把待求解的问题也用谓词公式表示出来 然后将其否定 并与一谓词ANSWER构成析取式 谓词ANSWER是一个专为求解问题而设置的谓词 其变量必须与问题公式的变量完全一致 3 把问题公式与谓词ANSWER构成的析取式化为子句集 并把该子句集与S1合并构成子句集S 3 5归结推理方法 4 对子句集S应用谓词归结原理进行归结 在归结的过程中 通过合一置换 改变ANSWER中的变元 5 如果得到归结式ANSWER 则问题的答案即在ANSWER谓词中 3 5归结推理方法 例任何兄弟都有同一个父亲 John和Peter是兄弟 且John的父亲是David 问Peter的父亲是谁 解第一步 将已知条件用谓词公式表示出来 并化成子句集 那么要先定义谓词 1 定义谓词 设Father x y 表示x是y的父亲 Brother x y 表示x和y是兄弟 3 5归结推理方法 2 将已知事实用谓词公式表示