工学第讲逻辑代数.pptx

第第 6 6 讲讲主讲主讲 孙霞孙霞安徽理工大学电气工程系安徽理工大学电气工程系数字电子技术基础数字电子技术基础3.3 逻辑函数的卡诺图法化简逻辑函数的卡诺图法化简 3.3.1 卡诺图化简的基本原理卡诺图化简的基本原理 在在两两个个乘乘积积项项中中，除除了了其其中中一一个个变变量量分分别别是是原原变变量量和和反反变变量量之之外外，其其它它变变量量都都相相同同时时，就就称称这这两两个个乘乘积积项项在在逻逻辑辑上上具具有有相相邻邻性性，或或称称为为相相邻邻项项。两两个个相相邻邻项项可可以以利利用用吸吸收收法法进进行行合合并并，合合并并时时可可消消去去此此相相异异的的变量。例如：变量。例如：对对于于一一个个三三变变量量的的乘乘积积项项，能能和和它它合合并并的的相相邻邻项项只可能有三个。例如：只可能有三个。例如：可与可与 合并的相邻项有：合并的相邻项有：A B CABCABCABC 对对n个个变变量量的的乘乘积积项项，则则可可找找到到n个个可可与与之之合合并并化化简简的的相相邻邻项项。为为了了方方便便地地找找出出这这种种对对应应关关系系，我我们们提提出出了了逻逻辑辑函函数数的的标标准准式式（最最小小项项表表达达式式）及及一一种种比比较较直直观观的的图图形形表表示法，这种方法就是卡诺图法。示法，这种方法就是卡诺图法。3.3.2 逻辑函数的标准式逻辑函数的标准式最小项表达式最小项表达式 1.逻辑函数的最小项及其性质逻辑函数的最小项及其性质 所所谓谓最最小小项项是是这这样样一一个个乘乘积积项项：在在该该乘乘积积项项中中含含有有逻逻辑辑问问题题的的全全部部变变量量，每每个个变变量量都都以以原原变变量量或或反反变变量的形式仅出现一次。量的形式仅出现一次。对于两个变量对于两个变量A、B来讲，有来讲，有4个最小项，个最小项，。而。而 就不是最小项。对于三变量就不是最小项。对于三变量A、B、C讲，有讲，有8个最小项，个最小项，AB AB AB AB、而而 就就不不是是最最小小项项。由由此此可可知知，n个个变变量量共共有有2n个个最最小小项项。为为叙叙述述和和书书写写方方便便，通通常常用用“mi”表表示示最最小小项项，并并按按如如下下规规则则确确定定下下标标“i”的的值值：把把变变量量的的每每一一个个组组合合的的取取值值都都看看成成二二进进制制码码，与与之之相相对对应应的的十十进进制制数数就就是是i的的值值。例例如如，三三变变量量最最小小项项标号如表标号如表3.3.1所示。所示。表表3.3.1 三变量最小项标号及真值表三变量最小项标号及真值表 由表由表3.3.1可以看出，最小项具有下列性质：可以看出，最小项具有下列性质：(1)对对于于任任意意一一个个最最小小项项有有且且仅仅有有一一组组变变量量的的取取值值使它等于使它等于1。(2)任意两个不同最小项的乘积恒为任意两个不同最小项的乘积恒为0。(3)全部最小项的和恒为全部最小项的和恒为1。2.逻辑函数的标准式逻辑函数的标准式最小项表达式最小项表达式 一一个个全全以以最最小小项项组组成成的的“与与或或”式式逻逻辑辑函函数数就就是是最小项表达式。它可以写成下列形式，例如最小项表达式。它可以写成下列形式，例如 任任何何一一个个逻逻辑辑函函数数都都能能展展开开成成最最小小项项表表达达式式，其其变换方法有两种：变换方法有两种：(1)逻辑函数逻辑函数真值表真值表最小项表达式。最小项表达式。例如，将例如，将F=AB+A C展开成最小项表达式。展开成最小项表达式。先列出真值表如表先列出真值表如表3.3.2所示。所示。再由真值表写出最小项表达式为再由真值表写出最小项表达式为表表3.3.2 真值表真值表 (2)逻辑函数逻辑函数 最小项表达式。最小项表达式。代数法 去反、脱括号、配项 例如，将例如，将 展开成最小项表达式。展开成最小项表达式。第一步，第一步，“去反去反”：第二步，第二步，“脱括号脱括号”：第第三三步步，“配配项项”：3.3.3 用卡诺图表示逻辑函数用卡诺图表示逻辑函数 1.卡诺图卡诺图 卡卡诺诺图图就就是是根根据据真真值值表表按按一一定定的的规规则则画画出出来来的的一一种种方方块块图图。此此规规则则就就是是使使逻逻辑辑相相邻邻的的关关系系表表现现在在几几何何位位置置上上的的相相邻邻，使使得得寻寻找找“可可以以合合并并化化简简”的的最最小小项项工工作作变变得得很很直直观观。由由于于卡卡诺诺图图中中“每每一一小小方方块块”都都表表示示了了一一个个“最最小小项项mi”，所所以以也也可可以以说说“卡卡诺诺图图就就是是最最小小项项方方块块图图”。图图3.3.12.卡诺图的画法卡诺图的画法 卡诺图的绘制方法很多，这里仅介绍其中的一种。卡诺图的绘制方法很多，这里仅介绍其中的一种。1)二变量卡诺图二变量卡诺图设设输输入入变变量量为为A、B(高高位位低低位位)。最最小小项项个个数数为为22=4个个，我们用我们用4个小方块分别表个小方块分别表示示4个最小项个最小项mi，如图，如图3.3.1所示。图中所示。图中左边一半区域标记为左边一半区域标记为“0”，用来表示反变量，用来表示反变量 。右边一半区域标记为右边一半区域标记为“1”，用来表示原变量，用来表示原变量B。上边一半区域标记为上边一半区域标记为“0”，用来表示反变量，用来表示反变量 。下边一半区域标记为下边一半区域标记为“1”，用来表示原变量，用来表示原变量A。2)三变量卡诺图三变量卡诺图 设设输输入入变变量量为为A、B、C(高高位位低低位位)。最最小小项项个个数数为为23=8个个，我我们们用用8个个小小方方块块分分别别表表示示mi，如如图图3.3.2所示。图中所示。图中 左边一半区域表示左边一半区域表示 ，右边一半区域表示，右边一半区域表示B。上边一半区域表示上边一半区域表示 ，下边一半区域表示，下边一半区域表示A。两侧一半区域表示两侧一半区域表示 ，中间一半区域表示，中间一半区域表示C。图图3.3.2 三变量卡诺图三变量卡诺图m00m11m44m55BCA000101m33m22m 77m661110 3)四变量卡诺图四变量卡诺图 设设输输入入变变量量为为A、B、C、D(高高位位低低位位)。最最小小项项个个数数为为24=16个个，我我们们用用16个个小小方方块块分分别别表表示示mi，如如图图3.3.3所示。所示。图图中中，、A、B、C、D都都各各占占卡卡诺诺图区域的一半。图区域的一半。为为了了进进一一步步掌掌握握卡卡诺诺图图的的构构图图思思想想，下下面面将将一一些些共共性及应该注意的地方再说明一下：性及应该注意的地方再说明一下：(1)n个变量的卡诺图有个变量的卡诺图有2n个小方块，分别表示个小方块，分别表示2n个个最小项。每个原变量及其反变量总是各占整个卡诺图最小项。每个原变量及其反变量总是各占整个卡诺图区域的一半。区域的一半。图图3.3.3 四变量卡诺图四变量卡诺图m00m11m44m55AB00010001m33m22m 77m661110CDm1212m1313m1515m1414m88m99m1111m10101110 (2)在在卡卡诺诺图图中中，任任意意相相邻邻的的两两格格所所表表示示的的最最小小项项都都仅仅有有一一个个因因子子不不同同，也也即即这这两两个个最最小小项具有项具有“相邻性相邻性”。(3)与与每每一一格格“相相邻邻”的的格格数数是是随随着着变变量量的的增增加加而而增增加加的的，“相相邻邻格格数数”等等于于“变变量量数数n”。例例如如，对对三三变变量量来来说说，每每一一格格总总有有三三格格相相邻邻，也即每个最小项总有三个最小项能与之合并。也即每个最小项总有三个最小项能与之合并。(4)在在寻寻找找“相相邻邻性性”上上要要注注意意上上、下下、左左、右右的的邻邻格格，因因为为卡卡诺诺图图可可以以卷卷起起来来看看，也也可可以以折叠起来看。折叠起来看。例例如如，四四变变量量卡卡诺诺图图，当当左左、右右卷卷起起来来时时，左左边边第第一一列列还还与与右右边边第第四四列列相相邻邻。当当上上、下下卷卷起来时，上边第一行还与下边第四行相邻。起来时，上边第一行还与下边第四行相邻。3.用卡诺图表示逻辑函数用卡诺图表示逻辑函数 如如果果一一个个逻逻辑辑函函数数F已已经经以以最最小小项项之之和和的的形形式式给给出出，则则只只要要根根据据变变量量数数画画出出对对应应的的卡卡诺诺图图框框，然然后后按按最最小小项项标标号号在在相相应应的的方方格格中中填填写写“1”，其其余余的的方方格格填填写写“0”，也即是按真值表来填写卡诺图。，也即是按真值表来填写卡诺图。例如，画出例如，画出 的卡诺图。的卡诺图。第一步，写出最小项表达式：第一步，写出最小项表达式：必须指出的是：必须指出的是：(1)上上面面画画的的是是函函数数F的的卡卡诺诺图图。若若要要画画 的的卡卡诺诺图图，则则只只要要将将 中中的的各各个个最最小小项项用用“0”填填进进卡卡诺诺图图，其余填其余填“1”。(2)为为避避免免烦烦琐琐，在在填填卡卡诺诺图图时时可可以以不不一一定定按按真真值值表表全全貌貌来来填填写写。例例如如，F的的卡卡诺诺图图，只只要要填填入入F=1的的方方格格，对对F=0的的方方格格可可以以不不填填(如如图图3.3.4(b)所所示示)。的的卡卡诺诺图图，只只要要填填入入 的的方方格格，对对 的的方方格格可以不填。可以不填。图图3.3.4 卡诺图卡诺图 000113120405171600011110BCA01（a）111100011110BCA01（b）简画成：简画成：下面介绍填图的技巧下面介绍填图的技巧寻找变量的公共部位。寻找变量的公共部位。当当我我们们熟熟悉悉卡卡诺诺图图之之后后，可可以以发发现现不不必必每每次次都都先先求求出出最最小小项项表表达达式式，而而只只要要写写出出函函数数F的的“与与或或”式式，然然后后“寻寻找找变变量量的的公公共共部部位位”，就就可可直直接接“填填进进”(也也称称“写入写入”)卡诺图了。卡诺图了。例例如如,上上题题中中的的乘乘积积项项 展展开开成成最最小小项项时时包包含含了了m3和和m2两两项项。如如果果将将 直直接接填填进进卡卡诺诺图图，只只要要在在填填图图时时寻寻找找出出 和和 B的的公公共共部部位位(既既要要在在 中中，如如图图3.3.5(A)阴阴影影部部分分，又又要要在在B中中，如如图图3.3.5(b)阴阴影影部部分分)，其其公公共共部部位位只只是是 m3,m2 两两格格了了，如如图图3.3.6所所示示。可可见与前面的结论一致。见与前面的结论一致。图3.3.5 和B的公共部位 图图3.3.6 B的卡诺图的卡诺图 00011110BCA01图图3.3.7 合并最小项合并最小项（a）（c ）1100011110BCA01F=ABC+ABC=BC（b）00011110CDAB0001F=ABCD+ABCD=ABD111110（d）1100011110BCA01F=AC100011110CDAB0001F=BCD11110图图3.3.7 合并最小项合并最小项111100011110BCA01F=ABC+ABC+ABC+ABC =AB+AB=B1100011110BCA0001F=BC111110D111100011110BCA01F=A（f）1100011110BCA0001F=BD111110D（h）图图3.3.7 合并最小项合并最小项 3.3.4 利用卡诺图化简逻辑函数利用卡诺图化简逻辑函数 1.合并最小项的规律合并最小项的规律 利利 用用 卡卡 诺诺 图图 合合 并并 最最 小小 项项，实实 质质 上上 就就 是是 在在 反反 复复 运运 用用 公公 式式 ，消消去去相相异异的的变变量量，从从而而得得到到最最简简的的“与与或或”式式。由由于于卡卡诺诺图图中中任任意意两两个个相相邻邻项项都都仅仅有有一一个个因因子子不不同同，所所以以两两个个相相邻邻项项(包包含含21个个方方格格)合合并并时时，可可以以消消去去一一个个相相异异的的变变量量。同同理理，4个个相相邻邻项项(包包含含22个个方方格格)合合并并为为一一项项时时，可可消消去去两两个个相相异异变变量量。8个个相相邻邻项项(包包含含23个个方方格格)合合并并为为一一项项时时，可可消消去去三三个个相相异异变变量量由由此此可可得得出出合合并并最最小小项项的的规规律律是是：2n个个相相邻邻项项(包包含含2n个个方方格格)合合并并为为一一项项时时，可可以以消消去去n个个相相异异变量，变量，n为为1、2、3等正整数。等正整数。具具体体的的化化简简方方法法是是画画包包围围圈圈。必必须须指指出出的的是是：卡卡诺诺图图包包围围圈圈只只能能圈圈2n个个方方格格。当当n=0时时，20=1，即即当当只只有有一一个个“孤孤立立”的的“1”时时，则则可可圈圈1格格，而而不不能能圈圈3格格、6格格。下下面面以以三三变变量量、四四变变量量卡卡诺诺图图为为例，来熟悉此合并规律，见图例，来熟悉此合并规律，见图3.3.7。下下面面介介绍绍“读读图图”(又又称称“读读出出”)技技巧巧：“根根据据包包围围圈圈所所处处的的变变量量位位置置，直直接接读读出出化化简简结结果果”。通通过过图图3.3.7中中的的一一些些例例题题可可以以看看出出，当当包包围围圈圈一一半半在在某某变变量量中中，一一半半不不在在这这个个变变量量中中，正正好好说说明明此此变变量量与与乘乘积积项项无无关关，可可消消去去。换换言言之之，整整个个包包围围圈圈处处在在哪哪个个变变量量中中，则则正正好好说说明明此此变变量量是是要要保保留留的的。例例如如，图图3.3.7(A)，整整个个包包围围圈圈处处在在变变量量B和和 中中，所所以以化化简简结结果果为为 。又又例例如如，图图3.3.7(h)，整整个个包包围围圈圈处处在在变变量量 和和 中，所以化简结果为中，所以化简结果为 。2.利用卡诺图化简逻辑函数利用卡诺图化简逻辑函数 下面通过举例来说明化简步骤。下面通过举例来说明化简步骤。解：第一步，画出解：第一步，画出F的卡诺图，如图的卡诺图，如图3.3.8所示。所示。第二步，正确选择乘积项，合并最小项。第二步，正确选择乘积项，合并最小项。将必须合并的最小项分别用圈圈出来，如图将必须合并的最小项分别用圈圈出来，如图3.3.8所示。所示。第第三三步步，将将每每个个包包围围圈圈的的结结果果相相加加，就就可可得得到到最最简简“与与或式或式”。所以化简结果为。所以化简结果为图图3.3.8 卡诺图化简逻辑函数卡诺图化简逻辑函数 00000110110111321415761121131514819111110011110BCBDABCABCD 画包围圈画包围圈(即选择乘积项即选择乘积项)时应当遵循的原则是：时应当遵循的原则是：(1)必须包含必须包含(覆盖覆盖)函数所有的最小项。函数所有的最小项。(2)按按照照“从从小小到到大大”的的次次序序，先先圈圈孤孤立立的的“1”，再再圈圈只只能能两两个个组组合合的的，再再圈圈只只能能四四个个组组合的合的 例例如如，在在图图3.3.9中中，图图(A)是是最最简简结结果果。图图(b)因因为为没没有有遵遵循循从从小小到到大大的的次次序序，先先去去圈圈了了一一个个不不必必要要圈圈的的大大圈圈(含含4格格)，然然后后，为为了了覆覆盖盖所所有有的的“1”，又圈了，又圈了4个小圈，所以就不是最简结果。个小圈，所以就不是最简结果。图图3.3.9 不用化简结果比较不用化简结果比较 (A)最简结果；最简结果；(b)非最简结果非最简结果此大圈此大圈多余了多余了11111111(a)11111111(b)(3)圈的圈数要尽可能的少圈的圈数要尽可能的少(即乘积项的总数要少即乘积项的总数要少)。因因为为每每个个圈圈对对应应一一个个“与与门门”，所所以以圈圈数数越越少少，所用的与门数也越少。所用的与门数也越少。(4)圈圈要要尽尽可可能能的的大大(使使每每个个乘乘积积项项所所含含有有的的因因子子最最少少)，不论是否与其他圈，不论是否与其他圈“相重相重”，也要尽可能地画大。，也要尽可能地画大。所所谓谓“相相重重”就就是是同同一一块块区区域域可可以以重重复复圈圈多多次次，但每个圈至少要包含一个但每个圈至少要包含一个“尚未被圈过尚未被圈过”的的“1”。例例如如，在在图图3.3.10中中，显显然然，图图(A)F=A+B是是最最简简结果，图结果，图(b)不是最简结果。不是最简结果。图图3.3.10 不用化简结果比较不用化简结果比较(A)最简结果；最简结果；(b)非最简结果非最简结果111100011110CDAB0001F=A+B（a ）1111111111101111000111100001F=AB+A（b）111111111110CDAB 3.3.5 其它函数形式的卡诺图化简其它函数形式的卡诺图化简 一一个个逻逻辑辑函函数数可可以以有有许许多多不不同同的的表表达达式式，其其基基本本形形式式有有五五种种。前前面面我我们们主主要要介介绍绍了了最最常常见见的的“与与或或”式式的的化化简简，下下面面再再简简略略地地介介绍绍一一下下其其它它四四种种函函数数形形式式的化简。的化简。1.与非式的化简与非式的化简 第一步，先求出最简与或式。第一步，先求出最简与或式。第第二二步步，利利用用“两两次次求求反反”法法及及摩摩根根定定律律，再再将将最简与或式转换成与非最简与或式转换成与非与非式。与非式。2.或与式的化简或与式的化简 通过实例介绍化简步骤。通过实例介绍化简步骤。例例 3.3.2 化化简简F=(0,4、5、7、8、12、13、14、15)为最简或与式。为最简或与式。解解：第第一一步步，先先在在卡卡诺诺图图上上用用圈圈“0”的的方方法法求求得得反函数反函数 的最简与或式为的最简与或式为 如图如图3.3.11所示。所示。并保持原式中的运算顺序，求得并保持原式中的运算顺序，求得 在在熟熟悉悉了了此此步步骤骤后后，我我们们可可以以发发现现不不必必每每次次都都先先求求出出 ，而而只只要要在在F的的卡卡诺诺图图上上圈圈“0”，就就可可直直接接读读出或与式的化简结果，如图出或与式的化简结果，如图3.3.12所示。所示。运算符变量常量原变量 反变量反变量 原变量图3.3.11 卡诺图法化简 图3.3.12 从卡诺图上直接读出或与式000001101110010302141517061121131151141809011010011110B+DBACDB+CA+C+D 3.或非式的化简或非式的化简 利利用用“两两次次求求反反”及及摩摩根根定定律律，将将最最简简或或与与式式转转换为或非式，具体方法见换为或非式，具体方法见2.4.3节。节。4.与或非式的化简与或非式的化简 最简便的化简方法是：最简便的化简方法是：第第一一步步，先先圈圈“0”，求求得得 的的最最简简与与或或式式。例例如，例如，例3.3.2中：中：第二步，再求第二步，再求 ，但不用摩根定律处理，得，但不用摩根定律处理，得 3.3.6 具有具有“约束约束”的逻辑函数的化简的逻辑函数的化简 1.什么是什么是“约束约束”“约约束束”是是用用来来说说明明逻逻辑辑函函数数中中各各逻逻辑辑变变量量之之间间互相有一种互相有一种“制约制约”关系的一个概念。关系的一个概念。“约束条件约束条件”所含的最小项称为所含的最小项称为“约束项约束项”，或，或称为称为“任意项任意项”、“禁止项禁止项”、“无关项无关项”都可以，都可以，用用“di”表示。填入卡诺图时用表示。填入卡诺图时用“”或或“”符号表符号表示。示。2.具有具有“约束约束”的逻辑函数的化简的逻辑函数的化简 对对于于具具有有“约约束束”的的逻逻辑辑函函数数，可可以以充充分分利利用用“约束条件约束条件”使表达式大大简化。现举例说明其优越性。使表达式大大简化。现举例说明其优越性。图图3.3.13 例例3.3.13图图 例例3.3.3 如如图图3.3.13，设设输输入入A、B、C、D是是十十进进制制数数x的的二二进进制制编编码码，当当x5时时，输输出出F为为1，求求F的的最最简简“与或与或”表达式。表达式。解：解：(1)先根据题意列真值表，如表先根据题意列真值表，如表3.3.3所示。所示。表中：表中：当当ABCD的取值为的取值为00000100时：时：因为因为x4，所以，所以F=0。当当ABCD的取值为的取值为01011001时：时：因为因为x5，所以，所以F=1。表表3.3.3 真值表真值表 因因为为对对十十进进制制数数来来说说，只只有有0、1、29这这10个个数数码码，对对应应的的二二进进制制编编码码是是00001001，所所以以对对于于ABCD的的这这6组组取取值值是是不不允允许许出出现现的的。也也就就是是说说，这这6个个最最小小项项是是“约约束束项项”。本本题题含含有有约约束束项项的的逻逻辑辑函函数数表表达达式式为为 F=m(5、6、7、8、9)+d(10、11、12、13、14、15)或写成或写成 F=m(5、6、7、8、9)d(10、11、12、13、14、15)=0 或或F=m(5、6、7、8、9)约束条件为约束条件为AB+AC=0 (2)用卡诺图化简用卡诺图化简 因因为为约约束束项项根根本本不不会会出出现现，或或不不允允许许出出现现，所所以以在在化化简简时时可可以以充充分分利利用用约约束束项项取取值值的的任任意意性性，有有时时将将约约束束项项认认为为是是1，有有时时又又可可将将其其认认为为是是0，完完全全视视需需要要而而定定，取取1或或取取0都都不不会会影影响响其其函函数数值值。下下面面我我们们来来比比较一下：较一下：不不考考虑虑约约束束条条件件的的化化简简如如图图3.3.14(A)所所示示，化化简简结结果为果为考虑约束条件的化简如图考虑约束条件的化简如图3.3.14(b)所示，化简结果为所示，化简结果为 图图3.3.14 卡诺图化简卡诺图化简(A)不考虑约束项的化简；不考虑约束项的化简；(b)考虑约束项的化简考虑约束项的化简 例例3.3.4 用卡诺图化简用卡诺图化简 F(A、B、C、D)=m(3、4、5、6、9、1415)+d(10、12、13)解解：将将m项项、d项项填填入入卡卡诺诺图图，化化简简过过程程如如图图3.3.15所示。所示。化简结果为化简结果为 在例在例3.3.4中，可根据需要将中，可根据需要将d12,d13两个约束项两个约束项看作看作1，圈进去了，而将，圈进去了，而将d10看作看作0，没圈进去。，没圈进去。图图3.3.15 例题例题3.3.4的化简过程的化简过程