# 3. 布林代數與邏輯閘 *Boolean Algebra and Logical gates*
###### tags: `DLD-VHDL-kl` `digital logic`

[TOC]

---


::: warning
[NOT](#312-反相閘-NOT-gate)——0、1 對調
[AND](#313-及閘-AND-gate)——全 1 則 1
[OR](#314-或閘-OR-gate)——有 1 則 1
[NAND](#315-反及閘-NAND-gate)——全 1 則 0
[NOR](#316-反或閘-NOR-gate)——有 1 則 0
[XOR](#317-互斥或閘-XOR-gate)——奇 1 則 1
[NXOR](#318-互斥反或閘-NXOR-gate)——偶 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）來決定。
#### 真值表
|輸入 <br> $A$ |輸出 <br> $X=\overline{A}$ |
|:---:|:---:|
|0|1|
|1|0|

::: spoiler 三變數真值表
|輸入 <br> $A$ | 輸入 <br> $B$ | 輸入 <br> $C$ |輸出 <br> $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|
:::

::: spoiler 連續輸入
:::

### 3.1.3 及閘 *AND gate*
**及閘**的作用是進行邏輯乘法運算。
> 若++所有++輸入皆為 $1$，則輸出為 $1$；否則為 $0$。
#### 符號
|ANSI/IEEE Std 91-1984|IEC 60617-12|
|:---:|:---:|
|||

#### 真值表
|輸入 <br> $A$ | 輸入 <br> $B$ |輸出 <br> $X=AB$ |
|:---:|:---:|:---:|
|0|0|0|
|1|0|0|
|0|1|0|
|1|1|1|

|輸入 <br> $A$ | 輸入 <br> $B$ | 輸入 <br> $C$ |輸出 <br> $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|
|:---:|:---:|
|||

#### 真值表
|輸入 <br> $A$ | 輸入 <br> $B$ |輸出 <br> $X=A + B$ |
|:---:|:---:|:---:|
|0|0|0|
|1|0|1|
|0|1|1|
|1|1|1|

|輸入 <br> $A$ | 輸入 <br> $B$ | 輸入 <br> $C$ |輸出 <br> $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|
|:---:|:---:|
|||

#### 真值表
|輸入 <br> $A$ | 輸入 <br> $B$ |輸出 <br> $X=\overline{AB}$ |
|:---:|:---:|:---:|
|0|0|1|
|1|0|1|
|0|1|1|
|1|1|0|

|輸入 <br> $A$ | 輸入 <br> $B$ | 輸入 <br> $C$ |輸出 <br> $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|
|:---:|:---:|
|||

#### 真值表
|輸入 <br> $A$ | 輸入 <br> $B$ |輸出 <br> $X=\overline{A+B}$ |
|:---:|:---:|:---:|
|0|0|1|
|1|0|0|
|0|1|0|
|1|1|0|

|輸入 <br> $A$ | 輸入 <br> $B$ | 輸入 <br> $C$ |輸出 <br> $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|
|:---:|:---:|
|||

#### 真值表
|輸入 <br> $A$ | 輸入 <br> $B$ |輸出 <br> $X=A\oplus B$ |
|:---:|:---:|:---:|
|0|0|0|
|1|0|1|
|0|1|1|
|1|1|0|

|輸入 <br> $A$ | 輸入 <br> $B$ | 輸入 <br> $C$ |輸出 <br> $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|
|:---:|:---:|
|||

#### 真值表
|輸入 <br> $A$ | 輸入 <br> $B$ |輸出 <br> $X=\overline{A\oplus B}$ |
|:---:|:---:|:---:|
|0|0|1|
|1|0|0|
|0|1|0|
|1|1|1|

|輸入 <br> $A$ | 輸入 <br> $B$ | 輸入 <br> $C$ |輸出 <br> $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=\overline{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](https://www.allaboutcircuits.com/technical-articles/boolean-identities/) | 加法 OR | 乘法 AND |
|----|----|----|----|
|**對偶定理** <br> *duality theorem*| **恆等性** <br> *identity* | $A+0=A$ | $A\cdot 1=A$ |
|**吸收定理** <br> *absorptive theorem*| **優勢性** <br> *dominance* | $A+1=1$ | $A\cdot 0=0$ |
|**全等定理** <br> *equal theorem*| **冪等性** <br> *idempotence* | $A+A=A$ | $A\cdot A=A$ |
|**補數定理** <br> *duality theorem* | **互補性** <br> *complementarity* | $A+\overline{A}=1$ | $A\cdot \overline{A}=0$ |


| 名稱 1 | [名稱 2](https://www.allaboutcircuits.com/technical-articles/boolean-identities/) | |
|----|----|----|
|**自補定理** <br> *involution theorem* | **對合** <br> *involution* | $\overline{\overline{A}}=A$ |


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

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

| 名稱 1| [名稱 2](https://www.allaboutcircuits.com/technical-articles/boolean-identities/) | 加法 OR | 乘法 AND |
|----|----|----|----|
|**消去律** <br> *elimination law* | **吸收律** <br> *absorption* | $A+A\cdot B = A$ | $A\cdot (A+B)=A$ |

| 名稱 | 加法 OR （第一定律） | 乘法 AND（第二定律） |
|----|----|----|
|**狄摩根定律** <br> *DeMorgan's laws*| $\overline{A+B}=\overline{A}\cdot\overline{B}$ | $\overline{A\cdot B}=\overline{A}+\overline{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$ 否定的連言


::: success

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

:::

## 3.3 邏輯 IC *Logic ICs*
常用的邏輯 IC 有 5 種：
1. **TTL**：**電晶體電晶體邏輯**（Transistor-Transistor Logic）
種類最多、用途最廣
| 中文 | 英文 | 型號 |
|--|--|--|
| 標準 TTL | standard TTL | [74](https://zh.wikipedia.org/wiki/%E9%9B%BB%E6%99%B6%E9%AB%94-%E9%9B%BB%E6%99%B6%E9%AB%94%E9%82%8F%E8%BC%AF#74%E7%B3%BB%E5%88%97%E8%88%8754%E7%B3%BB%E5%88%97) |
| 低功率 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 | [4000](https://zh.wikipedia.org/wiki/4000%E7%B3%BB%E5%88%97)B |
| 矽閘 CMOS | low-power TTL | 74C |
| 高速 CMOS | high-speed CMOS | 74HC |
| 蕭特基 TTL | Schottky-TTL | 74S |

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

5. **I^2^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*