補題：ブール関数について

ブール代数

（補題：ブール関数について - Plus Le Toolから移動しました。）


初期seedから日時を求める無謀な挑戦 - Plus Le Blogのための補題。
使う記号の定義は補題：数式中で使う記号の定義 - Plus Le Blog参照。

【追記】
計算ミスを直したら、重要になるはずだったリード・マラー標準形がいらない子になった。
その結果、積和標準形とリード・マラー標準形との関係に記事の大部分を割いていたこの記事はほぼ無価値になったため、この記事は書き途中ですがお蔵入りになりました。


ブール関数をコンピュータで扱う際にめんどうになるのが、等価な最小積和形が複数存在しうるということだ。
例えば、次のブール関数（＊１）は（＊２）のように２通りの最小積和形で表される。

（＊１）
\[
f\left(x,y,z\right)
=\bar{x}\bar{y}\bar{z}\,\cup\,\bar{x}\bar{y}z\,\cup\,\bar{x}yz\,\cup\,xyz\,\cup\,xy\bar{z}
\]

x＼yz 00 01 11 10
0 1 1 1
1 1 1

（＊２）最小積和形
\begin{eqnarray*}
f\left(x,y,z\right)
&=&\bar{x}\bar{y}\,\cup\,xy\,\cup\,\bar{x}z\\
&=&\bar{x}\bar{y}\,\cup\,xy\,\cup\,yz
\end{eqnarray*}

コンピュータで扱うなら等価な式は一意に表せる方が都合がいいので、最小積和形はコンピュータで扱うのに向かない。
ではどうするか。


ブール関数を一意に表す方法はいくつかあるが、そのうちの2つを挙げる。例として3変数の場合を見てみる。
1つ目の方法は、次のようにカルノー図の各マスに8個のbool型係数 \(a_{0},a_{1},\dots,a_{7}\) を割り当て、それをそのまま式にする方法である。

（＊３）
\[
\begin{array}{rclclclcl}
f\left(x,y,z\right)
&=&a_{7}xyz&\cup&a_{6}xy\bar{z}&\cup&a_{5}x\bar{y}z&\cup&a_{4}x\bar{y}\bar{z}\\
&\cup&a_{3}\bar{x}yz&\cup&a_{2}\bar{x}y\bar{z}&\cup&a_{1}\bar{x}\bar{y}z&\cup&a_{0}\bar{x}\bar{y}\bar{z}
\end{array}
\]

x＼yz 00 01 11 10
0 \(a_{0}\) \(a_{1}\) \(a_{3}\) \(a_{2}\)
1 \(a_{4}\) \(a_{5}\) \(a_{7}\) \(a_{6}\)

これが（3変数の）任意のブール関数を一意に表しているのは明らかだろう。
なお、係数の添字の順番は後に重要になるので、この順でなければならない。
\(x\bar{y}\bar{z}\) の項と \(\bar{x}yz\) の項の順序が逆なのではと思うかもしれないが、これで正しい。
（＊４）のように添字を二進表記にすれば分かりやすいだろうか。\(x\) か \(\bar{x}\) のどちらがその項に含まれるかを、添字の最上位bitに対応させているのだ（ \(y,z\) も同様）。

（＊４）
\[
\begin{array}{rclclclcl}
f\left(x,y,z\right)
&=&a_{111}xyz&\cup&a_{110}xy\bar{z}&\cup&a_{101}x\bar{y}z&\cup&a_{100}x\bar{y}\bar{z}\\
&\cup&a_{011}\bar{x}yz&\cup&a_{010}\bar{x}y\bar{z}&\cup&a_{001}\bar{x}\bar{y}z&\cup&a_{000}\bar{x}\bar{y}\bar{z}
\end{array}
\]

x＼yz 00 01 11 10
0 \(a_{000}\) \(a_{001}\) \(a_{011}\) \(a_{010}\)
1 \(a_{100}\) \(a_{101}\) \(a_{111}\) \(a_{110}\)

この形の式を「積和標準形」という。

2つ目の方法は、次のように論理積（AND）と排他的論理和（XOR）のみを使った最簡易形で表す方法である。

（＊５）
\[
\begin{array}{rclclclcl}
f\left(x,y,z\right)
&=&p_{7}xyz&\oplus&p_{6}xy&\oplus&p_{5}xz&\oplus&p_{4}x\\
&\oplus&p_{3}yz&\oplus&p_{2}y&\oplus&p_{1}z&\oplus&p_{0}
\end{array}
\]

これも係数の添字の順番が後に重要になる。
こちらは添字を二進表記にすると、その項に \(x\) が含まれるか否かを、添字の最上位bitに対応させている（ \(y,z\) も同様）。
（簡単にいえば、 \(x^{i}y^{j}z^{k}\) の係数が \(p_{ijk}\) ということ。）

（＊６）
\[
\begin{array}{rclclclcl}
f\left(x,y,z\right)
&=&p_{111}xyz&\oplus&p_{110}xy&\oplus&p_{101}xz&\oplus&p_{100}x\\
&\oplus&p_{011}yz&\oplus&p_{010}y&\oplus&p_{001}z&\oplus&p_{000}
\end{array}
\]

