第一章数字逻辑与数字电子_王立欣1_4节

1.4 卡诺图化简法卡诺图化简法 1.4.1 卡诺图卡诺图 1.4.2 逻辑函数如何填入卡诺图逻辑函数如何填入卡诺图 1.4.3 卡诺图化简法卡诺图化简法 m i 1.4 卡诺图化简法 1.4.1 卡诺图卡诺图 1.4.1.1 卡诺图的画法 卡诺图通常为正方形或矩形均匀分成2n个小格， 每个小格代表一个最小项。二个变量的卡诺图见下图 所示。 A B A B A BA B A BA B ( ) a 1 1 0 0 0 00 1 1 01 1 ( )b A B 01 23 m i 掌握卡诺图的构成特点，就可以从印 在表格旁边的AB、CD的“0”、“1”值直接写 出最小项的文字符号内容。例如在四变量 卡诺图中，第四行第二列相交的小方格。 00011110 0132 6754 12131514 891110 A B CD 00 01 11 10 0000010011001000 0010011011101010 0011011111111011 0001010111011001 表格第四行的“AB”标为“10”，应记为 ，第二列的“CD”标为“01”，记为 ， 所以该小格为 。 BA DC DCBA 1 0 000111 ( )b 10 BC A 000 001 100110100 011111101 0132 6754 ( ) a A A BCBCBCBC ABC AAABCBCBC ABC A BC A BC ABC 三变量卡诺图 卡诺图的特征 卡诺图上几何相邻的最小项逻辑上也相邻。 几何相邻 相接 行或列首尾相接 逻辑相邻两个最小项中只有一个变 、 量出现的形式不同 m i 1.4.1.2 邻接与化简 由于卡诺图中最小项的排列满足上述关系，所以可以用来化简 因为在最小项相加时，相邻两项可以进行合并，从而消去一个变 量。以四变量为例，m12与m13相邻接，则m12+m13为： CABDDCABDCABDCAB=+=+)( 00011110 0132 6754 12131514 891110 A B CD 00 01 11 10 0000010011001000 0010011011101010 0011011111111011 0001010111011001 所以，在卡诺图中只要将有关的最小项重新组合，就也可能 消去一些变量，使逻辑函数得到化简。 ABC BCD ABD m i 1.4.2 逻辑函数如何填入卡诺图逻辑函数如何填入卡诺图 1.4.2.1 与项如何填入卡诺图 例如，将逻辑式 填入卡诺图。它为一个三变量的逻辑式，结果见下图。 CABCBACBAP+=),( 10 AB C 0 0 1 00 0 0 100 01 11 10 00 1 100 CBA 11 11 0 1 CAB 1. 与项是最小项的形式 与项是最小项时，按最 小项编号的位置直接填入。 m i 与项不是最小项的形式，按邻接关系直接填入卡诺图。例如与项不是最小项的形式，按邻接关系直接填入卡诺图。例如 2. 与项不是最小项的形式 ABDCDADCBAP+=),( 先填 ,CDA 这是CD; 这是 A , 所以 处于第一第二行和第 三列的交点上（二行一列）。 CDA 再填 ,ABD这是AB ，这是D 。 00011110 AB CD 00 01 11 10 1111 0 0 11 所以 处于第一第二行和第 三列的交点上（二行一列）。 CDA 所以ABD处于第三行和第二、第 三列的交点上（一行二列）。 1 1 3 7 15 11 13 CDBABCDA CDBBACDA += +=)( 00 m i 00011110 AB CD 00 01 11 10 例：将逻辑式P= + 填入卡诺图 CBDB 先填 ，CB这是B，这是 ；C 11 11 1 1 00 CB 这一与项处于第二、 第三行和第一、第二列的交 点处（二行二列）。 DB再填 ，B这是 ，D这是 。 0 0 00 DB 这一与项处于第一、 第四行和第一、第四列的交点 处（二行二列）。1 11 1 m i 例：将逻辑式 填入卡诺图DABCBP+= AB 00011110 CD 00 01 11 10 11 11 C BBC 11 AB D ABD 填CB 填DAB m i 由上述各例题可以看出，与项中变量数 越少，在卡诺图中占的小格越多； 最小项在卡诺图中占1个小格；与最小项 相比，少一个变量占二个小格；少二个变 量占四个小格；少三个变量占八个小 格，。 m i 卡诺图中的与项对应的小格，只能一个一组；二个一组； 四个一组；八个一组，即按2i 的规律组成矩形带。i为缺 少的变量数。以四变量为例，与项只有一个变量，即缺3个变 量，应占23个小格，且组成一个矩形带；与项只有二个变量， 即缺2个变量，应占22个小格，且组成一个矩形带；与项只有 三个变量，即缺1个变量，应占21个小格，且组成一个矩形带。 我们的任务是化简逻辑函数，将与或型逻辑 函数填入卡诺图后，这样原来的逻辑函数就以最 小项的面貌出现在卡诺图中。然后，经过重新组 合，将具有“1”的小格按照 2i 的规律尽可能大地 圈成矩形带。这样新得到的逻辑函数可能会更简 单一些。 下面我们来讨论如何用卡诺图进行化简。也 就是如何重新组合带有“1”的小格，如何尽可能 大地圈成矩形带，以得到最简与或逻辑式。 m i 1.4.3 卡诺图化简步骤卡诺图化简步骤 1.4.3.1 如何使与项最简 由前面的讨论可知，卡诺图中的矩形带包括的小格越多， 对应的与项的变量数就越少。所以一个需要化简的逻辑函数， 填入卡诺图后，经过重新组合，圈出的矩形带应越大越好。 CACBAP+= 该逻辑式是否最简？显然不是最简 形式，因为 CBCACBA ABACCACBAP +=+= +=+= )( )( 00011110 1 AB CD 00 01 11 10 1 11 11 显然 对应下面四个小格； 对应上面四个小格，中间二个小格被 覆盖，属于公共享有。 CACB 所以，为使与项最简，圈矩形带时，小格可以公用，互相覆盖。 例如左图若把上面两个小方格圈在 一起有 ，下面四个小方格圈在一 起有 ，于是逻辑式为： CBA CA CB CA m i 1.4.3.2 关于覆盖 00011110 1 AB CD 00 01 11 10 1 1 1 111 1 但是在小格覆盖时，需要注意，每一个矩形带中至少要 有一个小格是独立的，即没有被其他矩形带所覆盖。 CBA CDA ABC DCA BD 例如下图中，四个矩 形带对应的与项分别是 CBA CDA ABC 中间的四个小格圈成的 矩形带对应的与项BD虽然最 简单， 但 BD 对应的四个小格 一一被其他四个矩形带所覆盖， 所以就应从最简与或式中取消， 最简与或式为 DCAABCCDACBAP+= DCA m i 总之，一个矩形带中的所有小格最少要有一个未被覆盖， 这个矩形带所代表的与项才是化简后的与或型逻辑式中不可 缺少的项。反之，一个矩形带中的所有小格都被其它矩形带 所覆盖，那么这个矩形带所代表的与项就不是独立的，如果 写入与或型逻辑式中就是多余的。 卡诺图化简法的步骤如下： 1逻辑式填入卡诺图，如果逻辑式不是与或型， 先将逻辑式转换为与或型。 2尽可能将矩形带圈大一些。 3选出至少有一个小格是独立的矩形带，写出它 们所对应的最简与项的逻辑和。 4如有遗漏，添上遗漏小格所对应的一个最简与 项，它们的逻辑和就是最简化的与或型逻辑式。 m i 例例:化简 DBADCAABCBAP+= 00011110 AB CD 00 01 11 10 11 1 1 11 111110 11 11 01 0 0 11 00 00011110 1 AB CD 00 01 11 10 1 11 1 1 11 1 1 化简结果 DCADBACBAP+= 动画1- 1动画1- 2 00011110 18191716 20212322 30312928 26272524 1000110001000000 1010111001100010 1011111101110011 1001110101010001 m i 00011110 0132 6754 12131514 891110 A B CD 00 01 11 10 0000010011001000 0010011011101010 0011011111111011 0001010111011001 EE 最小项编号变量按EABCD顺序 00011110 18191716 20212322 30312928 26272524 1000110001000000 1010111001100010 1011111101110011 1001110101010001 轴 五变量卡诺图的画法：五变量卡诺图 是在四变量卡诺图的基础上翻转构成的。 动画1- 3 我们将逻辑函数中带有 的与项填入轴左侧的 四变量 卡诺图中；将带有E 的与项填入轴右侧的E 四变量卡诺图中； 不带变量E 的与项填入以轴为对称的二个四变量卡诺图中。 EE 习题 ABC ABD ACD CD ABC ACD+ ACACBDBD+ P 1 ( A , B , C ) = P 1 ( A , B , C ) = =)7 , 6 , 5 , 2 , 1 , 0(),(mCBAF ) P 3 ( A , B , C , D ) = =)15,14,13,12,10, 9 , 8 , 6 , 4 , 1 , 0(),(mDCBAF A CDBCDACDABCD()+ 答案 DADBCBAB+ CBACBA+CBCAAB+ DA+ ABCDDCBADCBADCBA+ DCDC+ 1 1 111 AB CD 00 01 11 10 0001 1110 1 1 1 1 11 =)15,14,13,12,10, 9 , 8 , 6 , 4 , 1 , 0(),(mDCBAF DADBCBAB+ 1 11 AB C 00 01 11 10 01 1 1 1 =)7 , 6 , 5 , 2 , 1 , 0(),(mCBAF CBACBA+CBCAAB+ 1 11 AB C 00 01 11 10 01 1 1 1