动机
一个逻辑表达式可以有多种写法,却在每种情况下表达相同判断。真值表把这种含义逐行列清楚,子句形式则便于系统寻找满足赋值。不过这些表示的大小不一定相近:直接列出的表可能比原公式大得多,甚至呈指数级增长。
本节构造两种完全等价的范式,证明归结消元恰好保留可扩张的赋值,再谨慎引入辅助变量。紧凑编码可以保留是否存在解,却不一定是同一组变量上的等价公式。
赋值与等价
定义 12.1.1
(赋值、等价、可满足与有效)
固定一个有限的互不相同的布尔(Boole)变量列表。赋值为每个所列变量指定假或真。连接词 、、 按通常的真值规则计算;常量 和 分别表示假和真。定义蕴含与双条件为
若对出现在两个公式中任一处的所有变量的每个赋值,公式 、 取值相同,就称它们等价,记为 。至少有一个赋值使公式为真时称其可满足;每个赋值都使其为真时称其有效。因此 当且仅当 有效。
把较大公式中的子公式替换为一个等价式,较大公式的值不变:可对周围连接词作归纳证明。
定义 12.1.2
(文字、子句、项与范式)
文字是变量或变量的否定。子句是有限多个文字的析取,项是有限多个文字的合取。合取范式(CNF)是子句的合取;析取范式(DNF)是项的析取。重复文字或重复子句可删去。一个子句若同时含变量和其否定,就恒真,可从合取中删去;一个项若同时含二者,就恒假,可从析取中删去。
空子句是 ,空项是 。零个子句的空合取是 ;零个项的空析取是 。这些约定也使无变量公式和消元边界一致。
定理 12.1.3
(每个真值表都有两种精确范式)
对所声明的 个变量上的任何公式,都可构造仅用同一列表变量且与原式等价的 DNF 和 CNF。规范 DNF 为每个取真的行构造一项,规范 CNF 为每个取假的行构造一个子句。总共有 行,包括 时的一行。
如何构造范式
证明
(逐行分离)
对每个赋值 ,构造一个项:在 下为真的变量正向出现,为假的变量取否定。该项恰好只在行 为真。把属于真行的项全部析取,结果就与原式有相同真值表。如果没有真行,使用空析取 。
构造 CNF 时则令子句恰在 为假:行中为真的变量取否定,为假的变量正向出现。把所有假行对应的子句合取。任何不同赋值都满足该假行对应的子句,所以结果恰好拒绝原式的所有假行。若没有假行,使用空合取 。当 时,唯一一行按情况产生空项或空子句。
证明透视
一行就是一次精确检验
这里只有一个想法:用一次检验就能分离出一行。由真行 构造的项是与 完全吻合的文字的合取,所以它在 为真,在其他行都为假:任何其他行至少在一个变量上与 不同,使相应文字为假。由假行构造的子句则使用相反的符号,所有文字在 取假,因此子句恰在该行为假;其他行在不同的变量上满足相应文字。符号相反,是因为合取只要一个文字失败就失败,而析取要所有文字都失败才失败。论证以真值表决定公式作结:把全部真行的项析取,或把全部假行的子句合取,就重现每一行。只用到变量列表有限这一点。
这个构造既证明存在,也给出明确算法,但可能写出多达 次文字出现。简短公式可能有更短的非规范范式;真值表构造只给上界,不声称表达式最短。反过来,任何必须显式输出大范式的算法都要支付输出成本,无论输入多短。
若要否定一个等价断言,只需给出两式取值不同的一个赋值;若用真值表证明等价,则必须检查每一行,包括只在其中一个公式出现的变量的赋值。这样,代数式的改写是否正确就成为可检验的语义问题。
常见恒等式 和 也可逐一检查相应两输入或三输入真值表的所有行。随后利用等价替换可在较大公式内应用。此类改写很有用,但某个分配步骤次序不保证结果最短。
归结与精确消元
定义 12.1.4
(归结式)
设 与 是子句,其中 、 均不含 。它们的归结式是子句 。
归结式由两个父子句蕴含:满足两个父子句的赋值必满足归结式,因为若 和 都为假,两个父子句就分别要求 为真和为假。
概念视角几何
子句是被禁止的子立方体
把 个赋值看作 维立方体的顶点。一个含 个文字、且文字取自不同变量的子句,恰好禁止使其所有文字为假的赋值,这些赋值构成 维子立方体;CNF 恰由避开所有被禁止子立方体的顶点满足。在这个图像中, 与 的归结式禁止 、 都为假的顶点,而每个这样的顶点已落在第一个父子句( 为假时)或第二个父子句( 为真时)所禁止的区域内。归结的可靠性就是说,新增的禁止区域已被两个旧区域覆盖。
定义 12.1.5
(消去一个变量)
给定 CNF,先删去恒真子句和重复文字。消去 时,保留所有不含 的子句,并对每个 与每个 的配对加入归结式。然后删除所有含 或 的子句,并删去恒真的归结式。如果正、负两族有一族为空,就没有配对。空子句必须保留。
定理 12.1.6
(归结给出存在量化投影)
对剩余变量的每个赋值,消元后的 CNF 为真,当且仅当存在一个 的取值使原 CNF 为真。因此消元保留可满足性;所有变量都消去后,原 CNF 不可满足当且仅当剩下空子句。
证明
(为被消去的变量选值)
正方向通过构造 的值证明。固定一个满足所有保留子句和归结式的剩余变量赋值。若某个正父子句的 为假,则每个负父子句的 都必须为真,否则它与该正父子句的归结式为假。令 为真:正父子句全部满足,负父子句则因各自的 满足。若没有任何正父子句的 为假,令 为假:正父子句靠其 满足,负父子句靠 满足。这也覆盖正族或负族为空的情形。
反过来,若某个 的值满足原 CNF,则所有保留子句和所有归结式都为真,因为每个归结式都由两个父子句蕴含。这证明逐赋值的投影结论。依次消去全部变量就保留是否存在模型。最后没有文字可用,剩余结果只能是空合取(真),或含有空子句的合取(假)。每个生成的归结式都是先前子句的逻辑后果;若生成空子句,其生成历史就是有限反驳证书。
证明透视
归结式是唯一的障碍
不显眼的一步,是把归结式读成选择 时唯一的障碍。令 为真可行,当且仅当每个负父子句的 都为真;令 为假可行,当且仅当每个正父子句的 都为真。两种选择都失败,只在某个正父子句的 为假、且某个负父子句的 为假时发生,这时它们的归结式 为假。、 不含 这个假设,保证它们的值不依赖 的选择。被删去的恒真归结式本来就为真;任何一侧的子句族为空时,相应的选择自动可行,所以证明不需要另外处理边界情形。
一对父子句也可能产生 这样的恒真归结式;删除它不会增加约束。最坏情况下,两两配对可能产生很多子句,所以这个证明没有给出一般 SAT 的多项式时间算法。变量消去次序会影响中间大小,但不会改变最终可满足性。
反例模式
同时对两个变量归结是不可靠的
声称:由 与 可以同时消去两对相反文字,推出空子句。赋值 使两个子句皆真,而空子句在任何赋值下都为假,所以这个推导不可靠。归结式的定义一次只对一个变量进行;这里 与 含有第二个变量,对 的归结式是恒真式 ,不带任何信息。
辅助变量保证的事情不同
设公式由一个有向无环表达式图表示,共有 个 AND、OR 或 NOT 门。为每个门引入一个全新变量,用子句强制该变量等于其门的计算值。例如 等价于
OR 和 NOT 同理使用常数个子句,再以单文字子句要求输出门为真。常量、文字作为输出及空门图可直接处理。在每门扇入为常数、只计门和使用到的输入引用时,子句数及文字出现数为 。
定理 12.1.7
(门编码在存在投影下是精确的)
设公式由有向无环的门图给出, 是由每个门的定义子句再加上要求输出门为真的单子句组成的 CNF。对原变量的每个赋值 ,恰有一个门变量赋值满足所有门定义子句;并且 有满足的扩张,当且仅当原公式在 下为真。
证明
(按拓扑顺序计算各门)
对于原变量的每个赋值,按拓扑顺序计算各门,为门变量给出恰好一个满足全部门定义的赋值。此时输出单子句为真,当且仅当原公式为真。反过来,任何满足编码子句的赋值都必须与这些门值一致。因此,原公式在某输入赋值下为真,当且仅当存在其扩张使新 CNF 为真。
这比整体上仅有可满足性等价更强,但并不表示对新增变量的任意赋值两个公式都等价。
反例模式
全新变量不能当成无条件替换
公式 和 都可满足,因而可满足性等价。但它们在合并后的变量上并不等价:令 真、 假便能区分。存在合适扩张是带量词的结论,不能任意指定新变量还声称等价。
例题
例题 12.1.8
(按行构造异或)
对于变量 ,异或在 和 两行取真。其规范 DNF 为 。假行是 与 ,得到规范 CNF 。
例题 12.1.9
(消去一个变量)
从 消去 ,得到单个子句 。若 和 均为假,原式要求 同时取两个值;否则可选一个值使两个子句都真。把 也计入赋值时,原式与结果并不等价:结果只记录是否存在合适的 。
例题 12.1.10
(完整反驳)
子句 、 和 在 上分别归结出 与 ,再在 上归结出空子句。所以原来三个子句没有满足赋值;这些归结步骤是可检查的推导,不只是搜索失败记录。
常见错误与范围
常见错误
(消元不是等价变换)
从 消去 得 。当 、 为真而 为假时,它为真,原公式却为假。消元保留的是存在合适 的值,而非 取每个固定值时原公式的值。
常见错误
(消元尚未完成就停下)
从 消去 ,保留 并加入归结式 。结果不含空子句,原来的子句却不可满足:要消去 之后才出现空子句。归结反驳能证明不可满足,但中途没有空子句并不能说明任何事情。
也不要因找到一个满足行就断言有效,更不要把 CNF 读成单个析取:只要有一个子句为假,CNF 就为假。
这里的构造针对有限命题公式与有限变量列表,不直接证明多项式 SAT 算法、一阶完备性或最小等价 CNF 的大小界。辅助门编码的输出大小对表达式图线性,但判定其可满足性仍是另一问题。
小结
真值表的行构造出只用原变量的等价 DNF 和 CNF。归结逐个消去变量,精确保留可扩张的赋值。全新门变量给出紧凑 CNF,其存在投影是原公式;若要断言等价,不能忽略新增变量的取值。
练习
快速检查
(写出变量为 时 的规范 CNF,并指出其假行。)
解答 · 答案
蕴含只在 真、 假时为假。其规范 CNF 是单个子句 ,恰在该行取假。
快速检查
(从 消去 。解释为什么无需加入归结式。)
解答 · 答案
没有含 的负父子句,所以没有配对,也没有归结式。删去两个正父子句并保留 。只要 为真,无论 如何取值都可令 真来满足原子句; 为假时任何 都无用。
快速检查
(空变量列表上的 的规范 DNF、CNF 是什么?从子句 和 消去 后剩下什么?)
解答 · 答案
空列表恰有一个赋值, 在该行取假。其规范 DNF 是空析取 ;规范 CNF 是一个空子句的合取,仍为 。单文字子句 与 归结得到空子句,消元后保留它。
快速检查
(在定义 的三个子句中, 为假时 唯一可取什么?为什么编码作为 上的公式不等价于 ?)
解答 · 答案
若 为假, 强制 为假;此时另两个子句无论 取什么值都成立。作为三个变量上的公式,门定义在 全假时为真,而 为假。要求输出为真的单子句才选择出门值为真的输入。