1.4 卡诺图化简（续）
－ 特殊形式的逻辑函数化简
逻辑函数的基本形式：
单输出逻辑函数,F＝ f(A,B,C… )
特殊形式的逻辑函数：
1,多输出逻辑函数
2,包含不管项的逻辑函数
(1)多输出逻辑函数的化简多输出逻辑函数：同一组输入变量，有两个以上的输出。
F1＝ f(A,B,C… )
F2＝ f(A,B,C… )
化简时，在,与或,表达式中要尽量寻找公共的,或,项，使公共项为多个函数共享，这时从单个输出看可能不是最简，但总体是最简。
例,P39上的例题，如果按每个表达式单独化简到最简，用 4个门 (图 2-24(b))。如果两个表达式综合考虑，只用 3个门 (图 2-25(b))。
(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
有,不管项,的逻辑函数化简（续）
作 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”
1.5 逻辑函数的表格法化简 (Q-M法 )
—— 计算机辅助逻辑设计的方法
卡诺图法化简直观方便，过程简单明了，
但只适合于变量数 <=4的函数。
Q-M(Quine-McCluskey) 法和卡诺图法的化简思路是一致的。
Q-M法是用分组表格法，把两相邻与项合成为一新的与项，从而消去一变量。
它适合于变量数 >4的函数，化简过程规律性强，适用于计算机算法实现。
Q-M方法的基本思想
什么情况下会出现,相邻两个最小项中有一个变量互补,？
从最小项的编号上看有什么规律？
观察：以 4变量卡诺图为例：
m1 同 m0,m3,m5,m9相邻，
下标编号为,0001与 0000,0011,0101,1001
m1 同 m4,m8,m10,m13等不相邻，
下标编号为,0001与 0100,1000,1010,1101
结论,
最小项编号中,1”的个数差＝ 0,肯定不相邻最小项编号中,1”的个数差 >＝ 2，肯定不相邻最小项编号中,1”的个数差＝ 1，可能相邻！
按照最小项 mi下标编号中二进制数,1”的个数进行分组比较，
可以化简 。
4变量 Karnaugh Map
B
AD
C
00 1101 10
00
11
01
10
m1m0 m3 m2
m5m4 m7 m6
m13m12 m15 m14
m9m8 m11 m10
逻辑函数的 Q-M法化简步骤 1 寻找函数的全部质蕴涵项先把 F中的各 mi，按下标 i中,1”的个数，由少到多，
分组排队列表 (见表 I) 。组号是 mi中 i所包含,1”的个数。
在表 I的相邻组间进行逐项搜索，寻找相邻项，把可以合并的记在 表 II中，并在表 I中相应的最小项旁作记号
,√” 。表 II所列均是变量数为 n-1的与项（ n是 F的变量数），它们同样按与项所含,1”的个数由少到多，分组排列。
重复上述过程，直到不能合并为止。
逻辑函数的 Q-M法化简（续）
例,
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
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
逻辑函数的 Q-M法化简（续）
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
逻辑函数的 Q-M法化简（续）
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
P5
逻辑函数的 Q-M法化简（续）
由图可见,P1~ P7覆盖了 F的全部最小项；对每个 P项,它们是不能再和其它 P项或最小项合并了 。
由图还可见,P1~ P7中有不必要的质蕴涵项：
例如,若 P2,P3必须,则 P1就不必要 。
为此,下一步骤就要从全部质蕴涵项中选出必要的质蕴涵项 。
步骤 2 寻找必要的质蕴涵项先作 P1~ P7和 mi对应的表格（表 IV），进行“行消去”
表 IV
质蕴涵项最小项
P1
P2
P3
P4
P5
P6
P7
m2 m4 m8m6 m9 m12m10 m13 m15
步骤 2 寻找必要的质蕴涵项（续）
,行消去,,
在 mi列记有 △ 的各行,若在 mj列对应行也均记有 △,
则 mi列记有 △ 所对应的 P项为必要 。
对表 IV,m9列只有一个 △,它所对应的 P7有 4个 △,
分别对应 m8,m9,m12,m13。 由于 P7为必要,P7所蕴涵的 m8,m9,m12,m13均可从表中删去,以简化表 IV。
同理,P6也为必要,P6所蕴涵的 m13,m15可以从表中删去,如下图 。
简化后的表 IV,示于表 V。 再对表 V进行,列消去,。
步骤 2 寻找必要的质蕴涵项（续）
表 V
P1
P2
P3
P4
P5
P6
P7
m2 m4 m8m6 m9 m12m10 m13 m15质蕴涵项 最小项步骤 2 寻找必要的质蕴涵项（续）
,列消去,,
在 Pi行记有 △ 的各列,若在 Pj行对应列中也均记有 △,则 Pi行为非必要质蕴涵项 。
对于表 V,P4行只有一个 △,它所对应的 m4列包含在 P3行中,故 P4为非必要的质蕴涵项 。
同理,P5也为非必要的质蕴涵项 。
步骤 2 寻找必要的质蕴涵项（续）
P1
P2
P3
P4
P5
m2 m4 m6 m10质蕴涵项最小项质蕴涵项最小项
m2 m4 m6
P1
P2
P3
m10
表 V
表 VI
步骤 2 寻找必要的质蕴涵项（续）
最后，再对简化后的表 VI进行,行消去,。
m2 m4 m6
P1
P2
P3
m10质蕴涵项最小项 P
2,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
表格法很繁琐，并非实用。
计算机辅助逻辑化简的其他方法，在高年级选修课程和研究生课程中还会学到。
书上改错,36－ 37
1.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? B
A X+
门电路符号
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
BABAF
BABAF
BABAFBAABF
与－或 与非－与非与－或－非 或非－或非
A
B F
异或五种实现的传输级数
与非－与非、或非－或非都是 2级门
,与－或－非,,,异或,门是 1.5级门
,与非,门最常用
,与,门,,或,门最少用综合例题逻辑问题的描述：逻辑设计的第一步。
由文字叙述的设计要求，抽象为逻辑表达式的过程。然后才能化简、实现。
例 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
Fn Cn
Xn
Yn
Cn-1
实现方案二直接由最小项用与或非门实现，需要 3级门实现方案三写 的表达式F C
1111 nnnnnnnnnnnn CYXCYXCYXCYXF
1111 nnnnnnnnnnnn CYXCYXCYXCYXFF
11 nnnnnnn CYCXYXC
11 nnnnnnnn CYCXYXCC
经变换后只要 2级门。
实现方案三（续）
本章重点：
逻辑代数与逻辑函数的概念逻辑函数的化简，重点是卡诺图法第二章 组合逻辑电路
Combinational Logic Circuit
组合逻辑电路的特点
电路的输出只是和当前状态有关，和过去的状态无关。
区别于时序电路：和过去的状态有关。
组合逻辑：电路的输出只是和当前状态有关，
和过去的状态无关。
a
b c
a
b
c
理想情况：门电路没有延迟组合逻辑：电路的输出只是和当前状态有关，
和过去的状态无关。
a
b c
a
b
c
pDtpDt
实际情况：门电路存在延迟 pDt
组合逻辑：电路的输出只是和当前状态有关，
和过去的状态无关 。
a
b c
a
b
c
pHLtpLHt
实际情况：门电路存在延迟前沿延迟与后沿延迟不相等基本的组合逻辑电路
（ 1）门电路 （ Gates）
（ 2）译码电路 （ Decoders）
编码电路 （ Encoders）
（ 3）数据选择电路 （ Multiplexer）（多路开关）
或数据选择器 （ Data Selector）
（ 4） 加法器 （ Adders）
算术逻辑单元 ( Arithmetic Logic Units )
（ 5）奇偶校验电路
作业,2.8; 2.10; 2.11.3; 2.12.3;
2.13.4; 2.14.1; 2.16.1
(2.10第二个门是或非门，书上少,＋,）
下周一交到实验室,9区 416
166.111.136.2/incoming
答疑：周四下午 2,30－ 5,00
地点：主楼 8区 403或 412找巴林凤老师
Email,yangshq@tsinghua.edu.cn
－ 特殊形式的逻辑函数化简
逻辑函数的基本形式：
单输出逻辑函数,F＝ f(A,B,C… )
特殊形式的逻辑函数：
1,多输出逻辑函数
2,包含不管项的逻辑函数
(1)多输出逻辑函数的化简多输出逻辑函数：同一组输入变量，有两个以上的输出。
F1＝ f(A,B,C… )
F2＝ f(A,B,C… )
化简时，在,与或,表达式中要尽量寻找公共的,或,项，使公共项为多个函数共享，这时从单个输出看可能不是最简，但总体是最简。
例,P39上的例题，如果按每个表达式单独化简到最简，用 4个门 (图 2-24(b))。如果两个表达式综合考虑，只用 3个门 (图 2-25(b))。
(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
有,不管项,的逻辑函数化简（续）
作 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”
1.5 逻辑函数的表格法化简 (Q-M法 )
—— 计算机辅助逻辑设计的方法
卡诺图法化简直观方便，过程简单明了，
但只适合于变量数 <=4的函数。
Q-M(Quine-McCluskey) 法和卡诺图法的化简思路是一致的。
Q-M法是用分组表格法，把两相邻与项合成为一新的与项，从而消去一变量。
它适合于变量数 >4的函数，化简过程规律性强，适用于计算机算法实现。
Q-M方法的基本思想
什么情况下会出现,相邻两个最小项中有一个变量互补,？
从最小项的编号上看有什么规律？
观察：以 4变量卡诺图为例：
m1 同 m0,m3,m5,m9相邻，
下标编号为,0001与 0000,0011,0101,1001
m1 同 m4,m8,m10,m13等不相邻，
下标编号为,0001与 0100,1000,1010,1101
结论,
最小项编号中,1”的个数差＝ 0,肯定不相邻最小项编号中,1”的个数差 >＝ 2，肯定不相邻最小项编号中,1”的个数差＝ 1，可能相邻！
按照最小项 mi下标编号中二进制数,1”的个数进行分组比较，
可以化简 。
4变量 Karnaugh Map
B
AD
C
00 1101 10
00
11
01
10
m1m0 m3 m2
m5m4 m7 m6
m13m12 m15 m14
m9m8 m11 m10
逻辑函数的 Q-M法化简步骤 1 寻找函数的全部质蕴涵项先把 F中的各 mi，按下标 i中,1”的个数，由少到多，
分组排队列表 (见表 I) 。组号是 mi中 i所包含,1”的个数。
在表 I的相邻组间进行逐项搜索，寻找相邻项，把可以合并的记在 表 II中，并在表 I中相应的最小项旁作记号
,√” 。表 II所列均是变量数为 n-1的与项（ n是 F的变量数），它们同样按与项所含,1”的个数由少到多，分组排列。
重复上述过程，直到不能合并为止。
逻辑函数的 Q-M法化简（续）
例,
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
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
逻辑函数的 Q-M法化简（续）
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
逻辑函数的 Q-M法化简（续）
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
P5
逻辑函数的 Q-M法化简（续）
由图可见,P1~ P7覆盖了 F的全部最小项；对每个 P项,它们是不能再和其它 P项或最小项合并了 。
由图还可见,P1~ P7中有不必要的质蕴涵项：
例如,若 P2,P3必须,则 P1就不必要 。
为此,下一步骤就要从全部质蕴涵项中选出必要的质蕴涵项 。
步骤 2 寻找必要的质蕴涵项先作 P1~ P7和 mi对应的表格（表 IV），进行“行消去”
表 IV
质蕴涵项最小项
P1
P2
P3
P4
P5
P6
P7
m2 m4 m8m6 m9 m12m10 m13 m15
步骤 2 寻找必要的质蕴涵项（续）
,行消去,,
在 mi列记有 △ 的各行,若在 mj列对应行也均记有 △,
则 mi列记有 △ 所对应的 P项为必要 。
对表 IV,m9列只有一个 △,它所对应的 P7有 4个 △,
分别对应 m8,m9,m12,m13。 由于 P7为必要,P7所蕴涵的 m8,m9,m12,m13均可从表中删去,以简化表 IV。
同理,P6也为必要,P6所蕴涵的 m13,m15可以从表中删去,如下图 。
简化后的表 IV,示于表 V。 再对表 V进行,列消去,。
步骤 2 寻找必要的质蕴涵项（续）
表 V
P1
P2
P3
P4
P5
P6
P7
m2 m4 m8m6 m9 m12m10 m13 m15质蕴涵项 最小项步骤 2 寻找必要的质蕴涵项（续）
,列消去,,
在 Pi行记有 △ 的各列,若在 Pj行对应列中也均记有 △,则 Pi行为非必要质蕴涵项 。
对于表 V,P4行只有一个 △,它所对应的 m4列包含在 P3行中,故 P4为非必要的质蕴涵项 。
同理,P5也为非必要的质蕴涵项 。
步骤 2 寻找必要的质蕴涵项（续）
P1
P2
P3
P4
P5
m2 m4 m6 m10质蕴涵项最小项质蕴涵项最小项
m2 m4 m6
P1
P2
P3
m10
表 V
表 VI
步骤 2 寻找必要的质蕴涵项（续）
最后，再对简化后的表 VI进行,行消去,。
m2 m4 m6
P1
P2
P3
m10质蕴涵项最小项 P
2,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
表格法很繁琐，并非实用。
计算机辅助逻辑化简的其他方法，在高年级选修课程和研究生课程中还会学到。
书上改错,36－ 37
1.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? B
A X+
门电路符号
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
BABAF
BABAF
BABAFBAABF
与－或 与非－与非与－或－非 或非－或非
A
B F
异或五种实现的传输级数
与非－与非、或非－或非都是 2级门
,与－或－非,,,异或,门是 1.5级门
,与非,门最常用
,与,门,,或,门最少用综合例题逻辑问题的描述：逻辑设计的第一步。
由文字叙述的设计要求，抽象为逻辑表达式的过程。然后才能化简、实现。
例 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
Fn Cn
Xn
Yn
Cn-1
实现方案二直接由最小项用与或非门实现，需要 3级门实现方案三写 的表达式F C
1111 nnnnnnnnnnnn CYXCYXCYXCYXF
1111 nnnnnnnnnnnn CYXCYXCYXCYXFF
11 nnnnnnn CYCXYXC
11 nnnnnnnn CYCXYXCC
经变换后只要 2级门。
实现方案三（续）
本章重点：
逻辑代数与逻辑函数的概念逻辑函数的化简，重点是卡诺图法第二章 组合逻辑电路
Combinational Logic Circuit
组合逻辑电路的特点
电路的输出只是和当前状态有关，和过去的状态无关。
区别于时序电路：和过去的状态有关。
组合逻辑：电路的输出只是和当前状态有关，
和过去的状态无关。
a
b c
a
b
c
理想情况：门电路没有延迟组合逻辑：电路的输出只是和当前状态有关，
和过去的状态无关。
a
b c
a
b
c
pDtpDt
实际情况：门电路存在延迟 pDt
组合逻辑：电路的输出只是和当前状态有关，
和过去的状态无关 。
a
b c
a
b
c
pHLtpLHt
实际情况：门电路存在延迟前沿延迟与后沿延迟不相等基本的组合逻辑电路
（ 1）门电路 （ Gates）
（ 2）译码电路 （ Decoders）
编码电路 （ Encoders）
（ 3）数据选择电路 （ Multiplexer）（多路开关）
或数据选择器 （ Data Selector）
（ 4） 加法器 （ Adders）
算术逻辑单元 ( Arithmetic Logic Units )
（ 5）奇偶校验电路
作业,2.8; 2.10; 2.11.3; 2.12.3;
2.13.4; 2.14.1; 2.16.1
(2.10第二个门是或非门，书上少,＋,）
下周一交到实验室,9区 416
166.111.136.2/incoming
答疑：周四下午 2,30－ 5,00
地点：主楼 8区 403或 412找巴林凤老师
Email,yangshq@tsinghua.edu.cn
