第 4 章　逻辑门：与、或、非

4.1布尔逻辑：真与假也能做代数

计算机处理的是「二选一」——0 和 1。但光有 0 和 1 还不够，我们要能对它们做运算。早在 19 世纪，一位英国数学家就为「真/假」这类两值问题建立了一套完整的代数，这就是 布尔代数（Boolean algebra）。

布尔代数的核心是：变量只有 0 和 1 两个值，运算规则只有少数几条。我们把「真」记作 1，「假」记作 0——于是「逻辑」和「二进制」完美合一。

它和「普通代数」哪里不一样？

刚接触布尔代数，最容易犯的错是把它当成算术。试试这个「怪题」：在布尔代数里，1 + 1 = 1，不是 2，也不是 10（二进制进位）。这里的「+」是「或」：两个真命题，任一为真结果就为真；两个都真，结果还是真——「真上加真」并不会更真。同理，1 × 1 = 1、1 + 0 = 1、0 × 1 = 0，乘法对应「与」。数值没有大小、不能累加，只有「真/假」两种状态。一旦习惯这一点，布尔运算就会变得像查表一样确定。

为什么这套「怪代数」能落地成电路？因为布尔变量只有两个值，而上一章我们看到，MOSFET 这类开关恰好也只有两种稳定状态——导通与截止、高与低、1 与 0。变量的取值范围和开关的状态范围严丝合缝，这是布尔代数能被电路「实体化」的根本原因。

从纸面到金属：真假即高低电压

布尔的「真/假」落到电路里，就是我们熟悉的高电平/低电平。工程上通行的是正逻辑约定：高电压代表 1，低电压代表 0——上一章 CMOS 非门里 Vdd=1、GND=0 用的正是这一套。（用低电压代表 1 的「负逻辑」也存在，本套书不采用。）为什么高/低能稳稳当当地表达真/假？第 2 章讲过噪声容限：CMOS 高电平至少 4.5V、低电平至多 0.5V，判 1 判 0 各有约 1V 的余量，中间的「无人区」由门电路主动制造。逻辑世界的「非黑即白」，是靠电路的电压纪律买来的。

延伸：布尔代数与集合论是同一张脸

布尔代数与集合论结构相同：AND 对应「交集」（两个集合都包含的元素），OR 对应「并集」（任一集合所含），NOT 对应「补集」（全集里剩下的部分）。文氏图里两个圆圈相交的那块，就是 A AND B。这层对应很有用：对某条逻辑表达式拿不准时，把它翻译成集合语言在图上画一画，对错常常一眼可见。布尔当年研究的是概念与类，{0,1} 在他那里只是特例；香农把这个特例焊到电路上，反而成就了整门数字技术。

布尔代数的「九九表」：常用运算律

算术有九九乘法表，布尔代数也有自己的口诀。设 Ā 表示 NOT A，「+」表示 OR、「·」表示 AND：

特别看一眼分配律的或版本 A+B·C = (A+B)·(A+C)——它在普通代数里完全不成立（算术的 a+bc ≠ (a+b)(a+c)），但在布尔代数里八种组合逐行验证成立：逻辑没有大小，只有真假的叠加。这张表不必背，第 5 章化简电路时它会自然长在手上——比如吸收律能把 A+A·B 直接缩成 A，一半的电路就省下来了。

几条定律值得单独点名：幂等律 A+A=A 说「真加上真还是真」——重复的告警条件不必装两盏灯；互补律 A+Ā=1 说「命题与它的否定至少一个成立」——正是上一章补码圆环「非负数右半圈、负数左半圈」那种二分世界的逻辑版；吸收律则专门砍冗余电路。定律不是装饰，每一条都对应一处真实的省工。

4.2三种基本门：与、或、非

布尔代数里最基本的三种运算，对应三种最基本的电路，统称 逻辑门（logic gate）。「门」这个名字很形象：输入信号从一侧进来，经过「门」的判断，决定输出是 0 还是 1。

