第三章一阶谓词逻辑.ppt

第三章一阶谓词逻辑表示知识 3 1一阶谓词逻辑形式 3 2谓词公式 永真性 可满足性 不可满足性 3 3谓词公式的等价性与永真蕴含 3 4自然演绎推理 3 5归结演绎推理 3 6归结策略讨论 3 1一阶谓词逻辑形式 前面离散数学课程已经讲述过谓词逻辑 在这里简要回顾如下 1 命题逻辑定义具有确定真值的陈述句 称为命题 例 1 2是素数 2 雪是黑的 3 今年的十二月一号是个晴天 4 X Y 5命题若是简单的陈述句 不能分解成更简单的句子 我们称这样的命题为简单命题或原子命题 可以用英文字母P Q R 或是带有下标的大写英文字母Pi等表示简单命题 将命题用合适的符号表示 称为命题符号化 命题逻辑的局限性 例如 命题 焦作是一个漂亮的城市P郑州是一个漂亮的城市Q晋城是一个漂亮的城市R新乡是一个漂亮的城市S安阳是一个漂亮的城市T要表达这样一个类别的知识时 命题逻辑表达起来 不方便 用谓词结构的形式最方便定义谓词 BeautifulCity x x是一个漂亮的城市像这样表达知识的形式就是谓词表达知识的形式 2 一阶谓词逻辑谓词的一般形式是 P x1 x2 xn 其中P是谓词 通常才用首字母大写开头的字母字符串表示 x1 x2 x3 是个体 通常用小写字母来表示 在谓词逻辑中 命题被细分为谓词和个体两个部分 n元谓词 含有n个个体符号的谓词P x1 x2 xn 表示一个映射 P Dn T F 或是 D1 D2 D3 Dn T F 谓词 用于刻画个体的性质 状态或个体之间的关系 称为谓词 谓词一般也用P Q R等大写字母表示 例1 x是一个美丽的城市可以写成 BeautifulCity x 其中 BeautifulCity是谓词 x是个体例2 x y可定义成 Greater x y 这里 x y是个体 Greater是谓词 谓词的一般形式是 P x1 x2 xn 其中P是谓词 通常首字母用大写字母表示 x1 x2 x3 是个体 通常用小写字母来表示 在谓词逻辑中 命题被细分为谓词和个体两个部分 n元谓词 含有n个个体符号的谓词P x1 x2 xn 表示一个映射 P Dn T F 或是 D1 D2 D3 Dn T F 谓词的语义是由使用者根据需要人为定义的 如 S x 可以定义成x是船也可定义成x是学生谓词中包含的个体数目称为谓词的元数 如 Q x 是一元谓词 P x y 是二元谓词 A x1 x2 xn 是n元谓词 若Xi是个体常元 变元或函数 谓词称为一阶谓词 如果某个Xi本身又是一个一阶谓词 则谓词称为二阶谓词 依次类推 个体变元的取值范围称为个体域 或称论域 个体域可以是有限的也可以是无限的 例I x x是整数 则个体域是所有整数 它是无限的 函数符号 是从若干个研究对象到某个研究对象的映射的符号 n元函数f x1 x2 xn 规定为一个映射 f Dn D谓词与函数的区别 1 谓词的真值是真和假 而函数无真值可言 其值是个体域中的某个个体 2 谓词描述的是个体域中的个体之间的关系或性质 而函数实现的是一个个体的出现依赖于个体中中的其他个体 他是一个个体在个体域中的映射 3 在谓词逻辑中 函数本身不能单独使用 它必须嵌入到谓词中 注意 有人讲命题逻辑是0元谓词逻辑 3 2谓词公式 永真性 可满足性 不可满足性3 2 1谓词公式1 联接词 用于联接两谓词公式 组成一个复杂的复合命题 否定 联接按词 当命题P为真时 则 P为假 反之为真 析取 联接词 它表示两个命题存在 或 者的关系 合取 联接词 两个命题之间具有 与 关系 蕴含 条件命题 P Q表示 如果P 则Q P为条件 Q为条件的后件 等价 双条件 表示 P当且仅当P 上述联结词构成谓词公式其定义如下 PQPP QP QP QPQTTFTTTTTFFTFFFFTTTFTFFFTFFTT 联接词的优先级 2 量词 用于刻划谓词与个体之间关系的词 在谓词逻辑中引入了两个量词 全称量词符号 x 及存在量词符号 x 全称量词符号 变元 全称量词 如 x 存在量词符号 变元 存在量词 如 x x 它表示对个体域中所有个体x x 表示在个体域中存在某个个体x 例 设谓词P x 表示x是正数 F x y 表示x与y是好朋友 则 x P x 表示个体域中所有个体x都是正数 x y F x y 表示在个体域中对任何个体x 都存在个体y x与y是好朋友 x y F x y 表示在个体域中存在个体x 它与个体域中的任何个体y都是朋友 y x F x y 表示在个体域中存在个体x与个体y x与y是朋友 x y F x y 表示对于个体域中的任何两个个体x和y x与y都是朋友 3 量词辖域与约束变元在一个谓词公式中 如果有量词出现 位于量词后面的单个谓词或者用括弧扩起来的合式公式称为量词的辖域 在辖域内与量词同名的变元称谓约束变元 不受约束的变元称谓自由变元 例如 x P x y R x y 其中 x 的辖域是 P x y R x y 辖域内的x是受 x 的约束的变元 而 y 的辖域是R x y R x y 的y是受 y 约束的变元 在这个公式中没有自由变元 在谓词公式中 变元的名字是无关紧要的 可以把一个变元的名字换成另一个变元的名字 但是 必须注意 当对量词辖域内的约束变元更名时 必须把同名的约束变元都统一改成相同的名字 且不能与辖域内的自由变元同名 同样 对辖域内的自由变元改名时 也不能改成与约束变元相同的名字 例如 对于公式 x R x y 可以改名为 t R t u 这里将约束变元x改成了t 把自由变元y改成了u 4 谓词公式 按下述规则得到谓词演算的合式公式 1 单个谓词和单个谓词的否定 称为原子谓词公式 原子谓词公式是合式公式 2 若A是合式公式 则 A也是合式公式 3 若A B都是合式公式 则A B A B A B AB也都是合式公式 4 若A是合式公式 x是任一个体变元 则 x A x A也都是合式公式 5 谓词公式的解释在谓词逻辑中 对谓词公式中各个个体变元的一次真值指派称为谓词公式的一个解释 也即蜕化成命题逻辑 一旦解释确定 根据各联接词的定义就可求出谓词公式中真值 T或F 定义 谓词公式G的论域为D 根据D和G中的常量符号 函数符号和谓词符号按下列规则作的一组指派成为G的一个解释I 或赋值 解释I 三个赋值规定 1 对公式G 为每个常量指派D中的一个元素 解释I 三个赋值规定 2 对公式G 为每个n元函数指派一个Dn D的映射 其中Dn x1 x2 xn x1 x2 xn D 3 对公式G 为每个n元谓词指派一个Dn T F 的映射 则称这些指派为公式G在D上的一个解释 公式只有经过指派才与现实联系起来 才有意义 解释I称为公式G在论域D上的一个解释 对应每个解释 公式G都有一个真值 T F 一阶谓词的公式解释数目 一阶谓词的公式解释数通常是相当可观的 是一种排列组合 设个体域有m个元素 则 每个常量有m个取值 n个常量有mn种取值的可能性 一个n元函数一般有种指派 一个n元谓词有种指派 整个公式在给定域上的解释数目将达到该公式所包含的所有函数和谓词指派数目的连乘积 由于存在多种组合情况 所以一个谓词公式的解释可能有很多个 对于每个解释 谓词公式都可求出一个真值 T或F 需要注意 x P x 的真值为1当且仅当对论域D的每一个元素x P x 都取值为1 x P x 的真值为0当且仅当对D的每个元素x P x 都取值为0 例3 2 1 设谓词公式A y P y Q y a B x P f x Q x f a 它们不含自由变元 解释给定为 D 2 3 a 2 f函数和谓词P Q的解释如下表所示 f 2 f 3 32 01 P 2 P 3 1111 Q 2 2 Q 2 3 Q 3 2 Q 3 3 求A B的值 则A P 2 Q 2 2 P 3 Q 3 2 0 1 1 1 0B P f 2 Q 2 f 2 P f 3 Q 3 f 2 P 3 Q 2 3 P 2 Q 3 3 1 1 0 1 1 例 设变元x和y的个体域是D 1 2 谓词P x y 表示x大于等于y 给出公式A x y P x y 在D上的解释 并指出在每一种解释下公式A的真值 解 由于在公式A中没有包括个体常量和函数 所以可由谓词P x y 的定义得出谓词的真值指派 设对谓词P x y 在个体域D上的真值指派为 P 1 1 T P 1 2 F P 2 1 T P 2 2 T这就是公式A在D上的一个解释 在此解释下 因为x 1时有y 1使P x y 的真值为T x 2时也有y 1使P x y 的真值为T 即x对于D中的所有取值 都存在y 1 使P x y 的真值为T 所以在此解释下公式A的真值为T 例 设个体域D 1 2 谓词公式B x P f x a 已知a 1 若指派f 1 1 f 2 2指派P 1 1 T P 2 1 T则上述各个指派就确定了谓词公式B的一个解释即对x在D上的任意取值 都使B为T 3 2 2 谓词公式的永真性 可满足性和永假性 永真性若谓词公式P对非空个体域D上的任一解释都有真值T 则称P在D上是永真的即 若P在任何非空个体域上均永真 则称P永真 可满足性对谓词公式P 若至少存在D上的一个解释 使P在此解释下真值为T 则称P在D上是可满足的永假性 不可满足性 不相容性 若谓词公式P对非空个体域D上的任一解释都有真值F 则称P在D上是永假的即 P在任何非空个体域上均永假 则称P永假 当个体域个数少 每个域自身又小时 易于判断或当解释的个数有限 也总是可判定的但若解释的个数无限时 就不能确保可以判定或者不能确保在有限的时间内判定 3 3谓词公式的等价性与永真蕴含 3 3 1等价性含义定义 设 与 是两个谓词公式 是它们共同的个体域 若对于 上的任何解释 和 都有相同的真值 则称 与 在个体域D上是等价的 如果D是任意个体域 则称P和Q是等价的 记作 P Q以下公式是等价式 推理时常用到 1 双重否定 P P 2 交换律P Q Q PP Q Q P 3 结合律 P Q R P Q R P Q R P Q R 4 分配律P Q R P Q P R P Q R P Q P R 5 狄 摩根定律 P Q P Q P Q P 6 吸收律P P Q PP P Q P 7 补余律P P TP P F 8 联词化归律P Q P Q蕴涵式转化PQ P Q P Q PQ P Q P Q 9 量词否定 x P x x P x x P x x P x 10 量词分配 x P x Q x x P x x Q x x P x Q x x P x x Q x 3 3 2谓词公式的永真蕴涵性 永真蕴涵性含义如果P Q永真 则称P永真蕴涵Q且称Q为P的逻辑结论 称P为Q的前提记作P Q 这就是知识的一种表达形式 永真蕴涵式 推理规则 1 化简式P Q PP Q Q 2 附加式P P QQ P Q 3 析取三段论 P P Q Q 表示 4 假言推理P P Q Q 5 拒取式 Q P Q P 6 假言三段论P Q Q R P R 7 二难推理P Q P R Q R R 8 全称固化 x P x P y 作用 y是任一个体 消去全称量词 9 存在固化 x P x P y 作用 y是某一个体 使P y 为真 消去存在量词其它规则1 规则 在推理的任何步骤上都可以引入前提2 规则 推理时 如果前面步骤中有一个或多个公式永真蕴含公式 则可以把 引入推理过程中3 规则 如果能从 和前提集合中推出 来 则可 则可以从前提集合推出 S来 反证法 Q 当且仅当 P QF 即Q为 的逻辑结论 当且仅当P Q是不可满足的 定理 为 1 n的逻辑结论 当且仅当 1 2 3 n 是不可满足的 该公式将在以后的推理中用到 是归结反演的理论依据 3 2 3用谓词公式表示知识的步骤 1 定义谓词及个体 确定每个谓词及个体的确切含义 2 根据所要表达的事物或概念 为每个谓词中的变元赋以特定的值 3 根据所要表达的知识的语义 用适当的联结符号将各个谓词联结起来 形成谓词公式 例 3 2 2人人爱劳动 所有整数不是偶数就是奇数 自然数都是大于零的整数 3 2 3用谓词公式表示知识的步骤 续1 解 首先定义谓词如下MAN x x是人LOVE x y x爱yN x x是自然数I x x是整数E x x是偶数O x x是奇数GZ x x大于零 3 2 3用谓词公式表示知识的步骤 续2 按照第2 3步要求 得到 人人爱劳动 用谓词公式表示为 x MAN x LOVE x labour 所有整数不是偶数就是奇数 用谓词公式表示为 x I x E x O x 自然数都是大于零的整数 用谓词公式表示为 x E x GZ x I x 3 2 3用谓词公式表示知识的步骤 续3 例 3 2 3梵塔 Hanoi 问题表示已知3个柱子1 2 3和3个盘子A B C A比B小 B比C小 初始状态下 A B C依次放在1号柱子上 搬动规则是每次可移动一个盘子 盘子上方是空时方可移动 任何时候都不允许大盘在小盘之上 解本问题涉及的常量是三个盘子 A B C 三个柱子 1 2 3 儿S表示状态 定义谓词和函数如下 3 2 3用谓词公式表示知识的步骤 续4 Disk x x是盘子PEE p w 盘子w在柱子p上Smaller x y x比y小Free x S 状态S下 x空顶Legal x y S 状态S下 x可向y移动ON x y S 状态S下 x在y上为了实现盘子的移动需要定义一个操作函数S move x y S 表示状态S下 x移到y上得到的新状态S 经上述处理后 他们之间有如下关系 3 2 3用谓词公式表示知识的步骤 续5 x y z Smaller x y Smaller y z Smaller x z 表示盘子大小的传递性 x S Free x S y ON x y S 表示状态S下 如果x是空顶 则必知S状态下无y在x上 x y S Legal x y S Free x S Free y S Disk x Smaller x y 表示x可向y上移动的充分必要条件为x和y均空顶 且x比y小 x是盘 3 2 3用谓词公式表示知识的步骤 续6 x y S S S move x y S ON x y S z1 z2 z1 x z2 y ON z1 z2 S ON z1 z2 S z ON x z S Free z S 表示如果在状态S下 将x移动到y上得新状态S 则没移动的盘子间的ON关系没有变动 而x下面的盘子却是空顶了 定义了谓词 函数后 就可以用一阶逻辑公式对问题进行表示 该问题的初始状态和目标状态用谓词公式表示如下 3 2 3用谓词公式表示知识的步骤 续7 初始状态S0的谓词公式 Disk A Disk B Disk C PEE 1 A PEE 1 B PEE 1 C Smaller A B Smaller B C Free A S0 ON A B S0 ON B C S0 目标状态Sg的谓词公式 Disk A Disk B Disk C PEE 3 A PEE 3 B PEE 3 C Smaller A B Smaller B C Free A Sg ON A B Sg ON B C Sg 3 2 3用谓词公式表示知识的步骤 续8 初始状态S0的谓词公式 Disk A Disk B Disk C PEE 1 A PEE 1 B PEE 1 C Smaller A B Smaller B C Free A S0 ON A B S0 ON B C S0 目标状态Sg的谓词公式 Disk A Disk B Disk C PEE 3 A PEE 3 B PEE 3 C Smaller A B Smaller B C Free A Sg ON A B Sg ON B C Sg 3 4自然演绎推理 特点 从一组已知为真的事实出发 直接运用经典逻辑中的推理规则 推出结论的过程 主要规则是三段论推理 它是演绎推理的核心 三段论推理包括假言推理 拒取式推理 假言三段论 二难推理 析取三段论 3 4自然演绎推理 续 1 假言推理形式 P P Q Q由P P Q为真 推出Q为真 P P Q P P Q Q P P Q Q T T T T T T F F F T T F F F F T F T T T 3 4自然演绎推理 续1 2 拒取式推理 拒取式是假言推理的后件否定形式 P Q Q P由P Q为真 Q为假 推出P为假 Q P Q P Q P P Q Q P T T T T T T F F F T T F F F F T F T T T Q 3 4自然演绎推理 续2 3 假言三段论的形式是 P Q Q R P R由P Q Q R为真 推出P R为真4 二难推论 P Q P R Q R R由P Q P R Q R为真 推出R为真5 析取三段论 P P Q Q由P为假 P Q为真 推出Q为真 3 4自然演绎推理 续3 P P Q Q P P Q Q P Q Q R P R P Q P R Q R R 假言推理 拒取式推理 假言三段论 二难推论 析取论三段论 P Q Q P 推理规则总结如下 自然演绎推理 推理规则 通常是正向推理 也可以反向推理P规则 引入前提 T规则 引入结论 假言推理P P Q Q由P Q为真及P为真 可推出Q为真拒取式推理P Q Q P由P Q为真及Q为假 可推出P为假 已知事实 经典逻辑推理规则 结论 定义 自然演绎推理举例 举例已知如下事实A B A C B C D D Q求证Q为真 T 证明因为A A C C假言推理B C B C引入合取词B C B C D D假言推理D D Q Q假言推理所以Q为T 自然演绎推理应用 已知如下事实 1 只要是需要编程序的课 王程都喜欢 2 所有的程序设计语言课都是需要编程序的课 3 C是一门程序设计语言课求证王程喜欢C这门课证明第一步定义谓词prog x x是需要编程序的课like x y x喜欢ylang x x是一门程序设计语言课 第二步用谓词表示已知事实和问题 1 prog x like wang x 2 x lang x prog x 3 lang C 第三步应用推理规则进行推理lang y prog y 全称固化lang C lang y prog y prog C 假言推理prog C prog x like wang x like wang C 假言推理因此王程喜欢C这门课 自然演绎推理应用 已知如下事实 1 凡是容易的课程小王 Wang 都喜欢2 C班的课程都是容易的3 ds是C班的一门课程求证 小王喜欢ds这门课程证明第一步定义谓词Easy x x是容易的Like x y x喜欢yC x x是C班的一门课程第二步用谓词表示已知事实和问题 1 Easy x Like Wang x 凡是容易的课程小王都喜欢 2 x C x Easy x C班的课程是容易的 3 C ds ds是C班的课程 4 Like Wang ds 小王喜欢ds这门课程 待证明的问题 自然演绎推理应用 第三步应用推理规则进行推理 x C x Easy x C ds Easy ds C ds C ds Easy ds Easy ds 假言推理Easy ds Easy x Like wang x Like wang ds 变量用ds代替 假言推理因此王程喜欢C这门课 全称固化 自然演绎推理特点 一般来说 自然演绎推理由已知事实推出的结论可能有很多 只要其中包含了需要证明的结论 就认为问题得到了解决优点证明过程自然 易于理解有丰富的推理规则可用缺点容易产生组合爆炸 推理过程中得到的中间结论一般按指数规律递增对于复杂问题的推理不利 甚至难以实现 3 5归结演绎推理 定理证明的实质是对前提P和结论Q 证明P Q的永真性 由P Q的谓词公式可知 如果前件P满足则一定得出Q 只要证明P Q是永真的则可知 从P可推出Q成立 要证明P Q处处永真 有时比较困难 也就是当论域有限 解释有限时可以逐一证明其正确性 当论域无限解释无限时 就无法证明其永真性 这时 必须用反证法 要证明P Q永真 只要证明 P Q 是永假的也可以 P Q P Q P Q即 证明P Q永假性即可 在实际证明中 常将谓词公式变成子句的办法进行证明 3 5 1子句 定理证明的实质是对前提P和结论Q 证明P Q的永真性 由P Q的谓词公式可知 如果前件P满足则一定得出Q 只要证明P Q是永真的则可知 从P可推出Q成立 要证明P Q处处永真 有时比较困难 也就是当论域有限 解释有限时可以逐一证明其正确性 当论域无限解释无限时 就无法证明其永真性 这时 必须用反证法 要证明P Q永真 只要证明 P Q 是永假的也可以 P Q P Q P Q即 证明P Q永假性即可 在实际证明中 常将谓词公式变成子句的办法进行证明 3 5 1子句 续1 文字 在谓词逻辑中把原子谓词公式及其否定式统称为文字 例如R x P x f x Q x g x 原子谓词公式 单个谓词公式或其否定式称为原子谓词公式 例如 A x A x 字句定理 任何文字的析取式称为子句 例如P x f x Q x g x 空子句不包含任何文字的子句一般记为 nil或NIL空子句是永假的子句集由子句或空子句所构成的集合例如P x P x Q y P y Q x 子句集合取公 范 式下的各析取式的集合例如P x P x Q y P y Q x 的子句集是 P x P x Q y P y Q x 在谓词逻辑中 任何一个谓词公式都可以通过应用等价关系及推理规则 化成相应的子句集 下述用一个例子 介绍将谓词公式化成子句集的步骤 x y P x y y Q x y R x y 3 5 1子句 续2 谓词公式化成子句集步骤 1 消蕴涵符 双条件理论根据P Q P Q PQ P Q P Q 上式变成如下形式 x y P x y y Q x y R x y 2 利用等价关系将 符号移到紧靠谓词的地方理论根据 P Q P Q 或 P P P Q P Q x P x x P x x P x x P x 上式变成下式 x y P x y y Q x y R x y 3 重新命名变元名 使不同量词约束的变元有不同的名字上式变成如下形式 x y P x y z Q x z R x z 4 消去存在量词这里存在两种情况 1 存在量词不出现在全称量词的辖域内 如 x P x 此时我们只要用一个新的个体常量替换受该存在量词约束的变元 即可消去存在量词 因为 若原公式为真 则总能找到一个个体常量 替换后仍使公式为真 也可理解为 此时存在量词的变元的取值不依赖于任何其它变量 并且 这个新的个体常量没有在谓词公式中出现过 即 x P x P a 4 消去存在量词 续 2 如果存在量词出现在全称量词的辖域内 如 x y P x y 此时对每一个x都有一个y与之对应 y的取值依赖于x 我们记为f x 称f x 为Skolem 斯格林 函数 用Skolem函数代替每一个存在量词量化的过程称为Skolem化 所以有 x y P x y Skolem化后 x P x f x 不同变元对应的Skolem函数的函数符号要不同 更一般形式 存在量词位于多个全称量词的辖域内 如 x1 x2 x3 xn y P x1 x2 x3 xn y 此时需要用Skolem函数f x1 x2 x3 xn 4 消去存在量词 续 替换受该存在量词约束的变元 才能消去存在量词 即 x1 x2 x3 xn P x1 x2 x3 xn f x1 x2 x3 xn 对于上例而言 存在量词 y 及 z 都位于 x 的辖域内 所以都要用Skolem函数来替换 设替换y与z的Skolem函数分别为f x 和g x 则上例变为 x P x f x Q x g x R x g x 5 全称量词全部移到公式的左边对于在公式内部的全称量词都要把其移到公式的左边 x P x f x Q x g x R x g x 6 用等价关系P Q R P Q P R 把公式化成斯格林标准形 Skolem标准形 x1 x2 x3 xn M其中M是子句的合取式 称为Skolem 斯格林 标准形的母式 则上例变为 x P x f x Q x g x P x f x R x g x 7 消去全称量词 则上式变为 P x f x Q x g x P x f x R x g x 8 对变元更名 使不同子句中的变元不同名上式改写成 P x f x Q x g x P y f y R y g y 9 消去合取词得子句集消去合取词 上例变为子句集 P x f x Q x g x P y f y R y g y 显然 在子句集中各子句之间是合取关系 如果谓词公式是不可满足的 则子句集也一定不可满足 反之亦然 两者在不可满足性上是等价的 定理 设有谓词公式P 其标准形的子句集为S 则P不可满足的充要条件是 S是不可满足的 判断子句集的不可满足性 需对个体域上的一切解释逐个地进行判断 任何一个解释都是不可满足时 才能判定该子句是不可满足的 这在实际中难以实现 在实际中 如果选取个体域的某一有限部分 在此个体域中处处不可满足 则认为子句集处处不可满足成立 就简单多了 海伯伦构造了一特殊的域 并证明只要对这个特殊的域上的一切解释进行判定 就可知子句集是否不可满足 这个特殊的域就是海伯伦域 3 5 2海伯伦理论 Herbrand 按照下述方法构成的个体域称为海伯伦域 在此域中子句处处不可满足 则认为子句集处处不可满足 定理 设S为子句集 则按下述方法构造成的域H 称为海伯伦域 简记为H域 也有记为H S 1 令H0是S中所有个体常量的集合 若S中不包含个体常量 则令H0 a 其中a为任意指定的一个个体常量 2 Hi 1 Hi f x1 x2 xn f是S中出现的所有n元函数 3 例1 求子句集S的H域 看起来 海伯伦全域很庞大 实际上 它至多是一个可列集 对于不出现函数的任何子句集S H S 仅有一个或有限个常量组成 从下述举例可以看出 例2 求子句集S P x Q f x R g y 的H域 解 H0 a H1 a f a g a H2 a f a g a f f a f g a g f a g g a 例3 求子句集S P x Q y R y 的H域解 由于无常量又无函数 指定a为个体常量 从而得到 H0 H1 H2 H a 有前面求海伯伦全域可知 全域H实际上可以认为有相应子句集中所有常量和函词组成的各种可能的组合 基表达式 基例与H基定义项 原子 文字 子句 以及他们各自的集合 统称为表达式 不出现变量表达式称为基表达式 不出现变量的项称为基项 基原子 基子句 基子句集等分别是不出现变量的原子 子句和子句集 定义如果用H域中的元素代换子句中的变元 则所得的基子句称为子句的一个基例 其中的谓词称为基原子 由基子句构成的集合称为基子句集 另一种讲法 子句集 子句 用域中的元素代替变元而得到的基子句称为子句的一个基例 定义 子句集中所有基原子构成的集合称为原子集 海伯伦基 H基 记B S 由S的谓词符号和H域中的基项组成的全体基原子的集合 B S P t1 tn P是 中出现的谓词符号 例设S P x Q a R f y 求S的海伯伦全域H S H基H S 和第一个子句的基例 H S a f a f f a f f f a B S P a Q a R a P f a Q f a R f a P f f a Q f f a R f f a 例设S P x Q a R f y 求S的海伯伦全域H S H基H S 和第一个子句的基例 H S a f a f f a f f f a B S P a Q a R a P f a Q f a R f a P f f a Q f f a R f f a 第一个子句 P x Q a 的基例有 P a Q a P f a Q a P f f a Q a 子句集的H 解释 子句集S在海伯伦全域 上的一个解释称为H 解释 是指对于子句集 中出现的常量 函数和谓词符号按下述方法进行赋值 对每个常量指派常量本身 对每个n元函数指派一个从 n到 的映射 对每个n元谓词指派一个从 n到真值 的映射 注意 与一般论域D的解释不同 H 解释对常量和函数的指派是固定的 不随解释的变化而变化 H 解释中可以随意指派的只有谓词的真值指派 主要是为了方便公式的判定 定理 谓词公式F的子句集为S 则F永假的充要条件是S不可满足定理 子句集S不可满足的充要条件是S对H域上的一切解释均为假 定理 子句集S不可满足的充要条件是存在一个有限的不可满足的基子句集S 该定理称为海伯伦定理 对于字句集S在任一论域D上的一个解释I 都可以构造一个H 解释I 与之对应 例 设谓词公式S P x Q y f y a D 1 2 S在D上的一个解释I定义为 af 1 1 f 1 2 f 2 1 f 2 2 P 1 P 2 Q 1 1 Q 1 2 Q 2 1 Q 2 2 21221TFFTFT 现在构造与I对应的H 解释I 首先给出S的海伯伦全域H S 以及S的基原子集B S H0 a H1 a f a a H2 a f a a f f a a a H3 a f a a f f a a a f f f a a a a H a f a f f a f f f a a H S a f a a f f a a a f f f a a 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 按解释I的常量和函数指派把B S 中每个原子的所有基项代换成D的某各值 再按I的真值指派给出相应基原子的真值 若指派a 2 f a a f 2 2 1f f a a a f 1 2 2确定原子集中各元素的取值P a P 2 FQ a a Q 2 2 TP f a a P f 2 2 P 1 TQ a f a a Q 2 f 2 2 Q 2 1 FQ f a a a Q f 2 2 2 Q 1 2 T Q f a a f a a Q f 2 2 f 2 2 Q 1 1 F这就是与I对应的H 解释I 即 I P a Q a a P f a a Q a f a a Q f a a a 海伯伦理论 海伯伦定理意义从理论上给出了证明子句集不可满足性的可行性及方法局限要在计算机上实现其证明过程却是很困难的鲁宾逊归结原理1965年提出 使机器定理证明变为现实 由谓词公式化成子句集的过程可知 在子句集中子句之间是合取关系 其中只要有一个子句不可满足 则这个子句集就不可满足 另外我们前面已指出过 空子句是不可满足的 因此 若一个子句集中包含空子句 则这个子句集一定是不可满足的 这就是鲁宾逊的归结原理的基本立足点 鲁宾逊的归结原理基本思想方法是 检查子句集S中是否包含空子句 若包含 则S不可满足 若不包含 就要在子句集中选择合适的子句进行归结 一旦能归结出空子句 就说明子句集S是不可满足的 3 5 3鲁宾逊归结原理 1 命题逻辑中的归结原理定义设C1与C2是子句集中的任意两个子句 如果C1中的文字L1与C2中的文字L2互补 那么从C1和C2中分别消去L1和L2 并将二个子句中余下的部分析取 构成一个新子句C12 则称这一过程为归结 称C12为C1和C2的归结式 称C1和C2为C12的亲本子句 设子句C1 L C1 C2 L C2 则归结式C12 C1 C2 C1和C2为C12的亲本子句 互补文字的定义若P是原子谓词公式 则称P与 P是互补文字 P Q Q P Q NIL 举例设C1 P Q RC2 P S则归结式C12为C12 Q R S设C1 PC2 P则归结式C12为C12 NIL归结过程的树形表示例如C1 P QC2 QC3 P求C1C2C3的归结式C123 一 命题逻辑中的归结原理 定理 归结式C12是其亲本子句C1和C2的逻辑结论 C12的值是C1合取C2的值 即 C1 C2 C12是一种推理规则证明 设C1 L C1 C2 L C2 通过归结可得到 C12 C1 C2 由定义知 C1和C2是C12的亲本子句 L C1 C1 LC1 L C1 L L C2 L C2 C1 C2 C1 L L C2 根据假言三假论 P Q Q R P R 得到 C1 L L C2 C1 C2 C1 C2 C1 C2 C12 C1 C2 C12推论1 设C1与C2是子句集S中的两个子句 C12是它们的归结式 若用C12代替C1和C2后得到新子句集S1 则由S1的不可满足性可推出原子句集S的不可满足性 推论2 设C1与C2是子句集S中的两个子句 C12是它们的归结式 若把C12加入S中 得到新子句集S2 则S与S2在不可满足的意义上是等价的 从前面的推论中可以看出 要证明子句集S的不可满足性 只要对其中可进行归结的子句进行归结 并把归结式加入子句集S或用归结式替换它的亲本子句 而后 对新子句集证明不可满足性即可 在归结的过程中能得到空子句 立即可得到原子句集S是不可满足的结论 谓词逻辑与命题逻辑相比是含有变元 需选用最一般合一对变元进行代换 然后才能进行归结 定义设C1与C2是两个没有相同变元的子句 L1和L2分别是C1和C2中的文字 若 是L1和L2的最一般合一 则称C12 C1 L1 C2 L2 为C1和C2的二元归结式 L1和L2称为归结式的文字 二 谓词逻辑的归结原理 例1设C1 P a Q x R x C2 P y Q b 给出C1和C2的归结式 解若选L1 P a L2 P y 则 a y 是L1与 L2的最一般合一 根据定义 可得 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 Q x R x Q B 本例的一种归结树 P A Q x R x P y Q B Q x R x Q B A y 若选L1 Q x L2 Q b b x 则可得 C12 P a Q b R b Q b P y Q b Q b P a R b P y P a R b P y P a R b P y 另一种归结树 P a Q x R x P y Q b P a R b P y b x 解由于C1与C2有相同的变元 不符合定义的要求 为了进行归结 需修改C2中变元的名字 令C2 P B R y 此时 对C1和C2有L1 P x L2 P B L1与 L2的最一般合一 B x 则C12 P B Q A P B P B R y P B Q A R y Q A R y 例2设C1 P x Q A C2 P B R x 写出C1和C2的归结式 归结树 P x Q A P B R y Q A R y B x 定义 子句C1和C2的归结式是下列二元归结式之一 1 C1与C2的二元归结式 2 C1与C2的因子C2 2二元归结式 3 C1的因子C1 1与C2二元归结式 4 C1的因子C1 1与C2的因子C2 2二元归结式 三 归结反演 归结原理给出了证明子句集不可满足性的方法 归结反演就是用子句归结的方法证明Q是前提F的逻辑结论 定理 为 1 n的逻辑结论 当且仅当 1 2 3 n 是不可满足的 这就是归结反演的理论依据 定理 设有谓词公式F 其标准形的子句集为S 则F不可满足的充要条件是 S是不可满足的 也就是说 在不可满足的意义上 公式 1 2 3 n 与其子句集是等价的 因此 我们可用归结原理进行定理证明 或在机器上实现定理的自动证明 归结反演步骤 设F为已知前提的公式集 Q为目标公式 结论 用归结反演证明Q为结论的步骤是 否定Q 得到 Q 把 Q并入到公式集F中 得到 F Q 把公式集 F Q 化为子句集S 对子句集S应用归结原理 寻找最一般合一 对子句进行归结 并把每次归结得到的归结式都并入S中 如此反复进行 若出现了空子句 则停止归结 此时就证明了Q为真 例 已知 F x y A x y B y y C y D x y G x C x x y A x y B y 求证 G是F的逻辑结论证明 把F和 G化为子句集 1 A x y B y C f x 2 A u v B v D u f u 3 C z 4 A a b 5 B b 归结如下 6 A x y B y 由 1 与 3 归结 z f x 7 B b 由 4 与 6 归结 a x b y 8 nil由 5 与 7 归结所以 G是F的逻辑结论 用归结树表示如下 对前例注释 证明第一步 把F化为子句集1 消 x y A x y B y y C y D x y 2 深入 x y A x y B y y C y D x y 3 换名 x y A x y B y z C z D x z 4 消 x y A x y B y C f x D x f x 5 前束 x y A x y B y C f x D x f x 已知F x y A x y B y y C y D x y G x C x x y A x y B y 求证G是F的逻辑结论 对例3 5 11注释 续1 6 变合取 x y A x y B y C f x A x y B y D x f x 7 消 A x y B y C f x A x y B y D x f x 8 换名 A x y B y C f x A u v B v D u f u 9 消 得到F的子句 1 A x y B y C f x 2 A u v B v D u f u 第二步把 G化为子句集 x C x x y A x y B y 1 消 x C x x y A x y B y 2 深靠 x C x x y A x y B y x C x x y A x y B y x C x x y A x y B y x C x x y A x y B y 3 换名 z C z x y A x y B y 4 消 z C z A a b B b a b是常量5 前束 z C z A a b B b 6 合取不变7 消 C z A a b B b 8 换名不变9 消 C z A a b B b G的子句 3 4 5 对例3 5 11注释 续2 第三步用归结树描述归结过程 1 A x y B y C f x 3 C z A x y B y f x z 4 A a b a x b y B b 5 B b NIL 第四步出现空子句 证明G是F的逻辑结论 归结反演应用 证明第一步 把已知条件和要求证问题用谓词表示出来设用P x 录取x 则已知F 1 P a P b P c 2 P a P b P c 3 P b P c 求证G P c 已知某公司招聘工作人员 a b c三人应试 经面试后公司表示如下想法 1 三人中至少录取一人 2 如果录取a而不录取b 则一定录取c 3 如果录取b 则一定录取c求证公司一定录取c 归结反演应用 第二步把F和 G化为子句集F 1 P a P b P c 2 P a P b P c 3 P b P c G P c 第三步用归结树描述归结过程 1 P a P b P c 2 P a P b P c P b P c 3 P b P c P c 4 P c NIL 第四步出现空子句 证明公司一定录取C 应用归结原理求解问题的答案步骤如下 1 把已知前提用谓词公式表示出来 并且化为相应的子句集 设该子句集的名字为S 2 把待求解的问题也用谓词公式表示出来 然后把它否定并与谓词ANSWER构成析取式 ANSWER是一个为了求解问题而专设的谓词 其变元必须与问题公式的变元完全一致 3 把此析取式化为子句集 并且把该子句集并入到子句集S中 得到子句集S 4 对S 应用归结原理进行归结 5 若得到归结式ANSWER 则答案就在ANSWER中 四应用归结原理求取问题的答案 基于归结反演的问题求解举例 例设A B C三人中有人从不说真话 也有人从不说假话 某人向这三人分别提出同一个问题 谁是说谎者 A答 B和C都是说谎者 B答 A和C都是说谎者 C答 A和B中至少有一个是说谎者 求谁是老实人 谁是说谎者 解首先 定义谓词T x 表示x说真话 如果A说的是真话 则有T A T B T C 如果A说的是假话 则有 T A T B T C 对B和C说的话作相同的处理 可得 T B T A T C T B T A T C T C T A T B T C T A T B 把上面这些公式化成子句集S 1 T A T B 2 T A T C 3 T A T B T C 4 T B T C 5 T C T A T B 6 T C T A 7 T C T B T A T B T C T A T B T C T B T A T C T B T A T C T C T A T B T C T A T B 下面首先求谁是老实人 把目标公式 x T x 的否定式 x T x 与ANSWER x 组成的析取式化为子句并入S得到S1 即S1比S多如下一个子句 8 T x ANSWER x 应用归结原理进行归结 求谁是老实人的归结树 由ANSWER C 可得C是老实人 即C从不说假话 除此之外 无论如何对S1进行归结 都推不出ANSWER B 和ANSWER A 下面来证明A和B不是老实人 归结反演 设A不是老实人 则有 T A 把它的否定式T A 并入到S中 得到子句集S2应用归结原理对S2进行归结 证明A不是老实人的归结树 证明B不是老实人的归结树 例 某村农民张某被害 有四个嫌疑犯A B C D 公安局派出五个侦察员 他们的侦察结果分别是 A B之中至少有一人作案 B C中至少有一人作案 C D中至少有一人作案 A C中至少有一人与此案无关 B D中至少有一人与此案无关 所有侦察结果都是可靠的 求出谁是罪犯 解 设谓词C y 表示y为罪犯对于第一个侦察员 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是罪犯 1 C A C B 2 C B C C 3 C C C D 4 C A C C 5 C B C D 6 C U ANSWER U 归结反演引起的反思 对子句集进行归结反演时 由于事先不知道哪两个子句可以进行归结 更不知道通过对哪些子句对的归结可以尽快地得到空子句 因而必须对子句集中的所有子句逐对地进行比较 对任何一个可归结的子句对都进行归结 也就是说 在子句集中采用了类似广度优先搜索方法来搜索亲本子句 因此归结的效率很低 3 6归结策略讨论 要解决的问题如何能尽快找到归结子句对控制策略的目的归结点尽量少控制策略的原则给出控制策略 选择合适的子句方可做归结避免多余的 不必要的归结式出现或者说 少做些归结仍能导出空子句控制策略的分类删除策略删除某些无用的子句 以缩小搜索范围限制策略对参加归结的子句进行某些限制 启发信息 以减