ブール関数

数学において、ブール関数は、引数と結果が2要素の集合（通常は{true, false}、{0,1}、または{-1,1}）の値をとる関数です。 ^{[1] [2]}別名はスイッチング関数（特に古いコンピュータサイエンスの文献で使用）、^{[3] [4]}真理値関数（または論理関数）（論理で使用される）です。ブール関数はブール代数とスイッチング理論の対象です。^[5]

ブール関数は という形式をとり、 はブール領域と呼ばれ、は関数の引数と呼ばれる非負の整数です。 の場合、関数は の定数要素です。 は複数の出力を持つブール関数で、はベクトルまたはベクトル値のブール関数です（対称暗号のSボックス）。^[6]${\displaystyle f:\{0,1\}^{k}\to \{0,1\}}$${\displaystyle \{0,1\}}$${\displaystyle k}$${\displaystyle k=0}$${\displaystyle \{0,1\}}$${\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}$${\displaystyle m>1}$

引数を持つさまざまなブール関数が存在します。これは、エントリを持つさまざまな真理値表の数に相当します。 ${\displaystyle 2^{2^{k}}}$${\displaystyle k}$${\displaystyle 2^{k}}$

すべての-ary ブール関数は変数の命題式として表現でき、2 つの命題式は、同じブール関数を表現する場合にのみ 論理的に同等です。${\displaystyle k}$${\displaystyle k}$${\displaystyle x_{1},...,x_{k}}$

基本的な対称ブール関数 (論理接続子または論理ゲート) は次のとおりです。

• NOT、否定または補数- 1つの入力を受け取り、その入力が偽（「not」）の場合に true を返します。
• ANDまたは結合- すべての入力が true の場合に true になります ("both")
• ORまたは論理和- いずれかの入力が true の場合に true になります ("いずれか")
• XORまたは排他的論理和- 入力の 1 つが true で、もう 1 つが false (「等しくない」) の場合に true になります。
• NANDまたはSheffer ストローク- すべての入力が true ではない場合 (「両方ではない」) に true になります。
• NORまたは論理和- 入力のいずれも真でない場合 (「どちらでもない」) は真
• XNORまたは論理的等価性- 両方の入力が同じ ("等しい") 場合に true になります

より複雑な関数の例としては、多数決関数（奇数個の入力）があります。

ブール関数はさまざまな方法で指定できます。

• 真理値表: 引数の可能なすべての値に対する値を明示的にリストする
  • マルカン図: 真理値表の値を 2 次元グリッドに並べたもの (カルノー図で使用)
  • 二分決定図、二分木の一番下に真理値表の値をリストする
  • ベン図、真理値表の値を平面の領域の色分けとして表す

代数的には、基本的なブール関数を使用した 命題式として次のようになります。

• 否定正規形、引数とその補集合のANDとORの任意の組み合わせ
• 選言正規形、引数とその補集合の論理積の論理和として
• 連言正規形、引数とその補集合の論理和の論理積
• 正規正規形、関数を一意に識別する標準化された式:
  • 代数正規形またはゼガルキン多項式、引数のANDのXOR（補数は許可されません）
  • 完全な（標準的な）選言正規形、各引数または補数（最小項）を含むANDのOR
  • 完全な（標準的な）連言正規形、各引数または補集合（ maxterms）を含むORのAND
  • ブレイク標準形、関数のすべての主項の論理和

ブール式はグラフとして表示することもできます。

• 命題有向非巡回グラフ
  • 論理ゲートのデジタル回路図、ブール回路
  • ANDとNOTのみを使用したAND反転グラフ

電子回路を最適化するために、クワイン・マクラスキーアルゴリズムまたはカルノー図を使用してブール式を最小化することができます。

ブール関数は様々な特性を持つことができる: ^[7]

• 定数: 引数に関係なく、常に true または常に false になります。
• 単調: 引数値のすべての組み合わせにおいて、引数を false から true に変更すると、出力は false から true に切り替わるだけで、true から false に切り替わることはありません。関数が特定の変数の変化に対して単調である場合、その関数は特定の変数において単調であると言われます。
• 線形: 各変数について、変数の値を反転すると、真理値に常に違いが生じるか、まったく違いが生じないかのどちらかです (パリティ関数)。
• 対称: 値は引数の順序に依存しません。
• 一度だけ読み取り可能:各変数の単一のインスタンスを使用して、論理積、論理和、否定で表現できます。
• バランスが取れている:真理値表に0 と 1 の数が等しい場合。関数のハミング重みは、真理値表内の 1 の数です。
• 曲がっている：その導関数はすべてバランスが取れている（自己相関スペクトルはゼロ）
• m次の相関なし: 出力が最大m個の引数のすべての（線形）組み合わせと相関しない場合
• 回避的: 関数の評価には常にすべての引数の値が必要な場合
• ブール関数は、任意のブール関数を（合成によって）作成できる場合、シェファー関数である（関数の完全性を参照）。
• 関数の代数次数は、その代数正規形における最高次単項式の次数である。