先回答一个常见的疑问：变量为什么只留 0 和 1 两个值？电压明明可以分三档、四档，信息量更大。三值逻辑确实被造出来过——第 2 章介绍过的三进制计算机 Сетунь 性能不俗，但工程代价压倒了信息优势：状态越多，各状态之间的判别窗口越窄、噪声容限越小，每种门的组合数还翻着倍地涨。二值是把「容错」推到极致的选择——宁可每个符号少带点信息，也要每次判断都稳如磐石。本章所有内容都建立在这个前提上：每个变量、每根线、每个门，都只认 0 和 1。

非门（NOT）：取反

非门最简单：输入 0 输出 1，输入 1 输出 0。它把信号「翻个面」，所以也叫反相器（inverter）。

与门（AND）：都真才真

与门对应日常的「且」：只有两个输入都是 1，输出才是 1；只要有一个是 0，输出就是 0。好比「门要两把钥匙都插上才开」。

或门（OR）：有真就真

或门对应日常的「或」：只要两个输入里有任意一个是 1，输出就是 1；只有两个都是 0，输出才为 0。好比「两扇门，打开任意一扇都能进去」。

看懂「门」的符号语言

翻开任何一份数字电路图，你都会看到三种基本形状：D 形（平背圆弧，代表与门）、盾形（尖背圆弧，代表或门）、三角加小圆圈（非门）。符号的规律极其简单：小圆圈（泡泡）= 取反。D 形加个泡泡就是与非门（NAND），盾形加个泡泡就是或非门（NOR），三角加个泡泡就是非门。记住「形状定功能、泡泡定取反」，你就能看懂绝大多数电路图，不必死记硬背每种门的画法。

另外，门的输入不止两个。工业标准库里有两输入、三输入、四输入乃至八输入的与门、或门——符号还是那个形状，只是多几条「腿」；行为规则不变，3 输入 AND 就是「三个都 1 才 1」。多输入门内部仍是标准结构的组合（或直接做成多管 CMOS 阵列），所以看图时不必被「腿多」吓住。

还有一件事值得留心：中文里说「或」，多数时候指的是二选一——「咖啡或茶」，默认不能两个都要。但逻辑里的「或」是兼容或（inclusive OR）：两个都为真时，结果照样为真。想要「二选一、不许多」的逻辑，得用另一种门——异或门（XOR）：A ≠ B 时输出 1，A = B 时输出 0。它专门负责「不同才真」的判断，比如比较两个 bit 是否一致。XOR 我们先记下名字，它在本套书后面讲加法器和校验时会反复登场。

XOR 的「异」就是「相异」：A、B 相异才输出 1。给你一个马上能用的例子：两台设备各自报送同一个状态 bit，把两个 bit 送进 XOR，输出 1 就说明两边数据不一致，触发复检——它天生是最小的「不一致探测器」。第 7 章加法器、第 9 章校验位，全靠它串场。

顺带注意：XOR 没有专属自己的四管 CMOS 结构——它由 AND、OR、NOT 组合而成。这也从侧面印证了下一节的断言：几种基本门，搭得出一切。

把本章认识（和打过照面）的门整理成一张速查表，随身携带：

前五种本章都正面讲过；XOR 在 4.2 打过照面。它们之间的换算关系（谁能用谁搭出来），4.5 节会给出完整答案。

看这张表还有个习惯值得养成：扫一眼「输出 1 的行数」。AND 只在 1 行输出 1（最挑剔），OR 在 3 行输出 1（最宽容），XOR 恰好一半一半（2 行）——同一张 4 行真值表，输出 1 的分布就是门的「性格」。以后拿到陌生的真值表，先数输出 1 有几行、再看它们落在哪些组合上，门的行为往往一眼定性；这一手「先数后读」，下一章设计组合逻辑时天天用得上。

4.3真值表：穷尽所有可能

