03 第一章 Basic LogicBoolean Algebra-3.pptx

第1页：数字电子技术基础 1-3 封面

本页为《数字电子技术基础》课件 1-3 分册封面，标示英文课程名称 Fundamentals of Digital Electronic Techniques、分册编号 1-3 以及授课对象 For Oceanography Dept.（海洋学系）。

第2页：卡诺图概述

卡诺图 Karnaugh Maps（K-Maps）是一种把布尔函数的 0 与 1 可视化的图形方法，其作用类似真值表，在变量数不超过 5 个时对布尔化简非常有用。本课程主要讨论 2、3、4 变量卡诺图。熟悉之后，卡诺图比用布尔方程化简更易用。

第3页：卡诺图与真值表的对比

• 真值表使用输入列与输出列
• 卡诺图则用 X-Y（横—纵）坐标表示某种确定的输入组合，并把对应的输出填入该坐标方格
• 一个图格对应真值表中的一行，也对应布尔表达式中的一个最小项或最大项

第4页：逻辑相邻与合并定理

• 化简定理：XY + X′Y = Y
• 逻辑相邻：两个乘积项只有一个文字不同，且该文字在一项中取反、在另一项中不取反，则称二者逻辑相邻
• 两个逻辑相邻的项可以合并为只含公共文字的一项

第5页：卡诺图的排列规则

卡诺图可以看作真值表的一种特殊排列，排列方式类似格雷码，即相邻的两个格必须逻辑相邻（只有一个变量变化），以便于分组化简。

• 相邻指左右、上下或边界环绕相邻，不包括对角相邻
• 任意两个相邻格之间只有一个变量不同，该变量在一格中取反、在另一格中不取反
• 例如 m0（x1′x2′）与 m1（x1′x2）、m2（x1x2′）相邻，但与 m3（x1x2）不相邻

第6页：二变量卡诺图

对 f(x1,x2)，x1 为行、x2 为列，变量排列顺序很重要。0 号格表示 x1′x2′，1 号格表示 x1′x2，依此类推。若函数中包含某最小项，就在对应格中填入 1。

第7页：二变量卡诺图化简示例

例：f(x1,x2) = x1′x2′ + x1′x2 + x1x2′ = m0 + m1 + m2 = x1′ + x2′。

• 把指定最小项 m0、m1、m2 对应的格填 1
• 对相邻的 1 分组（相或）即可化简
• m0 + m1 = x1′，m0 + m2 = x2′，其中 m0 被重复使用两次

第8页：用卡诺图求最简与或式

用卡诺图求最简与或式的步骤：

• 把函数中每个乘积项对应的格填 1
• 把含 1 的相邻格分组以消去变量，组的大小必须是 2 的幂（2、4、8、…、2ⁿ）
• 三变量及以上的卡诺图要注意边界环绕 boundary wrap
• 注意化简结果可能不唯一

第9页：三变量卡诺图

三变量卡诺图的变量顺序为 (x,y,z)：yz 指定列，x 指定行。每个格与另外三个格相邻（左右、上下或边界环绕，不含对角）。图中标出 m0 至 m7 各方格的位置与编号。

第10页：三变量卡诺图的分组类型

右侧给出在三变量卡诺图中可能出现的结构：它们或是最小项，或是对最小项反复应用化简定理得到的项。可能的分组大小为 1、2、4、8。

第11页：三变量卡诺图化简示例

化简步骤：先把布尔函数的各个最小项填入图中，再进行分组。

例：f(a,b,c) = a′c + abc + bc′，化简结果为 f(a,b,c) = a′c + b。

第12页：三变量卡诺图例题

• f1(x,y,z) = Σm(2,3,5,7)，化简得 f1(x,y,z) = x′y + xz
• f2(x,y,z) = Σm(0,1,2,3,6)，化简得 f2(x,y,z) = x′ + yz′

第13页：四变量卡诺图

四变量卡诺图中，最上一行与最下一行相邻，最左一列与最右一列相邻，注意变量顺序为 WXYZ。图中标出 m0 至 m15 各方格的编号与位置。

第14页：分组大小与消去变量数

小结：2ⁿ 个相邻方格组成的矩形可以消去 n 个变量。当某变量在圈内同时以原变量和反变量形式出现时，该变量即从表达式中消去；圈内各方格取值相同的变量则必须保留在最终表达式中。

第15页：四变量卡诺图化简示例

例：化简布尔函数 g(A,B,C,D) = Σm(0,1,2,4,5,7,8,9,10,12,13)。

先把函数填入图中，再尽可能大地把 1 分组，得 g(A,B,C,D) = c′ + b′d′ + a′bd。

第16页：五变量卡诺图

五变量卡诺图由 A = 0 与 A = 1 两张四变量图叠加构成，两图对应位置的方格彼此相邻。图中标出各格编号，并示例 A′BCDE′ 与 ABCDE′ 两格在两图间的对应关系。

第17页：六变量卡诺图

六变量卡诺图由 AB = 00、01、11、10 四张四变量子图组成。本页给出示例函数 ƒ(A,B,C,D,E,F) = Σm(2,8,10,18,24,26,34,37,42,45,50,53,58,61) 及其化简结果 D′EF′ + ADE′F + A′CD′F。

课程对四变量以上的卡诺图不作解题要求。

第18页：分组规则

