第03讲逻辑函数的化简K图法

1、数字逻辑设计K图法图法卡诺图 化简逻辑函数l卡诺图是真值表的图形表示卡诺图是真值表的图形表示l卡诺图中卡诺图中1个小方格对应于真值表中的个小方格对应于真值表中的1行。行。卡诺图 化简逻辑函数（续）12xxl名词术语：名词术语：l乘积项（乘积项（product term，简称积项），简称积项）l变量以原变量或反变量的形式出现，多个变量之间执行变量以原变量或反变量的形式出现，多个变量之间执行“与与”操作。操作。l文字文字（literal）l乘积项中的变量或该变量的反变量称作一个文字。乘积项中的变量或该变量的反变量称作一个文字。l最小项（最小项（minterm）l对于对于n 变量的逻辑函数来说，若每

2、一个变量或以原变量形式、或以变量的逻辑函数来说，若每一个变量或以原变量形式、或以反变量形式在一个乘积项中出现反变量形式在一个乘积项中出现 1 次、且仅出现次、且仅出现 1 次，则该乘积项次，则该乘积项是最小项。是最小项。l最小项对应于卡诺图中的一个小方格，它可以表示为最小项对应于卡诺图中的一个小方格，它可以表示为 n 个变量之积，个变量之积，也可以记作也可以记作 m i 。l例如最小项例如最小项 的另一个等价表示形式是的另一个等价表示形式是 m1。l最大项（最大项（maxterm）l对于对于n 变量的逻辑函数来说，若某个变量的逻辑函数来说，若某个“或或”项中包含的文字个数为项中包含的文字个数为

3、 n，则称该，则称该“或或”项为最大项。项为最大项。 2 个 0 维块合并为 1 个 1 维块x3x2 11X 2 个 0 维块合并为 1 个 1 维块x2 x1 X10 卡诺图化简逻辑函数（续）卡诺图化简逻辑函数（续）l举例：举例：l最小项的性质：最小项的性质：l全体最小项之和（全体最小项之和（“或或”运算）为运算）为1。l任意任意2个最小项互不相交，故任意个最小项互不相交，故任意2个最小项之积（个最小项之积（“与与”运算）运算）为为0。l若若2个最小项之间只有个最小项之间只有1个文字不同，即在一个最小项中该文字为个文字不同，即在一个最小项中该文字为原变量，而在另一个最小项中该文字为反变量，

4、则称这原变量，而在另一个最小项中该文字为反变量，则称这2个最小项个最小项“逻辑相邻逻辑相邻”。根据公式（。根据公式（1-11a），逻辑相邻的），逻辑相邻的2个最小项可以个最小项可以合并为合并为1个乘积项，并且合并所得乘积项中的文字个数减少个乘积项，并且合并所得乘积项中的文字个数减少1个。个。l卡诺图是把逻辑相邻的最小项尽量安排成几何位置相邻，通过观卡诺图是把逻辑相邻的最小项尽量安排成几何位置相邻，通过观察即可判定哪些最小项可以合并。察即可判定哪些最小项可以合并。 x2x1 x4x3 2 个相邻的 0 维块合并为 1 个 1 维块 001X 2 个相邻的 1 维块合并为 1 个 2 维块 1XX

5、1 “X”表示该变量因 块的合并而被消去 卡诺图化简逻辑函数（续）卡诺图化简逻辑函数（续）l举例：举例： x4x3 x2x1 14xx 1XX0 ( a ) x4x3 13xx X0X0 x2x1 ( b ) 123xxx X010 卡诺图化简逻辑函数（续）卡诺图化简逻辑函数（续）l逻辑相邻与几何相邻：逻辑相邻与几何相邻：l2个逻辑相邻的乘积项在卡诺图中表现为几何位置的相邻，使我们个逻辑相邻的乘积项在卡诺图中表现为几何位置的相邻，使我们通过观察图形即可实现块的合并，达到化简逻辑函数的目的。通过观察图形即可实现块的合并，达到化简逻辑函数的目的。l可以把卡诺图想象为一张图纸，将其卷成一个圆筒，则原

