布尔代数与逻辑函数化简.ppt

第三章布尔代数与逻辑函数化简 3 1基本公式和规则3 2逻辑函数的代数法化简3 3卡诺图化简 3 1基本公式和规则 3 1 1基本公式 表3 1基本公式 表3 2证明分配律的真值表 A BC A B A C 其它公式的证明 1 A A B A B A A A B A A 因为 其它公式的证明 C A AB B C A C AB BC A ABC C A AB A A BC C A AB BC C A AB 1 1 3 1 2基本法则 1 代入法则逻辑等式中的任何变量A 都可用另一函数Z代替 等式仍然成立 例1证明 证明 等式两边的B用B C代入便得到 这样就得到三变量的摩根定律 同理可将摩根定律推广到n变量 C B A C B A B A B A n n n n A A A A A A A A A A A A 2 1 2 1 2 1 2 1 2 对偶法则 对于任何一个逻辑表达式F 如果将其中的 换成 换成 换成 0 0 换成 1 并保持原先的逻辑优先级 变量不变 两变量以上的非号不动 则可得原函数F的对偶式G 根据对偶法则知原式F成立 则其对偶式也一定G成立 其对偶式为 3 反演法则 由原函数求反函数 称为反演或求反 多次应用摩根定律 可以求出一个函数的反函数 例2 求 的反函数 解用摩根定律求 E D C B A E D C B A E D C B A E D C B A F 3 1 3基本公式应用1 证明等式 例3用公式证明 解 AB B A B A B A AB B A B A B A B A AB B B B A AB A A 2 逻辑函数不同形式的转换 逻辑函数的表达形式通常可分为五种 与或表达式 与非 与非表达式 与或非表达式 或与表达式 或非 或非表达式 不同的表达式之间可以相互转换 例4将函数与或表达式转换为其它形式 解 1 与非 与非式 2 与或非式 或与式 4 或非 或非式 C A B A C A AB F C A AB F C A B A C A B A C A B A F 多余项定律 3 2逻辑函数的代数法化简 3 2 1逻辑函数与逻辑图 图3 2函数的逻辑图 A B 1 F 1 1 BC B B A C B A C AB F C B A A 1 B C A B C A B C A B B C B F F AC B 图3 4函数化简后的逻辑图 图3 3原函数逻辑图 3 2 2逻辑函数化简的原则 逻辑函数化简 通常遵循以下几条原则 1 逻辑电路所用的门最少 2 各个门的输入端要少 3 逻辑电路所用的级数要少 4 逻辑电路能可靠地工作 3 2 3与或逻辑函数的化简 1 应用吸收定律1 例5 解 例6 解 所以 C B A D C B A D C B A D B A D C B A D C B A D C A D C B A D C B A D C B D C B A D C B A 2 应用吸收定律2 3 例8 解 例9 解 令 A B AB B 原式 CD B A B A B A B A CD B A AB B A B A 原式 3 应用多余项定律 例10化简 解 例11化简 解 D C B AC AB D C B AC AB D AB C B AC D B A C B AC 原式 4 综合例子 例12化简 解 5 拆项法 例13化简 此例就是用和分别去乘第三项和第四项 然后再进行化简 C B C A B A C B A BC A C B A C B A C B B A C C B A A A C B C B B A 原式 直接用公式已无法再化简时 可采用拆项法 拆项法就是用去乘某一项 将一项拆成两项 再利用公式与别的项合并达到化简的目的 6 添项法 在函数中加入零项因子 利用加进的新项 进一步化简函数 例14化简 解 AB f x x x x 或 3 3卡诺图化简 3 3 1卡诺图化简的基本原理 例15 解 BC A BC B A B A 原式 C B A ABC BC A C B A C B A F 1 最小项标准式定义 最小项 对于一个给定变量数目的逻辑函数 所有变量参加相 与 的项叫做最小项 在一个最小项中 每个变量只能以原变量或反变量出现一次 例如 一个变量A有二个最小项 二个变量AB有四个最小项 3 3 2逻辑函数的标准式 最小项 以此类推 四个变量ABCD共有24 16个最小项 n变量共有2n个最小项 1 2 A A AB B A B A B A 2 2 2 由一般式获得最小项标准式 1 代数法 对逻辑函数的一般式采用添项法 由上式可看出 第二项缺少变量A 第三项缺少变量B 我们可以分别用和乘第二项和第三项 其逻辑功能不变 例如 2 真值表法 将原逻辑函数A B C取不同值组合起来 得其真值表 而该逻辑函数是将F 1那些输入变量相或而成的 如表3 3所示 表3 3某逻辑函数的真值表 从真值表上得到 表3 4三变量最小项的编号 3 最小项的性质 1 对任何变量的函数式 全部最小项之和为1 即 2 两个不同最小项之积为0 即 3 n变量有项最小项 且对每一最小项而言 有n个最小项与之相邻 0 j i m m 3 3 3卡诺图的结构 卡诺图的结构特点是需保证逻辑函数的逻辑相邻关系 即图上的几何相邻关系 因此卡诺图的变量标注均采用循环码 一变量卡诺图 有 2个最小项 因此有两个方格 0表示取A的反变量 1表示取A的原变量 二变量 三变量 四变量 五变量卡诺图分别有4 8 16和32个最小项 卡诺图如下图所示 图3 51 5变量的卡诺图 3 3 4逻辑函数的卡诺图表示法 若将逻辑函数式化成最小项表达式 则可在相应变量的卡诺图中 表示出这函数 如 在卡诺图相应的方格中填上1 其余填0 0 AB C 00 01 11 10 0 1 1 0 1 0 0 1 1 例将用卡诺图表示 解 在B 1 C 0对应的方格 不管A D取值 得m4 m5 m12 m13 在对应位置填1 在C 1 D 0所对应的方格中填1 即m2 m6 m10 m14 在B 0 C D 1对应方格中填1 即m3 m11 在A C 0 D 1对应方格中填1 即m1 m5 ABCD 在A B C D 1对应方格中填1 即m15 图3 7逻辑函数直接用卡诺图表示 C C B B A A D D 1 1 1 1 1 1 1 1 1 1 1 1 AB CD 00 01 11 10 00 01 11 10 3 3 5相邻最小项合并规律 1 两相邻项可合并为一项 消去一个取值不同的变量 保留相同变量 2 四相邻项可合并为一项 消去两个取值不同的变量 保留相同变量 标注为1 原变量 0 反变量 3 八相邻项可合并为一项 消去三个取值不同的变量 保留相同变量 标注与变量关系同上 图3 8相邻最小项合并规律 1 1 1 1 AB CD 00 01 11 10 00 01 11 10 ABD ACD a 1 1 1 1 1 1 1 1 AB CD 00 01 11 10 00 01 11 10 BD CD b 1 1 1 1 1 1 1 1 AB CD 00 01 11 10 00 01 11 10 BD BD c 1 1 1 1 1 1 1 1 AB CD 00 01 11 10 00 01 11 10 B d 3 3 6与或逻辑化简 运用最小项标准式 在卡诺图上进行逻辑函数化简 得到的基本形式是与或逻辑 其步骤如下 1 将原始函数用卡诺图表示 2 根据最小项合并规律画卡诺圈 圈住全部 方格 3 将上述全部卡诺圈的结果 或 起来即得化简后的新函数 4 由逻辑门电路 组成逻辑电路图 例22化简 解第一步 用卡诺图表示该逻辑函数 对应m3 m11 对应m4 m5 m12 m13 对应m1 m5 对应m10 m11 图3 9例22函数的卡诺图表示 1 1 1 1 1 1 1 1 AB CD 00 01 11 10 00 01 11 10 第二步 画卡诺圈圈住全部 方格 图3 10化简过程 1 1 1 1 1 1 1 1 AB CD 00 01 11 10 00 01 11 10 ABD ABC BC 第三步 组成新函数 每一个卡诺圈对应一个与项 然后再将各与项 或 起来得新函数 故化简结果为第四步 画出逻辑电路 图3 11例22化简后的逻辑图 例23化简 解在卡诺圈有多种圈法时 要注意如何使卡诺圈数目最少 同时又要尽可能地使卡诺圈大 逻辑图如图3 13所示 其化简函数为 a 1 1 1 1 1 1 1 1 1 AB CD 00 01 11 10 00 01 11 10 ABC BD ABC ABD ACD 图3 12例23化简过程 图3 13例23逻辑图 A B 1 F A C C B D A C D B 例24化简 图3 14例24的化简过程 1 1 1 1 1 1 1 1 1 1 AB CD 00 01 11 10 00 01 11 10 ACD ABCD BC AB ACD BCD b c 1 1 1 1 1 1 1 1 1 1 AB CD 00 01 11 10 00 01 11 10 ACD ABCD BD BC ACD AB 例26化简 图3 15例26化简过程及逻辑图 A C 1 F A C D A C A C D B B a c 3 3 7其它逻辑形式的化简 1 与非逻辑形式 与非式就是全由与非门实现该逻辑 将与或式两次求反即得与非式 其化简步骤如下 第一步 在卡诺图上圈 方格 求得最简与或式 第二步 将最简与或式两次求反 用求反律展开一次 得到与非表示式 第三步 根据与非式 用与非门组成逻辑电路 例27将例22 26用与非门实现 解例22与或结果为 图3 16例22用与非门实现 A B F B C C A B D 例23 D C A D B C AB C B A D C A BD C AB C B A D C A BD C AB C B A F A F A C C B D A D B B C a 图3 17例23用与非门实现 例24 A F A D D B C B D C A C B C D B A b 图3 18例24用与非门实现 2 或与逻辑形式 首先从卡诺图上求其反函数 其方法是圈 方格 然后再用摩根定律取反即得或与式 例28求的反函数和或与式 图3 19例28的反函数 解求反函数过程如图3 19所示 再由反函数求得原函数 利用摩根定律就得或与式 总结如下 在卡诺图上圈 0 方格 其化简结果 变量为0 原变量 变量为1 反变量 然后变量再相 或 起来 就得每一或项 最后再将每一或项 与 起来而得或与式 故此例可不通过求反函数 直接由上述过程得到或与式 如图3 20所示 图3 20从卡诺图上直接圈得或与式 1 1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 AB CD 00 01 11 10 00 01 11 10 A C D B C B D B F B D C A C D 1 1 1 图3 21或与逻辑图 3 或非逻辑形式 将或与逻辑两次求反即得或非表示式 图3 22例28的或与逻辑图 B F B D C A C D 1 1 1 1 D C A C B D B D C A C B D B F D C A C B D B 3 3 8无关项及无关项的应用 逻辑问题分完全描述和非完全描述两种 对应于变量的每一组取值 函数F都有确定的值 不是 就是 如表3 6所示 逻辑函数与每个最小项均有关 这类问题称为完全描述问题 在实际中 变量的某些取值组合不允许出现 或者是变量之间具有一定的制约关系 这类问题称为非完全描述 如表3 7所示 该函数只与部分最小项有关 而与另一些最小项无关 我们用 或者用 表示 表3 6完全描述 表3 7非完全描述 对于含有无关项逻辑函数可表示为 也可表示为 即不允许AB或AC或BC同为1 0 C B A C B A F BC AC AB 约束条件为 图3 24不考虑无关项的化简 图3 25考虑无关项函数化简 0 0