清华大学：《数字逻辑与数字集成电路电路》课程教材电子教案（PPT教学课件，第2版）第二章（2.2）逻辑函数的表格法化简（Q-M法）

2.2.3逻辑函数的表格法化简(Q-M法) 计算机辅助逻辑设计的方法 卡诺图化简法直观方便,过程简单明了, 但只适合于变量数4的函数,化简过程有 规律,可编程,便于计算机实现

2.2.3逻辑函数的表格法化简(Q-M法 ) ——计算机辅助逻辑设计的方法 • 卡诺图化简法直观方便，过程简单明了， 但只适合于变量数4的函数，化简过程有 规律，可编程，便于计算机实现

4变量卡诺图的最小项 A00 011110 “相邻两个最小项中 00mm|mm2有一个变量互补” 如何体现? 01 丛最小项的编号上 11 m12 m13 m15 m14 看有什么规律? 10

4变量卡诺图的最小项 B A D C 00 01 11 10 00 11 01 10 m0 m1 m3 m2 m4 m5 m7 m6 m13 m12 m15 m14 m8 m9 m11 m10 “相邻两个最小项中 有一个变量互补” 如何体现？ 从最小项的编号上 看有什么规律？

QM方法的基本思想 ·“相邻两个最小项中有一个变量互补”在最小项编号 上的规律: ·以4变量卡诺图为例分析观察 m1同皿0,皿3,m5,m相邻,(每个m都有4个相邻) 它们的下标编号为:0001与0000,0011,0101,1001 结论:相邻最小项编号中“1”的个数差等于1; m同皿2皿4mg23个最小项不相邻,它们的下标编号 中1”的个数差等于0 政不相邻管们下称01出置,:吗等个最 这些最小项编号中“1”的个数差可能等于1,也可能 不等于1

Q-M方法的基本思想 • “相邻两个最小项中有一个变量互补”在最小项编号 上的规律： • 以4变量卡诺图为例分析观察： m1同 m0,m3,m5,m9相邻，（每个mi都有4个相邻） 它们的下标编号为：0001与0000,0011,0101,1001 结论：相邻最小项编号中“1”的个数差等于1； m1同 m2,m4,m8,3个最小项不相邻，它们的下标编号 中“1”的个数差等于0； m1还有 m6,m7, m10, m11, m12, m13, m14,m15等8个最 小项不相邻，它们的下标0110,0111,1010,1011……, 这些最小项编号中“1”的个数差可能等于1，也可能 不等于1

QM方法的基本思想(续) 根据最小项编号中“”的个数差就能判断是否相邻! 最小项编号中“1”的个数差: 等于0,最小项肯定不相邻! 等于1,最小项有可能相邻! ·算法步骤:(1)最小项分组:将最小项编号中“1”的 个数相同的最小项分在一组,并按组号大小排序; (2)相邻组比较:合并最小项编号中“1”的个数差 等于1的所有相邻最小项,得到函数的全部质项 (3)求必要质蕴涵项:从全部质蕴涵项中消去冗余项, 得到必要质蕴涵项,即为化简结果

Q-M方法的基本思想（续） • 根据最小项编号中“1”的个数差就能判断是否相邻！ • 最小项编号中“1”的个数差： 等于0，最小项肯定不相邻！ 等于1，最小项有可能相邻！ • 算法步骤：（1）最小项分组：将最小项编号中“1”的 个数相同的最小项分在一组，并按组号大小排序； （2）相邻组比较：合并最小项编号中“1”的个数差 等于1的所有相邻最小项，得到函数的全部质蕴涵项； （3）求必要质蕴涵项：从全部质蕴涵项中消去冗余项， 得到必要质蕴涵项，即为化简结果

步骤1求函数的全部质蕴涵项 函数的“质蕴涵项”就是不能再合并的最小项 先把F中的各m,按下标i中“1”的个数,由少到多 分组排队列表I。组号是m中所包含“1”的个数。 在表工的姐邻组闳进行逐项搜索,寻找相邻项。把可以合并 的记在表工中,并在表I中相应的最小项旁作记号“y” 表工所列均是变量数为n-1的与项(n是F的变量数),它们 同样按与项所含“1”的个数由少到多,分组排列。 重复上述过程,直到不能合并为止

步骤1 求函数的全部质蕴涵项 函数的“质蕴涵项”就是不能再合并的最小项. 先把F中的各mi，按下标i中“1”的个数，由少到多， 分组排队列表I。组号是mi中i所包含“1”的个数。 在表I的相邻组间进行逐项搜索，寻找相邻项。把可以合并 的记在表II中，并在表I中相应的最小项旁作记号“√” 。 表II所列均是变量数为n-1的与项（n是F的变量数），它们 同样按与项所含“1”的个数由少到多，分组排列。 重复上述过程，直到不能合并为止

步骤1求函数的全部质蕴涵项(续) F=∑m(246891621315)表Ⅱ 表I 组号 DCBA 组号最小项DCBA 260-10 2,10 010 00 0 24869 4,6010 0 00 4.12 0|0 1|000 89100 0110 2 8,1010_0 1|001 8,121 00 101010 121100 9,131 0|1 12,13110 3 13 4 313,151 问:1组需要和3,4组比吗?

