东京电机大讲义资料.ppt

論理回路および論理設計2011年度 （第1回） 中島 克人 情報メディア学科nakajima@im.dendai.ac.jp 授業の概要 目的 実世界の問題を論理の世界にマッピングし、論理回路として設計するための基礎知識を学ぶ。また、基本的?代表的な論理回路の幾つかについて理解する。 達成目標 論理回路の基本的概念と設計手法の基礎知識の習得を目指す。 教科書： 柴山潔著 　 「コンピュータサイエンスで学ぶ　論理回路とその設計」（近代科学社） 参考書：特になし 評価方法（目安） （期末試験） ： （出席数等） ＝ 8 ： 2 授業の概要 どんな内容？ 論理代数（論理式） ... （原則） 0 か 1 だけの数学 集合 と 論理代数 集合 と 論理代数 論理代数 と 論理回路 論理代数 と 論理回路 アナログ vs デジタル＝連続 vs 離散 論理＝2値（賛vs否、真vs偽、男vs女、左vs右）の世界 ＝ 1 vs 0 （記号として使用）→ 論理値 ビット＝1つの論理（論理値） 2進数（デジタル値を表現可能） ≠論理＝非数値 ＝2冪の各桁の有り無しを論理で示す数表現 論理代数＝論理を扱う数学 論理関数＝論理の関係を表現する関数 論理回路＝論理関数の電気的実現手段 論理代数 論理定数 .... 1 または 0 （論理値そのもの） 論理変数 .... 1 または 0 を取り得る変数 論理演算記号（論理演算子） 基本は否定（NOT）、論理積（AND）、論理和（OR）の3つ 基本論理演算 定義1.1：否定（NOT） ... X 定義1.2：論理積（AND） ... X?Y 定義1.3：論理和（OR） ... X+Y 基本論理演算の演算順位 定義1.4 優先順位の高いものから順に、 否定（NOT） → 論理積（AND）→ 論理和（OR） 論理式と論理関数 論理式 論理の関係を表す数式 例： X ＋ （ Y ? Z ） 双対 定義1.5： 双対 ある論理式Lで 論理記号 ? （AND） ? ＋ （OR） の入替え 論理定数 0 ? 1 の入替え によって得られる論理式Ldを双対と称する 演算順位と双対 双対性 双対性 ある論理式Lが成立している時、双対な論理式Ldも成立することを「双対性がある」という 定理1.1（双対性） 論理式P,QがP＝Qならば、 Pd＝Qdである ? P＝Qだけを証明すれば、 Pd＝Qdの証明は省略できる 種々の基本定理 （1変数） 定理1.2 X?0＝0 ? X＋1＝1 定理1.3（2値の存在） X?1＝X なるXが存在 ? X＋0＝X なるXが存在 定理1.4（同一則、ベキ等則） X?X＝X ? X＋X＝X X?X???X ＝X ? X＋X＋‥‥＋X ＝X （系1.5） 種々の基本定理（多変数） 定理1.8（交換則） X?Y＝Y?X ? X＋Y＝Y＋X 定理1.9（結合則） （X?Y）?Z＝X?（Y?Z） ? （X＋Y）＋Z＝X＋（Y＋Z） 定理1.10（分配則） X?（Y＋Z）＝（X?Y）＋（X?Z） ? X＋（Y?Z）＝（X＋Y）?（X＋Z） 種々の基本定理（ド?モルガンの定理） 定理1.13（De Morgan の定理） X?Y＝X＋Y ? X＋Y＝ X?Y 種々の基本定理（ド?モルガンと双対） 定理1.16（拡張されたDe Morganの定理） L ＝ f（X1, X1 , X2, X2 ,???Xn, Xn, ? ,＋） ＝ f（X1, X1 , X2, X2 ,???Xn, Xn,＋, ? ） 種々の基本定理（展開定理） 定理1.17（展開定理） Xi?f（X1, ??, Xi, ??,Xn）＝Xi?f（X1, ??, 1, ??,Xn） Xi＋f（X1, ??, Xi, ??,Xn）＝Xi＋f（X1, ??, 0, ??,Xn） 種々の基本定理（展開定理） 種々の基本定理（展開定理） 論理関数の表現（準備） 論理回路および論理設計2011年度 （第2回） 中島 克人 情報メディア学科nakajima@im.dendai.ac.jp 論理関数の表現 定義1.8： リテラル（literal） 論理式を構成する論理変数、または、その否定をリテラルと総称する。 Xのリテラルを X と表記することにする。 X = { X, X } X0 = X, X1 = X ? Xl （l＝0, 1) 論理積項と論理和項 論理積項：複数のリテラルをAN