查看“︁代数范式”︁的源代码

[[分类:命题逻辑]]
[[分类:逻辑代数]]{{DEFAULTSORT:dai4shu4fan4shi4}}
{{#seo:
|keywords=代数范式, ANF, Zhegalkin范式, Жегалкина范式, Zhegalkin多项式, Жегалкина多项式, 里德-马勒展开式
|description=代数范式(ANF)是命题公式的标准表示形式，仅使用合取和异或运算。每个布尔函数都有唯一的代数范式，在密码学、电路设计和编码理论中有重要应用，也称为Zhegalkin多项式或里德-马勒展开式。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2023-06-24
}}
{{InfoBox
|name=代数范式
|eng_name=algebraic normal form
|aliases=ANF,Zhegalkin 范式,Zhegalkin normal form, 里德–马勒展开式, Reed–Muller expansion
}}
'''代数范式'''('''algebraic normal form''', '''ANF''')在命题逻辑中是[[命题公式]]的一种标准表示形式，它仅使用[[合取]]和[[互斥析取]]联结词以及[[真值]]常量[[真]]表达命题公式。在逻辑代数中也是通过[[逻辑与]]和[[逻辑异或]]表达逻辑代数式的标准形式。
与[[主析取范式、主合取范式]]不同，代数范式基于布尔代数的环状结构观点建立。

== 定义 ==

=== 基本形式 ===

一个命题公式、逻辑代数式的代数范式是具有以下形式的逻辑代数式：

<math>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>\oplus</math> 表示逻辑异或运算；
* <math>\land</math> 表示逻辑与运算；
* <math>c_0, c_1, c_2, \dots</math> 是系数，取值为 0 （假）或 1 （真）；
* <math>P_1, P_2, \dots, P_n</math> 是命题变元。

注：依据逻辑代数的习惯，也使用逻辑与 <math>\cdot</math> 和逻辑异或 <math>\oplus</math> 符号，表示为：

<math>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>\mathbb{F}_2</math> 上的多项式，乘法对应逻辑与，加法对应异或。

对于 <math>n</math> 个变元的布尔函数 <math>f: \{0,1\}^n \to \{0,1\}</math> ，其代数范式可写为：
<math>f(x_1, \dots, x_n) = \bigoplus_{S \subseteq \{1,\dots,n\}} a_S \prod_{i \in S} x_i</math>
其中 <math>a_S \in \{0,1\}</math> ，且 <math>\prod</math> 表示逻辑与。

== 性质 ==

* 每个布尔函数都有唯一的代数范式表示；在变元顺序固定的情况下，代数范式表示是唯一的。
* 代数性质
** [[线性性]]：异或运算满足[[结合律]]、[[交换律]]，且对合取运算满足[[分配律]] ；
** <math>x \land x = x</math> ；
** <math>x \oplus x = 0</math> 。

== 相关概念 ==

根据多项式的次数和分类，可以定义：
* 代数次数：代数范式中包含变元最多的项所含变元的个数。
* 项数：代数范式中非零系数的个数。
* 线性多项式：代数次数为 1 的多项式。

== 构造方法 ==

=== 递归展开法 ===

# 使用以下恒等式，将其他联结词转换为异或和合取两个联结词：
#* <math>P \lor Q = P \oplus Q \oplus (P \land Q)</math> ；
#* <math>P \rightarrow Q = 1 \oplus P \oplus (P \land Q)</math> ；
#* <math>\lnot P = 1 \oplus P</math> ；
# 通过异或的结合性与对合取的分配律展开成多个合取项的异或；
# 去除同一变元在合取项中的重复出现，以及同一合取项在表达式中的重复出现。

=== 真值表法 ===

通过[[主析取范式]]构造代数范式：

# 列出函数的真值表。
# 对函数值为 1 的每一行，构造对应的极小项。
# 将所有极小项用异或连接。这是由于多个极小项间的析取和互斥析取一定等价。
# 使用 <math>\lnot P = 1 \oplus P</math> 将否定展开为异或。
# 通过异或的结合性与对合取的分配律展开成多个合取项的异或；
# 去除同一变元在合取项中的重复出现，以及同一合取项在表达式中的重复出现。

=== 待定系数+杨辉三角法 ===

可在 <math>\mathbb{F}_2</math> 上的线性空间中使用待定系数法求解。其系数矩阵一定是一个下对角阵，且从左下角到主对角线是一个杨辉三角对 2 取余的结果。
# 将真值表值按顺序排列。
# 应用杨辉变换得到代数范式系数。
# 根据系数重构代数范式。

这些系数矩阵有如下规律：
* 1 个变量
<math>
\begin{pmatrix}
1&0\\
1&1\\
\end{pmatrix}
</math>
* 2 个变量
<math>
\begin{pmatrix}
1&0&0&0\\
1&1&0&0\\
1&0&1&0\\
1&1&1&1\\
\end{pmatrix}
</math>
* 3 个变量
<math>
\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>g(x) = \bigoplus_{y\in \langle x\rangle} f(y) \leftrightarrow f(x)=\bigoplus_{y\in\langle x\rangle} g(y)</math>
，其中 <math>\langle x\rangle</math> 是[[序理想]]，此处即积偏序下元素 <math>x</math> 的[[下方集]]。

这给出了主析取范式和代数范式的关系。以三个变量的场景为例，以下三式必然相等：
* <math>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>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>g(000) + g(001)C + g(010)B + g(011)BC + \cdots + g(111)ABC</math>

其中满足二元域上的线性方程：
<math>
\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>


{{命题逻辑}}