Concept in mathematics
ジェガルキン 多項式 （ ロシア語 ： полиномы Жегалкина ） は 代数正規形 とも呼ばれ、 ブール代数 における関数の表現法である。 1927年に ロシアの数学者 イヴァン ・ イヴァノビッチ ・ ジェガルキンによって導入された [2]。 これ は 2 を法とする整数 上の 多項式環である。 モジュラー演算 の結果生じる退化 により、ジェガルキン多項式は通常の多項式よりも単純となり、係数も指数も不要になる。係数は冗長である。なぜなら、1は唯一の非ゼロ係数である。指数は、2を法とする演算では x 2 = x であるためである。したがって、 3 x 2 y 5 z などの多項式は xyz と合同なので、次のように書き直すことができます 。
ブール値の同等物 1927 年より前、ブール代数は、 論理積 、 選言 、 否定 など の論理演算を伴う 論理値の計算であると考えられていました。ジェガルキンは、すべてのブール演算が通常の数値多項式で表すことができ、 偽 値と 真値 を 0 と 1、つまり 2 を法とする整数で表せることを示しました。論理積は xy と表され、 排他的論理和は 2 を法とする算術加算 ( 包括論理和 ∨ の同義語として + がよく使用されるため、ここでは x ⊕ yと表記) と表記されます。したがって、論理補集合 ¬ x は x ⊕1 です。∧ と ¬ はブール代数の基礎となるため、他のすべての論理演算はこれらの基本演算の合成となり、通常の代数の多項式ですべてのブール演算を表せるため、 初等代数 を使用してブール推論を実行できます 。
たとえば、ブール値の 2-out-of-3 しきい値または 中央値演算は 、Zhegalkin 多項式 xy ⊕ yz ⊕ zx と記述されます。
正式には、 ジェガルキン単項式 は有限個の異なる変数の積（したがって 平方フリー ）であり、積が 1 で示される空集合も含まれる。 各単項式は各変数の有無によって完全に指定されるため、 n 個の変数を持つジェガルキン単項式は2 n 通り存在する。ジェガルキン多項式 は、空集合を 0 で示すジェガルキン単項式集合の和（排他的論理和）である。多項式における特定の単項式の存在または不在は、その単項式の係数がそれぞれ 1 または 0 であることに対応している。ジェガルキン単項式は 線形独立であり、 ガロア体 GF (2)上の 2 n 次元 ベクトル空間 に張られる（注：乗算が全く異なる GF (2 n ) ではない）。この空間の 2 2 n ベクトル、すなわち単位ベクトルとしてのそれらの単項式の線形結合は、ジェガルキン多項式を構成する。 n 変数 に対する ブール演算 の数（{0,1} に対する n 項演算をすべて網羅）との正確な一致は、ブール基底としての Zhegalkin 多項式の完全性を直接的に数える議論を提供します。
このベクトル空間は、 演算として補項（ビット論理否定）を欠いているため（同様に、定数としてトップ要素を欠いているため）、 n 個の生成子上の 自由ブール代数とは等価ではない。これは、空間が補項に関して閉じていない、あるいはトップ要素（ すべて1のベクトル ）を要素として欠いているということではなく、この空間や同様に構築された空間の線型変換は、補項とトップ要素を保存する必要がないということである。これらを保存する線型変換はブール準同型に対応する。例えば、1変数のジェガルキン多項式のベクトル空間から変数のないベクトル空間への線型変換は4つあるが、そのうちブール準同型は2つだけである。
計算方法 Zhegalkin多項式の計算には、一般的にさまざまな既知の方法が使用されます。
不定係数法を用いる 標準的な選言正規形を構築することによって 表を使うことで パスカル法 合計法 カルノー図の使用
不定係数法 不定係数法を用いて、関数のすべての組とその値からなる線形方程式を生成します。この線形方程式を解くことで、ジェガルキン多項式の係数が得られます。
例 ブール関数 が与えられたとき 、それをゼガルキン多項式として表す。この関数は列ベクトルとして表すことができる。 f ( A , B , C ) = A ¯ B ¯ C ¯ + A ¯ B C ¯ + A B ¯ C ¯ + A B C {\displaystyle f(A,B,C)={\bar {A}}{\bar {B}}{\bar {C}}+{\bar {A}}B{\bar {C}}+A{\bar {B}}{\bar {C}}+ABC} f → = ( 1 0 1 0 1 0 0 1 ) . {\displaystyle {\vec {f}}={\begin{pmatrix}1\\0\\1\\0\\1\\0\\0\\1\end{pmatrix}}.}
このベクトルは、A、B、Cの全ての可能な論理積が取り得る値を表す8x8の 論理 行列を、未定係数のベクトルに左乗算した出力である 。これらの可能な値は、以下の真理値表に示されている。 c → = ( c 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 ) {\displaystyle {\vec {c}}={\begin{pmatrix}c_{0}\\c_{1}\\c_{2}\\c_{3}\\c_{4}\\c_{5}\\c_{6}\\c_{7}\end{pmatrix}}}
あ B C 1 C B 紀元前 あ 交流 AB ABC 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1
上記の真理値表の情報は、次の論理行列にエンコードできます。 ここで、「S」は「Sierpiński」を表します。これは、 Sierpiński 三角形 の場合と同じです。また、下付き文字の 3 は、その大きさの指数を示します 。 S 3 = ( 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 ) {\displaystyle S_{3}={\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}}} 2 3 × 2 3 {\displaystyle 2^{3}\times 2^{3}}
数学的帰納法とブロック行列乗算によって、そのような「シェルピンスキー行列」はそれ自身の逆行列であることが証明できる 。 [注 1] S n {\displaystyle S_{n}}
すると、線形システムは 次のようになり、これを解くことができます 。 [ 説明が必要 ] また、対応する Zhegalkin 多項式は です 。 S 3 c → = f → {\displaystyle S_{3}{\vec {c}}={\vec {f}}} c → {\displaystyle {\vec {c}}} c → = S 3 − 1 f → = S 3 f → = ( 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 ) ( 1 0 1 0 1 0 0 1 ) = ( 1 1 1 ⊕ 1 1 ⊕ 1 1 ⊕ 1 1 ⊕ 1 1 ⊕ 1 ⊕ 1 1 ⊕ 1 ⊕ 1 ⊕ 1 ) = ( 1 1 0 0 0 0 1 0 ) , {\displaystyle {\vec {c}}=S_{3}^{-1}{\vec {f}}=S_{3}{\vec {f}}={\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}1\\0\\1\\0\\1\\0\\0\\1\end{pmatrix}}={\begin{pmatrix}1\\1\\1\oplus 1\\1\oplus 1\\1\oplus 1\\1\oplus 1\\1\oplus 1\oplus 1\\1\oplus 1\oplus 1\oplus 1\end{pmatrix}}={\begin{pmatrix}1\\1\\0\\0\\0\\0\\1\\0\end{pmatrix}},} c → {\displaystyle {\vec {c}}} 1 ⊕ C ⊕ A B {\displaystyle 1\oplus C\oplus AB}
この手法を用いると、まず 標準選言正規形 （完全に展開された 選言正規形 ）が計算される。次に、この式の否定を、変数と1のmod 2の和を用いた等価な式に置き換える。選言符号はmod 2の加算に変換され、括弧が開かれ、結果として得られるブール式は簡略化される。この簡略化により、Zhegalkin多項式が得られる。
表の使用 例題関数 P のZhegalkin多項式を表法で計算する をn 変数の関数 P の真理値表の出力とし 、のインデックスが 最小項 の2進インデックスに対応するものとします。[nb 2] 関数ζを再帰的に定義します。ここで、は2を法として約分された二 項 係数 で ある こと に 注意 し て ください 。 c 0 , … , c 2 n − 1 {\displaystyle c_{0},\dots ,c_{2^{n}-1}} c i {\displaystyle c_{i}} ζ ( c i ) := c i {\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}}
は 、負のリテラルが削除される（または 1 に置き換えられる）ことを除いて、 i 番目の単項式のリテラルが i 番目 の 最小 項のリテラルと同じである Zhegalkin 多項式の i 番目 の係数
です。 g i = ζ ( c 0 , … , c i ) {\displaystyle g_{i}=\zeta (c_{0},\dots ,c_{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 i = ζ ( g 0 , … , g i ) . {\displaystyle c_{i}=\zeta (g_{0},\dots ,g_{i}).}
図の表に当てはめると、真理値表の出力（ P とラベル付けされた列）を三角表の左端の列にコピーします。次に、垂直方向に隣接するセルの各ペアにXORを適用することで、左から右へと列を順に計算し、各ペアの最上位セルのすぐ右のセルを埋めていきます。三角表全体が埋められると、最上行には線形結合の係数が示され、これを簡略化する（ゼロを削除する）と、Zhegalkin多項式が得られます。
ジェガルキン多項式から真理値表を作成するには、三角表の最上行をジェガルキン多項式の係数で埋めることができます（多項式に含まれない正のリテラルの組み合わせにはゼロを代入します）。次に、水平方向に隣接するセルの各ペアにXORを適用し、各ペアの左端のセルのすぐ下までセルを埋めるように、上から下に向かって行を順に計算します。三角表全体が埋められたら、その左端の列を 真理値表の P列にコピーできます。
余談ですが、この計算方法は、ルール102と呼ばれる 基本的なセルオートマトン の動作方法に対応しています。例えば、ブール式10101001の真理値表の出力（または標準選言正規形の係数）を持つ8つのセルを持つセルオートマトンを開始します。次に、左端のセルの状態を記録しながら、セルオートマトンをさらに7世代実行します。このセルの履歴は11000010となり、これは対応するジェガルキン多項式の係数を示しています。 [3] [4]
パスカル法 パスカル法を用いてブール関数のジェガルキン多項式を計算します 。下部のロシア語の行には、 「ビット演算「排他的論理和」」と書かれています。 a ¯ b ¯ c ¯ + a ¯ b c ¯ + a ¯ b c + a b c ¯ {\displaystyle {\bar {a}}{\bar {b}}{\bar {c}}+{\bar {a}}b{\bar {c}}+{\bar {a}}bc+ab{\bar {c}}} ⊕ {\displaystyle \oplus } 計算量と Zhegalkin 多項式を手動で構築する手段の点で最も経済的なのは、パスカル法です。
列と行 からなる表を作成します 。ここで、 N は関数の変数の数です。表の一番上の行には、関数値のベクトル、つまり真理値表の最後の列を配置します。 2 N {\displaystyle 2^{N}} N + 1 {\displaystyle N+1}
結果の表の各行は、ブロック（図の黒い線）に分割されます。1行目ではブロックは1つのセルを占有し、2行目では2つ、3行目では4つ、4行目では8つ、というように、セルを占有します。各行のブロック（ここでは「下ブロック」と呼びます）は、常に前の行の2つのブロックに対応します。これらを「左上ブロック」と「右上ブロック」と呼びます。
構築は2行目から始まります。左上のブロックの内容は、そのまま下のブロックの対応するセルに転送されます（図の緑の矢印）。次に、右上と左上のブロックに対して「2を法とする加算」という演算をビット単位で実行し、その結果を下のブロックの右側の対応するセルに転送します（図の赤い矢印）。この演算は、上から下まですべての行と、各行のすべてのブロックに対して実行されます。構築が完了すると、最下行には、前述の三角形法と同じ順序で書かれた、ゼガルキン多項式の係数である数値の列が含まれます。
合計法 変数の数が異なる関数の Zhegalkin 多項式の係数のグラフ表現。 真理値表によれば、ジェガルキン多項式の個々の係数は簡単に計算できます。そのためには、真理値表の行のうち、接続詞に含まれない変数（計算対象の係数に対応する変数）がゼロ値を取る行の関数の値を、2を法として合計します。
例えば、 3変数関数の xz 連立方程式の係数を求める必要があるとします。この連立方程式には変数 y は存在しません。変数 y が0となる入力集合を求めます。これらは0、1、4、5（000、001、100、101）です。すると、連立方程式 xz の係数は f ( x , y , z ) {\displaystyle f(x,y,z)}
a 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)}
定数項を持つ変数はないので、 a 0 = f 0 . {\displaystyle a_{0}=f_{0}.}
すべての変数を含む項の場合、合計には関数のすべての値が含まれます。 a 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を法とする和としてグラフィカルに表してみましょう。そのために、正方形の表を作成します。各列は関数の特定の点における値を表し、行はジェガルキン多項式の係数を表します。ある列と行の交点は、この点における関数の値が、多項式の与えられた係数の和に含まれることを意味します（図を参照）。この表を と呼びます。 ここで、 N は関数の変数の数です。 T N {\displaystyle T_{N}}
N 変数の関数の表を、変数の関数の表から 作成できるパターンがあります 。新しい表は 2×2の表の行列として配置され 、行列の右上のブロックはクリアされます。 N − 1 {\displaystyle N-1} T N + 1 {\displaystyle T_{N}+1} T N {\displaystyle T_{N}}
格子理論的解釈 表の列が、 サイズ の ブール格子 の要素に対応するとします 。各列について、 数 M を2進数 で表すと 、 が成り立ちます。ただし 、 は ビット ごとの論理和を表します。 T N {\displaystyle T_{N}} 2 N {\displaystyle 2^{N}} f M {\displaystyle f_{M}} M 2 {\displaystyle M_{2}} f M ≤ f K {\displaystyle f_{M}\leq f_{K}} M 2 ∨ K 2 = K 2 {\displaystyle M_{2}\vee K_{2}=K_{2}} ∨ {\displaystyle \vee }
表の行に 上から下に 0 から までの番号が付けられている場合、行番号 R の表の内容は、 格子の 要素によって生成された イデアル です。 T N {\displaystyle T_{N}} 2 N − 1 {\displaystyle 2^{N}-1} f R {\displaystyle f_{R}}
ちなみに、表全体のパターンは、 論理行列 シェルピンスキー三角形 のパターンであることに注意してください 。また、このパターンはルール60と呼ばれる 基本的なセルオートマトン に対応しており、左端のセルを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がジェガルキン多項式に追加され、カルノー図全体が反転されます。 次の反転後にカルノー図のすべてのセルがゼロ、つまり don't care 状態になったときに、変換プロセスは完了したとみなされます。
メビウス の逆関数公式は、 ブール最小項和式とジェガルキン多項式の係数を関連付けます。これはメビウスの逆関数公式の半順序版であり、数論的な公式ではありません。半順序版のメビウスの逆関数公式は [5] です。
ここで 、| x |は 0からの x の ハミング距離 です。ジェガルキン代数では、メビウス関数は定数1に縮退するためです。 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|}} − 1 ≡ 1 {\displaystyle -1\equiv 1}
与えられた数x の約数の集合は、 その数によって生成される 位数イデアル でもある 。和は2を法とするため、この式は次のように言い換えられる。 ⟨ 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変数の場合を考えてみましょう。次の表は割り切れる関係を示しています。
× x の約数 000 000 001 000, 001 010 000, 010 011 000、001、010、011 100 000, 100 101 000、001、100、101 110 000、010、100、110 111 000、001、010、011、100、101、110、111
それから 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 進数とそれに関連する Zhegalkin 単項式およびブール最小項を示しています。
ブール最小項 ABC ジェガルキン単項式 A ¯ B ¯ C ¯ {\displaystyle {\bar {A}}{\bar {B}}{\bar {C}}} 000 1 A ¯ B ¯ C {\displaystyle {\bar {A}}{\bar {B}}C} 001 C A ¯ B C ¯ {\displaystyle {\bar {A}}B{\bar {C}}} 010 B A ¯ B C {\displaystyle {\bar {A}}BC} 011 紀元前 A B ¯ C ¯ {\displaystyle A{\bar {B}}{\bar {C}}} 100 あ A B ¯ C {\displaystyle A{\bar {B}}C} 101 交流 A B C ¯ {\displaystyle AB{\bar {C}}} 110 AB A B C {\displaystyle ABC} 111 ABC
ジェガルキン単項式は割り切れる順序で自然に順序付けられますが、ブール最小項式はそれほど自然に順序付けられません。各単項式は3変数 ベン図 の8分の1を表します。単項式の順序はビット文字列に次のように変換されます。 と 、ビットトリプレットのペアが与えられている場合、 となります 。 a 1 a 2 a 3 {\displaystyle a_{1}a_{2}a_{3}} b 1 b 2 b 3 {\displaystyle b_{1}b_{2}b_{3}} a 1 a 2 a 3 ≤ b 1 b 2 b 3 ↔ a 1 ≤ b 1 ∧ a 2 ≤ b 2 ∧ a 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変数ブール最小項の和とZhegalkin多項式の間の対応は次のようになります。 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 Wildberger は これを ブール・メビウス変換と呼んでいます。
以下に、 gから f の方向 への変換の 「XOR スプレッドシート 」形式を示します。
f 000 {\displaystyle f_{000}} f 001 {\displaystyle f_{001}} f 010 {\displaystyle f_{010}} f 011 {\displaystyle f_{011}} f 100 {\displaystyle f_{100}} f 101 {\displaystyle f_{101}} f 110 {\displaystyle f_{110}} f 111 {\displaystyle f_{111}} g 000 {\displaystyle g_{000}} g 000 ⊕ g 001 {\displaystyle g_{000}\oplus g_{001}} g 000 ⊕ g 010 {\displaystyle g_{000}\oplus g_{010}} g 000 ⊕ g 010 ⊕ g 001 ⊕ g 011 {\displaystyle g_{000}\oplus g_{010}\oplus g_{001}\oplus g_{011}} g 000 ⊕ g 100 {\displaystyle g_{000}\oplus g_{100}} g 000 ⊕ g 100 ⊕ g 001 ⊕ g 101 {\displaystyle g_{000}\oplus g_{100}\oplus g_{001}\oplus g_{101}} g 000 ⊕ g 100 ⊕ g 010 ⊕ g 110 {\displaystyle g_{000}\oplus g_{100}\oplus g_{010}\oplus g_{110}} g 000 ⊕ g 100 ⊕ g 010 ⊕ g 110 ⊕ g 001 ⊕ g 101 ⊕ g 011 ⊕ g 111 {\displaystyle g_{000}\oplus g_{100}\oplus g_{010}\oplus g_{110}\oplus g_{001}\oplus g_{101}\oplus g_{011}\oplus g_{111}} g 001 {\displaystyle g_{001}} g 001 ⊕ g 010 {\displaystyle g_{001}\oplus g_{010}} g 001 ⊕ g 011 {\displaystyle g_{001}\oplus g_{011}} g 001 ⊕ g 011 ⊕ g 010 ⊕ g 100 {\displaystyle g_{001}\oplus g_{011}\oplus g_{010}\oplus g_{100}} g 001 ⊕ g 101 {\displaystyle g_{001}\oplus g_{101}} g 001 ⊕ g 101 ⊕ g 010 ⊕ g 110 {\displaystyle g_{001}\oplus g_{101}\oplus g_{010}\oplus g_{110}} g 001 ⊕ g 101 ⊕ g 011 ⊕ g 111 {\displaystyle g_{001}\oplus g_{101}\oplus g_{011}\oplus g_{111}} g 010 {\displaystyle g_{010}} g 010 ⊕ g 011 {\displaystyle g_{010}\oplus g_{011}} g 010 ⊕ g 100 {\displaystyle g_{010}\oplus g_{100}} g 010 ⊕ g 100 ⊕ g 011 ⊕ g 101 {\displaystyle g_{010}\oplus g_{100}\oplus g_{011}\oplus g_{101}} g 010 ⊕ g 110 {\displaystyle g_{010}\oplus g_{110}} g 010 ⊕ g 110 ⊕ g 011 ⊕ g 111 {\displaystyle g_{010}\oplus g_{110}\oplus g_{011}\oplus g_{111}} g 011 {\displaystyle g_{011}} g 011 ⊕ g 100 {\displaystyle g_{011}\oplus g_{100}} g 011 ⊕ g 101 {\displaystyle g_{011}\oplus g_{101}} g 011 ⊕ g 101 ⊕ g 100 ⊕ g 110 {\displaystyle g_{011}\oplus g_{101}\oplus g_{100}\oplus g_{110}} g 011 ⊕ g 111 {\displaystyle g_{011}\oplus g_{111}} g 100 {\displaystyle g_{100}} g 100 ⊕ g 101 {\displaystyle g_{100}\oplus g_{101}} g 100 ⊕ g 110 {\displaystyle g_{100}\oplus g_{110}} g 100 ⊕ g 110 ⊕ g 101 ⊕ g 111 {\displaystyle g_{100}\oplus g_{110}\oplus g_{101}\oplus g_{111}} g 101 {\displaystyle g_{101}} g 101 ⊕ g 110 {\displaystyle g_{101}\oplus g_{110}} g 101 ⊕ g 111 {\displaystyle g_{101}\oplus g_{111}} g 110 {\displaystyle g_{110}} g 110 ⊕ g 111 {\displaystyle g_{110}\oplus g_{111}} g 111 {\displaystyle g_{111}}
1927年、ジェガルキンの論文と同じ年に、 [2] アメリカの数学者 エリック・テンプル・ベル がリチャード・デデキント のイデアル理論と一般モジュラー算術（2を法とする算術とは対照的） に基づいたブール代数の洗練された算術化を発表しました。 [6] ジェガルキン多項式のはるかに単純な算術的特徴に西側で初めて気づいたのは（当時ソ連と西側の数学者の交流は非常に限られていたため、独立して） 1936年 、[7]アメリカの数学者 マーシャル・ストーンでした。ストーンは、有名な ストーン双対 定理を書いているときに、 ブール代数 と 環 の間のいわゆる緩い類似性が、 実際には有限代数と無限代数の両方に成り立つ正確な同値として定式化できることに気づき、その後数年間にわたって論文を大幅に再構成することになりました。
参照
注記 ^ 基本ケースとして、 ここで は サイズ の 単位行列 を表すものとする 。帰納的仮定は である。 そして、帰納的ステップは以下の通りである。 ここで は クロネッカー積 を表す。あるいは 、 クロネッカー積を用いて次のように 表す。QED S 0 := ( 1 ) {\displaystyle S_{0}:={\begin{pmatrix}1\end{pmatrix}}} ( S 0 ) 2 = ( 1 ) = I 0 {\displaystyle (S_{0})^{2}={\begin{pmatrix}1\end{pmatrix}}=I_{0}} I n {\displaystyle I_{n}} 2 n × 2 n {\displaystyle 2^{n}\times 2^{n}} ( S n ) 2 = I n . {\displaystyle (S_{n})^{2}=I_{n}.} S n + 1 := ( S n O S n S n ) ≡ ( 1 0 1 1 ) ⊗ S n , {\displaystyle S_{n+1}:={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}\equiv {\begin{pmatrix}1&0\\1&1\end{pmatrix}}\otimes S_{n},} ⊗ {\displaystyle \otimes } ( S n + 1 ) 2 = ( S n O S n S n ) ( S n O S n S n ) = ( S n S n ⊕ O S n S n O ⊕ O S n S n S n ⊕ S n S n S n O ⊕ S n S n ) = ( I n O I n ⊕ I n I n ) = ( I n O O I n ) = I n + 1 , {\displaystyle (S_{n+1})^{2}={\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}{\begin{pmatrix}S_{n}&O\\S_{n}&S_{n}\end{pmatrix}}={\begin{pmatrix}S_{n}S_{n}\oplus OS_{n}&S_{n}O\oplus OS_{n}\\S_{n}S_{n}\oplus S_{n}S_{n}&S_{n}O\oplus S_{n}S_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\I_{n}\oplus I_{n}&I_{n}\end{pmatrix}}={\begin{pmatrix}I_{n}&O\\O&I_{n}\end{pmatrix}}=I_{n+1},} S n + 1 2 = ( S 1 ⊗ S n ) ( S 1 ⊗ S n ) = S 1 2 ⊗ S n 2 = I 1 ⊗ I n = I n + 1 . {\displaystyle S_{n+1}^{2}=(S_{1}\otimes S_{n})(S_{1}\otimes S_{n})=S_{1}^{2}\otimes S_{n}^{2}=I_{1}\otimes I_{n}=I_{n+1}.} ^ 最小 項は、ジェガルキン 単項式 のブール版です 。 n 変数コンテキストでは、ジェガルキン単項式と ブール最小項も 存在します。 n変数コンテキストの最小項は、 n 個のリテラルの AND 積で構成されます。 各リテラルは、コンテキスト内の変数、またはそのような変数の NOT 否定のいずれかです。さらに、コンテキスト内の各変数に対して、各最小項には対応するリテラル（その変数の表明または否定のいずれか）が 1 回だけ出現する必要があります。 n 変数のブール関数の真理値表は正確に 行あり 、各行の入力は、そのブール関数の独立変数の集合をコンテキストとする最小項に自然に対応します。 (各 0 入力は否定変数に対応し、各 1 入力は肯定変数に対応します。) 任意のブール式は、AND を OR に関して、NOT を AND または OR に関して (ド・モルガン恒等式を通じて) 繰り返し分配し、二重否定を打ち消す (否定正規形 を参照 ) ことによって、最小項の和の形式に変換できます。次に、積の和が得られたら、欠落したリテラルを含む積と、欠落したリテラルを含む排中律のインスタンスを乗算します 。 最後に、AND を再び OR に関して分配します。特定のコンテキストでは、Zhegalkin 単項式とブール最小項の間に形式的な対応があることに注意してください。 ただし 、この対応は論理的に同値ではありません。たとえば、コンテキスト { A 、 B 、 C } では、Zhegalkin 単項式 AB とブール最小項 の間に形式的な対応があります が、それらは論理的に同値ではありません。 (この例の詳細については、「メビウス変換」セクションの 2 番目の表を参照してください。ブール最小項のセットと Zhegalkin 単項式のセットの両方をインデックスするために、同じビット文字列のセットが使用されます。) 2 n {\displaystyle 2^{n}} 2 n {\displaystyle 2^{n}} 2 n {\displaystyle 2^{n}} A B C ¯ {\displaystyle AB{\bar {C}}}
参考文献 ^ Steinbach, Bernd [ドイツ語] ; Posthoff, Christian (2009). 「序文」. ドイツのフライベルクで執筆. 論理関数と方程式 - 例題と演習 (第1版). ドルドレヒト, オランダ: Springer Science + Business Media BV p. xv. ISBN 978-1-4020-9594-8 。 LCCN 2008941076。 ^ ab Жега́лкин [Zhegalkin]、Ива́н Ива́нович [Ivan Ivanovich] (1927). 「O Tekhnyke Vychyslenyi Predlozhenyi v Symbolytscheskoi Logykye」 О технике вычислений предложений в символической логике [記号論理学における命題の計算手法について (Sur le calcul象徴的な論理の命題)]。 Matematicheskii Sbornik (ロシア語とフランス語)。 34 (1)。モスクワ、ロシア : 9–28.Mi msb7433 。 2017年10月12日時点のオリジナルよりアーカイブ 。 2017年10月12日 閲覧。 ^ シュプルン [Супрун]、ヴァレリー P. [Валерий Павлович] (1987)。 「タブリチヌイ法多項式ノゴ・ラズロジェニヤ・ブレヴィフ・ファンクツィー」 Табличный метод полиномиального разложения булевых функций [ブール関数の多項式分解の表形式法]. キベルネティカ [Кибернетика] (サイバネティクス) (ロシア語) (1): 116– 117. ^ スープラン [Супрун]、ヴァレリー P. [Валерий Павлович] (2017). 「オスノヴィ・テオリイ・ブレヴィフ・ファンクツィー」 Основы теории булевых функций [ブール関数理論の基礎]。 М.: レナンド [Ленанд] / URSS (ロシア語): 208. ^ “Möbius inversion”. Encyclopedia of Mathematics . 2021年2月17日 [2011年2月7日]. オリジナルより2020年7月16日時点のアーカイブ。 2021年3月27日 閲覧 。 ^ ベル、エリック・テンプル (1927). 「論理の算術」. アメリカ数学会誌 . 29 (3): 597– 611. doi : 10.2307/1989098 . JSTOR 1989098. ^ ストーン、マーシャル (1936). 「ブール代数の表現理論」. アメリカ数学会誌 . 40 (1): 37–111 . doi :10.2307/1989664. ISSN 0002-9947. JSTOR 1989664.
さらに読む ギンディキン [Гиндикин]、ザーメン グリゴレヴィッチ [Семен Г.] (1972)。 代数論理 алгебра логики в задачах [ 代数論理 ] (ロシア語) (第 1 版)。モスクワ、ロシア: Наука [ナウカ] 。 ISBN 0-387-96179-8 。 （288ページ）（注：翻訳： Springer-Verlag 、1985年[1]） Perkowski, Marek A.; Grygiel, Stanislaw (1995-11-20). 「6. 分解研究の歴史的概観」. 関数分解に関する文献調査. バージョンIV. 関数分解グループ, 電気工学科, ポートランド大学, オレゴン州ポートランド, 米国. pp. 21– 22. CiteSeerX 10.1.1.64.1129 . （188ページ）
![{\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\oプラスg(111)ABC.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b499a2671d54e34f1c9c94fee059e5dbbe5719e)
