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

三 布尔代数与逻辑函数化简3.1 基本公式和法则 3.2 逻辑函数的代数法化简 3.3 卡诺图化简 1.3.1 基本公式和规则3.1.1 基本公式表 3 1 基本公式2.续表表 3 2 证明分配律的真值表3.由表中可知A+BC=(A+B)(A+C)在吸收律1的证明中，只证第二式：在吸收律2的证明中，也只证第二式：A+AB=A(1+B)=A(因为1+B=1)吸收律3也只证第二式：（证毕）（证毕）（证毕）4.表 3 3 求反律的真值表多余项定律证明如下：5.多余项定律可推广为6.3.1.2 基本法则 1、代入法则 逻辑等式中的任何变量A，都可用另一函数Z代替，等式仍然成立。代入法则可以扩大基本公式的应用范围。7.例 1 证明解这是两变量的求反公式，若将等式两边的B用B+C代入便得到这样就得到三变量的摩根定律。同理可将摩根定律推广到n变量8.2.对偶法则 对于任何一个逻辑表达式F，如果将其中的“+”换成“”，“”换成“+”，“”换成“0”，“0”换成“1”，并保持原先的逻辑优先级，变量不变，两变量以上的非号不动，则可得原函数F的对偶式G，且F和G互为对偶式。根据对偶法则知原式F成立，则其对偶式也一定成立。这样，我们只需记忆表3-1基本公式的一半即可，另一半按对偶法则可求出。注意，在求对偶式时，为保持原式的逻辑优先关系，应正确使用括号，否则就要发生错误。如9.其对偶式为如不加括号，就变成显然是错误的。10.3.反演法则 由原函数求反函数，称为反演或求反。摩根定律是进行反演的重要工具。多次应用摩根定律，可以求出一个函数的反函数。例 2求的反函数解:用摩根定律求11.由上面可以看出反复用摩根定律即可，当函数较复杂时，求反过程就相当麻烦。为此，人们从实践中归纳出求反的法则。其法则指出，将原函数F中的“”换成“+”,“+”换成“”；“0”换成“1”，“1”换成“0”；原变量换成反变量，反变量换成原变量，长非号即两个或两个以上变量的非号不变，即可得反函数。如上例 与上面用摩根定律求出结果一样。注意，与求对偶式一样，为了保持原函数逻辑优先顺序，应合理加括号，否则出错。12.3.1.3 基本公式应用1.证明等式例 3 用公式证明解:是 的反函数13.例 4 求 的反函数。解:14.2.逻辑函数不同形式的转换 逻辑函数的形式是多种多样的，一个逻辑问题可以用多种形式的逻辑函数来表示，每一种函数对应一种逻辑电路。逻辑函数的表达形式通常可分为五种：与-或表达式、与非-与非表达式、与-或非表达式、或-与表达式、或非-或非表达式。15.例 5 将函数与-或表达式 转换为其它形式。解 (1)与非-与非式。将与或式两次取反，利用摩根定律可得(2)与-或非式。首先求出反函数然后再取反一次即得与或非表达式_CABACAABF+=+=16.（）或-与式。将与或非式用摩根定律展开，即得或与表达式如下：(4)或非-或非式。将或与表达式两次取反，用摩根定律展开一次得或非-或非表达式17.图 3 1 同一逻辑的五种逻辑图18.3.2 逻辑函数的代数法化简3.2.1 逻辑函数与逻辑图图 3 2 函数的逻辑图19.从逻辑问题概括出来的逻辑函数式，不一定是最简式。化简电路，就是为了降低系统的成本，提高电路的可靠性，以便用最少的门实现它们。例如函数如直接由该函数式得到电路图，则如图3-3所示。图 3-3F原函数的逻辑图20.但如果将函数化简后其函数式为F=AC+B只要两个门就够了，如图3-4所示。图 3 4 函数化简后的逻辑图21.3.2.2 逻辑函数化简的原则 逻辑函数化简，并没有一个严格的原则，通常遵循以下几条原则：(1)逻辑电路所用的门最少；(2)各个门的输入端要少；(3)逻辑电路所用的级数要少；(4)逻辑电路能可靠地工作。22.3.2.3 与或逻辑函数的化简 1.应用吸收定律1 任何两个相同变量的逻辑项，只有一个变量取值不同(一项以原变量形式出现，另一项以反变量形式出现)，我们称为逻辑相邻项(简称相邻项)。如AB与 ，ABC与 都是相邻关系。如果函数存在相邻项，可利用吸收定律1，将它们合并为一项，同时消去一个变量。23.例 6解 有时两个相邻项并非典型形式，应用代入法则可以扩大吸收定律1的应用范围。例 7解 令 ，则24.例 8解令25.例 9解利用等幂律，一项可以重复用几次。26.例 10其中 与其余四项均是相邻关系，可以重复使用。解所以27.2.应用吸收定律2、3 利用它们，可以消去逻辑函数式中某些多余项和多余因子。若式中存在某单因子项，则包含该因子的其它项为多余项，可消去。如其它项包含该因子的“反”形式，则该项中的“反”因子为多余变量，可消去。例 11解28.例 12解 令 ,则29.例 13解令30.3.应用多余项定律例 14解例 15解31.例 16 化简解32.4.综合例子例 17 化简解33.5.拆项法例18 化简 解 直接用公式已无法再化简时，可采用拆项法。拆项法就是用 去乘某一项，将一项拆成两项，再利用公式与别的项合并达到化简的目的。此例就是用 和 分别去乘第三项和第四项，然后再进行化简。化简过程如下：34.6.添项法 在函数中加入零项因子 ，利用加进的新项，进一步化简函数。例 19 化简 解35.3.3 卡 诺 图 化 简3.3.1 卡诺图化简的基本原理例 20解36.3.3.2 逻辑函数的标准式最小项 1.最小项标准式定义 最小项标准式是以“与或”形式出现的标准式。最小项：对于一个给定变量数目的逻辑函数，所有变量参加相“与”的项叫做最小项。在一个最小项中，每个变量只能以原变量或反变量出现一次。例如，一个变量A有二个最小项：二个变量AB有四个最小项：37.三个变量ABC有八个最小项：以此类推，四个变量ABCD共有24=16个最小项，n变量共有2n个最小项。最小项标准式：全是由最小项组成的“与或”式，便是最小项标准式(不一定由全部最小项组成)。例如38.2.由一般式获得最小项标准式(1)代数法。对逻辑函数的一般式采用添项法，例如由上式可看出，第二项缺少变量A，第三项缺少变量B，我们可以分别用 和 乘第二项和第三项，其逻辑功能不变。39.(2)真值表法。将原逻辑函数A、B、C取不同值组合起来，得其真值表，而该逻辑函数是将F=1那些输入变量相或而成的，如表3-4所示。表 3 4 某逻辑函数的真值表40.从真值表上找得到表 3 5 三变量最小项的编号41.3.最小项的性质(1)对任何变量的函数式来讲，全部最小项之和为1，即(2)两个不同最小项之积为0，即(3)n变量有2n项最小项，且对每一最小项而言，有n个最小项与之相邻。42.3.3.3 卡诺图的结构 卡诺图的结构特点是需保证逻辑函数的逻辑相邻关系，即图上的几何相邻关系。卡诺图上每一个小方格代表一个最小项。为保证上述相邻关系，每相邻方格的变量组合之间只允许一个变量取值不同。为此，卡诺图的变量标注均采用循环码。一变量卡诺图：有21=2个最小项，因此有两个方格。外标的0表示取A的反变量，1表示取A的原变量。其图如图3-5(a)所示。43.二变量卡诺图：有2=4个最小项，因此有四个方格。外标的0、1含义与前一样。其图如图3-5(b)所示。三变量卡诺图：有23=8个最小项，其卡诺图如图3-5(c)所示。四变量、五变量卡诺图分别有24=16和25=32个最小项，其卡诺图如图3-5(d)和3-5(e)所示。44.图 3 5 15变量的卡诺图45.3.3.4 逻辑函数的卡诺图表示法 若将逻辑函数式化成最小项表达式，则可在相应变量的卡诺图中，表示出这函数。如 ，在卡诺图相应的方格中填上1，其余填0，上述函数可用卡诺图表示成图3-6。如逻辑函数式是一般式，则应首先展开成最小项标准式。实际中，一般函数式可直接用卡诺图表示。46.图 3 6 逻辑函数用卡诺图表示47.例 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；48.：在A=C=0,D=1对应方格中填1，即m1、m5；ABCD：即m15。图 3 7 逻辑函数直接用卡诺图表示49.3.3.5 相邻最小项合并规律 (1)两相邻项可合并为一项，消去一个取值不同的变量，保留相同变量；(2)四相邻项可合并为一项，消去两个取值不同的变量，保留相同变量，标注为1原变量，0反变量；(3)八相邻项可合并为一项，消去三个取值不同的变量，保留相同变量，标注与变量关系同上。50.按上规律，不难得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不相邻，因而这四个最小项不可合并为一项。51.图 3 8 相邻最小项合并规律52.3.3.6 与或逻辑化简 运用最小项标准式，在卡诺图上进行逻辑函数化简，得到的基本形式是与或逻辑。其步骤如下：(1)将原始函数用卡诺图表示；(2)根据最小项合并规律画卡诺圈，圈住全部“”方格；(3)将上述全部卡诺圈的结果，“或”起来即得化简后的新函数；(4)由逻辑门电路，组成逻辑电路图。53.例 22 化简解 第一步：用卡诺图表示该逻辑函数。：对应m3、m11对应m4、m5、m12、m13对应m1、m5对应m10、m11图 3-9 例22函数的卡诺图表示54.第二步：画卡诺圈圈住全部“”方格。具体化简过程见图3-10。为便于检查，每个卡诺圈化简结果应标在卡诺图上。图 3 10 例22的化简过程55.第三步：组成新函数。每一个卡诺圈对应一个与项，然后再将各与项“或”起来得新函数。故化简结果为 第四步：画出逻辑电路。图 3 11 例22化简后的逻辑图56.例 23 化简 解 其卡诺图及化简过程如图3-12所示。在卡诺圈有多种圈法时，要注意如何使卡诺圈数目最少，同时又要尽可能地使卡诺圈大。比较图(a)、(b)两种圈法，显然图(b)圈法优于图(a)圈法，因为它少一个卡诺圈，组成电路就少用一个与门。故化简结果应为图(b)，逻辑图如图3-13所示。其化简函数为57.图 3 12 例23化简过程58.图 3 13 例23逻辑图59.例 24 化简 解 该函数的卡诺图如图3-14(a)所示，化简情况如图(b)、(c)所示。图(b)是初学者常圈成的结果，图(c)是正确结果，即这二者的差别在于图(b)将m6和m14圈为二单元圈。图(c)将m4、m6、m12、m14圈成四单元圈。前者化简结果为BCD，而后者为BD，少了一个变量。60.图 3 14 例24的化简过程61.例 25 化简 解 其卡诺图及化简过程如图3-15(a)所示，逻辑图如图(b)所示，化简函数为 此例在圈的过程中注意四个角m0、m2、m8、m10可以圈成四单元圈。62.图 3 15 例25化简过程及逻辑图63.例 26 化简 解 化简过程如图3-16(a)、(b)所示，(a)中出现了多余圈。m5、m7、m13、m15虽然可圈成四单元圈，但它的每一个最小项均被别的卡诺圈圈过，是多余圈，此时最佳结果应如图(b)所示。化简结果的逻辑电路图如图3-16(c)所示，化简函数为64.图 3 16 例26化简过程及逻辑图65.3.3.7 其它逻辑形式的化简 1.与非逻辑形式 所谓与非式，就是全由与非门实现该逻辑，前面讲逻辑函数相互变换时已讲过，将与或式两次求反即得与非式。其化简步骤如下：第一步：在卡诺图上圈“”方格，求得最简与或式；第二步：将最简与或式两次求反，用求反律展开一次，得到与非表示式；第三步：根据与非式，用与非门组成逻辑电路。66.例 27 将例2226用与非门实现。解 例22与或结果为图 3 17 例22用与非门实现67.例23例26各与非式为(例23)(例24)68.(例25)(例26)69.图 3 18 例23例26的与非逻辑图(a)例23；(b)例24；(c)例25；(d)例2670.2.或与逻辑形式 首先从卡诺图上求其反函数，其方法是圈“”方格，然后再用摩根定律取反即得或与式。例 28求 的反函数和或与式。图 3 19 求例28的反函数71.解 求反函数过程如图3-19所示。其次，再由反函数求得原函数，利用摩根定律就得或与式。72.总结如下：在卡诺图上圈“0”方格，其化简结果：变量为0原变量；变量为1反变量，然后变量再相“或”起来，就得每一或项，最后再将每一或项“与”起来而得或与式。故此例可不通过求反函数，直接由上述过程得到或与式(如图3-20所示)：73.图 3 20 从卡诺图上直接圈得或与式74.其逻辑图如图3-21所示。图 3 21 例28的或与逻辑图75.3.或非逻辑形式将或与逻辑两次求反即得或非表示式：76.按逻辑表达式即可画出或非逻辑电路图，如图3-22所示。图 3 22 例28的或与逻辑图77.4.与或非逻辑形式 与或非逻辑形式可从两种途径得到：一种是从与或式得到，例22将结果两次求反，不用摩根定律处理，即得与或非式。另一种是求得反函数后，再求一次反，即不用摩根定律处理，也可得与或非式。例28的结果求反即得。其逻辑图如图3-23所示。一般前一种途径所得电路要多用一个反相器，所以常用后一种方法得最简与或非式。78.图 3 23 例22、例28的与或非逻辑图79.3.3.8 无关项及无关项的应用 逻辑问题分完全描述和非完全描述两种，对应于变量的每一组取值，函数都有定义，即在每一组变量取值下，函数F都有确定的值，不是“”就是“”，如表3-6所示。逻辑函数与每个最小项均有关，这类问题称为完全描述问题。80.表 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 081.表 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所示。该函数只与部分最小项有关，而与另一些最小项无关，我们用或者用表示。82.对于含有无关项逻辑函数可表示为也可表示为即不允许AB或AC或BC同为1。83.图 3 24 不考虑无关项的化简84.图 3 25 考虑无关项函数化简85.例29 化简解 化简过程如图3-26所示，化简函数为图 3 26 例29化简及逻辑图86.例 30 化简 解 化简过程如图3-27所示，由于m11和m15对化简不利，因此就没圈进。图 3 27 例30化简及逻辑图87.例 31 化简 解 AB=0即表示A与B不能同时为1，则AB=11所对应的最小项，应视为无关项。其卡诺图及化简过程如图3-28所示。化简函数为88.图 3 28 例31化简过程89.*3.3.9 输入只有原变量没有反变量的逻辑函数化简 例 32 用最少的门电路实现函数 解 实现该逻辑的电路如图3-29所示，为了获得反变量多用了三个非门。阻塞法主要就是解决在保证功能的前提下尽可能地少用非门。图 3 29 例32逻辑图90.1.代数法代数法又称为综合反变量法。我们可以证明91.同理我们也能证明这样原式变为92.图 3 30 例32采用综合反变量的逻辑图93.2.阻塞法图 3 31 卡诺图上表示全1方格94.如以四变量为例：二单元圈：m13与m15ABDm7与m15BCDm11与m15ACDm14与m15ABC95.m5，m7，m13，m15BD m6，m7，m14，m15BC m9，m11，m13，m15AD m10，m11，m14，m15AC m3，m7，m11，m15CD m12，m3，m14，m15AB 四单元圈：96.八单元圈：m1，m3，m5，m7m9，m11，m13，m15 m2，m3，m6，m7m10，m11，m14，m15 m4，m5，m6，m7m12，m13，m14，m15 m8，m9，m10，m11m12，m13，m14，m15 DCBA97.所以，如果在化简时每次圈卡诺圈时均含全“”方格，则就不出现反变量，因此也就节省了非门。但在实际的逻辑问题中，逻辑函数不一定包含全“”方格，按常规圈法必然出现反变量。例如按常规化简得98.其电路如图3-32所示。图 3 32 化简过程及逻辑图99.为了获得化简结果为原变量，我们将m7圈进，得C，这结果显然与原功能不一致，因为它将m7也看成是“”，而实际是“”。为此，将m7作用除掉，怎样除掉呢?用m7与圈得的结果相与即可。证明如下：m7项称为阻塞项。为了保证不出反变量，阻塞项也应围绕全“”方格圈。为了保证化简结果最佳，阻塞项应尽可能圈大。仍以图3-33为例，我们将阻塞项圈为m6、m7，则阻塞项为AB，如图3-33(a)所示。其正确性证明如下：100.图 3 33 阻塞法化简结果101.例 33 输入是单轨输入，用与非门实现 解 图3-34(a)中A多圈了m7，应将其扣除，故为A ABC。BC多圈了m7应将其扣除，故应为BC ABC，得化简函数为102.图 3 34 例33阻塞法化简过程及逻辑图103.例 34 输入只有原变量，用与非门实现解 化简过程及化简后电路图如图3-35所示，其函数为104.图 3 35 例34阻塞法化简过程及逻辑图105.例35 用阻塞法化简解图 3 36 例35阻塞法化简过程106.图(a)：此圈多圈了m3和m15，为了阻塞项也是原变量，我们用为阻塞项，故得其中m7和m11在其它项体现。图(b)：此圈本来只多圈了m15，我们将阻塞项扩大为故得107.故图(c)：本来只多圈了m15，我们将阻塞项扩大为图(d)：其考虑与AD AB相同，检查化简结果，包含了逻辑函数的全部最小项，故化简结果正确，其函数为108.图 3 37 例35化简后的逻辑图用常规化简法化简，其结果为109.例 36 输入只有原变量，用或非门实现逻辑函数解 化简过程及逻辑电路如图3-38所示。图 3 38 例36的阻塞法化简及逻辑图110.例 37 化简 解 化简过程及逻辑图如图3-39所示。图(a)、(b)按常规化简，用了5个门。图(c)、(d)用阻塞法化简，只用了4个门。它们均扣除m5+m7+m13+m15=BD。111.图 3 39 例37两种化简的比较112.3.3.10 多输出函数的化简图 3 40 多输出函数的方框图113.例 38 对多输出函数 解 各自的卡诺图和各自的化简结果如图3-41所图 3 41 例38各函数独立化简结果114.如将两个输出函数视为一个整体，其化简过程如图3-42所示。图 3 42 例38将F1F2函数作为整体考虑的化简115.