企业官网建设流程全解析

之前不少读者看到 DNF 三个字母，第一反应是游戏《地下城与勇士》。但在这篇文章里，DNF 是理论计算机科学中的 Disjunctive Normal Form，也就是析取范式。更准确地说，我们讨论的是无歧义析取范式的最优表示问题，以及一个和它有着微妙联系、名字看起来像“两个不相关话题强行拼在一起”的图论猜想：Alon-Saks-Seymour 猜想。

这两条线交叉起来，恰恰是布尔函数复杂度与图结构之间的经典故事：边集的覆盖、划分，对应 DNF 中项的结构；图的色数，又和布尔函数的某些复杂度下界有关。本文将用尽量通俗的方式，把这些概念串起来，并给出可直接运行的小规模 Python 验证实验。无论你是对组合数学感兴趣的研究生，还是想补一补理论功底的工程师，都可以跟着这篇文章走一遍。

1. 背景：DNF 撞名背后的两个世界

1.1 析取范式不是游戏术语

在布尔逻辑中，一个布尔函数接受 n 个布尔变量，输出 0 或 1。比如常见的“三个变量中至少两个为真”就是一个布尔函数。

我们通常用两种标准形式来表示一个布尔函数：

• CNF，合取范式：多个子句做“与”运算，每个子句内部是“或”关系；
• DNF，析取范式：多个合取项做“或”运算，每个合取项内部是一组文字的“与”关系。

一个“文字”是指变量本身或它的否定，比如 x 和 ¬x。一个“合取项”是若干个文字的合取，比如 x ∧ y ∧ ¬z。一个 DNF 就是若干合取项的析取：

f(x, y, z) = (x ∧ y) ∨ (¬x ∧ z)

这条式子的意思是：当 x 和 y 都为真，或者 x 为假且 z 为真时，f 输出 1。

在数字电路综合、SAT 求解、规则系统、决策列表等场景中，DNF 都大量出现。它的优点是直观，缺点是同一个函数可能有很多种不同大小的 DNF，因此“最小 DNF”是一个很自然的优化问题。

1.2 无歧义 DNF 是什么

普通 DNF 允许一个赋值让多个合取项同时为真。比如：

g(x, y, z) = (x ∧ y) ∨ (y ∧ z)

当 x=1、y=1、z=1 时，两个合取项都为真，这并不违反 DNF 的定义。

但“无歧义 DNF”要求更严格：对于任意让函数值为 1 的赋值，有且只有一个合取项为真。也就是说，各个合取项的满足集合两两不相交。

这个约束看似苛刻，却让 DNF 具备了某些好的结构性质。比如在概率近似正确学习、布尔函数复杂度下界、伪随机性与组合设计研究中，无歧义 DNF 都经常作为一类特殊的表示模型出现。

1.3 图论为什么会“乱入”

很多人觉得图论和布尔公式是两门课，但组合数学中有一类基本操作就是“用结构覆盖图”。把一张图的边集划分成若干完全二部图，这在很大程度上等同于把一个布尔函数拆成若干合取项的并。理解这种对应关系，是进入 Alon-Saks-Seymour 猜想的前提。

某种意义上，本文是在回答三个问题：

1. 无歧义 DNF 的最优表示为什么困难；
2. 图的 biclique 划分如何对应 DNF 的结构；
3. Alon-Saks-Seymour 猜想说了什么，它为什么错得很有价值。

2. 无歧义 DNF：定义与判定方法

2.1 形式化定义

设有一个关于 n 个布尔变量 x1, x2, ..., xn 的布尔函数 f。一个合取项 T 可以写成：

T = (∧_{i∈P} xi) ∧ (∧_{j∈N} ¬xj)

其中 P 和 N 是不相交的变量下标集合，分别表示 T 要求哪些变量为真、哪些变量为假。

一个 DNF 是无歧义的，如果对于任意赋值 a ∈ {0,1}^n，满足 f(a)=1 时，恰好只有一个合取项在 a 上为真。

两个合取项 T1 和 T2 互斥，当且仅当存在某个变量 xk，T1 要求 xk 为真，而 T2 要求 xk 为假；或者反过来。因为此时没有任何赋值能同时满足两个项。

