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

三三 布尔代数与逻辑函数化简布尔代数与逻辑函数化简3.1 基本公式和法则基本公式和法则 3.2 逻辑函数的代数法化简逻辑函数的代数法化简 3.3 卡诺图化简卡诺图化简 3.1 基本公式和规则基本公式和规则3.1.1 基本公式基本公式表表 3 – 1 基本公式基本公式续表表 3 – 2 证明分配律的真值表由表中可知A+BC=(A+B)(A+C)在吸收律1的证明中， 只证第二式： 在吸收律2的证明中， 也只证第二式： A+AB=A(1+B) =A(因为1+B=1) 吸收律3也只证第二式： （证毕）（证毕）（证毕）表表 3 – 3 求反律的真值表求反律的真值表多余项定律证明如下：多余项定律可推广为3.1.2 基本法则基本法则 1、代入法则、代入法则 逻辑等式中的任何变量逻辑等式中的任何变量A，， 都可用另一函数都可用另一函数Z代替代替，等式仍然成立等式仍然成立  代入法则可以扩大基本公式的应用范围。

例例 1 证明解解这是两变量的求反公式， 若将等式两边的B用B+C代入便得到这样就得到三变量的摩根定律同理可将摩根定律推广到n变量 2. 对偶法则对偶法则 对于任何一个逻辑表达式F， 如果将其中的如果将其中的“+”换换成成“·”，， “·”换成换成“+”，， “１１”换成换成“0”，， “0”换成换成“1”，并保持原先的逻辑优先级，，并保持原先的逻辑优先级， 变量不变，变量不变， 两变量以上的非号不动，两变量以上的非号不动， 则可得原函数F的对偶式G， 且F和G互为对偶式 根据对偶法则知原式F成立，则其对偶式也一定成立 这样，我们只需记忆表3-1基本公式的一半即可，另一半按对偶法则可求出注意，在求对偶式时，为保持原式的逻辑优先关系， 应正确使用括号， 否则就要发生错误 如其对偶式为如不加括号，就变成显然是错误的  3. 反演法则反演法则 由原函数求反函数，称为反演或求反摩根定律是进行反演的重要工具 多次应用摩根定律，可以求出一个函数的反函数  例例 2求的反函数解解: 用摩根定律求 由上面可以看出反复用摩根定律即可，当函数较复杂时， 求反过程就相当麻烦。

为此，人们从实践中归纳出求反的法则其法则指出， 将原函数将原函数F中的中的“·”换成换成“+”, “+”换换成成“·”；； “0”换成换成“1”，， “1”换成换成“0”；； 原变量换原变量换成反变量，成反变量， 反变量换成原变量，长非号即两个或两个以上变反变量换成原变量，长非号即两个或两个以上变量的非号不变，量的非号不变， 即可得反函数如上例 与上面用摩根定律求出结果一样注意，与求对偶式一样，为了保持原函数逻辑优先顺序，应合理加括号，否则出错 3.1.3 基本公式应用基本公式应用1. 证明等式证明等式例例 3 用公式证明解解: 是是 的反函数的反函数例例 4 求 的反函数解解: 2. 逻辑函数不同形式的转换逻辑函数不同形式的转换 逻辑函数的形式是多种多样的，一个逻辑问题可以用多种形式的逻辑函数来表示， 每一种函数对应一种逻辑电路 逻辑函数的表达形式通常可分为五种： 与-或表达式、 与非-与非表达式、与-或非表达式、或-与表达式、或非-或非表达式。

例例 5 将函数与-或表达式 转换为其它形式解解 (1) 与非-与非式 将与或式两次取反，利用摩根定律可得(2) 与-或非式 首先求出反函数然后再取反一次即得与或非表达式_____CABACAABF+=+=（３） 或-与式  将与或非式用摩根定律展开， 即得或与表达式如下：(4) 或非-或非式 将或与表达式两次取反， 用摩根定律展开一次得或非-或非表达式图 3 –1 同一逻辑的五种逻辑图3.2 逻辑函数的代数法化简逻辑函数的代数法化简3.2.1 逻辑函数与逻辑图逻辑函数与逻辑图图 3 – 2 函数的逻辑图 从逻辑问题概括出来的逻辑函数式， 不一定是最简式 化简电路， 就是为了降低系统的成本，提高电路的可靠性， 以便用最少的门实现它们例如函数如直接由该函数式得到电路图，则如图3 - 3所示图 3 - 3F原函数的逻辑图 但如果将函数化简后其函数式为F=AC+B只要两个门就够了， 如图3 - 4所示图 3 – 4 函数化简后的逻辑图 3.2.2 逻辑函数化简的原则逻辑函数化简的原则 逻辑函数化简， 并没有一个严格的原则，通常遵循以下几条原则：  (1) 逻辑电路所用的门最少；  (2) 各个门的输入端要少；  (3) 逻辑电路所用的级数要少；  (4) 逻辑电路能可靠地工作。

