3. 布林代數與邏輯閘 Boolean Algebra and Logical gates

tags: DLD-VHDL-kl digital logic

• 3. 布林代數與邏輯閘 Boolean Algebra and Logical gates
  • 3.1 基本邏輯閘 Basic logic gates
    • 3.1.1 簡介 Introduction
    • 3.1.2 反相閘 NOT gate
    • 3.1.3 及閘 AND gate
    • 3.1.4 或閘 OR gate
    • 3.1.5 反及閘 NAND gate
    • 3.1.6 反或閘 NOR gate
    • 3.1.7 互斥或閘 XOR gate
    • 3.1.8 互斥反或閘 NXOR gate
  • 3.2 布林代數 Boolean algebra
    • 3.2.1 布林運算 Boolean operations
    • 3.2.2 布林代數恆等式 Boolean Algebraic Identities
  • 3.3 邏輯 IC Logic ICs
    • 3.3.2 邏輯 IC 的特性

---

NOT——0、1 對調
AND——全 1 則 1
OR——有 1 則 1
NAND——全 1 則 0
NOR——有 1 則 0
XOR——奇 1 則 1
NXOR——偶 1 則 1

---

3.1 基本邏輯閘 Basic logic gates

3.1.1 簡介 Introduction

在數位電路中，閘（gate）是指「具有一個或多個輸入，但只有一個輸出」的元件。用邏輯閘組成的電路稱為邏輯電路（logical circuit）。

基本的邏輯閘有：

• 反相閘（NOT）
• 及閘（AND）
• 或閘（OR）

真值表（truth table）可以顯示邏輯閘的各種輸入狀態和輸出的關係。若輸入個數為

$n$ 則，輸入狀態有

$2^n$ 種。

3.1.2 反相閘 NOT gate

反相閘的作用是改變邏輯位準（logic level），簡單來說，就是

$1$ 換成

$0$，

$0$ 換成

$1$。
（1 = High 高電位，0 = Low 低電位，下同）

符號

ANSI/IEEE Std 91-1984	IEC 60617-12

其中符號輸入端或輸出端的小圈為否定指示器（negation indicator），它的位置要依據輸入信號的作用狀態（active state）來決定。

真值表

輸入 $A$	輸出 $X=\bar{A}$
0	1
1	0

三變數真值表

輸入 $A$	輸入 $B$	輸入 $C$	輸出 $X=A\cdot B\cdot C$
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

連續輸入

3.1.3 及閘 AND gate

及閘的作用是進行邏輯乘法運算。

若所有輸入皆為

$1$，則輸出為

$1$；否則為

$0$。

符號

ANSI/IEEE Std 91-1984	IEC 60617-12

真值表

輸入 $A$	輸入 $B$	輸出 $X=AB$
0	0	0
1	0	0
0	1	0
1	1	1

輸入 $A$	輸入 $B$	輸入 $C$	輸出 $X=ABC$
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

3.1.4 或閘 OR gate

或閘的作用是進行邏輯加法運算。

若任一輸入為

$1$，則輸出為

$1$；；否則，輸出為

$0$。

符號

ANSI/IEEE Std 91-1984	IEC 60617-12

真值表

輸入 $A$	輸入 $B$	輸出 $X=A+B$
0	0	0
1	0	1
0	1	1
1	1	1

輸入 $A$	輸入 $B$	輸入 $C$	輸出 $X=A+B+C$
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

3.1.5 反及閘 NAND gate

反及閘的作用是先進行邏輯乘法運算，再進行反相運算。

若所有輸入為

$0$，則輸出為

$1$；否則，輸出為

$0$。

符號

ANSI/IEEE Std 91-1984	IEC 60617-12

真值表

輸入 $A$	輸入 $B$	輸出 $X=\overline{AB}$
0	0	1
1	0	1
0	1	1
1	1	0

輸入 $A$	輸入 $B$	輸入 $C$	輸出 $X=\overline{ABC}$
0	0	0	1
0	0	1	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

3.1.6 反或閘 NOR gate

反或閘的作用是先進行邏輯加法運算，再進行反相運算。

若任一輸入為

$1$，則輸出為

$0$；否則，輸出為

$1$。

符號

ANSI/IEEE Std 91-1984	IEC 60617-12

真值表

輸入 $A$	輸入 $B$	輸出 $X=\overline{A+B}$
0	0	1
1	0	0
0	1	0
1	1	0

輸入 $A$	輸入 $B$	輸入 $C$	輸出 $X=\overline{A+B+C}$
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

3.1.7 互斥或閘 XOR gate

互斥或閘的作用是執行互斥或（exclusive or）運算，它是前述基本邏輯運算的組合。因為在許多應用中它是一個重要定理，所以也將它視為基本基本邏輯運算。

若有奇數個輸入為

$1$，則輸出為

$1$；否則，輸出為

$0$。

符號

ANSI/IEEE Std 91-1984	IEC 60617-12

真值表

輸入 $A$	輸入 $B$	輸出 $X=A\oplus B$
0	0	0
1	0	1
0	1	1
1	1	0

輸入 $A$	輸入 $B$	輸入 $C$	輸出 $X=A\oplus B\oplus C$
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

