5個以下の2入力NANDで3入力ORは作れるか?

作れません。(タイトル回収終了)

🐟

2入力NANDゲート回路だけで任意の論理演算が表現可能であるという事実はよく知られています。また、最小個数のNANDを用いてNOT・AND・OR・XORなどのゲートを実現する方法も有名です。(下画像)

f:id:sh-mug:20200507222911p:plain

ところで、3入力ゲート回路(AND・NAND・OR・NOR・XOR・XNOR)を実現するために必要なNANDの最小個数はあまり知られていない(はず)です。3入力ゲート回路の定義ですが、AND・OR・XORについては結合法則が成り立つので自然に定義できます。NAND・NOR・XNORは前の3つの論理否定とします。

やったこと

NAND同士を配線するときに回路内にループができると順序回路ができてしまうため、そうならないような配線方法のみを考えます。使用するNANDの個数を1個から順番に調べていき、求める出力を得られる回路が見つかればそのときの個数が最小だと分かります。

配線方法の探索にはSMTソルバの一つであるz3を使用しました。書いたコードは ここ です。リンク先のコードでは最小個数の3入力NANDから3入力XNORを構成するような配線方法を求めています。

結果など

2入力NANDを用いる場合、3入力NANDを用いる場合の最小個数を調べました。

使用するNAND AND NAND  OR  NOR XOR XNOR
2入力 4 3 6 7 8 9
3入力 2 1 4 5 7 7

3入力NANDを7個用いて3入力XOR・XNORを構成できるというのは比較的非自明で面白い結論かもしれません。回路図は下に示します。なお、NAND(A, A, B) = NAND(A, B)より、このような入力パターンの3入力NANDは2入力NANDを用いて略記しています。

f:id:sh-mug:20200507223004p:plain
XOR

f:id:sh-mug:20200507223023p:plain
XNOR

一方で、その他のゲート回路とNANDの入力の組み合わせについて、最小個数のNANDで構成するのは🐟にある回路の組み合わせだけで可能であり、必要なNAND数をそこから減らせないことも明らかになりました。(タイトル回収2回目)

🍣

z3を使う前にC++で配線方法を全探索するコードを書いていたのですが、z3を使ったほうが実行速度が圧倒的に速かったです。z3最高ですね

家にNANDしか無くて困っている人は参考にしてみてください。