3.2.3 与或逻辑函数的化简与或逻辑函数的化简 1. 应用吸收定律应用吸收定律1 任何两个相同变量的逻辑项， 只有一个变量取值不同(一项以原变量形式出现， 另一项以反变量形式出现)， 我们称为逻辑相邻项(简称相邻项) 如AB与 ，ABC与 都是相邻关系如果函数存在相邻项，可利用吸收定律1， 将它们合并为一项，同时消去一个变量 例例 6解解 有时两个相邻项并非典型形式， 应用代入法则可以扩大吸收定律1的应用范围 例例 7解解 令 ， 则例例 8解解令例例 9解解利用等幂律，一项可以重复用几次例例 10其中 与其余四项均是相邻关系，可以重复使用解解所以所以2. 应用吸收定律应用吸收定律2、、 3 利用它们，可以消去逻辑函数式中某些多余项和多余因子 若式中存在某单因子项，则包含该因子的其它项为多余项，可消去如其它项包含该因子的“反”形式， 则该项中的“反”因子为多余变量，可消去。

例例 11解解例例 12解解 令 , 则例例 13解解令3. 应用多余项定律应用多余项定律例例 14解解例例 15解解例例 16 化简解解4. 综合例子综合例子例例 17 化简解解5. 拆项法拆项法例例18 化简 解解 直接用公式已无法再化简时，可采用拆项法拆项法就是用 去乘某一项，将一项拆成两项，再利用公式与别的项合并达到化简的目的此例就是用 和 分别去乘第三项和第四项，然后再进行化简化简过程如下： 6. 添项法添项法 在函数中加入零项因子 ，利用加进的新项，进一步化简函数  例 19 化简  解解3.3 卡卡 诺诺 图图 化化 简简3.3.1 卡诺图化简的基本原理卡诺图化简的基本原理例例 20解解 3.3.2 逻辑函数的标准式逻辑函数的标准式——最小项最小项 1. 最小项标准式定义最小项标准式定义 最小项标准式是以“与或”形式出现的标准式。

 最小项： 对于一个给定变量数目的逻辑函数， 所有变量参加相“与”的项叫做最小项 在一个最小项中， 每个变量只能以原变量或反变量出现一次 例如，  一个变量A有二个最小项： 二个变量AB有四个最小项：三个变量ABC有八个最小项： 以此类推，四个变量ABCD共有24=16个最小项，n变量共有2n个最小项 最小项标准式：全是由最小项组成的“与或”式， 便是最小项标准式(不一定由全部最小项组成) 例如2. 由一般式获得最小项标准式由一般式获得最小项标准式(1) 代数法对逻辑函数的一般式采用添项法， 例如由上式可看出，第二项缺少变量A，第三项缺少变量B， 我们可以分别用 和 乘第二项和第三项， 其逻辑功能不变 (2) 真值表法将原逻辑函数A、B、C取不同值组合起来，得其真值表，而该逻辑函数是将F=1那些输入变量相或而成的，如表3 - 4所示 表 3 – 4 某逻辑函数的真值表从真值表上找得到表表 3 – 5 三变量最小项的编号三变量最小项的编号3. 最小项的性质最小项的性质(1) 对任何变量的函数式来讲，全部最小项之和为1， 即(2) 两个不同最小项之积为0， 即(3) n变量有2n项最小项， 且对每一最小项而言， 有n个最小项与之相邻。

3.3.3 卡诺图的结构卡诺图的结构 卡诺图的结构特点是需保证逻辑函数的逻辑相邻关系， 即图上的几何相邻关系卡诺图上每一个小方格代表一个最小项 为保证上述相邻关系， 每相邻方格的变量组合之间只允许一个变量取值不同为此，卡诺图的变量标注均采用循环码  一变量卡诺图：有21=2个最小项，因此有两个方格外标的0表示取A的反变量，1表示取A的原变量 其图如图3- 5(a)所示 二变量卡诺图：有2２=4个最小项，因此有四个方格外标的0、 1含义与前一样其图如图3 - 5(b)所示  三变量卡诺图：有23=8个最小项，其卡诺图如图3- 5(c)所示  四变量、 五变量卡诺图分别有24=16和25=32个最小项， 其卡诺图如图3 - 5(d)和3 - 5(e)所示 图 3 – 5 1~5变量的卡诺图3.3.4 逻辑函数的卡诺图表示法逻辑函数的卡诺图表示法 若将逻辑函数式化成最小项表达式，则可在相应变量的卡诺图中，表示出这函数如 ， 在卡诺图相应的方格中填上1，其余填0，上述函数可用卡诺图表示成图3 - 6。

