布林函數

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

有限布林函數

在數學中，有限布林函數是如下形式的函數f : B^k → B，這裡的B = {0, 1}是布林域，而k是非負整數。在k = 0的情況下，函數簡單的是B的一個恆定元素。

更一般的說，形如f : X → B函數，這裡的X是任意集合，是布林值函數。如果X = M = {1, 2, 3, …}，則f是「二進制序列」，就是說0和1的無限序列。如果X = [k] = {1, 2, 3, …, k}，則f是長度為k的「二進制序列」

有$2^{2^{k}}$個這種函數。

代數範式

布林函數可以唯一的寫為積（AND）之和（XOR）。這叫做代數範式（ANF），也叫做Zhegalkin多項式。

$f(x_{1},x_{2},\ldots ,x_{n})=\!$	$a_{0}+\!$
	$a_{1}\;x_{1}+a_{2}\;x_{2}+\ldots +a_{n}\;x_{n}+\!$
	$a_{1,2}\;x_{1}x_{2}+\ldots +a_{n-1,n}\;x_{n-1}x_{n}+\!$
	$\ldots \quad \ldots \quad \ldots +\!$
	$a_{1,2,\ldots ,n}\;x_{1}x_{2}\ldots x_{n}\!$

這裡的$a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}$。 序列$a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}$的值因此還唯一的表示一個布林函數。

布林函數的代數次數被定義為出現在乘積項中的$x_{i}$的最高次數。所以$f(x_{1},x_{2},x_{3})=x_{1}+x_{3}$有次數1（線性），而$f(x_{1},x_{2},x_{3})=x_{1}+x_{1}x_{2}x_{3}$有次數3（立方）。

對於每個函數$f$都有一個唯一的ANF。只有四個函數有一個參數: $f(x)=0$ ，$f(x)=1$ ，$f(x)=x$ ，$f(x)=1+x$ ；它們都可以在ANF中給出。要表示有多個參數的函數，可以使用如下等式：

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

這裡的$g(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})$ 並且 $h(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})+f(1,x_{2},\ldots ,x_{n})$ 。

實際上，

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

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

因為$g$和$h$二者都有比$f$少的參數，可以得出遞迴的使用這個過程將完成於只有一個變數的函數。

例如，讓我們構造一個$f(x,y)=x\lor y$（邏輯或）的ANF：

$f(x,y)=f(0,y)+x(f(0,y)+f(1,y))$ ；

因為$f(0,y)=0\lor y=y$ 並且$f(1,y)=1\lor y=1$，可以得出$f(x,y)=y+x(y+1)$；

通過打開括號我們得到最終的ANF：$f(x,y)=y+xy+x=x+y+xy$ 。

參見

• 布林代數主題列表
• 真值函數
• 零階邏輯

外部連結

• Boolean Planet （頁面存檔備份，存於網際網路檔案館）—boolean functions in cryptography.