補題：任意のブール方程式の解き方

初期seedから日時を求める無謀な挑戦 - Plus Le Toolのための補題。
使う記号の定義は[id:plusletool:20130427:p2]参照。

論理式（＝ブール関数）の連立方程式の解き方。
ブール代数の方程式に関する資料はなぜかかなり少ないけど、ようやく見つけた。それも２つも。

（★１）

Kyoto University Research Information Repository: ブール方程式によるシーケンス・ペアの拡張 (情報科学と函数解析の接点 : これまでとこれから)

CiNii 論文 - ブール方程式によるシーケンス・ペアの拡張 (情報科学と函数解析の接点--これまでとこれから研究集会報告集)

（※どちらも同じです。）

1つ目は9年前の論文。1変数のブール方程式の解の公式が書かれてた。
残念ながら多変数のブール方程式の解の公式には触れられていなかった。

（★２）

HERMES-IR : Research & Education Resources: 「ブール代数での方程式」

CiNii 論文 - 「ブール代数での方程式」

（※どちらも同じです。）

2つ目は49年前の論文。1変数と多変数のブール方程式の解の公式が書かれてた。
論文（★１）より少し読みにくいのが難点。
コンピュータがあったかなかったか分からんような時代の論文でブール代数を扱ってるのに驚き。

さっそく1つ目の論文（★１）から見てみよう。
最初に関連部分を（記号をこの記事の表記法に修正して）引用しておく。

（＊１）論文（★１）P.5 命題5
$x$ に関するブール方程式 $ax\,\cup\,b\bar{x}=0$ が解をもつための必要十分条件は $ab=0$ である。
また、この条件が満たされるとき、解は $b\le x\le \bar{a}$ である。

（＊２）論文（★１）P.5 命題6
$x$ に関するブール方程式 $ax\,\cup\,b\bar{x}\,\cup\,c=0$ が解をもつための必要十分条件は $ab\,\cup\,c=0$ である。
また、この条件が満たされるとき、解は $b\le x\le \bar{a}$ である。

まず（＊２）についてだが、（＊２）の方程式の左辺は次のように変形できる。

（＊３）
（左辺）
$\begin{eqnarray}\;&=&ax\,\cup\,b\bar{x}\,\cup\,c\\&=&ax\,\cup\,b\bar{x}\,\cup\,c\left(x\cup\bar{x}\right)\\&=&\left(a\cup c\right)x\,\cup\,\left(b\cup c\right)\bar{x}\\&\overset{\mathrm{def}}{=}&a'x\,\cup\,b'\bar{x}\end{eqnarray}$

この形の式には（＊１）を適用できるので、（＊１）についてだけ考えれば充分である。

次に（＊１）について考える。
一般には、方程式は次のように両辺に式がある形になっている。

（＊４）
$F\left(x\right)=G\left(x\right)$

右辺の $G\left(x\right)$ を左辺に移項する（つまり、両辺に $G\left(x\right)$ を $\oplus$ する）ことで、右辺を0にすることができる。

（＊５）
$\begin{eqnarray}F\left(x\right)&=&G\left(x\right)\\\Leftrightarrow\;F\left(x\right)\,\oplus\,G\left(x\right)&=&G\left(x\right)\,\oplus\,G\left(x\right)\\&=&0\end{eqnarray}$

左辺を $f\left(x\right)$ とおけば、 $f\left(x\right)=0$ の形の方程式にすることができる。

（＊６）
$\begin{eqnarray}f\left(x\right)&\overset{\mathrm{def}}{=}&F\left(x\right)\,\oplus\,G\left(x\right)\\&=&0\end{eqnarray}$

ここで、左辺をシャノン展開により積和標準形で表す。

（＊７）
$f\left(x\right)=f\left(1\right)x\,\cup\,f\left(0\right)\bar{x}$

$a\overset{\mathrm{def}}{=}f\left(1\right)$ ， $b\overset{\mathrm{def}}{=}f\left(0\right)$ とおくことで、（＊１）の方程式と同じ式を得る。

（＊８）
$f\left(x\right)=ax\,\cup\,b\bar{x}=0$

よって、（＊１）を書き直すと次のようになる。

（＊１）再掲
$x$ に関するブール方程式 $ax\,\cup\,b\bar{x}=0$ が解をもつための必要十分条件は $ab=0$ である。
また、この条件が満たされるとき、解は $b\le x\le \bar{a}$ である。