如逻辑函数式是一般式，则应首先展开成最小项标准式 实际中，一般函数式可直接用卡诺图表示 图 3 – 6 逻辑函数用卡诺图表示 例例 21 将将 用卡诺用卡诺图表示  解解: 我们逐项用卡诺图表示，然后再合起来即可我们逐项用卡诺图表示，然后再合起来即可 ：在：在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： 即即m15 图 3 – 7 逻辑函数直接用卡诺图表示 3.3.5 相邻最小项合并规律相邻最小项合并规律 (1) 两相邻项可合并为一项， 消去一个取值不同的变量，保留相同变量；  (2) 四相邻项可合并为一项， 消去两个取值不同的变量， 保留相同变量， 标注为1→原变量，0→反变量；  (3) 八相邻项可合并为一项，消去三个取值不同的变量，保留相同变量，标注与变量关系同上。

 按上规律，不难得16个相邻项合并的规律这里需要指出的是：合并的规律是2n个最小项的相邻项可合并，不满足2n关系的最小项不可合并如2、4、8、16个相邻项可合并，其它的均不能合并，而且相邻关系应是封闭的，如m0、m1、m3、m2四个最小项，m0与m1，m1与m3，m3与m2均相邻，且m2和m0还相邻这样的2n个相邻的最小项可合并 而m0、m1、m3、m7，由于m0与m7不相邻，因而这四个最小项不可合并为一项 图 3 – 8 相邻最小项合并规律3.3.6 与或逻辑化简与或逻辑化简 运用最小项标准式， 在卡诺图上进行逻辑函数化简， 得到的基本形式是与或逻辑 其步骤如下：  (1) 将原始函数用卡诺图表示；  (2) 根据最小项合并规律画卡诺圈， 圈住全部“１”方格； (3) 将上述全部卡诺圈的结果， “或”起来即得化简后的新函数；  (4) 由逻辑门电路， 组成逻辑电路图 例例 22 化简解解 第一步： 用卡诺图表示该逻辑函数 ： 对应m3、m11对应m4、m5、m12、m13对应m1、m5对应m10、m11图 3-9 例22函数的卡诺图表示 第二步： 画卡诺圈圈住全部“１”方格。

 具体化简过程见图3 -10为便于检查，每个卡诺圈化简结果应标在卡诺图上图 3 — 10 例22的化简过程 第三步： 组成新函数  每一个卡诺圈对应一个与项，然后再将各与项“或”起来得新函数故化简结果为 第四步：画出逻辑电路 图 3 — 11 例22化简后的逻辑图例例 23 化简 解解 其卡诺图及化简过程如图3 - 12所示在卡诺圈有多种圈法时，要注意如何使卡诺圈数目最少，同时又要尽可能地使卡诺圈大比较图(a)、 (b)两种圈法，显然图(b)圈法优于图(a)圈法，因为它少一个卡诺圈，组成电路就少用一个与门故化简结果应为图(b)，逻辑图如图3 - 13所示其化简函数为图 3 – 12 例23化简过程图 3 – 13 例23逻辑图例例 24 化简 解解 该函数的卡诺图如图3 - 14(a)所示，化简情况如图(b)、 (c)所示图(b)是初学者常圈成的结果，图(c)是正确结果，即这二者的差别在于图(b)将m6和m14圈为二单元圈图(c)将m4、 m6、m12、m14圈成四单元圈前者化简结果为BCD，而后者为BD，少了一个变量。

