布尔代数由英国数学家乔治·布尔 (George Boole) 于 19 世纪中叶在其著作《逻辑的数学分析》(The mathematical analysis of logic, 1847) 和《思维规律的研究》(The Laws of Thought, 1854) 中系统提出。他试图将逻辑推理形式化为一种代数系统，从而用数学方法处理命题的真假关系。这一思想最初被视为纯理论逻辑工具，但随着 20 世纪电子技术的发展，尤其是数字电路的兴起，布尔代数被克劳德·香农 (Claude Shannon) 于 1937 年在其硕士论文中成功应用于开关电路的设计，奠定了现代数字系统设计的理论基础。

如今，布尔代数已成为计算机科学的核心数学工具之一。它不仅支撑着数字逻辑电路 (如与门、或门、非门等) 的设计与优化，还在编程语言的条件判断、数据库查询、形式验证、人工智能推理以及密码学等领域发挥着关键作用。可以说，没有布尔代数，就没有现代计算机体系结构和数字信息处理技术。

基本概念与运算

布尔代数建立在一个二值逻辑系统之上，其基本元素集合为 {0, 1}，其中 0 和 1 叫做布尔常量，它们不随上下文变化，是布尔表达式中的基本构建单元。

布尔值具有多重语义解释，实际意义取决于应用上下文。在逻辑语境中用来表示真 (True) /假 (False)，在电子工程中用来表示高电平/低电平 (5V/3.3 - 0V)，在计算机存储中用来表示比特 (bit) 的基本状态。这种二值性使得布尔代数特别适合描述和操作离散、确定性的系统行为，是构建可靠数字系统的数学基石。例如，x=1 表示变量 x 处于 “真” 或 “激活” 状态。

布尔变量 (Boolean variable) 是指取值为布尔常量的符号，通常用字母如 x, y, z 等表示。其取值用 x=1 这样的等式来表示。

三种基本运算（AOI）

布尔代数的核心在于其定义的逻辑运算，这些运算是构建复杂逻辑表达式和数字电路的基础。根据参与运算的操作数个数，布尔运算可分为一元运算和二元运算。

■ 一元运算 (NOT)

非运算 (NOT) 是对单个布尔变量取反的操作，实现 0 与 1 之间的转换。

if x=1 output 0
else output 1

┏━━━━━━━━━━━━━━━┓
┃   Not Gate    ┃
┣━━━━━━━┳━━━━━━━┫
┃   A   ┃  out  ┃
┣━━━━━━━╋━━━━━━━┫
┃   0   ┃   1   ┃
┠───────╂───────┨
┃   1   ┃   0   ┃
┗━━━━━━━┻━━━━━━━┛

■ 二元运算 (AND)

逻辑与 (AND, x·y) 对应同时成立逻辑关系。在当且仅当两个输入均为 1 时结果为 1。

if x=y=1 output 1
else output 0

┏━━━━━━━━━━━━━━━━━━━━━━━┓
┃       And Gate        ┃
┣━━━━━━━┯━━━━━━━┳━━━━━━━┫
┃   A   │   B   ┃  out  ┃
┣━━━━━━━┿━━━━━━━╋━━━━━━━┫
┃   0   │   0   ┃   0   ┃
┠───────┼───────╂───────┨
┃   0   │   1   ┃   0   ┃
┠───────┼───────╂───────┨
┃   1   │   0   ┃   0   ┃
┠───────┼───────╂───────┨
┃   1   │   1   ┃   1   ┃
┗━━━━━━━┷━━━━━━━┻━━━━━━━┛

■ 二元运算 (OR)

逻辑或 (OR, x+y) 则是反过来，对应至少一个成立的逻辑关系。只要有一个输入为 1 时结果为 1。

if x=y=0 output 0
else output 1

┏━━━━━━━━━━━━━━━━━━━━━━━┓
┃        Or Gate        ┃
┣━━━━━━━┯━━━━━━━┳━━━━━━━┫
┃   A   │   B   ┃  out  ┃
┣━━━━━━━┿━━━━━━━╋━━━━━━━┫
┃   0   │   0   ┃   0   ┃
┠───────┼───────╂───────┨
┃   0   │   1   ┃   1   ┃
┠───────┼───────╂───────┨
┃   1   │   0   ┃   1   ┃
┠───────┼───────╂───────┨
┃   1   │   1   ┃   1   ┃
┗━━━━━━━┷━━━━━━━┻━━━━━━━┛

运算优先级与表达式语法

为避免歧义，布尔表达式遵循特定的运算优先级规则。与算术表达式类似，逻辑运算符并非从左到右简单依次执行，而是根据其绑定强度优先级从高到低为 NOT > AND > OR。例如，表达式 x + y′⋅ z 应解释为 x + ((y′) ⋅ z))。这种优先级安排不仅符合逻辑直觉 (否定作用于单个变量，与运算是 “乘积” 式的组合，或运算是 “求和” 式的聚合)，也与数字电路中门级实现的层次结构相一致。

■ 括号的作用

