布尔代数

布尔代数 (Boolean Algebra)

概述 (Overview)

布尔代数是一种数学系统，用于分析和简化逻辑电路。它基于二值逻辑，即变量仅有两个可能的取值：0（假）和 1（真）。布尔代数的基本操作包括与（AND）、或（OR）、非（NOT），以及其他复合操作。

Boolean algebra is a mathematical system used to analyze and simplify logic circuits. It is based on binary logic, where variables have only two possible values: 0 (false) and 1 (true). The basic operations in Boolean algebra include AND, OR, and NOT, along with other compound operations.

基本操作 (Basic Operations)

与操作（AND）

与操作表示为 $\mathbf{A}\cdot \mathbf{B}$ 或 $\mathbf{A}\wedge \mathbf{B}$，其输出在且仅在所有输入均为 1 时为 1。

AND operation is denoted as $\mathbf{A}\cdot \mathbf{B}$ or $\mathbf{A}\wedge \mathbf{B}$, and its output is 1 if and only if all inputs are 1.

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

或操作（OR）

或操作表示为 $\mathbf{A}+\mathbf{B}$ 或 $\mathbf{A}\vee \mathbf{B}$，其输出在且仅在至少有一个输入为 1 时为 1。

OR operation is denoted as $\mathbf{A}+\mathbf{B}$ or $\mathbf{A}\vee \mathbf{B}$, and its output is 1 if and only if at least one input is 1.

A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

非操作（NOT）

非操作表示为 $\overline{\mathbf{A}}$ 或 ${\mathbf{A}}^{\prime }$，其输出为输入的反值。

NOT operation is denoted as $\overline{\mathbf{A}}$ or ${\mathbf{A}}^{\prime }$, and its output is the complement of the input.

A	NOT A
0	1
1	0

布尔定律 (Boolean Laws)

基本定律 (Basic Laws)

基本定律包括一些与常规代数类似的规则，如交换律、结合律、分配律等。

Basic laws include rules similar to conventional algebra, such as commutative law, associative law, distributive law, etc.

交换律 (Commutative Law)

$$A+B=B+A$$ $$A\cdot B=B\cdot A$$

结合律 (Associative Law)

$$(A+B)+C=A+(B+C)$$ $$(A\cdot B)\cdot C=A\cdot (B\cdot C)$$

分配律 (Distributive Law)

$$A\cdot (B+C)=(A\cdot B)+(A\cdot C)$$ $$A+(B\cdot C)=(A+B)\cdot (A+C)$$

补充定律 (Additional Laws)

补充定律包括双重否定律、幂等律、零和一律、反演律、吸收律等一些布尔代数的特殊规则。

Additional laws include the double negation law, idempotent law, null and identity law, complement law, absorption law, and other special rules of Boolean algebra.

双重否定律 (Double Negation Law)

$$\overline{\overline{A}}=A$$

幂等律 (Idempotent Law)

$$A+A=A$$ $$A\cdot A=A$$

零和一律 (Null and Identity Law)

$$A+0=A$$ $$A\cdot 1=A$$

反演律 (Complement Law)

$$A+\overline{A}=1$$ $$A\cdot \overline{A}=0$$

吸收律 (Absorption Law)

$$A+(A\cdot B)=A$$ $$A\cdot (A+B)=A$$

De Morgan’s Laws - 德摩根定律

De Morgan’s Laws are essential for simplifying Boolean expressions, which is crucial in reducing the number of transistors in a CMOS circuit. The laws are stated as follows:

德摩根定律对于简化布尔表达式至关重要，这对于减少 CMOS 电路中的晶体管数量至关重要。该定律如下：

1. $\overline{A\cdot B}=\overline{A}+\overline{B}$
2. $\overline{A+B}=\overline{A}\cdot \overline{B}$

复合操作 (Compound Operations)

异或操作（XOR）

异或操作表示为 $\mathbf{A}\oplus \mathbf{B}$，其输出在且仅在两个输入不同时为 1。

XOR operation is denoted as $\mathbf{A}\oplus \mathbf{B}$, and its output is 1 if and only if the two inputs are different.

异或操作可以用基本逻辑门表示为：

XOR operation can be expressed using basic logic gates as:

$\mathbf{A}\oplus \mathbf{B}=(\mathbf{A}\cdot \overline{\mathbf{B}})+(\overline{\mathbf{A}}\cdot \mathbf{B})$

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

多变量异或操作 (Multi-variable XOR Operation)

性质 (Properties)

1. 交换律 (Commutative Law): $A\oplus B=B\oplus A$

2. 结合律 (Associative Law): $(A\oplus B)\oplus C=A\oplus (B\oplus C)$

3. 恒等律 (Identity Law): $A\oplus 0=A$

4. 自反律 (Self-Inverse Law): $A\oplus A=0$

多变量异或的分解 (Decomposition of Multi-variable XOR)

对于多个变量的异或操作，我们可以通过两种主要方法进行分解：

1. 递归分解 (Recursive Decomposition)
2. 展开分解 (Expanded Decomposition)

1. 递归分解 (Recursive Decomposition)

对于 $n$ 个变量 $A_1,A_2,\dots ,A_n$ 的异或操作，我们可以递归地应用两变量异或的公式：

$A_1\oplus A_2\oplus \dots \oplus A_n=((A_1\oplus A_2)\oplus A_3)\oplus \dots \oplus A_n$

然后，我们可以对每个两变量异或使用基本分解：