この形の式を「リード・マラー標準形」という。

リード・マラー標準形も積和標準形と同じく、任意のブール関数を一意に表すことができる。
以下、積和標準形を式変形することでそれを確認してみる。
（積和標準形は任意のブール関数を一意に表せるので、リード・マラー標準形が積和標準形と一対一対応していれば、リード・マラー標準形も任意のブール関数を一意に表せることになる。）

その前に、公式を３つほど導いておく。
リード・マラー標準形ではAND（論理積），XOR（排他的論理和）のみを使用し、OR（論理和），NOT（論理否定）は使用しない。
そのため一般のブール関数をリード・マラー標準形に変形するには、OR，NOTをAND，XORだけで表す必要がある。
具体的には次の２式を使う。

（＊Ａ）論理和のリード・マラー標準形
\[
x\,\cup\,y=x\,\oplus\,y\,\oplus\,xy
\]

（＊Ｂ）論理否定のリード・マラー標準形
\[
\bar{x}=x\,\oplus\,1
\]

また、積和標準形ではAND，OR，NOTのみを使用し、XORは使用しない。
そのため一般のブール関数を積和標準形に変形するには、XORをAND，OR，NOTだけで表す必要がある。
具体的には次の式を使う。

（＊Ｃ）排他的論理和の積和標準形
\[
x\,\oplus\,y=\bar{x}y\,\cup\,x\bar{y}
\]

【簡易証明】
（＊Ａ）

\(x\) \(y\) \(xy\) \(x\,\oplus\,y\,\oplus\,xy\) \(x\,\cup\,y\)
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 1

（＊Ｂ）

\(x\) \(x\,\oplus\,1\) \(\bar{x}\)
0 1 1
1 0 0

（＊Ｃ）

\(x\) \(y\) \(\bar{x}\) \(\bar{y}\) \(\bar{x}y\) \(x\bar{y}\) \(\bar{x}y\,\cup\,x\bar{y}\) \(x\,\oplus\,y\)
0 0 1 1 0 0 0 0
0 1 1 0 1 0 1 1
1 0 0 1 0 1 1 1
1 1 0 0 0 0 0 0


では実際に、積和標準形（＊３）を変形してみる。
計算過程はめんどうなだけで難しくないので省略するが、式（＊Ａ）（＊Ｂ）を使って変形していくと最終的に（＊７）のようになる。

（＊３）再掲
\[
\begin{array}{rclclclcl}
f\left(x,y,z\right)
&=&a_{7}xyz&\cup&a_{6}xy\bar{z}&\cup&a_{5}x\bar{y}z&\cup&a_{4}x\bar{y}\bar{z}\\
&\cup&a_{3}\bar{x}yz&\cup&a_{2}\bar{x}y\bar{z}&\cup&a_{1}\bar{x}\bar{y}z&\cup&a_{0}\bar{x}\bar{y}\bar{z}
\end{array}
\]

（＊７）
\begin{eqnarray*}
f\left(x,y,z\right)
&=&\left(a_{7}\,\oplus\,a_{6}\,\oplus\,a_{5}\,\oplus\,a_{4}\,\oplus\,a_{3}\,\oplus\,a_{2}\,\oplus\,a_{1}\,\oplus\,a_{0}\right)xyz\\
&\oplus&\left(a_{6}\,\oplus\,a_{4}\,\oplus\,a_{2}\,\oplus\,a_{0}\right)xy\\
&\oplus&\left(a_{5}\,\oplus\,a_{4}\,\oplus\,a_{1}\,\oplus\,a_{0}\right)xz\\
&\oplus&\left(a_{4}\,\oplus\,a_{0}\right)x\\
&\oplus&\left(a_{3}\,\oplus\,a_{2}\,\oplus\,a_{1}\,\oplus\,a_{0}\right)yz\\
&\oplus&\left(a_{2}\,\oplus\,a_{0}\right)y\\
&\oplus&\left(a_{1}\,\oplus\,a_{0}\right)z\\
&\oplus&a_{0}
\end{eqnarray*}

よって \(p_{0},p_{1},\dots,p_{7}\) を次のように定義することで、リード・マラー標準形（＊５）を得る。

（＊８）
\[
\begin{array}{lclclclclclclclcl}
p_{7}
&=&a_{7}&\oplus&a_{6}&\oplus&a_{5}&\oplus&a_{4}&\oplus&a_{3}&\oplus&a_{2}&\oplus&a_{1}&\oplus&a_{0}\\
p_{6}&=&&&a_{6}&&&\oplus&a_{4}&&&\oplus&a_{2}&&&\oplus&a_{0}\\
p_{5}&=&&&&&a_{5}&\oplus&a_{4}&&&&&\oplus&a_{1}&\oplus&a_{0}\\
p_{4}&=&&&&&&&a_{4}&&&&&&&\oplus&a_{0}\\
p_{3}&=&&&&&&&&&a_{3}&\oplus&a_{2}&\oplus&a_{1}&\oplus&a_{0}\\
p_{2}&=&&&&&&&&&&&a_{2}&&&\oplus&a_{0}\\
p_{1}&=&&&&&&&&&&&&&a_{1}&\oplus&a_{0}\\
p_{0}&=&&&&&&&&&&&&&&&a_{0}
\end{array}
\]

