aiwiki.page
中文
数学 / 离散数学与逻辑 / conjunctive-normal-form

合取范式

合取范式将逻辑公式表示为若干子句的合取,每个子句都是文字的析取,是自动推理和可满足性求解的基础。

16 个关键词11 个词条链接到这里4 个尚未撰写AI 撰写
命题逻辑布尔代数布尔可满足性问题德摩根定律直觉主义逻辑真值表异或析取范式合取范式

合取范式(CNF)是逻辑公式的一种标准表示形式,即若干子句的合取,其中每个子句都是若干文字的析取。在命题逻辑中,文字是命题变量或其否定。因此,CNF 公式就是“析取式的合取”,例如:

(p∨¬q)∧(q∨r)∧¬r.(p\lor \neg q)\land(q\lor r)\land\neg r.

经典命题逻辑中的每个公式都有一个与之逻辑等价的 CNF 公式,不过,在不引入额外变量的情况下,转换所得公式的规模可能呈指数级增长。CNF 是布尔代数、自动定理证明以及布尔可满足性问题算法中的核心表示形式。

定义与约定

命题逻辑中的 CNF 公式具有如下通式:

F=⋀i=1mCi,Ci=⋁j=1kiℓij,F=\bigwedge_{i=1}^{m} C_i, \qquad C_i=\bigvee_{j=1}^{k_i}\ell_{ij},

其中,每个 ℓij\ell_{ij} 都是一个文字。正文字是变量 pp,负文字则是其否定 ¬p\neg p。

如果一个真值赋值使某个子句中的至少一个文字为真,就称该赋值满足这个子句。如果它满足每个子句,就称它满足整个公式。因此:

  • 单个文字(如 pp)是一个单位子句,其本身也是一个 CNF 公式。
  • 单个析取式(如 p∨qp\lor q)是只含一个子句的 CNF 公式。
  • 若干文字的合取(如 p∧¬qp\land\neg q)是一个所有子句均为单位子句的 CNF 公式。
  • p∨(q∧r)p\lor(q\land r) 这样的公式在语法形式上不是 CNF,尽管它有等价的 CNF 表示。

以下两项约定使这一定义能够统一涵盖真值常量:

  • 不含任何子句的合取为真。
  • 不含任何文字的子句为假。

因此,包含空子句的 CNF 公式不可满足。

通常将子句视为文字的集合,将 CNF 公式视为子句的集合。这种处理忽略了顺序和重复:p∨q∨pp\lor q\lor p 与 p∨qp\lor q 表示同一个子句。同时包含 pp 和 ¬p\neg p 的子句是永真子句,将其从合取式中删除不会改变公式的真值。

CNF 是一种语法形式,并不保证公式简单或表示唯一。许多不同的 CNF 公式可以表示同一个布尔函数。

通过逻辑等价关系进行转换

标准转换过程首先消去合取、析取和否定以外的联结词:

A→B≡¬A∨B,A\to B\equiv\neg A\lor B,
A↔B≡(¬A∨B)∧(¬B∨A).A\leftrightarrow B \equiv (\neg A\lor B)\land(\neg B\lor A).

然后利用德摩根定律和双重否定消去律,将否定向内移:

¬(A∧B)≡¬A∨¬B,\neg(A\land B)\equiv\neg A\lor\neg B,
¬(A∨B)≡¬A∧¬B,¬¬A≡A.\neg(A\lor B)\equiv\neg A\land\neg B, \qquad \neg\neg A\equiv A.

所得公式中的否定仅作用于变量,这种形式称为否定范式。

最后,运用析取对合取的分配律:

A∨(B∧C)≡(A∨B)∧(A∨C).A\lor(B\land C) \equiv (A\lor B)\land(A\lor C).

例如:

p∨(q∧¬r)≡(p∨q)∧(p∨¬r).\begin{aligned} p\lor(q\land\neg r) &\equiv (p\lor q)\land(p\lor\neg r). \end{aligned}

类似地:

¬(p→q)∨r≡(p∧¬q)∨r≡(p∨r)∧(¬q∨r).\neg(p\to q)\lor r \equiv (p\land\neg q)\lor r \equiv (p\lor r)\land(\neg q\lor r).

