否定論理積NANDですべての2変数論理関数を表してみた
はじめに
この記事はタイトルの通り全ての２変数論理関数をNANDを使って表してみたというものです.
${\large \bigstar}$ちなみにこの内容は,私が参考にさせていただいた「数学の基礎体力をつけるためのろんりの練習帳」（共立出版）の$\mathrm{P.}39$の演習問題$1$に対応しているので,参考にしていただけると嬉しいです.
命題の真偽と真理値
ある命題に対して,それが正しければその命題は真であるといい,正しくなければ偽であるという.
ある命題が真であることを$1$,偽であることを$0$と略記して,それを命題の真理値と呼ぶ.
2変数論理関数
論理積を$f(p,q)= p\land q$とおく.
２変数の論理関数の種類を考えてみると,$p,q$の真理値の取りうる値は$$(p,q)=(1,1),(1,0),(0,1),(0,0)$$の4通りである.
したがって,関数$f(p,q)$は全部で$16$個あることがわかる.
それらを$f_n(p,q)$(ただし $n=1,2 \cdot\cdot\cdot\cdot16 $)を全て書き上げると以下のようになる.
真理値表A
| $(p,q)$ | $(1,1)$ | $(1,0)$ | $(0,1)$ | $(0,0)$ |
|---|---|---|---|---|
| $f_1$ | $1$ | $1$ | $1$ | $1$ |
| $f_2$ | $1$ | $1$ | $1$ | $0$ |
| $f_3$ | $1$ | $1$ | $0$ | $1$ |
| $f_4$ | $1$ | $1$ | $0$ | $0$ |
| $f_5$ | $1$ | $0$ | $1$ | $1$ |
| $f_6$ | $1$ | $0$ | $1$ | $0$ |
| $f_7$ | $1$ | $0$ | $0$ | $1$ |
| $f_8$ | $1$ | $0$ | $0$ | $0$ |
| $f_9$ | $0$ | $1$ | $1$ | $1$ |
| $f_{10}$ | $0$ | $1$ | $1$ | $0$ |
| $f_{11}$ | $0$ | $1$ | $0$ | $1$ |
| $f_{12}$ | $0$ | $1$ | $0$ | $0$ |
| $f_{13}$ | $0$ | $0$ | $1$ | $1$ |
| $f_{14}$ | $0$ | $0$ | $1$ | $0$ |
| $f_{15}$ | $0$ | $0$ | $0$ | $1$ |
| $f_{16}$ | $0$ | $0$ | $0$ | $0$ |
ここで,$f_2$は論理和$\mathrm{(OR)}$,$f_8$は論理積$\mathrm{(AND)}$,$f_9$が否定論理積$\mathrm{(NAND)}$,$f_{10}が$排他的論理和$\mathrm{(XOR)}$,$f_{15}$は否定論理和$\mathrm{(NOR)}$である.
ここで,この先の変形で用いるド・モルガンの法則を証明しておく.
$(1)\overline{p\land q}\equiv \overline{p} \lor \overline{q}$
$(2)\overline{p\lor q}\equiv \overline{p} \land\overline{q}$
$(1)$
| $p$ | $q$ | $p\land q$ | $\overline{p\land q}$ | $\overline{p}$ | $\overline{q}$ | $\overline{p}\lor \overline{q}$ |
|---|---|---|---|---|---|---|
| $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ |
| $1$ | $0$ | $0$ | $1$ | $0$ | $1$ | $1$ |
| $0$ | $1$ | $0$ | $1$ | $1$ | $0$ | $1$ |
| $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ |
上表より,$\overline{p\land q}$と$\overline{p}\lor \overline{q}$の真理値が一致するので成立.$\blacksquare$
$(2)$
| $p$ | $q$ | $p\lor q$ | $\overline{p\lor q}$ | $\overline{p}$ | $\overline{q}$ | $\overline{p}\land \overline{q}$ |
|---|---|---|---|---|---|---|
| $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ |
| $1$ | $0$ | $1$ | $0$ | $0$ | $1$ | $0$ |
| $0$ | $1$ | $1$ | $0$ | $1$ | $0$ | $0$ |
| $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ |
上表より,$\overline{p\lor q}$と$\overline{p}\land \overline{q}$の真理値が一致するので成立.$\blacksquare$
問題
$f_n(p,q)$ ($n=1,2 \cdot\cdot\cdot\cdot16 $)を全て$f_9\mathrm{(NAND)}$を用いて表せ.
$f_1$について
\begin{align} f_1(p,q) &= \overline{p\land \overline{q}}
\\ & \equiv\overline{p\land(\overline{p\land p})}\\ & \equiv \overline{p\land f_9(p,p)}\\ & \equiv f_9(p,f_9(p,p))
\end{align}
となる.
$f_2\mathrm{(OR)}$について
\begin{align}
f_2(p,q) &=p\lor q
\\ & \equiv\overline{\overline{p}\land \overline{q}}\\ & \equiv \overline{f_9(p,p)\land f_9(q,q)}\\ & \equiv \overline{f_9(p,p)}\lor \overline{f_9(q,q)}
\\ &\equiv f_9(f_9(p,p).f_9(q,q))
\end{align}
となる.
$f_3$について
\begin{align}
f_3(p,q)&=p\lor\overline{q}
\\ &\equiv p\lor f_9(q,q)
\\&\equiv \overline{\overline{p\lor f(q,q)}}
\\&\equiv \overline{\overline{p}\land \overline{f_9(q.q)}}
\\&\equiv \overline{f_9(p,p)\land f_9(f_9(q,q),f_9(q,q))}
\\&\equiv f_9(f_9(p,p),f_9(f_9(q,q),f_9(q,q)))
\\&\equiv f_9(f_9(p.p),q)
\end{align}
となる.
注意と言うほどの注意ではないが最後の変形について,$f_9(f_9(q,q),f_9(q,q))$は,否定をさらに否定しているので$q$になる.
$f_4$について
\begin{align}
f_4(p,q)&=p
\\&\equiv \overline{\overline{p}}
\\&\equiv \overline{\overline{p\land p}}
\\&\equiv \overline{f_9(p.p)\land f_9(p,p)}
\\&\equiv f_9(f_9(p,p),f_9(p,p))
\end{align}
となる.
$f_9(p,q)\equiv p$なのだが,問題では$f_9$で表現しろと書いてあるので,仕方なく複雑な式の方にした.
$f_5$について
\begin{align}
f_5(p,q)&=\overline{p}\lor q
\\&\equiv \overline{(p\land p)}\lor q
\\&\equiv \overline{\overline{f_9(p,p)\lor q}}
\\&\equiv \overline{\overline{f_9(p,p)}\land \overline{q}}
\\&\equiv \overline{f_9(f_9(p,p),f_9(p,p))\land f_9(q,q)}
\\&\equiv \overline{p\land f_9(q,q)}
\\&\equiv f_9(p,f_9(q,q))
\end{align}
となる.
$f_6$について
\begin{align}
f_6(p,q)&=q
\\&\equiv \overline{\overline{q}}
\\&\equiv \overline{\overline{q\land q}}
\\&\equiv \overline{f_9(q.q)\land f_9(q,q)}
\\&\equiv f_9(f_9(q,q),f_9(q,q))
\end{align}
となる.(変形の方法は$f_4$の時と同じ)
$f_7$について
\begin{align}
f_7(p,q)&=\overline{(p\land \overline{q})\lor (\overline{p}\land q)}
\\&\equiv \overline{\overline{(\overline {p\land \overline{q}})\land(\overline {\overline{p}\land q})}}
\\&\equiv \overline{\overline{f_9(p,\overline{q})\land f_9(\overline{p},q)}}
\\&\equiv \overline{f_9(f_9(p,\overline{q}),f_9(\overline{p},q))}
\\&\equiv f_9(f_9(f_9(p,\overline{q}),f_9(\overline{p},q)),f_9(f_9(p,\overline{q}),f_9(\overline{p},q)))
\\&\equiv f_9(f_9(f_9(p,f_9(q,q)),f_9(f_9(p,p),q)),f_9(f_9(p,f_9(q,q)),f_9(f_9(p,p),q)))
\end{align}
となる.
$f_8\mathrm{(AND)}$について
\begin{align}
f_8(p,q)&=p\land q
\\&\equiv \overline{(\overline {p\land q})}
\\&\equiv \overline{f_9(p,q)}
\\&\equiv f_9(f_9(p,q),f_9(p,q))
\end{align}
となる.
ここで、先の真理値表$\mathrm{A}$ より、$f_n(p,q)$は$n=1\sim8$と$n=9\sim16 $で対称性があることに着目して式変形を進めていく.
$f_9\mathrm{(NAND)}$
これはそのまま$f_9(p,q)$となる.
$f_{10}\mathrm{(XOR)}$について
\begin{align}
f_{10}(p,q)&=(p\land \overline{q})\lor (\overline{p}\land q)
\\&\equiv \overline{(\overline {p\land \overline{q}})}\lor \overline{(\overline {\overline{p}\land q})}
\\&\equiv \overline{\overline{(p\land \overline{q})}\land\overline{(\overline{p}\land q)}}
\\&\equiv {\overline{f_9(p,\overline{q})\land f_9(\overline{p},q)}}
\\&\equiv f_9(f_9(p,\overline{q})\land f_9(\overline{p},q))
\\&\equiv f_9(f_9(p,f_9(q,q)),f_9(f_9(p,p),p))
\end{align}
となる.
$f_{11}$について
\begin{align} f_{11}(p,q)&=\overline{f_6(p,q)} \\&\equiv \overline{q} \\&\equiv \overline{q\land q} \\&\equiv f_9(q,q) \end{align}となる.
$f_{12}$について
\begin{align}
f_{12}(p,q)&=
\\&\equiv \overline{f_5(p,q)}
\\&\equiv \overline{\overline{p}\lor q}
\\&\equiv p\land \overline{q}
\\&\equiv \overline{\overline{p\land \overline{q}}}
\\&\equiv \overline{f_9(p,\overline{q})}
\\&\equiv f_9(f_9(p,\overline{q}),f_9(p,\overline{q}))
\\&\equiv f_9(f_9(p,f_9(q,q)),f_9(p,f_9(q,q)))
\end{align}
となる.
$f_{13}$について
\begin{align}
f_{13}(p,q)&=\overline{f_4(p,q)}
\\&\equiv \overline{p}
\\&\equiv f_9(p,p)
\end{align}
となる.
$f_{14}$について
\begin{align}
f_{14}(p,q)&=\overline{f_3(p,q)}
\\&\equiv \overline{p\lor \overline{q}}
\\&\equiv \overline{p}\land q
\\&\equiv \overline{\overline{\overline{p}\land q}}
\\&\equiv \overline{f_9(\overline{p},q)}
\\&\equiv f_9(f_9(\overline{p},q),f_9(\overline{p},q))
\\&\equiv f_9(f_9(f_9(p,p),q),f_9(f_9(p,p),q))
\end{align}
となる.
$f_{15}$について
\begin{align}
f_{15}(p,q)&=\overline{f_2(p,q)}
\\&\equiv \overline{p\lor q}
\\&\equiv \overline{\overline{\overline{p}\land\overline{q}}}
\\&\equiv \overline{f_9(\overline{p},\overline{q})}
\\&\equiv f_9(f_9(\overline{p},\overline{q}),f_9(\overline{p},\overline{q}))
\\&\equiv f_9(f_9(f_9(p,p),f_9(q,q)),f_9(f_9(p,p),f_9(q,q)))
\end{align}
となる.
$f_{16}$について
\begin{align}
f_{16}(p,q)&=\overline{f_1(p,q)}
\\&\equiv \overline{\overline{p\land \overline{p}}}
\\&\equiv \overline{f_9(p,\overline{p})}
\\&\equiv f_9(f_9(p,\overline{p}),f_9(p,\overline{p}))
\\&\equiv f_9(f_9(p,f_9(p,p)),f_9(p,f_9(p,p)))
\end{align}
となる.
結果をまとめると,以下のようになる.
| $f_n$ | $f_9$を用いて表した結果 |
|---|---|
| $f_1$ | $f_9(p,f_9(p,p))$ |
| $f_2$ | $f_9(f_9(p,p).f_9(q,q))$ |
| $f_3$ | $f_9(f_9(p.p),q)$ |
| $f_4$ | $f_9(f_9(p,p),f_9(p,p))$ |
| $f_5$ | $f_9(p,f_9(q,q))$ |
| $f_6$ | $f_9(f_9(q,q),f_9(q,q))$ |
| $f_7$ | $f_9(f_9(f_9(p,f_9(q,q)),f_9(f_9(p,p),q)),f_9(f_9(p,f_9(q,q)),f_9(f_9(p,p),q)))$ |
| $f_8$ | $f_9(f_9(p,q),f_9(p,q))$ |
| $f_9$ | $f_9(p,q)$ |
| $f_{10}$ | $f_9(f_9(p,f_9(q,q)),f_9(f_9(p,p),p))$ |
| $f_{11}$ | $f_9(q,q)$ |
| $f_{12}$ | $f_9(f_9(p,f_9(q,q)),f_9(p,f_9(q,q)))$ |
| $f_{13}$ | $f_9(p,p)$ |
| $f_{14}$ | $f_9(f_9(f_9(p,p),q),f_9(f_9(p,p),q))$ |
| $f_{15}$ | $f_9(f_9(f_9(p,p),f_9(q,q)),f_9(f_9(p,p),f_9(q,q)))$ |
| $f_{16}$ | $f_9(f_9(p,f_9(p,p)),f_9(p,f_9(p,p)))$ |
個々の関数を$\mathrm{NAND}$を用いた表現法は一意的ではないので,もう少しシンプルな表現法があったら教えていただけると幸いです.
NAND関数のメリットについて
NAND関数は主にデジタル回路に用いられています.
NAND回路で他の論理回路を作ることができるので回路の製造コストを抑えることができたり,他の回路素子を購入する必要がなくなり,部品の不足ががなくなるというメリットがあります.
このような理由で,NANDゲートはユニバーサル・ゲートとも呼ばれているそうです.
まとめと感想
長ったらしくなってしまいました.
一生分のド・モルガンをした気がします.
時間があったら「ろんりと集合」$\mathrm{P}.39$の演習問題2と3も解いて,答えを投稿したいと思います.(答えがついていないので)
なにか間違っているところがあったらコメントいただけると嬉しいです.
最後まで読んでいただきありがとうございました.