回路の複雑さは、ブール関数を計算できる回路のサイズまたは深さに基づいてブール関数を分類しようとします。

ブール関数はブール展開定理を用いて正と負のシャノン 余因子（シャノン展開）に分解することができる。シャノン余因子は引数の1つを（0または1に）固定することで得られる（k-1）元関数である。入力の集合（線形部分空間）に線形制約を課すことで得られる一般的な（k-元）関数は部分関数として知られている。^[8]

関数の引数の1つに対するブール微分は、関数の出力が選択された入力変数に敏感な場合に真となる(k-1)項関数であり、2つの対応する補因子のXORです。導関数と補因子はリード・ミュラー展開で使用されます。この概念は、関数のxとx + dxの差(XOR)として得られる、方向dxのk項微分として一般化できます。^[8]

ブール関数のメビウス変換（またはブール-メビウス変換）は、その多項式（代数正規形）の係数の集合であり、単項式指数ベクトルの関数として表される。これは自己逆変換である。これは、高速フーリエ変換に類似したバタフライアルゴリズム（「高速メビウス変換」）を使用して効率的に計算できる。^[9]一致するブール関数はメビウス変換に等しい。つまり、その真理値表（最小項）の値は代数（単項式）係数に等しい。^[10] k個の引数を持つ一致する関数は 2^2^( k −1)個ある。^[11]

ブール関数のウォルシュ変換は、フーリエ変換による実数値関数の高調波への分解に類似した、線形関数 (ウォルシュ関数) への分解の係数を与える k 元整数値関数です。その平方はパワースペクトルまたはウォルシュスペクトルです。単一ビットベクトルのウォルシュ係数は、そのビットとブール関数の出力との相関の尺度です。最大 (絶対値) のウォルシュ係数は、関数の線形性として知られています。 ^[8]すべてのウォルシュ係数が 0 である (つまり、サブ関数がバランスが取れている) 最大ビット数 (次数) は復元力として知られ、関数はその次数の相関に影響されないと言われています。^{[8]ウォルシュ係数は、}線形暗号解読で重要な役割を果たします。

ブール関数の自己相関は、入力の特定のセットの変化と関数の出力との相関関係を示す k 進整数値関数です。特定のビットベクトルの場合、その方向の導関数のハミング重みと関連しています。最大の自己相関係数 (絶対値) は絶対指標として知られています。^{[7] [8]}特定のビット数に対してすべての自己相関係数が 0 (つまり、導関数がバランスしている) の場合、関数はその順序への伝播基準を満たしていると言われます。すべてが 0 の場合、関数は曲がった関数です。^{[12]自己相関係数は}、差分暗号解読で重要な役割を果たします。

ブール関数のウォルシュ係数とその自己相関係数は、自己相関とパワースペクトルがウォルシュ変換のペアであることを述べるウィーナー・ヒンチン定理と同等の関係にある。 ^[8]

これらの概念は、出力ビット（座標）を個別に考慮するか、より徹底的に、出力ビットのすべての線形関数の集合（その成分）を見ることによって、ベクトルブール関数に自然に拡張できます。^[6]成分のウォルシュ変換の集合は、線形近似表（LAT）^{[13] [14]}または相関行列^{[15] [16]}として知られています。これは、入力ビットと出力ビットの異なる線形結合間の相関関係を記述します。 成分の自己相関係数の集合は自己相関表^[14]であり、成分のウォルシュ変換^[17]によって、より広く使用されている差分分布表（DDT）^{[13] [14]}に関連付けられています。DDTは、入力ビットと出力ビットの差の間の相関関係をリストします（Sボックスも参照）。