6、来两边可以把卡诺图想象为一张图纸，将其卷成一个圆筒，则原来两边不相邻的部分就变成相邻的部分了。不相邻的部分就变成相邻的部分了。 卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续）l5变量卡诺图：变量卡诺图：变量个数 5时，很难画出对应的卡诺图！卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续）l蕴含项（蕴含项（implicant）l若某乘积项能指明输入变量的取值组合可使给定逻辑函若某乘积项能指明输入变量的取值组合可使给定逻辑函数数 f 取值为取值为1，则该乘积项是函数，则该乘积项是函数 f 的蕴含项。的蕴含项。l蕴含项的包含关系（蕴含项的包含关系（contain）l设蕴含项设蕴含项 A 由相邻

7、最小项集合由相邻最小项集合 Sa 合并而成，蕴含项合并而成，蕴含项 B 由相邻最小项集合由相邻最小项集合 Sb 合并而成。若，即合并而成。若，即 Sa 中的每一中的每一个最小项都存在于个最小项都存在于Sb中，则称蕴含项中，则称蕴含项B包含蕴含项包含蕴含项A，记作记作 。l质蕴含项（质蕴含项（prime implicant）l若某蕴含项不被其他任何一个蕴含项所包含，则该蕴含若某蕴含项不被其他任何一个蕴含项所包含，则该蕴含项是质蕴含项。在卡诺图中，若某个由相邻最小项构成项是质蕴含项。在卡诺图中，若某个由相邻最小项构成的块已经是维数最大的块，不被其它任何一个块所包含，的块已经是维数最大的块，不被其它

8、任何一个块所包含，则该块对应的乘积项是质蕴含项。则该块对应的乘积项是质蕴含项。BA 卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续）l特征最小项和必要质蕴含项（特征最小项和必要质蕴含项（essential prime implicant）l若某最小项仅被唯一的一个质蕴含项所包含，则该最小项称若某最小项仅被唯一的一个质蕴含项所包含，则该最小项称为特征最小项，包含特征最小项的质蕴含项称为必要质蕴含为特征最小项，包含特征最小项的质蕴含项称为必要质蕴含项。项。 1 ： 特征最小项 ：必要质蕴含项 ：质蕴含项 ：非质蕴含项 x4 x3 x2 x1 卡诺图 化简逻辑函数（续）l覆盖（覆盖（cover）l

9、若一个蕴含项的集合能说明给定逻辑函数若一个蕴含项的集合能说明给定逻辑函数 f 为为 1 的所有情况，的所有情况，则称此蕴含项集合是函数则称此蕴含项集合是函数 f 的覆盖。覆盖和函数的的覆盖。覆盖和函数的“积之和积之和”表达式相对应。表达式相对应。l最小覆盖（最小覆盖（minimal cover）l函数的最小覆盖和成本最低的函数的最小覆盖和成本最低的“积之和积之和”表达式相对应，其要表达式相对应，其要求为：求为：l最小覆盖中包含的蕴含项个数最少。l每一个蕴含项的文字个数尽量少，即蕴含项的维数尽量大。l必要质蕴含项必定是最小覆盖的元素。l无冗余覆盖（无冗余覆盖（non-redundant cover）l覆盖中每一个蕴含项必须是质蕴含项。覆盖中每一个蕴含项必须是质蕴含项。l覆盖中不含冗余项。覆盖中不含冗余项。l当变量个数很多时，若求解函数的最小覆盖有困难，可退而求当变量个数很多时，若求解函数的最小覆盖有困难，可退而求其次，转而求无冗余覆盖。其次，转而求无冗余覆盖。 x4x3 x2x1 : 冗余蕴含项 : 必要质蕴含项 卡诺图 化简逻辑函数（续）l冗余项（冗余项（redundant term）l设设 A 是