尽管优先级规则提供了默认的解析方式，括号在布尔表达式中仍扮演着至关重要的角色。它们可以显式地覆盖默认优先级，强制改变运算顺序，从而精确表达设计者的意图。特别是在复杂表达式中，合理使用括号不仅能避免误解，还能提升可读性。

例如，若希望先计算 x + y′ 再与 z 相与，则必须写作 (x + y′) · z；若省略括号，系统将按优先级先算 y′ · z，导致完全不同的逻辑功能。因此，括号是构建任意逻辑结构的必要工具，也是确保表达式语法合法性的关键要素。

■ 合法表达式示例

基于上述规则，许多形式都构成合法的布尔表达式。最简单的包括常量和变量本身，如 0、1 或 x。稍复杂的可通过递归应用运算符构造，例如：

x′ + y · z
(x + y′) · (x′ + z)
((a · b)′ + c) · d′

只要表达式由原子项 (常量或变量) 通过有限次应用 NOT、AND、OR 并配以适当括号构成，即视为语法合法。这种严格的语法规则使得布尔表达式既能被人类清晰理解，也能被计算机程序准确解析，为后续的逻辑分析、等价验证和电路综合奠定了基础。

布尔函数及其语义

布尔函数是布尔代数中的基本对象，它描述了从一组布尔输入到一个布尔输出的确定性映射。形式上，一个 n 元布尔函数是一个从 {0,1}^n 到 {0,1} 的映射：

$$ \begin{align} f(x_1, x_2, \ldots, x_n): \{0, 1\}^n \to \{0, 1\} \end{align} $$

这意味着函数接受 n 个布尔变量作为输入（每个变量取值为 0 或 1），并返回一个布尔值作为输出。由于共有 2ⁿ 种不同的输入组合，而每种组合的输出可以独立地指定为 0 或 1，因此总共存在 2^(2ⁿ) 个不同的 n 元布尔函数。举个例子，f(x,y) 共有 2 个变量作为输入，且 x、y 均可独立的等于 0 或 1，因此所有的输入组合共有 2²=4 种，而 f(x,y) 的输出与输入没有关联，因此每种输入组合又可以对应 0 或 1 这两种取值，因此可以构造出 2⁴ 个彼此行为不同的布尔函数。

在实际中，布尔函数通常通过布尔表达式来表示。表达式的合法性由其语法决定：最基本的成分包括布尔常量 (0 和 1) 和布尔变量 (如 x, y, z)；更复杂的表达式则通过逻辑运算符 NOT (记作 ′)、AND (记作 · 或省略) 和 OR (记作 +) 递归构造而成。括号可用于明确运算顺序，避免歧义。例如，以下均为合法的布尔表达式：

x′ + y·z
(x + y′)·(x′ + z)
1
x

这些表达式本身只是符号串，其意义需通过语义来赋予。语义规定了在给定变量赋值下如何计算表达式的真值：首先为每个变量赋予 0 或 1，然后按照运算优先级 (NOT > AND > OR) 并结合括号逐步求值，最终得到 0 或 1。这个结果即为该输入下所对应布尔函数的输出。因此，每一个布尔表达式都定义了一个布尔函数，该函数的行为完全由表达式在所有可能输入下的语义计算结果所确定。不同的表达式可能定义相同的函数 (即语义等价)，但每个表达式唯一对应一个函数。

一个典型例子是三元多数函数，其表达式为：

$$ \begin{align} \mathrm{Maj}(x, y, z) = xy + yz + xz \end{align} $$

该函数在至少两个输入为 1 时输出 1，否则输出 0。这一行为正是通过上述表达式在全部 8 种输入组合下的语义计算所体现的。由此可见，布尔表达式提供了函数的 “语法描述”，而布尔函数则是其完整的 “语义实体”。这种语法与语义的对应关系，构成了布尔代数应用于逻辑设计和数字电路实现的理论基础。

真值表与函数表示

■ 真值表

真值表以穷举方式列出所有可能的输入组合及其对应的输出，是定义布尔运算最清晰的方式：

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃              Truth Table              ┃
┣━━━━━━━┯━━━━━━━┳━━━━━━━┯━━━━━━━┯━━━━━━━┫
┃   A   │   B   ┃   x′  │  x·y  │  x+y  ┃
┣━━━━━━━┿━━━━━━━╋━━━━━━━┿━━━━━━━┿━━━━━━━┫
┃   0   │   0   ┃   1   │   0   │   0   ┃
┠───────┼───────╂───────┼───────┼───────┨
┃   0   │   1   ┃   1   │   0   │   1   ┃
┠───────┼───────╂───────┼───────┼───────┨
┃   1   │   0   ┃   0   │   0   │   1   ┃
┠───────┼───────╂───────┼───────┼───────┨
┃   1   │   1   ┃   0   │   1   │   1   ┃
┗━━━━━━━┷━━━━━━━┻━━━━━━━┷━━━━━━━┷━━━━━━━┛

注：(1) 上表为 f(x)=x′, f(x,y)=x·y, f(x,y)=x+y 的真值表；
    (2) x′ 仅依赖于 x，因此在表中与 y 无关。