任意のブール関数は、 の多重線型多項式によって実領域に一意に拡張（補間）できます。多重線型多項式は、指示多項式を乗じた真理値表の値を合計することで構築されます。たとえば、バイナリ XOR 関数の拡張は であり、これは に等しくなります。その他の例としては、否定（）、AND（）、OR（）などがあります。すべてのオペランドが独立している（変数を共有しない）場合、ブール式の演算子の多項式を繰り返し適用することで、関数の多項式形式を見つけることができます。係数を2 を法として計算すると、代数正規形（ジェガルキン多項式）が得られます。 ${\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}}$${\displaystyle \mathbb {R} ^{n}}$$${\displaystyle f^{*}(x)=\sum _{a\in {\{0,1\}}^{n}}f(a)\prod _{i:a_{i}=1}x_{i}\prod _{i:a_{i}=0}(1-x_{i})}$$${\displaystyle x\oplus y}$$${\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy}$$$${\displaystyle x+y-2xy}$$${\displaystyle 1-x}$${\displaystyle xy}$${\displaystyle x+y-xy}$

多項式の係数の直接表現は、適切な導関数を取ることで導くことができます。これは、ビット ベクトルの部分的に順序付けられたセットのメビウス反転として一般化されます。ここで、はビット ベクトルの重みを表します。2 を法として取ると、これはブールメビウス変換となり、代数正規形の係数が得られます。どちらの場合も、合計はmでカバーされるすべてのビット ベクトルaに対して取られます。つまり、 aの「1」のビットは、mの 1 のビットのサブセットを形成します。 $${\displaystyle {\begin{array}{lcl}f^{*}(00)&=&(f^{*})(00)&=&f(00)\\f^{*}(01)&=&(\partial _{1}f^{*})(00)&=&-f(00)+f(01)\\f^{*}(10)&=&(\partial _{2}f^{*})(00)&=&-f(00)+f(10)\\f^{*}(11)&=&(\partial _{1}\partial _{2}f^{*})(00)&=&f(00)-f(01)-f(10)+f(11)\\\end{array}}}$$$${\displaystyle f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)}$$${\displaystyle |a|}$${\displaystyle a}$$${\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)}$$

ドメインが n 次元超立方体 に制限されている場合、多項式は、ブール関数fがn 個の独立したランダム (ベルヌーイ) 変数 (個々の確率xを持つ)に適用されたときに、肯定的な結果の確率を与えます。この事実の特殊なケースは、パリティ関数の積み重ね補題です。ブール関数の多項式形式は、ファジー論理への自然な拡張として使用することもできます。 ${\displaystyle [0,1]^{n}}$${\displaystyle f^{*}(x):[0,1]^{n}\rightarrow [0,1]}$

多くの場合、ブール領域は とみなされ、偽 ("0") は 1 に、真 ("1") は -1 にマッピングされます (ブール関数の解析 を参照)。 に対応する多項式は次のように与えられます。対称ブール領域を使用すると、解析の特定の側面が簡略化されます。これは、否定が -1 を掛けることに対応し、線形関数が単項式(XOR は乗算) であるためです。したがって、この多項式形式は、関数のウォルシュ変換(この文脈ではフーリエ変換とも呼ばれます) に対応します (上記を参照)。多項式の統計的解釈は、期待値を扱う点を除いて、標準ブール領域の解釈と同じです(例については、 積み上げ補題を参照)。${\displaystyle \{-1,1\}}$${\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}}$$${\displaystyle g^{*}(x)=\sum _{a\in {\{-1,1\}}^{n}}g(a)\prod _{i:a_{i}=-1}{\frac {1-x_{i}}{2}}\prod _{i:a_{i}=1}{\frac {1+x_{i}}{2}}}$$${\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}$

ブール関数は、複雑性理論の問題やデジタルコンピュータのプロセッサの設計において基本的な役割を果たし、論理ゲートを使用して電子回路に実装されます。

ブール関数の特性は暗号化、特に対称鍵アルゴリズムの設計において重要です(置換ボックスを参照)。

協力ゲーム理論では、単調なブール関数は単純ゲーム（投票ゲーム）と呼ばれ、この概念は社会的選択理論の問題を解くために適用されます。

• Crama, Yves; Hammer, Peter L. (2011)、ブール関数: 理論、アルゴリズム、およびアプリケーション、ケンブリッジ大学出版局、doi :10.1017/CBO9780511852008、ISBN 9780511852008
• 「ブール関数」、数学百科事典、EMS Press、2001 [1994]
• Janković, Dragan; Stanković, Radomir S.; Moraga, Claudio (2003 年 11 月)。「デュアル極性特性を使用した算術式の最適化」。Serbian Journal of Electrical Engineering。1 ( 71– 80、第 1 号): 71– 80。doi : 10.2298/ SJEE0301071J。
• アーノルド、ブラッドフォード・ヘンリー（2011年1月1日）。論理とブール代数。クーリエコーポレーション。ISBN 978-0-486-48385-6。
• マノ、MM; シレッティ、MD (2013)、デジタルデザイン、ピアソン