（＊９）1変数のブール方程式の解の存在条件と解の公式
$x$ に関するブール方程式 $f\left(x\right)=0$ が解をもつための必要十分条件は $f\left(0\right)f\left(1\right)=0$ である。
また、この条件が満たされるとき、解は $f\left(0\right)\le x\le \bar{f\left(1\right)}$ である。

（＊９）は任意の $f\left(x\right)$ で成り立つ。

次に論文（★２）を見ていくが、ただし前提分野が異なる（？）上に古い論文のため少し読みづらい。
なので、自分なりの解釈を加えて使いやすい式に変形していこうと思う。

とりあえずまずは関連部分をそのまま引用しておく（記号だけこの記事の表記法に統一した）。

（＊10）論文（★２）P.16 第4章〔定理〕
1元方程式 $F\left(x\right)=0$ が可解であるための必要十分条件は $F\left(1\right)F\left(0\right)=0$ であり、
根の公式は $\left[\left.F\left(0\right)\,\cup\,\bar{F\left(1\right)}u\,\right|\,u\in\mathbb{B},\,u\le\bar{F\left(1\right)}\bar{F\left(0\right)}\right]$ 、
根の個数は $N\left(\bar{F\left(1\right)}\bar{F\left(0\right)}\right)$ である。

（＊11）論文（★２）P.24 第5章〔定理〕
$n$ 元方程式 $F\left(x_{1},\dots,x_{n}\right)=0$ が可解であるための必要十分条件は $\bigcap_{\xi}F\left(\xi_{1},\dots,\xi_{n}\right)=0$ であり、
根の公式は
$\left[\left(X_{1},X_{2},\dots,X_{n}\right)\,\left|\;\begin{eqnarray}X_{i}&=&\left(\bigcap_{\xi}F\left(X_{1},\dots,X_{i-1},0,\xi_{i+1},\dots,\xi_{n}\right)\right)\,\cup\,\left(\bigcup_{\xi}\bar{F\left(X_{1},\dots,X_{i-1},1,\xi_{i+1},\dots,\xi_{n}\right)}\right)u_{i}\\&&\begin{eqnarray}u_{i}&\le&\left(\bigcup_{\xi}\bar{F\left(X_{1},\dots,X_{i-1},1,\xi_{i+1},\dots,\xi_{n}\right)}\right)\left(\bigcup_{\xi}\bar{F\left(X_{1},\dots,X_{i-1},0,\xi_{i+1},\dots,\xi_{n}\right)}\right)\\&&i=1,2,\dots,n\end{eqnarray}\end{eqnarray}\right.\right]$ 、
根の個数は $\sum_{u_{n-1}}\sum_{u_{n-2}}\!\,\dots\sum_{u_{1}}N\left(\bar{F\left(X_{1},\dots,X_{n-1},1\right)}\bar{F\left(X_{1},\dots,X_{n-1},0\right)}\right)$ である。

表現が古臭いので翻訳。

「根」は「解」と同じ意味。（厳密には違うんだけど細かいことは気にしない。実はよく分かってないだけなんてナイショ。）
「可解である」は「解をもつ」の意味。これは第4章の最初（P.15）にも書いてある。
「 $N\left(\alpha\right)$ 」は、「集合 $\left\{x\,\left|\,x\le\alpha,\,x\in\mathbb{B}\right.\right\}$ のカージナル数」と定義されている（P.13 第3章）。
カージナル数ってのは要素数のことだと思えばいい。
よって「 $\alpha=0$ のとき $N\left(\alpha\right)=1$ 、 $\alpha=1$ のとき $N\left(\alpha\right)=2$ 」である。
あるいは $\alpha$ をbool型整数でなく普通の整数とみなせば、単に「 $N\left(\alpha\right)=\alpha+1$ 」となる。
「 $\xi$ 」は“ξ”（グザイ）。手書きレポートで書きたくない文字ランキング万年ワースト１。
全然関係ないけど、“ξ”の大文字“Ξ”の筆記体が「Z」を縦に2個重ねたもの（のこぎりの歯みたいな形）なので、それを意識するときれいに“ξ”が書ける。
「」は「」を略記したもの。これは第3章の直前（P.11）に書いてある。
つまり、すべてのの組み合わせについてのの総和（総論理和）を表す。
- 明記はされてないけど、「 $\bigcap_{\xi}\left(\mathrm{something}\right)$ 」も同様の定義。のはず。
式を見れば分かるように、 $X_{i}$ は $X_{1},X_{2},\dots,X_{i-1}$ および媒介変数 $u_{i}$ の関数である。
よって $X_{1},X_{2},\dots,X_{i-1}$ にそれぞれ解の公式を代入して消去すれば、 $X_{i}$ は媒介変数 $u_{1},u_{2},\dots,u_{i}$ の関数となる。