逆に、リード・マラー標準系（＊５）も同様に変形してみる。
こちらもめんどうなだけで難しくないので計算過程を省略するが、式（＊Ｃ）を使って変形すると最終的に（＊９）のようになる。

（＊５）再掲
\[
\begin{array}{rclclclcl}
f\left(x,y,z\right)
&=&p_{7}xyz&\oplus&p_{6}xy&\oplus&p_{5}xz&\oplus&p_{4}x\\
&\oplus&p_{3}yz&\oplus&p_{2}y&\oplus&p_{1}z&\oplus&p_{0}
\end{array}
\]

（＊９）
\begin{eqnarray*}
f\left(x,y,z\right)
&=&\left(p_{7}\,\oplus\,p_{6}\,\oplus\,p_{5}\,\oplus\,p_{4}\,\oplus\,p_{3}\,\oplus\,p_{2}\,\oplus\,p_{1}\,\oplus\,p_{0}\right)xyz\\
&\cup&\left(p_{6}\,\oplus\,p_{4}\,\oplus\,p_{2}\,\oplus\,p_{0}\right)xy\bar{z}\\
&\cup&\left(p_{5}\,\oplus\,p_{4}\,\oplus\,p_{1}\,\oplus\,p_{0}\right)x\bar{y}z\\
&\cup&\left(p_{4}\,\oplus\,p_{0}\right)x\bar{y}\bar{z}\\
&\cup&\left(p_{3}\,\oplus\,p_{2}\,\oplus\,p_{1}\,\oplus\,p_{0}\right)\bar{x}yz\\
&\cup&\left(p_{2}\,\oplus\,p_{0}\right)\bar{x}y\bar{z}\\
&\cup&\left(p_{1}\,\oplus\,p_{0}\right)\bar{x}\bar{y}z\\
&\cup&p_{0}\bar{x}\bar{y}\bar{z}
\end{eqnarray*}

よって \(a_{0},a_{1},\dots,a_{7}\) を次のように定義することで、積和標準形（＊３）を得る。

（＊10）
\[
\begin{array}{lclclclclclclclcl}
a_{7}
&=&p_{7}&\oplus&p_{6}&\oplus&p_{5}&\oplus&p_{4}&\oplus&p_{3}&\oplus&p_{2}&\oplus&p_{1}&\oplus&p_{0}\\
a_{6}&=&&&p_{6}&&&\oplus&p_{4}&&&\oplus&p_{2}&&&\oplus&p_{0}\\
a_{5}&=&&&&&p_{5}&\oplus&p_{4}&&&&&\oplus&p_{1}&\oplus&p_{0}\\
a_{4}&=&&&&&&&p_{4}&&&&&&&\oplus&p_{0}\\
a_{3}&=&&&&&&&&&p_{3}&\oplus&p_{2}&\oplus&p_{1}&\oplus&p_{0}\\
a_{2}&=&&&&&&&&&&&p_{2}&&&\oplus&p_{0}\\
a_{1}&=&&&&&&&&&&&&&p_{1}&\oplus&p_{0}\\
a_{0}&=&&&&&&&&&&&&&&&p_{0}
\end{array}
\]

なお、（＊10）は（＊８）を \(a_{0},a_{1},\dots,a_{7}\) について解いた式と同じである（当然だが）。

以上より、（3変数の）積和標準形にはそれと一対一に対応するリード・マラー標準形が存在するので、リード・マラー標準形は任意の（3変数の）ブール関数を一意に表すことができるといえる。
例として3変数で計算したが、このことは3変数に限らず任意個の変数の場合にも成り立つ（証明はできないので省略する）。


さて、ブール関数を一意に表す2通りの方法を見てみたが、これらには論理演算に対してそれぞれ得意・不得意がある。
積和標準形はAND（論理積）とOR（論理和）が得意だが、XOR（排他的論理和）とNOT（論理否定）が苦手。AND（論理積），OR（論理和），XOR（排他的論理和），NOT（論理否定）はどれも得意。
一方、リード・マラー標準形はXORとNOTが得意だが、ANDとORは苦手。
どういうことか見てみよう。

2つのbool型変数 \(\alpha,\beta\) があり、積和標準形とリード・マラー標準形で次のように表されるとする。
がある。

（＊11）
\begin{eqnarray*}
\alpha
&=&a_{7}xyz\,\cup\,a_{6}xy\bar{z}\,\cup\,a_{5}x\bar{y}z\,\cup\,a_{4}x\bar{y}\bar{z}\,\cup\,a_{3}\bar{x}yz\,\cup\,a_{2}\bar{x}y\bar{z}\,\cup\,a_{1}\bar{x}\bar{y}z\,\cup\,a_{0}\bar{x}\bar{y}\bar{z}\\
&=&p_{7}xyz\,\oplus\,p_{6}xy\,\oplus\,p_{5}xz\,\oplus\,p_{4}x\,\oplus\,p_{3}yz\,\oplus\,p_{2}y\,\oplus\,p_{1}z\,\oplus\,p_{0}
\end{eqnarray*}