逻辑门的行为，可以用一张 真值表（truth table）完全说清：把输入的所有组合都列出来，对应写出输出。因为输入只有 0/1，两个输入的组合一共就 2×2 = 4 种，一张小表就能「穷尽一切」。

真值表看起来简单，却是数字电路设计的第一工具：任何复杂的逻辑，都可以先用真值表精确描述，再一步步转化成电路。后面每一章，你都会反复见到它。

输入变多，表怎么长？——2ⁿ 行

每个输入都有 0/1 两种取值，彼此独立，所以 n 个输入的完整真值表共 2ⁿ 行：2 输入 4 行，3 输入 8 行，4 输入 16 行。行数随输入个数指数增长——这是真值表「穷尽一切」的威力，也是它的软肋：输入到十几二十个时，手工列全一张表已经不现实，工程师就要改用化简法（第 5 章会见到）。但在本套书面对的 2~4 输入场景，列真值表永远是最可靠的第一步：不怕遗漏、不怕想偏，照表施工就行。

「2ⁿ」从哪儿来？每个新输入都是一个独立的「0/1 二选一」：每多一个输入，就要把原有每一行各复制一次、一次填 0、一次填 1——行数翻倍。2 输入 4 行，3 输入 8 行，4 输入 16 行，逐级翻番。写程序穷举时，两层 for 循环恰好把这件事做干净——下面的代码例题就带你走一遍。

真值表和门电路之间可以双向翻译：给需求列真值表，就能照表搭出门电路；反过来，拿到一张陌生的门电路图，逐组代入输入画出真值表，它的行为也立刻原形毕露。下面这道例题走一遍「从需求到真值表」的全过程。

真值表不止能「验」，还能「翻」——把表中输出为 1 的行各写成一个「与项」，再用「或」连起来，就得到这个逻辑的表达式。以上面的表决器为例，输出为 1 的前三行各对应一个「两人同意」的与项：011 对应 B·C，101 对应 A·C，110 对应 A·B；最后一行 111（三人全同意）已被前三项覆盖——三人全同意时，任何「两人组合」自然都同意。于是表决器可以写成 M = A·B + B·C + A·C，读作「任意两人同意即通过」。这个把真值表翻译成表达式的方法叫「最小项之和」，是下一章从表走向电路的正式路线，这里先见它一面。

把本章过手的方法收拢成一条四步流水线：① 定义变量（明确 1 代表什么）；② 列全 2ⁿ 行真值表；③ 读表写出表达式（最小项之和）；④ 用门实现，并逐行验证。第 ③④ 步之间还藏着一门手艺——化简：同一个真值表可以写出许多等价表达式，电路代价却天差地别；怎样用最少的门、最短的延迟实现同一张表，正是下一章的正题。

还有一句行规：四步里的「验证」最常被新手省略，工程上却恰恰相反——电路每改一次，就把真值表对照重跑一遍，这是防止「改一处、坏两处」的最低成本保险。

print("A B | AND OR XOR")
for A in (0, 1):
    for B in (0, 1):
        print(f"{A} {B} |  {A & B}    {A | B}    {A ^ B}")

A B | AND OR XOR
0 0 |  0    0    0
0 1 |  0    1    1
1 0 |  0    1    1
1 1 |  1    1    0

4.4晶体管如何搭出「非门」和「与非门」

逻辑门不是抽象符号，它是由真实晶体管搭出来的。最容易理解的是用 MOSFET 搭非门。

非门：一个「上拉」加一个「下拉」开关

一个非门由两个 MOSFET串联「接力」组成：上面一个 P 型管（栅压低时导通），下面一个 N 型管（栅压高时导通）。输出点接在两者之间。

