ブールの展開定理

ブールの展開定理は、シャノン展開またはシャノン分解とも呼ばれ、次の恒等式である。${\displaystyle F=x\cdot F_{x}+x'\cdot F_{x'}}$、 どこ${\displaystyle F}$は任意のブール関数です。${\displaystyle x}$変数です。${\displaystyle x'}$は${\displaystyle x}$、 そして${\displaystyle F_{x}}$そして${\displaystyle F_{x'}}$は${\displaystyle F}$議論とともに${\displaystyle x}$等しく設定する${\displaystyle 1}$そして${\displaystyle 0}$それぞれ。

条件${\displaystyle F_{x}}$そして${\displaystyle F_{x'}}$これらはそれぞれ、正および負のシャノン補因子と呼ばれることがあります。${\displaystyle F}$に関して${\displaystyle x}$これらは、によって計算される関数です。${\displaystyle \operatorname {restrict} }$オペレーター、${\displaystyle \operatorname {restrict} (F,x,0)}$そして${\displaystyle \operatorname {restrict} (F,x,1)}$。

この定理は「ブール代数の基本定理」と呼ばれています。^{[ 1 ]}理論的な重要性に加えて、二分決定図（BDD）、充足可能性ソルバー、およびコンピュータ工学やデジタル回路の形式検証に関連するその他多くの技術への道を開きました。このような文脈、特にBDDでは、展開はif-then-elseとして解釈され、変数は${\displaystyle x}$条件であり、補因子は分岐である（${\displaystyle F_{x}}$いつ${\displaystyle x}$は真であり、それぞれ${\displaystyle F_{x'}}$いつ${\displaystyle x}$偽である）。^{[ 2 ]}

この定理をより明確に表現すると次のようになります。

${\displaystyle f(X_{1},X_{2},\dots ,X_{n})=X_{1}\cdot f(1,X_{2},\dots ,X_{n})+X_{1}'\cdot f(0,X_{2},\dots ,X_{n})}$

XOR形式

論理和「+」をXOR演算子に置き換えた場合も、この記述は成り立つ。

${\displaystyle f(X_{1},X_{2},\dots ,X_{n})=X_{1}\cdot f(1,X_{2},\dots ,X_{n})\oplus X_{1}'\cdot f(0,X_{2},\dots ,X_{n})}$

デュアルフォーム

シャノン展開には双対形式が存在する（ただし、関連するXOR形式は存在しない）。

${\displaystyle f(X_{1},X_{2},\dots ,X_{n})=(X_{1}+f(0,X_{2},\dots ,X_{n}))\cdot (X_{1}'+f(1,X_{2},\dots ,X_{n}))}$

各引数に対して繰り返し適用すると、ブール関数の積和形（SoP）の標準形が得られます。${\displaystyle f}$例えば、${\displaystyle n=2}$それは

${\displaystyle {\begin{aligned}f(X_{1},X_{2})&=X_{1}\cdot f(1,X_{2})+X_{1}'\cdot f(0,X_{2})\\&=X_{1}X_{2}\cdot f(1,1)+X_{1}X_{2}'\cdot f(1,0)+X_{1}'X_{2}\cdot f(0,1)+X_{1}'X_{2}'\cdot f(0,0)\end{aligned}}}$

同様に、双対形式を適用すると、積和(PoS) 標準形式 (分配法則を使用) が得られます。${\displaystyle +}$以上${\displaystyle \cdot }$):

${\displaystyle {\begin{aligned}f(X_{1},X_{2})&=(X_{1}+f(0,X_{2}))\cdot (X_{1}'+f(1,X_{2}))\\&=(X_{1}+X_{2}+f(0,0))\cdot (X_{1}+X_{2}'+f(0,1))\cdot (X_{1}'+X_{2}+f(1,0))\cdot (X_{1}'+X_{2}'+f(1,1))\end{aligned}}}$

補因子の線形特性：

2つのブール関数GとHから構成されるブール関数Fについては、以下のことが成り立ちます。

もし${\displaystyle F=H'}$それから${\displaystyle F_{x}=H'_{x}}$

もし${\displaystyle F=G\cdot H}$それから${\displaystyle F_{x}=G_{x}\cdot H_{x}}$

もし${\displaystyle F=G+H}$それから${\displaystyle F_{x}=G_{x}+H_{x}}$

もし${\displaystyle F=G\oplus H}$それから${\displaystyle F_{x}=G_{x}\oplus H_{x}}$

単調関数の特徴：

Fが単調関数であり、かつ...

Fが正の整数である場合${\displaystyle F=x\cdot F_{x}+F_{x'}}$

Fが負の不等式である場合${\displaystyle F=F_{x}+x'\cdot F_{x'}}$

ブール値の差：

関数Fのリテラルxに関するブール差分またはブール微分は、次のように定義されます。

${\displaystyle {\frac {\partial F}{\partial x}}=F_{x}\oplus F_{x'}}$

全称量化：

Fの普遍量化は次のように定義される。

${\displaystyle \forall xF=F_{x}\cdot F_{x'}}$

存在量化：

Fの存在量化は次のように定義される。

${\displaystyle \exists xF=F_{x}+F_{x'}}$

ジョージ・ブールはこの拡張を、彼の著書『思考の法則』 （1854年）^{[ 3 ]}の命題II「任意の数の論理記号を含む関数を拡張または展開する」として提示し、それは「ブールや他の19世紀の論理学者によって広く応用された」^{[ 4 ] 。}

クロード・シャノンは、1949年の論文^{[ 5 ]}で、他のブール恒等式とともにこの拡張について言及し、その恒等式のスイッチングネットワーク解釈を示した。コンピュータ設計とスイッチング理論の文献では、この恒等式はしばしば誤ってシャノンに帰属されている。^{[ 6 ] [ 4 ]}

1. この定理を体系的に用いることで、二分決定図が得られる。
2. この定理を繰り返し適用することで、基本マルチプレクサの階層構造を用いたスイッチング回路に、任意のブール関数を直接実装することができる。

• リード・ミュラー展開

• 多重化装置を用いたシャノン分解の例。
• シャノン分解とリタイミングによるシーケンシャルサイクルの最適化（PDF）応用に関する論文。