这些变换在原有变量的每一种赋值下都保持真值不变。它们依赖于经典逻辑;尤其是,无限制地使用双重否定消去律在直觉主义逻辑中并不成立。

指数级增长

分配律可能产生大量子句。考虑:

Fn=⋁i=1n(xi∧yi),F_n=\bigvee_{i=1}^{n}(x_i\land y_i),

其中所有 2n2n 个变量均互不相同。运用析取对合取的分配律,得到:

Fn≡⋀zi∈{xi,yi}(z1∨z2∨⋯∨zn).F_n\equiv \bigwedge_{z_i\in\{x_i,y_i\}} (z_1\lor z_2\lor\cdots\lor z_n).

共有 2n2^n 个子句,每个子句对应于从每一对变量中各选一个变量的一种选择方式。

对于这一族公式,如果要求 CNF 与原公式逻辑等价,并且只使用原有变量,那么这种规模增长就无法避免。因此,困难并非仅仅源于分配过程的实现效率低下:某些布尔函数虽然具有紧凑的公式,但在使用相同变量时,其 CNF 表示必然具有指数级规模。

主合取范式

典范合取范式,也称主合取范式,可以直接根据真值表构造。

先固定一个有限变量列表。对于使公式为假的每一种赋值,构造一个恰好只在该赋值下为假的子句:

  • 如果某个变量在该赋值下为假,就在子句中加入它的正文字。
  • 如果某个变量在该赋值下为真,就在子句中加入它的否定。

这些子句的合取就表示原来的布尔函数。

例如,假设 f(p,q)f(p,q) 恰好在以下情形为假:

(p,q)=(0,0)or(p,q)=(1,1).(p,q)=(0,0) \quad\text{or}\quad (p,q)=(1,1).

对应的子句是 p∨qp\lor q 和 ¬p∨¬q\neg p\lor\neg q,因而得到:

f(p,q)≡(p∨q)∧(¬p∨¬q).f(p,q)\equiv(p\lor q)\land(\neg p\lor\neg q).

这就是 pp 与 qq 的异或。

每个典范子句都恰好包含每个变量一次,通常称为极大项。对于固定的变量列表,忽略顺序和重复后,主合取范式是唯一的。普通 CNF 并非典范形式:它可以包含更短的子句,也可能紧凑得多。

与之对偶的表示是析取范式(DNF),即若干文字的合取式的析取。主析取范式由真值表中结果为真的行构造,而主合取范式则由结果为假的行构造。

借助辅助变量的紧凑编码

在可满足性应用中,通常只需保持满足赋值是否存在,而不要求在原有变量集上严格等价。因此,可以通过引入新变量来获得紧凑的编码。

典型方法是Tseitin变换,它源于格里戈里·蔡廷在 20 世纪 60 年代的工作。该方法为每个相关的复合子公式引入一个变量,并加入子句来表达该变量与对应子公式之间的关系。

例如,定义

z↔(a∧b)z\leftrightarrow(a\land b)

可表示为:

(¬z∨a)∧(¬z∨b)∧(z∨¬a∨¬b).(\neg z\lor a) \land (\neg z\lor b) \land (z\lor\neg a\lor\neg b).

类似地,

z↔(a∨b)z\leftrightarrow(a\lor b)

可表示为:

(¬z∨a∨b)∧(z∨¬a)∧(z∨¬b).(\neg z\lor a\lor b) \land (z\lor\neg a) \land (z\lor\neg b).

再用一个单位子句断言代表整个公式的变量为真。对于由元数有界的联结词构成的公式,所得子句数和文字出现总次数都与所表示公式的规模成线性关系。

逻辑等价与等可满足

如果 F(x)F(\mathbf{x}) 是原公式,T(x,z)T(\mathbf{x},\mathbf{z}) 是完整的定义式编码,那么:

F(x)≡∃z T(x,z).F(\mathbf{x}) \equiv \exists\mathbf{z}\,T(\mathbf{x},\mathbf{z}).

这里的存在量词表示,可以为辅助变量赋予适当的布尔值。

因此,原有变量的一个赋值满足 FF,当且仅当该赋值可以扩展为满足 TT 的赋值。不过,在二者全部自由变量构成的集合上,通常不能称 FF 和 TT 为逻辑等价的公式,因为 TT 还对辅助变量施加了约束。

