逻辑运算基础

官方工学老师·32 页·深入(追求细节与边界)·0 次浏览·2 天前
逻辑门数字电路布尔代数

逻辑运算基础

从两个开关出发,搞懂与/或/非门如何构成CPU的判断基石

按 空格/→ 演示下一步

1 / 32 页

全部页面点击任意一页,跳回舞台从这页播放

逻辑门数字电路布尔代数

逻辑运算基础

从两个开关出发,搞懂与/或/非门如何构成CPU的判断基石

1第 1 页 · 逻辑运算基础

什么是逻辑变量

判断题只有对或错,温度开关只有触发或未触发——现实中很多现象天然就是二值的。逻辑变量就是用来描述这种「非此即彼」状态的最小单位。

二值变量
同一时刻只能取两个互斥状态之一,不存在第三种可能
0/1 是约定标签
不是数学上的「零」和「一」,只是给两个状态起的代号
物理实现为电平
电路里对应两个电压区间,如<0.8V 视作 0,>2.0V 视作 1
电灯开关对应 →逻辑变量 0/1

扳到上=1,扳到下=0;只可能停在两个位置,没有中间挡位

2第 2 页 · 什么是逻辑变量

基本逻辑运算:与

上页把现实压成 0 和 1,那这两个值之间最自然的运算是?——「与」AND:只有两个都为 1,结果才为 1。

全 1 才 1
A、B 同为 1 时输出 1;其余三种组合 (0·0)(0·1)(1·0) 输出均为 0
遇 0 即 0
只要任一输入为 0,输出必为 0——这叫「零律」
交换律与结合律
A·B = B·A;(A·B)·C = A·(B·C),分组和顺序都不影响结果
短路求值
if (A && B) 中,A 为假则 B 不再执行——AND 在程序里的真实语义
串联的两个开关对应 →AND 运算

两开关都闭合灯才亮;任一断开灯就灭——开关=输入,灯=输出

AB=1    A=1 且 B=1A \land B = 1 \iff A=1 \text{ 且 } B=1
3第 3 页 · 基本逻辑运算:与

基本逻辑运算:或

上一页的“与”像串联开关:两个都通,灯才亮。现实中,声控灯只要任一声响或手动开关一个动作就能亮;这对应“或”。任一输入为 1,输出就是 1。

或门规则
只要 A、B 中至少一个为 1,A∨B 就为 1;只有二者都为 0 时才为 0。
四种组合
00→0;01、10、11 都→1。11 仍为 1,不是“恰好一个”。
德摩根转换
由德摩根律,A∨B=¬(¬A∧¬B);或也可用与、非组合实现。
并联开关对应 →逻辑或

任一开关闭合电路就通;只有全部断开时才不通。

AB=¬(¬A¬B)A \lor B = \neg(\neg A \land \neg B)
4第 4 页 · 基本逻辑运算:或

基本逻辑运算:非

与、或都是看两个信号做判断。但工程里经常只有一个信号,还希望结果完全相反——反相器(NOT)正是为这个场景而生。

单目运算
只看一个输入,是唯一的一元布尔运算
完全相反
真值表只有两行:0→1,1→0,没有第三种可能
双重否定律
两次取反回到原值:¬¬A = A,是 NOT 的特征性质
通用构件
NAND、NOR 都由 NOT 加上与、或组合而成
汉语双重否定句对应 →双重否定律 ¬¬A = A

「不」否定一次,「不不」又肯定回来——两次取反 = 原值

¬¬A=A\neg\neg A = A
5第 5 页 · 基本逻辑运算:非

与非、或非、与或非

与非、或非是基本运算的简单复合;与或非则在单级门延迟内实现更复杂的逻辑判断。

1
与非:与后取反
先逐位做与运算,再对整个结果取反——仅当两输入都为1时才输出0。
2
或非:或后取反
先逐位做或运算,再对整个结果取反——仅当两输入都为0时才输出1。
3
与或非:先与再或再非
多组与运算的结果再做或运算,最后整体取反,单级门延迟即可实现。
6第 6 页 · 与非、或非、与或非

基本定律:0-1定律与同一定律

上一页认识了与、或、非三种运算。本页看更基础的问题:变量与常量(0、1)放一起结果会怎样?变量与自己运算又会怎样?这两类规则合称0-1定律与同一律。