これらの翻訳を使って（＊10）（＊11）を書き換えるのだが、その前に解の公式部分を少し変形しておく。

まず（＊10）から。
解の存在条件 $F\left(0\right)F\left(1\right)=0$ を満たすとき、解の公式 $x=F\left(0\right)\,\cup\,\bar{F\left(1\right)}u$ は次のように変形できる。

（＊12）
$\begin{eqnarray}x&=&F\left(0\right)\,\cup\,\bar{F\left(1\right)}u\\&=&F\left(0\right)\left(u\cup\bar{u}\right)\,\cup\,\bar{F\left(1\right)}u\\&=&F\left(0\right)\bar{u}\,\cup\,\left(F\left(0\right)\,\cup\,\bar{F\left(1\right)}\right)u\\&=&F\left(0\right)\bar{u}\,\cup\,\left(F\left(0\right)\left(F\left(1\right)\cup\bar{F\left(1\right)}\right)\,\cup\,\bar{F\left(1\right)}\right)u\\&=&F\left(0\right)\bar{u}\,\cup\,\left(F\left(0\right)F\left(1\right)\,\cup\,\left(F\left(0\right)\cup 1\right)\bar{F\left(1\right)}\right)u\\&=&F\left(0\right)\bar{u}\,\cup\,\left(0\,\cup\,\bar{F\left(1\right)}\right)u\\&=&F\left(0\right)\bar{u}\,\cup\,\bar{F\left(1\right)}u\end{eqnarray}$

これにより、（＊10）は（＊13）のように書き換えられる。

（＊10）再掲
1元方程式 $F\left(x\right)=0$ が可解であるための必要十分条件は $F\left(1\right)F\left(0\right)=0$ であり、
根の公式は $\left[\left.F\left(0\right)\,\cup\,\bar{F\left(1\right)}u\,\right|\,u\in\mathbb{B},\,u\le\bar{F\left(1\right)}\bar{F\left(0\right)}\right]$ 、
根の個数は $N\left(\bar{F\left(1\right)}\bar{F\left(0\right)}\right)$ である。

（＊13）1変数のブール方程式の解の存在条件と解の公式
$x$ に関するブール方程式 $f\left(x\right)=0$ が解をもつための必要十分条件は $f\left(1\right)f\left(0\right)=0$ である。
また、この条件を満たすとき、解は $0\le u\le\bar{f\left(1\right)}\bar{f\left(0\right)}$ を満たす媒介変数 $u\;\left(\in\mathbb{B}\right)$ を使って次のように表される。

$\begin{eqnarray}x&=&\bar{f\left(1\right)}u\,\cup\,f\left(0\right)\\&=&\bar{f\left(1\right)}u\,\cup\,f\left(0\right)\bar{u}\end{eqnarray}$

><

（※好みの問題で関数名は小文字に変更した。）
（※解の個数は不要なので省略した。）

なお、（＊13）は表現が異なるだけで（＊９）と同値である（当たり前だが）。

（＊９）再掲
$x$ に関するブール方程式 $f\left(x\right)=0$ が解をもつための必要十分条件は $f\left(0\right)f\left(1\right)=0$ である。
また、この条件が満たされるとき、解は $f\left(0\right)\le x\le \bar{f\left(1\right)}$ である。

【簡易証明】

