布林函數- 維基百科，自由的百科全書

在數學中，布林函數（Boolean function），又稱邏輯函數，描述如何基於對布林輸入的某種邏輯計算確定布林值輸出。

它們在複雜性理論的問題和數字電腦的晶片設計中扮演 ... 布林函數 維基百科，自由的百科全書 跳至導覽 跳至搜尋 此條目需要精通或熟悉相關主題的編者參與及協助編輯。

(2014年1月18日)請邀請適合的人士改善本條目。

更多的細節與詳情請參見討論頁。

各種函數x↦f (x) 不同定義域和對應域 X {\displaystyleX} → B {\displaystyle\mathbb{B}} , B {\displaystyle\mathbb{B}} → X {\displaystyleX} , B n {\displaystyle\mathbb{B}^{n}} → B {\displaystyle\mathbb{B}} X {\displaystyleX} →（英語：integer-valuedfunction） Z {\displaystyle\mathbb{Z}} , Z + {\displaystyle\mathbb{Z}^{+}} → X {\displaystyleX} X {\displaystyleX} →（英語：real-valuedfunction） R {\displaystyle\mathbb{R}} , R {\displaystyle\mathbb{R}} → X {\displaystyleX} , R n {\displaystyle\mathbb{R}^{n}} →（英語：functionofseveralrealvariables） X {\displaystyleX} X {\displaystyleX} →（英語：complex-valuedfunction） C {\displaystyle\mathbb{C}} , C {\displaystyle\mathbb{C}} → X {\displaystyleX} , C n {\displaystyle\mathbb{C}^{n}} →（英語：Functionofseveralcomplexvariables） X {\displaystyleX}  函數類/性質  常值 恆等 線性 多項式 有理 代數 解析 光滑 連續 可測 單射 滿射 對射 構造 限制 複合 λ 逆 推廣 偏（英語：Partialfunction） 多值 隱 閱論編 在數學中，布林函數（Booleanfunction），又稱邏輯函數，描述如何基於對布林輸入的某種邏輯計算確定布林值輸出。

它們在複雜性理論的問題和數字電腦的晶片設計中扮演基礎角色。

布林函數的性質在密碼學中扮演關鍵角色，特別是在對稱金鑰演算法的設計中（參見S-box）。

目次 1有限布爾函數 2代數範式 3參見 4外部連結 有限布林函數[編輯] 在數學中，有限布林函數是如下形式的函數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的「二進位序列」 有 2 2 k {\displaystyle2^{2^{k}}} 個這種函數。

代數範式[編輯] 布林函數可以唯一的寫為積（AND）之和（XOR）。

這叫做代數範式（ANF），也叫做Zhegalkin多項式。

f ( x 1 , x 2 , … , x n ) = {\displaystylef(x_{1},x_{2},\ldots,x_{n})=\!} a 0 + {\displaystylea_{0}+\!} a 1 x 1 + a 2 x 2 + … + a n x n + {\displaystylea_{1}\;x_{1}+a_{2}\;x_{2}+\ldots+a_{n}\;x_{n}+\!} a 1 , 2 x 1 x 2 + … + a n − 1 , n x n − 1 x n + {\displaystylea_{1,2}\;x_{1}x_{2}+\ldots+a_{n-1,n}\;x_{n-1}x_{n}+\!} … … … + {\displaystyle\ldots\quad\ldots\quad\ldots+\!} a 1 , 2 , … , n x 1 x 2 … x n {\displaystylea_{1,2,\ldots,n}\;x_{1}x_{2}\ldotsx_{n}\!} 這裡的 a 0 , a 1 , … , a 1 , 2 , … , n ∈ { 0 , 1 } ∗ {\displaystylea_{0},a_{1},\ldots,a_{1,2,\ldots,n}\in\{0,1\}^{*}} 。

序列 a 0 , a 1 , … , a 1 , 2 , … , n {\displaystylea_{0},a_{1},\ldots,a_{1,2,\ldots,n}} 的值因此還唯一的表示一個布林函數。

布林函數的代數次數被定義為出現在乘積項中的 x i {\displaystylex_{i}} 的最高次數。

