Download presentation
Presentation is loading. Please wait.
1
2. 論理ゲート と ブール代数 五島 正裕
2
今日の内容 前回の復習 アナログとディジタル 本論 論理ゲート ブール代数 今日のまとめ
3
前回の復習
4
アナログ と ディジタル 情報処理の過程において， 媒体の持つ物理量 と それの表す値 との 写像の方式 アナログ：連続
連続的なデータ ⇔ 媒体の連続的な状態 ディジタル：離散 離散的なデータ ⇔ 媒体の離散的な状態
5
物理量 と 値 の 写像 閾値 値 値 3 2 1 O O 物理量 物理量 アナログ ディジタル
6
アナログ，ディジタル と 信号劣化 劣化がなければ（S/N 比∞）… アナログがよい アナログ： 情報量∞ ディジタル： 量子化誤差がある
8b（256階調）で 0.4%（≒ 人間の識別限界） ビット数を増やせば，誤差は減る
7
アナログ，ディジタル と 信号劣化 劣化があるので… ディジタルがよい アナログ： 決して元に戻らない ディジタル：
閾値未満のノイズなら，完全に元に戻る 2値なら，10～20％ くらいなら耐えられる ただし，それでも誤るとアナログより致命的になり得る
8
ディジタル の メリット（まとめ） 記録/伝送 ノイズによって誤りが発生しにくい コピーや経年によって情報が劣化しにくい 再現性が高い 処理
ディジタル式のコンピュータとの親和性が高い プログラミング可能 圧縮が容易 誤り訂正符号などによる誤り訂正が可能 …
9
ディジタル回路 と 論理回路 ディジタル回路 物理的 通常は，Low/High の2つの物理状態を扱う 通常は，電子回路で作る 論理回路
抽象的，モデル 真理値の 0/1，false/true を扱う ディジタル回路で作る
10
論理ゲート と ブール代数
11
今日の目標 すべての論理回路は，AND，OR，NOT の組み合わせでできる．
12
論理ゲート AND OR NOT （論理積） （論理和） （論理否定） z = a∙b z = a + b z = a z = ¬ a a
MIL記号 MIL symbol a a z z a z b b 論理式 logic expression z = a∙b z = a + b z = a z = ¬ a a b z 1 a b z 1 a z 1 真理値表 truth table
13
論理ゲート NAND NOR buffer? z = a∙b z = a + b z = a a a z z a z b b MIL記号
MIL symbol a a z z a z b b 論理式 logic expression z = a∙b z = a + b z = a a b z 1 a b z 1 a z 1 真理値表 truth table
14
論理ゲート XOR (EOR) XNOR (EQ) （排他的論理和） z = a b z = a b a a z z b b MIL記号
MIL symbol a a z z b b 論理式 logic expression z = a b z = a b a b z 1 a b z 1 真理値表 truth table
15
余談 MIL 記号 MIL : 米国軍用規格（Military Standard） JIS の論理記号もある（が，誰も使わない）
OR と XOR OR : （包含的）論理和 (inclusive-OR) XOR : 排他的 論理和 (exclusive-OR) 日常の「または」は，どっち？ 1年以下の懲役 または 100万円以下の罰金 x = 0, 1
16
組み合わせ回路 (Combinational Circuit)
z c d z = a∙b + c∙d
17
ブール代数
18
ブール代数 ブール代数 (Boolean Algebra) George Bool 論理計算のために考案 Claude Shannon
論理回路に応用
19
ブール代数の公理系 変数（ブール変数）の値 0 または 1 論理和
0 + 0 = 0, = 1, = 0, = 1 論理積 0 ∙ 0 = 0, 0 ∙ 1 = 1, 1 ∙ 0 = 1, 1 ∙ 1 = 1
20
論理関数 f : (i1, i2, …, in) → o (i1, i2, …, in, o : ブール変数） 2入力論理関数：先ほどの AND，OR 等 1入力論理関数：NOT ，BUF 等 n入力の論理関数は 22n とおり 入力は 2n とおり そのそれぞれに，0 または 1 を指定できる i1 i2 … in o 0/1 1 2n
21
すべての1，2入力論理関数 すべての1入力論理関数 すべての2入力論理関数 21 = 2 221 = 4 22 = 4 222 = 16
i1 o0 o1 o2 o3 1 すべての1入力論理関数 21 = 2 221 = 4 すべての2入力論理関数 i2 i1 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15 1 22 = 4 222 = 16
22
ブール代数の定理 対合律 ¬(¬x) = x 補元律 x∙(¬x) = 0 x + (¬x) = 1 べき等律 x∙x = x,
交換律 x∙y = y∙x x + y = y + x 結合律 (x∙y)∙z = x∙(y∙z) (x + y) + z = x + (y + z) 分配律 x + y∙z = (x + y)∙(x + z) x∙(y + z) = x∙y + x∙z 吸収律 x∙(x + y) = x x + x∙y = x ド・モルガンの定理 ¬(x∙y) = ¬x + ¬y ¬(x + y) = (¬x)∙(¬y)
23
ド・モルガンの法則 ¬(x∙y) = ¬x + ¬y ¬(x + y) = (¬x)∙(¬y)
24
完全性（Completeness，完備性）
完全集合 (Complete Set) 論理関数の集合で， その要素の組み合わせによって，すべての論理関数を表現できる 完全集合の例 {AND, OR, NOT} {AND, NOT} {OR, NOT} {NAND} {NOR}
25
完全性の証明 {AND, OR, NOT} 数学的帰納法： 1入力の論理関数は {AND, OR, NOT} の組合せで表現できる
n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して，(n + 1) 入力の関数が表現できることをいう
26
完全性の証明 {AND, OR, NOT} o0 = 0 o1 = i1 o2 = ¬i1 o3 = 1 1
1 o0 = 0 o1 = i1 o2 = ¬i1 o3 = 1 1
27
すべての1，2入力論理関数 すべての1入力論理関数 すべての2入力論理関数 21 = 2 221 = 4 22 = 4 222 = 16
i1 o0 o1 o2 o3 1 すべての1入力論理関数 21 = 2 221 = 4 すべての2入力論理関数 i2 i1 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15 1 22 = 4 222 = 16
28
完全性の証明 {AND, OR, NOT} f0 f1 i1 i1 1 i2 = 0
2 入力の関数が表現できることをいう f0 i1 f1 i1 1 i2 = 0
29
完全性の証明 {AND, OR, NOT} f0 f1 i1 i1 1 i2 = 1
2 入力の関数が表現できることをいう f0 i1 f1 i1 1 i2 = 1
30
完全性の証明 {AND, OR, NOT} f = ¬in+1∙f0 + in+1∙f1 f0 f1
n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して， (n + 1) 入力の関数が表現できることをいう in+1 in … i2 i1 o 1 f0 f = ¬in+1∙f0 + in+1∙f1 f1
31
完全性の証明 {AND, OR, NOT} f0 f1 i1 i2 in i1 i2 in in+1
n 入力の関数を {AND, OR, NOT} の組合せで表現できたと仮定して， (n + 1) 入力の関数が表現できることをいう i1 f0 i2 in i1 f1 i2 in in+1
32
完全性の証明 一般の場合 {AND, OR, NOT} が作れることを言う ex) {NAND} AND OR NOT
33
今日のまとめ
34
ブール代数 完全集合： すべての論理関数が作れる 完全集合の例： ｛AND，OR，NOT｝ ｛NAND}
完全集合をディジタル回路で作ればよい！ 普通は，｛NAND，NOR，NOT｝
35
来週以降の予定 11/ 3 文化の日 11/10 組み合わせ回路の最小化
Similar presentations