图 3 – 14 例24的化简过程例例 25 化简 解解 其卡诺图及化简过程如图3-15(a)所示，逻辑图如图(b)所示，化简函数为 此例在圈的过程中注意四个角m0、m2、m8、m10可以圈成四单元圈图 3 – 15 例25化简过程及逻辑图例例 26 化简 解解 化简过程如图3 - 16(a)、 (b)所示， (a)中出现了多余圈m5、m7、m13、m15虽然可圈成四单元圈，但它的每一个最小项均被别的卡诺圈圈过，是多余圈，此时最佳结果应如图(b)所示化简结果的逻辑电路图如图3-16(c)所示，化简函数为图 3 – 16 例26化简过程及逻辑图3.3.7 其它逻辑形式的化简其它逻辑形式的化简 1. 与非逻辑形式与非逻辑形式 所谓与非式， 就是全由与非门实现该逻辑，前面讲逻辑函数相互变换时已讲过，将与或式两次求反即得与非式 其化简步骤如下：  第一步： 在卡诺图上圈“１”方格， 求得最简与或式； 第二步： 将最简与或式两次求反， 用求反律展开一次， 得到与非表示式；  第三步： 根据与非式， 用与非门组成逻辑电路。

例例 27 将例22~26用与非门实现 解解 例22与或结果为图 3 – 17 例22用与非门实现例23~例26各与非式为(例23)(例24)(例25)(例26)图 3 – 18 例23~例26的与非逻辑图(a) 例23； (b) 例24； (c) 例25； (d) 例26 2. 或与逻辑形式或与逻辑形式 首先从卡诺图上求其反函数，其方法是圈“０”方格， 然后再用摩根定律取反即得或与式  例例 28求求 的反函数和或与式 图 3 – 19 求例28的反函数 解解 求反函数过程如图3 - 19所示 其次， 再由反函数求得原函数， 利用摩根定律就得或与式 总结如下：  在卡诺图上圈“0”方格， 其化简结果： 变量为0→原变量；变量为1→反变量，然后变量再相“或”起来，就得每一或项，最后再将每一或项“与”起来而得或与式故此例可不通过求反函数，直接由上述过程得到或与式(如图3 - 20所示)：图 3 – 20 从卡诺图上直接圈得或与式其逻辑图如图3 - 21所示。

图 3 – 21 例28的或与逻辑图3. 或非逻辑形式或非逻辑形式将或与逻辑两次求反即得或非表示式：按逻辑表达式即可画出或非逻辑电路图，如图3 - 22所示图 3 – 22 例28的或与逻辑图 4. 与或非逻辑形式与或非逻辑形式 与或非逻辑形式可从两种途径得到：一种是从与或式得到， 例22将结果两次求反，不用摩根定律处理， 即得与或非式 另一种是求得反函数后，再求一次反，即不用摩根定律处理， 也可得与或非式例28的结果求反即得其逻辑图如图3 - 23所示一般前一种途径所得电路要多用一个反相器，所以常用后一种方法得最简与或非式 图 3 – 23 例22、例28的与或非逻辑图3.3.8 无关项及无关项的应用无关项及无关项的应用 逻辑问题分完全描述和非完全描述两种，逻辑问题分完全描述和非完全描述两种， 对应于变量的每一组取值，对应于变量的每一组取值， 函数都有定义，即在每一组函数都有定义，即在每一组变量取值下，变量取值下， 函数函数F都有确定的值，不是都有确定的值，不是“１１”就是就是“００”，，如表如表3 - 6所示。

所示 逻辑函数与每个最小项均有关，这类问题称逻辑函数与每个最小项均有关，这类问题称为完全描述问题为完全描述问题 表 3 – 6 完全描述 A B C A B CF F0 00 00 00 01 11 11 11 10 00 01 11 10 00 01 11 10 01 10 01 10 01 10 01 10 00 00 01 10 00 01 10 0表 3 – 7 非完全描述 A B C A B CF F0 00 00 00 01 11 11 11 10 00 01 11 10 00 01 11 10 01 10 01 10 01 10 01 10 01 10 0X X1 1X XX XX X 在实际的逻辑问题中，变量的某些取值组合不允许出现，在实际的逻辑问题中，变量的某些取值组合不允许出现， 或者是变量之间具有一定的制约关系我们将这类问题称为非或者是变量之间具有一定的制约关系我们将这类问题称为非完全描述，如表完全描述，如表3 - 7所示该函数只与部分最小项有关，而与所示。