这个判定条件非常便宜，只需检查项与项之间是否存在“正负冲突”。于是，“判断一个 DNF 是否无歧义”可以在多项式时间内完成。

2.2 一个可运行的小例子

我们用 Python 实现上述判定规则。下面这一段只依赖 Python 标准库，可以直接复制运行。

def terms_conflict(t1, t2): """ 判断两个合取项是否互斥。 t1, t2 都是 dict 类型，形如 {变量下标: True/False} True 表示该变量以正文字出现，False 表示以负文字出现。 """ common = set(t1.keys()) & set(t2.keys()) for var in common: if t1[var] != t2[var]: return True return False def is_unambiguous(dnf): """ 判断一个 DNF 是否无歧义。 dnf 是 list，每个元素是一个 dict{变量下标: True/False}。 """ n = len(dnf) for i in range(n): for j in range(i + 1, n): if not terms_conflict(dnf[i], dnf[j]): return False, (i, j) return True, None # 示例 1：f = (x ∧ y) ∨ (¬x ∧ z) dnf1 = [ {0: True, 1: True}, # x ∧ y {0: False, 2: True}, # ¬x ∧ z ] print(is_unambiguous(dnf1)) # (True, None) # 示例 2：g = (x ∧ y) ∨ (y ∧ z) dnf2 = [ {0: True, 1: True}, # x ∧ y {1: True, 2: True}, # y ∧ z ] print(is_unambiguous(dnf2)) # (False, (0, 1))

运行结果应该是：

(True, None) (False, (0, 1))

第一个 DNF 无歧义，因为第一个项要求 x 为真，第二个项要求 x 为假，二者必然互斥。第二个 DNF 有歧义，因为当 x=1、y=1、z=1 时，两个项同时为真。

2.3 最优无歧义 DNF 问题

给定一个布尔函数的真值表，我们希望找到项数最少（或者文字总数最少）的无歧义 DNF。这比普通最小 DNF 更复杂，因为不仅要覆盖所有输出为 1 的赋值，还要求覆盖用的“项”两两互斥。

小规模时可以用暴力搜索：先枚举所有可能的合取项，再寻找一组两两互斥且覆盖整个真值表的项。枚举空间随 n 指数增长，因此只适合 n≤4 或 n≤5 的情况。不过，这种小规模搜索对建立直觉很有帮助。

这个问题的价值在于：无歧义 DNF 相当于把函数的 1 集合划分成若干个“立方体”，立方体之间不能相交。它天然是一种不相交覆盖，这与图的边划分问题在结构上完全一致。下面我们就进入图论那一侧。

3. 为什么图论会出现在这里

3.1 用 DNF 描述图的边集

给定一个无向简单图 G=(V,E)，其中 V 是顶点集合，E 是边集合。我们定义一个布尔函数 f_G：对于顶点集合 S⊆V，设它的指示向量为 x∈{0,1}^{|V|}，当 S 诱导的子图中至少存在一条边时，f_G(x)=1。

这个函数显然可以写成一个自然 DNF：每条边 (u,v) 对应一个合取项 xu ∧ xv。

f_G(x) = ∨_{(u,v)∈E} (xu ∧ xv)

但这个 DNF 通常不是无歧义的。比如三角形 K3 的三条边对应的三个项，在三个顶点都为 1 时三者为真。普通 DNF 并不介意这种重叠，但无歧义 DNF 需要把这些边重新组织成“互不重叠”的块。

3.2 完全二部图与 biclique

完全二部图 K_{A,B} 是指顶点被分成两个非空集合 A 和 B，且 A 中每个顶点都与 B 中每个顶点相连，A 内部和 B 内部没有边。

在文献中，K_{A,B} 也常被叫作 biclique，即二部团。

一个重要操作是：把图 G 的边集覆盖或划分成若干 biclique。

• biclique 覆盖：允许 biclique 之间的边有重叠，目标是让每个 biclique 的边集并起来等于 E(G)；
• biclique 划分：要求每个 biclique 的边集互不相交，所有 biclique 的边集并起来恰好等于 E(G)。

显然，划分比覆盖更难做到，因为一旦重叠就不符合要求。

来看两个具体例子：

