合取范式(CNF)是逻辑公式的一种标准表示形式,即若干子句的合取,其中每个子句都是若干文字的析取。在命题逻辑中,文字是命题变量或其否定。因此,CNF 公式就是“析取式的合取”,例如:
经典命题逻辑中的每个公式都有一个与之逻辑等价的 CNF 公式,不过,在不引入额外变量的情况下,转换所得公式的规模可能呈指数级增长。CNF 是布尔代数、自动定理证明以及布尔可满足性问题算法中的核心表示形式。
定义与约定
命题逻辑中的 CNF 公式具有如下通式:
其中,每个 都是一个文字。正文字是变量 ,负文字则是其否定 。
如果一个真值赋值使某个子句中的至少一个文字为真,就称该赋值满足这个子句。如果它满足每个子句,就称它满足整个公式。因此:
- 单个文字(如 )是一个单位子句,其本身也是一个 CNF 公式。
- 单个析取式(如 )是只含一个子句的 CNF 公式。
- 若干文字的合取(如 )是一个所有子句均为单位子句的 CNF 公式。
- 这样的公式在语法形式上不是 CNF,尽管它有等价的 CNF 表示。
以下两项约定使这一定义能够统一涵盖真值常量:
- 不含任何子句的合取为真。
- 不含任何文字的子句为假。
因此,包含空子句的 CNF 公式不可满足。
通常将子句视为文字的集合,将 CNF 公式视为子句的集合。这种处理忽略了顺序和重复: 与 表示同一个子句。同时包含 和 的子句是永真子句,将其从合取式中删除不会改变公式的真值。
CNF 是一种语法形式,并不保证公式简单或表示唯一。许多不同的 CNF 公式可以表示同一个布尔函数。
通过逻辑等价关系进行转换
标准转换过程首先消去合取、析取和否定以外的联结词:
然后利用德摩根定律和双重否定消去律,将否定向内移:
所得公式中的否定仅作用于变量,这种形式称为否定范式。
最后,运用析取对合取的分配律:
例如:
类似地:
这些变换在原有变量的每一种赋值下都保持真值不变。它们依赖于经典逻辑;尤其是,无限制地使用双重否定消去律在直觉主义逻辑中并不成立。
指数级增长
分配律可能产生大量子句。考虑:
其中所有 个变量均互不相同。运用析取对合取的分配律,得到:
共有 个子句,每个子句对应于从每一对变量中各选一个变量的一种选择方式。
对于这一族公式,如果要求 CNF 与原公式逻辑等价,并且只使用原有变量,那么这种规模增长就无法避免。因此,困难并非仅仅源于分配过程的实现效率低下:某些布尔函数虽然具有紧凑的公式,但在使用相同变量时,其 CNF 表示必然具有指数级规模。
主合取范式
典范合取范式,也称主合取范式,可以直接根据真值表构造。
先固定一个有限变量列表。对于使公式为假的每一种赋值,构造一个恰好只在该赋值下为假的子句:
- 如果某个变量在该赋值下为假,就在子句中加入它的正文字。
- 如果某个变量在该赋值下为真,就在子句中加入它的否定。
这些子句的合取就表示原来的布尔函数。
例如,假设 恰好在以下情形为假:
对应的子句是 和 ,因而得到:
这就是 与 的异或。
每个典范子句都恰好包含每个变量一次,通常称为极大项。对于固定的变量列表,忽略顺序和重复后,主合取范式是唯一的。普通 CNF 并非典范形式:它可以包含更短的子句,也可能紧凑得多。
与之对偶的表示是析取范式(DNF),即若干文字的合取式的析取。主析取范式由真值表中结果为真的行构造,而主合取范式则由结果为假的行构造。
借助辅助变量的紧凑编码
在可满足性应用中,通常只需保持满足赋值是否存在,而不要求在原有变量集上严格等价。因此,可以通过引入新变量来获得紧凑的编码。
典型方法是Tseitin变换,它源于格里戈里·蔡廷在 20 世纪 60 年代的工作。该方法为每个相关的复合子公式引入一个变量,并加入子句来表达该变量与对应子公式之间的关系。
例如,定义
可表示为:
类似地,
可表示为:
再用一个单位子句断言代表整个公式的变量为真。对于由元数有界的联结词构成的公式,所得子句数和文字出现总次数都与所表示公式的规模成线性关系。
逻辑等价与等可满足
如果 是原公式, 是完整的定义式编码,那么:
这里的存在量词表示,可以为辅助变量赋予适当的布尔值。
因此,原有变量的一个赋值满足 ,当且仅当该赋值可以扩展为满足 的赋值。不过,在二者全部自由变量构成的集合上,通常不能称 和 为逻辑等价的公式,因为 还对辅助变量施加了约束。
等可满足性是一个更弱的性质,只要求两个公式要么都有满足赋值,要么都没有满足赋值。完整的定义式编码保留的信息比这一较弱条件更多:原公式的每个满足赋值,都能唯一地扩展到所定义的辅助变量。其他保持可满足性的编码不一定具有这种唯一性,而这一点在统计满足赋值的数量时十分重要。
可满足性与受限子句类
CNF-SAT 问题询问给定的 CNF 公式是否存在满足赋值。它是 NP完全的。不过,对子句结构加以限制,可以显著改变计算复杂度。
| 类别 | 限制 | 可满足性判定 |
|---|---|---|
| 1-CNF | 每个子句至多包含一个文字 | 可在线性时间内求解 |
| 2-CNF | 每个子句至多包含两个文字 | 可在线性时间内求解 |
| 3-CNF | 每个子句至多包含三个文字 | NP完全 |
| 霍恩 CNF | 每个子句至多包含一个正文字 | 可在线性时间内求解 |
| 对偶霍恩 CNF | 每个子句至多包含一个负文字 | 可在线性时间内求解 |
这里的时间界以输入的总规模为衡量基准。
对于 2-CNF,子句 可以表示为以下蕴含式:
将这些蕴含关系构造成有向图后,可以通过其强连通分量判定可满足性:公式不可满足,当且仅当某个变量及其否定属于同一个强连通分量。
霍恩子句通常可以解读为一条规则。例如:
等价于:
这种结构支持高效的前向链推理过程。
根据所采用的约定,“-CNF”既可能指每个子句至多包含 个文字,也可能指每个子句恰好包含 个文字。应明确说明采用哪一种含义,尤其是在不允许重复文字时。
归结与 SAT 求解
CNF 特别适合归结。归结是一条推理规则,可以从
推出
其中, 和 代表其他文字的析取。
例如,对
进行归结,可得到 。推导出空子句就证明了不可满足性。命题归结具有反驳完备性:对于每个不可满足的有限子句集,都存在一个推导出空子句的归结推导。不过,这类推导的长度仍可能达到指数级。
实际使用的 SAT 求解器通过以下操作利用 CNF:
- **单位传播:**单位子句强制其文字为真;这一赋值可以简化其他子句,并产生更多单位子句。
- **分支:**当仅靠传播无法判定问题时,试探性地为某个变量赋值。
- **冲突分析与子句学习:**分析冲突,推导出一个子句,以排除相关的失败赋值。
- **回溯与重启:**求解器调整搜索过程,同时保留有用的已学习信息。
CNF 是形式验证、规划、配置以及约束编码中常用的目标表示形式。它本身并不能消除问题在最坏情况下固有的困难。同一问题采用不同编码,也可能使求解器的性能产生巨大差异。
一阶逻辑的子句形式
在一阶逻辑中,文字是原子公式或其否定,而不再仅仅是命题变量。例如:
就是一个一阶子句。
转换为子句形式通常包括:消去蕴含、将否定向内移、在必要时重命名约束变量,以及处理量词。斯科olem化通过引入表示见证的新常量或函数符号来消去存在量词。按照约定,子句集中剩余的变量均被理解为受全称量词约束。
例如:
经斯科勒姆化后得到:
所得子句为 ,其中 隐含地受全称量词约束。
斯科勒姆化保持的是扩充词汇表中的可满足性,而非原词汇表中的通常意义上的逻辑等价。这与命题逻辑中利用分配律进行的转换不同,后者在不改变变量集的情况下保持等价性。一阶归结还需要通过合一来匹配不同子句中的项。