动机
一条适用所有对象的规则,不应要求为每个名字另写副本。由“所有已检查包裹均放行”与“A 已检查”,推理程序应找到合适代换。遇上嵌套项及多个变量时,所有相同变量都必须换成同一项,不能逐个出现位置独立猜测,否则所得“证明”可能根本不受原前提支持。
合一处理这个一致代换问题,归结则用它消去互补文字。把两者分开,有助理解为何每步可靠的推理程序仍可能永不停止:局部步骤保持后果,并不表示可能步骤只有有限多个。本节完整证明有限项合一、一阶归结可靠性,以及有限命题片段的归谬完备性;每个保证都有明确范围。
读者应先熟悉解释、量词与语义蕴涵。
定义
定义 4.1.1
(项与代换)
有限项可以是变量、常数,或由有限项组成的 。合一把函数符号看成语法构造器;不同构造器不会因代入而相同,即使某个特定解释碰巧给它们相同值。代换 把有限多个变量换成项,并穿过所有构造器延伸;同一变量的各次出现一律一致。合成约定为 ,所以次序不能倒转。
定义 4.1.2
(合一代换与最一般合一代换)
方程集 的合一代换,令每对项在语法上完全相同。最一般合一代换,简称 MGU,是合一代换 ,使任意其他解 在原方程变量上都能写成 。它不必有唯一写法;重新命名未受限制的变量,可得到等价答案。
定义 4.1.3
(子句与归结)
文字是原子或其否定;子句是文字的析取,其中变量隐含全称量化。空子句在任何解释都假。结合两子句之前,要把变量重新命名至两边互不相交,因为两个全称量词各自独立。对原子 ,若 合一它们,通常选 MGU,便由 及 归结出 。
一般公式转子句时,要消去蕴涵、把否定往内移、重新命名束缚变量并分配连接词。存在见证尤其要小心: 可用新函数 取代 ,在扩充语言保持可满足性。原模型为每个 选见证,扩充模型则在忘掉函数后给原公式见证。这不是原语言中的逻辑等价,也不能一般地换成同一常数。此处使用非空论域的普通经典语义及通常的见证选择设定。
定理/命题
定理 4.1.4
(用方程简化合一有限项)
对有限个有限一阶项方程,下列程序会终止,无解时报失败,有解时构造 MGU:删除 ;把同构造器方程按分量分解;把变量方程定向为 ;不同构造器或 真正出现在 内部时失败;其余情况以 全面替换 并记录绑定。依应用次序合成所有已记录绑定。
定理 4.1.5
(归结可靠,有限命题归谬完备)
使用真正合一代换的一阶归结步骤可靠,即父子句蕴涵归结子句。对有限原子上的有限命题子句,系统地以所有正负子句对消去变量,可判定可满足性;当且仅当原集合不可满足时导出空子句。下述有限证明本身不证任意一阶实现完备。
证明思路
证明
(方程简化的正确性与终止性)
删去恒等式及分解 ,准确保留所有语法解。不同构造器不能靠换变量变成相同。若 真正在 内,任何有限代换后,右边仍包含 作真子树,比它大,不能与它相等。这就是出现检查;容许循环无穷项将是另一种模型。
对合法方程 ,任何解都必须令 取 经该解代换后的值。因此把此绑定传到其余方程,不会失去任何解;反过来,变换后方程的解也可经此绑定延伸为旧解。逐步重复这个分解性质,得任意原解皆为记录代换的实例。成功终止时已无剩余方程,所以记录本身是解,且最一般。
终止不能只说“式子变小”,因代换可能令式子变大。用字典序比较三个自然数:未解系统中的相异变量数目、项符号总数,以及左边非变量而右边是变量的 方程数。消去严格减第一量,即使代换增大第二量也无妨;分解与删恒等式不增第一量而减第二量;定向只转此种 ,保持前两量而减第三量。此良基量度排除无穷运行。
证明透视
出现检查是一条数学界线
若有有限树解,该树便要包含自己作真部分,与有限大小矛盾。接受循环图的程序正在解另一个问题;它的答案不能默认为本定理中的有限项代换。这个限制来自对象的定义,并非无关紧要的程序习惯。
证明
(归结步骤的可靠性)
证归结可靠性:满足全称父子句的模型,也满足每个代换实例。合一后,所选原子一致;假如归结子句所有剩余文字都假,第一父句会逼该原子真,第二父句会逼它假,矛盾。因此所有父句模型都满足归结子句。预先把变量分开,避免意外把两个独立量词当成同一变量。
证明
(消去一个原子保持可满足性)
有限完备性可用消元证明。先删恒真句与重复文字,再消去原子 ,把相关子句写成 、;余式不含 的任一符号。保留无关句,加入所有 ,再删恒真句。可靠性给旧模型必满足新句。反过来,取满足新句的其余原子赋值。某个 假会要求 真;某个 假会要求 假。两要求不可能同时出现,否则对应归结子句也假。按唯一要求选 ,没有要求则任选,便延伸成旧模型。因此消元双向保持可满足性。对有限原子数归纳,最后只剩恒真句或空子句,故不可满足恰好导出空句。
证明透视
扩展一步为何需要每一个归结式
容易的方向是可靠性:每个归结式都被蕴涵,所以旧集合的模型也满足新集合。真正的想法在逆向。在新集合的模型中,余式 为假会迫使 为真,余式 为假则迫使 为假。这两项要求不会同时出现,因为子句 属于新集合,若两者皆假它就会是假的。所以归结式恰好是使 所受要求保持一致的子句;缺少任何一对 ,都可能留下无法扩展的模型。舍弃恒真式没有影响,因为它们处处为真;原子个数有限只用于重复这一步,直到没有原子剩下。
例题详解
例题 4.1.6
(MGU 需要合成代换)
合一 与 ,分解得 、。先绑定 ,再绑定 ,后者也要传入先前 的像,得 。两原子直接代入都成为 。只记 而不说后续合成,是未完成的答案;其他无关变量无须限制。
概念视角结构
按一般程度排序的合一子
若存在代换 使 ,记作 ,即 是 的一个实例。可解问题的全体合一子在这个预序下构成一个集合,而 MGU 就是其中的最小元:它位于每个合一子之下,即每个合一子都是它的实例。任意两个 MGU 互为对方的实例,只相差变量改名。对 与 , 与 都是 MGU;合一子 则是第一个 MGU 后接 。
例题 4.1.7
(以全称规则归谬)
子句为 、、。首两句以 归结得 ,再与第三句得空子句。因此原规则及事实蕴涵 ,因加入其否定便不一致。这不表示原来一致的知识库蕴涵语言中所有原子;矛盾只用来证指定后果。
例题 4.1.8
(消元可得矛盾,也可重建模型)
、、、 消去 得 ,再与 归结得 ,最后得空句。若移除 ,可取 假、 真满足消元系统。首个原句要求 真,这也满足第二句,于是重建原模型。延伸论证不是只说“有解”,而能实际给赋值。
常见错误
反例模式
不能各次出现独立匹配
不同常数 下, 与 无法合一,因同时要求 、。把第一个出现配 、第二个配 ,并不是代换。修正方法是使用共同方程系统,全面传播每个绑定。
常见错误
(混淆可靠性、完备性与终止)
可靠性、归谬完备性与终止各不相同。有限命题消元会终止,但子句数仍可指数增长。有函数符号的一阶语言可产生无穷多基项,所以“试所有实例”不是有限判定算法。适当公平的归结系统配合因子化等规则,有更广的归谬完备性结果;本节有限证明并未提供该结果的证明。一直重试无关子句的任意策略,也不自动享有它。
常见错误
(以为等号已内置于归结)
若等号指真正相等,普通谓词归结不会自动提供等者代换、函数同余等性质,须有相等专用推理系统或合适公理。限时内找不到证明,也不等于找到反模型。精确有限推论与受资源限制的搜索,不能标上同一种确定性。
常见错误
(归结前没有把变量改名分开)
子句 与 合起来不可满足: 给出 ,而 给出 。若不改名,直接合一 与 ,会在出现检查失败,找不到归结式。把第二个子句改名为 后,MGU 就得到空子句。
总结
合一强制共享变量承诺,对有限项给最一般代换。归结保持后果地消去互补实例。有限命题消元完备,关键是任何缩减模型都能逐步延伸回原模型。无穷项空间、公平策略、因子化及相等,各需要额外分析;一步可靠不等于整个程序已解决它们。
练习
快速检查
(求 与 的 MGU,直接代入验证,指出自由变量。)
把原子的方程拆成各分量的方程,分解至每条方程一侧是变量。
解答 · 答案
方程为 、、。分解中式与末式一致,得 ,而 不受限制。两原子同成 。其他解只能再选 的值,并把同值放进 ,验证最一般性。
快速检查
(解释 与 为何无有限项合一,导出触发出现检查的方程。)
把第一个代换代入第二条方程,看变量现在出现在哪里。
解答 · 答案
有 、,把前者代后者得 。定向为 ,右边真正包含 ,故出现检查失败。循环式不是有限项解。
快速检查
(从 消去 ,判断可满足性并重建原模型。)
按 的正负号分组,作出所有正负配对的归结式,并丢弃恒真式。
解答 · 答案
正余式为 ,负余式为 ,得归结句 及恒真句 。删恒真句,取 真;第三原句再要求 真,所有原句均满足。得到单文字子句与得到空子句不同。
快速检查
(要求 及 ,用两元素模型说明把 换成 为何可改变可满足性。)
试试 为相等的两元素模型,再看常数版本强制了什么。
解答 · 答案
两个指定句子与原句可在 、 为相等时成立,每个对象见证自己。常数替换配合明确的相等公理,却要求所有对象等于同一 ,与两对象不同矛盾。若没有该公理,无限制谓词 可关联所有元素对,只选一个相等解释不足以证不可满足。新函数 能让见证随 变,保留原可能性;普通谓词归结仍非自动内置相等推理。