• C4，也就是 4 个顶点的环，它本身就是 K_{2,2}，所以最小 biclique 划分数是 1；
• K4，4 个顶点的完全图，需要 3 个 biclique 才能划分完 6 条边。

3.3 从划分到项的直觉对应

如果 E(G) 可以被划分成 m 个 biclique，那么每个 biclique 对应一个合取项：把这个 biclique 两个端点集合中的所有变量都写成正文字。这种 DNF 使用的项数等于 m，比逐条边写项的 |E| 更紧凑。

不过需要注意，这里的 DNF 未必是无歧义的。两个 biclique 如果共享某个顶点，就可能出现一个赋值同时命中两个项。要构造无歧义 DNF，通常还需要引入辅助变量或更精细的文字设计。

所以严格的结论是：biclique 划分数与某种带冲突约束的 DNF 规模之间存在深刻联系，但“直接一一对应”只是一种直观理解，不能当作定理使用。真正引导研究者去思考的，是 Alon-Saks-Seymour 猜想所关心的那座桥梁。

4. Alon-Saks-Seymour 猜想：从线性上界到反例

4.1 猜想的陈述

Alon、Saks 和 Seymour 在研究图覆盖问题时提出了一个猜想：

如果图 G 的边集可以被划分成 m 个完全二部图，那么 G 的色数 χ(G) 不超过 m 的线性阶。

更流行的表述是：

χ(G) ≤ m + 1

其中 χ(G) 是图 G 的色数，也就是给顶点染色、使得相邻顶点颜色不同所需的最少颜色数。

猜想的边界情况是容易验证的：

• 当 m=1 时，G 是一个完全二部图的子图，一定是二部图，所以 χ(G)≤2；
• 当 m=|E| 时，每一条边单独作为一个 biclique，那么普通边贪心染色给 χ(G)≤|E|+1。

真正的问题是：在 m 很小时，色数是否仍被一个关于 m 的线性函数控制？

4.2 为什么这个猜想很有吸引力

如果猜想成立，会带来很强的结构结论：一张图的边集如果可以分成很少的 biclique，那这图一定可以用很少的颜色正确染色。这相当于说“biclique 划分数小”意味着“图的可着色性强”。

从算法角度看，色数一般很难计算，但如果我们能估计 biclique 划分数，就能给色数提供一个有效上界。更重要的是，这会给无歧义 DNF 的复杂度研究带来工具：DNF 的合取项数量对应划分的块数，色数又对应某种布尔函数复杂度参数，两者之间的不等式可以把看似无关的下界问题互相转化。

这也是为什么这个猜想在 2012 年被证伪之前，吸引了大量组合数学家的关注。

4.3 反例：Huang-Sudakov 的工作

2012 年，Huang 和 Sudakov 给出了决定性的反例。他们构造了一张图 G，其边集可以被划分成 m 个完全二部图，但色数不是线性的，而是达到了大约 m 的 6/5 次方：

χ(G) ≥ m^{6/5}

更精确的叙述中往往还有对数因子，我们不在这里纠结细节。关键是：这个反例说明 Alon-Saks-Seymour 猜想的原始线性上界是错的。

有趣的是，他们使用的构造工具不是完全随机的图，而是结合了图论、线性代数和概率方法。这种“随机但带代数结构”的构造，后来成为证明各种下界的常见范式。

4.4 猜想失败之后剩下了什么

猜想虽然被证伪，但这个问题并没有结束。反过来可以问：biclique 划分数为 m 的图，其色数最大能到多少？也就是说，我们需要求：

最大可能的 χ(G) 关于 m 的增长阶

已知下界是超线性的 m^{6/5} 量级，后续又有工作进一步改进了构造，把差距拉大。但精确的指数级究竟是多少，仍然是一个开放问题。这个问题在组合数学中属于“色数 vs 结构覆盖数”这一大家族，与很多经典猜想都有联系。

对无歧义 DNF 而言，这种反例构造同样有启示：它说明“合取项很少”并不自动意味着“布尔函数的复杂度很低”。看似结构简单的划分，也可能编码出非常复杂的真值表行为。

5. 用 Python 做小规模实验

理论文章容易让人越读越抽象，所以我用 Python 写了一个小工具：输入一张小图，自动计算它的色数和最小 biclique 划分数。由于算法是穷举，只适合顶点数不超过 6 或 7 的小图，但它能帮助我们直观理解 m 和 χ(G) 的关系。