■ 布尔表达式

还可以使用布尔表达式来定义布尔函数。例如 f(x,y,z) = (x Or y) And Not(z) = (x+y)·(z′)。其中：

x And y == x · y
x Or y == x + y
Not(x) == x′

这两种表示方式各有优缺点。真值表表示法与布尔函数一一对应，一个布尔函数仅有唯一一个真值表，这使得真值表表示法非常直观、完备。但当变量数 n 较大时 (如 n>5)，表格规模成指数爆炸，限制较大。

布尔表达式法则完全相反。通过一行布尔表达式可以用描述式的语言来表达布尔函数的计算方法，这种表示方式抽象、高效，但每个布尔函数的布尔表达式并不唯一，这意味着同一个布尔函数可以由许多不同但等价的布尔表达式表示，其中一些表达式更短、更容易处理。例如，表达式 (Not(x And y) And (Not(x) Or y) And (Not(y) Or y)) 等价于表达式 Not(x)。这个过程叫做布尔表达式的化简。有关布尔表达式的化简技巧，我们放到后面的小节再讲解。

布尔代数的公理体系与基本定理

布尔代数不仅是一套逻辑运算规则，更是一个形式化的代数系统。其严谨性源于一组公理 (axioms)，所有其他性质和定理均可由此推导得出。1904 年，数学家爱德华·亨廷顿 (Edward V. Huntington) 提出了布尔代数的一组简洁公理系统。在二值集合 {0,1} 上，结合两种二元运算 (+ 表示 OR，· 表示 AND) 和一元补运算 (′)，布尔代数满足以下公理。

公理	英文	And 形式	Or 形式
封闭性	Closure	a · b ∈ {0,1}	a + b ∈ {0,1}
交换律	Commutativity	a · b == b · a	a + b == b + a
结合律	Associativity	(a · b) · c == a · (b · c)	(a + b) + c == a + (b + c)
分配律	Distributivity	a · (b + c) == (a · b) + (a · c)	a + (b · c) == (a + b) · (a + c)
单位元	Identity Elements	a · 1 == a	a + 0 == a
补元	Complement	a · a′ == 0	a + a′ == 1

这些公理共同定义了布尔代数的代数结构，使其成为一个有补分配格 (complemented distributive lattice)。

由上述公理可推导出一系列常用恒等式，在逻辑化简与电路优化中极为实用。

公理	英文	And 形式	Or 形式
幂等律	Idempotent Law	a · a == a	a + a == a
吸收律	Absorption Law	a · (a + b) == a	a + (a · b) == a
广义吸收律	Generalized Absorption Law	a · (a′+ b) == a · b	a + a′b == a + b
零一律	Null / Dominance Law	a · 0 = 0	a + 1 == 1
对合律	Involution Law	(a′)′ == a
互补律 (已作为公理，但常列为恒等式)		a · a′ == 0	a + a′ == 1
同一律 (见单位元)	Identity	a · 1 == a	a + 0 == a

对偶原理 (Duality Principle)

对偶原理是布尔代数中体现结构对称性的重要性质。即：给定一个布尔表达式 E，其对偶式 E^D 是通过以下替换得到的新表达式：

将所有 + 替换为 ⋅；
将所有 ⋅ 替换为 +；
将常量 0 替换为 1，1 替换为 0；
变量及其补保持不变。

对偶原理断言：若等式 E1=E2 在布尔代数中成立，则其对偶等式 E1^D=E2^D 也成立。

示例：

原恒等式                   对偶式
------------------------   ----------------------------
x + 0 == x                 x ⋅ 1 == x
x ⋅ (y + z) == x⋅y + x⋅z   x + y ⋅ z == (x + y)⋅(x + z)

注：对偶不等于逻辑等价。
    例如，f(x)=x 与其对偶 f^D(x)=x 相同；
    但 f(x,y)=x+y 的对偶是 x⋅y，二者并非等价函数；
    而是在代数定律层面具有对称性。

对偶原理常用于推导新定理或简化证明过程。

德·摩根定律 (De Morgan’s Laws)

由英国数学家奥古斯都·德·摩根 (Augustus De Morgan) 提出，是布尔代数中最深刻且应用最广泛的定理之一。它揭示了与、或运算在取反下的对偶关系：

公理	英文	And 形式	Or 形式
德·摩根定律	De Morgan’s Laws	(a · b)′ == a′ + b′	(a + b)′ == a′ · b′

德·摩根定律可自然推广到任意有限个变量的情形：

推论一：多个变量或后的非，等于各变量分别取非后再与；

$$ \begin{align} \left( \bigvee_{i=1}^{n} A_i \right)' = \bigwedge_{i=1}^{n} A_i' \quad\equiv\quad (A_1 + A_2 + \cdots + A_n)' = A_1' \cdot A_2' \cdot \cdots \cdot A_n' \end{align} $$

推论二：多个变量与后的非，等于各变量分别取非后再或。

