8
0
0

《图灵完备》笔记-0x01:基础逻辑电路

2026-06-09
2026-08-18
《图灵完备》笔记
数字逻辑/数字电路/《图灵完备》
文章摘要
|

前言

以前总在各种地方看到过这款游戏，在《数字逻辑》这门课结束许久过后，还是下定决心开始玩了。死去的数电知识开始回归了……

这篇也算是我复习数电的一些笔记吧，里面的内容不一定是最佳内容，所以请原谅。

笔记将会分若干篇，希望给没有基础的人提供一点帮助。

那现在，开始我们的旅程。

第一章：基础逻辑电路

原力觉醒

原力觉醒

与非门(NAND)

alt text

隆重介绍接下来要开始打交道的东西：逻辑门。

前置知识-1：逻辑门

逻辑门是逻辑电路的基本组件，根据逻辑门的组合，可以让特定的输入产生特定的输出。

类型(英文符号)图标中文名注释逻辑表达式真值表
AND (∧ / &)AND与门只有当两个输入都为 1 时输出才为 1Y=A\cdot BA,B\to Y
0,0\to 0
0,1\to 0
1,0\to 0
1,1\to 1
OR (∨ / |)OR或门只要有一个输入为 1，输出就为 1Y=A+BA,B\to Y
0,0\to 0
0,1\to 1
1,0\to 1
1,1\to 1
NOT (¬ / !)NOT非门将输入取反Y=\overline{A}A\to Y
0\to 1
1\to 0
NAND (↑)NAND与非门与门后再取反；最常用的通用门之一Y=\overline{A\cdot B}A,B\to Y
0,0\to 1
0,1\to 1
1,0\to 1
1,1\to 0
NOR (↓)NOR或非门或门后再取反；也是通用门之一Y=\overline{A+B}A,B\to Y
0,0\to 1
0,1\to 0
1,0\to 0
1,1\to 0
XOR (⊕)XOR异或门两个输入不同时输出为 1Y=A\oplus B=A\overline{B}+\overline{A}BA,B\to Y
0,0\to 0
0,1\to 1
1,0\to 1
1,1\to 0

非门(NOT)

非门关卡

通过这个关卡，你应该会发现一件事情，非门居然可以通过与非门制作出来，是不是意味着一些逻辑门元件的实现方式本质就是其他逻辑门元件拼装实现的？

与门(AND)

与门关卡

我们手上与与非门和非门，思考一下后不难发现，与非门是先与门后非门，我们只需要再接一个非门，这样子就可以得到与门了，用逻辑表达式就是：

Y=\overline{\overline{A\cdot B}}

其中，\cdot是与 (AND) 运算。上横线则是非 (NOT) 运算。

那为什么与非门后接非门就是与门了呢？这就要提到另外一个东西了：逻辑表达式的布尔恒等式。

前置知识-2：布尔恒等式

实际上你会发现，这些逻辑门是具有严谨的数学运算法则的。进一步研究后会发现，一些不同的逻辑表达式，虽然写法不同，但它们在真值表上的结果完全一致。我们就把这种“表达式等价”的关系叫作布尔恒等式。

这里先约定一下：

  • A,B,C 都表示布尔变量，只能取 0 或 1
  • + 表示“或”运算
  • \cdot 表示“与”运算
  • 上横线 \overline{A} 表示“非”运算

下面是后面最常用的一些布尔恒等式：

名称公式说明
双重否定律\overline{\overline{A}} = A取反两次，结果回到原值
交换律A+B=B+A
A\cdot B=B\cdot A		“与”和“或”都可以交换顺序
结合律(A+B)+C=A+(B+C)
(A\cdot B)\cdot C=A\cdot(B\cdot C)		多个输入可以自由分组
分配律A\cdot(B+C)=A\cdot B+A\cdot C
A+(B\cdot C)=(A+B)\cdot(A+C)		“与”对“或”分配，“或”对“与”也分配
互补律A+\overline{A}=1
A\cdot\overline{A}=0		一个变量和它的反相组合后，结果固定
德摩根律\overline{A\cdot B}=\overline{A}+\overline{B}
\overline{A+B}=\overline{A}\cdot\overline{B}		取反会把“与”和“或”互换，同时把每个输入都取反
吸收律A+A\cdot B=A
A\cdot(A+B)=A		多余的条件有时可以直接被吸收掉

