NAND回路の問題について

２入力１出力の論理回路は全部で１６通り存在する。これらすべてがNAND回路で構成できることを証明せよ、という問題があるのですが、さっぱりわかりません。

とりあえずそのそのような回路が１６通りあることまでは確認しました。でもこれらすべてがNAND回路で構成できることを証明せよ、という部分が全くわかりません。

「計算科学の基礎」（八村広三郎著）や「情報科学と基礎」（竹田仁）といった参考書を何度読んでも、ヒントすら得られない状況です。

どなたかこの問題のキーポイントを教えてくださいませんか？よろしくも願いします。

No.6 回答者： subtanaka 回答日時： 2007/05/25 11:51

論理回路の基本ですのでよく勉強しておいて下さい。

http://laputa.cs.shinshu-u.ac.jp/~yizawa/logic_t …

No.5 回答者： tadys 回答日時： 2007/05/21 11:05

１６種類ぐらいであるならば、その１６種類を実際に作って見せればいいのです。

出来る事を証明すれば良いだけなので効率などは無視して良いですね。

２ビットの入力をデコードして４ビットにしてその４ビットを適当に
組み合わせて１６種類の出力を得るようにすれば出来ます。

No.4 回答者： Microstar 回答日時： 2007/05/21 00:03

前仕事として制御系マイクロコンピュータのレイアウト設計を経験したので、回答します。

半導体チップ上のデジタル回路は、ＮＡＮＤ、ＮＯＲ、ＮＯＴの３個を基本にして構成されるようになっているため、こういう問題が出てくるのです。

すぐ解けるようにするには、論理式と入出力による符号表をしっかり身につけるのが早道です。
それがわかれば、ＮＡＮＤ回路だけでＯＲ回路を構成できます。

今思えば、懐かしい問題です。

No.3 回答者： Oh-Orange 回答日時： 2007/05/20 23:13

★MIL記号では。

・MIL記号で NAND 回路は AND 回路の出力に NOT の○を追加していますよね。
　これを OR の入力部にすべて NOT の○をつけて表したのと同じになります。
　イメージわきますか。NAND＝入力部に NOT が付いた OR と同じ論理なのです。
・この変形表記した NAND(NOT 付きの OR)にさらに NAND で作った NOT を入力側に
　２つ付けます。そうすると OR 回路になりますね。
・OR 回路が出来れば、出力端子に NAND で作った NOT を入れると NOR 回路になります。
・NAND 回路の出力端子に NAND で作った NOT を入れると AND 回路になります。
・これで NAND、OR、NOR、AND の４つが出来ます。
　すると２入力(組み合わせ数：４)×４タイプの回路(NAND、OR、NOR、AND)＝16通りです。
　こう考えると簡単ですよ。

補足:
・この説明は MIL 記号の意味と NAND が NOT 付きの入力端子を持つ OR と同じ論理になる
　ことを事前に知らないと理解できそうにないね。でも、この解説をきっかけにお勉強しましょう。
・MIL 記号で NAND 回路は、NOT 付きの入力を持つ OR 回路と同じになるのです。
　
　(NAND)
　A B Y
　0 0 1
　0 1 1
　1 0 1
　1 1 0
　　↓
　(OR)
　A B Y
　0 0 0
　0 1 1
　1 0 1
　1 1 1
　　↓
　(入力がNOT 付きの OR)
　A B Y
　1 1 1
　1 0 1
　0 1 1
　0 0 0
・以上。私なりの解説でした。

No.2 回答者： ymmasayan 回答日時： 2007/05/20 22:49

No.1の方のやり方が正道かも知れませんが泥臭い方法で。

16種類と言うのはＢＯＸがＯＲかＡＮＤで
入出力は３つで、肯定否定の組み合わせで結局2^4＝１６通りです。

つまり、ＡＮＤ、ＯＲ　、ＮＯＴの組み合わせと言うことです。
そこで、ＡＮＤ、ＯＲ、ＮＯＴがそれぞれＮＡＮＤで構成できることを証明すればいいですね。

ＮＯＴ・・・例えば入力を直結するとＮＯＴ(Ａ・Ｂ)＝ＮＯＴ(Ａ・Ａ)
　　　　　　＝ＮＯＴ(Ａ)
　　　　　　またＢ＝１で固定すればＮＯＴ(Ａ・Ｂ)＝ＮＯＴ(Ａ・１)
　　　　　　＝ＮＯＴ(Ａ)
ＯＲ・・・・ＮＯＴ(Ａ・Ｂ)＝ＮＯＴ(Ａ)＋ＮＯＴ(Ｂ)
　　　　　　これはＮＡＮＤの前にＮＯＴ２つをおけばＯＲが構成できることを
　　　　　　示しています。
ＡＮＤはご自分でやってみてください。ごく簡単です。
ＮＡＮＤを否定すればいいのです。

No.1 回答者： arihina 回答日時： 2007/05/20 19:54

ANDとNOTは２つで万能であるという定理が問題のどこかにありませんか？

その定理と、NANDだけでNOTを作れるということでNANDの万能性が証明できるとおもいます。