所以 f ( x 1 , x 2 , x 3 ) = x 1 + x 3 {\displaystylef(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 {\displaystylef(x_{1},x_{2},x_{3})=x_{1}+x_{1}x_{2}x_{3}} 有次數3（立方）。

對於每個函數 f {\displaystylef} 都有一個唯一的ANF。

只有四個函數有一個參數: f ( x ) = 0 {\displaystylef(x)=0} ， f ( x ) = 1 {\displaystylef(x)=1} ， f ( x ) = x {\displaystylef(x)=x} ， f ( x ) = 1 + x {\displaystylef(x)=1+x} ；它們都可以在ANF中給出。

要表示有多個參數的函數，可以使用如下等式： f ( x 1 , x 2 , … , x n ) = g ( x 2 , … , x n ) + x 1 h ( x 2 , … , x n ) {\displaystylef(x_{1},x_{2},\ldots,x_{n})=g(x_{2},\ldots,x_{n})+x_{1}h(x_{2},\ldots,x_{n})} ， 這裡的 g ( x 2 , … , x n ) = f ( 0 , x 2 , … , x n ) {\displaystyleg(x_{2},\ldots,x_{n})=f(0,x_{2},\ldots,x_{n})} 並且 h ( x 2 , … , x n ) = f ( 0 , x 2 , … , x n ) + f ( 1 , x 2 , … , x n ) {\displaystyleh(x_{2},\ldots,x_{n})=f(0,x_{2},\ldots,x_{n})+f(1,x_{2},\ldots,x_{n})} 。

實際上， 如果 x 1 = 0 {\displaystylex_{1}=0} ，則 x 1 h = 0 {\displaystylex_{1}h=0} ，並因此 f ( 0 , … ) = f ( 0 , … ) {\displaystylef(0,\ldots)=f(0,\ldots)} ； 如果 x 1 = 1 {\displaystylex_{1}=1} ，則 x 1 h = h {\displaystylex_{1}h=h} ，並因此 f ( 1 , … ) = f ( 0 , … ) + f ( 0 , … ) + f ( 1 , … ) {\displaystylef(1,\ldots)=f(0,\ldots)+f(0,\ldots)+f(1,\ldots)} 。

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

例如，讓我們構造一個 f ( x , y ) = x ∨ y {\displaystylef(x,y)=x\lory} （邏輯或）的ANF： f ( x , y ) = f ( 0 , y ) + x ( f ( 0 , y ) + f ( 1 , y ) {\displaystylef(x,y)=f(0,y)+x(f(0,y)+f(1,y)} ； 因為 f ( 0 , y ) = 0 ∨ y = y {\displaystylef(0,y)=0\lory=y} 並且 f ( 1 , y ) = 1 ∨ y = 1 {\displaystylef(1,y)=1\lory=1} ，可以得出 f ( x , y ) = y + x ( y + 1 ) {\displaystylef(x,y)=y+x(y+1)} ； 通過打開括號我們得到最終的ANF： f ( x , y ) = y + x y + x = x + y + x y {\displaystylef(x,y)=y+xy+x=x+y+xy} 。

參見[編輯] 布林代數主題列表 真值函數 零階邏輯 外部連結[編輯] BooleanPlanet（頁面存檔備份，存於網際網路檔案館）—booleanfunctionsincryptography. 取自「https://zh.wikipedia.org/w/index.php?title=布尔函数&oldid=71477905」 分類：​密碼學布爾代數函數隱藏分類：​自2014年1月需要專業人士關注的頁面 導覽選單 個人工具 沒有登入討論貢獻建立帳號登入 命名空間 條目討論 臺灣正體 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 閱讀編輯檢視歷史 更多 搜尋 導航 首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科 說明 說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科 工具 連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目 列印/匯出 下載為PDF可列印版 其他語言 العربيةCatalàDeutschEnglishEspañolEuskaraفارسیFrançaisहिन्दीMagyarՀայերենItaliano日本語Қазақша한국어LatviešuМакедонскиNederlandsPolskiPortuguêsРусскийУкраїнська 編輯連結