Email: jiangjie@bjut.edu.cn
第二章 逻辑代数基础
◆◆ 证明等式(真值表、公式、卡诺图)
◆◆ 逻辑函数的化简(最简与或式、最简或与式)
◆◆ 逻辑函数的最小项之和形式
最大项之积形式
P61 2.10, 2.11
公式法
卡诺图法(包含无关项的卡诺图化简)
P62 2.15, 2.18, 2.19, 例
:基本公式、常用公式
第二章 逻辑代数基础
◆◆ 逻辑函数不同形式间的转换
与非-与非
或非-或非
与或非
P61 2.12, 2.13, 例题
◆◆ 利用卡诺图进行逻辑运算
P64 2.25
◆◆ 根据波形图,列逻辑函数式
P60 2.8, 2.9
2.1 逻辑代数
基本公式和常用公式
1、基本公式
(1)交换律 A • B = B • A ;A+B = B+A
A • ( B • C ) = ( A • B ) • C ; A+( B +C ) = ( A+B ) + C (2)结合律
(3)分配律 A • ( B+C ) = A • B+A • C
A+BC = ( A+B ) • ( A+C)
(4) 0、1律 A • 1 = A; A+1 = 1
A • 0 = 0; A+0 = A
(5)互补律 A • A = 0 ; A+A = 1
(6)重叠律 A • A = A ; A+A = A ;
(7)否定律 A=A
(8)反演律 A • B = A + B ; A + B = A • B
2.1 逻辑代数
2、常用公式
(1)A+AB = A
(2)AB+AB = A
(3)A+AB = A+B
(4)AB+AC+BC = AB+AC
基本公式、常用公式,
可由真值表证明。
例、用真值表法证明 A+B = A • B
01 1
01 0
00 1
10 0
A+BA B
0
0
0
1
A • B
列出输入变
量的所有取
值组合
2.1 逻辑代数
三个重要定理
1、代入定理
在任何一个逻辑恒等式中,
若将等式两边都出现的某一个变量A,同时
代之以一个逻辑函数F,则等式仍成立。
主要用途:
扩展公式的应用范围
用于证明恒等式
2.1 逻辑代数
2、反演定理(德 • 摩根定理)
对任意一个逻辑函数表达式F,若将F中所有的:
① “ • ” ¨ “+ ”
② “+ ” ¨ “ • ”
③ “ 1 ” ¨ “ 0 ”
④ “ 0 ” ¨ “ 1 ”
⑤ 原变量 ¨ 反变量
⑥ 反变量 ¨ 原变量
并保持原来的运算优
先级,则所得到的表
达式为F的反函数F。
主要用途:
直接求任何一个逻辑函数的反函数
2.1 逻辑代数
例1、已知 F = A • B+C,求 F。
解: 方法 1
根据反演定理,可得: F = A+B • C( )
保持运算优
先级不变
方法 2
F = A • B+C = AB • C
=( A+B )• C
例2、已知 F = A+ B+C • D+E ,求 F 。
解: F = A • B • C+ D • E( )
对 偶 定 理
对任意一个逻辑函数表达式F,若将F中所有的:
① “ • ” ¨ “+ ”
② “+ ” ¨ “ • ”
③ “ 1 ” ¨ “ 0 ”
④ “ 0 ” ¨ “ 1 ”
并保持原来的运算优先
级,则所得到的表达式
为F的对偶式FD。
若两个函数式相等,则它们的对偶式也相等。
F=G FD = GD
2.1 逻辑代数
2.1 逻辑代数
例、某公司有A、B、C 三个股东,分别占公司50%、30%
和 20% 的股份。一个议案要获得通过,必须有超过 50%股
份的股东投赞成票。
解:
试列出该公司表决电路的真值表 和逻辑函数式。
1:股东赞成
0:股东反对
A、B、C
1:议案通过
0:议案未通过F
F 股份A B C
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
F 股份A B C
1001 1 1
801 1 0
701 0 1
501 0 0
500 1 1
300 1 0
200 0 1
00 0 0
F 股份A B C
1001 1 1
801 1 0
701 0 1
0501 0 0
0500 1 1
0300 1 0
0 200 0 1
000 0 0
F 股份A B C
11001 1 1
1801 1 0
1701 0 1
0501 0 0
0500 1 1
0300 1 0
0 200 0 1
000 0 0
F 股份A B C
(1)真值表
(2)逻辑函数式
A B C
A B C
A B C
>
>
>
F= ABC + ABC + ABC
逻辑函数的表示方法
真值表 逻辑函数式
◆◆ 找出使逻辑函数 F=1 的输入变量
的取值组合;
◆◆ 每组输入变量的取值组合对应一个
乘积项;
◆◆ 将各乘积项相加,即可求得F的逻辑
函数式。
?
2.2 逻辑函数的简化
2.1 逻辑代数
逻辑函数的两种
形式
1、最小项表达式
(1)什么是最小项?
① 乘积项
② 包含了全部输入变量
③ 每个输入变量都以原变量或反变量的形式在
乘积项中出现、且仅出现一次
(2)什么是最小项表达式?
由最小项相加构成的表达式,称为最小项表达式、
标准与或式、标准积之和式。
2.1 逻辑代数
例1、求函数 F (A, B, C) = AB+BC+ABC 的最小项表达式
解: 〖方法〗
利用基本公式 A+A=1,将乘积项中所缺的变量逐步
补齐,可把任意一个逻辑函数展开成最小项表达式。
F (A, B, C) = AB+BC+ABC
= AB(C+C)+ (A+A)BC+ABC
= ABC+ABC+ABC+ABC+ABC = ABC+ABC+ABC+ABC+ABC
= ABC+ABC+ABC+ABC
= m3 + m4 + m5 + m7
= ∑ m ( 3, 4, 5, 7 )
2.1 逻辑代数
2、最大项表达式
(1)什么是最大项?
(2)什么是最大项表达式?
① 和项
② 包含了全部输入变量
③ 每个输入变量都以原变量或反变量的形式在和项
中出现、且仅出现一次
由最大项相乘构成的表达式,称为最大项表达式、
标准或与式、标准和之积式。
2.1 逻辑代数
例2、求函数 F (A, B, C) = A(B+C)的最大项表达式
解:
F(A,B,C) = ( A + BB + CC ) ( AA + B+C )
( A +B+C ) ( A +B+C )= ( A + BB + C ) ( A + BB + C )
= ( A+B +C ) ( A +B +C )
( A +B+C ) ( A +B+C )
( A+B +C ) ( A +B +C )= ( A+B +C ) ( A +B +C )
( A +B+C ) ( A +B+C )
( A+B +C ) ( A +B +C )
= ( A+B +C ) ( A +B +C ) ( A +B+C )( A+B +C ) ( A +B +C )
= M0 • M1 • M2 • M3 • M6
= ΠM ( 0, 1, 2, 3, 6 )
2.1 逻辑代数
3、最小项表达式与最大项表达式间的关系
已知逻辑函数为Y = ∑ mi 时,定能将Y化为编号
为i以外的那些最大项的乘积。
例3、将例1中 F (A, B, C) = AB+BC+ABC 化为最大项表达式
解: 由例1, F = ∑ m ( 3, 4, 5, 7 )
= ∏ M( 0, 1, 2, 6 )
2.2 逻辑函数的简化
例、化简逻辑函数 Y= AB+BC+BC+AB
Y= AB+BC+BC+AB
= AB+BC+BC(A+A)+AB (C+C)
= AB+BC+ABC+ABC+ABC+ABC= AB+BC+ABC+ABC+ABC+ABC
= AB+BC+ABC+ABC
= AB+BC+ABC+ABC
= AB+BC+AC
A、不受任何条件限制, 通用性好
B、没有固定步骤,需要经验技巧
公式化简法
2.2 逻辑函数的简化
(1)用卡诺图表示逻辑函数
逻辑函数包含哪些最小项,与其对应的位置上
填 1,其余位置填 0,就得到表示该逻辑函数
的卡诺图。
例、用卡诺图表示逻辑函
数 F( A, B, C )=Σ(1, 3)
00 01 11 10
AB
C
0
1 1
00 01 11 10
AB
C
0
1 11
00 01 11 10
AB
C
0
1 0011
0000
00 01 11 10
AB
C
0
1
逻辑函数式 卡诺图?
思考: ?卡诺图 逻辑函数式
?
真值表 卡诺图
卡诺图化简法
2.2 逻辑函数的简化
(2)化简方法
① 逻辑相邻的2个最小项为1,消去1个变量
11
111
00 01 11 10
AB
C
0
1
AB
B C
BC
11
111
00 01 11 10
AB
C
0
1
ABC+ABC+ABC = AB+ABC =B(A+AC)
= B( A+C) = AB+BC
11
11
11
11
AB
CD 00 01 11 10
00
01
11
10
BD
BD
11
11
11
11
AB
CD 00 01 11 10
00
01
11
10
BD
BD
② 逻辑相邻的4个最小项为1,消去2个变量
2.2 逻辑函数的简化
111
1111
00 01 11 10
AB
C
0
1 A
B
1111
00 01 11 10
AB
C
0
1
C
2.2 逻辑函数的简化
③ 逻辑相邻的8个最小项为1,消去3个变量
1111
11
11
1111
AB
CD 00 01 11 10
00
01
11
10
11
1111
1111
11
AB
CD 00 01 11 10
00
01
11
10
B
D
D
B
2.2 逻辑函数的简化
(3)化简步骤
◆◆ 画出逻辑函数的卡诺图
◆◆ 将逻辑相邻的1格圈圈,直到所有1格
均被覆盖
◆◆ 将每个圈用相应的乘积项表示
逻辑函数的最简与或式
◆◆ 将各乘积项相加
满足上述条件,圈的方案可能不同,化简结果
有时不唯一。
2.2 逻辑函数的简化
例1、求函数 F(A, B, C, D) = Σm (0, 3, 4, 6, 7, 9, 12, 14, 15 )
的最简与或式。
解:
CD
AB 00 01 11 10
00
01
11
10
AB
1
111
111
11
CD
00 01 11 10
00
01
11
10
BD
BC
A C D ACD
ABCD
F = BC + BD + ACD + AC D + AB CD
2.2 逻辑函数的简化
例2、求函数F(A, B, C, D) = Σm (1, 5, 6, 7, 11, 12, 13, 15 )
的最简与或式。
解:
AB
CD
00 01 11 10
00
01
11
10
AB
1
111
111
1
CD
00 01 11 10
00
01
11
10
BD 多余项!
F = ABC + ABC + ACD + ACD
2.2 逻辑函数的简化
例3、求函数F(A, B, C, D) = Σm ( 0, 2, 3, 5, 7, 8, 10, 11, 13 )
的最简或与式。
解:
AB
CD
00 01 11 10
00
01
11
10
AB
111
1
11
111
CD
00 01 11 10
00
01
11
10
AB
1101
0010
0110
1101
CD
00 01 11 10
00
01
11
10
B+D
A+B+C
B+C+D
F = ( B+D)(A+B+C)(B+C+D)
2.2 逻辑函数的简化
例4、求函数 F(A, B, C, D) = ΠM ( 0, 1, 2, 5, 7) 的
最简或与式。
解:
AB
CD
00 01 11 10
00
01
11
10
AB
00
000
CD
00 01 11 10
00
01
11
10
A+B+D
A+B+D
A+B+C
F = (A+B+C ) (A+B+D) ( A+B+D )
2.10 将下列函数化为最小项之和形式
(3) Y = A+B+CD
111
1111
111
111
AB
CD 00 01 11 10
00
01
11
10
练习
2.3 已知逻辑函数的真值表,写出函数式。
2.5 已知逻辑函数式,列出真值表。
2.11 将下列各式化为最大项之积的形式
(3) Y = ABC + BC + ABC
AB
C
0
1
00 01 11 10
11
1
AB
C
0
1
00 01 11 10
1001
0010
AB
C
0
1
00 01 11 10
A+B+C
A+B+C
A+B+CA+B+C
A+B+C
Y =(A+B+C)•(A+B+C)•(A+B+C)
•(A+B+C)•(A+B+C)
请充分利用卡诺图!
练习
Y = AB+BC+AC(1)
2.12 用与非门实现下列函数
= AB+BC+AC
= AB • BC • AC
(2) Y =( A+B)(A+B)C +BC
Y=ABC+BC(1)
2.13 用或非门实现下列函数
1000
0110
AB
C
0
1
00 01 11 10
A+C B+C
B+C
Y=(A+C)•(B+C)•(B+C)
=(A+C)•(B+C)•(B+C)
= A+C + B+C + B+C
用与或非门实现?用与非门、或非门、与或非门实现非门?
2.15 用公式法化简
(2) Y=ABC+A+B+C
(8) Y=A+B+C (A+B+C)(A+B+C)
2.23 用卡诺图法化简
(3)Y(A, B, C, D)=∑m(3, 5, 6, 7, 10)+ ∑d(0, 1, 2, 4, 8)
2.25 利用卡诺图之间的运算,将下列函数
化为最简与或式。
(3)Y=(A D +CD +CD)⊕(A C D +ABC+AD+CD)
解:
Y1=A D +CD +CD Y2= A C D +ABC+AD+CD
1010
1010
1011
1011
CD
AB 00 01 11 10
00
01
11
10
Y1
0101
1101
0110
0110
CD
AB 00 01 11 10
00
01
11
10
Y2
1010
1010
1011
1011
CD
AB 00 01 11 10
00
01
11
10
Y1
0101
1101
0110
0110
CD
AB 00 01 11 10
00
01
11
10
Y2
2.25 (续)
1111
0111
1101
1101
CD
AB 00 01 11 10
00
01
11
10
Y
AC
AB
C D AD
Y=AD+AB+AC+CD