$((A_1\cdot \overline{A_2}+\overline{A_1}\cdot A_2)\cdot \overline{A_3}+\overline{(A_1\cdot \overline{A_2}+\overline{A_1}\cdot A_2)}\cdot A_3)\oplus \dots \oplus A_n$

2. 展开分解 (Expanded Decomposition)

另一种方法是直接展开多变量异或的定义。对于 $n$ 个变量，异或的结果为 1 当且仅当有奇数个变量为 1。

例如，对于三个变量 $A,B,C$ 的异或操作：

$A\oplus B\oplus C=(A\cdot \overline{B}\cdot \overline{C})+(\overline{A}\cdot B\cdot \overline{C})+(\overline{A}\cdot \overline{B}\cdot C)+(A\cdot B\cdot C)$

这个公式可以理解为：只有一个变量为 1 或所有变量为 1 的情况的和。

示例 (Example)

让我们以三变量异或为例，展示这两种分解方法：

$A\oplus B\oplus C$

1. 递归分解 (Recursive Decomposition):

   $(A\oplus B)\oplus C=((A\cdot \overline{B}+\overline{A}\cdot B)\cdot \overline{C}+\overline{(A\cdot \overline{B}+\overline{A}\cdot B)}\cdot C)$

2. 展开分解 (Expanded Decomposition):

   $A\oplus B\oplus C=(A\cdot \overline{B}\cdot \overline{C})+(\overline{A}\cdot B\cdot \overline{C})+(\overline{A}\cdot \overline{B}\cdot C)+(A\cdot B\cdot C)$

这两种方法都可以用于分解多变量异或操作，选择哪种方法通常取决于具体的应用场景和个人偏好。

---

同或操作（XNOR）

同或操作表示为 $\mathbf{A}\odot \mathbf{B}$ 或 $\overline{\mathbf{A}\oplus \mathbf{B}}$，其输出在且仅在两个输入相同时为 1。

XNOR operation is denoted as $\mathbf{A}\odot \mathbf{B}$ or $\overline{\mathbf{A}\oplus \mathbf{B}}$, and its output is 1 if and only if the two inputs are the same.

同或操作可以用基本逻辑门表示为：

XNOR operation can be expressed using basic logic gates as:

$\mathbf{A}\odot \mathbf{B}=(\mathbf{A}\cdot \mathbf{B})+(\overline{\mathbf{A}}\cdot \overline{\mathbf{B}})$

或者表示为异或的反操作：

Or as the negation of XOR:

$\mathbf{A}\odot \mathbf{B}=\overline{\mathbf{A}\oplus \mathbf{B}}=\overline{(\mathbf{A}\cdot \overline{\mathbf{B}})+(\overline{\mathbf{A}}\cdot \mathbf{B})}$

A	B	A XNOR B
0	0	1
0	1	0
1	0	0
1	1	1

表达式简化 (Expression Simplification)

布尔代数表达式可以通过应用上述定律进行简化，以减少逻辑电路的复杂性。常用的方法包括：

Boolean algebra expressions can be simplified by applying the above laws to reduce the complexity of logic circuits. Common methods include:

• 代数法 (Algebraic Method): 通过逐步应用布尔定律来简化表达式。

  Algebraic Method: Simplifying expressions step-by-step using Boolean laws.

• 卡诺图法 (Karnaugh Map Method): 通过构建卡诺图来识别和消除冗余变量。

  Karnaugh Map Method: Identifying and eliminating redundant variables by constructing Karnaugh maps.

• 真值表法 (Truth Table Method): 根据真值表直接构建和简化布尔表达式。

  Truth Table Method: Constructing and simplifying Boolean expressions directly based on the truth table.

实例 (Example)

代数法 (Algebraic Method)

简化表达式 $\mathbf{A}\cdot \overline{\mathbf{A}}\cdot \mathbf{B}+\mathbf{A}\cdot \mathbf{B}$：

Simplify the expression $\mathbf{A}\cdot \overline{\mathbf{A}}\cdot \mathbf{B}+\mathbf{A}\cdot \mathbf{B}$:

$$\begin{gathered} A\cdot \overline{A}\cdot B+A\cdot B \\ =0\cdot B+A\cdot B\text{(根据反演律 According to Complement Law)} \\ =0+A\cdot B \\ =A\cdot B\text{(根据零律 According to Null Law)} \end{gathered}$$

真值表法 (Truth Table Method)

假设我们有以下真值表：

Assume we have the following truth table:

A	B	Output
0	0	1
0	1	1
1	0	0
1	1	0

根据真值表，可以构建布尔表达式：

Based on the truth table, we can construct the Boolean expression:

$$\mathbf{F}=\overline{A}\cdot \overline{B}+\overline{A}\cdot B$$

应用分配律简化：

Apply the Distributive Law to simplify:

$\mathbf{F}=\overline{A}(\overline{B}+B)=\overline{A}\cdot 1\text{(根据反演律 According to Complement Law)}=\overline{A}\text{(根据幂等律 According to Idempotent Law)}$

因此，简化后的表达式为 $\overline{A}$。

Thus, the simplified expression is $\overline{A}$.

应用 (Applications)

布尔代数在数字电路设计、计算机科学、逻辑学等领域具有广泛应用。通过简化布尔表达式，可以优化逻辑电路的设计，减少门电路的数量和复杂性，提高效率和可靠性。

Boolean algebra has wide applications in digital circuit design, computer science, logic, and other fields. By simplifying Boolean expressions, the design of logic circuits can be optimized, reducing the number and complexity of gates, thereby improving efficiency and reliability.