最近独学で論理回路を勉強している者です。
ある本に以下のゲート(素子)の組み合わせは万能(任意のブール
関数を表現できる)であるとあったのですが、
(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ベストアンサー
- 回答日時:
(ご指摘ありがとう^^)
内容については、全く、不勉強の限りでそうかもしれません。 重ね重ね失礼しました。
また 句読点など、これから注意していこうと思っています。 ありがとうございました。
これからも、皆さんの回答など参考にさせて貰おうと楽しみにしています。
この回答への補足
(1)yuragifuu様の謙虚な御姿勢に感銘を受けた
(2)同じ疑問を抱いた人に私が投稿した「お礼」の内容を参考にしてほしい
以上2点の理由からこの回答にポイントをつけさせていただきます。
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は恒真)。
参考文献:「論理設計―スイッチング回路理論」(笹尾勤著、近代科学社)、他
No.2
- 回答日時:
(返答に対して)
失礼しました (はるか昔ですが)40年ほど前 電卓を作りたくて 当時は LSI はおろか MSI SSI もなく HTL(IC SSI? )レベルの頃で 2進十進変換回路さえも 単純なロジックで構成しなければならないときでした 私はその頃 そのために論理回路をかじり ブール代数もその関連でちょこっと理解した程度でした そのため 私の中では 論理回路=ブール代数みたいな等式ができており 今回の回答もそれで簡単に考えてしまいました 実際のブール代数は集合の概念など理解しないといけないし かなり難しそうですね 集合論に関しては私はまるっきりわかりません 論理回路はブール代数を使って表現できるというだけで(ブール代数は論理回路を内包する?)論理回路は 上記の基本ゲートの組み合わせで全てを記述できますが 確かに 期待された回答とそぐわないものになっていたかもしれません 失礼しました
yuragifuu様 再度の書き込みをありがとうございます。
論理回路はブール代数を用いて論理演算を行う電気回路
(デジタル回路、スイッチング回路)ですから(Wikipediaより)、
論理回路の動作を論じる上で「論理回路=ブール代数」と
考えるのは自然(それで問題は生じない)なことだと思います。
ですが、「論理回路=ブール代数」と考えることがyuragifuu
様が回答No.1で書かれたような内容に結びつくというのは
私にはまったく理解できません。
ちなみに、本題とは関係ないことですが、日本語の文章を
書かれる際は句読点を用いられた方が読者にとってはありが
たいと思います。
質問者、年少(私はまだ40年生きておりませんので)の立場で
ありながらズケズケと書いてしまいましたが、ご容赦いただ
ければ幸いです。
それでは失礼いたします。
No.1
- 回答日時:
(A)は 論理回路は(1)から(4)の組み合わせで表現できると言っている のです もし それらで表現できない回路があれば それが 答えになります
(その論理を組み立てるのに必要な 上の4種以外の基本的な 素子が必要になるはずですが 現在のところ 4種で表現で きてしまいます)=存在しません
(B)は 例えば{XOR}なら NOT と OR の組み合わせですね
つまり XOR が万能性を持たないというよりは 基本の NOTと
OR の組み合わせであるというだけです
以下 想定されるゲートは 基本の4種で全て表現できてします ので 万能性を持たないことを証明できるのではなく 必要がな いのです
yuragifuu様、書き込みをありがとうございます。
ただ、私の文章が拙かったようで質問の意図が伝わらなかった
ようなのが残念です。
>論理回路は(1)から(4)の組み合わせで表現できると言っている
>のです
(1)~(4)の"いずれか一つだけで"万能(=任意のブール関数を表現
可能)です。
>現在のところ4種で表現できてしまいます=存在しません
現在のところ(1)~(4)(のいずれか一つ)で任意のブール関数が
表現できるからといって、他にも万能性を持つゲートの組み合
わせが他に存在しないことの証明にはならないと思います。
>XORが万能性を持たないというよりは基本のNOTとORの組み合わせ
>であるというだけです
申し訳ありませんがどういうことを意図された文なのか理解
できません(ちなみに(当然ながら)XORは{AND, NOT}でも{NOR}
でも{NAND}でも表現できるわけですが)
>想定されるゲートは基本の4種で全て表現できてしますので
>万能性を持たないことを証明できるのではなく必要がないのです
私は学問的興味から(B)の答えを知りたいと思っています。
どうもありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(形式科学) 【ハードウェア 論理ゲート 論理回路】 6入力のOR回路には複数構成が考えられるそうなのですが、どの 1 2023/06/22 09:25
- その他(コンピューター・テクノロジー) 量子コンピュータの動作原理がわかりません。同じビットが、1でも0でも有って良いだろうか? 3 2023/02/04 03:20
- 英語 提示文は、全否定か部分否定のいずれなのか等について 1 2023/04/16 17:58
- 英語 提示した名言について(並列表現の文法規則) 4 2023/06/02 09:41
- 英語 提示した名言の解釈等について 9 2022/04/21 09:23
- 英語 "either A or not"が「~という問題に過ぎない」という意味になる根拠について 4 2023/07/03 15:34
- 政治 関東で相次ぐ「強盗事件」対策はアメリカに学ぶべきですよね? 4 2023/01/21 11:39
- 分譲マンション 古い分譲マンション・管理組合の初、理事長(女性)です。不明点①~⑥についてご意見をお願いします。 7 2022/11/07 13:03
- 数学 無理数の数字の組み合わせ。無限の意味について 5 2022/05/28 22:53
- 数学 回答の意味について 4 2023/07/11 11:19
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
勉強のことをかんがえる
-
ミラー指数:面間隔bを求める公...
-
中2です笑 証明の問題がどうし...
-
理論と原理の違い
-
計算式について教えてください。
-
NOxの問題で・・・
-
認定書と証明書の違い
-
validation cohort develpmen...
-
証明の終わりは、「よって題意...
-
数学の逆裏対偶の、「裏」と、...
-
何で√2はm/nと表せるのですか?...
-
合同式でもOKですか nが3の倍数...
-
死後の世界はない[無]になる...
-
運動方程式ma=Fは証明できますか?
-
遅延証明書って駅員の方が時間...
-
いわれなき差別を受けてます。...
-
素数の謎を解くことは 万物の理...
-
背理法ってどんな意味?
-
実在とは何か
-
2つの奇数の和は偶数になる。そ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
中2です笑 証明の問題がどうし...
-
過去質『すべての自然数とすべ...
-
理論と原理の違い
-
計算式について教えてください。
-
ミラー指数:面間隔bを求める公...
-
キノの旅「・・・・あなたが正...
-
天国や、極楽浄土は、あるので...
-
証明の終わりは、「よって題意...
-
在学証明書ってなんですか?
-
日本で神道と仏教はどちらが先...
-
東京都小池百合子知事の学歴詐...
-
血統書付きの種、という表現は...
-
認定書と証明書の違い
-
原理と理論の違いを教えてくだ...
-
二項定理を用いて、つぎのこと...
-
証明書の開封無効
-
数学の記述の書き方 数学でaとb...
-
数学の逆裏対偶の、「裏」と、...
-
奨学金の保証人、別生計の意味は?
-
窒息について
おすすめ情報