因此不难发现，双重否定律便能解释上面的疑问。

或门(OR)

或门关卡

有了前面的经验，我相信你可以推导出来的吧？

或者看下面的推导过程：

:::fold{title="推导过程"}
由于我们现在只有与非门和非门，因此我们需要想办法让或门变为“与非”和“非门”的表示方法。

\begin{aligned} Y &= A + B \\ &= \overline{\overline{A + B}} && \text{根据双重否定律，给整个表达式再取一次反，结果不变} \\ &= \overline{\overline{A}\cdot\overline{B}} && \text{根据德摩根律，$\overline{X+Z}=\overline{X}\cdot\overline{Z}$} \\ \end{aligned}

所以，A+B 就可以写成 \overline{\overline{A}\cdot\overline{B}}，也就是用非门与与非门表示或门了。

:::

或非门(NOR)

或非门关卡

不讲推导过程了，就是刚刚的或门取反就行了。

高电平

如何持续输出一个高电平呢？观察我们解锁的所有元件，发现或门的真值表：

ABA OR B
000
011
101
111

只有输入都为 0 的时候才为 0，那么我们有没有什么办法在输入都为 0 的时候输出 1 呢……诶，与非门是不是可以做到？

ABA NAND B
001
011
101
110

还真是，那么我们让他们互补一下就 OK 了。

当然我把与非门接在或门后面也是为了无论如何都有一路输入为 1，解法不唯一啦。

第二刻

从现在开始，正解图我放后面，先观察真值表。

ABY
000
101
010
110

不要被这个所谓的第二刻唬住了，观察真值表其实你会发现说白了就是让你在 A=1,B=0 的时候输出 1。
那这个就很简单了啊，首先我们马上想到与门，因为与门只有 A=1,B=1 的时候输出 1，其余时候都输出 0。但我们现在的 B=0 啊，怎么办？所以我们对 B 取反就可以了。

第二刻关卡

异或门(XOR)

注意到这关有一个成就：4NAND=XOR

因此我会从普通解法到成就解法讲起。

前置知识-3：通过真值表化简逻辑表达式

如果一个逻辑表达式看起来很乱，我们可以先把它写成真值表，再从真值表反推一个更简单的式子。

基本思路很简单：

  1. 先列出所有输入组合。
  2. 算出每一行对应的输出。
  3. 只保留输出为 1 的那些行。
  4. 如果有两行只差一个变量，就可以把这个变量消掉。

比如下面这个表达式：

Y = A\overline{B} + AB

先写成真值表：

ABY
000
010
101
111

你会发现，当 A=1 时，不管 B 是多少，输出都等于 1。
所以这个式子其实可以直接化简成：

Y = A

进一步说，这种“从真值表反推表达式”的写法，还会经常用到两个概念：最小项和最大项。

最小项（minterm）可以理解成：把某一行输入对应的变量都写出来，再用“与”连起来，得到一个只在这一行输出为 1 的项。

如果有三个变量 A,B,C，那么当输入是 A=1,B=0,C=1 时，对应的最小项就是：

m_5 = A\overline{B}C

因为只有在 A=1,B=0,C=1 的时候，这一项才等于 1。

最大项（maxterm）正好相反：把某一行输入对应的变量都写出来，再用“或”连起来，得到一个只在这一行输出为 0 的项。

还是上面的输入 A=1,B=0,C=1，对应的最大项就是：

M_5 = \overline{A}+B+\overline{C}

因为只有在 A=1,B=0,C=1 的时候，这一项才会变成 0。

:::tip[例子 1: 最小项之和]

假设真值表如下：

ABY
000
011
100
111