步骤1 求函数的全部质蕴涵项(续) 例: 8,12 1 _ 0 0 13,15 1 1 _ 1 12,13 1 1 0 _ 9,13 1 _ 0 1 8,10 1 0 _ 0 8,9 1 0 0 _ 4,12 _ 1 0 0 4,6 0 1 _ 0 2,10 _ 0 1 0 2,6 0 _ 1 0 15 1 1 1 1 3 13 1 1 0 1 4 12 1 1 0 0 10 1 0 1 0 9 1 0 0 1 6 0 1 1 0 2 8 1 0 0 0 4 0 1 0 0 2 0 0 1 0 1 组号 最小项 D C B A 表I 3 2 1 组号 m D C B A 表II √ √ √ √ √ √ √ √ √ = (2,4,6,8,9,10,12,13,15) 4 F m 问：1组需要和3，4组比吗？

步骤1求函数的全部质蕴涵项(续) 表II 对表工继续上述过程得表I;这 组号 m DCBA 过程一直要进行到没有可合并的 26010相邻组为止。 2.10 010 46010P 表II 4121 组号 m D CbA 8.9 00 18,9,12,131 0 8.10 0 812100在表II、I中,未打“ 2 9,131 0 的,标以P1~P7,称质蕴涵 12,13110 项。全部质蕴涵项覆盖了F的 13,1511 所有最小项

步骤1 求函数的全部质蕴涵项(续) 8,12 1 _ 0 0 13,15 1 1 _ 1 12,13 1 1 0 _ 9,13 1 _ 0 1 8,10 1 0 _ 0 8,9 1 0 0 _ 4,12 _ 1 0 0 4,6 0 1 _ 0 2,10 _ 0 1 0 2,6 0 _ 1 0 3 2 1 组号 m D C B A 表II √ √ √ √ 8,9,12,13 1 _ 0 _ P1 P2 P3 P4 P5 P6 P7 在表I、II、III中，未打“√” 的，标以P1~P7，称质蕴涵 项。全部质蕴涵项覆盖了F的 所有最小项。 1 组号 m D C B A 表III 对表II继续上述过程,得表III；这 一过程一直要进行到没有可合并的 相邻组为止

步骤1求函数的全部质蕴涵项(续) 用卡诺图画出F的全部质蕴涵项 F=m1(2468.910121315 B 00011110 P1=DBA, P2=CBA 00|0 01/ PBT 0 从卡诺图看哪些是冗余的? P4 11111P610 P1,P4,P5是冗余的。 P7 下面的目的是要用表格法 10P510 找出必要的质蕴涵项。 P2

步骤1 求函数的全部质蕴涵项(续) 00 01 11 10 00 11 01 10 0 0 0 1 1 0 0 1 1 1 1 0 1 1 0 1 B A D C 用卡诺图画出F的全部质蕴涵项 P1 P2 P3 P4 P6 P7 = (2,4,6,8,9,10,12,13,15) 4 F m P1，P4，P5是冗余的。 下面的目的是要用表格法 找出必要的质蕴涵项。 P1＝DBA，P2＝CBA …… 从卡诺图看哪些是冗余的？ P5

步骤1求函数的全部质蕴涵项(续) 由图可见,P1~P覆盖了F的全部最小项;对每个P 项,它们是不能再和其它P项或最小项合并了。 由图还可见,P1P2中有不必要的质蕴涵项: 例如,若P2,P3必要,则P1就不必要。 为此,下一步骤就要从全部质蕴涵项中消去冗余项, 选出必要的质蕴涵项

步骤1 求函数的全部质蕴涵项(续) 由图可见，P1 ~ P7覆盖了F的全部最小项；对每个P 项，它们是不能再和其它P项或最小项合并了。 由图还可见，P1 ~ P7中有不必要的质蕴涵项： 例如，若P2，P3必要，则P1就不必要。 为此，下一步骤就要从全部质蕴涵项中消去冗余项， 选出必要的质蕴涵项

步骤2寻找必要的质蕴涵项 寻找必要质蕴涵项的过程,就是在表格中消去冗余质蕴涵 项的过程。 作全部质蕴涵项P1~P7与全部最小项m对应的二维表格: 例如:P1包含了最小项m2和m6,在对应位置画三角;m2 被包含P和P2所包含 质缢最小项 表TV m 涵项 8 mo 10 12 13 15 P1△ △ P,△ 2 △ △△ 只有P包 3 含4个最小 项,其它 △ △ 只有2个最 6 △|△ 小项 △△ △△

步骤2 寻找必要的质蕴涵项 寻找必要质蕴涵项的过程，就是在表格中消去冗余质蕴涵 项的过程。 作全部质蕴涵项P1~ P7与全部最小项mi对应的二维表格： 例如：P1包含了最小项m2和m6，在对应位置画三角；m2 被包含P1和P2所包含…… 表IV 质蕴 涵项 最小项 P1 P2 P3 P4 P5 P6 P7 m2 m4 m6 m8 m9 m10 m12 m13 m15 只有P7包 含4个最小 项，其它 只有2个最 小项