$$ \begin{align} \left( \bigwedge_{i=1}^{n} A_i \right)' = \bigvee_{i=1}^{n} A_i' \quad\equiv\quad (A_1 \cdot A_2 \cdot \cdots \cdot A_n)' = A_1' + A_2' + \cdots + A_n' \end{align} $$

该性质在数字电路设计中尤为重要，可用于将复杂逻辑门转换为仅使用 Nand 或 Nor 门的等效实现，从而降低硬件成本。

布尔函数的等价性判定

要想两个布尔表达式 E1 和 E2 等价，当且仅当它们定义的布尔函数完全相同，即对所有 2ⁿ 种输入组合，输出一致。可通过真值表法、代数简化法来进行等价性判定。

■ 真值表法 (Truth Table Method)

真值表法顾名思义是通过真值表来判断布尔函数的等价性。其原理是，布尔函数的真值表是唯一的。通过列出 E1 与 E2 所有 2ⁿ 种输入组合，来判断 E1 与 E2 的输出是否完全相同，若相同则 E1≡E2。

下面使用真值表法判断 E1 == a′ + b 以及 E2 == (a · b′)′ 这两个布尔表达式的等价性：

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃                      Truth Table                      ┃
┣━━━━━━━┯━━━━━━━┳━━━━━━━┯━━━━━━━┯━━━━━━━┯━━━━━━━┯━━━━━━━┫
┃   a   │   b   ┃   a′  │   b′  │  a·b′ │(a·b′)′│ a′+ b ┃
┣━━━━━━━┿━━━━━━━╋━━━━━━━┿━━━━━━━┿━━━━━━━┿━━━━━━━┿━━━━━━━┫
┃   0   │   0   ┃   1   │   1   │   0   │   1   │   1   ┃
┠───────┼───────╂───────┼───────┼───────┼───────┼───────┨
┃   0   │   1   ┃   1   │   0   │   0   │   1   │   1   ┃
┠───────┼───────╂───────┼───────┼───────┼───────┼───────┨
┃   1   │   0   ┃   0   │   1   │   1   │   0   │   0   ┃
┠───────┼───────╂───────┼───────┼───────┼───────┼───────┨
┃   1   │   1   ┃   0   │   0   │   0   │   1   │   1   ┃
┗━━━━━━━┷━━━━━━━┻━━━━━━━┷━━━━━━━┷━━━━━━━┷━━━━━━━┷━━━━━━━┛

注：(1) 真值表法需要逐列计算中间结果 (a′, b′, a·b′) 和最终表达式 ((a·b′)′、a′+b)；
    (2) 表中(a·b′)′、a′+b 这两列的真值表输出完全一致，可证得 E1≡E2。

■ 代数化简法 (Algebraic Simplification)

代数化简法则利用布尔代数公理与定理 (如分配律、吸收律、德·摩根律等) 对两个表达式分别化简。若能化为相同的最简形式 (如最小积之和)，则等价。或将 $E1 \oplus E2$ (Xor, 异或) 化简为恒 0，也可证明等价。

下面使用代数化简法判断 $E1 = x+x' \cdot y$ 与 $E2=x+y$ 是否等价。

