列表化简法
列表化简法是 Quine-Mccluskey提出的一种系统化简法，故也称作 Q-M法，也称作表格法。这种方法具有严格的算法，虽然其工作量大、方法繁琐，但便于计算机化简多变量逻辑函数。
,数字逻辑电路,
吉林大学计算机科学与技术学院列表化简法
Q-M法化简逻辑函数的步骤如下：
第一步，将函数表示成最小项表达式。
第二步，找出函数的全部质蕴涵项。
1、将 n变量函数中的相邻最小项合并，消去相异的一个变量，得到 (n-1)个变量的与项（蕴涵项）。 这时如果存在不能合并的最小项，它便是所寻找的部分质蕴涵项。
2、再将相邻的（ n-1）个变量的与项合并，消去相异的一个变量，得到（ n-2）个变量的与项（蕴涵项）,这里如果存在不能合并的（ n-1）个变量的与项，则它们也是所寻找的质蕴涵项。
如此进行下去，直到不能再合并为止。得全部的质蕴涵项。
,数字逻辑电路,
吉林大学计算机科学与技术学院列表化简法
第三步，找出函数的必要质蕴涵项。
先画出质蕴涵表，然后在表上找出仅属于一个质蕴涵项的最小项，则包含该最小项的质蕴涵项就是必要质蕴涵项。
第四步，找出函数的最小覆盖。
当第三步找出的必要质蕴涵项不能包含函数的全部最小项时，可以通过行、列消去法，找出最小覆盖的其他必要质蕴涵项。最小覆盖指包含函数的全部最小项的最小质蕴涵项集合。
,数字逻辑电路,
吉林大学计算机科学与技术学院列表化简法用 Q-M法化简函数,
,数字逻辑电路,
15,10,9,7,6,5,4,2,0mF 4
吉林大学计算机科学与技术学院
1
1
1
1
1
1
1
1
1
AB
CD
00
01
11
10
00 01 11 10
BADAB C DDCBDCBAF
列表化简法
（ 1）找出全部质蕴涵项
①做最小项分组表并找出不能合并者,
将最小项 mi按变量取值表示成二进制数；其次，再根据这些二进制数中所包含 1的个数从少到多的次序进行分组排队；最后，把含有 1的个数相同的最小项划分成一组，
组内按下标 i的取值从小到大排列，如此制成最小项分组。
从含有 1个数最少的那组开始，在相邻组内比较最小项，将只有一个变量值不同的两个最小项合并，消去一个变量，并在已合并的最小项的右边 Pi栏内做记号,√”，
表示该项已被合并。在不能合并的最小项的右边 Pi栏内填入 P1，则 就是所寻找的质蕴涵项。注意合并最小项只能处于相邻的两组内，而不能处于同组或隔组内。
,数字逻辑电路,
吉林大学计算机科学与技术学院
DCBAP1?
DCBAP1?
DCBAP1?
列表化简法
,数字逻辑电路,
吉林大学计算机科学与技术学院
√1 1 1 1154
√ √ √0 1 1 173
√1 0 1 010
P11 0 0 19
√ √ √0 1 1 06
√ √0 1 0 15
2
√ √ √0 1 0 04
√ √ √0 0 1 021
√ √0 0 0 000
Pi变量
A B C D
最小项编号组号
（ 1的个数）
最小项分组表列表化简法
② 做（ n-1）个变量与项分组表并找出不能合并者,
在最小项合并过程中，用符号,—,表示被消去的变量，这样便得到若干个带有,—,的与项，
或称作合并项。按照对最小项的分组方法，对带有,—,的与项进行分组。对相邻组中的,—,处于相同位置的那些与项进行合并，已合并的与项做记号,√”，并记入 Pi栏；在不能合并的与项的
Pi栏内记入 P2和 P3，则也是质蕴涵项。
,数字逻辑电路,
吉林大学计算机科学与技术学院
DCB10,2mP 42
B C D15,7m3P 4
列表化简法组号
（ 1）
最小项编号变量
A B C D Pi
0 0 2 0 0 — 0 √0 4 0 — 0 0 √
1
2 6 0 — 1 0 √
2 10 — 0 1 0 P2
4 5 0 1 0 — √
4 6 0 1 — 0 √ √
2 5 7 0 1 — 1 √6 7 0 1 1 — √
3 7 15 — 1 1 1 P3
,数字逻辑电路,
吉林大学计算机科学与技术学院
√1 1 1 1154
√ √ √0 1 1 173
√1 0 1 010
P11 0 0 19
√ √ √0 1 1 06
√ √0 1 0 15
2
√ √ √0 1 0 04
√ √ √0 0 1 021
√ √0 0 0 000
Pi变量A B C D最小项 编号组号
（ 1的个数）
最小项分组表
（ n-1）个变量与项分组表列表化简法
③ 做（ n-2）个变量与项分组表并找出不能合并者：
在（ n-1）个变量与项合并过程中，也用符号
,—,表示被消去的变量，这样便得到若干个带有两个,—,的与项。按照上述的分组方法，得到（ n-2）
个变量与项分组表。
由表可以看出，仅有的两（ n-2）个变量与项不能再合并，在 Pi栏内分别记入 P4和 P5,P4和 P5就是最后所寻找的质蕴涵项。
,数字逻辑电路,
吉林大学计算机科学与技术学院列表化简法组号
（ 1的个数）
最小项编号变量
A B C D
Pi
0 0 2 4 6 0 — — 0 P4
1 4 5 6 7 0 1 — — P5
,数字逻辑电路,
吉林大学计算机科学与技术学院组号
（ 1）
最小项编号变量
A B C D Pi
0 0 2 0 0 — 0 √0 4 0 — 0 0 √
1
2 6 0 — 1 0 √
2 10 — 0 1 0 P2
4 5 0 1 0 — √
4 6 0 1 — 0 √ √
2 5 7 0 1 — 1 √6 7 0 1 1 — √
3 7 15 — 1 1 1 P3
（ n-2）个变量与项分组表
（ n-1）个变量与项分组表列表化简法
④ 列出全部质蕴涵项由上述分析可得全部质蕴涵 项：
,数字逻辑电路,
吉林大学计算机科学与技术学院
DCBA9mP 41
DCB10,2mP 42
B C D15,7mP 43
DA6,4,2,0mP 44
BA7,6,5,4mP 45
列表化简法
（ 2）找出必要质蕴涵项将函数的最小项和上述的质蕴涵项做序列表，
并在质蕴涵项包含的最小项下面填入符号,×,,
即做所谓质蕴涵表。
找出那些仅属于一个质蕴涵项的最小项，如
m0仅属于 P4； m5仅属于 P5； m9仅属于 P1；
m10仅属于 P2； m15仅属于 P3；并在相应的 × 处加圆圈。
质蕴涵项 P1～ P5均包含一个不属于其他质蕴涵项的最小项，即它们均包含一个，所以它们均为必要质蕴涵项，并在其左边加,﹡,号。
,数字逻辑电路,
吉林大学计算机科学与技术学院列表化简法
,数字逻辑电路,
吉林大学计算机科学与技术学院
×
×
× × ×
× × ×
﹡ P1
﹡ P2
﹡ P3
﹡ P4
﹡ P5
√ √ √ √ √ √ √ √ √
m0 m2 m4 m5 m6 m7 m9 m10 m15
mi
Pi
质蕴涵表
DCBA9mP 41
DCB10,2mP 42
B C D15,7mP 43
DA6,4,2,0mP 44
BA7,6,5,4mP 45
列表化简法
（ 3）找出函数的最小覆盖在上述的必要质蕴涵项 P1～ P5中，找出它们所包含的全部最小项，并在相应的最小项上面做记号,√” 。从表中可以看出，必要蕴涵项 P1～
P5包含函数的所有的最小项，也就是说,P1～
P5构成了函数的最小覆盖，因此，函数的最简与或式为：
,数字逻辑电路,
吉林大学计算机科学与技术学院
BADAB C DDCBDCBA
PPPPPF 54321
列表化简法
15,13,12,10,9,8,6,4,2mF 4
,数字逻辑电路,
吉林大学计算机科学与技术学院
1
1
1
1
1
1
1
1
1
AB
CD
00
01
11
10
00 01 11 10
1
1
1
1
1
1
1
1
1
AB
CD
00
01
11
10
00 01 11 10
CAA B CDBADCBF
化简函数：
列表化简法
,数字逻辑电路,
吉林大学计算机科学与技术学院用 Q-M法化简函数：
15,13,12,10,9,8,6,4,2mF 4
6,2mP 41
10,2mP 42
6,4mP 43
12,4mP 44
10,8mP 45
15,13mP 46
13,12,9,8mP 47
mi
pi
√ √ √ √ √
m2 m4 m6 m8 m9 m10 m12 m13 m15
p1 × ×
p2 × ×
p3 × ×
p4 × ×
p5 × ×
*p6 × ×
*p7 × × × ×
函数 F的质蕴涵表列表化简法
,数字逻辑电路,
吉林大学计算机科学与技术学院行列消去法的规则如下：
1、行消去法规则是：保留优势行，消去劣势行。
2、列消去法规则是：保留劣势列，消去优势列。
CAA B CDBADCB
13,12,9,8m15,13m6,4m10,2m
PPPPF
4444
7632
× ×
× ×
× ×
×
×
P1
﹡ P2
﹡ P3
P4
P5
m2 m4 m6 m10mi
Pi
简化质蕴涵表 优势行和劣势行 —— 若有质蕴涵项 i和 j两行，其中 j行中的,×,
完全包含在 i行之中，则称 i行为优势行,j行为劣势行。
优势列和劣势列 —— 若有最小项 mk和 ml两列，其中 ml中的
,×,完全包含中 mk列之中，则称 mk为优势列,ml为劣势列。
列表化简法是 Quine-Mccluskey提出的一种系统化简法，故也称作 Q-M法，也称作表格法。这种方法具有严格的算法，虽然其工作量大、方法繁琐，但便于计算机化简多变量逻辑函数。
,数字逻辑电路,
吉林大学计算机科学与技术学院列表化简法
Q-M法化简逻辑函数的步骤如下：
第一步，将函数表示成最小项表达式。
第二步，找出函数的全部质蕴涵项。
1、将 n变量函数中的相邻最小项合并，消去相异的一个变量，得到 (n-1)个变量的与项（蕴涵项）。 这时如果存在不能合并的最小项，它便是所寻找的部分质蕴涵项。
2、再将相邻的（ n-1）个变量的与项合并，消去相异的一个变量，得到（ n-2）个变量的与项（蕴涵项）,这里如果存在不能合并的（ n-1）个变量的与项，则它们也是所寻找的质蕴涵项。
如此进行下去，直到不能再合并为止。得全部的质蕴涵项。
,数字逻辑电路,
吉林大学计算机科学与技术学院列表化简法
第三步，找出函数的必要质蕴涵项。
先画出质蕴涵表，然后在表上找出仅属于一个质蕴涵项的最小项，则包含该最小项的质蕴涵项就是必要质蕴涵项。
第四步，找出函数的最小覆盖。
当第三步找出的必要质蕴涵项不能包含函数的全部最小项时，可以通过行、列消去法，找出最小覆盖的其他必要质蕴涵项。最小覆盖指包含函数的全部最小项的最小质蕴涵项集合。
,数字逻辑电路,
吉林大学计算机科学与技术学院列表化简法用 Q-M法化简函数,
,数字逻辑电路,
15,10,9,7,6,5,4,2,0mF 4
吉林大学计算机科学与技术学院
1
1
1
1
1
1
1
1
1
AB
CD
00
01
11
10
00 01 11 10
BADAB C DDCBDCBAF
列表化简法
（ 1）找出全部质蕴涵项
①做最小项分组表并找出不能合并者,
将最小项 mi按变量取值表示成二进制数；其次，再根据这些二进制数中所包含 1的个数从少到多的次序进行分组排队；最后，把含有 1的个数相同的最小项划分成一组，
组内按下标 i的取值从小到大排列，如此制成最小项分组。
从含有 1个数最少的那组开始，在相邻组内比较最小项，将只有一个变量值不同的两个最小项合并，消去一个变量，并在已合并的最小项的右边 Pi栏内做记号,√”，
表示该项已被合并。在不能合并的最小项的右边 Pi栏内填入 P1，则 就是所寻找的质蕴涵项。注意合并最小项只能处于相邻的两组内，而不能处于同组或隔组内。
,数字逻辑电路,
吉林大学计算机科学与技术学院
DCBAP1?
DCBAP1?
DCBAP1?
列表化简法
,数字逻辑电路,
吉林大学计算机科学与技术学院
√1 1 1 1154
√ √ √0 1 1 173
√1 0 1 010
P11 0 0 19
√ √ √0 1 1 06
√ √0 1 0 15
2
√ √ √0 1 0 04
√ √ √0 0 1 021
√ √0 0 0 000
Pi变量
A B C D
最小项编号组号
（ 1的个数）
最小项分组表列表化简法
② 做（ n-1）个变量与项分组表并找出不能合并者,
在最小项合并过程中，用符号,—,表示被消去的变量，这样便得到若干个带有,—,的与项，
或称作合并项。按照对最小项的分组方法，对带有,—,的与项进行分组。对相邻组中的,—,处于相同位置的那些与项进行合并，已合并的与项做记号,√”，并记入 Pi栏；在不能合并的与项的
Pi栏内记入 P2和 P3，则也是质蕴涵项。
,数字逻辑电路,
吉林大学计算机科学与技术学院
DCB10,2mP 42
B C D15,7m3P 4
列表化简法组号
（ 1）
最小项编号变量
A B C D Pi
0 0 2 0 0 — 0 √0 4 0 — 0 0 √
1
2 6 0 — 1 0 √
2 10 — 0 1 0 P2
4 5 0 1 0 — √
4 6 0 1 — 0 √ √
2 5 7 0 1 — 1 √6 7 0 1 1 — √
3 7 15 — 1 1 1 P3
,数字逻辑电路,
吉林大学计算机科学与技术学院
√1 1 1 1154
√ √ √0 1 1 173
√1 0 1 010
P11 0 0 19
√ √ √0 1 1 06
√ √0 1 0 15
2
√ √ √0 1 0 04
√ √ √0 0 1 021
√ √0 0 0 000
Pi变量A B C D最小项 编号组号
（ 1的个数）
最小项分组表
（ n-1）个变量与项分组表列表化简法
③ 做（ n-2）个变量与项分组表并找出不能合并者：
在（ n-1）个变量与项合并过程中，也用符号
,—,表示被消去的变量，这样便得到若干个带有两个,—,的与项。按照上述的分组方法，得到（ n-2）
个变量与项分组表。
由表可以看出，仅有的两（ n-2）个变量与项不能再合并，在 Pi栏内分别记入 P4和 P5,P4和 P5就是最后所寻找的质蕴涵项。
,数字逻辑电路,
吉林大学计算机科学与技术学院列表化简法组号
（ 1的个数）
最小项编号变量
A B C D
Pi
0 0 2 4 6 0 — — 0 P4
1 4 5 6 7 0 1 — — P5
,数字逻辑电路,
吉林大学计算机科学与技术学院组号
（ 1）
最小项编号变量
A B C D Pi
0 0 2 0 0 — 0 √0 4 0 — 0 0 √
1
2 6 0 — 1 0 √
2 10 — 0 1 0 P2
4 5 0 1 0 — √
4 6 0 1 — 0 √ √
2 5 7 0 1 — 1 √6 7 0 1 1 — √
3 7 15 — 1 1 1 P3
（ n-2）个变量与项分组表
（ n-1）个变量与项分组表列表化简法
④ 列出全部质蕴涵项由上述分析可得全部质蕴涵 项：
,数字逻辑电路,
吉林大学计算机科学与技术学院
DCBA9mP 41
DCB10,2mP 42
B C D15,7mP 43
DA6,4,2,0mP 44
BA7,6,5,4mP 45
列表化简法
（ 2）找出必要质蕴涵项将函数的最小项和上述的质蕴涵项做序列表，
并在质蕴涵项包含的最小项下面填入符号,×,,
即做所谓质蕴涵表。
找出那些仅属于一个质蕴涵项的最小项，如
m0仅属于 P4； m5仅属于 P5； m9仅属于 P1；
m10仅属于 P2； m15仅属于 P3；并在相应的 × 处加圆圈。
质蕴涵项 P1～ P5均包含一个不属于其他质蕴涵项的最小项，即它们均包含一个，所以它们均为必要质蕴涵项，并在其左边加,﹡,号。
,数字逻辑电路,
吉林大学计算机科学与技术学院列表化简法
,数字逻辑电路,
吉林大学计算机科学与技术学院
×
×
× × ×
× × ×
﹡ P1
﹡ P2
﹡ P3
﹡ P4
﹡ P5
√ √ √ √ √ √ √ √ √
m0 m2 m4 m5 m6 m7 m9 m10 m15
mi
Pi
质蕴涵表
DCBA9mP 41
DCB10,2mP 42
B C D15,7mP 43
DA6,4,2,0mP 44
BA7,6,5,4mP 45
列表化简法
（ 3）找出函数的最小覆盖在上述的必要质蕴涵项 P1～ P5中，找出它们所包含的全部最小项，并在相应的最小项上面做记号,√” 。从表中可以看出，必要蕴涵项 P1～
P5包含函数的所有的最小项，也就是说,P1～
P5构成了函数的最小覆盖，因此，函数的最简与或式为：
,数字逻辑电路,
吉林大学计算机科学与技术学院
BADAB C DDCBDCBA
PPPPPF 54321
列表化简法
15,13,12,10,9,8,6,4,2mF 4
,数字逻辑电路,
吉林大学计算机科学与技术学院
1
1
1
1
1
1
1
1
1
AB
CD
00
01
11
10
00 01 11 10
1
1
1
1
1
1
1
1
1
AB
CD
00
01
11
10
00 01 11 10
CAA B CDBADCBF
化简函数：
列表化简法
,数字逻辑电路,
吉林大学计算机科学与技术学院用 Q-M法化简函数：
15,13,12,10,9,8,6,4,2mF 4
6,2mP 41
10,2mP 42
6,4mP 43
12,4mP 44
10,8mP 45
15,13mP 46
13,12,9,8mP 47
mi
pi
√ √ √ √ √
m2 m4 m6 m8 m9 m10 m12 m13 m15
p1 × ×
p2 × ×
p3 × ×
p4 × ×
p5 × ×
*p6 × ×
*p7 × × × ×
函数 F的质蕴涵表列表化简法
,数字逻辑电路,
吉林大学计算机科学与技术学院行列消去法的规则如下：
1、行消去法规则是：保留优势行，消去劣势行。
2、列消去法规则是：保留劣势列，消去优势列。
CAA B CDBADCB
13,12,9,8m15,13m6,4m10,2m
PPPPF
4444
7632
× ×
× ×
× ×
×
×
P1
﹡ P2
﹡ P3
P4
P5
m2 m4 m6 m10mi
Pi
简化质蕴涵表 优势行和劣势行 —— 若有质蕴涵项 i和 j两行，其中 j行中的,×,
完全包含在 i行之中，则称 i行为优势行,j行为劣势行。
优势列和劣势列 —— 若有最小项 mk和 ml两列，其中 ml中的
,×,完全包含中 mk列之中，则称 mk为优势列,ml为劣势列。