5.1 实验目标

我们要验证三个小例子：

• C4：自身是 K_{2,2}，所以 m=1，χ=2；
• K4：m=3，χ=4；
• C5：m=3，χ=3。

可以看到后两个都满足 χ≤m+1，这也解释了为什么原始猜想看起来“挺合理”。

5.2 计算色数

先实现一个简单的回溯染色算法。对 n≤7 的图来说效率足够。

def chromatic_number(n, edges): adj = [[False] * n for _ in range(n)] for u, v in edges: adj[u][v] = adj[v][u] = True best = n color = [-1] * n def dfs(i, k): nonlocal best if k >= best: return if i == n: best = min(best, k) return used = set() for j in range(n): if adj[i][j] and color[j] != -1: used.add(color[j]) for c in range(k): if c not in used: color[i] = c dfs(i + 1, k) color[i] = -1 if k + 1 < best: color[i] = k dfs(i + 1, k + 1) color[i] = -1 dfs(0, 0) return best

这个算法从 0 开始分配颜色，始终使用最小的未用颜色来尝试新的颜色槽，是一种典型的回溯染色。

5.3 枚举所有 biclique

接下来枚举图里所有可能作为划分块的 biclique。一个 biclique 由两个不相交的非空顶点集合 A 和 B 决定，并且要求 A 中每个顶点与 B 中每个顶点都相连。

def all_bicliques(n, edges): edge_set = set(tuple(sorted(e)) for e in edges) result = set() vertices = range(n) for mask_a in range(1, 1 << n): A = [i for i in vertices if (mask_a >> i) & 1] if not A: continue remaining = ((1 << n) - 1) ^ mask_a sub = remaining while sub: B = [i for i in vertices if (sub >> i) & 1] ok = True for a in A: for b in B: if tuple(sorted((a, b))) not in edge_set: ok = False break if not ok: break if ok: es = frozenset(tuple(sorted((a, b))) for a in A for b in B) result.add(es) sub = (sub - 1) & remaining return list(result)

这里用整数掩码表示顶点集合。枚举顺序是：先选 A，再在剩余顶点中枚举 B。由于 A 和 B 顺序互换会得到同一个边集，最终用 set 去重。

5.4 递归求最小划分

当我们有了所有候选 biclique，就可以用递归搜索求最小划分数。核心策略是：每次找到一条尚未被覆盖的边，尝试用所有包含它的 biclique 去覆盖，然后继续递归。

def biclique_partition_number(n, edges): edge_set = set(tuple(sorted(e)) for e in edges) bics = all_bicliques(n, edges) edge_to_bics = {} for e in edge_set: edge_to_bics[e] = [] for idx, es in enumerate(bics): for e in es: edge_to_bics[e].append(idx) best = len(edges) covered = set() edge_list = list(edge_set) def dfs(cnt): nonlocal best if cnt >= best: return target = None for e in edge_list: if e not in covered: target = e break if target is None: best = min(best, cnt) return for idx in edge_to_bics[target]: es = bics[idx] if es & covered: continue covered |= es dfs(cnt + 1) covered -= es dfs(0) return best

由于每个候选 biclique 的边集之间不能重叠，递归深度不会超过边数，所以适合小图暴力验证。

5.5 运行与结果说明

把上面的函数组合起来，对三个图分别调用：

if __name__ == "__main__": c4 = [(0, 1), (1, 2), (2, 3), (3, 0)] k4 = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] c5 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)] for name, graph in [("C4", c4), ("K4", k4), ("C5", c5)]: chi = chromatic_number(4 if name != "C5" else 5, graph) m = biclique_partition_number(4 if name != "C5" else 5, graph) print(f"{name}: m={m}, chi={chi}, chi <= m+1: {chi <= m + 1}")

预期输出：

C4: m=1, chi=2, chi <= m+1: True K4: m=3, chi=4, chi <= m+1: True C5: m=3, chi=3, chi <= m+1: True

小图上的现象都符合猜想，但这并不能说明什么，因为反例构造需要把图做得非常大，m 和顶点数一起增长，才能让色数超过线性上界。

6. 常见误区与高频问题