論理ゲートとブール代数

ブール代数の基礎

3つの基本演算

AND (AND):  Y = A · B    「両方が1の場合のみ1」
OR (OR):    Y = A + B    「どちらかが1なら1」
NOT (NOT):  Y = Ā        「反転」

真理値表

AND          OR           NOT
A B | Y     A B | Y      A | Y
0 0 | 0     0 0 | 0      0 | 1
0 1 | 0     0 1 | 1      1 | 0
1 0 | 0     1 0 | 1
1 1 | 1     1 1 | 1

基本定理

結合法則:  (A·B)·C = A·(B·C)
         (A+B)+C = A+(B+C)
交換法則:  A·B = B·A
         A+B = B+A
分配法則:  A·(B+C) = A·B + A·C

ド・モルガンの定理 (極めて重要!):
  ───
  A·B = Ā + B̄     「ANDの否定 = NOTのOR」
  ───
  A+B = Ā · B̄     「ORの否定 = NOTのAND」

簡約:
  A + Ā = 1
  A · Ā = 0
  A + 1 = 1
  A · 0 = 0
  A + A = A
  A · A = A
  =    (二重否定)
  A = A

基本論理ゲート

記号と式

AND:     A ──┬──
              │  )── Y    Y = A·B
         B ──┴──

OR:      A ──┬──
              │  )── Y    Y = A+B
         B ──┴──

NOT:     A ──▷── Y        Y = Ā

NAND:    A ──┬──
              │  )─○ Y    Y = A·B̄  (AND + NOT)
         B ──┴──

NOR:     A ──┬──
              │  )─○ Y    Y = A+B̄  (OR + NOT)
         B ──┴──

XOR:     A ──┬──
              │  )── Y    Y = A⊕B = ĀB + AB̄
         B ──┴──            「入力が異なれば1」

XNOR:    A ──┬──
              │  )─○ Y    Y = A⊕B̄  「入力が同じなら1」
         B ──┴──

NAND / NOR の汎用性

NAND だけで任意の論理関数を実現できる!
  NOT:  A NAND A = Ā
  AND:  (A NAND B) NAND (A NAND B) = A·B
  OR:   (A NAND A) NAND (B NAND B) = A+B

NOR も同様にすべての論理を構築可能
これが NAND Flash や NOR Flash の名前の由来である

組合せ論理の簡略化

カルノ図 (Karnaugh Map)

2変数:
    B
  A 0  1
  0 0  1
  1 1  0   ← 出力値を填入

3変数:  AB/C の順に配置
  隣接する1をグループ化 (2ⁿ 個ずつ) → 最小項を導出 → 最簡式を得る

目的: 最少のゲート数で与えられた真理値表を実現する

競争とハザード

複数の信号経路で遅延が異なる → 出力に一時的な誤パルス (glitch) が発生

例: A と Ā が AND ゲートに同時に到達すべきだが、Ā はインバータを通るため遅延が生じる
     → 一瞬だけ A=1, Ā=1 (まだ0に切り替わっていない) → AND 出力が誤って1になる

解決策: 冗長項を追加するか、出力にコンデンサでフィルタリングを施す

論理レベル

TTL vs CMOS

       TTL (5V)         CMOS (5V)       CMOS (3.3V)
VIH:   > 2.0V           > 3.5V          > 2.0V
VIL:   < 0.8V           < 1.5V          < 0.8V
VOH:   > 2.4V           > 4.4V          > 2.9V
VOL:   < 0.4V           < 0.1V          < 0.4V

ノイズマージン = min(VOH-VIH, VIL-VOL)
CMOS のノイズマージンは TTL より明らかに優れている

入力タイプ

浮遊入力 — 絶対に避けること! CMOS の入力が浮遊すると、不確実な状態 + 大きな消費電力になる
未使用の入力ピン: Vcc または GND に接続する (抵抗を介して)

実際のゲート回路

CMOS インバータ

       Vdd
        │
    ┌───┤ PMOS (上側トランジスタ)
    │   │
A ──┤   ├── Y
    │   │
    └───┤ NMOS (下側トランジスタ)
        │
       GND

A=1 → NMOS ON, PMOS OFF → Y=0
A=0 → NMOS OFF, PMOS ON → Y=1

CMOS の最大の利点: 静止時の消費電力はほぼゼロ!
(切り替え時の瞬間のみ電力を消費する)

74 シリーズ早見表

74HC00:  2入力 NAND ゲート x 4
74HC02:  2入力 NOR ゲート x 4
74HC04:  NOT ゲート (インバータ) x 6
74HC08:  2入力 AND ゲート x 4
74HC32:  2入力 OR ゲート x 4
74HC86:  2入力 XOR ゲート x 4
74HC14:  シミットトリガ NOT ゲート x 6
74HC595: 8ビットシフトレジスタ (非常に一般的!)
74HC165: 8ビット並列→直列変換

キーワード: ブール代数, AND, OR, NOT, NAND, NOR, XOR, ド・モルガン, カルノ図, CMOS, TTL