ブール関数

ブール関数はさまざまな特性を持つことができます: ^{[ 7 ]}

• 定数：引数に関係なく、常に真または常に偽である。
• 単調性：引数の値のあらゆる組み合わせにおいて、引数を false から true に変更しても、出力は false から true にのみ変化し、true から false には変化しません。関数が特定の変数に関して単調であるとは、その変数の変化に関して関数が単調であることを意味します。
• 線形: 各変数について、変数の値を反転すると、常に真偽値に違いが生じるか、または決して違いが生じないかのどちらかです (パリティ関数)。
• 対称性：値は引数の順序に依存しない。
• 読み取り専用：各変数の単一のインスタンスを使用して、論理積、論理和、および否定で表現できます。
• バランスが取れている：真理値表にゼロとイチが同数含まれている場合。関数のハミング重みは、真理値表中のイチの数です。
• ベント：その導関数はすべてバランスが取れている（自己相関スペクトルはゼロである）
• 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 (つまり導関数がバランスしている) である場合、その関数はその次数まで伝播基準を満たすと言われます。すべてがゼロの場合、その関数はベント関数です。^{[ 12 ]}自己相関係数は差分暗号解読で重要な役割を果たします。

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

任意のブール関数${\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})}$$例えば、バイナリXOR関数の拡張${\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で計算すると、代数標準形(ジェガルキン多項式)が得られます。

多項式の係数の直接的な式は、適切な微分を行うことで導出できる。$${\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}$2を法としてとると、これはブールメビウス変換となり、代数的正規形の係数が得られます。$${\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)}$$どちらの場合も、合計はmによってカバーされるすべてのビットベクトルaについて取られます。つまり、a の「1」ビットはmの「1」ビットの部分集合を形成します。

領域がn次元超立方体に限定されている場合${\displaystyle [0,1]^{n}}$多項式${\displaystyle f^{*}(x):[0,1]^{n}\rightarrow [0,1]}$ブール関数f をn個の独立した確率変数 (ベルヌーイ)に適用したときの、正の結果となる確率( xはそれぞれ独立) を表します。この事実の特殊なケースとして、パリティ関数のパイリングアップ補題があります。ブール関数の多項式形式は、ファジー論理への自然な拡張としても使用できます。

多くの場合、ブール領域は次のように解釈されます。${\displaystyle \{-1,1\}}$偽（"0") は 1 に、真（"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}}}$$対称ブール領域を使用すると、否定が-1の乗算に対応し、線形関数が単項式（XORは乗算）であるため、解析の特定の側面が簡略化されます。したがって、この多項式形式は、関数のウォルシュ変換（この文脈ではフーリエ変換とも呼ばれる）に対応します（上記参照）。この多項式は、期待値を取り扱う点を除いて、標準ブール領域の多項式と同じ統計的解釈を持ちます。${\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}$（例については、積み重ね補題を参照のこと。）