布林函數

在數學中，布爾函數（Boolean function），又稱邏輯函數，描述如何基於對布爾輸入的某種邏輯計算確定布爾值輸出。它們在複雜性理論的問題和數字計算機的芯片設計中扮演基礎角色。布爾函數的性質在密碼學中扮演關鍵角色，特別是在對稱密鑰算法的設計中（參見S-box）。

有限布爾函數

在數學中，有限布爾函數是如下形式的函數${\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 f(x_{1},x_{2},\ldots ,x_{n})=\!}$	${\displaystyle a_{0}+\!}$
	${\displaystyle a_{1}\;x_{1}+a_{2}\;x_{2}+\ldots +a_{n}\;x_{n}+\!}$
	${\displaystyle a_{1,2}\;x_{1}x_{2}+\ldots +a_{n-1,n}\;x_{n-1}x_{n}+\!}$
	${\displaystyle \ldots \quad \ldots \quad \ldots +\!}$
	${\displaystyle a_{1,2,\ldots ,n}\;x_{1}x_{2}\ldots x_{n}\!}$

這裡的${\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.