\begin{eqnarray*}
\beta
&=&b_{7}xyz\,\cup\,b_{6}xy\bar{z}\,\cup\,b_{5}x\bar{y}z\,\cup\,b_{4}x\bar{y}\bar{z}\,\cup\,b_{3}\bar{x}yz\,\cup\,b_{2}\bar{x}y\bar{z}\,\cup\,b_{1}\bar{x}\bar{y}z\,\cup\,b_{0}\bar{x}\bar{y}\bar{z}\\
&=&q_{7}xyz\,\oplus\,q_{6}xy\,\oplus\,q_{5}xz\,\oplus\,q_{4}x\,\oplus\,q_{3}yz\,\oplus\,q_{2}y\,\oplus\,q_{1}z\,\oplus\,q_{0}
\end{eqnarray*}

この \(\alpha,\beta\) について、AND，OR，XOR，NOTを積和標準形とリード・マラー標準形のそれぞれで表すと以下のようになる（計算過程は省略）。

（＊12）論理積（AND）
（積和標準形）
\begin{eqnarray*}
\alpha\beta
&=&a_{7}b_{7}xyz\,\cup\,a_{6}b_{6}xy\bar{z}\,\cup\,a_{5}b_{5}x\bar{y}z\,\cup\,a_{4}b_{4}x\bar{y}\bar{z}\\
&\cup&a_{3}b_{3}\bar{x}yz\,\cup\,a_{2}b_{2}\bar{x}y\bar{z}\,\cup\,a_{1}b_{1}\bar{x}\bar{y}z\,\cup\,a_{0}b_{0}\bar{x}\bar{y}\bar{z}
\end{eqnarray*}

