| 本條目存在以下問題,請協助 改善本條目或在 討論頁針對議題發表看法。
| 此條目需要 精通或熟悉相關主題的編者參與及協助編輯。 (2014年1月18日) 請邀請適合的人士改善本條目。更多的細節與詳情請參見討論頁。 |
|
在數學中,布林函數(Boolean function),又稱邏輯函數,描述如何基於對布林輸入的某種邏輯計算確定布林值輸出。它們在複雜性理論的問題和數字電腦的晶片設計中扮演基礎角色。布林函數的性質在密碼學中扮演關鍵角色,特別是在對稱金鑰演算法的設計中(參見S-box)。
有限布林函數
在數學中,有限布林函數是如下形式的函數f : Bk → 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的「二進位序列」
有
個這種函數。
代數範式
布林函數可以唯一的寫為積(AND)之和(XOR)。這叫做代數範式(ANF),也叫做Zhegalkin多項式。
|
|
|
|
|
|
|
|
|
|
這裡的
。
序列
的值因此還唯一的表示一個布林函數。
布林函數的代數次數被定義為出現在乘積項中的
的最高次數。所以
有次數1(線性),而
有次數3(立方)。
對於每個函數
都有一個唯一的ANF。只有四個函數有一個參數:
,
,
,
;它們都可以在ANF中給出。要表示有多個參數的函數,可以使用如下等式:
,
這裡的
並且
。
實際上,
- 如果
,則
,並因此
;
- 如果
,則
,並因此
。
因為
和
二者都有比
少的參數,可以得出遞迴的使用這個過程將完成於只有一個變數的函數。
例如,讓我們構造一個
(邏輯或)的ANF:
;
- 因為
並且
,可以得出
;
- 通過打開括號我們得到最終的ANF:
。
參見
外部連結