論理回路

質問

NORとNANDはそれのみですべての素子を表現できるということは結構有名な話かと思うのですが、先日、ANDとORだけではNOTは表現できないことを証明しなさいという問題を見かけました。
NORとNANDがAND、OR、NOTを表現できることを示すという問題は良く見るのですが、表現できないことを示す問題は初めてで、どのように解くのだろうと疑問に思いました。
ANDとORの式変形ではどうにもならないような気がするのですが、どうすれば証明できるのでしょうか？NOTを表現できないと言われればまぁ当然な気もするんですが。。。
この問題が載っていた資料には解答はなく、ヒントに『ゲートの数の帰納法』とありました。
１つのゲートじゃ表現できないのは当然ですが、ｋ個のとき表現できないことを仮定してもｋ＋１で表現できないということは必ずしも言えないんじゃないかと思ってしまいます。
おそらくは何かしらの考え方をするとそう言えてしまうのでしょう。
どんな些細なことでも構いませんのでご教授くださいませ。

回答No.1

rabbit_cat · ベストアンサー

入力がＡだとして、他に可能な入力として1と0があると仮定します。
1つのOR回路で実現できるのは、
A or A = A
A or 1 = 1
A or 0 = A
1 or 1 = 1
1 or 0 = 1
0 or 0 = 0
だけで、OR回路を通しても A,1,0の３種類から増えません。

同様に１つのAND回路に、A,0,1の３種類の入力をどう組み合わせて入力しても、A,0,1以外の結果を得ることはできません。

つまり、「k個のゲートでは、A,0,1の出力しか得られない」ことを仮定すると、「(k+1)個のゲートでも、A,0,1の出力しか得られない」がいえます。

お礼

その様に考える確かにそうですね。
とても参考になりました。ありがとうございます。

回答No.3

noname#101087

#2 ですが、肝心のとこがミスでした。
-----
しかし、(1) は常に0を出し、(2) は常に1を出す構成である。
そのため、 a=0 かa=1 かに応じて (1),(2) を選ぶには、a の否定が必要になり「無限遡行」の状況に陥るらしい。

お礼

このような考え方もあるのですね。
否定系のNORやNANDが重宝するのはこういう所以なんでしょうかね。
ありがとうございました。

回答No.2

noname#101087

#1 さんと本質的には同じストーリーですが、ゲート回路で考えてみましょう。

二つの二進値a,bを AND,OR に入れてみる。
(1) a=1 のとき0が出るのは、AND でb=0 の場合のみ。
(2) a=0 のとき1が出るのは、OR でb=1 の場合のみ。
しかし、(1) は常に0を出し、(2) は常に0を出す構成である。
そのため、 a=0 かa=1 かに応じて (1),(2) を選ぶには、a の否定が必要になり「無限遡行」の状況に陥るらしい。