顺便收编两个高频黑词：「上拉」指把输出点拉向电源（高电平），「下拉」指把输出点拉向地（低电平）——上面这只 P 管、下面这只 N 管干的就是这两件事。CMOS 里由晶体管亲自出面拉；更简单的电路也可以用电阻拉，代价是持续漏电。以后见到「上拉电阻」「下拉管」，默念「把电位拉向哪一边」就不会迷路。

关键在「一个通，另一个就断」的接力逻辑：

• 输入 A = 1（高电压）：N 管导通、P 管截止。输出 Y 通过 N 管连到「地」（0），所以 Y = 0。
• 输入 A = 0（低电压）：P 管导通、N 管截止。输出 Y 通过 P 管连到「电源」（1），所以 Y = 1。

输入被翻了个面——这就是非门。

与非门（NAND）：先与后非

与非门（NAND）就是「与门 + 非门」的组合：只有当两个输入都为 1 时输出才为 0，其余情况输出都是 1。它等于把与门的结果取反。为什么单挑它出来讲？因为下一节你会发现——它是万能的门。

与非门的晶体管版：「上并下串」

非门是 1 个输入对 2 个管子；与非门有 2 个输入，晶体管数也翻倍：2 个 P 管 + 2 个 N 管，共 4 只。结构口诀是「上并下串」：两个 P 管并联在电源与输出之间，两个 N 管串联在输出与地之间。输入 A 接「一个 P 管栅极 + 一个 N 管栅极」，输入 B 接另外一对。为什么恰好这么接？把 4 种输入组合代进去走一遍，你会看到「并联/串联」与「都/任一」的对应关系天衣无缝——这正是下一道例题要做的。

打个对台：或非门（NOR）的 CMOS 结构恰好倒个个儿——上串下并：P 管串联在电源与输出之间，N 管并联在输出与地之间。为什么互换得如此整齐？NAND 要「N 管都导通才拉低」，所以 N 走串联；NOR 要「N 管任一导通就拉低」，所以 N 走并联——串联配「都」，并联配「任一」，规则完全对称。这也顺带解释了工艺偏爱：P 管里的空穴跑得比 N 管里的电子慢，NOR 把两只慢 P 管串在一条路上，速度吃亏；NAND 把慢家伙放进了并联路——同工艺下 NAND 更快、更省面积，这就是「工程师选 NAND 当标准积木」的电路层原因。

门不是瞬时的：传播延迟

还有一件实物的事必须交代：信号穿过一个门不是瞬时的，需要一点时间——传播延迟（propagation delay），CMOS 门典型在皮秒到几十皮秒量级。单个门看着无所谓，但信号串联穿过十个门，延迟就乘十；下一章做多位加法器时，「低位算完、进位才传到高位」的进位延迟就是整机速度的瓶颈。名字先记住，第 5 章正面遭遇它。

顺带回答一个常见疑问：CMOS 静态几乎不耗电（上一章的结论），那电都花在哪儿？主要就花在这亿万次的开关翻转上——每次翻转都要给线路的寄生电容充放电，翻转越频繁、时钟越高，动态功耗越大。这就是同款处理器降频能显著省电的电路根源，也是数据中心把「每瓦性能」当第一指标的物理原因。

4.5与非门的完备性：一个门搭出一切

这是本章最「震撼」的一节。数学家证明了：只用与非门（NAND）一种门，就能搭出非门、与门、或门——进而搭出任何逻辑电路。这种「用一个门搞定一切」的性质，叫 功能完备性（functional completeness）。

看它是怎么做到的：

• 搭非门：把与非门的两个输入接成同一个信号（A 和 A）。于是输出 = NOT(A AND A) = NOT A。
• 搭与门：先 NAND，再过一个「非门」（也由 NAND 搭成）取反，就还原成 AND。
• 搭或门：由德摩根定律，A OR B = NOT( NOT A AND NOT B )，用三个 NAND 就能搭出来。

幕后的功臣：德摩根定律

三条搭法里最费解的是「或门怎么来的」，它的底气是布尔代数里最重要的一条变换规则——德摩根定律（De Morgan's laws）：