3.1.8 互斥反或閘 NXOR gate

互斥反或閘的作用是先執行互斥或運算，再執行反相運算。

若有偶數個輸入為

$1$，則輸出為

$1$；否則，輸出為

$0$。

符號

ANSI/IEEE Std 91-1984	IEC 60617-12

真值表

輸入 $A$	輸入 $B$	輸出 $X=\overline{A\oplus B}$
0	0	1
1	0	0
0	1	0
1	1	1

輸入 $A$	輸入 $B$	輸入 $C$	輸出 $X=\overline{A\oplus B\oplus C}$
0	0	0	1
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	0

3.2 布林代數 Boolean algebra

喬治・布爾（George Boole）發表於 1854 年。
只處理 0 和 1 的代數

3.2.1 布林運算 Boolean operations

NOT 相當於 邏輯補數
AND 相當於 邏輯乘法
OR 相當於 邏輯加法

邏輯閘	運算	布林運算式
反相閘	NOT	$X=\bar{A}$
及閘	AND	$X=A\cdot B$
或閘	OR	$X=A+B$
反及閘	NAND	$X=\overline{A\cdot B}$
反或閘	NOR	$X=\overline{A+B}$
互斥或閘	XOR	$X=A\oplus B$
互斥反或閘	NXOR	$X=\overline{A\oplus B}$

3.2.2 布林代數恆等式 Boolean Algebraic Identities

名稱 1	名稱 2	加法 OR	乘法 AND
對偶定理 duality theorem	恆等性 identity	$A+0=A$	$A\cdot 1=A$
吸收定理 absorptive theorem	優勢性 dominance	$A+1=1$	$A\cdot 0=0$
全等定理 equal theorem	冪等性 idempotence	$A+A=A$	$A\cdot A=A$
補數定理 duality theorem	互補性 complementarity	$A+\bar{A}=1$	$A\cdot \bar{A}=0$

名稱 1	名稱 2
自補定理 involution theorem	對合 involution	$\overline{\stackrel{―}{A}}=A$

名稱	加法 OR	乘法 AND
交換律 commutativity	$A+B=B+A$	$A\cdot B=B\cdot A$
結合律 associativity	$(A+B)+C=A+(B+C)$	$(A\cdot B)\cdot C=A\cdot (B\cdot C)$
分配律 distributivity	$A+(B\cdot C)=(A+B)\cdot (A+C)$	$A\cdot (B+C)=(A\cdot B)+(A\cdot C)$

注意：一般代數只有乘法分配律，但布林代數具有加法分配律。

名稱 1	名稱 2	加法 OR	乘法 AND
消去律 elimination law	吸收律 absorption	$A+A\cdot B=A$	$A\cdot (A+B)=A$

名稱	加法 OR （第一定律）	乘法 AND（第二定律）
狄摩根定律 DeMorgan's laws	$\overline{A+B}=\bar{A}\cdot \bar{B}$	$\overline{A\cdot B}=\bar{A}+\bar{B}$

1. negation of a disjunction
   $\equiv$ conjunction of the negations
2. negation of a conjunction
   $\equiv$ disjunction of the negations

1. 連言的否定
   $\equiv$ 否定的並言
2. 並言的否定
   $\equiv$ 否定的連言

提示：可以利用真值表證明以上所有恆等式，例如：

3.3 邏輯 IC Logic ICs

常用的邏輯 IC 有 5 種：

1. TTL：電晶體電晶體邏輯（Transistor-Transistor Logic）
   種類最多、用途最廣

   中文	英文	型號
   標準 TTL	standard TTL	74
   低功率 TTL	low-power TTL	74L
   高速 TTL	high-speed TTL	74H
   蕭特基 TTL	Schottky-TTL	74S
   低功率蕭特基 TTL	low-power Schottky-TTL	74LS
   高級蕭特基 TTL	advanced-Schottky	74AS
   高級低功率蕭特基 TTL	advanced low-powe Schottky	74ALS

   

2. MOS：金屬氧化物半導體（Metal-Oxide Semiconductor）
   高密度，用於大型積體電路（LSI）

3. CMOS：互補式金屬氧化物半導體（Complementary Metal-Oxide Semiconductor）
   低功耗，分為金屬閘CMOS與矽閘CMOS

   中文	英文	型號
   金屬閘CMOS	standard TTL	4000B
   矽閘 CMOS	low-power TTL	74C
   高速 CMOS	high-speed CMOS	74HC
   蕭特基 TTL	Schottky-TTL	74S

4. ECL：射極耦合邏輯（Emitter-Coupled Logic）
   速度快

5. I²L：積體注入邏輯（Integrated-Injection）
   高密度，用於大型積體電路（LSI）

3.3.2 邏輯 IC 的特性

扇出數 Fan-out

一個邏輯閘（驅動閘）可以驅動其他同類邏輯閘（負載閘）的數量。

消耗功率 Power dissipation

$\text{Pd}=I_{\text{CC}}{V}_{\text{CC}}$

傳遞延遲 Propagation delay

訊號傳遞的速度

• $t_{\text{PHL}}$
• $t_{\text{PLH}}$
  

電壓位準 Propagation delay