NotとAnd／Orからならすべての論理回路が作れることは分かりました。ではAnd、OrのみからNot回路は作れないのでしょうか？
直感的に「作れない」って感じるんですが、きちんと論理的に説明するのはけっこう難しい気がします。
ではどうやったら説明できるか。
Notは１入力１出力の回路です。まずは入力をaとおきます。最初の入力の可能性としてはa、定数0、定数1のどれかしかありません。
最初の入力から次の出力の可能性は次の表の通りです。やっぱりa,0,1のどれかになってしまいます。
| 入力１ | 入力２ | And出力 | Or出力 |
|---|---|---|---|
| a | 0 | 0 | a |
| a | 1 | a | 1 |
| a | a | a | a |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
つぎに1出力ってことを考えます。And、Orのみで回路を作るならケーブルをまとめる最後の素子はAndまたはOrのどっちかになります。そして回路の最初の入力も次の出力もa,0,1になってるので、最後の出力もやっぱりa,0,1になってしまう。
雑に図解するとこんな感じ。
途中の回路がどんな複雑でもAnd／Orのみなら中間出力も変わらないので、最後の論理素子の入力も変わらない。だから最後までNot aを作ることはできない。
……という説明を考えてみたけど、なんだかすっきりしない。背理法か何かでさっぱりと証明する方法はないのかなー。
追記：ツイートしたら@chiralさんが速攻で返信くれました。だいぶすっきりした！
@deltam それを実現する段数が最小の回路をXとしましょう。いま、出力が1だとすると、出力の手前の素子Yへの入力は(Xの段数最小性より)全てゼロのはずです。するとYがANDでもORでも入力が全てゼロなら出力は決して1にならないので矛盾。
Q.E.D.
— ITコンサルタント (@chiral) 2015, 4月 19
0 件のコメント:
コメントを投稿