• 所有的 1（或 0）都必须被圈到，不能留下未覆盖的格
• 组的数目尽可能少
• 每个组尽可能大
• 组与组之间可以重叠
• 不要出现完全包含在大组之内的子组
• 视 1 与 0 的分布情况，有时圈 0 比圈 1 更方便，可先求 F′ 再取反

例如可以先圈 0 求 F′ = BC′D′ + ABD′ = BD′(A + C′)，再取反得 F = (B′ + C + D)(A′ + B′ + D) = (B′ + D) + A′C；也可以直接圈 1 得 F = B′ + D + A′C，两种方法结果一致。

第19页：蕴涵项与质蕴涵项

蕴涵项 Implicant

函数 F 的一个乘积项 P，若 P 为 1 时 F 必为 1，即 F(P) = 1，则 P 是 F 的蕴涵项。

质蕴涵项 Prime Implicant

若把某蕴涵项 PI 的任意一个文字删去后所得乘积项都不再是 F 的蕴涵项，则 PI 称为 F 的质蕴涵项，即它不被任何更大的蕴涵项所包含。

第20页：质蕴涵项判定示例

以图示卡诺图的函数 f(a,b,c,d) 为例：

• a′b′ 不是质蕴涵项，因为它包含在 b′ 之中
• acd 不是质蕴涵项，因为它包含在 ad 之中
• b′、ad、a′cd′ 是质蕴涵项

第21页：必要质蕴涵项

若函数 F 的某个最小项只被唯一的一个质蕴涵项 p 所包含，则 p 是 F 的必要质蕴涵项 Essential Prime Implicant。必要质蕴涵项必须出现在该函数的所有与或表达式之中。

寻找方法：先求出函数的全部质蕴涵项，再选出那些至少包含一个未被其他质蕴涵项覆盖的 1 的质蕴涵项。上一示例中 b′、ad、a′cd′ 三者都是必要质蕴涵项。

第22页：必要质蕴涵项例题

考察图示卡诺图的函数 f2(a,b,c,d)：在它的若干质蕴涵项中，唯一的必要质蕴涵项是 b′d。

第23页：化简的系统步骤

布尔函数化简的系统化步骤：

• 求出函数的全部质蕴涵项
• 把所有必要质蕴涵项都纳入结果
• 对未被必要质蕴涵项覆盖的剩余最小项，再选一组其他质蕴涵项加以覆盖，并使重叠最少
• 最终化简结果即上述所选乘积项的逻辑或

第24页：卡诺图化简综合例题

例：化简 f(a,b,c,d) = Σm(0,1,2,3,4,5,7,14,15)。

• 共得到五个分组项，但并非全部都需要
• 有三个格只被唯一的组覆盖，因此对应三个必要质蕴涵项
• 结果为 F(a,b,c,d) = a′b′ + a′c′ + a′d + abc

第25页：用卡诺图求或与式

求或与式的方法：对卡诺图中函数为 0 的那些格用与或式化简，得到反函数 F′，再求 F′ 的补即得 F。

求布尔函数的补可先求对偶再把每个文字取反，也可以直接使用德摩根定理。

第26页：或与式化简示例

由图示卡诺图得：

• F′(a,b,c,d) = ab′ + ac′ + a′bcd′
• 求对偶：dual(F′) = (a + b′)(a + c′)(a′ + b + c + d′)
• 把对偶式中各文字取反即得 F = (a′ + b)(a′ + c)(a + b′ + c′ + d)

第27页：无关项的概念

无关项 Don t care terms

指某些输入取值组合或者永远不会出现（约束项），或者即使出现其输出也不必关心（任意项）。

无关项通常用 × 表示，在实现时可任意指定为 0 或 1，因此在卡诺图或真值表中不必关心它取 0 还是取 1。利用无关项可以进一步化简函数。

第28页：无关项示例：门禁报警

门禁报警系统示例：信号 A、B 来自两个门传感器，信号 C 来自时钟。

• C 为高表示处于 17:00 至次日 9:00 的非办公时间
• A 为高表示 A 门被打开，B 同理
• 若在非办公时间任一扇门被打开则报警
• 因 A、B 两门互锁不能同时打开，故 ABC 与 ABC′ 两种输入组合不会出现

第29页：利用无关项化简

仍以门禁报警系统为例：

• 不使用无关项时，逻辑表达式为 F = A′BC + AB′C
• 使用无关项后可得 F = BC + AC
• 若先求最大项：F′ = C′ + A′B′，则 F = (C′ + A′B′)′ = BC + AC

用与或式与用或与式得到的结果是相同的。

第30页：无关项取值的影响

把无关项当作 1 与当作 0 所得到的逻辑表达式是否相同？

• 取无关项为 1 时：F = CD + A′D = D(A′ + C)
• 取无关项为 0 时：F′ = D′ + BC′，F = D(B′ + C)

两个表达式之所以不同，仅仅是因为前一种情况把 A′BC′D 取作 1，而后一种情况取作 0。

第31页：含无关项的化简例题

化简图示卡诺图的函数 f(a,b,c,d)，答案不止一个：

• f = a′c′d + ab′ + cd′ + a′bc′，或
• f = a′c′d + ab′ + cd′ + a′bd′

中间两项是必要质蕴涵项，首项与末项则是为了覆盖最小项 m1、m4、m5 而选出的（还存在第三种解）。

第32页：含无关项的双解例题

化简图示卡诺图的函数 g(a,b,c,d)，可以得到两个答案：

• g = a′c′ + ab，或
• g = a′c′ + b′d