第2章 布尔代数与逻辑门（数学基础）
一、导读
1.1 本章学习目标
掌握布尔代数的三种基本运算（AND、OR、NOT）及其组合运算（NAND、NOR、XOR、XNOR）
理解布尔代数的基本定律和定理，包括交换律、结合律、分配律、德摩根定律等
学会使用真值表（Truth Table）完整描述逻辑函数
掌握逻辑表达式的代数化简方法，能够运用布尔定律简化电路
理解对偶性（Duality）原理及其在逻辑化简中的应用
认识基本逻辑门的电路符号、功能表和实际器件
了解万能门（Universal Gate）的概念，理解为什么NAND和NOR可以实现所有逻辑功能
掌握从文字描述到逻辑表达式的建模方法
1.2 为什么本章如此重要
布尔代数是整个数字逻辑设计的数学基石。如果说第1章让我们认识了数字世界的基本面貌，那么本章则赋予了我们描述和操作这个世界的数学语言。1854年，英国数学家George Boole提出了布尔代数的理论框架，他或许没有预见到，这套处理二值变量的代数系统将在近一个世纪后成为电子工程的数学基础。
在实际的数字电路设计中，每一个逻辑门、每一条信号通路、每一个功能模块，其行为都可以用布尔代数来精确描述。设计一个数字电路的过程，本质上就是将功能需求转化为布尔表达式，再通过逻辑门实现这个表达式的过程。布尔代数的定律和定理为我们提供了分析和优化这些表达式的工具，使得我们能够用最少的逻辑门实现所需的功能，从而降低电路的成本、功耗和面积。
更重要的是，布尔代数建立了数学抽象与物理实现之间的桥梁。通过真值表，我们可以穷举所有可能的输入组合来验证逻辑功能的正确性；通过代数化简，我们可以在不改变功能的前提下减少硬件资源的使用；通过对偶性原理，我们可以发现不同逻辑表达式之间的深层联系。这些能力是每一位数字电路工程师的基本功。
1.3 核心问题引导
布尔代数与普通代数有什么相同点和不同点？为什么布尔代数只有0和1两个值？
AND、OR、NOT三种基本运算各自的逻辑含义是什么？它们的真值表如何？
什么是德摩根定律（De Morgan's Theorem）？为什么它在逻辑化简中如此重要？
如何用真值表来表示一个逻辑函数？从真值表到逻辑表达式的转换方法是什么？
NAND门和NOR门为什么被称为万能门？如何用NAND门实现其他所有逻辑功能？
对偶性原理的内容是什么？如何利用对偶性来验证或推导布尔恒等式？
逻辑表达式的化简对实际电路设计有什么意义？化简的目标是什么？
二、核心概念详解
2.1 基本逻辑运算与复合逻辑运算
布尔代数定义了三种基本逻辑运算：与（AND）、或（OR）、非（NOT）。与运算（也称为逻辑乘）只有当所有输入都为1时输出才为1，否则输出为0。对于两输入与门，其布尔表达式为 Y = A AND B = A * B = AB。或运算（也称为逻辑加）只要有一个输入为1输出就为1，只有所有输入都为0时输出才为0。两输入或门的表达式为 Y = A OR B = A + B。非运算（也称为逻辑反或取反）将输入值翻转，0变为1，1变为0，表达式为 Y = NOT A = A' = /A。
由这三种基本运算可以组合出多种复合逻辑运算。与非（NAND）是与运算后接非运算，即 Y = (AB)'。或非（NOR）是或运算后接非运算，即 Y = (A+B)'。异或（XOR）当两个输入不同时输出为1，相同时输出为0，表达式为 Y = A XOR B = AB' + A'B。同或（XNOR）是异或的反运算，当两个输入相同时输出为1。
在实际的数字集成电路中，基本的逻辑门以标准器件的形式提供。例如，74系列TTL器件中，74LS08是四路2输入与门，74LS32是四路2输入或门，74LS04是六路非门，74LS00是四路2输入与非门。了解这些标准器件的引脚排列和功能对于实际的电路设计非常重要。
2.2 真值表与逻辑函数表示
真值表（Truth Table）是描述逻辑函数最直观、最完整的方法。它列出所有可能的输入组合以及每种组合对应的输出值。对于n个输入变量的逻辑函数，真值表共有2^n行，因为每个变量可以取0或1两个值。例如，2输入逻辑函数的真值表有4行，3输入的有8行，4输入的有16行。
从真值表可以直接写出逻辑函数的标准表达式。如果关注输出为1的行，可以写出积之和（Sum of Products, SOP）形式：对于每一个输出为1的行，写出一个乘积项（最小项），其中输入为1的变量以原变量形式出现，输入为0的变量以反变量形式出现，然后将所有乘积项相加。例如，对于一个2输入函数，如果真值表中第1行（A=0,B=1）和第2行（A=1,B=0）的输出为1，则SOP表达式为 F = A'B + AB'。
反之，如果关注输出为0的行，可以写出和之积（Product of Sums, POS）形式：对于每一个输出为0的行，写出一个和项（最大项），其中输入为0的变量以原变量形式出现，输入为1的变量以反变量形式出现，然后将所有和项相乘。SOP和POS是同一逻辑函数的两种等价表示，可以根据设计需求选择更简洁的形式。
2.3 布尔代数定律与化简规则
布尔代数拥有一套完整的定律体系，这些定律是逻辑表达式化简的理论基础。基本定律包括：
交换律：A + B = B + A，AB = BA。说明运算的顺序不影响结果。
结合律：(A + B) + C = A + (B + C)，(AB)C = A(BC)。说明多个变量进行同类运算时，分组方式不影响结果。
分配律：A(B + C) = AB + AC，A + BC = (A + B)(A + C)。注意第二个分配律是布尔代数特有的，在普通代数中不成立。
互补律：A + A' = 1，A * A' = 0。一个变量与其反变量的或为1，与为0。
幂等律：A + A = A，A * A = A。同一变量的重复运算可以简化。
吸收律：A + AB = A，A(A + B) = A。这是化简中常用的重要定律，可以消除多余的项。
德摩根定律：(A + B)' = A' B'，(AB)' = A' + B'。德摩根定律描述了与运算和或运算在对偶意义下的等价关系，是逻辑化简和电路变换中最常用的工具之一。它不仅适用于两个变量，可以推广到任意多个变量：(A + B + C + ...)' = A' B' C' ...。
2.4 对偶性原理
对偶性（Duality）是布尔代数中一个优美而实用的性质。布尔代数中的每个恒等式都有一个对偶式（Dual），通过将表达式中的AND运算符（*）与OR运算符（+）互换、常量0与1互换得到。注意，对偶变换不改变变量的取反状态。
例如，恒等式 A + 0 = A 的对偶式是 A * 1 = A。恒等式 A + BC = (A + B)(A + C) 的对偶式是 A(B + C) = AB + AC，恰好就是另一个分配律。这意味着，如果我们证明了一个布尔恒等式成立，那么它的对偶式也自动成立，无需额外证明。这一性质大大减少了需要记忆的恒等式数量。
对偶性原理在逻辑设计中有多方面的应用。首先，它可以帮助我们验证化简结果的正确性：如果一个化简步骤的对偶步骤也是合法的，那么原步骤就是正确的。其次，在电路设计中，如果一个电路使用AND和OR门实现了某个功能，那么将AND门和OR门互换、将0和1互换后得到的对偶电路将实现对偶功能。这种对称性为设计者提供了额外的灵活性。
2.5 万能门：NAND与NOR
NAND门和NOR门被称为万能门（Universal Gate），因为仅使用NAND门（或仅使用NOR门）就可以实现所有布尔逻辑功能。这一性质在集成电路设计中具有重要意义，因为使用单一类型的门来构建整个电路可以简化制造工艺、提高芯片良率。
用NAND门实现其他逻辑门的方法如下：非门——将一个NAND门的两个输入端连接在一起，即 NOT A = NAND(A, A) = (AA)' = A'。与门——在NAND门后接一个NAND实现的非门，即 AND(A, B) = NOT(NAND(A, B)) = ((AB)')' = AB。或门——利用德摩根定律，A + B = (A' B')' = NAND(A', B') = NAND(NAND(A,A), NAND(B,B))。
在实际的CMOS集成电路中，NAND和NOR门的晶体管数量比AND和OR门更少（2输入NAND需要4个晶体管，而2输入AND需要6个——4个NAND加2个反相器），因此使用NAND和NOR作为基本构建单元更加高效。现代标准单元库（Standard Cell Library）中通常包含NAND、NOR、反相器等多种基本门电路，综合工具会根据优化目标自动选择最合适的门类型。
三、深入分析与讨论
3.1 逻辑完备性与功能封闭性
逻辑完备性（Functional Completeness）是布尔代数中的一个重要概念。一个逻辑运算符集合被称为功能完备的，如果仅使用该集合中的运算符就可以表达所有可能的布尔函数。{AND, OR, NOT}构成一个功能完备集，这是最直观的完备集。
{NAND}和{NOR}各自单独就构成功能完备集，这一事实在工程上非常重要。CMOS工艺中，NAND和NOR门的实现效率最高（晶体管数量最少、速度最快），因此许多集成电路的设计方法论都以NAND或NOR为基础。例如，NMOS逻辑主要使用NOR门，而CMOS逻辑中NAND和NOR都是常用的基本门。
更一般地，Post完备性定理给出了一个逻辑运算符集合功能完备的充要条件。根据这一定理，{XOR, 1}也是功能完备的（因为A' = XOR(A, 1)，A AND B = XOR(XOR(A, 1), XOR(B, 1))再取反等等，虽然实现起来不够高效）。理解逻辑完备性有助于我们认识到，数字电路的设计存在多种等价的基本门选择，工程上的选择取决于具体的工艺特性和优化目标。
3.2 从布尔表达式到逻辑电路的映射
将布尔表达式映射为逻辑电路是数字设计的核心任务之一。同一个布尔函数可以有多种等价的表达式，每种表达式对应不同的电路实现。例如，函数 F = AB + AC 可以直接用两个与门和一个或门实现（共3个门），也可以通过代数变换写成 F = A(B + C)，只需要一个或门和一个与门（共2个门）。
电路优化的目标通常包括：最小化门的数量（减少面积和成本）、最小化逻辑层级数（减少传播延迟、提高速度）、最小化每个门的输入端数（减少晶体管数量和功耗）。这些目标之间往往存在矛盾，设计者需要根据具体的应用需求进行权衡。
例如，在FPGA（Field Programmable Gate Array）中，基本的逻辑单元是查找表（Look-Up Table, LUT），它可以实现任意不超过特定输入数（如4或6个输入）的布尔函数。在这种情况下，将逻辑函数映射为最少数量的LUT成为优化目标，而传统的门级优化指标可能不再是主要考量。
四、实践案例
4.1 三人投票电路的设计
设计一个三人投票电路：三个评委各有一个投票按钮（A、B、C），按下为1，不按为0。当多数评委同意（至少两人按下）时，提案通过（输出Y=1）。
首先建立真值表。列出所有8种输入组合，统计每种组合中1的个数，当个数大于等于2时输出为1。得到：Y = A'BC + AB'C + ABC' + ABC。
利用布尔代数化简：Y = A'BC + AB'C + ABC' + ABC = A'BC + AB'C + AB(C' + C) = A'BC + AB'C + AB = A'BC + A(B'C + B) = A'BC + A(B + C) = A'BC + AB + AC = BC(A' + A) + AB + AC - 需要更仔细地化简。
正确化简过程：Y = A'BC + AB'C + ABC' + ABC。合并最后两项：ABC' + ABC = AB。所以 Y = A'BC + AB'C + AB。再对前两项提取：A'BC + AB'C = C(A'B + AB') = C(A XOR B)。所以 Y = AB + C(A XOR B) = AB + AC + BC（展开后验证）。
最终表达式 Y = AB + BC + AC 是最简SOP形式，可以用3个2输入与门和1个3输入或门实现，共4个门。
4.2 用NAND门实现组合逻辑
将上述投票电路 Y = AB + BC + AC 转换为仅使用NAND门的形式。首先对表达式两次取反：Y = ((AB + BC + AC)')' = ((AB)' (BC)' (AC)')'（应用德摩根定律）。
观察这个表达式：(AB)' 是一个NAND门，(BC)' 是一个NAND门，(AC)' 是一个NAND门，最后三者的NAND是另一个NAND门。因此，整个电路可以用4个2输入NAND门实现，无需使用其他类型的门。
这个例子展示了万能门概念的实用价值。在实际的集成电路制造中，如果工厂的标准单元库中NAND门的性能最优（速度最快、面积最小），那么将所有逻辑转换为NAND实现可以获得更好的电路性能。
五、常见误区与注意事项
混淆布尔代数与普通代数：布尔代数中没有减法、除法，也没有负数。A + A = A（而非2A），A * A = A（而非A的平方）。在布尔代数中，变量的取值只有0和1。
忽略德摩根定律的推广形式：德摩根定律不仅适用于两个变量，对任意多个变量同样成立。例如，(A + B + C)' = A' B' C'，而不是 A' + B' + C'。这是初学者常犯的错误。
真值表行序与最小项编号的对应：真值表的每一行对应一个最小项，行号（从0开始）就是最小项的编号。例如，第5行（二进制101）对应最小项 m5 = A'BC'。在从真值表写表达式时，要注意这种对应关系。
过度化简导致功能改变：在化简过程中，每一步变换都必须严格遵循布尔代数的定律。随意合并或删除项可能导致逻辑功能改变。建议化简后通过真值表验证结果的正确性。
忽视逻辑门的扇入限制：实际器件的每个门有最大输入端数限制。例如，标准的74系列器件中，与门和或门通常只有2输入、3输入或4输入的规格。如果化简结果中出现5输入以上的门，需要进一步分解为多级电路。
六、本章小结
本章系统介绍了布尔代数的基本原理和逻辑门的基本知识。我们学习了AND、OR、NOT三种基本运算以及NAND、NOR、XOR、XNOR等复合运算，掌握了用真值表完整描述逻辑函数的方法。布尔代数的定律体系——特别是德摩根定律和吸收律——为逻辑表达式的化简提供了强大的工具。对偶性原理揭示了布尔代数的内在对称美，也简化了恒等式的验证过程。NAND和NOR作为万能门的重要性质，在集成电路设计中具有实际的工程意义。这些数学工具和概念构成了数字逻辑设计的语言基础，是后续章节学习组合逻辑综合和时序电路设计的必要前提。
七、思考题与练习
证明以下布尔恒等式：(a) A + A'B = A + B (b) (A + B)(A + C) = A + BC (c) AB + A'C + BC = AB + A'C（一致性定理）。
写出以下逻辑函数的对偶式：(a) F = A(B + C') + D (b) G = (A + B)(C + D'E) (c) H = A + B'C + 0。
用真值表验证德摩根定律：(a) (AB)' = A' + B' (b) (A + B + C)' = A'B'C'。
将布尔函数 F(A,B,C) = AB + A'C 转换为标准SOP形式（最小项之和）和标准POS形式（最大项之积）。
仅使用NOR门实现以下逻辑函数：(a) F = A'B + AB' (XOR) (b) G = AB + CD。画出对应的逻辑电路图。
一个4输入多数函数，当4个输入中有3个或更多为1时输出为1。请写出该函数的真值表，求出最简SOP表达式，并计算实现该函数所需的逻辑门数量。
证明：如果一个布尔恒等式成立，则其对偶式也必然成立。提示：考虑对偶变换对布尔代数公理体系的影响。
在实际的CMOS电路中，为什么2输入NAND门比2输入AND门更高效？请从晶体管数量和信号传播延迟两个角度进行分析。