More Related Content
What's hot (20)
Similar to kagamicomput201709 (17)
![[Basic 1] ブロックチェーンと計算機科学 / ブール代数 / 情報理論](https://cdn.slidesharecdn.com/ss_thumbnails/basic-01-180219093601-thumbnail.jpg?width=560&fit=bounds)
More from swkagami (16)
Recently uploaded (15)
kagamicomput201709
- 1. 東北大学 工学部 機械知能?航空工学科 2017年度 5セメスター?クラスC3 D1 D2 D3 計算機工学 大学院情報科学研究科 鏡 慎吾 http://www.ic.is.tohoku.ac.jp/~swk/lecture/ 9. 論理式の簡単化 (教科書3.1～3.3節)
- 2. 2( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 論理式（論理回路）の簡単化 x1 x2 x1 x2 このような組をどうやって見つけるか?
- 3. 3( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 カルノー図 (2入力の場合) x2 0 1 x1 0 1 0 1 1 1 ? 1つ1つのマス目（セル）が最小項を表す ? 論理関数に含まれる最小項のセルには1を，含まれな いセルには0を書き込む（あるいは空白のままとする） 1になる3つのセルの和を書き下すと 主加法標準形になる → 真理値表を 2 次元に並べ替える
- 4. 4( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 カルノー図の特徴 x2 0 1 x1 0 0 1 1 0 0 x2 0 1 x1 0 0 1 1 0 1 x2 0 1 x1 0 1 1 1 1 1 隣接する 2n 個のセルをまとめることが変数の削除に対応する
- 5. 5( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 カルノー図による簡単化 ? 2m 個のセルからなる長方形をルー プと呼ぶ → 基本積に対応 ? できるだけ少なく大きなループによ り，すべての1を覆う ? 少ないループ → 少ない項 ? 大きなループ → 少ないリテラル ? ダブって覆ってもよい セルを1個ずつ取り上げて和を取る 代わりに，隣接する1をまとめた積 項を取り上げてその和を取っても同 じ関数を表現できる x2 0 1 x1 0 1 0 1 1 1
- 6. 6( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 例: 3入力の場合 3入力多数決関数 x1 x2 00 01 11 10 x3 0 0 0 1 0 1 0 1 1 1 この並び方がミソ いずれの基本積もうまく長方形 で表せるようになっている
- 7. 7( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 例 x1 x2 00 01 11 10 x3 0 1 0 0 1 1 1 0 1 1 上下左右も隣接している! x1 x2 00 01 11 10 x3 0 1 0 0 1 1 1 0 1 1
- 8. 8( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 簡単化の手順の（一応の）まとめ 1. 1を覆うループのうち，他のループに包含されないもの（主 項ループ）のみを列挙する ? 隣接するループを結合できないか? と考えるとよい 2. ひとつの主項ループでしか覆われていない1がある場合， そのループ（必須主項ループ）は必ず残す 3. 必須主項ループで覆われていない1がある場合，できるだ け少ない主項ループで覆う ? このとき複数の選び方がある場合は，できるだけ大き なループの組合せを選ぶ （結局，完全に自動化できる手順ではない）
- 9. 9( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 例 x1 x2 00 01 11 10 x3x4 00 1 1 01 1 1 11 1 1 1 10 1 1 1 ?入力変数が増えるとだんだん難しくなってくる ?上下左右の隣接に注意 （特に四隅が気づきにくい） ?一般に，答えは一通りとは限らない(see 教科書例題3.2) x1 x2 00 01 11 10 x3x4 00 1 1 01 1 1 11 1 1 1 10 1 1 1 主項ループ (青線が必須主項)
- 10. 10( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 ドントケア項のある場合 x1 x2 00 01 11 10 x3 0 * 0 1 0 1 * * 1 1 最小項のうち一部に「1になっても0になってもよい」ものがある 場合（その項に対応する入力を考える必要がない場合） 冗長項 (don’t care term)， 組合せ禁止項などと呼び， × や * などで表す ループはできるだけ少なく，大きくしたいので， ? 既存のループを大きくできるなら積極的に使う ? 新たにループを作らないといけないなら無視する
- 11. 11( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 例: 7セグメントLED http://ja.wikipedia.org/wiki/%E7%94% BB%E5%83%8F:7segdisplay.jpg d3 d2 d1 d0 a b c d e f g a b c g LED点灯回路 (例: 74HC4511) ? 出力 e を d3, d2, d1, d0 の論理式で表し，簡単化せよ 2進数入力 (binary coded decimal, BCD)
- 12. 12( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 出力 e を簡単化する例 d1d0 00 01 11 10 d3d2 00 1 1 01 1 11 * * * * 10 1 * * d3 d2 d1 d0 e 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 * 1 0 1 1 * 1 1 0 0 * 1 1 0 1 * 1 1 1 0 * 1 1 1 1 * 0 1 2 3 4 5 6 7 8 9 don’t care
- 13. 13( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 参考: 実際の論理式簡単化 ? カルノー図による方法は，5入力以上になるとあまりうれしくな い（頑張っても6入力程度）．自動化に向いていない → より自動化に適した方法: e.g.: クワイン?マクラスキー法 ではそれで十分か? ? 複雑になると難しい （記憶容量，計算時間が大きすぎる） ? 多数の出力がある場合，さらに簡単な組み合わせがあり得る ? 積和形よりより回路があるかも知れない → 組合せ最適化問題の典型であり，厳密に解くのは難しい． ヒューリスティック（発見的）な解法が用いられる
- 14. 14( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 参考: 用語の意味をカルノー図で考える x1 x2 00 01 11 10 x3x4 00 01 11 1 10 x1 x2 00 01 11 10 x3x4 00 0 01 11 10 最小項: x1 x2 x3 x4 最大項: x1+x2+x3+x4
- 15. 15( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 参考: 用語の意味をカルノー図で考える 主加法標準形 x1 x2 00 01 11 10 x3 x4 00 01 11 1 10 x1 x2 00 01 11 10 x3 x4 00 01 1 11 10 x1 x2 00 01 11 10 x3 x4 00 01 11 10 1 + + + … 主乗法標準形 x1 x2 00 01 11 10 x3 x4 00 01 11 0 10 x1 x2 00 01 11 10 x3 x4 00 01 0 11 10 x1 x2 00 01 11 10 x3 x4 00 01 11 10 0 ? ? ? …
- 16. 16( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 練習問題 (1) カルノー図で表せ (2) できるだけ簡単な積和型の論理式で表せ (3) (2) で求めた論理式を表す論理回路図を示せ．AND, OR, NOT の各ゲートを使用してよい (4) 関数 f に冗長項 (x,y,w) = (0,1,1) を加えた不完全記述 論理関数を f ’ とする．f ’ をできるだけ簡単な積和型の論 理式で表し，論理回路図を示せ．
- 17. 17( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 解答例 x y 00 01 11 10 z w 00 1 1 01 11 1 10 1 1 1 1 x y z w f
- 18. 18( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 解答例 （つづき） x y 00 01 11 10 z w 00 1 1 01 * 11 * 1 10 1 1 1 1 y z w f ’
- 19. 19( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 例題(おまけ) ? 朝まで飲んでいたわけではなくて，晴れていて，落とせない講義がある日 は登校する ? 落とせない講義がなくても，朝まで飲んでいたわけではなくて，晴れてい る日は登校する ? 朝まで飲んでいた日でも，落とせない講義がある日は天気に関わらず登 校する ? 天気が悪くても，落とせない講義がある日で，朝まで飲んでたわけじゃな い場合は登校する ? 上記で挙がった場合以外は休む (1) x1: 朝まで飲んでいた, x2 落とせない講義がある, x3: 晴天である として「A君登校関数」を論理式で表せ． (2) 「A君登校関数」のカルノー図をかき，簡単化せよ． A君はあまり真面目に大学に来ない学生であるが，全く来ないわけ でもない．よく観察してみると以下の法則性があることがわかった:
- 20. 20( ): 2017 (9)鏡 慎吾 東北大学 計算機工学 例題（おまけ） 解答例 x1 x2 x3 + x1 x2 x3 + x1 x2 + x1 x2 x3 (飲) (講) (晴) x2 x3 00 01 11 10 x1 0 1 1 1 1 1 1 カルノー図から，簡単化すると x2 + x1 x3 （つまりA君は，落とせない講義が ある日，または，朝まで飲んで無く てかつ晴れている日は登校する） ? 朝まで飲んでいたわけではなくて，晴れていて，落と せない講義がある日は登校する ? 落とせない講義がなくても，朝まで飲んでいたわけで はなくて，晴れている日は登校する ? 朝まで飲んでいた日でも，落とせない講義がある日は 天気に関わらず登校する ? 天気が悪くても，落とせない講義がある日で，朝まで 飲んでたわけじゃない場合は登校する