（リード・マラー標準形）
\begin{eqnarray*}
\alpha\beta
&=&\left(\begin{array}{l}
\left(p_{7}\,\oplus\,p_{6}\,\oplus\,p_{5}\,\oplus\,p_{4}\,\oplus\,p_{3}\,\oplus\,p_{2}\,\oplus\,p_{1}\,\oplus\,p_{0}\right)\left(q_{7}\,\oplus\,q_{6}\,\oplus\,q_{5}\,\oplus\,q_{4}\,\oplus\,q_{3}\,\oplus\,q_{2}\,\oplus\,q_{1}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{6}\,\oplus\,p_{4}\,\oplus\,p_{2}\,\oplus\,p_{0}\right)\left(q_{6}\,\oplus\,q_{4}\,\oplus\,q_{2}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{5}\,\oplus\,p_{4}\,\oplus\,p_{1}\,\oplus\,p_{0}\right)\left(q_{5}\,\oplus\,q_{4}\,\oplus\,q_{1}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{3}\,\oplus\,p_{2}\,\oplus\,p_{1}\,\oplus\,p_{0}\right)\left(q_{3}\,\oplus\,q_{2}\,\oplus\,q_{1}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{4}\,\oplus\,p_{0}\right)\left(q_{4}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{2}\,\oplus\,p_{0}\right)\left(q_{2}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{1}\,\oplus\,p_{0}\right)\left(q_{1}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,p_{0}q_{0}
\end{array}\right)xyz\\
&\oplus&\left(\begin{array}{l}
\left(p_{6}\,\oplus\,p_{4}\,\oplus\,p_{2}\,\oplus\,p_{0}\right)\left(q_{6}\,\oplus\,q_{4}\,\oplus\,q_{2}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{4}\,\oplus\,p_{0}\right)\left(q_{4}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{2}\,\oplus\,p_{0}\right)\left(q_{2}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,p_{0}q_{0}
\end{array}\right)xy\\
&\oplus&\left(\begin{array}{l}
\left(p_{5}\,\oplus\,p_{4}\,\oplus\,p_{1}\,\oplus\,p_{0}\right)\left(q_{5}\,\oplus\,q_{4}\,\oplus\,q_{1}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{4}\,\oplus\,p_{0}\right)\left(q_{4}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{1}\,\oplus\,p_{0}\right)\left(q_{1}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,p_{0}q_{0}
\end{array}\right)xz\\
&\oplus&\left(\left(p_{4}\,\oplus\,p_{0}\right)\left(q_{4}\,\oplus\,q_{0}\right)\,\oplus\,p_{0}q_{0}\right)x\\
&\oplus&\left(\begin{array}{l}
\left(p_{3}\,\oplus\,p_{2}\,\oplus\,p_{1}\,\oplus\,p_{0}\right)\left(q_{3}\,\oplus\,q_{2}\,\oplus\,q_{1}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{2}\,\oplus\,p_{0}\right)\left(q_{2}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,\left(p_{1}\,\oplus\,p_{0}\right)\left(q_{1}\,\oplus\,q_{0}\right)\\
\;\;\,\oplus\,p_{0}q_{0}
\end{array}\right)yz\\
&\oplus&\left(\left(p_{2}\,\oplus\,p_{0}\right)\left(q_{2}\,\oplus\,q_{0}\right)\,\oplus\,p_{0}q_{0}\right)y\\
&\oplus&\left(\left(p_{1}\,\oplus\,p_{0}\right)\left(q_{1}\,\oplus\,q_{0}\right)\,\oplus\,p_{0}q_{0}\right)z\\
&\oplus&p_{0}q_{0}
\end{eqnarray*}

><

（＊13）論理和（OR）
（積和標準形）
\begin{eqnarray*}
\alpha\,\cup\,\beta
&=&\left(a_{7}\,\cup\,b_{7}\right)xyz\,\cup\,\left(a_{6}\,\cup\,b_{6}\right)xy\bar{z}\,\cup\,\left(a_{5}\,\cup\,b_{5}\right)x\bar{y}z\,\cup\,\left(a_{4}\,\cup\,b_{4}\right)x\bar{y}\bar{z}\\
&\cup&\left(a_{3}\,\cup\,b_{3}\right)\bar{x}yz\,\cup\,\left(a_{2}\,\cup\,b_{2}\right)\bar{x}y\bar{z}\,\cup\,\left(a_{1}\,\cup\,b_{1}\right)\bar{x}\bar{y}z\,\cup\,\left(a_{0}\,\cup\,b_{0}\right)\bar{x}\bar{y}\bar{z}
\end{eqnarray*}

（リード・マラー標準形）
\begin{eqnarray*}
\alpha\,\cup\,\beta
&=&\left(\left(p_{7}\,\oplus\,p_{6}\,\oplus\,p_{5}\,\oplus\,p_{4}\,\oplus\,p_{3}\,\oplus\,p_{2}\,\oplus\,p_{1}\,\oplus\,p_{0}\,\oplus\,1\right)\left(q_{7}\,\oplus\,q_{6}\,\oplus\,q_{5}\,\oplus\,q_{4}\,\oplus\,q_{3}\,\oplus\,q_{2}\,\oplus\,q_{1}\,\oplus\,q_{0}\,\oplus\,1\right)\,\oplus\,1\right)xyz\\
&\cup&\left(\left(p_{6}\,\oplus\,p_{4}\,\oplus\,p_{2}\,\oplus\,p_{0}\,\oplus\,1\right)\left(q_{6}\,\oplus\,q_{4}\,\oplus\,q_{2}\,\oplus\,q_{0}\,\oplus\,1\right)\,\oplus\,1\right)xy\\
&\cup&\left(\left(p_{5}\,\oplus\,p_{4}\,\oplus\,p_{1}\,\oplus\,p_{0}\,\oplus\,1\right)\left(q_{5}\,\oplus\,q_{4}\,\oplus\,q_{1}\,\oplus\,q_{0}\,\oplus\,1\right)\,\oplus\,1\right)xz\\
&\cup&\left(\left(p_{4}\,\oplus\,p_{0}\,\oplus\,1\right)\left(q_{4}\,\oplus\,q_{0}\,\oplus\,1\right)\,\oplus\,1\right)x\\
&\cup&\left(\left(p_{3}\,\oplus\,p_{2}\,\oplus\,p_{1}\,\oplus\,p_{0}\,\oplus\,1\right)\left(q_{3}\,\oplus\,q_{2}\,\oplus\,q_{1}\,\oplus\,q_{0}\,\oplus\,1\right)\,\oplus\,1\right)yz\\
&\cup&\left(\left(p_{2}\,\oplus\,p_{0}\,\oplus\,1\right)\left(q_{2}\,\oplus\,q_{0}\,\oplus\,1\right)\,\oplus\,1\right)y\\
&\cup&\left(\left(p_{1}\,\oplus\,p_{0}\,\oplus\,1\right)\left(q_{1}\,\oplus\,q_{0}\,\oplus\,1\right)\,\oplus\,1\right)z\\
&\cup&\left(\left(p_{0}\,\oplus\,1\right)\left(q_{0}\,\oplus\,1\right)\,\oplus\,1\right)
\end{eqnarray*}

（＊14）排他的論理和（XOR）
（積和標準形）
\begin{eqnarray*}
\alpha\,\oplus\,\beta
&=&\left(a_{7}\,\oplus\,b_{7}\right)xyz\,\cup\,\left(a_{6}\,\oplus\,b_{6}\right)xy\bar{z}\,\cup\,\left(a_{5}\,\oplus\,b_{5}\right)x\bar{y}z\,\cup\,\left(a_{4}\,\oplus\,b_{4}\right)x\bar{y}\bar{z}\\
&\cup&\left(a_{3}\,\oplus\,b_{3}\right)\bar{x}yz\,\cup\,\left(a_{2}\,\oplus\,b_{2}\right)\bar{x}y\bar{z}\,\cup\,\left(a_{1}\,\oplus\,b_{1}\right)\bar{x}\bar{y}z\,\cup\,\left(a_{0}\,\oplus\,b_{0}\right)\bar{x}\bar{y}\bar{z}
\end{eqnarray*}

（リード・マラー標準形）
\begin{eqnarray*}
\alpha\,\oplus\,\beta
&=&\left(p_{7}\,\oplus\,q_{7}\right)xyz\,\oplus\,\left(p_{6}\,\oplus\,q_{6}\right)xy\,\oplus\,\left(p_{5}\,\oplus\,q_{5}\right)xz\,\oplus\,\left(p_{4}\,\oplus\,q_{4}\right)x\\
&\oplus&\left(p_{3}\,\oplus\,q_{3}\right)yz\,\oplus\,\left(p_{2}\,\oplus\,q_{2}\right)y\,\oplus\,\left(p_{1}\,\oplus\,q_{1}\right)z\,\oplus\,\left(p_{0}\,\oplus\,q_{0}\right)
\end{eqnarray*}

（＊15）論理否定（NOT）
（積和標準形）
\[
\bar{\alpha}=\bar{a_{7}}xyz\,\cup\,\bar{a_{6}}xy\bar{z}\,\cup\,\bar{a_{5}}x\bar{y}z\,\cup\,\bar{a_{4}}x\bar{y}\bar{z}\,\cup\,\bar{a_{3}}\bar{x}yz\,\cup\,\bar{a_{2}}\bar{x}y\bar{z}\,\cup\,\bar{a_{1}}\bar{x}\bar{y}z\,\cup\,\bar{a_{0}}\bar{x}\bar{y}\bar{z}
\]

（リード・マラー標準形）
\[
\bar{\alpha}=p_{7}xyz\,\oplus\,p_{6}xy\,\oplus\,p_{5}xz\,\oplus\,p_{4}x\,\oplus\,p_{3}yz\,\oplus\,p_{2}y\,\oplus\,p_{1}z\,\oplus\,\left(p_{0}\,\oplus\,1\right)
\]

式（＊12）～（＊15）を見れば明らかなように、リード・マラー標準形のAND，ORはめんどくさく、それ以外は簡単に計算できるが分かる。
リード・マラー標準形で書かれた式のANDやORを計算する必要がある場合は、積和標準形に書きなおしてから計算するほうが簡単。
そこで、積和標準形とリード・マラー標準形の式の変換についてもう少し詳しく見てみようと思う。

積和標準形（＊３）からリード・マラー標準形（＊５）への変形は（＊８）を使い、逆にリード・マラー標準形（＊５）から積和標準形（＊３）への変形は（＊10）を使うのだった。

（＊３）再掲
\[
\begin{array}{rclclclcl}
f\left(x,y,z\right)
&=&a_{7}xyz&\cup&a_{6}xy\bar{z}&\cup&a_{5}x\bar{y}z&\cup&a_{4}x\bar{y}\bar{z}\\
&\cup&a_{3}\bar{x}yz&\cup&a_{2}\bar{x}y\bar{z}&\cup&a_{1}\bar{x}\bar{y}z&\cup&a_{0}\bar{x}\bar{y}\bar{z}
\end{array}
\]

><

（＊５）再掲
\[
\begin{array}{rclclclcl}
f\left(x,y,z\right)
&=&p_{7}xyz&\oplus&p_{6}xy&\oplus&p_{5}xz&\oplus&p_{4}x\\
&\oplus&p_{3}yz&\oplus&p_{2}y&\oplus&p_{1}z&\oplus&p_{0}
\end{array}
\]

><

（＊８）再掲
\[
\begin{array}{lclclclclclclclcl}
p_{7}
&=&a_{7}&\oplus&a_{6}&\oplus&a_{5}&\oplus&a_{4}&\oplus&a_{3}&\oplus&a_{2}&\oplus&a_{1}&\oplus&a_{0}\\
p_{6}&=&&&a_{6}&&&\oplus&a_{4}&&&\oplus&a_{2}&&&\oplus&a_{0}\\
p_{5}&=&&&&&a_{5}&\oplus&a_{4}&&&&&\oplus&a_{1}&\oplus&a_{0}\\
p_{4}&=&&&&&&&a_{4}&&&&&&&\oplus&a_{0}\\
p_{3}&=&&&&&&&&&a_{3}&\oplus&a_{2}&\oplus&a_{1}&\oplus&a_{0}\\
p_{2}&=&&&&&&&&&&&a_{2}&&&\oplus&a_{0}\\
p_{1}&=&&&&&&&&&&&&&a_{1}&\oplus&a_{0}\\
p_{0}&=&&&&&&&&&&&&&&&a_{0}
\end{array}
\]

（＊10）再掲
\[
\begin{array}{lclclclclclclclcl}
a_{7}
&=&p_{7}&\oplus&p_{6}&\oplus&p_{5}&\oplus&p_{4}&\oplus&p_{3}&\oplus&p_{2}&\oplus&p_{1}&\oplus&p_{0}\\
a_{6}&=&&&p_{6}&&&\oplus&p_{4}&&&\oplus&p_{2}&&&\oplus&p_{0}\\
a_{5}&=&&&&&p_{5}&\oplus&p_{4}&&&&&\oplus&p_{1}&\oplus&p_{0}\\
a_{4}&=&&&&&&&p_{4}&&&&&&&\oplus&p_{0}\\
a_{3}&=&&&&&&&&&p_{3}&\oplus&p_{2}&\oplus&p_{1}&\oplus&p_{0}\\
a_{2}&=&&&&&&&&&&&p_{2}&&&\oplus&p_{0}\\
a_{1}&=&&&&&&&&&&&&&p_{1}&\oplus&p_{0}\\
a_{0}&=&&&&&&&&&&&&&&&p_{0}
\end{array}
\]

ところで、式（＊８）の変数の順番を少し並べ替えて行列で表すと、次のようになる。

（＊16）
\[
\begin{bmatrix}
p_{0}\\p_{1}\\p_{2}\\p_{3}\\p_{4}\\p_{5}\\p_{6}\\p_{7}
\end{bmatrix}
\equiv
\begin{bmatrix}
1&&&&&&&\\
1&1&&&&&&\\
1&&1&&&&&\\
1&1&1&1&&&&\\
1&&&&1&&&\\
1&1&&&1&1&&\\
1&&1&&1&&1&\\
1&1&1&1&1&1&1&1
\end{bmatrix}
\begin{bmatrix}
a_{0}\\a_{1}\\a_{2}\\a_{3}\\a_{4}\\a_{5}\\a_{6}\\a_{7}
\end{bmatrix}
\pmod{2}
\]

（∵算術和の（mod 2）は排他的論理和に等しい。）
式（＊10）も同様に行列で表すと、次のようになる。

（＊17）
\[
\begin{bmatrix}
a_{0}\\a_{1}\\a_{2}\\a_{3}\\a_{4}\\a_{5}\\a_{6}\\a_{7}
\end{bmatrix}
\equiv
\begin{bmatrix}
1&&&&&&&\\
1&1&&&&&&\\
1&&1&&&&&\\
1&1&1&1&&&&\\
1&&&&1&&&\\
1&1&&&1&1&&\\
1&&1&&1&&1&\\
1&1&1&1&1&1&1&1
\end{bmatrix}
\begin{bmatrix}
p_{0}\\p_{1}\\p_{2}\\p_{3}\\p_{4}\\p_{5}\\p_{6}\\p_{7}
\end{bmatrix}
\pmod{2}
\]

（＊16）（＊17）を見比べると、係数行列が同一のものであることが分かる。
これはいったいなんなのか？　そこから調べてよう。
以下、この係数行列を \(M\) と書くことにする。また、2つの列ベクトル \(\vec{a},\vec{p}\) を次のように定義する。

（＊18）
\[
M\overset{def}{=}
\begin{bmatrix}
1&&&&&&&\\
1&1&&&&&&\\
1&&1&&&&&\\
1&1&1&1&&&&\\
1&&&&1&&&\\
1&1&&&1&1&&\\
1&&1&&1&&1&\\
1&1&1&1&1&1&1&1
\end{bmatrix}
\]
\begin{align*}
\vec{a}\overset{def}{=}
\begin{bmatrix}
a_{0}\\a_{1}\\a_{2}\\a_{3}\\a_{4}\\a_{5}\\a_{6}\\a_{7}
\end{bmatrix}
\,,
&&
\vec{p}\overset{def}{=}
\begin{bmatrix}
p_{0}\\p_{1}\\p_{2}\\p_{3}\\p_{4}\\p_{5}\\p_{6}\\p_{7}
\end{bmatrix}
\end{align*}

まず、（＊10）の下に書いたように、（＊８）を \(a_{0},a_{1},\dots,a_{7}\) について解くと（＊10）に一致する。
なので式（＊16）を \(\vec{a}\) について解けば式（＊17）に一致するはず。
そのためには（＊17）の係数行列 \(M\) が（＊16）の係数行列 \(M\) の逆行列 \(M^{-1}\) でなければならない。

\(M=M^{-1}\)

実際に計算してみると \(M^{2}\) は確かに単位行列になり、上記のことが成り立っていると分かる。


次に、

TODO:書き途中。たまたま閃いたこの式をどう導いたものか。
TODO:nCrはどこから出てきた？
TODO:3変数の場合に限らず一般の場合にまで拡張できるが、それの証明は？

（＊19）
\begin{eqnarray*}
&&\begin{bmatrix}
{}_{0}C_{0}&&&&&&&\\
{}_{1}C_{0}&{}_{1}C_{1}&&&&&&\\
{}_{2}C_{0}&{}_{2}C_{1}&{}_{2}C_{2}&&&&&\\
{}_{3}C_{0}&{}_{3}C_{1}&{}_{3}C_{2}&{}_{3}C_{3}&&&&\\
{}_{4}C_{0}&{}_{4}C_{1}&{}_{4}C_{2}&{}_{4}C_{3}&{}_{4}C_{4}&&&\\
{}_{5}C_{0}&{}_{5}C_{1}&{}_{5}C_{2}&{}_{5}C_{3}&{}_{5}C_{4}&{}_{5}C_{5}&&\\
{}_{6}C_{0}&{}_{6}C_{1}&{}_{6}C_{2}&{}_{6}C_{3}&{}_{6}C_{4}&{}_{6}C_{5}&{}_{6}C_{6}&\\
{}_{7}C_{0}&{}_{7}C_{1}&{}_{7}C_{2}&{}_{7}C_{3}&{}_{7}C_{4}&{}_{7}C_{5}&{}_{7}C_{6}&{}_{7}C_{7}
\end{bmatrix}\\
&=&\begin{bmatrix}
1&&&&&&&\\
1&1&&&&&&\\
1&2&1&&&&&\\
1&3&3&1&&&&\\
1&4&6&4&1&&&\\
1&5&10&10&5&1&&\\
1&6&15&20&15&6&1&\\
1&7&21&35&35&21&7&1
\end{bmatrix}\\
&\equiv&\begin{bmatrix}
1&&&&&&&\\
1&1&&&&&&\\
1&&1&&&&&\\
1&1&1&1&&&&\\
1&&&&1&&&\\
1&1&&&1&1&&\\
1&&1&&1&&1&\\
1&1&1&1&1&1&1&1
\end{bmatrix}
\pmod{2}\\
&=&M
\end{eqnarray*}

ここで、次のように \({}_{n}C_{r}\) の定義域を整数全体に拡張する。

（＊20）
\[
{}_{n}C_{r}=
\begin{cases}
0&\left(\,r\lt 0\,\text{のとき}\right)\\
\displaystyle\frac{n!}{r!\left(n-r\right)!}&\left(\,0\le r\le n\,\text{のとき}\right)\\
0&\left(\,r\gt n\,\text{のとき}\right)
\end{cases}
\]

これを使うと、係数行列 \(M\) は次のように書き表せる。

（＊21）
\begin{eqnarray*}
M
&=&\left[\,\left\{{}_{i}C_{j}\bmod{2}\right\}\,\right]\\
&\equiv&
\begin{bmatrix}
{}_{0}C_{0}&{}_{0}C_{1}&{}_{0}C_{2}&{}_{0}C_{3}&{}_{0}C_{4}&{}_{0}C_{5}&{}_{0}C_{6}&{}_{0}C_{7}\\
{}_{1}C_{0}&{}_{1}C_{1}&{}_{1}C_{2}&{}_{1}C_{3}&{}_{1}C_{4}&{}_{1}C_{5}&{}_{1}C_{6}&{}_{1}C_{7}\\
{}_{2}C_{0}&{}_{2}C_{1}&{}_{2}C_{2}&{}_{2}C_{3}&{}_{2}C_{4}&{}_{2}C_{5}&{}_{2}C_{6}&{}_{2}C_{7}\\
{}_{3}C_{0}&{}_{3}C_{1}&{}_{3}C_{2}&{}_{3}C_{3}&{}_{3}C_{4}&{}_{3}C_{5}&{}_{3}C_{6}&{}_{3}C_{7}\\
{}_{4}C_{0}&{}_{4}C_{1}&{}_{4}C_{2}&{}_{4}C_{3}&{}_{4}C_{4}&{}_{4}C_{5}&{}_{4}C_{6}&{}_{4}C_{7}\\
{}_{5}C_{0}&{}_{5}C_{1}&{}_{5}C_{2}&{}_{5}C_{3}&{}_{5}C_{4}&{}_{5}C_{5}&{}_{5}C_{6}&{}_{5}C_{7}\\
{}_{6}C_{0}&{}_{6}C_{1}&{}_{6}C_{2}&{}_{6}C_{3}&{}_{6}C_{4}&{}_{6}C_{5}&{}_{6}C_{6}&{}_{6}C_{7}\\
{}_{7}C_{0}&{}_{7}C_{1}&{}_{7}C_{2}&{}_{7}C_{3}&{}_{7}C_{4}&{}_{7}C_{5}&{}_{7}C_{6}&{}_{7}C_{7}
\end{bmatrix}
\pmod{2}
\end{eqnarray*}

よって、式（＊16）（＊17）はそれぞれ次のように書き直せる。

（＊22）
\begin{eqnarray*}
\vec{p}
&=&M\vec{a}\\
&=&\left[\,\left\{{}_{i}C_{j}\bmod{2}\right\}\,\right]\vec{a}
\end{eqnarray*}

（＊23）
\begin{eqnarray*}
\vec{a}
&=&M\vec{p}\\
&=&\left[\,\left\{{}_{i}C_{j}\bmod{2}\right\}\,\right]\vec{p}
\end{eqnarray*}

この例では3変数の場合を見てきたが、式（＊22）（＊23）の関係は任意個の変数の場合にも成り立つ[要出典]。
よって、これらを用いて積和標準形とリード・マラー標準形を変換すればいい。
（行列の積と（＊12）～（＊15）とどっちが簡単かなんて知らない。というかnやrが大きくなった時の組み合わせ計算のアルゴリズムってあまり速くなかった気がするけどそんなこと知らない。）


（日記はここで途切れている……どうやら途中保存のようだ。）
（反応がない。ただのお蔵入りのようだ。）


TODO：シャノン展開について書く
ところでオクラ入りのカレーっておいしいよね。