（＊13）⇒（＊９）
$\begin{array}{rlclcl}&0&\le&u&\le&\bar{f\left(0\right)}\bar{f\left(1\right)}\\\Rightarrow&0\,\cap\,\bar{f\left(1\right)}&\le&u\,\cap\,\bar{f\left(1\right)}&\le&\bar{f\left(0\right)}\bar{f\left(1\right)}\,\cap\,\bar{f\left(1\right)}\\\Leftrightarrow&0&\le&\bar{f\left(1\right)}u&\le&\bar{f\left(0\right)}\bar{f\left(1\right)}\\\Rightarrow&0\,\cup\,f\left(0\right)&\le&\bar{f\left(1\right)}u\,\cup\,f\left(0\right)&\le&\bar{f\left(0\right)}\bar{f\left(1\right)}\,\cup\,f\left(0\right)\\&&&&=&\bar{f\left(0\right)}\bar{f\left(1\right)}\,\cup\,f\left(0\right)\left(f\left(1\right)\,\cup\,\bar{f\left(1\right)}\right)\\&&&&=&\left(\bar{f\left(0\right)}\,\cup\,f\left(0\right)\right)\bar{f\left(1\right)}\,\cup\,f\left(0\right)f\left(1\right)\\&&&&=&\bar{f\left(1\right)}\,\cup\,f\left(0\right)f\left(1\right)\\\Leftrightarrow&f\left(0\right)&\le&x&\le&\bar{f\left(1\right)}\end{array}$
（＊９）⇒（＊13）
$\left(f\left(0\right),f\left(1\right)\right)=\left(0,0\right),\left(0,1\right),\left(1,0\right)$ の各組み合わせについて実際に代入して計算すればいい。
~~……正直に言うと、いい証明が思い浮かばなかったorz~~

次に、多変数方程式の解の公式（＊11）について考える。
次のような $n$ 個の変数 $x_{1},x_{2},\dots,x_{n}$ に関する $m$ 本の連立方程式を考える。

（＊14）
$\begin{eqnarray}F_{1}\left(x_{1},x_{2},\dots,x_{n}\right)&=&G_{1}\left(x_{1},x_{2},\dots,x_{n}\right)\\F_{2}\left(x_{1},x_{2},\dots,x_{n}\right)&=&G_{2}\left(x_{1},x_{2},\dots,x_{n}\right)\\&\vdots&\\F_{m}\left(x_{1},x_{2},\dots,x_{n}\right)&=&G_{m}\left(x_{1},x_{2},\dots,x_{n}\right)\end{eqnarray}$

それぞれ右辺を移項すると、

（＊15）
$\begin{array}{lclcl}F_{1}\left(x_{1},x_{2},\dots,x_{n}\right)&\oplus&G_{1}\left(x_{1},x_{2},\dots,x_{n}\right)&=&0\\F_{2}\left(x_{1},x_{2},\dots,x_{n}\right)&\oplus&G_{2}\left(x_{1},x_{2},\dots,x_{n}\right)&=&0\\&&&\vdots&\\F_{m}\left(x_{1},x_{2},\dots,x_{n}\right)&\oplus&G_{m}\left(x_{1},x_{2},\dots,x_{n}\right)&=&0\end{array}$

ところで、次の2つは同値である。

（＊16）

$\alpha_{1}=0$ かつ $\alpha_{2}=0$ かつ …… かつ $\alpha_{k}=0$

$\alpha_{1}\,\cup\,\alpha_{2}\,\cup\,\dots\,\cup\,\alpha_{k}=0$

よって $f\left(x_{1},x_{2},\dots,x_{n}\right)$ を次のように定義すれば、（＊15）は $f\left(x_{1},x_{2},\dots,x_{n}\right)=0$ の形の1本の方程式にすることができる。

（＊17）
$\begin{eqnarray}f\left(x_{1},x_{2},\dots,x_{n}\right)&\overset{\mathrm{def}}{=}&\left(F_{1}\left(x_{1},x_{2},\dots,x_{n}\right)\,\oplus\,G_{1}\left(x_{1},x_{2},\dots,x_{n}\right)\right)\\&\cup&\left(F_{2}\left(x_{1},x_{2},\dots,x_{n}\right)\,\oplus\,G_{2}\left(x_{1},x_{2},\dots,x_{n}\right)\right)\\&\vdots&\\&\cup&\left(F_{m}\left(x_{1},x_{2},\dots,x_{n}\right)\,\oplus\,G_{m}\left(x_{1},x_{2},\dots,x_{n}\right)\right)\\&=&0\end{eqnarray}$

このように、任意の連立方程式は1本の方程式に書き換えることができるので、その方程式に対して（＊11）を適用すればいい。

