[論理回路] ゲートの万能性の判定方法

質問

最近独学で論理回路を勉強している者です。
ある本に以下のゲート(素子)の組み合わせは万能(任意のブール
関数を表現できる)であるとあったのですが、
(1){AND, NOT}
(2){OR, NOT}
(3){NAND}
(4){NOT}
((3)、(4)は単一種類のゲートですが、便宜上集合表現にしました)
これに関して次の(A)、(B)の疑問が浮かびました。

(A)(1)～(4)以外に((1)～(4)を部分集合として含まない)万能
であるゲートの組み合わせは存在しないのか?
(B)あるゲートの組み合わせ(たとえば{XOR}、{XOR、NOT}など)
　が万能性を持たないことはどうやって証明すればいいのか?

ご存知の方、ご教示をいただければ幸いです(参考文献の指示等
でもありがたいです)。
どうぞよろしくお願いいたします。

回答No.3

yuragifuu

（ご指摘ありがとう^^)
　内容については、全く、不勉強の限りでそうかもしれません。　重ね重ね失礼しました。

　また　句読点など、これから注意していこうと思っています。　ありがとうございました。

　これからも、皆さんの回答など参考にさせて貰おうと楽しみにしています。

お礼

yuragifuu様、わざわざ返信をありがとうございます。

ところで、その後本を読んでこの疑問への解答を得ることが出来ました。結論を手短かに紹介しますと、次のような定理が存在するそうです。

[定理]
論理関数(ゲート)の集合Sは、以下の5つの論理関数集合のいずれの部分集合にもなっていないとき、またそのときに限り、万能となる。
(1)1を保存する論理関数全体の集合
　(すなわち、F(1,1,...,1)=1となる論理関数Fの集合)
(2)0を保存する論理関数全体の集合
　(すなわち、F(0,0,...,0)=0となる論理関数Fの集合)
(3)自己双対論理関数全体の集合
　(すなわち、F(not x1, not x2, ... , not xk) = not F(x1,x2,...,xk)となる論理関数Fの集合)
(4)単調増加論理関数全体の集合
　(すなわち、a1<=b1,a2<=b2,...,ak<=bkならばF(a1,a2,...,ak)<=F(b1,b2,...,bk)となる論理関数Fの集合)
(5)線形論理関数全体の集合
　(すなわち、F(x1,x2,...,xk)=a0#a1x1#a2x2#...#akxkと表せる論理関数Fの集合。ここでaiは0或いは1、#はXOR、ajxjはajとxjの論理積(AND)で、ANDの方がXORより優先度が高いとする。)
(定理終)

この定理から極小な万能論理関数集合は他にもいろいろとあることが分かります。たとえば、{OR, IFF, F}、{AND, XOR, T}など(IFFは同値、Fは恒偽、Tは恒真)。

参考文献:「論理設計―スイッチング回路理論」(笹尾勤著、近代科学社)、他

補足

(1)yuragifuu様の謙虚な御姿勢に感銘を受けた
(2)同じ疑問を抱いた人に私が投稿した「お礼」の内容を参考にしてほしい

以上2点の理由からこの回答にポイントをつけさせていただきます。

回答No.2

yuragifuu

（返答に対して）
失礼しました　（はるか昔ですが）40年ほど前　電卓を作りたくて　当時は　LSI　はおろか　MSI　SSI　もなく　HTL（IC　SSI？　）レベルの頃で　2進十進変換回路さえも　単純なロジックで構成しなければならないときでした　私はその頃　そのために論理回路をかじり　ブール代数もその関連でちょこっと理解した程度でした　そのため　私の中では　論理回路＝ブール代数みたいな等式ができており　今回の回答もそれで簡単に考えてしまいました　実際のブール代数は集合の概念など理解しないといけないし　かなり難しそうですね　集合論に関しては私はまるっきりわかりません　論理回路はブール代数を使って表現できるというだけで（ブール代数は論理回路を内包する？）論理回路は　上記の基本ゲートの組み合わせで全てを記述できますが　確かに　期待された回答とそぐわないものになっていたかもしれません　失礼しました

お礼

yuragifuu様　再度の書き込みをありがとうございます。

論理回路はブール代数を用いて論理演算を行う電気回路
(デジタル回路、スイッチング回路)ですから(Wikipediaより)、
論理回路の動作を論じる上で「論理回路=ブール代数」と
考えるのは自然(それで問題は生じない)なことだと思います。
ですが、「論理回路=ブール代数」と考えることがyuragifuu
様が回答No.1で書かれたような内容に結びつくというのは
私にはまったく理解できません。

ちなみに、本題とは関係ないことですが、日本語の文章を
書かれる際は句読点を用いられた方が読者にとってはありが
たいと思います。

質問者、年少(私はまだ40年生きておりませんので)の立場で
ありながらズケズケと書いてしまいましたが、ご容赦いただ
ければ幸いです。

それでは失礼いたします。

回答No.1

yuragifuu

(A)は　論理回路は（1)から(4)の組み合わせで表現できると言っている　　　　のです　　もし　それらで表現できない回路があれば　それが　　　　答えになります　
　　　　（その論理を組み立てるのに必要な　上の4種以外の基本的な　　　　　素子が必要になるはずですが　現在のところ　4種で表現で　　　　　きてしまいます）＝存在しません　
(B)は　例えば｛XOR｝なら　NOT　と　OR　の組み合わせですね
　　　つまり　XOR　が万能性を持たないというよりは　基本の　NOTと
　　　OR　の組み合わせであるというだけです
　　　以下　想定されるゲートは　基本の４種で全て表現できてします　　　ので　万能性を持たないことを証明できるのではなく　必要がな　　　いのです

お礼

yuragifuu様、書き込みをありがとうございます。
ただ、私の文章が拙かったようで質問の意図が伝わらなかった
ようなのが残念です。

>論理回路は（1)から(4)の組み合わせで表現できると言っている
>のです
(1)～(4)の"いずれか一つだけで"万能(=任意のブール関数を表現
可能)です。

>現在のところ4種で表現できてしまいます＝存在しません
現在のところ(1)～(4)(のいずれか一つ)で任意のブール関数が
表現できるからといって、他にも万能性を持つゲートの組み合
わせが他に存在しないことの証明にはならないと思います。

>XORが万能性を持たないというよりは基本のNOTとORの組み合わせ
>であるというだけです
申し訳ありませんがどういうことを意図された文なのか理解
できません(ちなみに(当然ながら)XORは{AND, NOT}でも{NOR}
でも{NAND}でも表現できるわけですが)

>想定されるゲートは基本の４種で全て表現できてしますので
>万能性を持たないことを証明できるのではなく必要がないのです
私は学問的興味から(B)の答えを知りたいと思っています。

どうもありがとうございました。