2.2.3逻辑函数的表格法化简 (Q-M法 )
—— 计算机辅助逻辑设计的方法
卡诺图化简法直观方便，过程简单明了，
但只适合于变量数 <=4的函数。
Q-M(Quine-McCluskey) 法和卡诺图法的化简思路是一致的,两相邻最小项可以合并,消去一个变量,[1952,1956]
Q-M法是用分组表格法，把两相邻与项合成为一新的与项，从而消去一变量。
它适合于变量数 >4的函数，化简过程有规律，可编程，便于计算机实现 。
4变量卡诺图的最小项
B
AD
C
00 1101 10
00
11
01
10
m1m0 m3 m2
m5m4 m7 m6
m13m12 m15 m14
m9m8 m11 m10
“相邻两个最小项中有一个变量互补,
如何体现？
从最小项的编号上看有什么规律？
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。
Q-M方法的基本思想（续）
根据最小项编号中,1”的个数差 就能判断是否相邻！
最小项编号中,1” 的个数差：
等于 0，最小项肯定不相邻！
等于 1，最小项有可能相邻！
算法步骤：（ 1）最小项分组：将 最小项编号中,1”的个数相同的最小项分在一组，并按组号大小排序；
（ 2）相邻组比较：合并 最小项编号中,1” 的个数差等于 1的所有相邻最小项，得到函数的 全部 质蕴涵项 ；
（ 3）求必要质蕴涵项：从全部质蕴涵项中消去冗余项，
得到 必要质蕴涵项,即为化简结果。
步骤 1 求函数的全部质蕴涵项函数的,质蕴涵项,就是不能再合并的最小项,
先把 F中的各 mi，按下标 i中,1”的个数，由少到多，
分组排队列表 I。组号是 mi中 i所包含,1”的个数。
在表 I的 相邻组间 进行逐项搜索，寻找相邻项。把可以合并的记在 表 II中，并在表 I中相应的最小项旁作记号,√” 。
表 II所列均是变量数为 n-1的与项（ n是 F的变量数），它们同样按与项所含,1”的个数由少到多，分组排列。
重复上述过程，直到不能合并为止。
步骤 1 求函数的全部质蕴涵项 (续 )
例,
00_18,12
1_1113,15
_01112,13
10_19,13
0_018,10
_0018,9
001_4,12
0_104,6
010_2,10
01_02,6
111115
1011133
4
001112
010110
10019
01106
2
00018
00104
01002
1
ABCD最小项组号表 I
3
2
1
ABCDm组号表 II
√
√
√
√
√
√
√
√
√
)15,13,12,10,9,8,6,4,2(4mF
问,1组需要和 3,4组比吗？
步骤 1 求函数的全部质蕴涵项 (续 )
00_18,12
1_1113,15
_01112,13
10_19,13
0_018,10
_0018,9
001_4,12
0_104,6
010_2,10
01_02,6
3
2
1
ABCDm组号表 II
√
√
√
√
1 _ 0 _8,9,12,13
P1
P2
P3
P4
P5
P6
P7
在表 I,II,III中，未打,√”
的，标以 P1~P7，称质蕴涵项。全部质蕴涵项覆盖了 F的所有最小项。
1
D C B Am组号表 III
对表 II继续上述过程,得表 III；这一过程一直要进行到没有可合并的相邻组为止。
步骤 1 求函数的全部质蕴涵项 (续 )
00 1101 10
00
11
01
10
00 0 1
01 0 1
11 1 0
11 0 1
B
AD
C
用卡诺图画出 F的全部质蕴涵项
P1
P2
P3
P4
P6
P7
)15,13,12,10,9,8,6,4,2(4mF
P1,P4,P5是冗余的。
下面的目的是要用表格法找出必要的质蕴涵项。
P1＝ DBA,P2＝ CBA
……
从卡诺图看哪些是冗余的？
P5
步骤 1 求函数的全部质蕴涵项 (续 )
由图可见,P1~ P7覆盖了 F的全部最小项；对每个 P
项,它们是不能再和其它 P项或最小项合并了 。
由图还可见,P1~ P7中有不必要的质蕴涵项：
例如,若 P2,P3必要,则 P1就不必要 。
为此,下一步骤就要从全部质蕴涵项中消去冗余项,
选出必要的质蕴涵项 。
步骤 2 寻找必要的质蕴涵项寻找必要质蕴涵项的过程，就是在表格中消去冗余质蕴涵项的过程。
作全部 质蕴涵项 P1~ P7与全部最小项 mi对应的二维表格,
例如,P1包含了 最小项 m2和 m6，在对应位置画三角； m2
被包含 P1和 P2所包含 ……
表 IV质蕴涵项最小项
P1
P2
P3
P4
P5
P6
P7
m2 m4 m8m6 m9 m12m10 m13 m15
只有 P7包含 4个最小项，其它只有 2个最小项步骤 2 寻找必要的质蕴涵项（续）
判断哪些行是必要的？ 先行消去,再列消去：
方法：先找只有一个 △ 的列,它们所对应的行一定要保留,这个 P项是 必要质蕴涵项 。
对表 IV,只有 m9和 m15对应的列只有一个 △ （ 在卡诺图中表示这两个最小项只被画一次 ）,这些列肯定是必要的； m9它所对应的 P7有 4个 △,分别对应 m8,m9,m12,m13.
因此 P7 为 必 要 的 。 由于 P7 必要,P7 所 蕴 涵 的
m8,m9,m12,m13可从表中暂时删去,以简化表 IV。
同理,由于 m15是必要的,P6也为必要,P6所蕴涵的 m13,
m15可以从表中暂时删去,如下图 。
,行消去,找到的是要保留的必要质蕴涵项,暂时从表格中消去的目的是为了简化表格 。
步骤 2 寻找必要的质蕴涵项（续）
表 V
P1
P2
P3
P4
P5
P6
P7
m2 m4 m8m6 m9 m12m10 m13 m15质蕴涵项最小项步骤 2 寻找必要的质蕴涵项（续）
,行消去,暂时消去了要保留的 必要质蕴涵项,使表格简化 。
,列消去,的目的是 去掉不必要的 质蕴涵项
方法：先找只有一个 △ 的行,如果在它所对应的列上也有 △,则表示这个 P项被其它行所包含,这个 P项就可以消去 。
在 Pi行记有 △ 的各列,若在 Pj行对应列中也均记有 △,则 Pi行就是不必要的质蕴涵项 。
步骤 2 寻找必要的质蕴涵项（续）
P1
P2
P3
P4
P5
m2 m4 m6 m10质蕴涵项最小项质蕴涵项最小项
m2 m4 m6
P1
P2
P3
m10
表 V 表 VI
表 V中,P4行只有一个 △,它所对应的 m4列包含在 P3行中,故 P4为非必要的质蕴涵项 。 同理,P5也为非必要的质蕴涵项 。 表 V简化为表 VI。
步骤 2 寻找必要的质蕴涵项（续）
最后，再对简化后的表 VI进行,行消去,。
m2 m4 m6
P1
P2
P3
m10质蕴涵项最小项 P
2,P3为必要质蕴涵项 （因为 m4 和 m10列只有一个 △，
所以 P2,P3 必须保留 ）
因 P2,P3蕴涵了表 VI中所列全部 m项（ m2,m4,m6,m10)，
故 P1为非必要 质蕴涵 项化简结果为
DBA C DDCACBA
PPPPF
7632
必要质蕴涵项的卡诺图表示
00 1101 10
00
11
01
10
00 0 1
01 0 1
11 1 0
11 0 1
B
AD
C
P2
P3
P6
P7
DBA C DDCACBA
PPPPF
7632
根据最小项编号中,1”的个数差 判断是否相邻 。
第一步求全部质蕴涵项 。 分组后在相邻组间反复比较,两个最小项间只要有一个变量不同,就可以消去一个变量,最后得到 覆盖 F所有最小项的 全部 质蕴涵项 。
第二步求必要质蕴涵项 。 找出只有一个 △ 的 mi列,
它所对应的 P项一定是要保留的； 找出只有一个 △ 的
Pi行,如果在它所对应的 m列上也有 △,则表示这个
P项是可以消去的 。 反复这一过程得到所有的 必要质蕴涵项 。
多输出逻辑函数的表格法化简不要求 (p38-45).
计算机辅助逻辑化简的其他算法还在继续研究 。
逻辑函数的表格化简法 (Q-M法 )小结
2.2.5 特殊形式的逻辑函数化简
基本形式的逻辑函数：
单输出逻辑函数,F＝ f(A,B,C…)
特殊形式的逻辑函数：
1,多输出逻辑函数
2,包含不管项的逻辑函数
只要求掌握卡诺图化简法
(1)多输出逻辑函数的化简多输出逻辑函数：同一组输入变量，有两个以上的输出。
F1＝ f(A,B,C…)
F2＝ f(A,B,C…)
化简时，在“与或”表达式中要尽量寻找公共的“与”项，使公共项为多个函数共享，这时从单个输出看可能不是最简，但总体是最简。
A B CCBACABF
A B CCBACBAF
2
1
0110
0010
BA
C 00 01 11 10
0
1
ACBAF1
0100
1100
BA
C 00 01 11 10
0
1
CBABF2
0110
0010
BA
C 00 01 11 10
0
1
A B CBAF1
0100
1100
BA
C 00 01 11 10
0
1
AB CCBF2
ABC是公共项单独看 F1,F2都是最简，但没有公共项。
(2)有“不管项”的逻辑函数化简包含不管项（ Don’t Care）的逻辑函数：函数 F的取值只和一部分最小项有关，另一部分最小项既可以取,0”，也可以取,1”，这些最小项称“不管项”或“任意项”。
“不管项”的两种情况：
1,这些输入组合不可能出现
2,其输入组合虽能出现，但最小项的值是,1”
还是,0”，人们不关心。
例：设计一位十进制数的数值范围判断器，
当 x>=5,F=1；否则,F=0。
(ABCD表示一位十进制数,A是低位,D是高位 )
10111
10110
10101
00100
00011
00010
00001
00000
FDCBA
φ1111
φ1110
φ1101
φ1100
φ1011
φ1010
11001
11000
FDCBA
0
1
2
3
4
5
6
7
8
9
有“不管项”的逻辑函数化简（续）
F的卡诺图
00 1101 10
00
11
01
10
00 0 0
10 1 1
φφ φ φ
11 φ φ
BC
D
AC
F=D+AC+BC
B
AD
C
把 φ项当作,1”
2.2.6 逻辑函数的实现由最小项和函数式表达的逻辑函数要用逻辑电路来实现。实现时要考虑的问题包括可用集成电路的种类、逻辑函数的形式、集成电路的级数等。
下列三种，”与非－与非”结构最常用。
与非－与非实现
与－或－非实现
或非－或非实现门电路符号
A X A X
B
A X
B
A X
B
A X
B
A X
B
A X
A X1
B
A X&
B
A X&
B
A X
1? BA X+
传统符号 IEEE标准符号 习惯符号门电路符号
B
A X
B
A X
B
A X
B
A X
1?
B
A X
1?
B
A X
1?
B
A X+
B
A X?
B
A X
例 1,异或逻辑
BABAF
A B F
0 0
1 0
0 1
1 1
0
1
1
0
A,B不相同时,F为 1； A,B
相同时,F为 0；因此称异或逻辑或半加逻辑。 表示为,F＝ A B
A
B F
逻辑符号异或逻辑的实现 AB F
BAABF
与－或－非
B
A
A
B
F
BABAF
或非－或非BA
A
B
F
与非－与非
BABAF
B
A
A
B
F
BABAF
与－或
B
A
A
B
F
书上例题书上例题书上例题书上例题书上例题例题逻辑问题的描述：逻辑设计的第一步。
由文字叙述的设计要求，抽象为逻辑表达式的过程。然后才能化简、实现。
真值表电路功能描述例,设计一个楼上、楼下开关的控制逻辑电路来控制楼梯上的路灯，使之在上楼前，用楼下开关打开电灯，上楼后，用楼上开关关灭电灯；
或者在下楼前，用楼上开关打开电灯，下楼后，
用楼下开关关灭电灯。
设楼上开关为 A，楼下开关为 B，灯泡为 Y。并设 A,B闭合时为 1，断开时为 0；灯亮时 Y为 1，
灯灭时 Y为 0。根据逻辑要求列出真值表。
A B Y
0 0
0 1
1 0
1 1
0
1
1
0
1
穷举法
1
2
逻辑表达式或卡诺图最简与或表达式化简 3
2
BABAY
已为最简与或表达式
4
逻辑变换
5
逻辑电路图
A
B
Y
&
&
& &
A
B
Y=1
用与非门实现 ABABABBABAY
BAY
用异或门实现真值表电路功能描述例,用与非门设计一个举重裁判表决电路。设举重比赛有 3个裁判，一个主裁判和两个副裁判。杠铃完全举上的裁决由每一个裁判按一下自己面前的按钮来确定。只有当两个或两个以上裁判判明成功，并且其中有一个为主裁判时，表明成功的灯才亮。
设主裁判为变量 C，副裁判分别为 B和 A；表示成功与否的灯为 Y，根据逻辑要求列出真值表。1
穷举法
1
C B A Y C B A Y
0 0 0
0 0 1
0 1 0
0 1 1
0
0
0
0
1 0 0
1 0 1
1 1 0
1 1 1
0
1
1
1
2
A B CBCACBAmmmY 765
2
逻辑表达式
B A
C 00 01 11 10
0
1
B
C
A
C
Y
&
&
&
3
卡诺图最简与或表达式化简 4
5
逻辑变换
6
逻辑电路图
3
化简 4
1 1 1
Y= BC +AC 5 ACBCY
6
例题例 1：设计一个多数表决逻辑电路，判别 A B
C三人中是否为多数赞同。
解：输入为 0，表示反对；
输入为 1，表示赞同；
当 ABC中有两个和两个以上为,1”时，表示多数赞同,F＝ 1；否则 F＝ 0。
C B A F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
多数表决逻辑电路的真值表
F＝ m3+m5+ m6+m7
例 2,1位二进制全加器的设计与实现
（不考虑进位叫半加,考虑进位叫全加 ）
真值表
11111
10011
10101
01001
10110
01010
01100
00000
CnFnCn-1YnXn
框图
Cn
Fn
Xn Yn Cn-1
∑
3个输入
2个输出输 入 输 出全加器逻辑的卡诺图化简
0101
1010
XnYn
Cn-1 00 01 11 10
0
1
nF
1110
0100
XnYn
Cn-1 00 01 11 10
0
1
nC
111 )( nnnnnnnnnnnn CYXYXCYCXYXC
)(
)()(
1
11
1111
nnn
nnnnnnnnnn
nnnnnnnnnnnnn
YXC
YXYXCYXYXC
CYXCYXCYXCYXF
实现方案一
Fn用异或门实现 Cn用,与非,门实现 Cn用,与或非,门实现
Xn
Yn
Cn-1 Fn
Xn
Yn
Cn-1
Cn Cn
Xn
Yn
Cn-1
Cn与或 —— 与非 Cn与或 —— 与或非实现方案二直接由最小项用与或非门实现，需要 3级门实现方案三写 的表达式F C
1111 nnnnnnnnnnnn CYXCYXCYXCYXF
1111 nnnnnnnnnnnn CYXCYXCYXCYXFF
11 nnnnnnn CYCXYXC
11 nnnnnnnn CYCXYXCC
经变换后只要 2级门。
实现方案三（续）
补充 逻辑函数的表示方法
1,真值表真值表：是由变量的所有可能取值组合及其对应的函数值所构成的表格。
真值表列写方法：每一个变量均有 0,1两种取值,n个变量共有 2i种不同的取值，将这 2i种不同的取值按顺序（一般按二进制递增规律）排列起来，同时在相应位置上填入函数的值，
便可得到逻辑函数的真值表。
A B C Y
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
0
1
0
0
1
1
例如：当 A=B=1、或则 B=C=1时，
函数 Y=1；否则 Y=0。
2,逻辑表达式逻辑表达式：是由逻辑变量和与、或、非 3种运算符连接起来所构成的式子。
函数的标准与或表达式的列写方法：将函数的真值表中那些使函数值为
1的最小项相加，便得到函数的标准与或表达式。
)7,6,3(m
ABCCABBCAY
3,卡诺图卡诺图：是由表示变量的所有可能取值组合的小方格所构成的图形。
逻辑函数卡诺图的填写方法：
在那些使函数值为 1的变量取值组合所对应的小方格内填入 1，其余的方格内填入 0，便得到该函数的卡诺图。
A B
C 00 01 11 10
0 0 0 1 0
1 0 1 1 0
4,逻辑图逻辑图：是由表示逻辑运算的逻辑符号所构成的图形。
Ｙ＝ＡＢ＋ＢＣ
Y
&
≥ 1
&
A
B
B
C
ＡＢ
ＢＣ
５、波形 图波形图：是由输入变量的所有可能取值组合的高、低电平及其对应的输出函数值的高、
低电平所构成的图形。
Ｙ＝ＡＢ＋ＢＣ
Ａ
Ｂ
Ｃ
Ｙ
０
０
０
０
０
０
１
０
０
１
０
０
０
１
１
１
１
０
０
０
１
０
１
０
１
１
０
１
１
１
１
１
０
０
０
０
Ｙ
2.4.2 逻辑函数表示方法之间的转换
1、由真值表到 逻辑图的转换真值表逻辑表达式或卡诺图
A B C Y
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
1
0
0
1
1
1
)7,6,5,2(m
ABCCABCBACBAY
1 1
A B
C 00 01 11 10
0 0 1 0 1
1 0 0 1 1
最简与或表达式化简 2
或
ACBACBAY
2
&
画逻辑图
3 &
&
≥1
ABCA
最简与或表达式
ACBACBAY
&
C
B
B
A
A
C
AB
AC
Y
A
C
B
B
A
A
C
Y
&
&
&
ABC
AB
AC
若用与非门实现，将最简与或表达式变换乘最简与非 -
与非表达式
ACBACBAY
3
2、由 逻辑图 到真值表 的转换逻辑图逻辑表达式
1
1
最简与或表达式化简 2
&
A ≥1
C
B
B
A
A
C
Y≥1
≥1
CBAY1
BAY2
CAY3
1Y
2Y
3Y
))()((
321
CABACBA
YYYY
2
CAABCBA
CBACBACABACBAY
))(())()((
从输入到输出逐级写出
A B C Y
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
1
0
0
1
0
1
1
最简与或表达式
3
真值表
CAABCBAY
3
—— 计算机辅助逻辑设计的方法
卡诺图化简法直观方便，过程简单明了，
但只适合于变量数 <=4的函数。
Q-M(Quine-McCluskey) 法和卡诺图法的化简思路是一致的,两相邻最小项可以合并,消去一个变量,[1952,1956]
Q-M法是用分组表格法，把两相邻与项合成为一新的与项，从而消去一变量。
它适合于变量数 >4的函数，化简过程有规律，可编程，便于计算机实现 。
4变量卡诺图的最小项
B
AD
C
00 1101 10
00
11
01
10
m1m0 m3 m2
m5m4 m7 m6
m13m12 m15 m14
m9m8 m11 m10
“相邻两个最小项中有一个变量互补,
如何体现？
从最小项的编号上看有什么规律？
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。
Q-M方法的基本思想（续）
根据最小项编号中,1”的个数差 就能判断是否相邻！
最小项编号中,1” 的个数差：
等于 0，最小项肯定不相邻！
等于 1，最小项有可能相邻！
算法步骤：（ 1）最小项分组：将 最小项编号中,1”的个数相同的最小项分在一组，并按组号大小排序；
（ 2）相邻组比较：合并 最小项编号中,1” 的个数差等于 1的所有相邻最小项，得到函数的 全部 质蕴涵项 ；
（ 3）求必要质蕴涵项：从全部质蕴涵项中消去冗余项，
得到 必要质蕴涵项,即为化简结果。
步骤 1 求函数的全部质蕴涵项函数的,质蕴涵项,就是不能再合并的最小项,
先把 F中的各 mi，按下标 i中,1”的个数，由少到多，
分组排队列表 I。组号是 mi中 i所包含,1”的个数。
在表 I的 相邻组间 进行逐项搜索，寻找相邻项。把可以合并的记在 表 II中，并在表 I中相应的最小项旁作记号,√” 。
表 II所列均是变量数为 n-1的与项（ n是 F的变量数），它们同样按与项所含,1”的个数由少到多，分组排列。
重复上述过程，直到不能合并为止。
步骤 1 求函数的全部质蕴涵项 (续 )
例,
00_18,12
1_1113,15
_01112,13
10_19,13
0_018,10
_0018,9
001_4,12
0_104,6
010_2,10
01_02,6
111115
1011133
4
001112
010110
10019
01106
2
00018
00104
01002
1
ABCD最小项组号表 I
3
2
1
ABCDm组号表 II
√
√
√
√
√
√
√
√
√
)15,13,12,10,9,8,6,4,2(4mF
问,1组需要和 3,4组比吗？
步骤 1 求函数的全部质蕴涵项 (续 )
00_18,12
1_1113,15
_01112,13
10_19,13
0_018,10
_0018,9
001_4,12
0_104,6
010_2,10
01_02,6
3
2
1
ABCDm组号表 II
√
√
√
√
1 _ 0 _8,9,12,13
P1
P2
P3
P4
P5
P6
P7
在表 I,II,III中，未打,√”
的，标以 P1~P7，称质蕴涵项。全部质蕴涵项覆盖了 F的所有最小项。
1
D C B Am组号表 III
对表 II继续上述过程,得表 III；这一过程一直要进行到没有可合并的相邻组为止。
步骤 1 求函数的全部质蕴涵项 (续 )
00 1101 10
00
11
01
10
00 0 1
01 0 1
11 1 0
11 0 1
B
AD
C
用卡诺图画出 F的全部质蕴涵项
P1
P2
P3
P4
P6
P7
)15,13,12,10,9,8,6,4,2(4mF
P1,P4,P5是冗余的。
下面的目的是要用表格法找出必要的质蕴涵项。
P1＝ DBA,P2＝ CBA
……
从卡诺图看哪些是冗余的？
P5
步骤 1 求函数的全部质蕴涵项 (续 )
由图可见,P1~ P7覆盖了 F的全部最小项；对每个 P
项,它们是不能再和其它 P项或最小项合并了 。
由图还可见,P1~ P7中有不必要的质蕴涵项：
例如,若 P2,P3必要,则 P1就不必要 。
为此,下一步骤就要从全部质蕴涵项中消去冗余项,
选出必要的质蕴涵项 。
步骤 2 寻找必要的质蕴涵项寻找必要质蕴涵项的过程，就是在表格中消去冗余质蕴涵项的过程。
作全部 质蕴涵项 P1~ P7与全部最小项 mi对应的二维表格,
例如,P1包含了 最小项 m2和 m6，在对应位置画三角； m2
被包含 P1和 P2所包含 ……
表 IV质蕴涵项最小项
P1
P2
P3
P4
P5
P6
P7
m2 m4 m8m6 m9 m12m10 m13 m15
只有 P7包含 4个最小项，其它只有 2个最小项步骤 2 寻找必要的质蕴涵项（续）
判断哪些行是必要的？ 先行消去,再列消去：
方法：先找只有一个 △ 的列,它们所对应的行一定要保留,这个 P项是 必要质蕴涵项 。
对表 IV,只有 m9和 m15对应的列只有一个 △ （ 在卡诺图中表示这两个最小项只被画一次 ）,这些列肯定是必要的； m9它所对应的 P7有 4个 △,分别对应 m8,m9,m12,m13.
因此 P7 为 必 要 的 。 由于 P7 必要,P7 所 蕴 涵 的
m8,m9,m12,m13可从表中暂时删去,以简化表 IV。
同理,由于 m15是必要的,P6也为必要,P6所蕴涵的 m13,
m15可以从表中暂时删去,如下图 。
,行消去,找到的是要保留的必要质蕴涵项,暂时从表格中消去的目的是为了简化表格 。
步骤 2 寻找必要的质蕴涵项（续）
表 V
P1
P2
P3
P4
P5
P6
P7
m2 m4 m8m6 m9 m12m10 m13 m15质蕴涵项最小项步骤 2 寻找必要的质蕴涵项（续）
,行消去,暂时消去了要保留的 必要质蕴涵项,使表格简化 。
,列消去,的目的是 去掉不必要的 质蕴涵项
方法：先找只有一个 △ 的行,如果在它所对应的列上也有 △,则表示这个 P项被其它行所包含,这个 P项就可以消去 。
在 Pi行记有 △ 的各列,若在 Pj行对应列中也均记有 △,则 Pi行就是不必要的质蕴涵项 。
步骤 2 寻找必要的质蕴涵项（续）
P1
P2
P3
P4
P5
m2 m4 m6 m10质蕴涵项最小项质蕴涵项最小项
m2 m4 m6
P1
P2
P3
m10
表 V 表 VI
表 V中,P4行只有一个 △,它所对应的 m4列包含在 P3行中,故 P4为非必要的质蕴涵项 。 同理,P5也为非必要的质蕴涵项 。 表 V简化为表 VI。
步骤 2 寻找必要的质蕴涵项（续）
最后，再对简化后的表 VI进行,行消去,。
m2 m4 m6
P1
P2
P3
m10质蕴涵项最小项 P
2,P3为必要质蕴涵项 （因为 m4 和 m10列只有一个 △，
所以 P2,P3 必须保留 ）
因 P2,P3蕴涵了表 VI中所列全部 m项（ m2,m4,m6,m10)，
故 P1为非必要 质蕴涵 项化简结果为
DBA C DDCACBA
PPPPF
7632
必要质蕴涵项的卡诺图表示
00 1101 10
00
11
01
10
00 0 1
01 0 1
11 1 0
11 0 1
B
AD
C
P2
P3
P6
P7
DBA C DDCACBA
PPPPF
7632
根据最小项编号中,1”的个数差 判断是否相邻 。
第一步求全部质蕴涵项 。 分组后在相邻组间反复比较,两个最小项间只要有一个变量不同,就可以消去一个变量,最后得到 覆盖 F所有最小项的 全部 质蕴涵项 。
第二步求必要质蕴涵项 。 找出只有一个 △ 的 mi列,
它所对应的 P项一定是要保留的； 找出只有一个 △ 的
Pi行,如果在它所对应的 m列上也有 △,则表示这个
P项是可以消去的 。 反复这一过程得到所有的 必要质蕴涵项 。
多输出逻辑函数的表格法化简不要求 (p38-45).
计算机辅助逻辑化简的其他算法还在继续研究 。
逻辑函数的表格化简法 (Q-M法 )小结
2.2.5 特殊形式的逻辑函数化简
基本形式的逻辑函数：
单输出逻辑函数,F＝ f(A,B,C…)
特殊形式的逻辑函数：
1,多输出逻辑函数
2,包含不管项的逻辑函数
只要求掌握卡诺图化简法
(1)多输出逻辑函数的化简多输出逻辑函数：同一组输入变量，有两个以上的输出。
F1＝ f(A,B,C…)
F2＝ f(A,B,C…)
化简时，在“与或”表达式中要尽量寻找公共的“与”项，使公共项为多个函数共享，这时从单个输出看可能不是最简，但总体是最简。
A B CCBACABF
A B CCBACBAF
2
1
0110
0010
BA
C 00 01 11 10
0
1
ACBAF1
0100
1100
BA
C 00 01 11 10
0
1
CBABF2
0110
0010
BA
C 00 01 11 10
0
1
A B CBAF1
0100
1100
BA
C 00 01 11 10
0
1
AB CCBF2
ABC是公共项单独看 F1,F2都是最简，但没有公共项。
(2)有“不管项”的逻辑函数化简包含不管项（ Don’t Care）的逻辑函数：函数 F的取值只和一部分最小项有关，另一部分最小项既可以取,0”，也可以取,1”，这些最小项称“不管项”或“任意项”。
“不管项”的两种情况：
1,这些输入组合不可能出现
2,其输入组合虽能出现，但最小项的值是,1”
还是,0”，人们不关心。
例：设计一位十进制数的数值范围判断器，
当 x>=5,F=1；否则,F=0。
(ABCD表示一位十进制数,A是低位,D是高位 )
10111
10110
10101
00100
00011
00010
00001
00000
FDCBA
φ1111
φ1110
φ1101
φ1100
φ1011
φ1010
11001
11000
FDCBA
0
1
2
3
4
5
6
7
8
9
有“不管项”的逻辑函数化简（续）
F的卡诺图
00 1101 10
00
11
01
10
00 0 0
10 1 1
φφ φ φ
11 φ φ
BC
D
AC
F=D+AC+BC
B
AD
C
把 φ项当作,1”
2.2.6 逻辑函数的实现由最小项和函数式表达的逻辑函数要用逻辑电路来实现。实现时要考虑的问题包括可用集成电路的种类、逻辑函数的形式、集成电路的级数等。
下列三种，”与非－与非”结构最常用。
与非－与非实现
与－或－非实现
或非－或非实现门电路符号
A X A X
B
A X
B
A X
B
A X
B
A X
B
A X
A X1
B
A X&
B
A X&
B
A X
1? BA X+
传统符号 IEEE标准符号 习惯符号门电路符号
B
A X
B
A X
B
A X
B
A X
1?
B
A X
1?
B
A X
1?
B
A X+
B
A X?
B
A X
例 1,异或逻辑
BABAF
A B F
0 0
1 0
0 1
1 1
0
1
1
0
A,B不相同时,F为 1； A,B
相同时,F为 0；因此称异或逻辑或半加逻辑。 表示为,F＝ A B
A
B F
逻辑符号异或逻辑的实现 AB F
BAABF
与－或－非
B
A
A
B
F
BABAF
或非－或非BA
A
B
F
与非－与非
BABAF
B
A
A
B
F
BABAF
与－或
B
A
A
B
F
书上例题书上例题书上例题书上例题书上例题例题逻辑问题的描述：逻辑设计的第一步。
由文字叙述的设计要求，抽象为逻辑表达式的过程。然后才能化简、实现。
真值表电路功能描述例,设计一个楼上、楼下开关的控制逻辑电路来控制楼梯上的路灯，使之在上楼前，用楼下开关打开电灯，上楼后，用楼上开关关灭电灯；
或者在下楼前，用楼上开关打开电灯，下楼后，
用楼下开关关灭电灯。
设楼上开关为 A，楼下开关为 B，灯泡为 Y。并设 A,B闭合时为 1，断开时为 0；灯亮时 Y为 1，
灯灭时 Y为 0。根据逻辑要求列出真值表。
A B Y
0 0
0 1
1 0
1 1
0
1
1
0
1
穷举法
1
2
逻辑表达式或卡诺图最简与或表达式化简 3
2
BABAY
已为最简与或表达式
4
逻辑变换
5
逻辑电路图
A
B
Y
&
&
& &
A
B
Y=1
用与非门实现 ABABABBABAY
BAY
用异或门实现真值表电路功能描述例,用与非门设计一个举重裁判表决电路。设举重比赛有 3个裁判，一个主裁判和两个副裁判。杠铃完全举上的裁决由每一个裁判按一下自己面前的按钮来确定。只有当两个或两个以上裁判判明成功，并且其中有一个为主裁判时，表明成功的灯才亮。
设主裁判为变量 C，副裁判分别为 B和 A；表示成功与否的灯为 Y，根据逻辑要求列出真值表。1
穷举法
1
C B A Y C B A Y
0 0 0
0 0 1
0 1 0
0 1 1
0
0
0
0
1 0 0
1 0 1
1 1 0
1 1 1
0
1
1
1
2
A B CBCACBAmmmY 765
2
逻辑表达式
B A
C 00 01 11 10
0
1
B
C
A
C
Y
&
&
&
3
卡诺图最简与或表达式化简 4
5
逻辑变换
6
逻辑电路图
3
化简 4
1 1 1
Y= BC +AC 5 ACBCY
6
例题例 1：设计一个多数表决逻辑电路，判别 A B
C三人中是否为多数赞同。
解：输入为 0，表示反对；
输入为 1，表示赞同；
当 ABC中有两个和两个以上为,1”时，表示多数赞同,F＝ 1；否则 F＝ 0。
C B A F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
多数表决逻辑电路的真值表
F＝ m3+m5+ m6+m7
例 2,1位二进制全加器的设计与实现
（不考虑进位叫半加,考虑进位叫全加 ）
真值表
11111
10011
10101
01001
10110
01010
01100
00000
CnFnCn-1YnXn
框图
Cn
Fn
Xn Yn Cn-1
∑
3个输入
2个输出输 入 输 出全加器逻辑的卡诺图化简
0101
1010
XnYn
Cn-1 00 01 11 10
0
1
nF
1110
0100
XnYn
Cn-1 00 01 11 10
0
1
nC
111 )( nnnnnnnnnnnn CYXYXCYCXYXC
)(
)()(
1
11
1111
nnn
nnnnnnnnnn
nnnnnnnnnnnnn
YXC
YXYXCYXYXC
CYXCYXCYXCYXF
实现方案一
Fn用异或门实现 Cn用,与非,门实现 Cn用,与或非,门实现
Xn
Yn
Cn-1 Fn
Xn
Yn
Cn-1
Cn Cn
Xn
Yn
Cn-1
Cn与或 —— 与非 Cn与或 —— 与或非实现方案二直接由最小项用与或非门实现，需要 3级门实现方案三写 的表达式F C
1111 nnnnnnnnnnnn CYXCYXCYXCYXF
1111 nnnnnnnnnnnn CYXCYXCYXCYXFF
11 nnnnnnn CYCXYXC
11 nnnnnnnn CYCXYXCC
经变换后只要 2级门。
实现方案三（续）
补充 逻辑函数的表示方法
1,真值表真值表：是由变量的所有可能取值组合及其对应的函数值所构成的表格。
真值表列写方法：每一个变量均有 0,1两种取值,n个变量共有 2i种不同的取值，将这 2i种不同的取值按顺序（一般按二进制递增规律）排列起来，同时在相应位置上填入函数的值，
便可得到逻辑函数的真值表。
A B C Y
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
0
1
0
0
1
1
例如：当 A=B=1、或则 B=C=1时，
函数 Y=1；否则 Y=0。
2,逻辑表达式逻辑表达式：是由逻辑变量和与、或、非 3种运算符连接起来所构成的式子。
函数的标准与或表达式的列写方法：将函数的真值表中那些使函数值为
1的最小项相加，便得到函数的标准与或表达式。
)7,6,3(m
ABCCABBCAY
3,卡诺图卡诺图：是由表示变量的所有可能取值组合的小方格所构成的图形。
逻辑函数卡诺图的填写方法：
在那些使函数值为 1的变量取值组合所对应的小方格内填入 1，其余的方格内填入 0，便得到该函数的卡诺图。
A B
C 00 01 11 10
0 0 0 1 0
1 0 1 1 0
4,逻辑图逻辑图：是由表示逻辑运算的逻辑符号所构成的图形。
Ｙ＝ＡＢ＋ＢＣ
Y
&
≥ 1
&
A
B
B
C
ＡＢ
ＢＣ
５、波形 图波形图：是由输入变量的所有可能取值组合的高、低电平及其对应的输出函数值的高、
低电平所构成的图形。
Ｙ＝ＡＢ＋ＢＣ
Ａ
Ｂ
Ｃ
Ｙ
０
０
０
０
０
０
１
０
０
１
０
０
０
１
１
１
１
０
０
０
１
０
１
０
１
１
０
１
１
１
１
１
０
０
０
０
Ｙ
2.4.2 逻辑函数表示方法之间的转换
1、由真值表到 逻辑图的转换真值表逻辑表达式或卡诺图
A B C Y
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
1
0
0
1
1
1
)7,6,5,2(m
ABCCABCBACBAY
1 1
A B
C 00 01 11 10
0 0 1 0 1
1 0 0 1 1
最简与或表达式化简 2
或
ACBACBAY
2
&
画逻辑图
3 &
&
≥1
ABCA
最简与或表达式
ACBACBAY
&
C
B
B
A
A
C
AB
AC
Y
A
C
B
B
A
A
C
Y
&
&
&
ABC
AB
AC
若用与非门实现，将最简与或表达式变换乘最简与非 -
与非表达式
ACBACBAY
3
2、由 逻辑图 到真值表 的转换逻辑图逻辑表达式
1
1
最简与或表达式化简 2
&
A ≥1
C
B
B
A
A
C
Y≥1
≥1
CBAY1
BAY2
CAY3
1Y
2Y
3Y
))()((
321
CABACBA
YYYY
2
CAABCBA
CBACBACABACBAY
))(())()((
从输入到输出逐级写出
A B C Y
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
1
0
0
1
0
1
1
最简与或表达式
3
真值表
CAABCBAY
3
