NANDだけでEx-NORを構成するときの、NANDの最小個数

NANDだけでEx-NORを構成するときの、NANDの最小個数は5個であることの証明。
を昔やろうとして、微妙に不完全だったもの。
頑張って樹形図的に組み合わせていって、texで書いていったやつ。
これだけパッ見ると文字化けしているようにしか見えない。
もし興味があればWinShellか何かで見てください。

（以下証明）
************************************************************************

　入力を$A$，$B$とすると，1個のNANDを用いて作ることが出来る出力は$\overline{A}，\ \overline{B}，\ \overline{A\cdot B}$のいずれかである．
スマートではないが，このように順々に樹形図的に考えていくこととする．\\
　いまEx-ORおよびEX-NORを表す式は，どのように式変形を行っても式中に$A$と$B$が等しく存在する．(この証明も必要であると思うが，至らなかった．)この性質と，$A\cdot\overline{A}$のような明らかに不必要な式を省略することを考え，NANDを4個使用した組み合わせを考えると次のようになる．\\
\begingroup
\renewcommand{\arraystretch}{1.7}
\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
　入力　&1つめのNAND& 2つめのNAND & 3つめのNAND & 4つめのNAND \\
\hline
\multirow{11}{*}{$A$} & \multirow{11}{*}{$\overline{A}$} & \multirow{3}{*}{$\overline{B}$} & $\overline{A\cdot\overline{B}}$ & \\
& & & $\overline{\overline{A}\cdot B}$&\\
& & & $\overline{\overline{A}\cdot \overline{B}}$&\\
\cline{3-5}
& & \multirow{4}{*}{$\overline{A\cdot B}$} & $\overline{A\cdot\overline{A\cdot B}}$ & $\overline{B\cdot \overline{A\cdot\overline{A\cdot B}}}$\\
\cline{4-5}
& & & \multirow{2}{*}{$\overline{B\cdot\overline{A\cdot B}}$}&$\overline{A\cdot \overline{B\cdot\overline{A\cdot B}}}$\\
& & & &$\overline{\overline{A}\cdot \overline{B\cdot\overline{A\cdot B}}}$\\
\cline{4-5}
& & & $\overline{\overline{A}\cdot\overline{A\cdot B}}$ & $\overline{B\cdot \overline{\overline{A}\cdot\overline{A\cdot B}}}$\\
\cline{3-5}
& & \multirow{4}{*}{$\overline{\overline{A}\cdot B}$} & $\overline{\overline{A}\cdot\overline{A\cdot B}}$ & $\overline{B\cdot \overline{\overline{A}\cdot\overline{A\cdot B}}}$\\
\cline{4-5}
\multirow{4}{*}{$B$} & & & \multirow{2}{*}{$\overline{B\cdot\overline{\overline{A}\cdot B}}$}&$\overline{A\cdot \overline{B\cdot\overline{\overline{A}\cdot B}}}$\\
& & & &$\overline{\overline{A}\cdot \overline{B\cdot\overline{\overline{A}\cdot B}}}$\\
\cline{4-5}
& & & $\overline{\overline{A}\cdot\overline{\overline{A}\cdot B}}$ & $\overline{B\cdot \overline{\overline{A}\cdot\overline{\overline{A}\cdot B}}}$\\
\cline{2-5}
& $\overline{B}$ & \multicolumn{2}{c}{　　　（$\overline{A}$と同様）} & \\
\cline{2-5}
&\multirow{4}{*}{$\overline{A\cdot B}$}& \multirow{3}{*}{$\overline{B\cdot\overline{A\cdot B}}$} & $\overline{A\cdot \overline{B\cdot\overline{A\cdot B}}}$ & $\overline{\overline{A\cdot B}\cdot \overline{A\cdot \overline{B\cdot\overline{A\cdot B}}}}$\\
\cline{4-5}
& & & $\overline{\overline{A\cdot B}\cdot \overline{B\cdot\overline{A\cdot B}}}$ & $\overline{A\cdot \overline{\overline{A\cdot B}\cdot \overline{B\cdot\overline{A\cdot B}}}}$\\
\cline{4-5}
& & & $\overline{A\cdot\overline{A\cdot B}}$ & $\overline{\overline{A\cdot\overline{A\cdot B}}\cdot \overline{B\cdot\overline{A\cdot B}}}$\\
\cline{3-5}
& &$\overline{A\cdot\overline{A\cdot B}}$ & \multicolumn{1}{c}{　　　　　　　（$\overline{B\cdot\overline{A\cdot B}}$と同様）}& \\
\hline
\end{tabular}
\end{center}
\end{table}
\endgroup

NANDを4個および3個用いて出来る式の内，$A$と$B$の数が等しいものに対し全て変形を行った結果Ex-NORの出力となるものは存在しなかった．このことから，Ex-NORを構成するNANDの最小個数は5個であることが示された．(不完全)\\