$$ \begin{align} E_1 &= x + x' \cdot y \\ &= (x + x')(x + y) && \text{(分配律)} \\ &= 1 \cdot (x + y) && \text{(互补律: } x + x' = 1\text{)} \\ &= x + y && \text{(恒等律)} \\ &= E_2 && \text{(由 } E_2 = x + y\text{)} \\ \therefore \quad E_1 &\equiv E_2 \end{align} $$

代数化简法更适用于符号推理和自动化工具 (如逻辑综合器)，但由于每个布尔函数具有多种不同但等价的布尔表达式表示，因此化简过程可能非唯一，且缺乏通用 “最简” 标准。

标准形式与规范表示

在布尔代数中，为了对布尔函数进行系统化分析、比较或硬件实现，通常会将其转换为某种标准形式 (canonical form)。这类形式具有唯一性，即同一个布尔函数只对应一种标准表达式 (不考虑项的顺序)，因而特别适用于理论推导、逻辑综合以及计算机辅助设计。其中最重要的两种规范表示是积之和 (Sum of Products, SOP) 与和之积 (Product of Sums, POS)，它们的构建基础分别是最小项 (minterm) 和最大项 (maxterm)。

例如，一个三变量函数可能以以下两种等价方式表示：

SOP 形式 (若干 “与项” 相 “或”)：f(x,y,z) == x′y′z + x′yz + xy′z + xyz
POS 形式 (若干 “或项” 相 “与”)：f(x,y,z) == (x′+y′+z)(x+y′+z)(x′+y+z)(x+y+z)

尽管结构迥异，这两个表达式描述的是同一个布尔函数——前者突出其输出为 1 的情况，后者则刻画其输出为 0 的条件。后续将详细说明如何从真值表系统地构造这两种标准形式。

最小项 (Minterm) 与最大项 (Maxterm)

最小项是一个包含所有 n 个变量的乘积项 (即 AND 项)，其中每个变量以原变量或补变量的形式恰好出现一次。由于每个变量都参与且仅出现一次，一个最小项在全部 2ⁿ 种输入组合中，仅在一种特定组合下取值为 1，其余情况下均为 0。因此，我们可以将最小项与该使其为 1 的输入组合一一对应，并用二进制数将其编码为一个整数下标 i，记作 m_i。例如，对于三元函数 f(x,y,z)，当输入组合为 (x=1,y=0,z=1) 时，对应的二进制为 101，即十进制 5，因此该最小项为：

$$ m_5=x \cdot y' \cdot z $$

与最小项对偶的是最大项。最大项是一个包含所有 n 个变量的和项 (即 OR 项)，同样每个变量以原变量或补变量形式恰好出现一次。不同之处在于，每个最大项在唯一一种输入组合下取值为 0，其余情况下均为 1。其下标 i 同样由使其为 0 的输入组合所对应的二进制数确定，记作 M_i。仍以三元变量为例，当 (x=1,y=0,z=1) 使函数为 0 时，对应的最大项需在该点输出 0，因此变量取反后相加 (可通过德·摩根定律转化为积的形式)：

$$ M_5=(x+y'+z) = x' \cdot y \cdot z' $$

这是因为当 x=1 时 x′=0，y=0 时 y=0，z=1 时 z′=0，三项相加得 0。最小项与最大项之间存在严格的对偶关系。即，M_i=(m_i)′ 且 m_i=(M_i)′。

积之和 (SOP) 与和之积 (POS)

基于最小项，可以构造标准积之和 (Standard Sum of Products, Standard SOP) 形式。该形式将布尔函数表示为所有使其输出为 1 的最小项之和 (即逻辑 OR)。由于每个最小项对应一个唯一的 “真” 输入组合，标准 SOP 实质上是函数真值表中所有输出为 1 的行的直接代数翻译。这种表示是唯一的 (忽略项的排列顺序)，并且完整刻画了函数的行为。例如，若函数 f(x,y,z) 在输入 001、011、101、111 (即十进制 1、3、5、7) 时输出为 1，则其标准 SOP 为：

$$ f(x,y,z)\;=\;m1+m3+m5+m7\;=\;x'y'z+x'yz+xy'z+xyz $$

类似地，标准和之积 (Standard Product of Sums, Standard POS) 形式利用最大项来表示函数：它将函数写成所有使其输出为 0 的最大项之积 (即逻辑 AND)。因为每个最大项在唯一一个 “假” 输入下为 0，整个乘积在这些输入下结果为 0，而在其他输入下所有因子均为 1，故乘积为 1。这也与真值表完全一致，且同样具有唯一性。继续以上述函数为例，若它在输入 000、010、100、110 (即 0、2、4、6) 时输出为 0，则其标准 POS 为：

$$ f(x,y,z)\;=\;M0 \cdot M2 \cdot M4 \cdot M6\;=\;(x+y+z)(x+y'+z)(x'+y+z)(x'+y'+z) $$

综上，标准 SOP 和标准 POS 分别从 “函数何时为真” 和 “函数何时为假” 两个互补视角出发，提供了布尔函数的规范、无歧义且可机械生成的代数表示。尽管它们通常不是最简形式，但作为中间表示，在逻辑设计自动化、函数等价性验证以及后续化简 (如卡诺图或奎因-麦克拉斯基算法)中扮演着不可或缺的角色。

SOP 与 POS 的互化

标准积之和 (SOP) 与标准和之积 (POS) 虽然是两种形式迥异的规范表示，但它们描述的是同一个布尔函数，因此在理论上可以相互转换。这种转换的核心工具是德·摩根定律 (De Morgan’s Laws)，即 (A⋅B)′==A′+B′ 与 (A+B)′==A′⋅B′，并可推广至任意有限项。由于 SOP 表达式直接对应函数输出为 1 的最小项之和，而 POS 对应输出为 0 的最大项之积，二者本质上互为补集关系，因此可以通过对函数取反、应用德·摩根定律、再取反的方式实现形式转换。

具体而言，若已知一个函数 f 的标准 SOP 形式，例如 f=∑mi (即所有使 f=1 的最小项之和)，那么其补函数 f′ 就是由其余最小项构成的和。但更有效的方法是：先将 f 表示为其最小项之和，然后对整个表达式取反得到 f′，此时 f′ 是若干乘积项的 OR 再取反，根据德·摩根定律，这等价于这些乘积项各自取反后的 AND。而每个最小项取反后恰好是一个最大项，因此 f′ 可写成若干最大项的积；再对 f′ 取反一次，即可得到原函数 f 的 POS 形式。不过更直接的做法是：函数的 POS 形式等于其补函数 SOP 形式中未出现的那些最大项的积，即若 f=∑m_i，则 f=∏M_j，其中 j 遍历所有不在 {i} 中的下标。

举个例子，设三元函数：

$$ \begin{align} f(x,y,z)\;&=\;\sum m(1,3,5,7)\\ &=\;m1+m3+m5+m7 \\ &=\;x'y'z+x'yz+xy'z+xyz \end{align} $$

该函数在输入 1、3、5、7 时为 1，因此在 0、2、4、6 时为 0。于是其标准 POS 直接由这些 0 点对应的最大项构成：

$$ \begin{align} f(x,y,z)\;&=\;\prod M(0,2,4,6)\\ &=\;M0 \cdot M2 \cdot M4 \cdot M6\\ &=\;(x+y+z)(x+y'+z)(x'+y+z)(x'+y'+z) \end{align} $$

反过来，若从该 POS 出发，也可通过观察哪些最大项缺失 (即 1、3、5、7 未出现)，推断出 SOP 应包含对应的最小项。这种对应关系本质上源于最小项与最大项的对偶性：

$$ \begin{align} M_i\;&=\;(m_i)' \\ \prod M(0,2,4,6)\;&=\;\sum m(1,3,5,7) \end{align} $$

因此函数的真值表一旦确定，其 SOP 与 POS 就如同一枚硬币的两面，可通过德·摩根定律在代数层面严格互化。尽管实际工程中很少直接进行这种完整展开式的转换 (因其可能指数级膨胀)，但理解这一互化机制对于掌握布尔函数的对称结构和逻辑完备性具有重要意义。

从真值表构造标准 SOP/POS 形式

从真值表构造布尔函数的标准形式，是连接函数语义与代数表达的关键步骤。给定一个包含 n 个变量的真值表，我们可以系统地生成两种规范表示：标准积之和 (SOP) 和标准和之积 (POS)。这两种形式虽然结构不同，但都唯一对应于该函数的行为。

构造标准 SOP 的核心思想是“聚焦函数为 1 的情形”。我们遍历真值表中所有输出 f=1 的行，对每一行，根据变量的具体取值写出一个最小项：若某变量在该行为 1，则保留其原变量；若为 0，则使用其补变量。这样构造出的乘积项 (AND 项) 恰好在该输入组合下为 1，其余情况下为 0。将所有这些最小项用逻辑或 (+) 连接起来，就得到了标准 SOP 表达式。例如，若某三元函数在输入 (x,y,z)=(0,1,1) 时输出为 1，则对应的最小项为 x′yz。

相比之下，标准 POS 则“关注函数为 0 的情形”。我们找出所有 f=0 的行，对每一行构造一个最大项：这里规则相反，若变量取值为 0，写原变量；若为 1，写补变量。这样设计是为了确保当该特定输入代入时，整个和项 (OR 项) 的值为 0。将所有这些最大项用逻辑与 (·) 相乘，便得到标准 POS 表达式。仍以 (x,y,z)=(0,1,1) 为例，若此行输出为 0，则对应的最大项为 x+y′+z′，因为代入后得 0+0+0=0。

这两种方法本质上是从互补视角刻画同一函数：SOP 明确列出所有使函数为真的输入组合，POS 则明确排除所有使函数为假的输入组合。

例如，考虑一个三变量函数 f(x,y,z)，其在输入 1、3、5、7 (即二进制 001、011、101、111) 时输出为 1，则其标准 SOP 为：

$$ f(x,y,z) = x'y'z + x'yz + xy'z + xyz $$

而由于它在输入 0、2、4、6 时输出为 0，其标准 POS 为：

$$ f(x,y,z) = (x+y+z)(x+y'+z)(x'+y+z)(x'+y'+z) $$

通过这种机械化的构造过程，任何真值表都能被精确转化为唯一的代数标准形式，为后续的化简、比较或电路实现奠定基础。

布尔表达式的化简

布尔表达式的化简是逻辑设计中的核心任务之一，其目标是在保持函数语义不变的前提下，减少表达式的复杂度 (如项数、文字数)，从而提升可读性、降低计算开销或为后续实现提供简洁形式。本节聚焦于代数化简法与卡诺图法 (作为纯代数工具)，并简要讨论无关项的处理。

■ 代数化简法：利用恒等式逐步简化

代数化简依赖布尔代数的基本公理与定理，通过等价变换逐步消去冗余项或合并相似项。常用技巧包括：

技巧	原理	示例
合并项	AB + AB′ == A (互补律 + 分配律)	xy + xy′ == x(y + y′) == x·1 == x
吸收冗余	A + AB == A	x + xyz == x
添加冗余项以促进合并 (共识定理)	AB + A′C + BC == AB + A′C (其中 BC 为冗余共识项)
德·摩根展开与重组	将复杂非运算展开以便化简	化简 f == x′y′z + x′yz + xy′ == x′z(y′ + y) + xy′ == x′z + xy′ (SOP)

代数法灵活但依赖经验，且难以保证全局最优。对于变量数较少 (≤4) 的情形，卡诺图提供了更系统、可视化的替代方案。

■ 卡诺图 (Karnaugh Map)

卡诺图作为一种二维真值表的可视化工具，其核心在于通过几何邻接的方式直观地反映逻辑相邻性。这种特性使得我们能够轻松识别并合并具有共同特征的项，从而简化布尔表达式。对于 2~4 变量的卡诺图构建来说，遵循一定的规则是关键。比如，在一个 2 变量 (x,y) 的卡诺图中，我们使用一个 2×2 的网格来表示，其中行和列分别对应变量 x 和 y 的状态，并按照格雷码顺序排列，以确保任何两个相邻单元之间仅有一个变量发生变化。这就意味着，如果从一个单元移动到另一个相邻单元，只会改变 x 或 y 中的一个，而另一个保持不变。

格雷码 (Gray code) 顺序为：00 → 01 → 11 → 10

例如：

┏━━━━━━━┳━━━━━━━┯━━━━━━━┓
┃       ┃  y=0  │  y=1  ┃
┣━━━━━━━╋━━━━━━━┿━━━━━━━┫
┃  x=0  ┃   1   │   0   ┃
┠───────╂───────┼───────┨
┃  x=1  ┃   1   │   1   ┃
┗━━━━━━━┻━━━━━━━┷━━━━━━━┛

注：在这个卡诺图中，每个单元格对应一个最小项：
    (1) 左上 (x=0, y=0) -> m₀=x′y′
    (2) 右上 (x=0, y=1) -> m₁=x′y
    (3) 左下 (x=1, y=0) -> m₂=xy′
    (4) 右下 (x=1, y=1) -> m₃=xy

函数值 f(x,y)=1 的位置是 m₀、m₂、m₃，因此该函数的标准 SOP 为：f(x,y)=x′y′+xy′+xy。在卡诺图中，我们可以圈出：

一个竖直的 2 格圈 (左列：m₀ 和 m₂)，对应 y'
一个水平的 2 格圈 (底行：m₂ 和 m₃)，对应 x

合并后得到最简 SOP：f(x,y)=y′+x (尽管 m₂ 被两个圈同时覆盖，这是允许的，且有助于实现更简表达式)

当扩展到 3 变量或 4 变量时，卡诺图的设计原则依然强调了这一逻辑相邻性的概念。例如，在 3 变量的卡诺图中，我们通常会采用 2 行乘以 4 列的形式，以便于展现所有可能的变量组合。而对于 4 变量的情况，则是一个 4×4 的网格，每个维度都用 2 位格雷码表示，确保了相邻单元间的逻辑一致性。这样的设计不仅便于理解和应用，而且为后续的圈组操作奠定了基础。

┏━━━━━━━┳━━━━━━━┯━━━━━━━┯━━━━━━━┯━━━━━━━┓      ┏━━━━━━━┳━━━━━━━┯━━━━━━━┯━━━━━━━┯━━━━━━━┓
┃       ┃ yz=00 │ yz=01 │ yz=11 │ yz=10 ┃      ┃       ┃ cd=00 │ cd=01 │ cd=11 │ cd=10 ┃
┣━━━━━━━╋━━━━━━━┿━━━━━━━┿━━━━━━━┿━━━━━━━┫      ┣━━━━━━━╋━━━━━━━┿━━━━━━━┿━━━━━━━┿━━━━━━━┫
┃  x=0  ┃   m₀  │   m₁  │   m₃  │   m₂  ┃      ┃ ab=00 ┃   m₀  │   m₁  │   m₃  │   m₂  ┃
┠───────╂───────┼───────┼───────┼───────┨      ┠───────╂───────┼───────┼───────┼───────┨
┃  x=1  ┃   m₄  │   m₅  │   m₇  │   m₆  ┃      ┃ ab=01 ┃   m₄  │   m₅  │   m₇  │   m₆  ┃
┗━━━━━━━┻━━━━━━━┷━━━━━━━┷━━━━━━━┷━━━━━━━┛      ┠───────╂───────┼───────┼───────┼───────┨
                                               ┃ ab=11 ┃   m₁₂ │   m₁₃ │   m₁₅ │   m₁₄ ┃
                                               ┠───────╂───────┼───────┼───────┼───────┨
                                               ┃ ab=10 ┃   m₈  │   m₉  │   m₁₁ │   m₁₀ ┃
                                               ┗━━━━━━━┻━━━━━━━┷━━━━━━━┷━━━━━━━┷━━━━━━━┛
注：左图为 3 变量卡诺图 f(x,y,z)，右图为 4 变量卡诺图 f(a,b,c,d)

在进行最简 SOP 求解时，我们需要根据给定的函数值分布情况，在卡诺图上圈出所有的 1。这个过程要求每个圈必须包含 2^k 个 1 (这里的 k 可以是0、1、2等)，并且尽可能大，以此消去更多变量，减少最终表达式的复杂度。值得注意的是，允许重叠圈的存在，这意味着同一位置的 1 可以被多个圈覆盖，只要这样做有助于简化表达式。此外，由于采用了格雷码的循环特性，卡诺图的边缘被视为相互连接的，这允许我们在边界处进行环绕圈选。

举个具体的例子来说明这一点：假设在一个 3 变量的卡诺图中，最小项 m₁、m₃、m₅、m₇ 对应的函数值均为 1，即所有 z=1 的情况。这时，我们可以圈出一个包含这四个位置的竖条，该圈实际上代表了一个乘积项，即 AND 项，其中 z 保持不变，而 x 和 y 则因为在这个圈内发生了变化而被消去，从而得到简化后的表达式为 z。

至于求最简 POS (主合取范式)，有两种方法可以实现。

一种方法是对原函数的补集进行卡诺图绘制，也就是圈出所有函数值为 0 的位置，然后求得这些位置上的最简 SOP 形式，并对结果取反。通过德·摩根定律转换后，即可得到所需的 POS 形式。
另一种直接的方法是在原始卡诺图上圈出所有的 0，每一个圈生成一个和项 (OR项)，最后将这些项相与。

这两种方法各有千秋，但它们的目的都是为了找到布尔函数的一种更简洁的表达方式，以便于进一步的分析和优化。无论选择哪种方法，理解卡诺图的基本原理和圈组规则都是至关重要的。

■ 冗余项与无关项 (Don’t-care Conditions)

在某些应用场景中，函数的部分输入组合永远不会出现或输出值无关紧要 (如编码器非法输入、未使用的状态) 。这些输入对应的输出可自由指定为 0 或 1，称为无关项 (Don’t-care conditions) ，记作 d 或 X。

在化简中，无关项可当作 1 或 0 使用，以帮助形成更大的圈组。目标是辅助主项 (必须覆盖的 1) 的化简，而非必须覆盖无关项。若将某无关项视为 1 能使表达式更简，则采用；否则忽略。

注意：无关项不是函数定义的一部分，仅是优化时的自由度。在纯数学布尔函数中通常不考虑，但在工程建模中极为重要。

参考文档

[1] 硬件设计创新, 卡诺图化简练习, https://zhuanlan.zhihu.com/p/578828158

课后练习：常用复合逻辑门的布尔表示

■ 异或 (Exclusive OR, XOR, ⊕) 化简：用基本运算表示 XOR

// 定义描述
if a≠b output 1
else output 0
// 化简过程
a Xor b == (a + b)(a′ + b′)  // POS
        == a·a′ + a·b′ + b·a′ + b·b′
        == a·b′ + b·a′  // SOP
        == a And Not(b) Or b And Not(a)

可以看出，只需要 2 个与门、2 个非门，以及 1 个或门即可实现 XOR

■ 同或 (XNOR, ⊙) 化简：用基本运算表示 XNOR

// 定义描述
if a=b output 1
else output 0
// 化简过程
a Xnor b == a·b + a′·b′
         == a And b Or Not(a) And Not(b)

可以看出，只需要 2 个与门、2 个非门，以及 1 个或门即可实现 XNOR

■ 与非 (NAND) 化简：用基本运算表示 NAND

// 定义描述
if a=b=1 output 0
else output 1

┏━━━━━━━━━━━━━━━━━━━━━━━┓
┃      Truth Table      ┃
┣━━━━━━━┯━━━━━━━┳━━━━━━━┫
┃   a   │   b   ┃ Nand  ┃
┣━━━━━━━┿━━━━━━━╋━━━━━━━┫
┃   0   │   0   ┃   1   ┃
┠───────┼───────╂───────┨
┃   0   │   1   ┃   1   ┃
┠───────┼───────╂───────┨
┃   1   │   0   ┃   1   ┃
┠───────┼───────╂───────┨
┃   1   │   1   ┃   0   ┃
┗━━━━━━━┷━━━━━━━┻━━━━━━━┛

// 通过真值表法可得，输出为 1 的行有 m₀、m₁、m₂
a Nand b == m₀ + m₁ + m₂
         == a′b′ + a′b + ab′  // SOP
         == a′(b′+ b) + ab′ // a′·1 + ab′，互补律
         == a′ + ab′
         == a′ + b′  // 广义吸收率 a + a′·b == a + b
         == (ab)′  // 德·摩根定律
         == Not(a And b)

因此，只需要 1 个与门、1 个非门即可实现 NAND

■ 或非 (NOR) 化简：用基本运算表示 NOR

// 定义描述
if a=b=0 output 1
else output 0

┏━━━━━━━━━━━━━━━━━━━━━━━┓
┃      Truth Table      ┃
┣━━━━━━━┯━━━━━━━┳━━━━━━━┫
┃   a   │   b   ┃ Nand  ┃
┣━━━━━━━┿━━━━━━━╋━━━━━━━┫
┃   0   │   0   ┃   1   ┃
┠───────┼───────╂───────┨
┃   0   │   1   ┃   0   ┃
┠───────┼───────╂───────┨
┃   1   │   0   ┃   0   ┃
┠───────┼───────╂───────┨
┃   1   │   1   ┃   0   ┃
┗━━━━━━━┷━━━━━━━┻━━━━━━━┛

// 通过真值表法可得
a Nor b == m₀
        == a′·b′  // SOP
        == (a + b)′  // 德·摩根定律
        == Not(a Or b)

因此，只需要 1 个或门、1 个非门即可实现 NAND