一句话概括：「非」横穿 AND/OR 时，算符要跟着互换——「非与」变「或非」，「非或」变「与非」。它为什么成立？用真值表一验便知：NOT(A AND B) 一列，与「NOT A OR NOT B」一列在全部 4 行上一模一样——两列完全相同，等式自然成立。德摩根定律是逻辑世界的「分配律」，后面化简表达式、翻译告警逻辑时都会反复用到。

把定律套进或门的搭法：A OR B = NOT(NOT A AND NOT B)。注意等号右边恰好是一个「与非门」的表达式——两个输入分别是 NOT A 和 NOT B，先 AND 再整体取反，正是 NAND 的定义。而 NOT A、NOT B 又各自能用「短接的 NAND」造出来。于是「三只 NAND 搭出或门」水到渠成。

nand = lambda x, y: 0 if (x and y) else 1   # 与非门：仅当 x、y 全为 1 时输出 0
print("A B | NAND搭出 | A OR B | 一致?")
for A in (0, 1):
    for B in (0, 1):
        built = nand(nand(A, A), nand(B, B))   # (A NAND A) NAND (B NAND B)
        print(f"{A} {B} |     {built}     |   {A | B}    |", "✓" if built == (A | B) else "✗")

A B | NAND搭出 | A OR B | 一致?
0 0 |     0     |   0    | ✓
0 1 |     1     |   1    | ✓
1 0 |     1     |   1    | ✓
1 1 |     1     |   1    | ✓

德摩根定律的价值远不止翻译手册，它是逻辑「等价变形」的总开关。往后有三种高频场景都靠它押阵：给整组条件取反（禁止、失效、灯不亮）；把深层嵌套的 NOT 推到最内层；在 AND 型与 OR 型电路之间互换实现。见到「整体否定」就条件反射「算符互换」，这门手艺就算练成了。

顺带一提：与门的「孪生兄弟」或非门（NOR）同样功能完备——把上面的推导全部对称地翻转（NOR 短接即非门，两只 NOR 先各自取反再 NOR 就得到与门）。事实上，宇宙第一台真正的计算机所依赖的继电器逻辑，两种门都能胜任。工程师最终选 NAND 做标准积木，更多是工艺原因：同样工艺下 NAND 的 CMOS 版本比 NOR 更快、占硅面积更小。

「万能」的门槛：为什么 AND 和 OR 不够用？

「万能」这顶帽子不是谁都能戴。试试只用 AND 和 OR（不许用 NOT）能不能搭出非门？不能——而且有个漂亮的证明：任何只由 AND、OR 组成的表达式，把全部输入置 1 后输出必然是 1（1 AND 1 = 1，1 OR 1 = 1，怎么算都是 1）；而非门在输入为 1 时必须输出 0。矛盾，所以 {AND, OR} 这个集合不完备，缺的是「能产生 0」的取反能力。NAND 和 NOR 之所以万能，正因为它们天生「输出里带反」——一只门同时握有取反和组合两股力量。完备的门槛并不低，而 NAND 恰好跨了过去。

最后把本章放进全局坐标：门是计算机的第一层积木——门拼成组合电路（加法器、选择器，下一章），组合电路加上时钟变成能记住状态的时序电路（第 6 章），时序电路再组织成 CPU 的运算器与控制器。回头看，本章的八道例题其实已经把「需求 → 真值表 → 门」这条路走了个来回；下一章，就让门开始「真正地做事」。

再感受一次尺度：一枚现代处理器里的晶体管以百亿计，但其中每一只的导通与截止，逻辑上都和本章例题里那只四管 NAND 一样朴素。数字世界的复杂性不在单个开关变复杂，而在同样简单的开关被重复了亿万次。硬件工程师用硬件描述语言（如 Verilog）写下逻辑，综合工具自动把它翻译成海量标准单元——这些单元绝大多数就是 NAND。