跳至內容

布林函數

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書


數學中,布林函數(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:

參見

外部連結