歴史 1927年以前は、ブール代数は論理積 、論理和 、否定 などの論理演算を用いた論理値の計算であると考えられていました。ジェガルキンは、すべてのブール演算は通常の数値多項式で表すことができ、 偽 と真の 値を0と1、つまりmod 2の整数で表すことを示しました。論理積はxyと書き、論理排他的論理和はmod 2の算術加算で表されます（ここでは、+を包含的論理和∨の同義語として一般的に使用することとの混同を避けるためにx⊕yと書きます）。論理補数¬x は x⊕1です 。∧と¬ は ブール代数 の基礎を形成するため、他のすべての論理演算はこれらの基本演算の合成であり、したがって通常の代数の多項式ですべてのブール演算を表すことができ、初等代数 を使用してブール推論を実行できます。
例えば、ブール値の2/3閾値または中央値演算は 、ゼガルキン多項式xy ⊕ yz ⊕ zx と表記されます。
1927年、ジェガルキンの論文と同じ年に[ 2 ] エリック・テンプル・ベルは、 リチャード・デデキント のイデアル理論と一般的なモジュラー算術（mod 2 の算術とは対照的に）に基づいたブール代数の洗練された算術化を発表しました。 [ 3 ] [ 4 ] 彼は、有名なストーン双対性 定理を執筆中に、ブール 代数 と環 の間の緩やかな類似性が、実際には有限代数と無限代数の両方で成り立つ正確な同値性として定式化できることに気づき、その後数年間で論文を大幅に再構成しました。
正式には、ジェガルキン単項式 は、異なる変数の有限集合（したがって 平方因子を持たない ）の積であり、その積は 1 と表記される空集合 も含まれます。各単項式は各変数の有無によって完全に指定されるため、n個の変数に対して 2 n 個 ジェガルキン多項式 は、空集合を 0 と表記したジェガルキン単項式の集合の和（排他的論理和）です。多項式における特定の単項式の存在または非存在は、その単項式の係数がそれぞれ 1 または 0 であることに対応します。ジェガルキン単項式は線形独立であるため、 ガロア体 GF (2)上の2 n ベクトル空間 を張ります（注:乗算がまったく異なるGF (2 n 2 n n 個の変数に対するブール演算 の数と、{0,1} 上のn 項演算を網羅するブール演算の数との正確な一致は、ブール基底としてのジェガルキン多項式の完全性に対する直接的な計数論証を提供する。
このベクトル空間は、 n 個の 生成元を持つ自由ブール代数 とは等価ではありません。なぜなら、演算として補数（ビットごとの論理否定）がないからです（言い換えれば、定数としてトップ要素がないからです）。これは、この空間が補数に関して閉じていないとか、トップ（すべて 1 のベクトル ）が要素としてないという意味ではなく、この空間や同様に構成された空間の線形変換が補数とトップを保存する必要がないという意味です。これらを保存する変換はブール準同型に対応します。例えば、1 変数のジェガルキン多項式のベクトル空間から変数なしのジェガルキン多項式のベクトル空間への線形変換は 4 つありますが、そのうちブール準同型は 2 つだけです。
一般的な用途 ANF は標準形であり、 論理的に同値な 2 つの式は同じ ANF に変換されるため、自動定理証明 において 2 つの式が同値であるかどうかを簡単に示すことができます。他の標準形とは異なり、変数名のリストの単純なリストとして表現できます。連言 標準形と選言 標準形では、各変数が否定されているかどうかも記録する必要があります。否定標準形は 同値性の判定には適していません。否定標準形では、同値性は等価性を意味しないためです。a ∨ ¬a は、論理的に同値であっても 1 と同じものに還元されません。
ANFに数式を記述することで、線形 関数（例えば、線形フィードバックシフトレジスタ で使用される関数）を容易に識別できます。線形関数とは、単一のリテラルの和で表される関数です。また、ANFにおけるフィードバック関数の特定の特性から、非線形フィードバックシフトレジスタ の特性を推測することもできます。
ANF入力に対して標準的なブール演算を実行してANF結果を得るための簡単な方法がいくつかあります。
XOR（論理排他的論理和）は直接実行されます。
( 1 ⊕ x ) ⊕ ( 1 ⊕ x ⊕ y ) 1 ⊕ x ⊕ 1 ⊕ x ⊕ y 1 ⊕ 1 ⊕ x ⊕ x ⊕ y y NOT（論理否定）は1をXORします：[ 5 ]
¬ (1 ⊕ x ⊕ y) 1 ⊕ (1 ⊕ x ⊕ y) 1 ⊕ 1 ⊕ x ⊕ y x ⊕ y AND（論理積）は代数的に分布している [ 6 ]
( 1 ⊕ x ) (1 ⊕ x ⊕ y) 1 (1 ⊕ x ⊕ y) ⊕ x (1 ⊕ x ⊕ y) (1 ⊕ x ⊕ y) ⊕ (x ⊕ x ⊕ xy) 1 ⊕ x ⊕ x ⊕ x ⊕ y ⊕ xy 1 ⊕ x ⊕ y ⊕ xy OR（論理和）は、1 ⊕ (1 ⊕ a)(1 ⊕ b) [ 7 ] [ 8 ]
( 1 ⊕ x ) + ( 1 ⊕ x ⊕ y ) 1 ⊕ (1 ⊕ 1 ⊕ x )(1 ⊕ 1 ⊕ x ⊕ y ) 1 ⊕ x(x ⊕ y) 1 ⊕ x ⊕ xy
数式内の各変数は既に純粋なANF形式になっているため、上記のように数式のブール演算を実行するだけで、数式全体をANF形式にすることができます。例：
x + (y ⋅ ¬z) x + (y(1 ⊕ z)) x + (y ⊕ yz) x ⊕ (y ⊕ yz) ⊕ x(y ⊕ yz) x ⊕ y ⊕ xy ⊕ yz ⊕ xyz
ANFは、時として以下のように表現される。
どこ1 0 、 1 1 、 … 、 1 1 、 2 、 … 、 n ∈ { 0 、 1 } * {\displaystyle a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}} f {\displaystyle f}
多引数ブール関数の再帰的導出 引数が1つの関数は4つしかありません。
f （ x ） = 0 {\displaystyle f(x)=0} f （ x ） = 1 {\displaystyle f(x)=1} f （ x ） = x {\displaystyle f(x)=x} f （ x ） = 1 ⊕ x {\displaystyle f(x)=1\oplus x} 複数の引数を持つ関数を表すには、次の等式を使用できます。
f （ x 1 、 x 2 、 … 、 x n ） = g （ x 2 、 … 、 x n ） ⊕ x 1 h （ x 2 、 … 、 x n ） {\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=g(x_{2},\ldots ,x_{n})\oplus x_{1}h(x_{2},\ldots ,x_{n})} g （ x 2 、 … 、 x n ） = f （ 0 、 x 2 、 … 、 x n ） {\displaystyle g(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 ） {\displaystyle h(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})\oplus f(1,x_{2},\ldots ,x_{n})} 確かに、
もしx 1 = 0 {\displaystyle x_{1}=0} x 1 h = 0 {\displaystyle x_{1}h=0} f （ 0 、 … ） = f （ 0 、 … ） {\displaystyle f(0,\ldots )=f(0,\ldots )} もしx 1 = 1 {\displaystyle x_{1}=1} x 1 h = h {\displaystyle x_{1}h=h} f （ 1 、 … ） = f （ 0 、 … ） ⊕ f （ 0 、 … ） ⊕ f （ 1 、 … ） {\displaystyle f(1,\ldots )=f(0,\ldots )\oplus f(0,\ldots )\oplus f(1,\ldots )} 両方ともg {\displaystyle g} h {\displaystyle h} f {\displaystyle f} f （ x 、 y ） = x ∨ y {\displaystyle f(x,y)=x\lor y}
f （ x 、 y ） = f （ 0 、 y ） ⊕ x （ f （ 0 、 y ） ⊕ f （ 1 、 y ） ） {\displaystyle f(x,y)=f(0,y)\oplus x(f(0,y)\oplus f(1,y))} 以来f （ 0 、 y ） = 0 ∨ y = y {\displaystyle f(0,y)=0\lor y=y} f （ 1 、 y ） = 1 ∨ y = 1 {\displaystyle f(1,y)=1\lor y=1} したがって、f （ x 、 y ） = y ⊕ x （ y ⊕ 1 ） {\displaystyle f(x,y)=y\oplus x(y\oplus 1)} 分配法によって、最終的なANFが得られます。f （ x 、 y ） = y ⊕ x y ⊕ x = x ⊕ y ⊕ x y {\displaystyle f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy}
計算方法 ジェガルキン多項式の計算には、一般的に以下のような様々な方法が知られています。
不定係数法 不定係数法を用いると、関数のすべての組とその値からなる線形システムが生成されます。この線形システムを解くことで、ジェガルキン多項式の係数が得られます。
この方法では、まず標準選言標準形 （完全展開された選言標準形 ）を計算します。次に、この式の否定を、変数と 1 の mod 2 和を用いた同等の式に置き換えます。選言記号を mod 2 の加算に変更し、括弧を開き、結果として得られるブール式を簡略化します。この簡略化により、ジェガルキン多項式が得られます。
テーブルを使用する 表法を用いて例となる関数P のジェガルキン多項式を計算する させてc 0 、 … 、 c 2 n − 1 {\displaystyle c_{0},\dots ,c_{2^{n}-1}} n 個 の変数を持つ関数P の真理値表の出力は、c 私 {\displaystyle c_{i}} 最小項 の二進インデックスに対応します。[ 注2 ] ζ （ c 私 ） := c 私 {\displaystyle \zeta (c_{i}):=c_{i}} ζ （ c 0 、 … 、 c k ） := ζ （ c 0 、 … 、 c k − 1 ） ⊕ ζ （ c 1 、 … 、 c k ） 。 {\displaystyle \zeta (c_{0},\dots ,c_{k}):=\zeta (c_{0},\dots ,c_{k-1})\oplus \zeta (c_{1},\dots ,c_{k}).} ζ （ c 0 、 … 、 c m ） = ⨁ k = 0 m （ m k ） 2 c k {\displaystyle \zeta (c_{0},\dots ,c_{m})=\bigoplus _{k=0}^{m}{m \choose k}_{2}c_{k}} （ m k ） 2 {\textstyle {m \choose k}_{2}} 二項係数を 法 2で簡約したものは何か。
それからg 私 = ζ （ c 0 、 … 、 c 私 ） {\displaystyle g_{i}=\zeta (c_{0},\dots ,c_{i})} は、 i 番目の単項式のリテラルが i 番目 の最小項のリテラルと同じである(ただし、負のリテラルは削除される (または 1 に置き換えられる))ジェガルキン多項式のi 番目 の係数です。
ζ変換はそれ自身の逆変換であるため、同じ種類の表を使用して係数を計算できます。c 0 、 … 、 c 2 n − 1 {\displaystyle c_{0},\dots ,c_{2^{n}-1}} g 0 、 … 、 g 2 n − 1 {\displaystyle g_{0},\dots ,g_{2^{n}-1}} c 私 = ζ （ g 0 、 … 、 g 私 ） 。 {\displaystyle c_{i}=\zeta (g_{0},\dots ,g_{i}).}
図の表に関して、真理値表の出力（P とラベル付けされた列）を三角形表の左端の列にコピーします。次に、左から右へ順に列を計算し、垂直に隣接するセルのペアごとに XOR 演算を適用して、各ペアの上側のセルのすぐ右にあるセルを埋めます。三角形表全体が埋められたら、最上行から線形結合の係数が読み出され、それを簡略化（ゼロを削除）すると、ジェガルキン多項式が得られます。
ジェガルキン多項式から真理値表を作成するには、まず三角形表の最上行をジェガルキン多項式の係数で埋めます（多項式に含まれない正のリテラルの組み合わせにはゼロを代入します）。次に、水平方向に隣接するセルのペアごとにXOR演算を適用し、各ペアの左端のセルのすぐ下のセルを埋めることで、上から下へ順に行を計算します。三角形表全体が埋められたら、その左端の列を真理値表のP列にコピーします。
余談ですが、この計算方法は、ルール 102と呼ばれる基本セル オートマトン の動作方法に対応しています。たとえば、ブール式 10101001 の真理値表 (または標準選言標準形の係数) の出力で設定された 8 つのセルを持つセル オートマトンを開始します。次に、左端のセルの状態を記録しながら、セル オートマトンをさらに 7 世代実行します。このセルの履歴は 11000010 となり、対応する Zhegalkin 多項式の係数を示します。[ 9 ] [ 10 ]
パスカル法 パスカル法を用いてブール関数のジェガルキン多項式を計算する1 ¯ b ¯ c ¯ + 1 ¯ b c ¯ + 1 ¯ b c + 1 b c ¯ {\displaystyle {\bar {a}}{\bar {b}}{\bar {c}}+{\bar {a}}b{\bar {c}}+{\bar {a}}bc+ab{\bar {c}}} ⊕ {\displaystyle \oplus } 計算量と手作業によるジェガルキン多項式の構築方法の効率性という点で最も経済的なのは、パスカル法である。
私たちは、2 N {\displaystyle 2^{N}} N + 1 {\displaystyle N+1} N とした場合のものです。表の最上行には、関数値のベクトル、つまり真理値表の最後の列を配置します。
結果として得られる表の各行は、ブロック（図中の黒線）に分割されます。1行目ではブロックは1つのセルを占め、2行目では2つ、3行目では4つ、4行目では8つ、といった具合です。ある行の各ブロック（これを「下ブロック」と呼びます）は、常に前の行の2つのブロックに対応します。これらを「左上ブロック」と「右上ブロック」と呼びます。
構築は2行目から始まります。左上のブロックの内容は、変更されずに下のブロックの対応するセルに転送されます（図中の緑色の矢印）。次に、右上ブロックと左上のブロックに対してビット単位で「2を法とする加算」演算が実行され、その結果が下のブロックの右側の対応するセルに転送されます（図中の赤色の矢印）。この演算は、上から下まで全ての行、および各行の全てのブロックに対して実行されます。構築が完了すると、最下行には、上記で説明した三角形法と同じ順序で記述された、ジェガルキン多項式の係数である数値列が含まれます。
総和法 変数の数が異なる関数に対する、ジェガルキン多項式の係数のグラフ表示。 真理値表によれば、ジェガルキン多項式の個々の係数を計算するのは簡単です。そのためには、真理値表の中で、論理積（計算対象の係数に対応するもの）に含まれていない変数がゼロの値をとる行の関数の値を、法2で合計します。
例えば、3変数関数のxz連言の係数を求める必要があるとします。 f （ x 、 y 、 z ） {\displaystyle f(x,y,z)} この連言には変数y はありません。変数y がゼロ値をとる入力セットを見つけます。これらはセット 0、1、4、5 (000、001、100、101) です。すると、連言xz の係数は
1 5 = f 0 ⊕ f 1 ⊕ f 4 ⊕ f 5 = f （ 0 、 0 、 0 ） ⊕ f （ 0 、 0 、 1 ） ⊕ f （ 1 、 0 、 0 ） ⊕ f （ 1 、 0 、 1 ） {\displaystyle a_{5}=f_{0}\oplus f_{1}\oplus f_{4}\oplus f_{5}=f(0,0,0)\oplus f(0,0,1)\oplus f(1,0,0)\oplus f(1,0,1)}
定数項を持つ変数がないため、1 0 = f 0 。 {\displaystyle a_{0}=f_{0}.}
すべての変数を含む項の場合、合計には関数のすべての値が含まれます。1 N − 1 = f 0 ⊕ f 1 ⊕ f 2 ⊕ ⋯ ⊕ f N − 2 ⊕ f N − 1 {\displaystyle a_{N-1}=f_{0}\oplus f_{1}\oplus f_{2}\oplus \dots \oplus f_{N-2}\oplus f_{N-1}}
ジェガルキン多項式の係数を、特定の点における関数値の法2の和としてグラフで表してみましょう。そのためには、各列が各点における関数値を表し、各行がジェガルキン多項式の係数を表す正方形の表を作成します。ある列と行の交点にある点は、その点における関数値が、与えられた多項式の係数に対する和に含まれることを意味します（図を参照）。この表をT N {\displaystyle T_{N}} N は関数の変数の数である。
N 変数の関数の表を取得できるパターンがあり、N − 1 {\displaystyle N-1} T N + 1 {\displaystyle T_{N}+1} T N {\displaystyle T_{N}}
カルノー図を使用する カルノー図をジェガルキン多項式に変換する。 図は、カルノー図 として表された3つの変数の関数P ( A , B , C )を示しています。読者はこれを、このような図をジェガルキン多項式に変換する方法の例として考えることができます。一般的な手順は次のとおりです。
カルノー図のすべてのセルを、コード内の単位数の昇順で考えます。3 変数の関数の場合、セルのシーケンスは 000–100–010–001–110–101–011–111 となります。カルノー図の各セルは、コード内の 1 の位置に応じて、ジェガルキン多項式の要素に対応します。たとえば、セル 111 は要素 ABC に対応し、セル 101 は要素 AC に対応し、セル 010 は要素 B に対応し、セル 000 は要素 1 に対応します。 該当するセルの値が0の場合は、次のセルに進みます。 対象のセルが 1 の場合、対応する項をジェガルキン多項式に追加し、この項が 1 である (または単項式のブール格子でこの項によって生成されるイデアル に属する) カルノー図のすべてのセルを反転し、次のセルに進みます。たとえば、セル 110 を調べたときに 1 が現れた場合、項 AB がジェガルキン多項式に追加され、A = 1 かつ B = 1 であるカルノー図のすべてのセルが反転されます。セル 000 に単位がある場合、項 1 がジェガルキン多項式に追加され、カルノー図全体が反転されます。 次の反転処理の後、カルノー図のすべてのセルがゼロ、つまり「気にしなくてよい」状態になった時点で、変換プロセスは完了したとみなすことができます。
メビウス反転公式は、 ブール最小項和式の係数とジェガルキン多項式を関連付けます。これは、数論的なメビウス公式ではなく、半順序版のメビウス公式です。半順序のメビウス反転公式は次のとおりです。[ 11 ] g （ x ） = ∑ y : y ≤ x f （ y ） ↔ f （ x ） = ∑ y : y ≤ x g （ y ） μ （ y 、 x ） 、 {\displaystyle g(x)=\sum _{y:y\leq x}f(y)\leftrightarrow f(x)=\sum _{y:y\leq x}g(y)\mu (y,x),} μ （ y 、 x ） = （ − 1 ） | x | − | y | {\displaystyle \mu (y,x)=(-1)^{|x|-|y|}} x |はx と0のハミング距離である。 − 1 ≡ 1 {\displaystyle -1\equiv 1}
与えられた数x の約数の集合は、その数によって生成される位数イデアル でもある。⟨ x ⟩ {\displaystyle \langle x\rangle } g （ x ） = ⨁ y : y ∈ ⟨ x ⟩ f （ y ） ↔ f （ x ） = ⨁ y : y ∈ ⟨ x ⟩ g （ y ） {\displaystyle g(x)=\bigoplus _{y:y\in \langle x\rangle }f(y)\leftrightarrow f(x)=\bigoplus _{y:y\in \langle x\rangle }g(y)}
例 例として、3つの変数がある場合を考えてみましょう。次の表は、割り算の関係を示しています。
それからg （ 000 ） = f （ 000 ） g （ 001 ） = f （ 000 ） ⊕ f （ 001 ） g （ 010 ） = f （ 000 ） ⊕ f （ 010 ） g （ 011 ） = f （ 000 ） ⊕ f （ 001 ） ⊕ f （ 010 ） ⊕ f （ 011 ） g （ 100 ） = f （ 000 ） ⊕ f （ 100 ） g （ 101 ） = f （ 000 ） ⊕ f （ 001 ） ⊕ f （ 100 ） ⊕ （ 101 ） g （ 110 ） = f （ 000 ） ⊕ f （ 010 ） ⊕ f （ 100 ） ⊕ f （ 110 ） g （ 111 ） = f （ 000 ） ⊕ f （ 001 ） ⊕ f （ 010 ） ⊕ f （ 011 ） ⊕ f （ 100 ） ⊕ f （ 101 ） ⊕ f （ 110 ） ⊕ f （ 111 ） {\displaystyle {\begin{aligned}g(000)&=f(000)\\[1ex]g(001)&=f(000)\oplus f(001)\\[1ex]g(010)&=f(000)\oplus f(010)\\[1ex]g(011)&=f(000)\oplus f(001)\oplus f(010)\oplus f(011)\\[1ex]g(100)&=f(000)\oplus f(100)\\[1ex]g(101)&=f(000)\oplus f(001)\oplus f(100)\oplus (101)\\[1ex]g(110)&=f(000)\oplus f(010)\oplus f(100)\oplus f(110)\\[1ex]g(111)&=f(000)\oplus f(001)\oplus f(010)\oplus f(011)\oplus f(100)\oplus f(101)\oplus f(110)\oplus f(111)\end{aligned}}}
上記の連立方程式はf について解くことができ、その結果は上記の連立方程式全体でg とfを入れ替えることで得られると要約できます。
以下の表は、2進数とそれに対応するジェガルキン単項式およびブール最小項を示しています。
ジェガルキン単項式は自然に割り切れる順序で並べられますが、ブール最小項は自然には並びません。それぞれが3変数ベン図 の排他的8分の1を表します。単項式の順序は、次のようにビット列に反映されます。1 1 1 2 1 3 {\displaystyle a_{1}a_{2}a_{3}} b 1 b 2 b 3 {\displaystyle b_{1}b_{2}b_{3}} 1 1 1 2 1 3 ≤ b 1 b 2 b 3 ↔ 1 1 ≤ b 1 ∧ 1 2 ≤ b 2 ∧ 1 3 ≤ b 3 {\displaystyle a_{1}a_{2}a_{3}\leq b_{1}b_{2}b_{3}\leftrightarrow a_{1}\leq b_{1}\wedge a_{2}\leq b_{2}\wedge a_{3}\leq b_{3}}
3変数ブール最小項和とジェガルキン多項式との対応関係は次のようになる。f （ 000 ） A ¯ B ¯ C ¯ ∨ f （ 001 ） A ¯ B ¯ C ∨ f （ 010 ） A ¯ B C ¯ ∨ f （ 011 ） A ¯ B C ∨ f （ 100 ） A B ¯ C ¯ ∨ f （ 101 ） A B ¯ C ∨ f （ 110 ） A B C ¯ ∨ f （ 111 ） A B C ≡ g （ 000 ） ⊕ g （ 001 ） C ⊕ g （ 010 ） B ⊕ g （ 011 ） B C ⊕ g （ 100 ） A ⊕ g （ 101 ） A C ⊕ g （ 110 ） A B ⊕ g （ 111 ） A B C 。 {\displaystyle {\begin{aligned}&f(000){\bar {A}}{\bar {B}}{\bar {C}}\vee f(001){\bar {A}}{\bar {B}}C\vee f(010){\bar {A}}B{\bar {C}}\vee f(011){\bar {A}}BC\vee f(100)A{\bar {B}}{\bar {C}}\vee f(101)A{\bar {B}}C\vee f(110)AB{\bar {C}}\vee f(111)ABC\\[1ex]&\qquad \equiv g(000)\oplus g(001)C\oplus g(010)B\oplus g(011)BC\oplus g(100)A\oplus g(101)AC\oplus g(110)AB\oplus g(111)ABC.\end{aligned}}}
上記の方程式系は、論理行列 方程式として要約できます。
（ g （ 000 ） g （ 001 ） g （ 010 ） g （ 011 ） g （ 100 ） g （ 101 ） g （ 110 ） g （ 111 ） ） = （ 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 ） （ f （ 000 ） f （ 001 ） f （ 010 ） f （ 011 ） f （ 100 ） f （ 101 ） f （ 110 ） f （ 111 ） ） {\displaystyle {\begin{pmatrix}g(000)\\g(001)\\g(010)\\g(011)\\g(100)\\g(101)\\g(110)\\g(111)\end{pmatrix}}={\begin{pmatrix}1&&0&&0&&0&&0&&0&&0&&0\\1&&1&&0&&0&&0&&0&&0&&0\\1&&0&&1&&0&&0&&0&&0&&0\\1&&1&&1&&1&&0&&0&&0&&0\\1&&0&&0&&0&&1&&0&&0&&0\\1&&1&&0&&0&&1&&1&&0&&0\\1&&0&&1&&0&&1&&0&&1&&0\\1&&1&&1&&1&&1&&1&&1&&1\end{pmatrix}}{\begin{pmatrix}f(000)\\f(001)\\f(010)\\f(011)\\f(100)\\f(101)\\f(110)\\f(111)\end{pmatrix}}}
NJ・ワイルドバーガーは これをブール・メビウス変換と呼んでいる。
以下に、 gから f への変換の「XORスプレッドシート 」形式を示します。
上述の代数標準形では正極性のみを使用し、各変数は非補数形式でのみ現れます。より一般的には、固定極性リード・ミュラー（FPRM）展開では、 各変数は補数形式または非補数形式のいずれかで現れ、極性はすべての項で固定されます。異なる極性を選択すると、n 個 の変数を持つ関数に対して2 n 個の 排他的論理和積和（ESOP） 展開は、同じ式内で混合極性を許容することでさらに一般化され、各積項は独立して補数または非補数のリテラルを使用できます。ESOP 最小化、つまり積項が最小の表現を見つけることは、論理合成における活発な研究分野であり、可逆回路や量子回路設計に応用されています。
1993年以来、ブール問題に関する国際ワークショップ（元々はリード・ミュラーワークショップ）は隔年で開催され、リード・ミュラー展開、ESOP最小化、スイッチング理論および論理合成における関連トピックに取り組む研究者が集まっている。[ 12 ]
参考文献 ↑ Steinbach, Bernd [ドイツ語] ; Posthoff, Christian (2009). 「序文」.論理関数と方程式 - 例と演習 (第 1 版). Springer Science + Business Media BV p. xv. ISBN 978-1-4020-9594-8 。LCCN 2008941076。 1 2 Жега́лкин [Zhegalkin]、Ива́н Ива́нович [Ivan Ivanovich] (1927)。 「おおテクニケ・ヴィチスレニ・プレドロジェニ対シンボリチェスコイ・ロジキエ」 О технике вычислений предложений в символической логике [ 記号論理学における命題の計算手法について (Sur le calcul des propositions dans la logiqueSymbolique) ] 。Matematicheskii Sbornik 34 (1)。モスクワ、ロシア: 9–28 . Mi msb7433。2017-10-12 のオリジナルからアーカイブ。 2017 年 10 月 12 日 に取得 。 ↑ Bell, Eric Temple (1927). "論理の算術" . Transactions of the American Mathematical Society . 29 (3): 597– 611. doi : 10.2307/1989098 . JSTOR 1989098 . ↑ Stone, Marshall (1936). "ブール代数の表現理論". アメリカ数学会紀要 . 40 (1): 37– 111. doi : 10.2307/1989664 . ISSN 0002-9947 . JSTOR 1989664 . ↑ WolframAlphaによるNOT等価性の証明：¬a = 1 ⊕ a ↑ WolframAlphaによるAND等価性の証明：(a ⊕ b)(c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd ↑ ド・モルガンの法則 より ↑ WolframAlphaによるOR等価性の証明：a + b = a ⊕ b ⊕ ab ↑ スープラン [Супрун]、ヴァレリー P. [Валерий Павлович] (1987)。 「タブリチヌイ法多項式ノゴ・ラズロジェニヤ・ブレヴィフ・ファンクツィー」 Табличный метод полиномиального разложения булевых функций [ ブール関数の多項式分解の表形式法] .サイバネティクス ( ロシア語) (1): 116–117 .↑ スープラン [Супрун]、ヴァレリー P. [Валерий Павлович] (2017)。 「オスノヴィ・テオリイ・ブレヴィフ・ファンクツィー」 Основы теории булевых функций [ ブール関数理論の基礎] 。М.: レナンド [Ленанд] / URSS (ロシア語): 208.↑ 「メビウス反転」 。 数学百科事典 。2021年2月17日 [2011年2月7日]。 2020年7月16日のオリジナルから アーカイブ。 2021年3月27日 取得 。 ↑ 「リード・ミュラーワークショップの歴史」 。 2026年4月15日 取得 。
さらに読む ウェゲナー、インゴ （1987）。ブール関数の複雑性 。ワイリー・トイブナー 。p . 6。ISBN 3-519-02107-2 。「プレゼンテーション」（PDF） （ドイツ語）。デュイスブルク＝エッセン大学 。2017年4月20日にオリジナルからアーカイブ（PDF） 。 2017年4月19日 に取得 。 マックスフィールド、クライヴ「マックス」（2006年11月29日）。「リード・ミュラー論理」。論理学入門。EETimes 。パート3。 2017年4月 19日のオリジナルからアーカイブ。2017年4月19日 に取得。 ギンディキン [Гиндикин]、ザーメン グリゴレヴィチ [Семен Г.] (1972)。代数論理 Малгебра логики в задачах [ 代数論理 ] （ ロシア語）（第1 版）。モスクワ、ロシア：ナウカ [Nauka] 。ISBN 0-387-96179-8 。 シュプリンガー・フェルラーク 、1985年)）Perkowski, Marek A.; Grygiel, Stanislaw (1995-11-20). "6. 分解に関する研究の歴史的概観".関数分解に関する文献調査 . バージョン IV. 関数分解グループ、ポートランド大学電気工学科、ポートランド、オレゴン州、アメリカ合衆国. pp. 21–22 . CiteSeerX 10.1.1.64.1129 . Жега́лкин [Zhegalkin]、Ива́н Ива́нович [Ivan Ivanovich] (1927)。「おおテクニケ・ヴィチスレニ・プレドロジェニ対シンボリチェスコイ・ロジキエ」О технике вычислений предложений в символической логике [ 記号論理学における命題の計算手法について (Sur le calcul des propositions dans la logiqueSymbolique) ] 。Matematicheskii Sbornik 34 (1)。モスクワ、ロシア: 9–28 . Mi msb7433。2017-10-12 のオリジナルからアーカイブ。 2017 年 10 月 12 日 に取得 。 リード、アーヴィング・ストイ （1954年9月）。「多重誤り訂正符号のクラスと復号方式」。IRE Transactions on Information Theory。IT 4 ：38-49 。ミュラー、デイビッド・ユージーン （1954年9月）。「ブール代数のスイッチング回路設計およびエラー検出への応用」。IRE Transactions on Electronic Computers。EC -3 ：6-12 。Kebschull, Udo; Rosenstiel, Wolfgang (1993). 「機能決定図の効率的なグラフベースの計算と操作」.第 4 回欧州設計自動化会議議事録 : 278–282 . マックスフィールド、クライヴ「マックス」（2006年11月29日）。「リード・ミュラー論理」。論理学入門。EETimes 。パート3。 2017年4月 19日のオリジナルからアーカイブ。2017年4月19日 に取得。 シュタインバッハ、ベルント [ドイツ語] ; ポストホフ、クリスティアン (2009)。「序文」。論理関数と方程式 - 例と演習 (第 1 版)。Springer Science + Business Media BV 、 p. xv。ISBN 978-1-4020-9594-8 。LCCN 2008941076。 Perkowski, Marek A.; Grygiel, Stanislaw (1995-11-20). "6. 分解に関する研究の歴史的概観".関数分解に関する文献調査 . バージョン IV. 関数分解グループ、ポートランド大学電気工学科、ポートランド、オレゴン州、アメリカ合衆国. pp. 21–22 . CiteSeerX 10.1.1.64.1129 .
![{\displaystyle {\begin{aligned}g(000)&=f(000)\\[1ex]g(001)&=f(000)\oplus f(001)\\[1ex]g(010)&=f(000)\oplus f(010)\\[1ex]g(011)&=f(000)\oplus f(001)\oplus f(010)\oplus f(011)\\[1ex]g(100)&=f(000)\oplus f(100)\\[1ex]g(101)&=f(000)\oplus f(001)\oplus f(100)\oplus (101)\\[1ex]g(110)&=f(000)\oplus f(010)\oplus f(100)\oplus f(110)\\[1ex]g(111)&=f(000)\oplus f(001)\oplus f(010)\oplus f(011)\oplus f(100)\oplus f(101)\oplus f(110)\oplus f(111)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/559beb6c1c918defe1f36762b95185f36036b31f)
![{\displaystyle {\begin{aligned}&f(000){\bar {A}}{\bar {B}}{\bar {C}}\vee f(001){\bar {A}}{\bar {B}}C\vee f(010){\bar {A}}B{\bar {C}}\vee f(011){\bar {A}}BC\vee f(100)A{\bar {B}}{\bar {C}}\vee f(101)A{\bar {B}}C\vee f(110)AB{\bar {C}}\vee f(111)ABC\\[1ex]&\qquad \equiv g(000)\oplus g(001)C\oplus g(010)B\oplus g(011)BC\oplus g(100)A\oplus g(101)AC\oplus g(110)AB\oplus g(111)ABC.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b499a2671d54e34f1c9c94fee059e5dbbe5719e)
