最近独学で論理回路を勉強している者です。
ある本に以下のゲート(素子)の組み合わせは万能(任意のブール
関数を表現できる)であるとあったのですが、
(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で質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
中2です笑 証明の問題がどうし...
-
関係と関係性の違いって何ですか?
-
理論と原理の違い
-
計算式について教えてください。
-
証明の終わりは、「よって題意...
-
原理と理論の違いを教えてくだ...
-
認定書と証明書の違い
-
太陽光線が平行であることの証明
-
視姦は違法ですか?合法ですか?
-
証明書の開封無効
-
x>0かつy>0の否定 わかる方教え...
-
validation cohort develpmen...
-
運動方程式ma=Fは証明できますか?
-
数学の質問です
-
走れメロス
-
数IIの問題です (1+x)^n(x+1)^n...
-
在学証明書ってなんですか?
-
「わたしの霊は、人のうちに永...
-
命題と証明の問題です。
-
仏検準1級をフランス語でいうと
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
中2です笑 証明の問題がどうし...
-
自己の存在を自己証明できますか?
-
計算式について教えてください。
-
関係と関係性の違いって何ですか?
-
ミラー指数:面間隔bを求める公...
-
認定書と証明書の違い
-
文書に於ける、『以上』『以下...
-
原理と理論の違いを教えてくだ...
-
理論と原理の違い
-
数学の逆裏対偶の、「裏」と、...
-
日本で神道と仏教はどちらが先...
-
√(平方根)は身の回りでどのよう...
-
証明の終わりは、「よって題意...
-
時空乱流って本当にありますか?
-
運動方程式ma=Fは証明できますか?
-
進化論は事実ですか?論だから...
-
整数m,nについて 「m2乗+n...
-
ma=Fは数学で証明されていない?
-
証明書の開封無効
-
小学生でジュニアシートやチャ...
おすすめ情報