该函数只与部分最小项有关，而与另一些最小项无关，我们用另一些最小项无关，我们用×或者用或者用φ表示 对于含有无关项逻辑函数可表示为也可表示为即不允许AB或AC或BC同为1图 3 – 24 不考虑无关项的化简图 3 – 25 考虑无关项函数化简例例29 化简解解 化简过程如图3 - 26所示，化简函数为图 3 – 26 例29化简及逻辑图例例 30 化简 解解 化简过程如图3 - 27所示，由于m11和m15对化简不利， 因此就没圈进图 3 – 27 例30化简及逻辑图例例 31 化简 解解 AB=0即表示A与B不能同时为1，则AB=11所对应的最小项，应视为无关项其卡诺图及化简过程如图3 - 28所示 化简函数为图 3 – 28 例31化简过程*3.3.9 输入只有原变量没有反变量的逻辑函数化简输入只有原变量没有反变量的逻辑函数化简 例例 32 用最少的门电路实现函数 解解 实现该逻辑的电路如图3 - 29所示，为了获得反变量多用了三个非门阻塞法主要就是解决在保证功能的前提下尽可能地少用非门。

图 3 – 29 例32逻辑图1. 代数法代数法代数法又称为综合反变量法我们可以证明同理我们也能证明这样原式变为图 3 – 30 例32采用综合反变量的逻辑图2. 阻塞法阻塞法图 3 – 31 卡诺图上表示全1方格如以四变量为例：二单元圈：m13与m15→ABDm7与m15→BCDm11与m15→ACDm14与m15→ABCm5，m7，m13，m15→BD m6，m7，m14，m15→BC m9，m11，m13，m15→AD m10，m11，m14，m15→AC m3，m7，m11，m15→CD m12，m3，m14，m15→AB 四单元圈：八单元圈：m1，m3，m5，m7m9，m11，m13，m15 m2，m3，m6，m7m10，m11，m14，m15 m4，m5，m6，m7m12，m13，m14，m15 m8，m9，m10，m11m12，m13，m14，m15 →D→C→B→A 所以，如果在化简时每次圈卡诺圈时均含全“１”方格，则就不出现反变量，因此也就节省了非门。

但在实际的逻辑问题中，逻辑函数不一定包含全“１”方格，按常规圈法必然出现反变量 例如按常规化简得其电路如图3 - 32所示图 3 – 32 化简过程及逻辑图 为了获得化简结果为原变量，我们将m7圈进，得C， 这结果显然与原功能不一致，因为它将m7也看成是“１”， 而实际是“０”为此，将m7作用除掉，怎样除掉呢? 用m7与圈得的结果相与即可证明如下： m7项称为阻塞项为了保证不出反变量，阻塞项也应围绕全“１”方格圈为了保证化简结果最佳，阻塞项应尽可能圈大仍以图3 - 33为例，我们将阻塞项圈为m6、m7，则阻塞项为AB，如图3 - 33(a)所示其正确性证明如下： 图 3 – 33 阻塞法化简结果例例 33 输入是单轨输入，用与非门实现 解解 图3-34(a)中A多圈了m7，应将其扣除，故为A ABCBC多圈了m7应将其扣除，故应为BC ABC，得化简函数为图 3 –34 例33阻塞法化简过程及逻辑图例例 34 输入只有原变量，用与非门实现解解 化简过程及化简后电路图如图3 - 35所示，其函数为图 3 – 35 例34阻塞法化简过程及逻辑图例例35 用阻塞法化简解解图 3 – 36 例35阻塞法化简过程 图(a)：此圈多圈了m3和m15，为了阻塞项也是原变量， 我们用为阻塞项， 故得其中m7和m11在其它项体现。

 图(b)：此圈本来只多圈了m15，我们将阻塞项扩大为故得故图(c)：本来只多圈了m15，我们将阻塞项扩大为图(d)： 其考虑与AD AB相同， 检查化简结果，包含了逻辑函数的全部最小项，故化简结果正确，其函数为图 3 – 37 例35化简后的逻辑图用常规化简法化简，其结果为例例 36 输入只有原变量，用或非门实现逻辑函数解解 化简过程及逻辑电路如图3 - 38所示图 3 – 38 例36的阻塞法化简及逻辑图例例 37 化简 解解 化简过程及逻辑图如图3 - 39所示图(a)、 (b)按常规化简，用了5个门图(c)、(d)用阻塞法化简，只用了4个门它们均扣除m5+m7+m13+m15=BD图 3 – 39 例37两种化简的比较3.3.10 多输出函数的化简多输出函数的化简图 3 – 40 多输出函数的方框图例例 38 对多输出函数 解解 各自的卡诺图和各自的化简结果如图3 - 41所图 3 – 41 例38各函数独立化简结果 如将两个输出函数视为一个整体，其化简过程如图3 - 42所示。

图 3 – 42 例38将F1F2函数作为整体考虑的化简。