代数范式
| 代数范式 | |
|---|---|
| 术语名称 | 代数范式 |
| 英语名称 | algebraic normal form |
| 别名 | ANF, Жегалкина范式, Zhegalkin 范式, Zhegalkin normal form, 里德–马勒展开式, Reed–Muller expansion |
代数范式(algebraic normal form, ANF)在命题逻辑中是命题公式的一种标准表示形式，它仅使用合取和互斥析取联结词以及真值常量真表达命题公式。在逻辑代数中也是通过逻辑与和逻辑异或表达逻辑代数式的标准形式。 与主析取范式、主合取范式不同，代数范式基于布尔代数的环状结构观点建立。
定义
基本形式
一个命题公式、逻辑代数式的代数范式是具有以下形式的逻辑代数式：
[math]\displaystyle{ c_0 \oplus (c_1 \land P_1) \oplus (c_2 \land P_2) \oplus \cdots \oplus (c_n \land P_n) \oplus (c_{12} \land P_1 \land P_2) \oplus \cdots \oplus (c_{n-1,n} \land P_{n-1} \land P_n) \oplus\cdots }[/math]
其中：
- [math]\displaystyle{ \oplus }[/math] 表示逻辑异或运算；
- [math]\displaystyle{ \land }[/math] 表示逻辑与运算；
- [math]\displaystyle{ c_0, c_1, c_2, \dots }[/math] 是系数，取值为 0 （假）或 1 （真）；
- [math]\displaystyle{ P_1, P_2, \dots, P_n }[/math] 是命题变元。
注：依据逻辑代数的习惯，也使用逻辑与 [math]\displaystyle{ \cdot }[/math] 和逻辑异或 [math]\displaystyle{ \oplus }[/math] 符号，表示为：
[math]\displaystyle{ c_0 \oplus c_1 P_1 \oplus c_2 P_2 \oplus \cdots \oplus c_n P_n \oplus c_{12} P_1 P_2 \oplus \cdots \oplus c_{n-1,n} P_{n-1} P_n \oplus\cdots }[/math]
数学表述
从代数角度看，代数范式是在二元域 [math]\displaystyle{ \mathbb{F}_2 }[/math] 上的多项式，乘法对应逻辑与，加法对应异或。
对于 [math]\displaystyle{ n }[/math] 个变元的布尔函数 [math]\displaystyle{ f: \{0,1\}^n \to \{0,1\} }[/math] ，其代数范式可写为： [math]\displaystyle{ f(x_1, \dots, x_n) = \bigoplus_{S \subseteq \{1,\dots,n\}} a_S \prod_{i \in S} x_i }[/math] 其中 [math]\displaystyle{ a_S \in \{0,1\} }[/math] ，且 [math]\displaystyle{ \prod }[/math] 表示逻辑与。
性质
- 每个布尔函数都有唯一的代数范式表示；在变元顺序固定的情况下，代数范式表示是唯一的。
- 代数性质
相关概念
根据多项式的次数和分类，可以定义：
- 代数次数：代数范式中包含变元最多的项所含变元的个数。
- 项数：代数范式中非零系数的个数。
- 线性多项式：代数次数为 1 的多项式。
构造方法
递归展开法
- 使用以下恒等式，将其他联结词转换为异或和合取两个联结词：
- [math]\displaystyle{ P \lor Q = P \oplus Q \oplus (P \land Q) }[/math] ；
- [math]\displaystyle{ P \rightarrow Q = 1 \oplus P \oplus (P \land Q) }[/math] ；
- [math]\displaystyle{ \lnot P = 1 \oplus P }[/math] ；
- 通过异或的结合性与对合取的分配律展开成多个合取项的异或；
- 去除同一变元在合取项中的重复出现，以及同一合取项在表达式中的重复出现。
真值表法
通过主析取范式构造代数范式：
- 列出函数的真值表。
- 对函数值为 1 的每一行，构造对应的极小项。
- 将所有极小项用异或连接。这是由于多个极小项间的析取和互斥析取一定等价。
- 使用 [math]\displaystyle{ \lnot P = 1 \oplus P }[/math] 将否定展开为异或。
- 通过异或的结合性与对合取的分配律展开成多个合取项的异或；
- 去除同一变元在合取项中的重复出现，以及同一合取项在表达式中的重复出现。
待定系数+杨辉三角法
可在 [math]\displaystyle{ \mathbb{F}_2 }[/math] 上的线性空间中使用待定系数法求解。其系数矩阵一定是一个下对角阵，且从左下角到主对角线是一个杨辉三角对 2 取余的结果。
- 将真值表值按顺序排列。
- 应用杨辉变换得到代数范式系数。
- 根据系数重构代数范式。
这些系数矩阵有如下规律：
- 1 个变量
[math]\displaystyle{ \begin{pmatrix} 1&0\\ 1&1\\ \end{pmatrix} }[/math]
- 2 个变量
[math]\displaystyle{ \begin{pmatrix} 1&0&0&0\\ 1&1&0&0\\ 1&0&1&0\\ 1&1&1&1\\ \end{pmatrix} }[/math]
- 3 个变量
[math]\displaystyle{ \begin{pmatrix} 1&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0\\ 1&0&1&0&0&0&0&0\\ 1&1&1&1&0&0&0&0\\ 1&0&0&0&1&0&0&0\\ 1&1&0&0&1&1&0&0\\ 1&0&1&0&1&0&1&0\\ 1&1&1&1&1&1&1&1\\ \end{pmatrix} }[/math]
Möbius 变换
通过偏序上的 Möbius 反演可知，考虑二进制串按照笛卡尔幂的积偏序下有： [math]\displaystyle{ g(x) = \bigoplus_{y\in \langle x\rangle} f(y) \leftrightarrow f(x)=\bigoplus_{y\in\langle x\rangle} g(y) }[/math] ，其中 [math]\displaystyle{ \langle x\rangle }[/math] 是序理想，此处即积偏序下元素 [math]\displaystyle{ x }[/math] 的下方集。
这给出了主析取范式和代数范式的关系。以三个变量的场景为例，以下三式必然相等：
- [math]\displaystyle{ f(000)\bar{A}\bar{B}\bar{C} + f(001)\bar{A}\bar{B}C + f(010)\bar{A}B\bar{C} + f(011)\bar{A}BC + \cdots + f(111)ABC }[/math]
- [math]\displaystyle{ f(000)\bar{A}\bar{B}\bar{C} \oplus f(001)\bar{A}\bar{B}C \oplus f(010)\bar{A}B\bar{C} \oplus f(011)\bar{A}BC \oplus \cdots \oplus f(111)ABC }[/math]
- [math]\displaystyle{ g(000) + g(001)C + g(010)B + g(011)BC + \cdots + g(111)ABC }[/math]
其中满足二元域上的线性方程： [math]\displaystyle{ \begin{pmatrix}g(000)\\g(001)\\g(010)\\g(011)\\\vdots\\g(111)\end{pmatrix} = \begin{pmatrix} 1&0&0&0&0&0&0&0 1&1&0&0&0&0&0&0 1&0&1&0&0&0&0&0 1&1&1&1&0&0&0&0 1&0&0&0&1&0&0&0 1&1&0&0&1&1&0&0 1&0&1&0&1&0&1&0 1&1&1&1&1&1&1&1 \end{pmatrix} \begin{pmatrix}f(000)\\f(001)\\f(010)\\f(011)\\\vdots\\f(111)\end{pmatrix} }[/math]