（＊11）再掲
$n$ 元方程式 $F\left(x_{1},\dots,x_{n}\right)=0$ が可解であるための必要十分条件は $\bigcap_{\xi}F\left(\xi_{1},\dots,\xi_{n}\right)=0$ であり、
根の公式は
$\left[\left(X_{1},X_{2},\dots,X_{n}\right)\,\left|\;\begin{eqnarray}X_{i}&=&\left(\bigcap_{\xi}F\left(X_{1},\dots,X_{i-1},0,\xi_{i+1},\dots,\xi_{n}\right)\right)\,\cup\,\left(\bigcup_{\xi}\bar{F\left(X_{1},\dots,X_{i-1},1,\xi_{i+1},\dots,\xi_{n}\right)}\right)u_{i}\\&&\begin{eqnarray}u_{i}&\le&\left(\bigcup_{\xi}\bar{F\left(X_{1},\dots,X_{i-1},1,\xi_{i+1},\dots,\xi_{n}\right)}\right)\left(\bigcup_{\xi}\bar{F\left(X_{1},\dots,X_{i-1},0,\xi_{i+1},\dots,\xi_{n}\right)}\right)\\&&i=1,2,\dots,n\end{eqnarray}\end{eqnarray}\right.\right]$ 、
根の個数は $\sum_{u_{n-1}}\sum_{u_{n-2}}\!\,\dots\sum_{u_{1}}N\left(\bar{F\left(X_{1},\dots,X_{n-1},1\right)}\bar{F\left(X_{1},\dots,X_{n-1},0\right)}\right)$ である。

（＊11）は（個人的に）分かりにくいので、少し書き換えさせてもらおう。

（＊18）n変数のブール方程式の解の存在条件と解の公式
ブール方程式 $f\left(x_{1},\dots,x_{n}\right)=0$ が解をもつための必要十分条件は $\bigcap_{\mathbf{b}\in\mathbb{B}^{n}}f\left(b_{1},\dots,b_{n}\right)=0$ である。
また、この条件を満たすとき、解は媒介変数 $u_{1},\dots,u_{n}\;\left(\in\mathbb{B}\right)$ を使って次のように表される。

$\left(x_{1},x_{2},\dots,x_{n}\right)=\left(\alpha_{1},\alpha_{2},\dots,\alpha_{n}\right)$
ただし、
$\begin{array}{rclcl}\alpha_{i}&=&\bar{\left(\bigcap_{\mathbf{b}\in\mathbb{B}^{n-i}}f\left(\alpha_{1},\dots,\alpha_{i-1},1,b_{1},\dots,b_{n-i}\right)\right)}u_{i}&\cup&\left(\bigcap_{\mathbf{b}\in\mathbb{B}^{n-i}}f\left(\alpha_{1},\dots,\alpha_{i-1},0,b_{1},\dots,b_{n-i}\right)\right)\\&=&\bar{\left(\bigcap_{\mathbf{b}\in\mathbb{B}^{n-i}}f\left(\alpha_{1},\dots,\alpha_{i-1},1,b_{1},\dots,b_{n-i}\right)\right)}u_{i}&\cup&\left(\bigcap_{\mathbf{b}\in\mathbb{B}^{n-i}}f\left(\alpha_{1},\dots,\alpha_{i-1},0,b_{1},\dots,b_{n-i}\right)\right)\bar{u_{i}}\\0\le u_{i}&\le&\bar{\left(\bigcap_{\mathbf{b}\in\mathbb{B}^{n-i}}f\left(\alpha_{1},\dots,\alpha_{i-1},1,b_{1},\dots,b_{n-i}\right)\right)}&\cap&\bar{\left(\bigcap_{\mathbf{b}\in\mathbb{B}^{n-i}}f\left(\alpha_{1},\dots,\alpha_{i-1},0,b_{1},\dots,b_{n-i}\right)\right)}\end{eqnarray}$

><

（※好みの問題で関数名は小文字に変更した。）
（※解の個数は不要なので省略した。）
（※式中の $\mathbf{b}\;\left(\in\mathbb{B}^{k}\right)$ は $\mathbb{B}$ に含まれる $k$ 個の値の組を表し、 $b_{l}\;\left(\in\mathbb{B}\right)$ は $\mathbf{b}$ の第 $l$ 成分を表す。つまり、 $\mathbf{b}\overset{\mathrm{def}}{=}\left(b_{1},\dots,b_{k}\right)$ である。）