A·0 = 0
任何变量与0做AND,结果必为0——0在AND中是吸收元
A·1 = A
任何变量与1做AND,结果等于自身——1在AND中是幺元
A+0 = A
任何变量与0做OR,结果等于自身——0在OR中是幺元
A+1 = 1
任何变量与1做OR,结果必为1——1在OR中是吸收元
同一律
A·A = A, A+A = A;变量与自身运算结果不变,重复不增信息
会议表决对应 →0-1定律与同一律

永久否决者是AND的吸收元(拖累到0),永久赞成者是OR的吸收元(拉到1);同一立场重复表态,结论不变

$A \cdot 0 = 0,\ A \cdot 1 = A,\ A + 0 = A,\ A + 1 = 1,\ A \cdot A = A,\ A + A = A$
7第 7 页 · 基本定律:0-1定律与同一定律

交换律、结合律、分配律

0-1定律处理变量与常量的关系,但实际电路往往是多个变量复合。靠什么化简(A∧B)∨(A∧C)这种表达式?这就轮到代数里的三条老熟人:交换律、结合律、分配律。

交换律
A∧B = B∧A,A∨B = B∨A,运算对象换位结果不变
结合律
(A∧B)∧C = A∧(B∧C),括号位置不影响结果
分配律(∧对∨)
A∧(B∨C) = (A∧B)∨(A∧C),∧可分配进∨
分配律(∨对∧)
A∨(B∧C) = (A∨B)∧(A∨C),∨也可分配进∧
普通代数的乘法对加法对应 →逻辑中∧和∨互为对偶

代数分配律只单向;逻辑里∧和∨像镜像,所以分配律双向都成立

AB=BAAB=BA(AB)C=A(BC)(AB)C=A(BC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)A \land B = B \land A \\ A \lor B = B \lor A \\ (A \land B) \land C = A \land (B \land C) \\ (A \lor B) \lor C = A \lor (B \lor C) \\ A \land (B \lor C) = (A \land B) \lor (A \land C) \\ A \lor (B \land C) = (A \lor B) \land (A \lor C)
8第 8 页 · 交换律、结合律、分配律

德·摩根定律

与非和或非形式不同,但摩根定律揭示它们可以互相转换——否定穿括号时,与和或会互换。

与的否定律
  • 原式:¬(A∧B),整体与运算后取非
  • 展开:¬A ∨ ¬B,运算翻转为或
  • 规则:∧→∨,非号分配进各项
  • 对偶:与门取非 = 或非形式
或的否定律
  • 原式:¬(A∨B),整体或运算后取非
  • 展开:¬A ∧ ¬B,运算翻转为与
  • 规则:∨→∧,非号分配进各项
  • 对偶:或门取非 = 与非形式
两者互为对偶:第二式是第一式对所有运算取对偶(∧↔∨)的产物。统一口诀:'非号穿过括号,与或必翻转'。
9第 9 页 · 德·摩根定律

吸收定律

前两节我们学了分配律和德·摩根定律,今天把它们再组合一下,推出三条化简时最常打交道的式子——吸收定律。核心就一句话:A 一旦出现,多余的项就被它「吞掉」了。

标准吸收律 A+AB=A
A 把含自己的 AB 整组吞掉,式子直接等于 A
对偶形式 A(A+B)=A
AND 域里的镜像版本,逻辑意义与上一条完全对称
推论 AB+ĀB=B
提公因子 B 后,A 与 Ā 互补抵消,只剩 B 本身
已买到全年健身卡对应 →吸收律 A+AB=A

年卡(A)已覆盖所有权益,再加「年卡+季卡」套餐(AB)等价于年卡本身(A)

A+AB=AA(A+B)=AAB+AˉB=BA + AB = A \\ A(A+B) = A \\ AB + \bar{A}B = B
10第 10 页 · 吸收定律

常用恒等式汇总

16个核心恒等式的速查表与推导

常用恒等式汇总
16个核心恒等式的速查表与推导
11第 11 页 · 常用恒等式汇总

逻辑函数的定义

前面我们已经认识了基本运算和大量公式,但要回答「一个复杂判断到底由什么决定」这件事,还必须把单个运算上升为一个整体——这就是逻辑函数。

映射关系
把一组输入变量的取值,按规则对应到唯一的输出值
自变量为逻辑变量
输入变量只能取 0 或 1
因变量为逻辑变量
输出结果同样只能是 0 或 1
取值唯一确定
同样的输入组合,必然得到唯一的输出
多种等价写法
同一个函数既可写成表达式,也可列成真值表
自动售货机对应 →逻辑函数

投入硬币+按键(输入)→吐出某瓶饮料(输出),组合确定,结果唯一

