布尔函数 📖 Wikipedia

在数学中，有限布尔函数是如下形式的函数${\displaystyle f:\mathbb {B} ^{k}\rightarrow \mathbb {B} }$ ，这里的${\displaystyle \mathbb {B} =\{0,1\}}$ 是布尔域，而 ${\displaystyle k}$  是非负整数。在 ${\displaystyle k=0}$  的情况下，函数简单的是 ${\displaystyle \mathbb {B} }$  的一个恒定元素。

更一般的说，形如 ${\displaystyle f:X\rightarrow \mathbb {B} }$  函数，这里的 ${\displaystyle X}$  是任意集合，是布尔值函数。如果${\displaystyle X=\mathbb {M} =\{1,2,3,\cdots \}}$ ，则 ${\displaystyle f}$  是“二进制序列”，就是说0和1的无限序列。如果${\displaystyle X=[k]=\{1,2,3,\cdots ,k\}}$ ，则 ${\displaystyle f}$  是长度为 ${\displaystyle k}$  的“二进制序列”

有${\displaystyle 2^{2^{k}}}$ 个这种函数。

布尔函数可以唯一的写为积（AND）之和（XOR）。这叫做代数范式（ANF），也叫做Zhegalkin多项式。

这里的${\displaystyle a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}}$ 。 序列${\displaystyle a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}}$ 的值因此还唯一的表示一个布尔函数。

布尔函数的代数次数被定义为出现在乘积项中的 ${\displaystyle x_{i}}$  的最高次数。所以${\displaystyle f(x_{1},x_{2},x_{3})=x_{1}+x_{3}}$ 有次数1（线性），而${\displaystyle f(x_{1},x_{2},x_{3})=x_{1}+x_{1}x_{2}x_{3}}$ 有次数3（立方）。

对于每个函数${\displaystyle f}$ 都有一个唯一的ANF。只有四个函数有一个参数: ${\displaystyle f(x)=0}$  ，${\displaystyle f(x)=1}$  ，${\displaystyle f(x)=x}$  ，${\displaystyle f(x)=1+x}$  ；它们都可以在ANF中给出。要表示有多个参数的函数，可以使用如下等式：

${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=g(x_{2},\ldots ,x_{n})+x_{1}h(x_{2},\ldots ,x_{n})}$  ，

这里的${\displaystyle g(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})}$  并且 ${\displaystyle h(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})+f(1,x_{2},\ldots ,x_{n})}$  。

实际上，

如果${\displaystyle x_{1}=0}$  ，则${\displaystyle x_{1}h=0}$  ，并因此${\displaystyle f(0,\ldots )=f(0,\ldots )}$  ；

如果${\displaystyle x_{1}=1}$  ，则${\displaystyle x_{1}h=h}$  ，并因此${\displaystyle f(1,\ldots )=f(0,\ldots )+f(0,\ldots )+f(1,\ldots )}$  。

因为${\displaystyle g}$ 和${\displaystyle h}$ 二者都有比${\displaystyle f}$ 少的参数，可以得出递归的使用这个过程将完成于只有一个变量的函数。

例如，让我们构造一个${\displaystyle f(x,y)=x\lor y}$ （逻辑或）的ANF：

${\displaystyle f(x,y)=f(0,y)+x(f(0,y)+f(1,y))}$  ；

因为${\displaystyle f(0,y)=0\lor y=y}$  并且${\displaystyle f(1,y)=1\lor y=1}$ ，可以得出${\displaystyle f(x,y)=y+x(y+1)}$ ；

通过打开括号我们得到最终的ANF：${\displaystyle f(x,y)=y+xy+x=x+y+xy}$  。

• 布尔代数主题列表
• 真值函数
• 零阶逻辑

• Boolean Planet （页面存档备份，存于互联网档案馆）—boolean functions in cryptography.