卡诺图化简法

(b)
1 10
CD 00 01 11 10 AB 0 0 0 0 00 0 0 01 0 011 0 0 10
0 4 1 5 3 7 2 6
0 1 0 1 00 0 1 01 0 111 0 1 10 1 1 1 1 00 1 1 01 1 111 1 1 10
12 8 13 9 15 11 14 10
CD 00 AB 00 0
0 01
先填 A CD , 这是 A ,
1 01 11 1 1
这是CD;
10
1 D 处于第一第二行和第 三列的交点上（二行一列）。 再填 ABD , 这是AB ， 这是D 。
7
11 1 1 10
1
1
15
所以ABD处于第三行和第二、第 三列的交点上（一行二列）。
我们的任务是化简逻辑函数，将与或型逻辑函 数填入卡诺图后，这样原来的逻辑函数就以最小项 的面貌出现在卡诺图中。然后，经过重新组合，将 具有“1”的小格按照 2i 的规律尽可能大地圈成矩形 带。这样新得到的逻辑函数可能会更简单一些。 下面我们来讨论如何用卡诺图进行化简。也就 是如何重新组合带有“1”的小格，如何尽可能大地 圈成矩形带，以得到最简与或逻辑式。
CD 00 01 11 10 AB 0 0 0 0 00 0 0 01 0 011 0 0 10
0 4 1 5 3 7 2 6
ABD
0 1 0 1 00 0 1 01 0 111 0 1 10
卡诺图的是按邻接规律 构建的，在几何位置上相邻 的小格是邻接的。同时，第 一行和第四行也是邻接的； 第一列和第四列也是邻接的； 四个角也是邻接的。
P A BC AC
1 1 1
BC
该逻辑式是否最简？显然不是最简 形式，因为
P A BC AC C ( A B A)
AC
( A B)C AC BC
显然 AC 对应下面四个小格； BC 对应上面四个小格，中间二个小格被 覆盖，属于公共享有。 所以，为使与项最简，圈矩形带时，小格可以公用，互相覆盖。
mi
17.6.3.2 关于覆盖
但是在小格覆盖时，需要注意，每一个矩形带中至少要 有一个小格是独立的，即没有被其他矩形带所覆盖。
CD 00 AB 00
01
11 1
10
例如下图中，四个矩 形带对应的与项分别是
A CD
ABC
A BC A CD ABC AC D
中间的四个小格圈成的 矩形带对应的与项BD虽然最 简，但 BD 对应的四个小格 一一被其他四个矩形带所覆盖， 所以就应从最简与或式中取消， 最简与或式为
B B A B 0
0 2
1 01 11
1 3
A A B AB A AB AB
0 00 1 10
(a )
(b)
mi
这是三变量卡诺图
BC BC BC BC A BC 00
0 4
01
1 5
11
3 7
10
2 6
A A BC A BC A BC A BC A A BC A BC A BC A BC
(a )
0 0 00 00 1 0 11 0 10 1 1 00 1 01 1 11
ABC
1 1 1 1 00 1 1 01 1 111 1 1 10
12 8 13 9 15 11
14 10
1 0 1 0 00 1 0 01 1 011 1 0 10
BCD
mi
17.6.2 与项的读取和填写 17.6.2.1 与项如何填入卡诺图 1. 与项是最小项的形式 例如，将逻辑式 P( A, B, C) A B C ABC
A BC
01 11 10
1
1
1
BD
1 1 1 1
AC D
P A BC A CD ABC AC D
mi
总之，一个矩形带中的所有小格最少要有一个未被覆盖， 这个矩形带所代表的与项才是化简后的与或型逻辑式中不可 缺少的项。反之，一个矩形带中的所有小格都被其它矩形带 所覆盖，那么这个矩形带所代表的与项就不是独立的，如果 写入与或型逻辑式中就是多余的。
卡诺图化简法的步骤如下： 1 ．逻辑式填入卡诺图，如果逻辑式不是与或型， 先将逻辑式转换为与或型。 2．照最小的原则，尽可能将矩形带圈大一些。 3 ．选出至少有一个小格是独立的矩形带，写出它 们所对应的最简与项的逻辑和。 4 ．如有遗漏，添上遗漏小格所对应的一个最简与 项，它们的逻辑和就是最简化的与或型逻辑式。 动画17-1 动画17-2
mi
17.6 卡诺图化简法
17.6.1 卡诺图 17.6.1.1 卡诺图的构成
卡诺图是最小项按一定规律排列的方格图，每一个最小项占 有一个小方格。因为最小项的数目与变量数有关，设变量数为n ，则最小项的数目为2n 。二个变量的卡诺图见下图所示。图中 第一行表示 A，第二行表示A；第一列表示 B ，第二列表示B。 这样四个小方格就由四个最小项分别对号占有，行和列的符号 相交就以最小项的与逻辑形式记入该方格中。
mi
卡诺图中的与项对应的小格，只能一个一组；二个一组； 四个一组；八个一组，…，即按2i 的规律组成矩形带。i为缺 少的变量数。以四变量为例，与项只有一个变量，即缺3个变 量，应占23个小格，且组成一个矩形带；与项只有二个变量， 即缺2个变量，应占22个小格，且组成一个矩形带；与项只有 三个变量，即缺1个变量，应占21个小格，且组成一个矩形带。
mi
17.6.3
卡诺图化简
17.6.3.1 如何使与项最简
由前面的讨论可知，卡诺图中的矩形带包括的小格越多， 对应的与项的变量数就越少。所以一个需要化简的逻辑函数， 填入卡诺图后，经过重新组合，圈出的矩形带应越大越好。
CD 00 AB 00 01 11 10 1 1 1
01
11
10
例如左图若把上面两个小方格圈在 一起有 A BC ，下面四个小方格圈在一 起有AC ，于是逻辑式为：
1 0 1 0 00 1 0 01 1 011 1 0 10
掌握卡诺图的构成特点，就可以从印 在表格旁边的 AB 、 CD 的“ 0” 、“ 1” 值直 接写 出最小项的文字符号内容。例如在四变量 卡诺图中，第四行第二列相交的小方格。 表格第四行的“AB”标为“10”，应记为 AB ，第二列的“CD”标为“01”，记为 CD AB C D ， 所以该小格为 。
mi
例：将逻辑式 P AB C 填入卡诺图
CD 00 AB 00 01 11 10 01 11 1 1 1 1 10 CD 00 AB 00 01 11 10 01 1 1 1 1 11 1 1 1 1 10
AB
D
由上述各例题可以看出，与项中变量数越少，在卡诺图 中占的小格越多； 最小项在卡诺图中占1个小格；与最小项相比，少一个变 量占二个小格；少二个变量占四个小格；少三个变量占八个 小格，…。
填入卡诺图。它为一个三变量的逻辑式，结果见下图。
C AB 00 01 0 0 0
1 1
0 0 0
与项是最小项时，按最 小项编号的位置直接填入。
ABC
1 11 1
10
1
0
ABC
mi
2. 与项不是最小项的形式
与项不是最小项的形式，按邻接关系直接填入卡诺图。例如
P( A, B, C, D) A CD ABD
mi
17.6.1.2 邻接与化简的关系
卡诺图为什么可以用来化简？这与最小项的排列满足邻接关 系有关。因为在最小项相加时，相邻两项就可以提出项，从而消 去一个变量。以四变量为例，m12与m13相邻接，则m12+m13为：
ABC D ABC D ABC ( D D) ABC
所以，在卡诺图中只要将有关的最小项重新排列、组合，就 也可能消去一些变量，使逻辑函数得到化简。
mi
例：将逻辑式P= BC + B D 填入卡诺图
先填 BC ， 这是B， 这是 C
CD 0 0 00 1 00 AB 00 1 01 1 11 1 10 11 10 0
；
1
BC 这一与项处于第二、 第三行和第一、第二列的交 点处（二行二列）。
1 1
1
1 1
1
再填 B D ， 这是 B ， 这是 D 。 B D 这一与项处于第一、 第四行和第一、第四列的交点 处（二行二列）。
mi
例:化简 P AB ABC A C D A B D
CD 00 AB 00 01 11
1 10 1 1
01
1 1
11
1
10
CD 00 AB 00 01
01 1 1
11 1
10 1
1
1 1 1 1
11 10 1 1
1 1
1 1