输出为 1 的行是 01 和 11，所以可以直接写成最小项之和：

Y=\overline{A}B+AB

再化简一下，就得到：

Y=B

:::

:::tip[例子 2: 最大项之积]
假设真值表如下：

ABY
001
010
101
110

输出为 0 的行是 01 和 11，所以可以直接写成最大项之积：

Y=(A+\overline{B})(\overline{A}+\overline{B})

这个式子继续化简后，也可以得到：

Y=\overline{B}

:::

那么回到正题，观察真值表：

ABY
000
011
101
110

观察发现输出为1的行为01和10，因此写成最小项之和：

Y=A\overline{B}+\overline{A}B

然后我们基于此得到该电路：
异或门普通电路
当然这不够，我们的目标是四与非门达成异或门，因此我们需要继续变形：

\begin{aligned} P &= \overline{A\cdot B} && \text{定义中间量 $P$，表示 $A$ 与 $B$ 先做与运算再取反} \\ Q &= \overline{A\cdot P} && \text{再定义中间量 $Q$} \\ &= \overline{A\cdot \overline{A\cdot B}} && \text{代入 $P$} \\ &= \overline{A(\overline{A}+\overline{B})} && \text{德摩根律：$\overline{X\cdot Y}=\overline{X}+\overline{Y}$} \\ &= \overline{A\overline{A}+A\overline{B}} && \text{分配律} \\ &= \overline{0+A\overline{B}} && \text{互补律：$A\cdot\overline{A}=0$} \\ &= \overline{A\overline{B}} && \text{恒等律：$0+X=X$} \\ &= \overline{A}+B && \text{德摩根律} \\ R &= \overline{B\cdot P} && \text{再定义中间量 $R$} \\ &= \overline{B\cdot \overline{A\cdot B}} && \text{代入 $P$} \\ &= \overline{B(\overline{A}+\overline{B})} && \text{德摩根律} \\ &= \overline{B\overline{A}+B\overline{B}} && \text{分配律} \\ &= \overline{B\overline{A}+0} && \text{互补律：$B\cdot\overline{B}=0$} \\ &= \overline{\overline{A}B} && \text{恒等律：$X+0=X$} \\ &= A+\overline{B} && \text{德摩根律} \\ Y &= \overline{Q\cdot R} && \text{最后把 $Q$ 和 $R$ 再做一次与非运算} \\ &= \overline{(\overline{A}+B)(A+\overline{B})} && \text{代入 $Q$ 和 $R$} \\ &= \overline{\overline{A}A+\overline{A}\overline{B}+BA+B\overline{B}} && \text{分配律} \\ &= \overline{0+\overline{A}\overline{B}+AB+0} && \text{互补律：$\overline{A}A=0$，$B\overline{B}=0$} \\ &= \overline{AB+\overline{A}\overline{B}} && \text{恒等律：$0+X=X$} \\ &= A\overline{B}+\overline{A}B && \text{德摩根律} \end{aligned}

所以，异或门可以写成四个与非门的组合：

Y=\overline{\overline{A\cdot \overline{A\cdot B}}\cdot \overline{B\cdot \overline{A\cdot B}}}

按照该表达式，我们最后得到的线路就是这样：
4NAND表达式

三路或门与三路与门

这两关没什么好讲的，三个门接起来就 OK。
三路或门
三路与门

同或门(XNOR)

同或门和异或门输出相反，所以你最简单的方式就是在异或门前面加个非门结束。
简单的同或门

当然我们也有不简单的做法：
不简单的同或门

看真值表：

ABY
001
010
100
111

所以直接求得最小项之和：

Y=\overline{A} \cdot \overline{B} + A \cdot B

第一章！完！

支持与分享

如果这篇文章对你有帮助，欢迎分享给更多人或者给予支持！

《图灵完备》笔记-0x01:基础逻辑电路
/archives/01-base
作者
Leave_Time(时泠)
发布于
2026-06-09
许可协议
CC BY-NC-SA 4.0

评论