布尔函数
定义
\(n \in N\)
由\(F_2^n\)到\(F_2\)函数称为n元布尔函数
n元布尔函数有\(2^{2^n}\)个，构成环
记全体集合为\(B_n\)
表示方法
真值表
\((x_1⋯x_n) \in F_2^n\)
在\(f(x_1⋯x_n)\)的值列表
\(f: \{0,1\}^n→\{0,1\}\)
向量布尔函数 \(F_2^n→F_2^m\) 结果为\((f_1⋯f_m)\)
多项式表示
对于\(i \in F_2\)
\(i = 0\)时\(x_j^i = 1\)
\(i=1\)时\(x_j^i=x_j\)
\(I=(i_1⋯i_n) \in F_2^n\)
\(x=(x_1,⋯x_n)\)
\(x^I=∏_{j=1}^n x_j^i\)
n元布尔函数 \(f(x_1⋯x_n)=∑_{I \in F_2^n} a_I x^I\)
称为ANF 即f的代数正规型
小项表示
\((x_1+c_1+1)⋯(x_n+c_n+1)\)在当\((c_1,\dots,c_n)=(x_1,\dots,x_n)\)时等于1，其它情况等于0
\(f(x_1⋯x_n)=∑_{c_i \in F_2^n} f(c_1⋯c_n)(x_1+c_1+1)⋯(x_n+c_n+1)\)
基本概念
汉明重量、汉明距离
向量\(V \in F_2^n\) 汉明重量 \(W_H(V)\)
n元布尔函数\(f(x) : W_H(f)=|{x \in F_2^n: f(x)=1}|\)
\(f(x),g(x) \in B_n\) 汉明距离
\(d_H(f,g)=|{x \in F_2^n: f(x)≠g(x)}| =W_H(f+g)\)
代数次数
\(f \in B_n\)
\(f\) ANF中系数非零项所含有的最多变元个数称为f的代数次数
\(deg(f)=max{|I|: I \in P(N), a_I≠0}\)
P(N)表示N幂集:N所有子集构成集合.
\(deg(f)≤1\) 仿射函数 \(c_1x_1+⋯+c_nx_n+c\)
\(c=0\)时 线性函数
支撑集、序关系
对于 \(c=(c_1⋯c_n) d=(d_1⋯d_n) \in F_2^n\)
\(supp(c)={1≤i≤n: c_i=1}\)
若 \(supp(c)\subseteq supp(d)\)
称 \((c_1⋯c_n)\preceq(d_1⋯d_n)\)
实例分析
对于函数 \(f(x_1,x_2,x_3)\)
真值表表示
| \(x_1\) | \(x_2\) | \(x₃\) | \(f = x_1x_2+x_2+x_3\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
定义域：\(F_2³ = \{(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)\}\)
值域：\(F_2 = \{0,1\}\)
函数总数：\(B_3\)包含 \(2^{2³} = 2^8 = 256\) 个不同的3元布尔函数
将上述函数表示为8维向量：
\(f = (0,1,1,0,0,1,0,1)\)
ANF：\(f(x_1,x_1,x_3) = x_1x_2 + x_2 + x_3\)
代数次数：\(deg(f) = 2\)
使用小项展开：
\(f = x_2x_3 + x_1x_3 + x_1x_2 + x_1x_2x_3\)
向量 \(v = (1,0,1,1,0)\) 的汉明重量：\(W_H(v) = 3\)
函数 \(f\) 的汉明重量：\(W_H(f) = 4\)（真值表中输出为1的个数）
考虑函数 \(g(x_1,x_2,x_3) = x_1 + x_2 + x_3\)
g的真值表向量：\((0,1,1,0,1,0,0,1)\)
汉明距离：\(d_H(f,g) = W_H(f+g) = 2\)
向量 \((1,0,1,1,0)\) 的支撑集：\(\{1,3,4\}\)
序关系
考虑向量 \(a = (1,0,1)，b = (1,1,1)\)
\(supp(a) = {1,3}，supp(b) = {1,2,3}\)
因为 \(\{1,3\} ⊆ \{1,2,3\}\)，所以 a \(\preceq\) b
Walsh谱变换
Walsh谱定义：对于n元布尔函数\(f，w \in F_2^n\)
\(W_f(w) = \sum_{x \in F_2^n} (-1)^{f(x) + w \cdot x}\)
其中内积：\(w \cdot x = w_1x_1 + w_2x_2 + \cdots + w_nx_n\)
与汉明重量的关系
- \(W_f(w) = 2^n - 2W_H(f + w \cdot x)\)
- \(W_f(0) = 2^n - 2W_H(f)\)
平衡函数判定
- \(W_f(0) = 0 \Leftrightarrow f(x) \text{为n元平衡布尔函数}\)
正交性
- \(\sum_{x \in F_2^n} (-1)^{c \cdot x} = 0\) （对于$ 0 + c ∈ F_2^n$）
Walsh逆变换
重构公式：\((-1)^{f(x)} = \frac{1}{2^n} \sum_{w \in F_2^n} W_f(w)(-1)^{w \cdot x}\)
Parseval等式:\(\sum_{w \in F_2^n} W_f^2(w) = 2^{2n}\)
蝴蝶变换
基本形式ANF表示：\(f(x_1, \cdots, x_n) = \sum_{I \subseteq F_2^n} a_I x^I \quad a_I \in F_2\)
系数计算：对 \(∀ I ∈ F_2^n\) → \(a_I = \sum_{x \in F_2^n, x \leq I} f(x)\)
布尔函数重要指标
- 平衡性
真值表中0和1的个数相同
\(|W_H(f)| = 2^{n-1}\) - 非线性度
f(x)与所有仿射函数距离的最小值
\(nl = \min_{l \in A_n} d_H(f, l) = \min_{l \in A_n} W_H(f + l)\)
其中 \(A_n\) 为所有n元仿射函数集合，\(l(x) = w \cdot x + c\)
上界：\(nl(f) \leq 2^{n-1} - 2^{\frac{n}{2}-1}\) - 代数免疫度
\(AI(f)\)
寻找满足 \(f(x) \cdot g(x) = 0\) 的非零函数g(x)，取其最小次数\(AI(f) = \min \deg(g(x))\)