$n$ 変数の場合を考えるのは難しいので、具体例を見てみよう。

まず1変数の場合から。
関数 $f\left(x\right)=a_{1}x\,\cup\,a_{0}\bar{x}$ について、1変数方程式 $f\left(x\right)=0$ を考える。
解の存在条件は $f\left(1\right)f\left(0\right)=0$ である。
このとき、 $0\le u\le\bar{f\left(1\right)}\bar{f\left(0\right)}$ を満たす $u\;\left(\in\mathbb{B}\right)$ を使って、解は $x=\bar{f\left(1\right)}u\,\cup\,f\left(0\right)\bar{u}$ と表せる。
$f\left(0\right)=a_{0},f\left(1\right)=a_{1}$ を使って整理すると、次のようになる。

（＊19）
1変数方程式 $f\left(x\right)=a_{1}x\,\cup\,a_{0}\bar{x}=0$ について、

解の存在条件

$a_{1}a_{0}=0$

解

$x=\bar{a_{1}}u\,\cup\,a_{0}\bar{u}$

ただし、
$0\le u\le\bar{a_{1}}\bar{a_{0}$

次に2変数の場合。
関数 $f\left(x,y\right)=a_{11}xy\,\cup\,a_{10}x\bar{y}\,\cup\,a_{01}\bar{x}y\,\cup\,a_{00}\bar{x}\bar{y}$ について、2変数方程式 $f\left(x,y\right)=0$ を考える。
解の存在条件は $f\left(1,1\right)f\left(1,0\right)f\left(0,1\right)f\left(0,0\right)=0$ である。
このとき、 $0\le u\le\bar{\left(f\left(1,1\right)f\left(1,0\right)\right)}\bar{\left(f\left(0,1\right)f\left(0,0\right)\right)}$ および $0\le v\le\bar{f\left(x,1\right)}\bar{f\left(x,0\right)}$ を満たす $u,v\;\left(\in\mathbb{B}\right)$ を使って、解は $x=\bar{\left(f\left(1,1\right)f\left(1,0\right)\right)}u\,\cup\,f\left(0,1\right)f\left(0,0\right)\bar{u}$ および $y=\bar{f\left(x,1\right)}v\,\cup\,f\left(x,0\right)\bar{v}$ と表せる。
計算がややめんどうだが、整理すると次のようになる。

（＊20）
2変数方程式 $f\left(x,y\right)=a_{11}xy\,\cup\,a_{10}x\bar{y}\,\cup\,a_{01}\bar{x}y\,\cup\,a_{00}\bar{x}\bar{y}=0$ について、

解の存在条件

$a_{11}a_{10}a_{01}a_{00}=0$

解

$\begin{array}{lclcl}x&=&\bar{\left(a_{11}a_{10}\right)}u\,\cup\,\left(a_{01}a_{00}\right)\bar{u}&&\\y&=&\left(\bar{a_{11}}\,\cup\,a_{11}a_{10}\bar{a_{01}}\right)uv&\cup&\left(a_{10}\bar{a_{11}}\,\cup\,a_{10}a_{11}a_{00}\bar{a_{01}}\right)u\bar{v}\\&\cup&\left(\bar{a_{01}}\,\cup\,a_{01}a_{00}\bar{a_{11}}\right)\bar{u}v&\cup&\left(a_{00}\bar{a_{01}}\,\cup\,a_{00}a_{01}a_{10}\bar{a_{11}}\right)\bar{u}\bar{v}\end{array}$

ただし、
$0\le u\le\bar{\left(a_{11}a_{10}\right)}\bar{\left(a_{01}a_{00}\right)}$
$0\le v\le\left(\bar{a_{11}}\bar{a_{10}}\,\cup\,a_{11}a_{10}\bar{a_{01}}\bar{a_{00}}\right)u\,\cup\,\left(\bar{a_{01}}\bar{a_{00}}\,\cup\,a_{01}a_{00}\bar{a_{11}}\bar{a_{10}}\right)\bar{u}$

もう1例、3変数の場合も見てみる。
関数 $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}$ について、3変数方程式 $f\left(x,y,z\right)=0$ を考える。
解の存在条件は $f\left(1,1,1\right)f\left(1,1,0\right)f\left(1,0,1\right)f\left(1,0,0\right)f\left(0,1,1\right)f\left(0,1,0\right)f\left(0,0,1\right)f\left(0,0,0\right)=0$ である。
このとき、 $0\le u\le\bar{\left(f\left(1,1,1\right)f\left(1,1,0\right)f\left(1,0,1\right)f\left(1,0,0\right)\right)}\bar{\left(f\left(0,1,1\right)f\left(0,1,0\right)f\left(0,0,1\right)f\left(0,0,0\right)\right)}$ ， $0\le v\le\bar{\left(f\left(x,1,1\right)f\left(x,1,0\right)\right)}\bar{\left(f\left(x,0,1\right)f\left(x,0,0\right)\right)}$ および $0\le w\le\bar{f\left(x,y,1\right)}\bar{f\left(x,y,0\right)}$ を満たす $u,v,w\;\left(\in\mathbb{B}\right)$ を使って、解は $x=\bar{\left(f\left(1,1,1\right)f\left(1,1,0\right)f\left(1,0,1\right)f\left(1,0,0\right)\right)}u\,\cup\,f\left(0,1,1\right)f\left(0,1,0\right)f\left(0,0,1\right)f\left(0,0,0\right)\bar{u}$ ， $y=\bar{\left(f\left(x,1,1\right)f\left(x,1,0\right)\right)}u\,\cup\,f\left(x,0,1\right)f\left(x,0,0\right)\bar{u}$ および $z=\bar{f\left(x,y,1\right)}w\,\cup\,f\left(x,y,0\right)\bar{w}$ と表せる。
計算がかなりめんどうだが、整理すると次のようになる。