F(A,B,C)=AB+CF(A,B,C) = A \cdot B + \overline{C}
12第 12 页 · 逻辑函数的定义

真值表构建方法

沿流程图从左到右读:六个构建步骤依次推进,最后回代验证保证一致性。

图解渲染中…
A3按二进制计数规律:000→001→…→111,确保不重不漏A4括号优先,然后非>与>或;不确定时加括号A5对每一行变量取值,按层级代入求最终输出A6用输出反推原表达式,确认无矛盾
13第 13 页 · 真值表构建方法

与或表达式

乘积项之和的标准形式

与或表达式
乘积项之和的标准形式
14第 14 页 · 与或表达式

与非式与或非式

上页学了德·摩根定律——能把非号从外面推到里面。这一页再推一步:能不能把整个表达式里的与、或、非全部去掉,只剩一种运算?

与非式
整个表达式只含与非运算一种形式
或非式
整个表达式只含或非运算一种形式
通用性
与非、或非各自功能完备——组合起来可表示任意逻辑函数
转换核心
F=(F')' 加德·摩根,与或式化为与非式,或与式化为或非式
只有方块的乐高对应 →只用与非门/或非门

一种积木靠拼接能拼出万物;一种门靠组合能实现全部逻辑

F=AB+CD=AB+CD=ABCDF = AB + CD = \overline{\overline{AB+CD}} = \overline{\overline{AB} \cdot \overline{CD}}
15第 15 页 · 与非式与或非式

最小项与最大项

我们已经能用与、或、非组合出任意表达式,但要分析、比较、化简函数,还需要一种『规范』写法——每一项都把全部变量召集齐全。这就是最小项和最大项出场的原因。

最小项
每个变量以原变量或反变量恰好出现一次的乘积项(与项),n 个变量共有 2ⁿ 个
最大项
每个变量以原变量或反变量恰好出现一次的求和项(或项),n 个变量共有 2ⁿ 个
编号规则
变量排好序,原变量记 1、反变量记 0,对应二进制转十进制即下标
互补关系
同编号 m_i 与 M_i 互补:m_i + M_i = 1、m_i · M_i = 0
团队决议的投票规则对应 →最小项与最大项

最小项=全票通过(所有变量各取定值,整体才为 1);最大项=一票否决(任一变量不对,整体就为 0)

$$m_i = \overline{M_i}, \quad m_i + M_i = 1, \quad m_i \cdot M_i = 0$$
16第 16 页 · 最小项与最大项

卡诺图作为表示工具

前面学的真值表是「一行一个输入组合」的一维清单。变量一多到4、5个,这张表就拉得老长,肉眼根本找不出规律。卡诺图把同样多的格子盘成二维网格——它的编码规则正是为了解决这个痛点。

折叠而非新增
格数仍是 2^n,只是从一行折成 m×k 的网格
行/列分变量
变量拆两组分别标在行轴、列轴
格雷码编码
轴坐标按格雷码排,相邻格只差一个变量
边界也相邻
最左与最右、最上与最下相邻,地图是环形的
格内填函数值
每格记函数 f 的输出 0/1(或不定值 X)
城市街区地图对应 →卡诺图网格

地图把相邻地块排在一起便于查找邻居;卡诺图用格雷码让「只差一个变量」的输入组合排成物理邻居

17第 17 页 · 卡诺图作为表示工具

化简的必要性

你已经会用卡诺图把一个函数「画」出来了。但同一个函数能写成很多等价形式——有的烧一摞门,有的只接一根线。这就是为什么要化简。

门数 ↔ 硬件成本
每个门对应若干晶体管,门越多则芯片面积、功耗、单价越大
级数 ↔ 传播延迟
信号每经过一级门都要等一个 t_pd,级数翻倍延迟翻倍,拖累时钟频率
扇入物理约束
实际芯片每个门输入端数有上限,化简后还要验证物理上能不能实现
送外卖选路线对应 →逻辑化简

同一份外卖,路线越短越省时间省体力;表达式门越少越便宜越快

F=ABC+ABCˉ+ABˉC+ABˉCˉ=AF = ABC + AB\bar{C} + A\bar{B}C + A\bar{B}\bar{C} = A
18第 18 页 · 化简的必要性

最简式的标准

我们已经知道为什么要化简,但"最简"二字本身需要一把精确的尺子。同一个函数可以写出十几种等价形式,光凭"看着短"来判断是不够的。下面就给出这把尺子的刻度。

与或式·项数最少
乘积项(即若干文字相与的项)数量最少,少一个就不算最简。
与或式·每项最简
每个乘积项里出现的文字个数最少,无法再被吸收合并。
或与式·项数最少
和项(即若干文字相或的项)数量最少,少一个就不算最简。
或与式·每项最简
每个和项里出现的文字个数最少,无法再被吸收合并。
两标准要同时达标
只满足一条不算最简;最简结果通常不唯一,但都同样"最简"。
合并采购清单对应 →最简与或式

清单行数少(项数少)+ 每行列出商品种类少(每项变量少);同时满足才算"合并到底"

19第 19 页 · 最简式的标准

代数法化简思路

前面我们定义了'最简'的标准,现在反过来问:怎么把一个复杂表达式一步步压到那个标准?答案就藏在前面那堆定律里。

核心思路
把定律当工具反复套用,消掉冗余的项和变量
双重目标
项数最少 + 每项变量数最少,但两者常冲突需权衡
合并互补
AB + AB' = A,把仅差一个互补因子的两项合一项
吸收消元
A+AB=A 吸收冗余项;A+A'B=A+B 消掉多余因子
经验依赖
无固定机械步骤,结果可能非最简,需多路径尝试
解魔方对应 →代数法化简

每步套用固定手法(定律),无最短公式,靠手感练出路径

AB+AB=AA+AB=AA+AB=A+BAB+AB'=A \quad A+AB=A \quad A+A'B=A+B
20第 20 页 · 代数法化简思路

卡诺图的结构原理

从二进制跳变不均出发,看Gray编码如何保证相邻格只差1位

图解渲染中…
a3Gray序:每次只翻1位的编码a8首尾环接:边界格也与对侧相邻
21第 21 页 · 卡诺图的结构原理

2变量卡诺图化简

从画图到写最简式,分五步走完完整流程。

1
画2×2方格
2变量各占一维,按格雷码00/01/11/10排列
2
填入最小项
根据真值表把函数值为1的格子标1,其余为0
3
识别相邻1
找位置相邻(仅一边变)的1格,可跨越边界
4
圈组并消元
每圈一对相邻1,对应一项消去一个变量
5
写出最简式
各圈对应项相或,得到化简后的与或表达式
22第 22 页 · 2变量卡诺图化简

3变量卡诺图化简

三变量卡诺图比两变量多了行维,相邻关系出现首尾相接。

1
画8格矩阵
三变量按格雷码顺序排列,保证相邻格只差一个变量
2
填入函数值
把函数值为1的最小项标入对应格子
3
找相邻1格
识别可合并的1格,含上下左右首尾环绕相邻
4
圈组并优化
圈成2/4/8格组,覆盖所有1格且尽量大
5
写出最简式
每组对应一个与项,组内变化的变量被消去
23第 23 页 · 3变量卡诺图化简

4变量卡诺图化简

4变量卡诺图把矩阵从8格扩到16格,相邻规则进化:边界上下、左右、四角全部互通,最大圈可包8格、消3变量。

1
画16格矩阵
AB、CD两轴按00-01-11-10排列,邻格只差一个变量
2
识别环回相邻
顶底相连、左右相连、四角相连,每格最多4个邻居
3
圈2的幂次组
按8、4、2格矩形圈1,圈尽量大、个数尽量少
4
用边界圈法
四角可并成4格圈,跨边界圈合并看似分离的1
5
选本质项
含独占1的项为本质项,余下用最少非本质项补齐
24第 24 页 · 4变量卡诺图化简

圈组原则与技巧

上页4变量卡诺图你已经能圈完所有1了,但圈法不同,最终式子可能差好几项。这页把圈组的'硬规矩'和'心法'讲透。

圈的硬规矩
大小只能是1、2、4、8、16格,且必须为矩形,不能L形也不能斜着圈
圈大项就小
每大一倍消去1个变量:2格消1个、4格消2个、8格消3个
圈少式才简
覆盖所有1的前提下,圈的数量越少,表达式中'+'号越少
允许重复圈
同一个1可以出现在多个圈里,这是常用技巧而非浪费
先圈孤岛1
只能被圈一次的1叫必需素项,先锁定它就能定最少圈数
一锅炖菜对应 →卡诺图圈组

能炖一锅就别分两锅,省火省时;但锅有固定大小(2/4/8格),不相邻的菜不能硬凑

n变量图中,  2k 格的圈项含 (nk) 个变量\text{n变量图中,}\; 2^k\text{ 格的圈} \Rightarrow \text{项含 }(n-k)\text{ 个变量}
25第 25 页 · 圈组原则与技巧

卡诺图化简步骤总结

前面我们分别做过2、3、4变量卡诺图的化简,现在把它们抽象成一套通用流程——三步走:填图、圈组、写式,再加最后一步合并。

填图
把最小项或真值表中为1的方格标1,其余可留0或留空
圈组
圈1的相邻方块,大小必为2^k,需含全部1,圈越大越好、圈数越少越好
写项
每组保留圈中取值不变的那几个变量,互补对全部消去
相加
把各组对应的与项用或号连起来,得到最简与或式
地图圈选行政区对应 →卡诺图化简流程

填图=标出所有目的地;圈组=划出覆盖全部点的最大区;写项=描述区的不变特征;相加=把描述合并

2k 格消去 k 个变量,留下 nk 个2^k \text{ 格} \Rightarrow \text{消去 } k \text{ 个变量,留下 } n-k \text{ 个}
26第 26 页 · 卡诺图化简步骤总结

卡诺图化简自测

点击作答

在卡诺图化简中,下列哪种圈组方式是错误的?

27第 27 页 · 卡诺图化简自测

五变量及以上卡诺图

4变量卡诺图我们熟了,可变量超过4个,32格挤在一张平面上圈组边界就开始模糊。工程师的解法不是升维,而是降维:把高维变量'剥'出去,一张大图变两张小图的嵌套。

两图并列结构
5变量图 = 两张4变量图左右拼起来,共32格
降维映射
把第5个变量压到两半上:左图=0,右图=1
跨半圈组
圈可跨越两半,对应位置相同时该变量被消去
嵌套结构
同一个圈在两半重复出现 = 一个高位的冗余约束
复式公寓的两层平面图对应 →5变量卡诺图的降维嵌套

上下两图位置对应的房间,其实是一套跨层的复式

28第 28 页 · 五变量及以上卡诺图

约束条件处理

处理 don't care 项的核心是「灵活取舍」——它既不是 0 也不是 1,而是我们可以根据化简需要临时定义的值。

1
识别 don't care 来源
从题设条件中找出实际不会出现或不允许出现的输入组合
2
卡诺图上标 ×
用 × 单独标注这些格子,区别于确定的 0 和 1
3
逐个决策取舍
每个 × 独立判断:圈入还是放弃,没有统一答案
4
大圈优先原则
只在 × 能让现有圈扩大为 2ⁿ 时才当作 1 处理
5
读出最简式
按每个圈对应的变量取值,写出最简与或式
29第 29 页 · 约束条件处理

多输出函数卡诺图

流程从多输出函数开始:共用输入→各自画卡诺图→跨图找公共圈组→决定是否用整体最优取代单图最简。

图解渲染中…
E比对各输出卡诺图,搜索形状相同、位置相同的圈组(公共质蕴含项)G放弃单个输出的最简圈法,换取多个输出复用同一与项H整体门数=各输出所需门之和,共享项只在电路中实现一次J完全无公共圈组时只能各自最简,无法多输出优化
30第 30 页 · 多输出函数卡诺图

逻辑运算基础总结

  • 三种基本运算对逻辑运算构成完备集
  • 代数化简凭定律识别,卡诺图化简凭几何相邻
  • 德·摩根定律是连接与/或两种形式的桥梁
  • 最简式须权衡门数、扇入与延迟等工程约束
  • 变量增多与约束出现时,需切换到QM法或启发式策略
延伸主题:Quine-McCluskey算法组合逻辑电路设计冒险与竞争现象
31第 31 页 · 逻辑运算基础总结

课后思考

先独自思考再看参考答案——三道题分别指向核心、应用与边界。

1为什么只用"与、或、非"三种运算就能表达任意逻辑函数?背后在保证什么?

参考答案因为真值表的每一行都能用最小项(与项)写出,再用或运算合并。三种运算构成"功能完备集",能拼出任意真值表。

2如果手头只有 NAND 一种门电路,能不能搭建出任何逻辑电路?需要什么前提?

参考答案可以。NAND 是"通用门":两输入短接即非门,再用非门与 NAND 组合可拼出与门、或门(背后即德·摩根定律)。前提是允许信号复用。

3卡诺图在变量数继续增加时会遇到什么本质困难?有什么替代方案?

参考答案卡诺图依赖"相邻单元只差一个变量"的二维平面邻接结构,变量超过 4 个时平面无法保持这种邻接关系。替代方法:Q-M 列表化简法、Espresso 算法。

32第 32 页 · 课后思考