布林函數

函数的一种,描述如何基于对布尔输入的某种逻辑计算确定布尔值输出


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

有限布林函數

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

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

 個這種函數。

代數範式

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

   
 
 
 
 

這裏的 。 序列 的值因此還唯一的表示一個布林函數。

布林函數的代數次數被定義為出現在乘積項中的 的最高次數。所以 有次數1(線性),而 有次數3(立方)。


對於每個函數 都有一個唯一的ANF。只有四個函數有一個參數:      ;它們都可以在ANF中給出。要表示有多個參數的函數,可以使用如下等式:

 

這裏的  並且  

實際上,

如果  ,則  ,並因此 
如果  ,則  ,並因此 

因為  二者都有比 少的參數,可以得出遞歸的使用這個過程將完成於只有一個變數的函數。


例如,讓我們構造一個 (邏輯或)的ANF:

 
因為  並且 ,可以得出 
通過打開括號我們得到最終的ANF: 

參見

外部連結