（＊21）
3変数方程式 $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}=0$ について、

解の存在条件

$a_{111}a_{110}a_{101}a_{100}a_{011}a_{010}a_{001}a_{000}=0$

解

$\begin{array}{lclcl}x&=&\bar{\left(a_{111}a_{110}a_{101}a_{100}\right)}u\,\cup\,\left(a_{011}a_{010}a_{001}a_{000}\right)\bar{u}&&\\y&=&\left(\bar{\left(a_{111}a_{110}\right)}\,\cup\,\left(a_{111}a_{110}\right)\left(a_{101}a_{100}\right)\bar{\left(a_{011}a_{010}\right)}\right)uv&\cup&\left(\left(a_{101}a_{100}\right)\bar{\left(a_{111}a_{110}\right)}\,\cup\,\left(a_{101}a_{100}\right)\left(a_{111}a_{110}\right)\left(a_{001}a_{000}\right)\bar{\left(a_{011}a_{010}\right)}\right)u\bar{v}\\&\cup&\left(\bar{\left(a_{011}a_{010}\right)}\,\cup\,\left(a_{011}a_{010}\right)\left(a_{001}a_{000}\right)\bar{\left(a_{111}a_{110}\right)}\right)\bar{u}v&\cup&\left(\left(a_{001}a_{000}\right)\bar{\left(a_{011}a_{010}\right)}\,\cup\,\left(a_{001}a_{000}\right)\left(a_{011}a_{010}\right)\left(a_{101}a_{100}\right)\bar{\left(a_{111}a_{110}\right)}\right)\bar{u}\bar{v}\end{array}$
$\begin{array}{lclcl}z&=&\left(\bar{a_{111}}\,\cup\,a_{111}a_{110}\left(\bar{a_{101}}\,\cup\,a_{101}a_{100}\left(\bar{a_{011}}\,\cup\,a_{011}a_{010}\bar{a_{001}}\right)\right)\right)uvw&\cup&\left(a_{110}\bar{a_{111}}\,\cup\,a_{110}a_{111}\left(a_{100}\bar{a_{101}}\,\cup\,a_{100}a_{101}\left(a_{010}\bar{a_{011}}\,\cup\,a_{010}a_{011}a_{000}\bar{a_{001}}\right)\right)\right)uv\bar{w}\\&\cup&\left(\bar{a_{101}}\,\cup\,a_{101}a_{100}\left(\bar{a_{111}}\,\cup\,a_{111}a_{110}\left(\bar{a_{001}}\,\cup\,a_{001}a_{000}\bar{a_{011}}\right)\right)\right)u\bar{v}w&\cup&\left(a_{100}\bar{a_{101}}\,\cup\,a_{100}a_{101}\left(a_{110}\bar{a_{111}}\,\cup\,a_{110}a_{111}\left(a_{000}\bar{a_{001}}\,\cup\,a_{000}a_{001}a_{010}\bar{a_{011}}\right)\right)\right)u\bar{v}\bar{w}\\&\cup&\left(\bar{a_{011}}\,\cup\,a_{011}a_{010}\left(\bar{a_{001}}\,\cup\,a_{001}a_{000}\left(\bar{a_{111}}\,\cup\,a_{111}a_{110}\bar{a_{101}}\right)\right)\right)\bar{u}vw&\cup&\left(a_{010}\bar{a_{011}}\,\cup\,a_{010}a_{011}\left(a_{000}\bar{a_{001}}\,\cup\,a_{000}a_{001}\left(a_{110}\bar{a_{111}}\,\cup\,a_{110}a_{111}a_{100}\bar{a_{101}}\right)\right)\right)\bar{u}v\bar{w}\\&\cup&\left(\bar{a_{001}}\,\cup\,a_{001}a_{000}\left(\bar{a_{011}}\,\cup\,a_{011}a_{010}\left(\bar{a_{101}}\,\cup\,a_{101}a_{100}\bar{a_{111}}\right)\right)\right)\bar{u}\bar{v}w&\cup&\left(a_{000}\bar{a_{001}}\,\cup\,a_{000}a_{001}\left(a_{010}\bar{a_{011}}\,\cup\,a_{010}a_{011}\left(a_{100}\bar{a_{101}}\,\cup\,a_{100}a_{101}a_{110}\bar{a_{111}}\right)\right)\right)\bar{u}\bar{v}\bar{w}\end{array}$

