复旦大学电子工程系 陈光梦数字逻辑基础复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 2
数字逻辑与数字电路的历史
逻辑代数的历史
1849年，爱尔兰数学家乔治 〃 布尔 (George Boole)创立布尔代数。
20世纪 30年代，在贝尔实验室工作的香农 (Claude
Shannon)继承了布尔的工作并加以 发展和应用。
随着电子技术和计算机技术的发展，布尔代数在数字逻辑电路的分析和设计中得到了广泛的应用，统称为逻辑代数。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 3
集成电路的历史
1947年晶体管发明引起了电子学的一次革命。晶体管由巴丁 (John Bardeen),布雷登 (Wailter Houser Brattain)和肖克莱 (William Schokley)共同发明，该发明促成了计算机、通信等方面的飞速发展。鉴于它的重要价值，这些人共同获得了 1956年的诺贝尔物理学奖。
1958年，德克萨斯仪器公司的基尔白 (Clair Kilby)、仙童半导体公司的诺依斯 (Robert Noyce)等人研究实现了集成电路。以后集成度越来越高，出现了超大规模集成电路，
这是电子学的又一次革命，也是近代科学技术发展的新的标志。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 4
集成电路的分类与数字集成电路的特点
集成电路分类
模拟集成电路，处理的信号是连续的（模拟信号）
数字集成电路，处理的信号是离散的（数字信号）
数字集成电路分类
逻辑集成电路、存储器、各类 ASIC
数字集成电路特点
信息表示形式统一、便于计算机处理
可靠性高
制造工艺成熟、可以大规模集成复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 5
数字集成电路的发展
集成度
SSI（ 1-10门，逻辑门电路）
MSI（ 10-100门，计数器、移位寄存器器 ）
LSI（ 100-1000门，小型存储器,8位算术逻辑单元）
VLSI（ 1000-100万门，大型存储器、微处理器 ）
ULSI（ 超过 100万门，可编程逻辑器件、多功能集成电路）
摩尔定律
集成度每 18个月翻一番复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 6
本课程的内容
数字逻辑的基本理论：逻辑代数
无记忆的逻辑电路：组合逻辑电路
有记忆的逻辑电路：触发器及时序逻辑电路（同步和异步）
可编程逻辑器件和数字系统：软件实验、后续课程学习复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 7
教科书与参考书教科书：陈光梦,数字逻辑基础,复旦大学出版社参考书：
陈光梦等，数字逻辑基础学习指导与教学参考，复旦大学出版社
阎石，数字电子技术基础，高教出版社
Victor P,Nelson etc,Digital Logic Circuit Analysis and Design，清华大学出版社
John M,Yarbrough，数字逻辑应用与设计，机械工业出版社
刘宝琴，数字电路与系统，清华大学出版社
唐竞新，数字电子技术基础解题指南，清华大学出版社
曾繁泰等,VHDL程序设计，清华大学出版社复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 8
与教师的联系
虚拟校园,http://vcampus.fudan.edu.cn
电子邮件,gmchen@fudan.edu.cn
电话,65643789
复旦大学电子工程系 陈光梦第 1章逻辑代数基础复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 10
本章要求
掌握逻辑代数的基本公式和基本定理
掌握逻辑函数的化简方法复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 11
1.1 逻辑代数概述
二值逻辑：逻辑关系中的条件和结论只取对立的两个值，例如是和非、对和错、真和假等等。
在逻辑代数中，通常用,1”代表“真”，用,0”代表
“假”。
二值逻辑的,1”与,0”是逻辑概念，仅代表真与假，没有数量大小。
在数字逻辑中，有时也用,1”与,0”表示二进制数。这仅仅是一种代码，实际的运算规律还是依照逻辑运算进行。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 12
常用二 － 十进制代码十进制码 二进制码（ 8421码） 余三码 余三循环码 移位码 5211码 5421码
0 0000 0011 0010 00000 0000 0000
1 0001 0100 0110 00001 0001 0001
2 0010 0101 0111 00011 0100 0010
3 0011 0110 0101 00111 0101 0011
4 0100 0111 0100 01111 0111 0100
5 0101 1000 1100 11111 1000 1000
6 0110 1001 1101 11110 1001 1001
7 0111 1010 1111 11100 1100 1010
8 1000 1011 1110 11000 1101 1011
9 1001 1100 1010 10000 1111 1100
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 13
逻辑函数
用一个数学表达式来描述一个逻辑关系问题
逻辑条件 → 输入变量 （ 自变量 ）
逻辑结论 → 输出变量 （ 因变量 ）
),( BAfY?
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 14
逻辑函数的表示方法
真值表
逻辑函数
逻辑图
卡诺图
硬件描述语言（ HDL）
以上 5种表示方法可以相互转换，各有特定用途复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 15
真值表
A B Y
0 0 0
0 1 0
1 0 0
1 1 1
A B Y
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 16
逻辑函数：基本逻辑运算
与 Y = A · B
或 Y = A + B
非 Y = A
A A
A + B
A · B
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 17
“与” 运算
A B Y = A·B
0 0 0
0 1 0
1 0 0
1 1 1
A B Y
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 18
“或” 运算
A B Y = A＋ B
0 0 0
0 1 1
1 0 1
1 1 1
A
B
Y
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 19
“非”运算
A Y
0 1
1 0
AY =
A Y
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 20
反函数
两个逻辑函数互为反函数，是指两个逻辑函数对于输入变量的任意取值，其输出逻辑值都 相反 。下面真值表中 F 和 G 互为反函数。
A B F(A,B) G(A,B)
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 21
复合逻辑运算
1,与非
2,或非
3,异或
4,同或
ABY?
BAY
Y A B A B A B
Y = A⊙ B BABA
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 22
复合逻辑运算的真值表
AB AB? AB?A B A⊙ B
0 0 1 1 0 1
0 1 1 0 1 0
1 0 1 0 1 0
1 1 0 0 0 1
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 23
逻辑图：基本逻辑单元
& 1 1
逻辑与 逻辑或 逻辑非
& 1 =1
与非 或非 异或
=
同或复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 24
逻辑图符号标注规定（ GB4728.12-1996）
所有逻辑符号都由方框（或方框的组合）和标注在方框内的总限定符号组成
&
总限定符号
&?1 =1 = 外部逻辑状态逻辑约定小圈表示逻辑非也可采用极性指示符内部逻辑状态复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 25
组合形式的逻辑图
&
=1
=1
&=1
一般表示法 组合表示法
A
B
C
A
B
C
Y Y
)()( CBBAY
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 26
国外逻辑图符号对照与门或门非门美、日常用符号国标符号GB4728.12-1996
&
1
1
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 27
异或门或非门与非门同或门
&
>1
=1
=
美、日常用符号国标符号GB4728.12-1996
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 28
1.2 逻辑代数的基本定理一,变量与常量的运算 (0-1律 )
A · 1 = A A + 0 = A
A · 0 = 0 A + 1 = 1
二、等幂律 A · A = A A+A = A
三、互补律 A · = 0 A+ = 1
四、自反律 = AA
AA
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 29
五、交换律
AB = BA A+B = B+A
六、结合律
A(BC) = (AB)C A+(B+C) = (A+B)+C
七、分配律
A(B+C) = AB+AC A+BC = (A+B)(A+C)
八、反演律（ De Morgan定理 ）
BABABAAB
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 30
代入定理在任何一个逻辑等式中，若将其中一个 逻辑变量全部 用另一个 逻辑函数 代替，则等式仍然成立。
例,若 Y=AC + BC，
C = P + Q
则 Y = A (P + Q) + B (P + Q)
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 31
反演定理对于任何一个逻辑函数式，将其中的,
所有逻辑符号,+,,,〃,交换 ;
所有逻辑常量,1,,,0,交换 ;
所有逻辑变量取反 ;
不改变原来的运算顺序。
得到的逻辑函数是原来逻辑函数的反函数。
例：
1))((
0
DCBAY
DCBAY
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 32
对偶定理对偶关系,逻辑符号,+,和,〃,
逻辑常量,1,和,0,
对偶式,所有逻辑符号,+,,〃,交换所有逻辑常量,1,,0,交换若两个函数相等，则由他们的对偶式形成的两个函数也相等。
例：若则
1))((
0)(
DCCACAD
DCCACDA
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 33
注意点
反演定理：描述原函数和反函数的关系（两个函数之间的关系）
对偶定理：描述原函数构成的逻辑等式和对偶函数构成的逻辑等式的关系（两个命题之间的关系）
在一般情况下，一个逻辑函数的反函数和对偶函数是不同的复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 34
常用逻辑恒等式
,( )
,( )
,
,( ) ( )
A A B A A A B A
A A B A B A A B A B
A A B A B A A B A B
A B A B B A B A B B
一,吸 收 律复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 35
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( )
A B A C B C A B A C
A B A C B C A B A C
A B A C B CD A B A C
A B A C B C D A B A C
二,冗 余 律复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 36
1.3 逻辑函数的化简与形式转换目标函数形式（原因：实际电路的需要）
与－或形式
或－与形式
与非－与非形式
或非－或非形式
与或非形式
混合形式复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 37
目标函数的要求：
逻辑电路的数量最少（面积约束）
逻辑电路的级数最少（速度约束）
输入端的数量最少（混合约束）
电路稳定可靠 （避免竞争－冒险）
具体问题具体分析，没有一成不变的规定复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 38
代数法化简逻辑函数
公式法化简可以适用于任何场合，但是通常没有一定的规律可循，需要敏锐的观察力和一定的技巧。
最常用的化简手段是吸收律、冗余律和反演律。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 39
代数法化简的例子
()
Y A B C A B C A B
A B A B A
Y A B C A B C A B
A B A B
B
例 一,化 简 函 数解,利 用,将 原 式 化 简,
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 40
()
()
Y A B A CD B CD
A B A A
Y A B A CD B CD
A B A B CD
A B A B CD
AB
AB
例 二,化 简 函 数解,利 用 反 演 律 和,将 原 式 化 简复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 41
1
( ) ( )
( ) ( ) ( )
Y A B B C B C A B
AA
Y A B B C A A B C A B C C
A B B C A B C A B C A B C A B C
A B A B C B C A B C A B C A B C
A B B C A C
例 三,化 简 函 数解,利 用,在 原 式 中 添 加 一 些 项,然 后 化 简复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 42
0
()
()
Y A B C A B C A B
AA
Y A B A B A B C A B C A B
A B A B C A B C A B
A B A B C A B C A B A B C
例 四,化 简 函 数解,利 用,在 原 式 中 添 加 一 些 项,然 后 化 简复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 43
逻辑函数形式转换的例子
* ( ) ( )
( * ) *
( ) ( ) ( ) ( )
Y A B C D
Y A B C D
A C B C A D B D
YY
A C B C A D B D
以 逻 辑 函 数 ＋ 为 例,
例 一,将,与 － 或,函 数 化 为,或 － 与,式利 用 对 偶 定 理 实 现 之,
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 44
Y A B C D
Y A B C D
A B C D
例 二,将,与 － 或,函 数 ＋
转 化 为,与 非 － 与 非,式利 用 两 次 求 反,将 原 式 转 换,
＋
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 45
( * ) *
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
Y A B CD
YY
A C B C A D B D
A C B C A D B D
A C B C A D B D
例 三,将,与 － 或,函 数 ＋
化 为,或 非 － 或 非,式解,先 利 用 对 偶 定 理 变 成,或 与,式,再 两 次 求 反复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 46
( ) ( )
Y A B CD
Y A B CD
A B CD
A B C D
A C B C A D B D
例 四,将,与 － 或,函 数 ＋
化 为,与 或 非,式解,利 用 两 次 求 反,将 原 式 转 换
＋
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 47
逻辑函数的卡诺图表示和卡诺图化简法特点：
图形化简法
标准的表达方式
规律的化简过程
变量数目有限制（最多 5～ 6个）
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 48
最小项在 n个逻辑变量的逻辑函数中，若 m为包含 n个因子的乘积项（逻辑与），且其中每个逻辑变量都以原变量或反变量的形式出现一次并仅仅出现一次，则称 m为这 n个变量的最小项。
例：
记为 m2
记为 m5
记为 m7abc
cba
cba
abccbacbaabcf)(
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 49
最大项在 n个逻辑变量的逻辑函数中，若 M为包含 n个因子的和项（逻辑或），且其中每个逻辑变量都以原变量或反变量的形式出现一次并仅仅出现一次，则称 M为这 n个变量的最大项。
例：
记为 M2
记为 M5
记为 M7cba
cba
cba
cbacbacbaabcf
))()(()(
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 50
最小项与最大项的比较以 3变量函数为例
CBAMCBAm
CBAMCBAm
CBAMCBAm
CBAMCBAm
CBAMCBAm
CBAMCBAm
CBAMCBAm
CBAMCBAm
77
66
55
44
33
22
11
00
最大项：最小项：
最大项：最小项：
最大项：最小项：
最大项：最小项：
最大项：最小项：
最大项：最小项：
最大项：最小项：
最大项：最小项：
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 51
最小项和最大项的性质对于一个具有 n 个变量的逻辑问题，在输入变量的任意一种取值情况下，总有：
一、必有且仅有一个最小项的逻辑值为 1；必有且仅有一个最大项的逻辑值为 0。
二、任意 2个 不同的最小项之积为 0；任意两个不同的最大项之和为 1。
1,0 jiji MMmm
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 52
三、全体最小项之和为 1；全体最大项之积为 0。
四、下标相同的最大项和最小项互补。
12
0
12
0
0,1
nn
i
i
i
i Mm
ii Mm?
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 53
逻辑函数的两种标准表达式
最小项之和形式，简称为积之和 (SOP)形式
最大项之积形式，简称为和之积 (POS)形式
10),...,,(
12
0
21 ormxxxf i
i
iin
n
＝，
＝
10)(),...,,(
12
0
21 orMxxxf i
i
iin
n
＝，
＝
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 54
标准表达式的关系性质 1、一个逻辑函数的两种标准逻辑表达式之间，
存在以下关系：
若 则性质 2、一个逻辑函数与其反函数的逻辑表达式之间，存在以下关系：
若 则
imF jMF
imF iMF
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 55
将逻辑函数化成标准形式
要求按积之和形式展开函数，可以将 非最小项的积项 乘以形如 的项，其中 A 是那个非最小项的积项中缺少的输入变量，然后展开，最后合并相同的最小项。
要求按和之积形式展开函数，可以将 非最大项的和项 加上形如 的项，其中 A 是那个非最大项的和项中缺少的输入变量，然后展开，最后合并相同的最大项。
AA?
AA?
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 56
卡诺图
每个方格代表一个最小项或者最大项。
变量排列按照相邻规则进行，即在卡诺图中相邻的方格在逻辑上也相邻。（相邻的意义：两个最小项或最大项之间只有一个变量发生变化）
BC
A 00 01 11 10
0
1
0 1 3 2
64 5 7
B
A 0 1
0
1
0 1
2 3
CD
AB
00 01 11 10
0 1 3 2
64 5 7
00
01
11
10
12 13 15 14
108 9 11
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 57
卡诺图的填法
X 3 X 4
X 1 X 2
00 01 11 10
1 0 0 0
01 1 0
00
01
11
10
0 1 1 1
01 1 1
)12,10,7,6,3,2,1(
)15,14,13,11,9,8,5,4,0(),,,( 4321
M
mxxxxf
最小项填 1
最大项填 0
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 58
卡诺图化简法根据相邻的方格在逻辑上也相邻的原理，只要相邻的方格满足以下条件：
一、逻辑值相同；
二、小方格数为 2n 个。
就可以将相邻的方格合并为一个 卡诺圈 。
卡诺圈越大，可以消去的变量越多，最后得到的逻辑函数越简单。
若卡诺圈包含的小方格数为 2n 个，而这个逻辑函数具有 m 个变量，则这个卡诺圈对应的项中包含的变量数目为 m–n 个。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 59
卡诺图的圈法（ SOP）
圈,1”
包含 2n个方格尽可能大不遗漏
X 3 X 4
X 1 X 2
00 01 11 10
1 0 0 0
01 1 0
00
01
11
10
0 1 1 1
01 1 1
X 1 X 2 X 3
X 1 X 4
X 2 X 3 X 4
X 1 X 2 X 3
41321321432 xxxxxxxxxxxf
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 60
卡诺图的圈法（ POS）
圈,0”
包含 2n个方格尽可能大不遗漏
X 3 X 4
X 1 X 2
00 01 11 10
1 0 0 0
01 1 0
00
01
11
10
0 1 1 1
01 1 1
X 2 + X 3 + X 4
X 1 + X 3
X 1 + X 2 + X 4
X 1 + X 2 + X 3 + X 4
))()()(( 314324321421 xxxxxxxxxxxxf
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 61
卡诺图化简法的要点
将逻辑函数化为标准形式（或真值表）
填卡诺图
圈卡诺圈（满足 2n个方格要求、尽可能大、不遗漏）
根据卡诺圈写出化简后的逻辑函数
若有必要，运用反演律对所得结果进行变换复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 62
卡诺图化简的例（一）
12(,,,) (,,,)
( 3,4,6,1 1,1 2,1 4 ) ( 0,1,2,5,8,1 0,1 3 )
F f a b c d F f a b c d
mm
0
01
1001
10
00 01 11 10
00
10
11
01
ab
0
0
01
1
0
0
cd
1
10
0010
01
00 01 11 10
00
10
11
01
ab
1
0
10
0
0
1
cd
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 63
卡诺图化简的例（二）
34(,,,) (,,,)
(0,1,2,5,8,1 0,1 3 ) ( 3,5,7,9,1 1)
F f a b c d F f a b c d
MM
0
01
1101
10
00 01 11 10
00
10
11
01
ab
0
1
01
1
1
0
cd
1
11
1001
01
00 01 11 10
00
10
11
01
ab
1
1
10
1
0
1
cd
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 64
卡诺图化简法的一些术语
蕴涵,逻辑函数的,与或,表达式中的各项
质蕴涵,不能再与其他蕴涵合并的蕴涵
必要质蕴涵,包含一个或多个唯一的最小项的质蕴涵
覆盖,包含了逻辑函数中所有最小项的一些蕴涵之,或,
非冗余覆盖,其中每一个蕴涵都是必不可少的覆盖
最小覆盖,包含蕴涵个数最少，每个蕴涵中包含的最小项又较少的非冗余覆盖复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 65
最小覆盖的不惟一性
X 3 X 4
X 1 X 2
00 01 11 10
1 0 0 1
01 1 1
00
01
11
10
0 1 1 0
10 0 1
一个逻辑函数，其最小覆盖总是由必要质蕴涵和部分质蕴涵组成，所以它的最小覆盖可能不是惟一的，即它的最简逻辑表达式可能不是惟一的。
绿色：必要质蕴涵红色和白色：质蕴涵最小覆盖：
绿色＋红色或：绿色＋白色复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 66
利用卡诺图运算来进行逻辑化简逻辑函数 → 卡诺图逻辑函数的运算 → 卡诺图的运算卡诺图的运算 → 对应的方格进行运算证明（以,与,运算为例）：
1 1 2 2
1 2 1 2
1 2 1 2 1 2
,,
( ) ( ) ( )
i i i i
i i i i
i i i i i i j i i i
i i j i
f m f m
f f m m
m m m m
设 则 有证明的最后一步运用了最小项的性质 2
思考题,试证明“或”、“非”运算亦符合上述规则复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 67
利用卡诺图运算来进行逻辑化简的例
CD
00 01 11 10
1 1 1 1
11 1 1
00
01
11
10
1 1 1
11 1
AB
CD
00 01 11 10
11 1 1
00
01
11
10
1 1 1 1
AB
CD
00 01 11 10
11 1 1
00
01
11
10
1 1 1
AB
Y B C DA
·=
·=
)14,13,12,7,6,5,4(),,,( mDCBAY
BADBCBY
C D ABY
常规化简运算化简复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 68
CD
00 01 11 10
11
00
01
11
10
1 1 1
1 1
AB
CD
00 01 11 10
1
1
00
01
11
10
1 1 1 1
1
AB
CD
00 01 11 10
1
00
01
11
10
1 1 1
1
AB
Y A B +C D A D+BC
·=
·=
)15,14,13,11,7(),,,( mDCBAY
A C DB C DA B CA B DY
)()( BCADCDABY
常规化简结果为 3,4 输入端，共 16输入端运算化简结果为 2 输入端，共 14输入端复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 69
卡诺图运算的一些有关规律
0重心,0号方格（即全部变量为 0的方格）
1重心,2n号方格（即全部变量为 1的方格）
包含 0重心但不包含 1重心的质蕴涵，其表达式全部用反变量标注
包含 1重心但不包含 0重心的质蕴涵，其表达式全部用原变量标注
既不包含 0重心也不包含 1重心的质蕴涵，其表达式中一定既有原变量又有反变量
目标函数是与非形式并要求全部用原变量表达时，围绕 1重心进行。其中卡诺圈圈 1，阻塞圈圈 0
目标函数是或非形式并要求全部用原变量表达时，围绕 0重心进行，其中卡诺圈圈 0，阻塞圈圈 1
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 70
不完全确定的逻辑函数的化简不完全确定的逻辑函数：
由 n 个逻辑变量构成的逻辑函数中，有效的逻辑状态数小于 2n个。那些无效的状态或者是不可能出现，或者无意义。
这些无效的状态被称为任意项，或称为无关项、约束项、禁止项，等等复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 71
任意项的处理任意项的值既可为 1也可为 0
带有任意项的逻辑函数在化简时既可以将任意项圈入卡诺圈，也可以不圈入卡诺圈适当地将一些任意项圈入卡诺圈，可以使化简的结果得到极大的简化
X 3 X 4
X 1 X 2
00 01 11 10
1 1
00
01
11
10
d 1 1
d 1 d
d
黄色：不考虑任意项红色：考虑任意项复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 72
0
10
0110
01
00 0 1 1 1 1 0
00
10
11
01
uv
d
1
dd
d
1
0
wx
56(,,,) (,,,)
( 2,3,4,5,1 3,1 5 ) ( 1,5,7,9,1 3,1 5 )
( 8,9,1 0,1 1 ) ( 8,1 0,1 1,1 4 )
F f a b c d F f u v w x
mm
dd
0
10
0011
10
00 01 11 10
00
10
11
01
ab
d
1
dd
0
d
1
cd
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 73
注意点任意项的表现形式除了直接用最小项形式表示外，
还经常用逻辑表达式表示，称为约束方程对于用约束方程给出的逻辑问题，一般要将约束条件改写成用最小项表示的任意项形式，才能用卡诺图进行化简例如,A =1,B =1这种输入状态不可能出现，可记为 AB=0。在卡诺图中就是对应 AB=11的最小项为任意项复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 74
使用异或函数的卡诺图化简异或运算的性质,
ABBA
CBACBACBA )()(
AAAA 1,0
1,0 AAAA
BABABA
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 75
异或（同或）函数的卡诺图
,棋盘格,特征
异或 函数的棋盘格特征,0号方格等于 0
同或 函数的棋盘格特征,0号方格等于 1
X 3 X 4
X 1 X 2
00 01 11 10
1
100
01
11
10
1
1
1
1 1
1
X 3 X 4
X 1 X 2
00 01 11 10
1
100
01
11
10
1
1
1
1 1
1
同或函数异或函数复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 76
利用异或函数化简的例子（一）
1
00
0010
00
00 01 11 10
00
10
11
01
ab
0
1
10
0
0
0
cd
))(( dbcaP dcbW
0
01
0101
01
00 01 11 10
00
10
11
01
ab
0
1
10
0
1
1
cd
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 77
利用异或函数化简的例子（二）
X 3 X 4
X 1 X 2
00 01 11 10
1
100
01
11
10
1
1
1
1
1 2 3 4 1 3
( 1,2,4,7,8,1 3 )
( ) ( )
fm
X X X X X X
先补成异或形式
（蓝色格子）
再利用运算法复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 78
多输出逻辑函数的化简
考虑公共蕴涵的使用
公共蕴涵也是越大越好
有时在寻找公共蕴涵过程中会有多种可能的方案出现，这时要根据实际情况作一定的取舍，部分地要依赖于人为的经验复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 79
寻找公共蕴涵的过程
单独化简。
观察在多个输出函数中的公共最小项。如果多输出函数比较复杂，这个过程也可以借助表格进行 。
将相邻的公共最小项合并成公共蕴涵（画公共卡诺圈），同时，将在单独化简的卡诺图中包含公共蕴涵的质蕴涵（卡诺圈）划去 。
检查覆盖情况：在卡诺图中观察是否存在未被圈入的最小项。如果没有任何其他最小项未被圈入（完成覆盖），则可以认为化简完成。否则要重新划分卡诺圈，
将未被包含的最小项圈入。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 80
第一章概要
逻辑代数是借助符号、利用数学方法研究逻辑推理和逻辑计算的一个数学分支。二值逻辑的逻辑变量只包含 0
和 1，它们表示两个对立的逻辑状态。
基本的逻辑运算有“与”、“或”、“非”三种，可以由此得到各种复合逻辑运算。逻辑代数运算借用了普通代数的某些运算符号，但是运算规律和其中的含义与代数运算迥然不同。为了进行逻辑运算，必须熟练掌握
1.2.1节的基本公式。另外，掌握 1.2.2节的辅助公式和
1.2.3节的基本定理，对于提高逻辑运算的速度和证明逻辑等式是极为有用的。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 81
逻辑函数有真值表、逻辑表达式、逻辑图和卡诺图四种表达形式，它们各具特点并且可以相互转换，可以根据使用的需要合理选用。
逻辑函数的化简是本章的重点。有代数法和图形法两种基本化简方法：公式法化简可以适用于任何场合，但是通常没有一定的规律可循，需要敏锐的观察力和一定的技巧。卡诺图化简法可以按照一定的步骤进行，但是只适用于变量数目较少的场合。在卡诺图化简过程中也有一些技巧性的手段，比较重要的有卡诺图运算法和影射变量卡诺图化简法。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 82
由于实际的逻辑系统为了获得最好的性能，可以由各种不同类型的逻辑电路构成，所以逻辑化简的目标形式可以是多种多样的，我们在本章讨论了几种常见的形式。可以通过一定的方法得到需要的逻辑函数形式：
包括在卡诺图化简后利用反演定理转换以及直接进行卡诺图运算化简等。
随着计算机辅助设计软件的发展，利用计算机软件进行逻辑化简已经越来越成熟。计算机化简的基本手段是表格法和代数法。
复旦大学电子工程系 陈光梦第 1章结束
2009-7-20 模拟电子学基础 2
数字逻辑与数字电路的历史
逻辑代数的历史
1849年，爱尔兰数学家乔治 〃 布尔 (George Boole)创立布尔代数。
20世纪 30年代，在贝尔实验室工作的香农 (Claude
Shannon)继承了布尔的工作并加以 发展和应用。
随着电子技术和计算机技术的发展，布尔代数在数字逻辑电路的分析和设计中得到了广泛的应用，统称为逻辑代数。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 3
集成电路的历史
1947年晶体管发明引起了电子学的一次革命。晶体管由巴丁 (John Bardeen),布雷登 (Wailter Houser Brattain)和肖克莱 (William Schokley)共同发明，该发明促成了计算机、通信等方面的飞速发展。鉴于它的重要价值，这些人共同获得了 1956年的诺贝尔物理学奖。
1958年，德克萨斯仪器公司的基尔白 (Clair Kilby)、仙童半导体公司的诺依斯 (Robert Noyce)等人研究实现了集成电路。以后集成度越来越高，出现了超大规模集成电路，
这是电子学的又一次革命，也是近代科学技术发展的新的标志。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 4
集成电路的分类与数字集成电路的特点
集成电路分类
模拟集成电路，处理的信号是连续的（模拟信号）
数字集成电路，处理的信号是离散的（数字信号）
数字集成电路分类
逻辑集成电路、存储器、各类 ASIC
数字集成电路特点
信息表示形式统一、便于计算机处理
可靠性高
制造工艺成熟、可以大规模集成复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 5
数字集成电路的发展
集成度
SSI（ 1-10门，逻辑门电路）
MSI（ 10-100门，计数器、移位寄存器器 ）
LSI（ 100-1000门，小型存储器,8位算术逻辑单元）
VLSI（ 1000-100万门，大型存储器、微处理器 ）
ULSI（ 超过 100万门，可编程逻辑器件、多功能集成电路）
摩尔定律
集成度每 18个月翻一番复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 6
本课程的内容
数字逻辑的基本理论：逻辑代数
无记忆的逻辑电路：组合逻辑电路
有记忆的逻辑电路：触发器及时序逻辑电路（同步和异步）
可编程逻辑器件和数字系统：软件实验、后续课程学习复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 7
教科书与参考书教科书：陈光梦,数字逻辑基础,复旦大学出版社参考书：
陈光梦等，数字逻辑基础学习指导与教学参考，复旦大学出版社
阎石，数字电子技术基础，高教出版社
Victor P,Nelson etc,Digital Logic Circuit Analysis and Design，清华大学出版社
John M,Yarbrough，数字逻辑应用与设计，机械工业出版社
刘宝琴，数字电路与系统，清华大学出版社
唐竞新，数字电子技术基础解题指南，清华大学出版社
曾繁泰等,VHDL程序设计，清华大学出版社复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 8
与教师的联系
虚拟校园,http://vcampus.fudan.edu.cn
电子邮件,gmchen@fudan.edu.cn
电话,65643789
复旦大学电子工程系 陈光梦第 1章逻辑代数基础复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 10
本章要求
掌握逻辑代数的基本公式和基本定理
掌握逻辑函数的化简方法复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 11
1.1 逻辑代数概述
二值逻辑：逻辑关系中的条件和结论只取对立的两个值，例如是和非、对和错、真和假等等。
在逻辑代数中，通常用,1”代表“真”，用,0”代表
“假”。
二值逻辑的,1”与,0”是逻辑概念，仅代表真与假，没有数量大小。
在数字逻辑中，有时也用,1”与,0”表示二进制数。这仅仅是一种代码，实际的运算规律还是依照逻辑运算进行。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 12
常用二 － 十进制代码十进制码 二进制码（ 8421码） 余三码 余三循环码 移位码 5211码 5421码
0 0000 0011 0010 00000 0000 0000
1 0001 0100 0110 00001 0001 0001
2 0010 0101 0111 00011 0100 0010
3 0011 0110 0101 00111 0101 0011
4 0100 0111 0100 01111 0111 0100
5 0101 1000 1100 11111 1000 1000
6 0110 1001 1101 11110 1001 1001
7 0111 1010 1111 11100 1100 1010
8 1000 1011 1110 11000 1101 1011
9 1001 1100 1010 10000 1111 1100
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 13
逻辑函数
用一个数学表达式来描述一个逻辑关系问题
逻辑条件 → 输入变量 （ 自变量 ）
逻辑结论 → 输出变量 （ 因变量 ）
),( BAfY?
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 14
逻辑函数的表示方法
真值表
逻辑函数
逻辑图
卡诺图
硬件描述语言（ HDL）
以上 5种表示方法可以相互转换，各有特定用途复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 15
真值表
A B Y
0 0 0
0 1 0
1 0 0
1 1 1
A B Y
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 16
逻辑函数：基本逻辑运算
与 Y = A · B
或 Y = A + B
非 Y = A
A A
A + B
A · B
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 17
“与” 运算
A B Y = A·B
0 0 0
0 1 0
1 0 0
1 1 1
A B Y
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 18
“或” 运算
A B Y = A＋ B
0 0 0
0 1 1
1 0 1
1 1 1
A
B
Y
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 19
“非”运算
A Y
0 1
1 0
AY =
A Y
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 20
反函数
两个逻辑函数互为反函数，是指两个逻辑函数对于输入变量的任意取值，其输出逻辑值都 相反 。下面真值表中 F 和 G 互为反函数。
A B F(A,B) G(A,B)
0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 21
复合逻辑运算
1,与非
2,或非
3,异或
4,同或
ABY?
BAY
Y A B A B A B
Y = A⊙ B BABA
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 22
复合逻辑运算的真值表
AB AB? AB?A B A⊙ B
0 0 1 1 0 1
0 1 1 0 1 0
1 0 1 0 1 0
1 1 0 0 0 1
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 23
逻辑图：基本逻辑单元
& 1 1
逻辑与 逻辑或 逻辑非
& 1 =1
与非 或非 异或
=
同或复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 24
逻辑图符号标注规定（ GB4728.12-1996）
所有逻辑符号都由方框（或方框的组合）和标注在方框内的总限定符号组成
&
总限定符号
&?1 =1 = 外部逻辑状态逻辑约定小圈表示逻辑非也可采用极性指示符内部逻辑状态复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 25
组合形式的逻辑图
&
=1
=1
&=1
一般表示法 组合表示法
A
B
C
A
B
C
Y Y
)()( CBBAY
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 26
国外逻辑图符号对照与门或门非门美、日常用符号国标符号GB4728.12-1996
&
1
1
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 27
异或门或非门与非门同或门
&
>1
=1
=
美、日常用符号国标符号GB4728.12-1996
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 28
1.2 逻辑代数的基本定理一,变量与常量的运算 (0-1律 )
A · 1 = A A + 0 = A
A · 0 = 0 A + 1 = 1
二、等幂律 A · A = A A+A = A
三、互补律 A · = 0 A+ = 1
四、自反律 = AA
AA
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 29
五、交换律
AB = BA A+B = B+A
六、结合律
A(BC) = (AB)C A+(B+C) = (A+B)+C
七、分配律
A(B+C) = AB+AC A+BC = (A+B)(A+C)
八、反演律（ De Morgan定理 ）
BABABAAB
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 30
代入定理在任何一个逻辑等式中，若将其中一个 逻辑变量全部 用另一个 逻辑函数 代替，则等式仍然成立。
例,若 Y=AC + BC，
C = P + Q
则 Y = A (P + Q) + B (P + Q)
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 31
反演定理对于任何一个逻辑函数式，将其中的,
所有逻辑符号,+,,,〃,交换 ;
所有逻辑常量,1,,,0,交换 ;
所有逻辑变量取反 ;
不改变原来的运算顺序。
得到的逻辑函数是原来逻辑函数的反函数。
例：
1))((
0
DCBAY
DCBAY
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 32
对偶定理对偶关系,逻辑符号,+,和,〃,
逻辑常量,1,和,0,
对偶式,所有逻辑符号,+,,〃,交换所有逻辑常量,1,,0,交换若两个函数相等，则由他们的对偶式形成的两个函数也相等。
例：若则
1))((
0)(
DCCACAD
DCCACDA
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 33
注意点
反演定理：描述原函数和反函数的关系（两个函数之间的关系）
对偶定理：描述原函数构成的逻辑等式和对偶函数构成的逻辑等式的关系（两个命题之间的关系）
在一般情况下，一个逻辑函数的反函数和对偶函数是不同的复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 34
常用逻辑恒等式
,( )
,( )
,
,( ) ( )
A A B A A A B A
A A B A B A A B A B
A A B A B A A B A B
A B A B B A B A B B
一,吸 收 律复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 35
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( )
A B A C B C A B A C
A B A C B C A B A C
A B A C B CD A B A C
A B A C B C D A B A C
二,冗 余 律复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 36
1.3 逻辑函数的化简与形式转换目标函数形式（原因：实际电路的需要）
与－或形式
或－与形式
与非－与非形式
或非－或非形式
与或非形式
混合形式复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 37
目标函数的要求：
逻辑电路的数量最少（面积约束）
逻辑电路的级数最少（速度约束）
输入端的数量最少（混合约束）
电路稳定可靠 （避免竞争－冒险）
具体问题具体分析，没有一成不变的规定复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 38
代数法化简逻辑函数
公式法化简可以适用于任何场合，但是通常没有一定的规律可循，需要敏锐的观察力和一定的技巧。
最常用的化简手段是吸收律、冗余律和反演律。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 39
代数法化简的例子
()
Y A B C A B C A B
A B A B A
Y A B C A B C A B
A B A B
B
例 一,化 简 函 数解,利 用,将 原 式 化 简,
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 40
()
()
Y A B A CD B CD
A B A A
Y A B A CD B CD
A B A B CD
A B A B CD
AB
AB
例 二,化 简 函 数解,利 用 反 演 律 和,将 原 式 化 简复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 41
1
( ) ( )
( ) ( ) ( )
Y A B B C B C A B
AA
Y A B B C A A B C A B C C
A B B C A B C A B C A B C A B C
A B A B C B C A B C A B C A B C
A B B C A C
例 三,化 简 函 数解,利 用,在 原 式 中 添 加 一 些 项,然 后 化 简复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 42
0
()
()
Y A B C A B C A B
AA
Y A B A B A B C A B C A B
A B A B C A B C A B
A B A B C A B C A B A B C
例 四,化 简 函 数解,利 用,在 原 式 中 添 加 一 些 项,然 后 化 简复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 43
逻辑函数形式转换的例子
* ( ) ( )
( * ) *
( ) ( ) ( ) ( )
Y A B C D
Y A B C D
A C B C A D B D
YY
A C B C A D B D
以 逻 辑 函 数 ＋ 为 例,
例 一,将,与 － 或,函 数 化 为,或 － 与,式利 用 对 偶 定 理 实 现 之,
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 44
Y A B C D
Y A B C D
A B C D
例 二,将,与 － 或,函 数 ＋
转 化 为,与 非 － 与 非,式利 用 两 次 求 反,将 原 式 转 换,
＋
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 45
( * ) *
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
Y A B CD
YY
A C B C A D B D
A C B C A D B D
A C B C A D B D
例 三,将,与 － 或,函 数 ＋
化 为,或 非 － 或 非,式解,先 利 用 对 偶 定 理 变 成,或 与,式,再 两 次 求 反复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 46
( ) ( )
Y A B CD
Y A B CD
A B CD
A B C D
A C B C A D B D
例 四,将,与 － 或,函 数 ＋
化 为,与 或 非,式解,利 用 两 次 求 反,将 原 式 转 换
＋
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 47
逻辑函数的卡诺图表示和卡诺图化简法特点：
图形化简法
标准的表达方式
规律的化简过程
变量数目有限制（最多 5～ 6个）
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 48
最小项在 n个逻辑变量的逻辑函数中，若 m为包含 n个因子的乘积项（逻辑与），且其中每个逻辑变量都以原变量或反变量的形式出现一次并仅仅出现一次，则称 m为这 n个变量的最小项。
例：
记为 m2
记为 m5
记为 m7abc
cba
cba
abccbacbaabcf)(
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 49
最大项在 n个逻辑变量的逻辑函数中，若 M为包含 n个因子的和项（逻辑或），且其中每个逻辑变量都以原变量或反变量的形式出现一次并仅仅出现一次，则称 M为这 n个变量的最大项。
例：
记为 M2
记为 M5
记为 M7cba
cba
cba
cbacbacbaabcf
))()(()(
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 50
最小项与最大项的比较以 3变量函数为例
CBAMCBAm
CBAMCBAm
CBAMCBAm
CBAMCBAm
CBAMCBAm
CBAMCBAm
CBAMCBAm
CBAMCBAm
77
66
55
44
33
22
11
00
最大项：最小项：
最大项：最小项：
最大项：最小项：
最大项：最小项：
最大项：最小项：
最大项：最小项：
最大项：最小项：
最大项：最小项：
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 51
最小项和最大项的性质对于一个具有 n 个变量的逻辑问题，在输入变量的任意一种取值情况下，总有：
一、必有且仅有一个最小项的逻辑值为 1；必有且仅有一个最大项的逻辑值为 0。
二、任意 2个 不同的最小项之积为 0；任意两个不同的最大项之和为 1。
1,0 jiji MMmm
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 52
三、全体最小项之和为 1；全体最大项之积为 0。
四、下标相同的最大项和最小项互补。
12
0
12
0
0,1
nn
i
i
i
i Mm
ii Mm?
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 53
逻辑函数的两种标准表达式
最小项之和形式，简称为积之和 (SOP)形式
最大项之积形式，简称为和之积 (POS)形式
10),...,,(
12
0
21 ormxxxf i
i
iin
n
＝，
＝
10)(),...,,(
12
0
21 orMxxxf i
i
iin
n
＝，
＝
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 54
标准表达式的关系性质 1、一个逻辑函数的两种标准逻辑表达式之间，
存在以下关系：
若 则性质 2、一个逻辑函数与其反函数的逻辑表达式之间，存在以下关系：
若 则
imF jMF
imF iMF
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 55
将逻辑函数化成标准形式
要求按积之和形式展开函数，可以将 非最小项的积项 乘以形如 的项，其中 A 是那个非最小项的积项中缺少的输入变量，然后展开，最后合并相同的最小项。
要求按和之积形式展开函数，可以将 非最大项的和项 加上形如 的项，其中 A 是那个非最大项的和项中缺少的输入变量，然后展开，最后合并相同的最大项。
AA?
AA?
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 56
卡诺图
每个方格代表一个最小项或者最大项。
变量排列按照相邻规则进行，即在卡诺图中相邻的方格在逻辑上也相邻。（相邻的意义：两个最小项或最大项之间只有一个变量发生变化）
BC
A 00 01 11 10
0
1
0 1 3 2
64 5 7
B
A 0 1
0
1
0 1
2 3
CD
AB
00 01 11 10
0 1 3 2
64 5 7
00
01
11
10
12 13 15 14
108 9 11
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 57
卡诺图的填法
X 3 X 4
X 1 X 2
00 01 11 10
1 0 0 0
01 1 0
00
01
11
10
0 1 1 1
01 1 1
)12,10,7,6,3,2,1(
)15,14,13,11,9,8,5,4,0(),,,( 4321
M
mxxxxf
最小项填 1
最大项填 0
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 58
卡诺图化简法根据相邻的方格在逻辑上也相邻的原理，只要相邻的方格满足以下条件：
一、逻辑值相同；
二、小方格数为 2n 个。
就可以将相邻的方格合并为一个 卡诺圈 。
卡诺圈越大，可以消去的变量越多，最后得到的逻辑函数越简单。
若卡诺圈包含的小方格数为 2n 个，而这个逻辑函数具有 m 个变量，则这个卡诺圈对应的项中包含的变量数目为 m–n 个。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 59
卡诺图的圈法（ SOP）
圈,1”
包含 2n个方格尽可能大不遗漏
X 3 X 4
X 1 X 2
00 01 11 10
1 0 0 0
01 1 0
00
01
11
10
0 1 1 1
01 1 1
X 1 X 2 X 3
X 1 X 4
X 2 X 3 X 4
X 1 X 2 X 3
41321321432 xxxxxxxxxxxf
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 60
卡诺图的圈法（ POS）
圈,0”
包含 2n个方格尽可能大不遗漏
X 3 X 4
X 1 X 2
00 01 11 10
1 0 0 0
01 1 0
00
01
11
10
0 1 1 1
01 1 1
X 2 + X 3 + X 4
X 1 + X 3
X 1 + X 2 + X 4
X 1 + X 2 + X 3 + X 4
))()()(( 314324321421 xxxxxxxxxxxxf
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 61
卡诺图化简法的要点
将逻辑函数化为标准形式（或真值表）
填卡诺图
圈卡诺圈（满足 2n个方格要求、尽可能大、不遗漏）
根据卡诺圈写出化简后的逻辑函数
若有必要，运用反演律对所得结果进行变换复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 62
卡诺图化简的例（一）
12(,,,) (,,,)
( 3,4,6,1 1,1 2,1 4 ) ( 0,1,2,5,8,1 0,1 3 )
F f a b c d F f a b c d
mm
0
01
1001
10
00 01 11 10
00
10
11
01
ab
0
0
01
1
0
0
cd
1
10
0010
01
00 01 11 10
00
10
11
01
ab
1
0
10
0
0
1
cd
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 63
卡诺图化简的例（二）
34(,,,) (,,,)
(0,1,2,5,8,1 0,1 3 ) ( 3,5,7,9,1 1)
F f a b c d F f a b c d
MM
0
01
1101
10
00 01 11 10
00
10
11
01
ab
0
1
01
1
1
0
cd
1
11
1001
01
00 01 11 10
00
10
11
01
ab
1
1
10
1
0
1
cd
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 64
卡诺图化简法的一些术语
蕴涵,逻辑函数的,与或,表达式中的各项
质蕴涵,不能再与其他蕴涵合并的蕴涵
必要质蕴涵,包含一个或多个唯一的最小项的质蕴涵
覆盖,包含了逻辑函数中所有最小项的一些蕴涵之,或,
非冗余覆盖,其中每一个蕴涵都是必不可少的覆盖
最小覆盖,包含蕴涵个数最少，每个蕴涵中包含的最小项又较少的非冗余覆盖复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 65
最小覆盖的不惟一性
X 3 X 4
X 1 X 2
00 01 11 10
1 0 0 1
01 1 1
00
01
11
10
0 1 1 0
10 0 1
一个逻辑函数，其最小覆盖总是由必要质蕴涵和部分质蕴涵组成，所以它的最小覆盖可能不是惟一的，即它的最简逻辑表达式可能不是惟一的。
绿色：必要质蕴涵红色和白色：质蕴涵最小覆盖：
绿色＋红色或：绿色＋白色复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 66
利用卡诺图运算来进行逻辑化简逻辑函数 → 卡诺图逻辑函数的运算 → 卡诺图的运算卡诺图的运算 → 对应的方格进行运算证明（以,与,运算为例）：
1 1 2 2
1 2 1 2
1 2 1 2 1 2
,,
( ) ( ) ( )
i i i i
i i i i
i i i i i i j i i i
i i j i
f m f m
f f m m
m m m m
设 则 有证明的最后一步运用了最小项的性质 2
思考题,试证明“或”、“非”运算亦符合上述规则复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 67
利用卡诺图运算来进行逻辑化简的例
CD
00 01 11 10
1 1 1 1
11 1 1
00
01
11
10
1 1 1
11 1
AB
CD
00 01 11 10
11 1 1
00
01
11
10
1 1 1 1
AB
CD
00 01 11 10
11 1 1
00
01
11
10
1 1 1
AB
Y B C DA
·=
·=
)14,13,12,7,6,5,4(),,,( mDCBAY
BADBCBY
C D ABY
常规化简运算化简复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 68
CD
00 01 11 10
11
00
01
11
10
1 1 1
1 1
AB
CD
00 01 11 10
1
1
00
01
11
10
1 1 1 1
1
AB
CD
00 01 11 10
1
00
01
11
10
1 1 1
1
AB
Y A B +C D A D+BC
·=
·=
)15,14,13,11,7(),,,( mDCBAY
A C DB C DA B CA B DY
)()( BCADCDABY
常规化简结果为 3,4 输入端，共 16输入端运算化简结果为 2 输入端，共 14输入端复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 69
卡诺图运算的一些有关规律
0重心,0号方格（即全部变量为 0的方格）
1重心,2n号方格（即全部变量为 1的方格）
包含 0重心但不包含 1重心的质蕴涵，其表达式全部用反变量标注
包含 1重心但不包含 0重心的质蕴涵，其表达式全部用原变量标注
既不包含 0重心也不包含 1重心的质蕴涵，其表达式中一定既有原变量又有反变量
目标函数是与非形式并要求全部用原变量表达时，围绕 1重心进行。其中卡诺圈圈 1，阻塞圈圈 0
目标函数是或非形式并要求全部用原变量表达时，围绕 0重心进行，其中卡诺圈圈 0，阻塞圈圈 1
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 70
不完全确定的逻辑函数的化简不完全确定的逻辑函数：
由 n 个逻辑变量构成的逻辑函数中，有效的逻辑状态数小于 2n个。那些无效的状态或者是不可能出现，或者无意义。
这些无效的状态被称为任意项，或称为无关项、约束项、禁止项，等等复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 71
任意项的处理任意项的值既可为 1也可为 0
带有任意项的逻辑函数在化简时既可以将任意项圈入卡诺圈，也可以不圈入卡诺圈适当地将一些任意项圈入卡诺圈，可以使化简的结果得到极大的简化
X 3 X 4
X 1 X 2
00 01 11 10
1 1
00
01
11
10
d 1 1
d 1 d
d
黄色：不考虑任意项红色：考虑任意项复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 72
0
10
0110
01
00 0 1 1 1 1 0
00
10
11
01
uv
d
1
dd
d
1
0
wx
56(,,,) (,,,)
( 2,3,4,5,1 3,1 5 ) ( 1,5,7,9,1 3,1 5 )
( 8,9,1 0,1 1 ) ( 8,1 0,1 1,1 4 )
F f a b c d F f u v w x
mm
dd
0
10
0011
10
00 01 11 10
00
10
11
01
ab
d
1
dd
0
d
1
cd
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 73
注意点任意项的表现形式除了直接用最小项形式表示外，
还经常用逻辑表达式表示，称为约束方程对于用约束方程给出的逻辑问题，一般要将约束条件改写成用最小项表示的任意项形式，才能用卡诺图进行化简例如,A =1,B =1这种输入状态不可能出现，可记为 AB=0。在卡诺图中就是对应 AB=11的最小项为任意项复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 74
使用异或函数的卡诺图化简异或运算的性质,
ABBA
CBACBACBA )()(
AAAA 1,0
1,0 AAAA
BABABA
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 75
异或（同或）函数的卡诺图
,棋盘格,特征
异或 函数的棋盘格特征,0号方格等于 0
同或 函数的棋盘格特征,0号方格等于 1
X 3 X 4
X 1 X 2
00 01 11 10
1
100
01
11
10
1
1
1
1 1
1
X 3 X 4
X 1 X 2
00 01 11 10
1
100
01
11
10
1
1
1
1 1
1
同或函数异或函数复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 76
利用异或函数化简的例子（一）
1
00
0010
00
00 01 11 10
00
10
11
01
ab
0
1
10
0
0
0
cd
))(( dbcaP dcbW
0
01
0101
01
00 01 11 10
00
10
11
01
ab
0
1
10
0
1
1
cd
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 77
利用异或函数化简的例子（二）
X 3 X 4
X 1 X 2
00 01 11 10
1
100
01
11
10
1
1
1
1
1 2 3 4 1 3
( 1,2,4,7,8,1 3 )
( ) ( )
fm
X X X X X X
先补成异或形式
（蓝色格子）
再利用运算法复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 78
多输出逻辑函数的化简
考虑公共蕴涵的使用
公共蕴涵也是越大越好
有时在寻找公共蕴涵过程中会有多种可能的方案出现，这时要根据实际情况作一定的取舍，部分地要依赖于人为的经验复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 79
寻找公共蕴涵的过程
单独化简。
观察在多个输出函数中的公共最小项。如果多输出函数比较复杂，这个过程也可以借助表格进行 。
将相邻的公共最小项合并成公共蕴涵（画公共卡诺圈），同时，将在单独化简的卡诺图中包含公共蕴涵的质蕴涵（卡诺圈）划去 。
检查覆盖情况：在卡诺图中观察是否存在未被圈入的最小项。如果没有任何其他最小项未被圈入（完成覆盖），则可以认为化简完成。否则要重新划分卡诺圈，
将未被包含的最小项圈入。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 80
第一章概要
逻辑代数是借助符号、利用数学方法研究逻辑推理和逻辑计算的一个数学分支。二值逻辑的逻辑变量只包含 0
和 1，它们表示两个对立的逻辑状态。
基本的逻辑运算有“与”、“或”、“非”三种，可以由此得到各种复合逻辑运算。逻辑代数运算借用了普通代数的某些运算符号，但是运算规律和其中的含义与代数运算迥然不同。为了进行逻辑运算，必须熟练掌握
1.2.1节的基本公式。另外，掌握 1.2.2节的辅助公式和
1.2.3节的基本定理，对于提高逻辑运算的速度和证明逻辑等式是极为有用的。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 81
逻辑函数有真值表、逻辑表达式、逻辑图和卡诺图四种表达形式，它们各具特点并且可以相互转换，可以根据使用的需要合理选用。
逻辑函数的化简是本章的重点。有代数法和图形法两种基本化简方法：公式法化简可以适用于任何场合，但是通常没有一定的规律可循，需要敏锐的观察力和一定的技巧。卡诺图化简法可以按照一定的步骤进行，但是只适用于变量数目较少的场合。在卡诺图化简过程中也有一些技巧性的手段，比较重要的有卡诺图运算法和影射变量卡诺图化简法。
复旦大学电子工程系 陈光梦
2009-7-20 模拟电子学基础 82
由于实际的逻辑系统为了获得最好的性能，可以由各种不同类型的逻辑电路构成，所以逻辑化简的目标形式可以是多种多样的，我们在本章讨论了几种常见的形式。可以通过一定的方法得到需要的逻辑函数形式：
包括在卡诺图化简后利用反演定理转换以及直接进行卡诺图运算化简等。
随着计算机辅助设计软件的发展，利用计算机软件进行逻辑化简已经越来越成熟。计算机化简的基本手段是表格法和代数法。
复旦大学电子工程系 陈光梦第 1章结束
