More Related Content
What's hot (20)
Viewers also liked (14)
Similar to kagami_comput2015_8 (20)
![[Basic 2] 計算機の構成 / プログラム実行の仕組み](https://cdn.slidesharecdn.com/ss_thumbnails/basic-02-180219142306-thumbnail.jpg?width=560&fit=bounds)
![[Basic 1] ブロックチェーンと計算機科学 / ブール代数 / 情報理論](https://cdn.slidesharecdn.com/ss_thumbnails/basic-01-180219093601-thumbnail.jpg?width=560&fit=bounds)
More from swkagami (15)
kagami_comput2015_8
- 1. 東北大学 工学部 機械知能?航空工学科 2015年度 5セメスター?クラスD 計算機工学 大学院情報科学研究科 鏡 慎吾 http://www.ic.is.tohoku.ac.jp/~swk/lecture/ 8. ブール代数と論理回路 (教科書2章)
- 2. 2鏡 慎吾 (東北大学): 計算機工学 2015 (8) ブール代数 集合 { 0, 1 } の上の演算 AND, OR, NOT からなる数学的体系 何のため? ? ある演算をどのような回路で実現すればよいのか? ? どうすれば回路が小さくなるのか? ? どうすれば回路が速く動くのか?
- 3. 3鏡 慎吾 (東北大学): 計算機工学 2015 (8) 復習: 真理値表とゲート記号 A B A?B 0 0 0 0 1 0 1 0 0 1 1 1 A B A?B A B A+B 0 0 0 0 1 1 1 0 1 1 1 1 A A 0 1 1 0 A B A+B A A 真理値表 ゲート記号
- 4. 4鏡 慎吾 (東北大学): 計算機工学 2015 (8) 論理関数と論理式 ? 論理関数 ? いくつかの論理値を引数として受け取り，論理値を返 す関数 ? f : {0, 1}n → { 0, 1 } ? 真理値表と 1 対 1 対応 ? 論理式 ? 論理値を持つ変数（論理変数）と論理値定数（つまり 0 または 1） に対して，AND, OR, NOT 演算を何度か適 用して得られる式 ? 演算子の優先順位は NOT → AND → OR の順 ? ゲート記号による論理回路図と 1 対 1 対応 ? 論理式は一つの論理関数を定める ? しかし，論理関数は論理式を一意に定めない
- 5. 5鏡 慎吾 (東北大学): 計算機工学 2015 (8) 論理式(論理回路)から真理値表へ: 例1 論理式 f(A, B) = A + B 真理値表 A B A+B 0 0 1 0 1 0 1 0 1 1 1 1 論理回路 A A+B ? 入力の組み合わせは高々有限個なの で，地道に評価していけばよい ? 慣れてくると，まとめて値を定められる 場合がある．例えばこのページの例で は，A = 1 なら OR ゲートの作用で結果 は必ず 1 になることがわかる B
- 6. 6鏡 慎吾 (東北大学): 計算機工学 2015 (8) 例2 論理式 f(A, B) = A + A · B 真理値表 (cf. 前ページ) 論理回路 A ? 同じ論理関数を実現する論理式(論 理回路)は複数ある ? どうせ同じなら，できるだけ小さくて 速い回路で実現したい A B A+A · B 0 0 1 0 1 0 1 0 1 1 1 1 B A + A · B
- 7. 7鏡 慎吾 (東北大学): 計算機工学 2015 (8) 真理値表から論理式へ XOR A B A ⊕ B 0 0 0 0 1 1 1 0 1 1 1 0 A B A ⊕ B = A?B + A?B ? 真理値表から出力が 1 の行を抜き出し，それぞれについて ? 入力が 1 の変数はそのまま，0 の変数は否定 ? それら全変数の論理積を取る ? それらすべての項の論理和を取る ? 後述する「主加法標準形」が得られる A B A B (A = 0, B = 1 のときのみ1) (A = 1, B = 0 のときのみ1)
- 8. 8鏡 慎吾 (東北大学): 計算機工学 2015 (8) 例3 A B C f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 ちょっと回路が複雑そうだ．もっと「簡 単な」回路（簡単な論理式）で表せな いだろうか? 3入力多数決関数 f(A, B, C)
- 9. 9鏡 慎吾 (東北大学): 計算機工学 2015 (8) ブール代数の公式 冪等則 単位元の存在 零元の存在 交換則 二重否定 相補則 分配則 ド?モルガン則 双対性
- 10. 10鏡 慎吾 (東北大学): 計算機工学 2015 (8) 各公式の理解 ? 相補則までは AND, OR, NOTの性質からすぐわかる ? 分配則はスイッチング回路図で考えるとよい b a c a a b c a a ab c b c ? ド?モルガン則はよく知られている通り （ベン図で考えるとよい） a b
- 11. 11鏡 慎吾 (東北大学): 計算機工学 2015 (8) ? 双対性: ? ある命題における AND と OR，および 1 と 0 をそれぞれ入 れ替えたものを，その命題の双対 (dual) と呼ぶ ? 正しい命題の双対は常に正しい．なぜならば ? AND と OR の真理値表は互いの 0 と 1 を入れ替えたも のであり，NOT の真理値表は 0 と 1 を入れ替えても変わ らない．あらゆる論理式はAND, OR, NOTで表せるので， 上記の入れ替えによって，命題の真偽は保存される ? （別の説明） ブール代数の定理（正しいと証明できる命 題）は，すべて前々ページの公式（の一部: ハンチントンの 公理）から証明できる．ある定理の証明に用いた公式をす べて双対に置き換えれば，元の定理の双対が証明できる
- 12. 12鏡 慎吾 (東北大学): 計算機工学 2015 (8) 公式の適用例 相補則 単位元 単位元 分配則 こんなのどうやって思いつくのか? → 「カルノー図」を勉強するまで待とう 冪等則 分配則 相補則 単位元 (例2) (例1) (例3) 零元 分配則
- 13. 13鏡 慎吾 (東北大学): 計算機工学 2015 (8) 論理関数の標準形 ? ある論理関数を論理式で表す方法は無数にあるため，例え ば2つの論理式を直接見比べても，それらが論理関数として 等価かどうかは判断できない ? 論理関数を一意に表すことができる「標準形」があると便利 である ? 特に，真理値表と関係の深い標準形として，主加法標準形と 主乗法標準形が挙げられる
- 14. 14鏡 慎吾 (東北大学): 計算機工学 2015 (8) 主加法標準形 ? リテラル ある入力変数，またはその否定 ? 基本積 リテラル，または2つ以上のリテラルの積で， 同じ入力変数を2度以上含まないもの ? 最小項 基本積のうち，すべての入力変数を含むも の ? 主加法標準形 論理関数を最小項の和で表した形式 A B C f 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 最小項 A B C に対応する行
- 15. 15鏡 慎吾 (東北大学): 計算機工学 2015 (8) 主加法標準形の作り方 真理値表から主加法標準形へ ? 1になる行の最小項を並べて論理和を取る （つまり，先に学んだ「真理値表→論理式」の変換方法で 得られるのは，主加法標準形そのものだった） 任意の論理式から主加法標準形へ ? 分配則などを使って展開して積和形へ ? 最小項でない積項に対して，その積項に含まれないすべ てのリテラル xi について，(xi + xi) を乗ずる ? さらに展開して，冗長な項を除去
- 16. 16鏡 慎吾 (東北大学): 計算機工学 2015 (8) 例
- 17. 17鏡 慎吾 (東北大学): 計算機工学 2015 (8) 主乗法標準形 ? 基本和 リテラル，または2つ以上のリテラルの 和で，同じ入力変数を2度以上含まな いもの ? 最大項 基本和のうち，すべての入力変数を含 むもの ? 主乗法標準形 論理関数を最大項の積で表した形式 A B C f 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 最大項 A + B + C に対応する行の集合
- 18. 18鏡 慎吾 (東北大学): 計算機工学 2015 (8) 参考: 主乗法標準形の作り方 真理値表から主乗法標準形 ? 0になる行の最小項を並べて論理和を取り，ド?モルガン 則を適用 (つまり，主加法標準形を作ることさえできれば，主乗法標準形へは 変換できる) 任意の論理式から主乗法標準形へ ? 分配則などを使って展開して和積形へ ? 最大項でない和項に対して，その和項に含まれないすべ てのリテラル xi について，(xi xi) を加える ? さらに展開して，冗長な項を除去 （分配のしかたに慣れないと難しいかも知れない）
- 19. 19鏡 慎吾 (東北大学): 計算機工学 2015 (8) 練習問題 右表の f(A, B, C) を適当な論理 式で表せ．(表したあと，A,B,Cに 各値を代入して自分で検算して みるとよい) A B C f 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 (1) (2) 4入力の論理関数 g(x4, x3, x2, x1) を， 2進数 x4x3x2x1 が 3の倍数と (10進 表示で) 3のつく数のときだけ 1 にな る関数とする．ただし 0 は3の倍数に 含まないものとする．論理関数gの真 理値表を書き，それに基づいてgを適 当な論理式で表せ．
- 20. 20鏡 慎吾 (東北大学): 計算機工学 2015 (8) 解答例 x4 x3 x2 x1 g 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 (2) 真理値表は右の通り．論理式の表示例 は (1) 論理式で表すと，例えば その他，正解は無数に存在する．
- 21. 21鏡 慎吾 (東北大学): 計算機工学 2015 (8) 練習問題 a, b, c の 3人の男がいる．そのうち一人以上は正直者で，一人 以上は嘘つきである．正直者は常に本当のことを言うが，嘘つき の言うことは本当かも知れないし嘘かも知れない．彼らは言う． a 「bは正直者だ」 b 「cは正直者だ」 c 「この中に正直者は一人しかいない」 a, b, c が正直者であるときに 1 になる論理変数をそれぞれ A, B, C とおく．a の発言からは「A = 1 かつ B = 1 であるか，または， A = 0 でなくてはならない」ことが読み取れる．つまり という式（が 1 であること）によって a の発言が表される． (1) 同様に b, c の発言を論理式で表し，それらの論理積を 取ることですべての条件を表す一つの論理式を導け． (2) (1) の論理式を主加法標準形にせよ． (3) a, b, c が正直者か嘘つきかを決定せよ．
- 22. 22鏡 慎吾 (東北大学): 計算機工学 2015 (8) 解答例 b: c: (1) (2) (3) 正直者は一人以上いなくてはならないので，c が正直者である．
- 23. 23鏡 慎吾 (東北大学): 計算機工学 2015 (8) 例題（おまけ） 天国と地獄の分かれ道に門番が立っている．門番は天国または 地獄のどちらから派遣されているが，どちらかはわからない．門 番には「はい」または「いいえ」で答えることのできる質問を一つ だけすることができる．ただし，天国からきた門番は本当の答え を教えてくれるが，地獄から来た門番は必ず嘘をつく．どのような 質問をすればよいか． (1) X を「左側の道が天国のときに 1，さもなくば 0」，Y を「門 番が天国から来たなら 1，さもなくば 0」 である論理変数と する．門番にする質問を論理関数 f(X, Y)，門番から返る答 え g(X, Y) とする．ただし「はい」を論理値 1 に対応させる とする．f(X, Y) を g(X, Y), X, Y を使った論理式で表せ． (2) g(X, Y) = X となるような f(X, Y) を求めたい．そのような f(X, Y) を論理式で表せ．これを日本語ではどう質問すれば よいか．
- 24. 24鏡 慎吾 (東北大学): 計算機工学 2015 (8) 解答例 よって質問すべき内容は: 「左の道は天国行きであってかつあなたは天国から来た」 かまたは「左の道は地獄行きであってかつあなたは地獄 から来た」のどちらかですか? 同じことだが，もう少しスマートにしたければ X = Y かどうか聞 いてもよい: あなたは左の道から来ましたか? (1) (2)