ただし、
$0\le u\le\bar{\left(a_{111}a_{110}a_{101}a_{100}\right)}\bar{\left(a_{011}a_{010}a_{001}a_{000}\right)}$
$\begin{eqnarray}0\le v&\le&\left(\bar{\left(a_{111}a_{110}\right)}\bar{\left(a_{101}a_{100}\right)}\,\cup\,\left(a_{111}a_{110}\right)\left(a_{101}a_{100}\right)\bar{\left(a_{011}a_{010}\right)}\bar{\left(a_{001}a_{000}\right)}\right)u\\&\cup&\left(\bar{\left(a_{011}a_{010}\right)}\bar{\left(a_{001}a_{000}\right)}\,\cup\,\left(a_{011}a_{010}\right)\left(a_{001}a_{000}\right)\bar{\left(a_{111}a_{110}\right)}\bar{\left(a_{101}a_{100}\right)}\right)\bar{u}\end{eqnarray}$
$\begin{eqnarray}0\le v&\le&\left(\bar{a_{111}}\bar{a_{110}}\,\cup\,a_{111}a_{110}\left(\bar{a_{101}}\bar{a_{100}}\,\cup\,a_{101}a_{100}\left(\bar{a_{011}}\bar{a_{010}}\,\cup\,a_{011}a_{010}\bar{a_{001}}\bar{a_{000}}\right)\right)\right)uv\\&\cup&\left(\bar{a_{101}}\bar{a_{100}}\,\cup\,a_{101}a_{100}\left(\bar{a_{111}}\bar{a_{110}}\,\cup\,a_{111}a_{110}\left(\bar{a_{001}}\bar{a_{000}}\,\cup\,a_{001}a_{000}\bar{a_{011}}\bar{a_{010}}\right)\right)\right)u\bar{v}\\&\cup&\left(\bar{a_{011}}\bar{a_{010}}\,\cup\,a_{011}a_{010}\left(\bar{a_{001}}\bar{a_{000}}\,\cup\,a_{001}a_{000}\left(\bar{a_{111}}\bar{a_{110}}\,\cup\,a_{111}a_{110}\bar{a_{101}}\bar{a_{100}}\right)\right)\right)\bar{u}v\\&\cup&\left(\bar{a_{001}}\bar{a_{000}}\,\cup\,a_{001}a_{000}\left(\bar{a_{011}}\bar{a_{010}}\,\cup\,a_{011}a_{010}\left(\bar{a_{101}}\bar{a_{100}}\,\cup\,a_{101}a_{100}\bar{a_{111}}\bar{a_{110}}\right)\right)\right)\bar{u}\bar{v}\end{eqnarray}$