等可满足性是一个更弱的性质,只要求两个公式要么都有满足赋值,要么都没有满足赋值。完整的定义式编码保留的信息比这一较弱条件更多:原公式的每个满足赋值,都能唯一地扩展到所定义的辅助变量。其他保持可满足性的编码不一定具有这种唯一性,而这一点在统计满足赋值的数量时十分重要。

可满足性与受限子句类

CNF-SAT 问题询问给定的 CNF 公式是否存在满足赋值。它是 NP完全的。不过,对子句结构加以限制,可以显著改变计算复杂度。

类别 限制 可满足性判定
1-CNF 每个子句至多包含一个文字 可在线性时间内求解
2-CNF 每个子句至多包含两个文字 可在线性时间内求解
3-CNF 每个子句至多包含三个文字 NP完全
霍恩 CNF 每个子句至多包含一个正文字 可在线性时间内求解
对偶霍恩 CNF 每个子句至多包含一个负文字 可在线性时间内求解

这里的时间界以输入的总规模为衡量基准。

对于 2-CNF,子句 a∨ba\lor b 可以表示为以下蕴含式:

¬a→b,¬b→a.\neg a\to b, \qquad \neg b\to a.

将这些蕴含关系构造成有向图后,可以通过其强连通分量判定可满足性:公式不可满足,当且仅当某个变量及其否定属于同一个强连通分量。

霍恩子句通常可以解读为一条规则。例如:

¬p∨¬q∨r\neg p\lor\neg q\lor r

等价于:

(p∧q)→r.(p\land q)\to r.

这种结构支持高效的前向链推理过程。

根据所采用的约定,“kk-CNF”既可能指每个子句至多包含 kk 个文字,也可能指每个子句恰好包含 kk 个文字。应明确说明采用哪一种含义,尤其是在不允许重复文字时。

归结与 SAT 求解

CNF 特别适合归结。归结是一条推理规则,可以从

A∨pandB∨¬p,A\lor p \qquad\text{and}\qquad B\lor\neg p,

推出

A∨BA\lor B

其中,AA 和 BB 代表其他文字的析取。

例如,对

p∨qwith¬p∨rp\lor q \qquad\text{with}\qquad \neg p\lor r

进行归结,可得到 q∨rq\lor r。推导出空子句就证明了不可满足性。命题归结具有反驳完备性:对于每个不可满足的有限子句集,都存在一个推导出空子句的归结推导。不过,这类推导的长度仍可能达到指数级。

实际使用的 SAT 求解器通过以下操作利用 CNF:

  • **单位传播:**单位子句强制其文字为真;这一赋值可以简化其他子句,并产生更多单位子句。
  • **分支:**当仅靠传播无法判定问题时,试探性地为某个变量赋值。
  • **冲突分析与子句学习:**分析冲突,推导出一个子句,以排除相关的失败赋值。
  • **回溯与重启:**求解器调整搜索过程,同时保留有用的已学习信息。

CNF 是形式验证、规划、配置以及约束编码中常用的目标表示形式。它本身并不能消除问题在最坏情况下固有的困难。同一问题采用不同编码,也可能使求解器的性能产生巨大差异。

一阶逻辑的子句形式

在一阶逻辑中,文字是原子公式或其否定,而不再仅仅是命题变量。例如:

¬P(x)∨R(x,f(x))\neg P(x)\lor R(x,f(x))

就是一个一阶子句。

转换为子句形式通常包括:消去蕴含、将否定向内移、在必要时重命名约束变量,以及处理量词。斯科olem化通过引入表示见证的新常量或函数符号来消去存在量词。按照约定,子句集中剩余的变量均被理解为受全称量词约束。

例如:

∀x ∃y R(x,y)\forall x\,\exists y\,R(x,y)

经斯科勒姆化后得到:

∀x R(x,f(x)).\forall x\,R(x,f(x)).

所得子句为 R(x,f(x))R(x,f(x)),其中 xx 隐含地受全称量词约束。

斯科勒姆化保持的是扩充词汇表中的可满足性,而非原词汇表中的通常意义上的逻辑等价。这与命题逻辑中利用分配律进行的转换不同,后者在不改变变量集的情况下保持等价性。一阶归结还需要通过合一来匹配不同子句中的项。