第 2章 逻辑代数基础第 2章 逻辑代数基础
2.1逻辑代数的三种基本运算
2.2 逻辑代数的基本定律和规则
2.3 复合逻辑
2.4 逻辑函数的两种标准形式
2.5 逻辑函数的代数化简法
2.6 逻辑函数的卡诺图化简
2.7 非完全描述逻辑函数的化简第 2章 逻辑代数基础
**初步 门电路 GATE
实现基本逻辑运算和常用复合逻辑运算的电子电路与或非与 非或 非异或与或非与 门或 门非 门与 非 门或 非 门异或门与或非门第 2章 逻辑代数基础
**逻辑变量与两状态开关低电平高电平断开闭合高电平 3 V
低电平 0 V
二值逻辑,所有逻辑变量只有两种取值 (1 或 0)。
数字电路,
3V
Iu S
Ou
Iu S Ou
逻辑状态
1
0
0
S 可由 二极管,三极管 或 MOS 管实现通过电子开关 S 的两种状态 (开或关 )
获得高、低电平，用来表示 1 或 0。
1
第 2章 逻辑代数基础
**关于高、低电平与正、负逻辑负逻辑正逻辑
0V
5V
2.4V
0.8V
高电平和低电平是两个不同的可以截然区别开来的电压范围。
0
1
0V
5V
2.4V
0.8V1
0
第 2章 逻辑代数基础
2.1 逻辑代数的三种基本运算 代数 集代数
={{集合 },{定义在该集合上的运算集 }} 布尔代数 {有限集 }
逻辑代数 {二值集 }
2.1.1 逻辑变量与逻辑函数 ={B={0,1},{.,+,}}
逻辑是指事物因果之间所遵循的规律 。 为了避免用冗繁的文字来描述逻辑问题,逻辑代数采用逻辑变量和一套运算符组成逻辑函数表达式来描述事物的因果关系 。
逻辑代数中的变量称为逻辑变量,一般用大写字母 A、
B,C,…表示,逻辑变量的取值只有两种,即逻辑 0和逻辑 1。 0和 1称为逻辑常量 。 但必须指出,这里的逻辑 0和 1
本身并没有数值意义,它们并不代表数量的大小,而仅仅是作为一种符号,代表事物矛盾双方的两种状态 。
第 2章 逻辑代数基础逻辑函数与普通代数中的函数相似,它是随自变量的变化而变化的因变量 。 因此,如果用自变量和因变量分别表示某一事件发生的条件和结果,那么该事件的因果关系就可以用逻辑函数来描述 。
数字电路的输入,输出量一般用高,低电平来表示,高,低电平也可以用二值逻辑 1和 0来表示 。 同时数字电路的输出与输入之间的关系是一种因果关系,因此它可以用逻辑函数来描述,并称为逻辑电路 。 对于任何一个电路,若输入逻辑变量 A,B,C,…的取值确定后,其输出逻辑变量 F的值也被惟一地确定了,则可以称 F是 A,B,C,… 的逻辑函数,并记为
),,,( CBAfF
逻辑代数是研究逻辑函数的描述,性质,变换,化简的学科它是数字电路的数学基础第 2章 逻辑代数基础
2.1.2 三种基本运算
1,与运算 (逻辑乘 )
与运算 (逻辑乘 )表示这样一种逻辑关系：只有当决定一事件结果的所有条件同时具备时,结果才能发生 。 例如在图 2-1所示的串联开关电路中,只有在开关 A和 B都闭合的条件下,灯 F才亮,这种灯亮与开关闭合的关系就称为与逻辑 。
如果设开关 A,B闭合为 1,断开为 0,设灯 F亮为 1,灭为 0，
则 F与 A,B的与逻辑关系可以用表 2-1所示的真值表来描述,
所谓真值表,就是将自变量的各种可能的取值组合与其因变量的值一一列出来的表格形式 。
第 2章 逻辑代数基础图 2 -1 与逻辑实例
A
F
B
E
第 2章 逻辑代数基础表 2-1 与逻辑运算真值表
A B F
0 0
0 1
1 0
1 1
0
0
0
1
与逻辑可以用逻辑表达式表示为
F=A·B
第 2章 逻辑代数基础在逻辑代数中,将与逻辑称为与运算或逻辑乘 。 符号
,·”表示逻辑乘,在不致混淆的情况下,常省去符号,·”。
在有些文献中,也采用 ∧,∩及 &等符号来表示逻辑乘 。
实现与逻辑的单元电路称为与门,其逻辑符号如图 2-2
所示,其中图 (a)为我国常用的传统符号,图 (b)为国外流行的符号,图 (c)为国标符号 (见附录一 )。 图 2-3是一个 2 输入的二极管与门电路 。 图中输入端 A,B的电位可以取两种值：
高电位 +3V或低电位 0V。 设二极管为理想开关,并规定高电位为逻辑 1,低电位为逻辑 0,那么 F与 A,B之间逻辑关系的真值表与表 2-1相同,因而实现了 F=A·B的功能 。
第 2章 逻辑代数基础图 2-2 与门的逻辑符号 图 2-3 二极管与门
F
A
B
( a )
( b )
&
F
A
B
( c )
F
A
B
U
CC
( + 5V )
R
3,9 k
A
B
F
V
1
V
2
第 2章 逻辑代数基础
2,或运算 (逻辑加 ),决定某事件发生的条件之一成立则该事件就发生的逻辑,
图 2-4 或逻辑实例
F
A
B
E
第 2章 逻辑代数基础表 2-2 或逻辑运算真值表
A B F
0 0
0 1
1 0
1 1
0
1
1
1
或逻辑可以用逻辑表达式表示为
F=A+B
或逻辑也称为或运算或逻辑加 。 符号,+”表示逻辑加 。
有些文献中也采用 ∨,∪ 等符号来表示逻辑加 。
第 2章 逻辑代数基础实现或逻辑的单元电路称为或门,其逻辑符号如图 2-5
所示,其中图 (a)为我国常用的传统符号,图 (b)为国外流行的符号,图 (c)为国标符号 (见附录一 )。 图 2-6是一个 2 输入的二极管或门电路 。 图中输入端 A,B的电位可以取两种值,高电位 +3V或低电位 0 V。
,并规定高电位为逻辑 1,低电位为逻辑 0,则 F与 A,B之间逻辑关系的真值表与表 2-2相同,
因此实现了 F=A+B的功能 。
第 2章 逻辑代数基础图 2-5 或门的逻辑符号 图 2-6 二极管或门
＋
F
A
B
( a )
( b )
F
A
B
( c )
≥1
F
A
B
R
3,9 k
B
A
F
V
2
V
1
第 2章 逻辑代数基础
3,非运算 (逻辑反 ) 逆反心理是也 !
非运算 (逻辑反 )是逻辑的否定,当条件具备时,结果不会发生；而条件不具备时,结果一定会发生 。 例如,在图 2-
7所示的开关电路中,只有当开关 A断开时,灯 F才亮,当开关 A闭合时,灯 F反而熄灭 。 灯 F的状态总是与开关 A的状态相反 。 这种结果总是同条件相反的逻辑关系称为非逻辑 。 非逻辑的真值表如表 2-3所示,其逻辑表达式为
AF?
通常称 A为原变量,A为反变量。
第 2章 逻辑代数基础图 2-7 非逻辑实例
A F
0
1
1
0
表 2-3 非逻辑运算真值表
F
A
R
E
第 2章 逻辑代数基础图 2-8 非门逻辑符号
FA
( a )
FA
( b )
1
FA
( c )
第 2章 逻辑代数基础图 2-9 三极管非
R
V
R
C
F
( U
I
)
U
CC
( + 5v )
A
( U
O
)
第 2章 逻辑代数基础
2.2 逻辑代数的基本定律和规则
2.2.1 基本定律
1,变量和常量的关系式 公理系统逻辑变量的取值只有 0和 1,根据三种基本运算的定义,可推得以下关系式 。
常数,0+0=0 0 1=1 0=0 1+0=0+1=1 1+1=1
0 0=0· 1=1 0=0 1 1=1
0-1律,A·0 =0 A+1 =1 自等律,A·1=A A+0=A
重叠律,A·A=A A+A=A 互补律,A·A=0 A+A=1
第 2章 逻辑代数基础
2,与普通代数相似的定律交换律 A·B=B·A A+B=B+A
结合律 (A·B)·C=A·(B·C) (A+B)+C=A+(B+C)
分配律 A·(B+C)=AB+AC A+BC=(A+B)(A+C)
以上定律可以用真值表证明,也可以用公式证明 。 例如,
证明加对乘的分配律 A+BC=(A+B)(A+C)。
证,(A+B)(A+C) =A·A+A·B+A·C+B·C
=A+AB+AC+BC
=A(1+B+C)+BC=A+BC
因此有 A+BC=(A+B)(A+C)
第 2章 逻辑代数基础
3,逻辑代数中的特殊定律反演律 ( De Morgan定律 )：
BABA
BABA
还原律,AA?
表 2-4 反演律证明
AB
0 0
0 1
1 0
1 1
1
1
1
0
1
1
1
0
1
0
0
0
1
0
0
0
AB BA? BA? BA
证明定理的方法,
1.用定理和公式
2.繁到简
3.两边均等于第三式
4.真值表,
5.证明其对偶式或其反函数相等,
第 2章 逻辑代数基础
2.2.2 三个重要规则
1,代入规则任何一个逻辑等式,如果将等式两边所出现的某一变量都代之以同一逻辑函数,则等式仍然成立,这个规则称为代入规则 。 由于逻辑函数与逻辑变量一样,只有 0,1两种取值,
所以代入规则的正确性不难理解 。 运用代入规则可以扩大基本定律的运用范围 。
例如,已知 A+B=A·B(反演律 ),若用 F=B+C代替等式中的 B,则可以得到适用于多变量的反演律,即
CBACBACBA
第 2章 逻辑代数基础
2,反演规则对于任意一个逻辑函数式 F,如果将其表达式中所有的算符,·”换成,+”,,+”换成,·”,常量,0”换成,1”，
,1”换成,0”,原变量换成反变量,反变量换成原变量,则所得到的结果就是 。 称为原函数 F的反函数,或称为补函数 。
反演规则是反演律的推广,运用它可以简便地求出一个函数的反函数 。 例如：
F F
,ACDCABF );]()[( CADCBAF若 则
,EDCBAF 。EDCBAF若 则运用反演规则时应注意两点,① 不能破坏原式的运算顺序 ——先算括号里的,
然后按,先与后或,的原则运算 。 ② 不属于单变量上的非号应保留不变 。
第 2章 逻辑代数基础
3,对偶规则对于任何一个逻辑函数,如果将其表达式 F中所有的算符
,·”换成,+”,“+”换成,·”,常量,0”换成,1”,,1”换成,0”,而 变量保持不变,则得出的逻辑函数式就是 F的对偶式,记为 F′(或 F*)。 例如：
AFAF
CBAFCBAF
CABAFCABAF
'
'
'
,;,
);1()(),0(
则若则若则若以上各例中 F′是 F的对偶式。不难证明 F也是 F′对偶式。 即 F
与 F′互为对偶式。
第 2章 逻辑代数基础任何逻辑函数式都存在着对偶式 。 若原等式成立,则对偶式也一定成立 。 反之亦然,即,如果 F=G,则 F′=G′。
这种逻辑推理叫做对偶原理,或对偶规则 。
必须注意,由原式求对偶式时,运算的优先顺序不能改变,且式中的非号也保持不变 。
观察前面逻辑代数基本定律和公式,不难看出它们都是成对出现的,而且都是互为对偶的对偶式 。
例如,已知乘对加的分配律成立,即 A(B+C)=AB+AC，
根据对偶规则有,A+BC=(A+B)(A+C),即加对乘的分配律也成立 。
第 2章 逻辑代数基础
4.山农展开定理
对于任何函数 F(x1,x2,…,xi,…,xn) 都有
F(x1,x2,…,xi,…,xn)
=xiF(x1,x2,…,1,…,xn)+ xi F (x1,x2,…,0,…,xn)
F(x1,x2,…,xi,…,xn)
={xi+ F(x1,x2,…,0,…,xn)}{xi+ (x1,x2,…,1,…,xn)}
n=1,…,N,i=1,…,n
证明,令 xi=0,左边 =右边,xi=1,左边 =右边,
这两个定理是下面函数两种标准表达式的理论基础第 2章 逻辑代数基础
2.2.3 若干常用公式
1,合并律
ABAAB
在逻辑代数中,如果两个乘积项分别包含了互补的两个因子 (如 B和 B),而其它因子都相同,那么这两个乘积项称为相邻项 。
合并律说明，两个相邻项可以合并为一项,消去互补量。
(B+B)=A*1=A
第 2章 逻辑代数基础
2,吸收律
A+AB=A
证,A+AB=A(1+B)=A·1=A
该公式说明,在一个与或表达式中,如果某一乘积项的部分因子 (如 AB项中的 A)恰好等于另一乘积项 (如 A)的全部,则该乘积项 (AB)是多余的 。
BABABAAABAA
BABAA
)(1))((证：
第 2章 逻辑代数基础该公式说明,在一个与或表达式中,如果一个乘积项 (如
A)取反后是另一个乘积项 (如 的因子,则此因子 是多余的 。
冗余定理,
BA A
CAAB
BCAA B CCAABBCAACAABBCCAAB
CAABBCCAAB
)(证：
推论：
CAABB C DCAAB
该公式及推论说明,在一个与或表达式中,如果两个乘积项中的部分因子互补 (如 AB项和 AC项中的 A和 A),而这两个乘积项中的其余因子 (如 B和 C)都是第三个乘积项中的因子,则这个第三项是多余的 。
第 2章 逻辑代数基础
2.3 复 合 逻 辑 运算口诀,与,11得 1,或,00得 0,
与非,11得 0,或非,00得 1,异或,不同为 1,同或,相同为 1
2.3.1 复合逻辑运算和复合门
1,与非,或非,与或非逻辑运算与非逻辑运算是与运算和非运算的组合,即
BAF
或非逻辑运算是或运算和非运算的组合,即
BAF
与或非逻辑运算是与、或、非三种运算的组合，即
CDABF
面向器件,
实现复杂功能第 2章 逻辑代数基础图 2-10 与非门,或非门和与或非门的逻辑符号 (a) 与非门； (b) 或非门； (c) 与或非门
F
F
B
F
A
( a )
F
A
&
A
B
B
F
B
F
A
( b )
F
A
A
B
B
＋
≥1
＋
F
B
A
D
C
A
B
C
D
F
B
A
D
C
≥1&
( c )
第 2章 逻辑代数基础
2,异或和同或逻辑运算 仅对二变量定义 !
异或逻辑的含义是：当两个输入变量相异时,输出为 1；
相同时输出为 0。 是异或运算的符号 。 异或运算也称模 2加运算 。
异或逻辑的真值表如表 2-5所示,其逻辑表达式为
BABABAF
A B F
0 0
0 1
1 0
1 1
0
1
1
0
表 2-5 异或逻辑真值表第 2章 逻辑代数基础图 2-11
(a) 异或门； (b) 同或门
F
B
F
A
( a )
F
A
A
B
B
1
＋
F
B
F
A
( b )
F
A
A
B
B
第 2章 逻辑代数基础同或逻辑与异或逻辑相反,它表示当两个输入变量相同时输出为 1；相异时输出为 0。 ⊙ 是同或运算的符号 。
同或逻辑的真值表如表 2-6所示，其逻辑表达式为
F A B A B A B
A B F
0 0
0 1
1 0
1 1
1
0
0
1
表 2-6 同或逻辑真值表第 2章 逻辑代数基础由定义和真值表可见，异或逻辑与同或逻辑互为反函数，即
,A B A B A B A B
不仅如此,它们还互为对偶式 。 如果,
G=A⊙ B,不难证明 F′=G,G′=F。 因此可以将,,作为
,⊙,的对偶符号,反之亦然 。 由以上分析可以看出,两变量的异或函数和同或函数既互补又对偶,这是一对特殊函数 。
BAF
第 2章 逻辑代数基础表 2-7 常用异或和同或运算公式此外，
A
AAAA
0
(A的个数为偶数 )
(A的个数为奇数 )
第 2章 逻辑代数基础补充,
x1⊕x2 ⊕x3 ⊕⊕xn=1,xk中 1的个数为奇数个,否则,
等于 0.
x1☉ x2☉ x3☉☉ xn=1,xk中 0的个数为偶数个,否则,等于 0.
若 F= x1⊕x2 ⊕x3 ⊕⊕xn,则
x1=F⊕x2 ⊕x3 ⊕⊕xn.
若 F= x1☉ x2 ☉ x3☉☉ xn,则
x1=F☉ x2☉ x3☉☉ xn.
计算复合函数的 口诀,与 11..11 1 或 00..0 0
与非 11..11 0 或非 00..00 1
异 不同 1 同 相同 1
第 2章 逻辑代数基础对于一个代数系统,若仅用它所定义的一组运算符号就能解决所有的运算问题,则称这一组符号是一个完备的集合,简称完备集 。
在逻辑代数中,与,或,非是三种最基本的运算,n
变量的所有逻辑函数都可以用 n个变量及一组逻辑运算符
,·,+,-”来构成,因此称,·,+,-”运算符是一组完备集 。
2.3.2 逻辑运算符的完备性第 2章 逻辑代数基础但是,与,或,非,并不是最好的完备集,因为它实现一个函数要使用三种不同规格的逻辑门 。 实际上从反演律可以看出,有了,与,和,非,可得出,或,,
有了,或,和,非,可得出,与,,因此,与非,,
,或非,,,与或非,运算中的任何一种都能单独实现
,与,或,非,运算,这三种复合运算每种都是完备集,而且实现函数只需要一种规格的逻辑门,这就给设计工作带来许多方便 。,异或,与,,”同或,与,也是完备的,可以证明如下,(A+B=A⊕B⊕AB,A+B=A☉ B☉ AB,A⊕1=A,0☉ A=A )
第 2章 逻辑代数基础例如，任何一个逻辑函数式都可以通过逻辑变换写成以下五种形式：
CABA
CABA
CAAB
CABA
CAABF
)()(
))((
与或式或与式与非与非式或非或非式与或非式第 2章 逻辑代数基础图 2-12 逻辑函数的五种形式
&A
B
&
C
≥1
( a )
&
B
&
A
C
&
( c )
A
A
F = AB + AC
A
B
C
≥1
( b )
B
A
( d )
A
&
≥1
F = ( A + B )( A + C )
≥1
≥1
≥1
A
C
A ≥1&
( e )
B
C
A
F = ( A + B ) + ( A + C )
F = AB + AC
F = AB AC
第 2章 逻辑代数基础
2.4 逻辑函数的两种标准形式
2.4.1 最小项和最小项表达式
1,最小项 Why call it Minimal term?
n个变量的最小项是 n个变量的,与项,,其中每个变量都以原变量或反变量的形式出现一次 。
两 个 变 量 A,B 可 以 构 成 四 个 最 小 项 ——
,三个变量 A,B,C可以构成八个最小项,可见 n个变量的最小项共有 个 。
ABCCABCBACBABCACBACBACBA,、、、、、、
ABBABABA,、、
2n
根据山农展开定理，任何函数均可以展成与或式或者或与式，因而有两种两种标准形式第 2章 逻辑代数基础表 2-8 三变量逻辑函数的最小项第 2章 逻辑代数基础最小项具有以下性质,
① n变量的全部最小项的逻辑和恒为 1，即
1
12
0
n
i
im
② 任意两个不同的最小项的逻辑乘恒为 0,即
)(0 jimm ji
③ n变量的每一个最小项有 n个相邻项 。 例如,三变量的某一最小项 有三个相邻项,。
这种相邻关系对于逻辑函数化简十分重要 。
CBA CBABCACBA,、
4.总共有 个最小项,2n
第 2章 逻辑代数基础
2,最小项表达式 ——标准与或式如果在一个与或表达式中,所有与项均为最小项,则称这种表达式为最小项表达式,或称为标准与或式,标准积之和式 。 例如：
CABCBACBACBAF),,(
是一个三变量的最小项表达式,它也可以简写为
546(,,)
( 4,5,6 )
F A B C m m m
m
101 100 110 5,4,6
546m m m
几种形式完全相同！！！
第 2章 逻辑代数基础任何一个逻辑函数都可以表示为最小项之和的形式：
只要将真值表中使函数值为 1的各个最小项相或,便可得出该函数的最小项表达式 。 由于任何一个函数的真值表是惟一的,因此其最小项表达式也是惟一的 。
表 2-9 真值表
A B C F
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
1
0
1
0
1
1
从真值表到表达式 m1
m2
m4
m6
m7
山农第一定理,
F=0 项消失,
f=1项保留第 2章 逻辑代数基础从真值表可知,当 A,B,C取值分别为 001,010、
100,111时,F为 1,因此最小项表达式由这四种组合所对应的最小项进行相或构成,即
)7,4,2,1(mABCCBACBACBAF
表 2-10 三变量逻辑函数的最大项山农第二定理,
F=1项消失,
f=0项保留第 2章 逻辑代数基础
2.4.2 最大项和最大项表达式
1,最大项 Why call it Maximal term?
n个变量的最大项是 n个变量的,或项,,其中每一个变量都以原变量或反变量的形式出现一次 。
n个变量可以构成 2n个最大项 。 最大项用符号 Mi表示 (见表 2-10)。 与最小项恰好相反,对于任何一个最大项,只有一组变量取值使它为 0,而变量的其余取值均使它为 1。
例如，或项 仅和变量取值 101对应，故用 M5
表示。
CBA
当 1 0 1
时，该项为 0！ 1 反变量,0 原变量第 2章 逻辑代数基础最大项具有以下性质：
① n变量的全部最大项的逻辑乘恒为 0，即
12
0
0
n
i
iM
② n变量的任意两个不同的最大项的逻辑和必等于 1，即
)(1 jiMM ji
③ n变量的每个最大项有 n个相邻项 。 例如,三变量的某一最大项 有三个相邻项：)( CBA
。、,)()()( CBACBACBA
④ 总共有 个最大项?2n
第 2章 逻辑代数基础
2,最小项与最大项之间的关系变量数相同,编号相同的最小项和最大项之间存在互补关系,即
iiii mMMm,
例如：
77M A B C A B C m
m A B C A B C A B C M
第 2章 逻辑代数基础
3,最大项表达式 ——标准或与式在一个或与式中,如果所有的或项均为最大项,则称这种表达式为最大项表达式,或称为标准或与式,标准和之积表达式 。 求函数的最大项表达式的方法有两种
① 如果一个逻辑函数的真值表已给出,要写出该函数的最大项表达式,可以先求出该函数的反函数,并写出的最小项表达式,然后将 再求反,利用 mi和 Mi的互补关系便得到最大项表达式 。 例如,已知表 2-11的真值表,可得
F
F
第 2章 逻辑代数基础表 2-11 真值表
A B C F F
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1 0
1 0
0 1
0 1
1 0
1 0
0 1
0 1
2 3 6 7
2 3 6 7
2 3 6 7
( 0,1,4,5 )
( 2,3,6,7 )
Fm
F m m m m
F F m m m m
m m m m
M
可见,② 最大项表达式是真值表中使函数值为 0的各个最大项相与 。
得出结论,任何一个逻辑函数既可以用最小项表达式表示,
也可以用最大项表达式表示 。 如果将一个 n变量函数的最小项表达式改为最大项表达式时,其最大项的编号必定都不是最小项的编号,而且这些最小项的个数和最大项的个数之和为 。
2n
第 2章 逻辑代数基础进一步
从一个真值表的函数的不同读法，对逻辑的深一步的理解：
1。选 1 读最小项 原函数
2。选 1 读最大项 反函数
3。选 0 读最大项 原函数
4。选 0 读最小项 反函数第 2章 逻辑代数基础
*函数化简的概念 *
1.甚么是化简?准则是甚么?
一个与或表达式,与项最少且每个与项的变量数最少
Min Cost,{Cost=α*与项数 +β*与项的变量数 }
2.为甚么要化简?意义何在?
3.怎么化简?
4.有那些化简的方法?
√A.代数法 √ B.卡诺图法
C.表格法 D.迭代一致法第 2章 逻辑代数基础
2.5 逻辑函数的 代数化 简法
1,并项法利用公式 AB+AB=A将两项合并成一项，并消去互补因子。如：
AACCA
CBBCACBCBA
CBAABCCABCBAF
DCADCABDCBAF
)()(
第 2章 逻辑代数基础
2.
利用吸收律 A+AB=A、
和 吸收 (消去 )多余的乘积项或多余的因子 。 如：
BABAA
CAABBCCAAB
DCACBAA D EDCACBADCA D EACBAF
DCDAABCBDDACABC
BDDCAABCBDDCDAABCF
CBDACDCBACDCABAF
CABCABABCBAABCBCAABF
)(
)(
第 2章 逻辑代数基础
3.配项 (法 )
利用重叠律 A+A=A,互补律 A+A=1 和吸收律
AB+AC+BC=AB+AC先配项或添加多余项,然后再逐步化简 。 如：
DCBAC
DABCBAC
DABABCBAC
DBACBAC
CBDBDAACF
)(
(添多余项 AB)
(去掉多余项 AB)
例 1.
第 2章 逻辑代数基础
ABCBCA
ABBCAA B CCBCBACBA
ABAABCCBCCBA
ABBCCBBAF
CBBACA
CABCBABCACBACBACBA
CABBCACBACBAF
)()(
)()()(
例 2.
例 3.
代数法的评价,简单,方便,但方法性不强,可操作性差,仅适用于简单函数的化简,
第 2章 逻辑代数基础
2.6 逻辑函数的卡诺图化简
2.6.1 卡诺图的构成在逻辑函数的真值表中,输入变量的每一种组合都和一个最小项相对应,这种真值表也称最小项真值表 。
卡诺图就是根据最小项真值表按一定规则排列的方格图 。
从文氏图到卡诺图
Explain Why Minimal term or Maximal term?
评论,简单,可操作性强,但四变量以下方便,当多于
5变量时,由于最小 (大 )项的相邻性已不再容易观察,使用不便,故其应用限于 四变量以下 …
第 2章 逻辑代数基础表 2-12 三变量最小项第 2章 逻辑代数基础图 2-14 四变量、五变量 K图
0
AB
CD
00 01 11 10
( a )
1
4 12 8
5 13 9
3
2
7 15 11
6 14 10
00
01
11
10
0
A B C
DE
0 0 0
( b )
1
4 12 8
5 13 9
3
2
7 15 11
6 14 10
00
01
11
10
24
25
28 20 16
29 21 17
27
26
31 23 19
30 22 18
0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0
A B C A B C A B C
A B C A B C A B C A B C
A B C
AB
C
00 01 11 10
0
1
( a )
m
0
AB
C
00 01 11 10
0
1
( b )
m
1
m
2
m
6
m
4
m
3
m
7
m
5
0
AB
C
00 01 11 10
0
1
( c )
1
2 6 4
3 7 5
图 2-13 三变量 K图第 2章 逻辑代数基础由图 2-14可以看出,K图具有如下特点：
① n变量的卡诺图有 2n个方格,对应表示 2n个最小项 。 每当变量数增加一个,卡诺图的方格数就扩大一倍 。
② 卡诺图中任何几何位置相邻的两个最小项,在逻辑上都是相邻的 。 由于变量取值的顺序按格雷码排列,保证了各相邻行 (列 )之间只有一个变量取值不同,从而保证画出来的最小项方格图具有这一重要特点 。
所谓几何相邻,一是相接,即紧挨着； 二是相对,即任意一行或一列的两头；三是相重,即对折起来位置重合 。
所谓逻辑相邻,是指除了一个变量不同外其余变量都相同的两个与项 。
第 2章 逻辑代数基础例如图 2-14(b)五变量 K图中,m5在几何位置上与 m4,m7、
m1,m13,m21相邻,与 相邻,
此外还与和 分别相邻,即 m5有五个相邻项 。 可见卡诺图也反映了 ⑶ n变量的任何一个最小项有 n个相邻项这一特点 。 卡诺图的 主要缺点 是随着输入变量的增加图形迅速复杂,相邻项不那么直观,因此它只适于用来表示 6个以下变量的逻辑函数 。 我将解决 5,6变量的化简问题方法,
EDCBAm?5 EDCBAm?4
EDBCAmEDCBAmC D EBAm 1317,、
EDCBAm?21
第 2章 逻辑代数基础
2.6.2 逻辑函数 的卡诺图表示法
1,给出逻辑函数的最小项表达式只要将构成逻辑函数的最小项在卡诺图上相应的方格中填 1,其余的方格填 0(或不填 ),则可以得到该函数的卡诺图 。 也就是说,任何一个逻辑函数都等于其卡诺图上填 1
的那些最小项之和 。
例如,用卡诺图表示函数 时,只需在三变量卡诺图中将 m0,m3,m4,m6处填 1,其余填 0(或不填 ),如图 2-15(a)所示 。
同理,的卡诺图如图 2-
15(b)所示。
)6,4,3,0(1 mF
)15,12,10,9,7,4,2,0(2 mF
得到卡诺图的方法：
1。表达式标准型非标准型
2。真值表第 2章 逻辑代数基础图 2-15 F1,Ｆ 2的卡诺图
1
AB
C
00 01 11 10
0
1
( a )
0 1 1
1
AB
CD
00 01 11 10
( b )
0
1 1 0
0 0 1
0
1
1 1 0
0 0 1
00
01
11
10
0 1 0 0
第 2章 逻辑代数基础
2.
将一般与或式中每个与项在卡诺图上所覆盖的最小项处都填 1，
其余的填 0(或不填 ),就可以得到该函数的卡诺图 。
例如,用卡诺图表示函数 时,先确定使每个与项为 1的输入变量取值,然后在该输入变量取值所对应的方格内填 1。
：当 ABCD=101× (× 表示可以为 0,也可以为 1)时该与项为 1，
在卡诺图上对应两个方格 (m10,m11)处填 1。
ADDCBACBAF3
CBA
@ 卡诺图的获的,真值表,标准型,非标准型,
最小项,最大项卡诺图第 2章 逻辑代数基础
：当 ABCD=001× 时该与项为 1,对应两个方格
(m2,m3)处填 1。
D：当 ABCD=××× 1时该与项为 1,对应八个方格
(m1,m3,m5,m7,m9,m11,m13,m15)处填 1。
AD：当 ABCD=1×× 1时该与项为 1,对应四个方格
(m9,m11,m13,m15)处填 1。
某些最小项重复，只需填一次即可。
CBA
第 2章 逻辑代数基础图 2-16 F3的卡诺图
AB
CD
00 01 11 10
1 1 1 1
1
1
1 1 1
1
00
01
11
10
第 2章 逻辑代数基础
3.
只要将构成逻辑函数的最大项在卡诺图相应的方格中填 0,其余的方格填 1即可 。 也就是说,任何一个逻辑函数都等于其卡诺图上填 0的那些最大项之积 。
例如,函数 的卡诺图如图 2-17所示 。
必须注意,在卡诺图中最大项的编号与最小项编号是一致的,但对应输入变量的取值是相反的 。
))()(()6,2,0(4 CBACBACBAMF
+F(000)
+F(010)
+F(110)
第 2章 逻辑代数基础图 2-17 F4的卡诺图
0
AB
C
00 01 11 10
0
1
0 0 1
1 1 1 1
第 2章 逻辑代数基础
4.
将一般或与式中每个或项在卡诺图上所覆盖的最大项处都填 0,其余的填 1即可 。
例如,将函数 填入卡诺图时,先确定使每个或项为 0时输入变量的取值,然后在该取值所对应的方格内填 0。
))((5 CBCAF
:)( CA?
:)( CB?
当 ABC=1× 0时，该或项为 0，对应两个方格
(M4,M6)处填 0。
当 ABC=× 10时，该或项为 0，对应两个方格
(M2,M6)处填 0。
第 2章 逻辑代数基础某些最大项重复，填一次即可。 F5的卡诺图如图 2-18所示。
图 2-18 F5的卡诺图
1
AB
C
00 01 11 10
0
1
0 0 0
1 1 1 1
第 2章 逻辑代数基础
2.6.3 最小项合并规律 要领,大 --新 --全在卡诺图中,凡是几何位置相邻的最小项均可以合并 。
两个相邻最小项合并为一项,消去一个互补变量 。 在卡诺图上该合并圈称为单元圈,它所对应的与项由圈内没有变化的那些变量组成,可以直接从卡诺图中读出 。 例如,图 2-
19(a) 中 m1,m3合并为,图 2-19(b)中 m0,m4合并为 。
任何两个相邻的单元 K圈也是相邻项,仍然可以合并,
消去互补变量 。 因此,如果 K圈越大,消去的变量数就越多 。
CA CB
最大项合并规律一样卡诺图化简的实质,1AA
第 2章 逻辑代数基础图 2-19(c),(d)表示 四个相邻最小项合并为一项,消去了两个变量,合并后积项由 K圈对应的没有变化的那些变量组成 。 图 2-19(c)中 m0,m1,m4,m5合并为,图 2-19(d)
中 m0,m2,m8,m10合并为,m5,m7,m13,m15合并为
BD,m12,m13,m15,m14合并为 AB。
图 2-19(e)表示 八个相邻最小项合并为一项,消去了三个变量,
DB
CA
DmAm )15,13,11,9,7,5,3,1(,)15,14,13,12,11,10,9,8(
3( 8 2 )?
第 2章 逻辑代数基础综上所述,最小项合并有以下特点：
① 任何一个合并圈 (即卡诺圈 )所含的方格数为 个 。
② 必须按照 相邻规则 画卡诺圈,几何位置相邻包括三种情况：一是相接,即紧挨着的方格相邻；二是相对,即一行
(或一列 )的两头,两边,四角相邻；三是相重,即以对称轴为中心对折起来重合的位置相邻 。
③ 2m个方格合并,消去 m个变量 。 合并圈 越大,消去的变量数越多 。
需要指出,上述最小项的合并规则,对最大项的合并同样是适用的 。 只是因为最大项是与函数的 0值相对应,在卡诺图中则与 0格对应,因此,最大项的合并在卡诺图中是相邻的 0格圈在一起 。
2i
第 2章 逻辑代数基础合并规律
2个最小项合并,消去一个变量
4个最小项合并,消去两个变量
8个最小项合并,消去三个变量
个最小项合并,消去 k个变量若,则 n个变量全消去,
2k
kn? 1F !
第 2章 逻辑代数基础图 2-19 最小项合并规律
1
AB
C
00 01 11 10
0
1
1
( b )
AB
C
00 01 11 10
0
1 1 1
1
AB
CD
00 01 11 10
1
1
1
00
01
11
10
( c )
( a )
1
AB
CD
00 01 11 10
1 1
1 1
1
1 1
1 1
00
01
11
10
( d )
AC
AC
BC
BD AB
CD
00 01 11 10
1
1 1
1 1 1
1 1 1 1
1 1
00
01
11
10
( e )
A
BD
AB
D
第 2章 逻辑代数基础
2.6.4 用卡诺图化简逻辑函数
1.
在卡诺图上以最少的卡诺圈数和尽可能大的卡诺圈覆盖所有填 1的方格,即满足最小覆盖,就可以求得逻辑函数的最简与或式 。
化简的 一般步骤 是：
① 画出逻辑函数的 K图 。
② 先从只有一种圈法的最小项开始圈起,K圈的数目应最少 (与项的项数最少 ),K圈应尽量大 (对应与项中变量数最少 )。
大第 2章 逻辑代数基础
③ 将每个 K圈写成相应的与项,并将它们相或,便得到最简与或式 。 (新 )
圈Ｋ圈时应注意,根据重叠律 (A+A=A),任何一个 1格可以多次被圈用,
但如果在某个 K圈中所有的 1格均已被别的 K圈圈过,则该圈为多余圈 。 为了避免出现多余圈,应保证每个 K圈内至少有一个 1格只被圈一次 。 (全 )
④ Check if all,1” elements of the function to be
simplified have been covered by all circles selected.
第 2章 逻辑代数基础
【 例 2-1】 求 ) F= m(1,3,4,5,10,11,12,13)的最简与或式 。
解,① 画出 F的 K图 (见图 2-20)。
图 2-20 例 2-1的卡诺图
AB
CD
00 01 11 10
1
1 1
1 1
1 1
1
00
01
11
10
BC
ABD
ABC
第 2章 逻辑代数基础
② 画 K圈 。 按照最小项合并规律,将可以合并的最小项分别圈起来 。
根据化简原则,应选择最少的 K圈和尽可能大的 K圈覆盖所有的 1格 。 首先选择只有一种圈法的 BC,剩下四个 1格 (m1,m3,m10,m11)用两个 K圈 覆盖 。
可见一共只要用三个 K圈即可覆盖全部 1格 。
③ 写出最简式。
CBADBA,
CBADBACBF
第 2章 逻辑代数基础
【 例 2-2】 求 A B C DCABDCBDBACDBF
的最简与或式。
解,① 画出 F的 K图 。 给出的 F为一般与或式,将每个与项所覆盖的最小项都填 1,K图如图 2-21所示 。
图 2-21 例 2-2的卡诺图
A B
C D
0 0 0 1 1 1 1 0
1 1
1
1
1
1 1
1 1
0 0
0 1
1 1
1 0
( a )
A B
C D
0 0 0 1 1 1 1 0
1 1
1
1
1
1 1
1 1
0 0
0 1
1 1
1 0
( b )
第 2章 逻辑代数基础
② 画 K 。
③ 写出最简与或式 。
本例有两种圈法,都可以得到最简式 。
按图 2-21(a)圈法：
A B DDCBDCACBF
按图 2-21(b)圈法：
A C DCABDBACBF
该例说明，逻辑函数的最简式不是惟一的。
第 2章 逻辑代数基础
**【 例 2-3】 求的最简与或式 。
解,① 画 F的 K图 。
这是一个五变量逻辑函数,按五变量 K图中的编号填图,得出 F的 K图如图 2 - 22所示 。
)31,29,27,25,24,23,22,21,20,16,15,13,11,8,7,6,5,4,0(mF
第 2章 逻辑代数基础
1
AB C
DE
0 0 0
1 *1
1 1 *
1 1 *1
*1
00
01
11
10
1
1
1 1
1 1
1 1 1
1 *
0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0
图 2-22 例 2-3的卡诺图第 2章 逻辑代数基础五,六变量的处理
)31,29,27,25,24,23,22,21,20,16,15,13,11,8,7,6,5,4,0(mF
断开小于 16的不变
③
①
② 大于等于 16的减去 16
0,4,5,6,7,8,9,11,13,15
④ 对②和 ③ 分别做两个四变量的 Karnaugh图
A A
⑤ F=AF(i<16)+AF(>=16)
⑥ 若有 A*Y+A*Y,则合并成 Y，等等。
第 2章 逻辑代数基础
② 画 K圈化简函数。
先找只有一种圈法的最小项：
覆盖；用余下覆盖；：用覆盖；：用覆盖；，：用覆盖；用、
ABEmm
EDCmm
CEmm
B D Emm
CBmmm
)31,29,27,25(
)24,16,8,0(
)31,29,23,21,15,13,7,5(
)3127,15,11(
)23,22,21,20,7,6,5,4(:
25
8
13
11
226
第 2章 逻辑代数基础
③ 写出最简式。
A B EEDCCEB D ECBF
如何判断得到的函数式是否为最简式呢? 下面从蕴含项的概念讨论最简式问题：
① 蕴含项 ( Implicant)。 组成逻辑函数的每一个与项
(积项 )称为该函数的蕴含项 。 它可以是最小项,也可以是合并项 。
第 2章 逻辑代数基础
② 本原蕴含项 (Prime Implicant)。 如果逻辑函数的一个蕴含项再也不能同该函数的其它蕴含项合并组成变量数更少的蕴含项,则称该蕴含项为本原蕴含项 。 实际上它对应着卡诺图中不能再扩大的合并项,
即最大卡诺圈 。
③ 实质本原蕴含项 (Essential Prime Implicant)。 不能被其它蕴含项所包含的本原蕴含项称为实质本原蕴含项 。 它对应着卡诺图中必不可少的最大卡诺圈,该圈至少包含了一个只有一种圈法的最小项 。
求本源蕰涵项集 最简与或式 (最简或与式 )
第 2章 逻辑代数基础例如,已知逻辑函数 F1,F2的卡诺图分别如图 2-23(a)、
(b)所示,化简 F1时只需用 3 个最大的 K圈就可以覆盖全部 1
格,如果用四个 K圈肯定有一个多余圈 。 从图 2-23(a)中看出,
合并项 AC为多余项,因为该圈中每个 1 格被圈了两次 。 因此可得出最简与或式为
CBDAABF1
化简图 2-23(b)的 F2,只用六个最大的 K圈覆盖所有的 1
格,观察每一个 K圈都有一个 1 格只被圈过一次,因此这六个 K圈都必须存在,最简与或式为
CDBADCADCABACBDBF2
第 2章 逻辑代数基础图 2-23 F1,F2的化简 K图
( a )
AB
CD
00 01 11 10
1
1 1
1 1
1
1 1
1 1
00
01
11
10
( b )
1
AB
CD
00 01 11 10
1
1 1 1
1 1
1
1
1 1
00
01
11
10
第 2章 逻辑代数基础
2,求最简或与式任何一个逻辑函数既可以等于其卡诺图上填 1的那些最小项之和,也可以等于其卡诺图上填 0的那些最大项之积,因此,如果要求出某函数的最简或与式,可以在该函数的卡诺图上合并那些填 0的相邻项 。 这种方法简称为圈 0合并,其化简步骤及化简原则与圈 1合并类同,只要按圈逐一写出或项,然后将所得的或项相与即可 。 但需注意,或项由 K圈对应的没有变化的那些变量组成,当变量取值为 0时写原变量,取值为 1时写反变量 。
第 2章 逻辑代数基础
【 例 2-4】 求 )13,11,9,7,6,5,4,3,1(mF 的最简或与式。
解：
① 画出 F的 K图 (见图 2-24)。
② 圈 K圈 。 圈 0合并,其规律与圈 1相同,即 K圈的数目应最少,K圈所覆盖的 0格应尽可能多 。 本例用三个 K圈覆盖所有 0格 。
③ 写出最简或与式。
))()(( CBADADBF
第 2章 逻辑代数基础图 2-24 例 2-4的卡诺图
0
AB
CD
00 01 11 10
1
1 0 0
1 1 1
1
0
1 0 1
1 0 0
00
01
11
10
第 2章 逻辑代数基础
【 例 2-5】 求 CCABADCBAF ))()(( 的最简或与式。
解,① 画出 F的 K图 。 本例给出的 F为一般或与式,因此将每个或项所覆盖的最大项都填 0,就可以得到 F的 K图如图
2-25所示 。
② 圈 K圈化简函数 。
③ 写出最简或与式。
))(( BADBACF
当需要将逻辑函数化为最简与或非式时,也可以采用合并 0格的方式,即在卡诺图上圈 0格,先求出 的最简与或式,然后根据 F=F再求出 F的最简与或非式 。
F
第 2章 逻辑代数基础图 2-25 例 2-5的卡诺图
AB
CD
00 01 11 10
0 0
0
0
0
0 0 0
0 0 0
00
01
11
10
第 2章 逻辑代数基础
2.7 非完全描述逻辑函数的化简
2.7.1 非完全描述的逻辑函数逻辑问题分为完全描述和非完全描述两种 。 如果对于输入变量的每一组取值,逻辑函数都有确定的值,则称这类函数为完全描述逻辑函数 。 如果对于输入变量的某些取值组合逻辑函数值不确定,即函数值可以为 0,也可以为 1(通常将函数值记为?或 × ),那么这类函数称为非完全描述的逻辑函数 。
第 2章 逻辑代数基础表 2-13 非完全描述逻辑函数真值表
A B C F
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
第 2章 逻辑代数基础无关项发生在以下两种情况：
① 由于某种条件的限制 (或约束 )使得输入变量的某些组合不可能出现,因而在这些取值下对应的函数值是,无关,紧要的,它可以为 1,也可以为 0。
② 某些输入变量取值所产生的输出并不影响整个系统的功能,因此可以不必考虑其输出是 0还是 1。
非完全描述逻辑函数一般用以下方法表示：
① 在真值表或 K图中填?或 ×,表示函数值为 0或 1均可。
② 在逻辑表达式中用约束条件来表示。
第 2章 逻辑代数基础例如,十字路口的交通灯规定红灯停,绿灯行,黄灯要注意 (即黄灯一亮,未过停车线的车辆也须停车 )。 若以变量 A、
B,C分别表示红,黄,绿灯的状态,且以灯亮为 1,灯灭为
0,用 F表示停车与否,且以停车为 1,通行为 0,则 F是 A,B、
C的函数 。 如果规定不允许有两个以上的灯同时亮,则 A,B、
C三个变量的取值组合只可能是 000,001,010,100,而不应出现 011,101,110,111这四种情况,即 A与 B,A与 C,B
与 C,A与 B与 C不可能同时为 1,所以 A,B,C是一组具有约束的变量,其相互约束关系可以表示为,AB=0,BC=0、
AC=0,ABC=0,即 AB+BC+AC+ABC=0,或写成 (3,5,6,7)=0。
式中的最小项就是我们所说的无关项 。
第 2章 逻辑代数基础由此可见,当约束条件满足时,这些无关项的值恒为 0，
如果将这些恒为 0的最小项加到逻辑函数式或从函数式中消去,都不会影响函数的逻辑功能和函数值,因此,我们可以将无关项对应的输出函数值视为 × 。 表 2-14写出了交通停车逻辑函数的真值表 。 该逻辑函数表达式可以写成：
0ACBCAB
CBACBAF
也可简写为
)7,6,5,3()1,0(
)7,6,5,3()4,2(
MF
mF
第 2章 逻辑代数基础
2.7.2
在非完全描述逻辑函数中,由于在无关项的相应取值下,
函数值随意取成 0或 1都不影响函数原有的功能,因此可以充分利用这些无关项来化简逻辑函数,即采用卡诺图化简函数时,可以利用? (或 × )来扩大卡诺圈 。
【 例 2-6】 化简上述交通停车逻辑函数 。
解：根据表 2-14交通停车逻辑函数的真值表画出该函数的卡诺图如图 2-26所示 。 在 K图上圈 1得
BAF
第 2章 逻辑代数基础图 2-26 例 2-6的卡诺图
0
AB
C
00 01 11 10
0
1
1 × 1
0 × × ×
第 2章 逻辑代数基础
【 例 2-7】 试化简逻辑函数 为最简或与式,并用与或非门实现电路 。
解：
① 画出 F的卡诺图如图 2-27(a)所示 。 是约束条件,在卡诺图中相应的位置填 × 。
② 圈 0求得 F 的最简与或式。
0
)8,6,4,2(
DCABCBA
mF
0 DCABCBA
ACABDF
③ 将函数 F变换为最简与或非式。
ACABDFF
第 2章 逻辑代数基础
④ 画出逻辑电路，如图 2-27(b)所示。
图 2-27 例 2-7的卡诺图
×
AB
CD
00 01 11 10
×
1 0 1
0 × 0
0
1
0 0 0
1 0 0
00
01
11
10
( a )
D ≥1&
( b )
B
C
A
F
第 2章 逻辑代数基础拾遗
1.化简方法,
A.代数法 B.卡诺图法
C.表格法 D.迭代一致法
2,5,6变量的函数的卡诺图法化简
3.真值表和卡诺图的深入理解
F,F 最小项 最大项 0 1
4.卡诺图的运算
12,,1 2,1 2,1 2F F F F F F F F F
等等
5.逻辑断语,因果表,真值表,卡诺图,表达式,逻辑图,电路图
6。 关于完全描述函数和非完全描述函数的补函数的注意：例如
(0,1,3,7),( 2,4,5,6 )F m F M
若
( 0,1,3,6 ) ( 7 ),
( 2,4,5,7 ),
( 2,4,5 ) ( 7 )
F m d
FM
F M d
7.卡诺图化简的步骤和要领,大,新全描述第 2章 逻辑代数基础继续
下一章将讨论用指定类型的门来实现一个逻辑函数,一般方法是,
1.若指定用”与 -非”实现
最好选最小项,读 1,得原函数,再两次取反变换即可
2.若指定用”或 -非”实现
最好选最大项,读 0,得原函数,再两次取反变换即可
3.若指定用”与 -或 -非”实现
最好选最小项,读 0,得反函数,取反得原函数
2.1逻辑代数的三种基本运算
2.2 逻辑代数的基本定律和规则
2.3 复合逻辑
2.4 逻辑函数的两种标准形式
2.5 逻辑函数的代数化简法
2.6 逻辑函数的卡诺图化简
2.7 非完全描述逻辑函数的化简第 2章 逻辑代数基础
**初步 门电路 GATE
实现基本逻辑运算和常用复合逻辑运算的电子电路与或非与 非或 非异或与或非与 门或 门非 门与 非 门或 非 门异或门与或非门第 2章 逻辑代数基础
**逻辑变量与两状态开关低电平高电平断开闭合高电平 3 V
低电平 0 V
二值逻辑,所有逻辑变量只有两种取值 (1 或 0)。
数字电路,
3V
Iu S
Ou
Iu S Ou
逻辑状态
1
0
0
S 可由 二极管,三极管 或 MOS 管实现通过电子开关 S 的两种状态 (开或关 )
获得高、低电平，用来表示 1 或 0。
1
第 2章 逻辑代数基础
**关于高、低电平与正、负逻辑负逻辑正逻辑
0V
5V
2.4V
0.8V
高电平和低电平是两个不同的可以截然区别开来的电压范围。
0
1
0V
5V
2.4V
0.8V1
0
第 2章 逻辑代数基础
2.1 逻辑代数的三种基本运算 代数 集代数
={{集合 },{定义在该集合上的运算集 }} 布尔代数 {有限集 }
逻辑代数 {二值集 }
2.1.1 逻辑变量与逻辑函数 ={B={0,1},{.,+,}}
逻辑是指事物因果之间所遵循的规律 。 为了避免用冗繁的文字来描述逻辑问题,逻辑代数采用逻辑变量和一套运算符组成逻辑函数表达式来描述事物的因果关系 。
逻辑代数中的变量称为逻辑变量,一般用大写字母 A、
B,C,…表示,逻辑变量的取值只有两种,即逻辑 0和逻辑 1。 0和 1称为逻辑常量 。 但必须指出,这里的逻辑 0和 1
本身并没有数值意义,它们并不代表数量的大小,而仅仅是作为一种符号,代表事物矛盾双方的两种状态 。
第 2章 逻辑代数基础逻辑函数与普通代数中的函数相似,它是随自变量的变化而变化的因变量 。 因此,如果用自变量和因变量分别表示某一事件发生的条件和结果,那么该事件的因果关系就可以用逻辑函数来描述 。
数字电路的输入,输出量一般用高,低电平来表示,高,低电平也可以用二值逻辑 1和 0来表示 。 同时数字电路的输出与输入之间的关系是一种因果关系,因此它可以用逻辑函数来描述,并称为逻辑电路 。 对于任何一个电路,若输入逻辑变量 A,B,C,…的取值确定后,其输出逻辑变量 F的值也被惟一地确定了,则可以称 F是 A,B,C,… 的逻辑函数,并记为
),,,( CBAfF
逻辑代数是研究逻辑函数的描述,性质,变换,化简的学科它是数字电路的数学基础第 2章 逻辑代数基础
2.1.2 三种基本运算
1,与运算 (逻辑乘 )
与运算 (逻辑乘 )表示这样一种逻辑关系：只有当决定一事件结果的所有条件同时具备时,结果才能发生 。 例如在图 2-1所示的串联开关电路中,只有在开关 A和 B都闭合的条件下,灯 F才亮,这种灯亮与开关闭合的关系就称为与逻辑 。
如果设开关 A,B闭合为 1,断开为 0,设灯 F亮为 1,灭为 0，
则 F与 A,B的与逻辑关系可以用表 2-1所示的真值表来描述,
所谓真值表,就是将自变量的各种可能的取值组合与其因变量的值一一列出来的表格形式 。
第 2章 逻辑代数基础图 2 -1 与逻辑实例
A
F
B
E
第 2章 逻辑代数基础表 2-1 与逻辑运算真值表
A B F
0 0
0 1
1 0
1 1
0
0
0
1
与逻辑可以用逻辑表达式表示为
F=A·B
第 2章 逻辑代数基础在逻辑代数中,将与逻辑称为与运算或逻辑乘 。 符号
,·”表示逻辑乘,在不致混淆的情况下,常省去符号,·”。
在有些文献中,也采用 ∧,∩及 &等符号来表示逻辑乘 。
实现与逻辑的单元电路称为与门,其逻辑符号如图 2-2
所示,其中图 (a)为我国常用的传统符号,图 (b)为国外流行的符号,图 (c)为国标符号 (见附录一 )。 图 2-3是一个 2 输入的二极管与门电路 。 图中输入端 A,B的电位可以取两种值：
高电位 +3V或低电位 0V。 设二极管为理想开关,并规定高电位为逻辑 1,低电位为逻辑 0,那么 F与 A,B之间逻辑关系的真值表与表 2-1相同,因而实现了 F=A·B的功能 。
第 2章 逻辑代数基础图 2-2 与门的逻辑符号 图 2-3 二极管与门
F
A
B
( a )
( b )
&
F
A
B
( c )
F
A
B
U
CC
( + 5V )
R
3,9 k
A
B
F
V
1
V
2
第 2章 逻辑代数基础
2,或运算 (逻辑加 ),决定某事件发生的条件之一成立则该事件就发生的逻辑,
图 2-4 或逻辑实例
F
A
B
E
第 2章 逻辑代数基础表 2-2 或逻辑运算真值表
A B F
0 0
0 1
1 0
1 1
0
1
1
1
或逻辑可以用逻辑表达式表示为
F=A+B
或逻辑也称为或运算或逻辑加 。 符号,+”表示逻辑加 。
有些文献中也采用 ∨,∪ 等符号来表示逻辑加 。
第 2章 逻辑代数基础实现或逻辑的单元电路称为或门,其逻辑符号如图 2-5
所示,其中图 (a)为我国常用的传统符号,图 (b)为国外流行的符号,图 (c)为国标符号 (见附录一 )。 图 2-6是一个 2 输入的二极管或门电路 。 图中输入端 A,B的电位可以取两种值,高电位 +3V或低电位 0 V。
,并规定高电位为逻辑 1,低电位为逻辑 0,则 F与 A,B之间逻辑关系的真值表与表 2-2相同,
因此实现了 F=A+B的功能 。
第 2章 逻辑代数基础图 2-5 或门的逻辑符号 图 2-6 二极管或门
＋
F
A
B
( a )
( b )
F
A
B
( c )
≥1
F
A
B
R
3,9 k
B
A
F
V
2
V
1
第 2章 逻辑代数基础
3,非运算 (逻辑反 ) 逆反心理是也 !
非运算 (逻辑反 )是逻辑的否定,当条件具备时,结果不会发生；而条件不具备时,结果一定会发生 。 例如,在图 2-
7所示的开关电路中,只有当开关 A断开时,灯 F才亮,当开关 A闭合时,灯 F反而熄灭 。 灯 F的状态总是与开关 A的状态相反 。 这种结果总是同条件相反的逻辑关系称为非逻辑 。 非逻辑的真值表如表 2-3所示,其逻辑表达式为
AF?
通常称 A为原变量,A为反变量。
第 2章 逻辑代数基础图 2-7 非逻辑实例
A F
0
1
1
0
表 2-3 非逻辑运算真值表
F
A
R
E
第 2章 逻辑代数基础图 2-8 非门逻辑符号
FA
( a )
FA
( b )
1
FA
( c )
第 2章 逻辑代数基础图 2-9 三极管非
R
V
R
C
F
( U
I
)
U
CC
( + 5v )
A
( U
O
)
第 2章 逻辑代数基础
2.2 逻辑代数的基本定律和规则
2.2.1 基本定律
1,变量和常量的关系式 公理系统逻辑变量的取值只有 0和 1,根据三种基本运算的定义,可推得以下关系式 。
常数,0+0=0 0 1=1 0=0 1+0=0+1=1 1+1=1
0 0=0· 1=1 0=0 1 1=1
0-1律,A·0 =0 A+1 =1 自等律,A·1=A A+0=A
重叠律,A·A=A A+A=A 互补律,A·A=0 A+A=1
第 2章 逻辑代数基础
2,与普通代数相似的定律交换律 A·B=B·A A+B=B+A
结合律 (A·B)·C=A·(B·C) (A+B)+C=A+(B+C)
分配律 A·(B+C)=AB+AC A+BC=(A+B)(A+C)
以上定律可以用真值表证明,也可以用公式证明 。 例如,
证明加对乘的分配律 A+BC=(A+B)(A+C)。
证,(A+B)(A+C) =A·A+A·B+A·C+B·C
=A+AB+AC+BC
=A(1+B+C)+BC=A+BC
因此有 A+BC=(A+B)(A+C)
第 2章 逻辑代数基础
3,逻辑代数中的特殊定律反演律 ( De Morgan定律 )：
BABA
BABA
还原律,AA?
表 2-4 反演律证明
AB
0 0
0 1
1 0
1 1
1
1
1
0
1
1
1
0
1
0
0
0
1
0
0
0
AB BA? BA? BA
证明定理的方法,
1.用定理和公式
2.繁到简
3.两边均等于第三式
4.真值表,
5.证明其对偶式或其反函数相等,
第 2章 逻辑代数基础
2.2.2 三个重要规则
1,代入规则任何一个逻辑等式,如果将等式两边所出现的某一变量都代之以同一逻辑函数,则等式仍然成立,这个规则称为代入规则 。 由于逻辑函数与逻辑变量一样,只有 0,1两种取值,
所以代入规则的正确性不难理解 。 运用代入规则可以扩大基本定律的运用范围 。
例如,已知 A+B=A·B(反演律 ),若用 F=B+C代替等式中的 B,则可以得到适用于多变量的反演律,即
CBACBACBA
第 2章 逻辑代数基础
2,反演规则对于任意一个逻辑函数式 F,如果将其表达式中所有的算符,·”换成,+”,,+”换成,·”,常量,0”换成,1”，
,1”换成,0”,原变量换成反变量,反变量换成原变量,则所得到的结果就是 。 称为原函数 F的反函数,或称为补函数 。
反演规则是反演律的推广,运用它可以简便地求出一个函数的反函数 。 例如：
F F
,ACDCABF );]()[( CADCBAF若 则
,EDCBAF 。EDCBAF若 则运用反演规则时应注意两点,① 不能破坏原式的运算顺序 ——先算括号里的,
然后按,先与后或,的原则运算 。 ② 不属于单变量上的非号应保留不变 。
第 2章 逻辑代数基础
3,对偶规则对于任何一个逻辑函数,如果将其表达式 F中所有的算符
,·”换成,+”,“+”换成,·”,常量,0”换成,1”,,1”换成,0”,而 变量保持不变,则得出的逻辑函数式就是 F的对偶式,记为 F′(或 F*)。 例如：
AFAF
CBAFCBAF
CABAFCABAF
'
'
'
,;,
);1()(),0(
则若则若则若以上各例中 F′是 F的对偶式。不难证明 F也是 F′对偶式。 即 F
与 F′互为对偶式。
第 2章 逻辑代数基础任何逻辑函数式都存在着对偶式 。 若原等式成立,则对偶式也一定成立 。 反之亦然,即,如果 F=G,则 F′=G′。
这种逻辑推理叫做对偶原理,或对偶规则 。
必须注意,由原式求对偶式时,运算的优先顺序不能改变,且式中的非号也保持不变 。
观察前面逻辑代数基本定律和公式,不难看出它们都是成对出现的,而且都是互为对偶的对偶式 。
例如,已知乘对加的分配律成立,即 A(B+C)=AB+AC，
根据对偶规则有,A+BC=(A+B)(A+C),即加对乘的分配律也成立 。
第 2章 逻辑代数基础
4.山农展开定理
对于任何函数 F(x1,x2,…,xi,…,xn) 都有
F(x1,x2,…,xi,…,xn)
=xiF(x1,x2,…,1,…,xn)+ xi F (x1,x2,…,0,…,xn)
F(x1,x2,…,xi,…,xn)
={xi+ F(x1,x2,…,0,…,xn)}{xi+ (x1,x2,…,1,…,xn)}
n=1,…,N,i=1,…,n
证明,令 xi=0,左边 =右边,xi=1,左边 =右边,
这两个定理是下面函数两种标准表达式的理论基础第 2章 逻辑代数基础
2.2.3 若干常用公式
1,合并律
ABAAB
在逻辑代数中,如果两个乘积项分别包含了互补的两个因子 (如 B和 B),而其它因子都相同,那么这两个乘积项称为相邻项 。
合并律说明，两个相邻项可以合并为一项,消去互补量。
(B+B)=A*1=A
第 2章 逻辑代数基础
2,吸收律
A+AB=A
证,A+AB=A(1+B)=A·1=A
该公式说明,在一个与或表达式中,如果某一乘积项的部分因子 (如 AB项中的 A)恰好等于另一乘积项 (如 A)的全部,则该乘积项 (AB)是多余的 。
BABABAAABAA
BABAA
)(1))((证：
第 2章 逻辑代数基础该公式说明,在一个与或表达式中,如果一个乘积项 (如
A)取反后是另一个乘积项 (如 的因子,则此因子 是多余的 。
冗余定理,
BA A
CAAB
BCAA B CCAABBCAACAABBCCAAB
CAABBCCAAB
)(证：
推论：
CAABB C DCAAB
该公式及推论说明,在一个与或表达式中,如果两个乘积项中的部分因子互补 (如 AB项和 AC项中的 A和 A),而这两个乘积项中的其余因子 (如 B和 C)都是第三个乘积项中的因子,则这个第三项是多余的 。
第 2章 逻辑代数基础
2.3 复 合 逻 辑 运算口诀,与,11得 1,或,00得 0,
与非,11得 0,或非,00得 1,异或,不同为 1,同或,相同为 1
2.3.1 复合逻辑运算和复合门
1,与非,或非,与或非逻辑运算与非逻辑运算是与运算和非运算的组合,即
BAF
或非逻辑运算是或运算和非运算的组合,即
BAF
与或非逻辑运算是与、或、非三种运算的组合，即
CDABF
面向器件,
实现复杂功能第 2章 逻辑代数基础图 2-10 与非门,或非门和与或非门的逻辑符号 (a) 与非门； (b) 或非门； (c) 与或非门
F
F
B
F
A
( a )
F
A
&
A
B
B
F
B
F
A
( b )
F
A
A
B
B
＋
≥1
＋
F
B
A
D
C
A
B
C
D
F
B
A
D
C
≥1&
( c )
第 2章 逻辑代数基础
2,异或和同或逻辑运算 仅对二变量定义 !
异或逻辑的含义是：当两个输入变量相异时,输出为 1；
相同时输出为 0。 是异或运算的符号 。 异或运算也称模 2加运算 。
异或逻辑的真值表如表 2-5所示,其逻辑表达式为
BABABAF
A B F
0 0
0 1
1 0
1 1
0
1
1
0
表 2-5 异或逻辑真值表第 2章 逻辑代数基础图 2-11
(a) 异或门； (b) 同或门
F
B
F
A
( a )
F
A
A
B
B
1
＋
F
B
F
A
( b )
F
A
A
B
B
第 2章 逻辑代数基础同或逻辑与异或逻辑相反,它表示当两个输入变量相同时输出为 1；相异时输出为 0。 ⊙ 是同或运算的符号 。
同或逻辑的真值表如表 2-6所示，其逻辑表达式为
F A B A B A B
A B F
0 0
0 1
1 0
1 1
1
0
0
1
表 2-6 同或逻辑真值表第 2章 逻辑代数基础由定义和真值表可见，异或逻辑与同或逻辑互为反函数，即
,A B A B A B A B
不仅如此,它们还互为对偶式 。 如果,
G=A⊙ B,不难证明 F′=G,G′=F。 因此可以将,,作为
,⊙,的对偶符号,反之亦然 。 由以上分析可以看出,两变量的异或函数和同或函数既互补又对偶,这是一对特殊函数 。
BAF
第 2章 逻辑代数基础表 2-7 常用异或和同或运算公式此外，
A
AAAA
0
(A的个数为偶数 )
(A的个数为奇数 )
第 2章 逻辑代数基础补充,
x1⊕x2 ⊕x3 ⊕⊕xn=1,xk中 1的个数为奇数个,否则,
等于 0.
x1☉ x2☉ x3☉☉ xn=1,xk中 0的个数为偶数个,否则,等于 0.
若 F= x1⊕x2 ⊕x3 ⊕⊕xn,则
x1=F⊕x2 ⊕x3 ⊕⊕xn.
若 F= x1☉ x2 ☉ x3☉☉ xn,则
x1=F☉ x2☉ x3☉☉ xn.
计算复合函数的 口诀,与 11..11 1 或 00..0 0
与非 11..11 0 或非 00..00 1
异 不同 1 同 相同 1
第 2章 逻辑代数基础对于一个代数系统,若仅用它所定义的一组运算符号就能解决所有的运算问题,则称这一组符号是一个完备的集合,简称完备集 。
在逻辑代数中,与,或,非是三种最基本的运算,n
变量的所有逻辑函数都可以用 n个变量及一组逻辑运算符
,·,+,-”来构成,因此称,·,+,-”运算符是一组完备集 。
2.3.2 逻辑运算符的完备性第 2章 逻辑代数基础但是,与,或,非,并不是最好的完备集,因为它实现一个函数要使用三种不同规格的逻辑门 。 实际上从反演律可以看出,有了,与,和,非,可得出,或,,
有了,或,和,非,可得出,与,,因此,与非,,
,或非,,,与或非,运算中的任何一种都能单独实现
,与,或,非,运算,这三种复合运算每种都是完备集,而且实现函数只需要一种规格的逻辑门,这就给设计工作带来许多方便 。,异或,与,,”同或,与,也是完备的,可以证明如下,(A+B=A⊕B⊕AB,A+B=A☉ B☉ AB,A⊕1=A,0☉ A=A )
第 2章 逻辑代数基础例如，任何一个逻辑函数式都可以通过逻辑变换写成以下五种形式：
CABA
CABA
CAAB
CABA
CAABF
)()(
))((
与或式或与式与非与非式或非或非式与或非式第 2章 逻辑代数基础图 2-12 逻辑函数的五种形式
&A
B
&
C
≥1
( a )
&
B
&
A
C
&
( c )
A
A
F = AB + AC
A
B
C
≥1
( b )
B
A
( d )
A
&
≥1
F = ( A + B )( A + C )
≥1
≥1
≥1
A
C
A ≥1&
( e )
B
C
A
F = ( A + B ) + ( A + C )
F = AB + AC
F = AB AC
第 2章 逻辑代数基础
2.4 逻辑函数的两种标准形式
2.4.1 最小项和最小项表达式
1,最小项 Why call it Minimal term?
n个变量的最小项是 n个变量的,与项,,其中每个变量都以原变量或反变量的形式出现一次 。
两 个 变 量 A,B 可 以 构 成 四 个 最 小 项 ——
,三个变量 A,B,C可以构成八个最小项,可见 n个变量的最小项共有 个 。
ABCCABCBACBABCACBACBACBA,、、、、、、
ABBABABA,、、
2n
根据山农展开定理，任何函数均可以展成与或式或者或与式，因而有两种两种标准形式第 2章 逻辑代数基础表 2-8 三变量逻辑函数的最小项第 2章 逻辑代数基础最小项具有以下性质,
① n变量的全部最小项的逻辑和恒为 1，即
1
12
0
n
i
im
② 任意两个不同的最小项的逻辑乘恒为 0,即
)(0 jimm ji
③ n变量的每一个最小项有 n个相邻项 。 例如,三变量的某一最小项 有三个相邻项,。
这种相邻关系对于逻辑函数化简十分重要 。
CBA CBABCACBA,、
4.总共有 个最小项,2n
第 2章 逻辑代数基础
2,最小项表达式 ——标准与或式如果在一个与或表达式中,所有与项均为最小项,则称这种表达式为最小项表达式,或称为标准与或式,标准积之和式 。 例如：
CABCBACBACBAF),,(
是一个三变量的最小项表达式,它也可以简写为
546(,,)
( 4,5,6 )
F A B C m m m
m
101 100 110 5,4,6
546m m m
几种形式完全相同！！！
第 2章 逻辑代数基础任何一个逻辑函数都可以表示为最小项之和的形式：
只要将真值表中使函数值为 1的各个最小项相或,便可得出该函数的最小项表达式 。 由于任何一个函数的真值表是惟一的,因此其最小项表达式也是惟一的 。
表 2-9 真值表
A B C F
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
1
0
1
0
1
1
从真值表到表达式 m1
m2
m4
m6
m7
山农第一定理,
F=0 项消失,
f=1项保留第 2章 逻辑代数基础从真值表可知,当 A,B,C取值分别为 001,010、
100,111时,F为 1,因此最小项表达式由这四种组合所对应的最小项进行相或构成,即
)7,4,2,1(mABCCBACBACBAF
表 2-10 三变量逻辑函数的最大项山农第二定理,
F=1项消失,
f=0项保留第 2章 逻辑代数基础
2.4.2 最大项和最大项表达式
1,最大项 Why call it Maximal term?
n个变量的最大项是 n个变量的,或项,,其中每一个变量都以原变量或反变量的形式出现一次 。
n个变量可以构成 2n个最大项 。 最大项用符号 Mi表示 (见表 2-10)。 与最小项恰好相反,对于任何一个最大项,只有一组变量取值使它为 0,而变量的其余取值均使它为 1。
例如，或项 仅和变量取值 101对应，故用 M5
表示。
CBA
当 1 0 1
时，该项为 0！ 1 反变量,0 原变量第 2章 逻辑代数基础最大项具有以下性质：
① n变量的全部最大项的逻辑乘恒为 0，即
12
0
0
n
i
iM
② n变量的任意两个不同的最大项的逻辑和必等于 1，即
)(1 jiMM ji
③ n变量的每个最大项有 n个相邻项 。 例如,三变量的某一最大项 有三个相邻项：)( CBA
。、,)()()( CBACBACBA
④ 总共有 个最大项?2n
第 2章 逻辑代数基础
2,最小项与最大项之间的关系变量数相同,编号相同的最小项和最大项之间存在互补关系,即
iiii mMMm,
例如：
77M A B C A B C m
m A B C A B C A B C M
第 2章 逻辑代数基础
3,最大项表达式 ——标准或与式在一个或与式中,如果所有的或项均为最大项,则称这种表达式为最大项表达式,或称为标准或与式,标准和之积表达式 。 求函数的最大项表达式的方法有两种
① 如果一个逻辑函数的真值表已给出,要写出该函数的最大项表达式,可以先求出该函数的反函数,并写出的最小项表达式,然后将 再求反,利用 mi和 Mi的互补关系便得到最大项表达式 。 例如,已知表 2-11的真值表,可得
F
F
第 2章 逻辑代数基础表 2-11 真值表
A B C F F
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1 0
1 0
0 1
0 1
1 0
1 0
0 1
0 1
2 3 6 7
2 3 6 7
2 3 6 7
( 0,1,4,5 )
( 2,3,6,7 )
Fm
F m m m m
F F m m m m
m m m m
M
可见,② 最大项表达式是真值表中使函数值为 0的各个最大项相与 。
得出结论,任何一个逻辑函数既可以用最小项表达式表示,
也可以用最大项表达式表示 。 如果将一个 n变量函数的最小项表达式改为最大项表达式时,其最大项的编号必定都不是最小项的编号,而且这些最小项的个数和最大项的个数之和为 。
2n
第 2章 逻辑代数基础进一步
从一个真值表的函数的不同读法，对逻辑的深一步的理解：
1。选 1 读最小项 原函数
2。选 1 读最大项 反函数
3。选 0 读最大项 原函数
4。选 0 读最小项 反函数第 2章 逻辑代数基础
*函数化简的概念 *
1.甚么是化简?准则是甚么?
一个与或表达式,与项最少且每个与项的变量数最少
Min Cost,{Cost=α*与项数 +β*与项的变量数 }
2.为甚么要化简?意义何在?
3.怎么化简?
4.有那些化简的方法?
√A.代数法 √ B.卡诺图法
C.表格法 D.迭代一致法第 2章 逻辑代数基础
2.5 逻辑函数的 代数化 简法
1,并项法利用公式 AB+AB=A将两项合并成一项，并消去互补因子。如：
AACCA
CBBCACBCBA
CBAABCCABCBAF
DCADCABDCBAF
)()(
第 2章 逻辑代数基础
2.
利用吸收律 A+AB=A、
和 吸收 (消去 )多余的乘积项或多余的因子 。 如：
BABAA
CAABBCCAAB
DCACBAA D EDCACBADCA D EACBAF
DCDAABCBDDACABC
BDDCAABCBDDCDAABCF
CBDACDCBACDCABAF
CABCABABCBAABCBCAABF
)(
)(
第 2章 逻辑代数基础
3.配项 (法 )
利用重叠律 A+A=A,互补律 A+A=1 和吸收律
AB+AC+BC=AB+AC先配项或添加多余项,然后再逐步化简 。 如：
DCBAC
DABCBAC
DABABCBAC
DBACBAC
CBDBDAACF
)(
(添多余项 AB)
(去掉多余项 AB)
例 1.
第 2章 逻辑代数基础
ABCBCA
ABBCAA B CCBCBACBA
ABAABCCBCCBA
ABBCCBBAF
CBBACA
CABCBABCACBACBACBA
CABBCACBACBAF
)()(
)()()(
例 2.
例 3.
代数法的评价,简单,方便,但方法性不强,可操作性差,仅适用于简单函数的化简,
第 2章 逻辑代数基础
2.6 逻辑函数的卡诺图化简
2.6.1 卡诺图的构成在逻辑函数的真值表中,输入变量的每一种组合都和一个最小项相对应,这种真值表也称最小项真值表 。
卡诺图就是根据最小项真值表按一定规则排列的方格图 。
从文氏图到卡诺图
Explain Why Minimal term or Maximal term?
评论,简单,可操作性强,但四变量以下方便,当多于
5变量时,由于最小 (大 )项的相邻性已不再容易观察,使用不便,故其应用限于 四变量以下 …
第 2章 逻辑代数基础表 2-12 三变量最小项第 2章 逻辑代数基础图 2-14 四变量、五变量 K图
0
AB
CD
00 01 11 10
( a )
1
4 12 8
5 13 9
3
2
7 15 11
6 14 10
00
01
11
10
0
A B C
DE
0 0 0
( b )
1
4 12 8
5 13 9
3
2
7 15 11
6 14 10
00
01
11
10
24
25
28 20 16
29 21 17
27
26
31 23 19
30 22 18
0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0
A B C A B C A B C
A B C A B C A B C A B C
A B C
AB
C
00 01 11 10
0
1
( a )
m
0
AB
C
00 01 11 10
0
1
( b )
m
1
m
2
m
6
m
4
m
3
m
7
m
5
0
AB
C
00 01 11 10
0
1
( c )
1
2 6 4
3 7 5
图 2-13 三变量 K图第 2章 逻辑代数基础由图 2-14可以看出,K图具有如下特点：
① n变量的卡诺图有 2n个方格,对应表示 2n个最小项 。 每当变量数增加一个,卡诺图的方格数就扩大一倍 。
② 卡诺图中任何几何位置相邻的两个最小项,在逻辑上都是相邻的 。 由于变量取值的顺序按格雷码排列,保证了各相邻行 (列 )之间只有一个变量取值不同,从而保证画出来的最小项方格图具有这一重要特点 。
所谓几何相邻,一是相接,即紧挨着； 二是相对,即任意一行或一列的两头；三是相重,即对折起来位置重合 。
所谓逻辑相邻,是指除了一个变量不同外其余变量都相同的两个与项 。
第 2章 逻辑代数基础例如图 2-14(b)五变量 K图中,m5在几何位置上与 m4,m7、
m1,m13,m21相邻,与 相邻,
此外还与和 分别相邻,即 m5有五个相邻项 。 可见卡诺图也反映了 ⑶ n变量的任何一个最小项有 n个相邻项这一特点 。 卡诺图的 主要缺点 是随着输入变量的增加图形迅速复杂,相邻项不那么直观,因此它只适于用来表示 6个以下变量的逻辑函数 。 我将解决 5,6变量的化简问题方法,
EDCBAm?5 EDCBAm?4
EDBCAmEDCBAmC D EBAm 1317,、
EDCBAm?21
第 2章 逻辑代数基础
2.6.2 逻辑函数 的卡诺图表示法
1,给出逻辑函数的最小项表达式只要将构成逻辑函数的最小项在卡诺图上相应的方格中填 1,其余的方格填 0(或不填 ),则可以得到该函数的卡诺图 。 也就是说,任何一个逻辑函数都等于其卡诺图上填 1
的那些最小项之和 。
例如,用卡诺图表示函数 时,只需在三变量卡诺图中将 m0,m3,m4,m6处填 1,其余填 0(或不填 ),如图 2-15(a)所示 。
同理,的卡诺图如图 2-
15(b)所示。
)6,4,3,0(1 mF
)15,12,10,9,7,4,2,0(2 mF
得到卡诺图的方法：
1。表达式标准型非标准型
2。真值表第 2章 逻辑代数基础图 2-15 F1,Ｆ 2的卡诺图
1
AB
C
00 01 11 10
0
1
( a )
0 1 1
1
AB
CD
00 01 11 10
( b )
0
1 1 0
0 0 1
0
1
1 1 0
0 0 1
00
01
11
10
0 1 0 0
第 2章 逻辑代数基础
2.
将一般与或式中每个与项在卡诺图上所覆盖的最小项处都填 1，
其余的填 0(或不填 ),就可以得到该函数的卡诺图 。
例如,用卡诺图表示函数 时,先确定使每个与项为 1的输入变量取值,然后在该输入变量取值所对应的方格内填 1。
：当 ABCD=101× (× 表示可以为 0,也可以为 1)时该与项为 1，
在卡诺图上对应两个方格 (m10,m11)处填 1。
ADDCBACBAF3
CBA
@ 卡诺图的获的,真值表,标准型,非标准型,
最小项,最大项卡诺图第 2章 逻辑代数基础
：当 ABCD=001× 时该与项为 1,对应两个方格
(m2,m3)处填 1。
D：当 ABCD=××× 1时该与项为 1,对应八个方格
(m1,m3,m5,m7,m9,m11,m13,m15)处填 1。
AD：当 ABCD=1×× 1时该与项为 1,对应四个方格
(m9,m11,m13,m15)处填 1。
某些最小项重复，只需填一次即可。
CBA
第 2章 逻辑代数基础图 2-16 F3的卡诺图
AB
CD
00 01 11 10
1 1 1 1
1
1
1 1 1
1
00
01
11
10
第 2章 逻辑代数基础
3.
只要将构成逻辑函数的最大项在卡诺图相应的方格中填 0,其余的方格填 1即可 。 也就是说,任何一个逻辑函数都等于其卡诺图上填 0的那些最大项之积 。
例如,函数 的卡诺图如图 2-17所示 。
必须注意,在卡诺图中最大项的编号与最小项编号是一致的,但对应输入变量的取值是相反的 。
))()(()6,2,0(4 CBACBACBAMF
+F(000)
+F(010)
+F(110)
第 2章 逻辑代数基础图 2-17 F4的卡诺图
0
AB
C
00 01 11 10
0
1
0 0 1
1 1 1 1
第 2章 逻辑代数基础
4.
将一般或与式中每个或项在卡诺图上所覆盖的最大项处都填 0,其余的填 1即可 。
例如,将函数 填入卡诺图时,先确定使每个或项为 0时输入变量的取值,然后在该取值所对应的方格内填 0。
))((5 CBCAF
:)( CA?
:)( CB?
当 ABC=1× 0时，该或项为 0，对应两个方格
(M4,M6)处填 0。
当 ABC=× 10时，该或项为 0，对应两个方格
(M2,M6)处填 0。
第 2章 逻辑代数基础某些最大项重复，填一次即可。 F5的卡诺图如图 2-18所示。
图 2-18 F5的卡诺图
1
AB
C
00 01 11 10
0
1
0 0 0
1 1 1 1
第 2章 逻辑代数基础
2.6.3 最小项合并规律 要领,大 --新 --全在卡诺图中,凡是几何位置相邻的最小项均可以合并 。
两个相邻最小项合并为一项,消去一个互补变量 。 在卡诺图上该合并圈称为单元圈,它所对应的与项由圈内没有变化的那些变量组成,可以直接从卡诺图中读出 。 例如,图 2-
19(a) 中 m1,m3合并为,图 2-19(b)中 m0,m4合并为 。
任何两个相邻的单元 K圈也是相邻项,仍然可以合并,
消去互补变量 。 因此,如果 K圈越大,消去的变量数就越多 。
CA CB
最大项合并规律一样卡诺图化简的实质,1AA
第 2章 逻辑代数基础图 2-19(c),(d)表示 四个相邻最小项合并为一项,消去了两个变量,合并后积项由 K圈对应的没有变化的那些变量组成 。 图 2-19(c)中 m0,m1,m4,m5合并为,图 2-19(d)
中 m0,m2,m8,m10合并为,m5,m7,m13,m15合并为
BD,m12,m13,m15,m14合并为 AB。
图 2-19(e)表示 八个相邻最小项合并为一项,消去了三个变量,
DB
CA
DmAm )15,13,11,9,7,5,3,1(,)15,14,13,12,11,10,9,8(
3( 8 2 )?
第 2章 逻辑代数基础综上所述,最小项合并有以下特点：
① 任何一个合并圈 (即卡诺圈 )所含的方格数为 个 。
② 必须按照 相邻规则 画卡诺圈,几何位置相邻包括三种情况：一是相接,即紧挨着的方格相邻；二是相对,即一行
(或一列 )的两头,两边,四角相邻；三是相重,即以对称轴为中心对折起来重合的位置相邻 。
③ 2m个方格合并,消去 m个变量 。 合并圈 越大,消去的变量数越多 。
需要指出,上述最小项的合并规则,对最大项的合并同样是适用的 。 只是因为最大项是与函数的 0值相对应,在卡诺图中则与 0格对应,因此,最大项的合并在卡诺图中是相邻的 0格圈在一起 。
2i
第 2章 逻辑代数基础合并规律
2个最小项合并,消去一个变量
4个最小项合并,消去两个变量
8个最小项合并,消去三个变量
个最小项合并,消去 k个变量若,则 n个变量全消去,
2k
kn? 1F !
第 2章 逻辑代数基础图 2-19 最小项合并规律
1
AB
C
00 01 11 10
0
1
1
( b )
AB
C
00 01 11 10
0
1 1 1
1
AB
CD
00 01 11 10
1
1
1
00
01
11
10
( c )
( a )
1
AB
CD
00 01 11 10
1 1
1 1
1
1 1
1 1
00
01
11
10
( d )
AC
AC
BC
BD AB
CD
00 01 11 10
1
1 1
1 1 1
1 1 1 1
1 1
00
01
11
10
( e )
A
BD
AB
D
第 2章 逻辑代数基础
2.6.4 用卡诺图化简逻辑函数
1.
在卡诺图上以最少的卡诺圈数和尽可能大的卡诺圈覆盖所有填 1的方格,即满足最小覆盖,就可以求得逻辑函数的最简与或式 。
化简的 一般步骤 是：
① 画出逻辑函数的 K图 。
② 先从只有一种圈法的最小项开始圈起,K圈的数目应最少 (与项的项数最少 ),K圈应尽量大 (对应与项中变量数最少 )。
大第 2章 逻辑代数基础
③ 将每个 K圈写成相应的与项,并将它们相或,便得到最简与或式 。 (新 )
圈Ｋ圈时应注意,根据重叠律 (A+A=A),任何一个 1格可以多次被圈用,
但如果在某个 K圈中所有的 1格均已被别的 K圈圈过,则该圈为多余圈 。 为了避免出现多余圈,应保证每个 K圈内至少有一个 1格只被圈一次 。 (全 )
④ Check if all,1” elements of the function to be
simplified have been covered by all circles selected.
第 2章 逻辑代数基础
【 例 2-1】 求 ) F= m(1,3,4,5,10,11,12,13)的最简与或式 。
解,① 画出 F的 K图 (见图 2-20)。
图 2-20 例 2-1的卡诺图
AB
CD
00 01 11 10
1
1 1
1 1
1 1
1
00
01
11
10
BC
ABD
ABC
第 2章 逻辑代数基础
② 画 K圈 。 按照最小项合并规律,将可以合并的最小项分别圈起来 。
根据化简原则,应选择最少的 K圈和尽可能大的 K圈覆盖所有的 1格 。 首先选择只有一种圈法的 BC,剩下四个 1格 (m1,m3,m10,m11)用两个 K圈 覆盖 。
可见一共只要用三个 K圈即可覆盖全部 1格 。
③ 写出最简式。
CBADBA,
CBADBACBF
第 2章 逻辑代数基础
【 例 2-2】 求 A B C DCABDCBDBACDBF
的最简与或式。
解,① 画出 F的 K图 。 给出的 F为一般与或式,将每个与项所覆盖的最小项都填 1,K图如图 2-21所示 。
图 2-21 例 2-2的卡诺图
A B
C D
0 0 0 1 1 1 1 0
1 1
1
1
1
1 1
1 1
0 0
0 1
1 1
1 0
( a )
A B
C D
0 0 0 1 1 1 1 0
1 1
1
1
1
1 1
1 1
0 0
0 1
1 1
1 0
( b )
第 2章 逻辑代数基础
② 画 K 。
③ 写出最简与或式 。
本例有两种圈法,都可以得到最简式 。
按图 2-21(a)圈法：
A B DDCBDCACBF
按图 2-21(b)圈法：
A C DCABDBACBF
该例说明，逻辑函数的最简式不是惟一的。
第 2章 逻辑代数基础
**【 例 2-3】 求的最简与或式 。
解,① 画 F的 K图 。
这是一个五变量逻辑函数,按五变量 K图中的编号填图,得出 F的 K图如图 2 - 22所示 。
)31,29,27,25,24,23,22,21,20,16,15,13,11,8,7,6,5,4,0(mF
第 2章 逻辑代数基础
1
AB C
DE
0 0 0
1 *1
1 1 *
1 1 *1
*1
00
01
11
10
1
1
1 1
1 1
1 1 1
1 *
0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 0
图 2-22 例 2-3的卡诺图第 2章 逻辑代数基础五,六变量的处理
)31,29,27,25,24,23,22,21,20,16,15,13,11,8,7,6,5,4,0(mF
断开小于 16的不变
③
①
② 大于等于 16的减去 16
0,4,5,6,7,8,9,11,13,15
④ 对②和 ③ 分别做两个四变量的 Karnaugh图
A A
⑤ F=AF(i<16)+AF(>=16)
⑥ 若有 A*Y+A*Y,则合并成 Y，等等。
第 2章 逻辑代数基础
② 画 K圈化简函数。
先找只有一种圈法的最小项：
覆盖；用余下覆盖；：用覆盖；：用覆盖；，：用覆盖；用、
ABEmm
EDCmm
CEmm
B D Emm
CBmmm
)31,29,27,25(
)24,16,8,0(
)31,29,23,21,15,13,7,5(
)3127,15,11(
)23,22,21,20,7,6,5,4(:
25
8
13
11
226
第 2章 逻辑代数基础
③ 写出最简式。
A B EEDCCEB D ECBF
如何判断得到的函数式是否为最简式呢? 下面从蕴含项的概念讨论最简式问题：
① 蕴含项 ( Implicant)。 组成逻辑函数的每一个与项
(积项 )称为该函数的蕴含项 。 它可以是最小项,也可以是合并项 。
第 2章 逻辑代数基础
② 本原蕴含项 (Prime Implicant)。 如果逻辑函数的一个蕴含项再也不能同该函数的其它蕴含项合并组成变量数更少的蕴含项,则称该蕴含项为本原蕴含项 。 实际上它对应着卡诺图中不能再扩大的合并项,
即最大卡诺圈 。
③ 实质本原蕴含项 (Essential Prime Implicant)。 不能被其它蕴含项所包含的本原蕴含项称为实质本原蕴含项 。 它对应着卡诺图中必不可少的最大卡诺圈,该圈至少包含了一个只有一种圈法的最小项 。
求本源蕰涵项集 最简与或式 (最简或与式 )
第 2章 逻辑代数基础例如,已知逻辑函数 F1,F2的卡诺图分别如图 2-23(a)、
(b)所示,化简 F1时只需用 3 个最大的 K圈就可以覆盖全部 1
格,如果用四个 K圈肯定有一个多余圈 。 从图 2-23(a)中看出,
合并项 AC为多余项,因为该圈中每个 1 格被圈了两次 。 因此可得出最简与或式为
CBDAABF1
化简图 2-23(b)的 F2,只用六个最大的 K圈覆盖所有的 1
格,观察每一个 K圈都有一个 1 格只被圈过一次,因此这六个 K圈都必须存在,最简与或式为
CDBADCADCABACBDBF2
第 2章 逻辑代数基础图 2-23 F1,F2的化简 K图
( a )
AB
CD
00 01 11 10
1
1 1
1 1
1
1 1
1 1
00
01
11
10
( b )
1
AB
CD
00 01 11 10
1
1 1 1
1 1
1
1
1 1
00
01
11
10
第 2章 逻辑代数基础
2,求最简或与式任何一个逻辑函数既可以等于其卡诺图上填 1的那些最小项之和,也可以等于其卡诺图上填 0的那些最大项之积,因此,如果要求出某函数的最简或与式,可以在该函数的卡诺图上合并那些填 0的相邻项 。 这种方法简称为圈 0合并,其化简步骤及化简原则与圈 1合并类同,只要按圈逐一写出或项,然后将所得的或项相与即可 。 但需注意,或项由 K圈对应的没有变化的那些变量组成,当变量取值为 0时写原变量,取值为 1时写反变量 。
第 2章 逻辑代数基础
【 例 2-4】 求 )13,11,9,7,6,5,4,3,1(mF 的最简或与式。
解：
① 画出 F的 K图 (见图 2-24)。
② 圈 K圈 。 圈 0合并,其规律与圈 1相同,即 K圈的数目应最少,K圈所覆盖的 0格应尽可能多 。 本例用三个 K圈覆盖所有 0格 。
③ 写出最简或与式。
))()(( CBADADBF
第 2章 逻辑代数基础图 2-24 例 2-4的卡诺图
0
AB
CD
00 01 11 10
1
1 0 0
1 1 1
1
0
1 0 1
1 0 0
00
01
11
10
第 2章 逻辑代数基础
【 例 2-5】 求 CCABADCBAF ))()(( 的最简或与式。
解,① 画出 F的 K图 。 本例给出的 F为一般或与式,因此将每个或项所覆盖的最大项都填 0,就可以得到 F的 K图如图
2-25所示 。
② 圈 K圈化简函数 。
③ 写出最简或与式。
))(( BADBACF
当需要将逻辑函数化为最简与或非式时,也可以采用合并 0格的方式,即在卡诺图上圈 0格,先求出 的最简与或式,然后根据 F=F再求出 F的最简与或非式 。
F
第 2章 逻辑代数基础图 2-25 例 2-5的卡诺图
AB
CD
00 01 11 10
0 0
0
0
0
0 0 0
0 0 0
00
01
11
10
第 2章 逻辑代数基础
2.7 非完全描述逻辑函数的化简
2.7.1 非完全描述的逻辑函数逻辑问题分为完全描述和非完全描述两种 。 如果对于输入变量的每一组取值,逻辑函数都有确定的值,则称这类函数为完全描述逻辑函数 。 如果对于输入变量的某些取值组合逻辑函数值不确定,即函数值可以为 0,也可以为 1(通常将函数值记为?或 × ),那么这类函数称为非完全描述的逻辑函数 。
第 2章 逻辑代数基础表 2-13 非完全描述逻辑函数真值表
A B C F
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
第 2章 逻辑代数基础无关项发生在以下两种情况：
① 由于某种条件的限制 (或约束 )使得输入变量的某些组合不可能出现,因而在这些取值下对应的函数值是,无关,紧要的,它可以为 1,也可以为 0。
② 某些输入变量取值所产生的输出并不影响整个系统的功能,因此可以不必考虑其输出是 0还是 1。
非完全描述逻辑函数一般用以下方法表示：
① 在真值表或 K图中填?或 ×,表示函数值为 0或 1均可。
② 在逻辑表达式中用约束条件来表示。
第 2章 逻辑代数基础例如,十字路口的交通灯规定红灯停,绿灯行,黄灯要注意 (即黄灯一亮,未过停车线的车辆也须停车 )。 若以变量 A、
B,C分别表示红,黄,绿灯的状态,且以灯亮为 1,灯灭为
0,用 F表示停车与否,且以停车为 1,通行为 0,则 F是 A,B、
C的函数 。 如果规定不允许有两个以上的灯同时亮,则 A,B、
C三个变量的取值组合只可能是 000,001,010,100,而不应出现 011,101,110,111这四种情况,即 A与 B,A与 C,B
与 C,A与 B与 C不可能同时为 1,所以 A,B,C是一组具有约束的变量,其相互约束关系可以表示为,AB=0,BC=0、
AC=0,ABC=0,即 AB+BC+AC+ABC=0,或写成 (3,5,6,7)=0。
式中的最小项就是我们所说的无关项 。
第 2章 逻辑代数基础由此可见,当约束条件满足时,这些无关项的值恒为 0，
如果将这些恒为 0的最小项加到逻辑函数式或从函数式中消去,都不会影响函数的逻辑功能和函数值,因此,我们可以将无关项对应的输出函数值视为 × 。 表 2-14写出了交通停车逻辑函数的真值表 。 该逻辑函数表达式可以写成：
0ACBCAB
CBACBAF
也可简写为
)7,6,5,3()1,0(
)7,6,5,3()4,2(
MF
mF
第 2章 逻辑代数基础
2.7.2
在非完全描述逻辑函数中,由于在无关项的相应取值下,
函数值随意取成 0或 1都不影响函数原有的功能,因此可以充分利用这些无关项来化简逻辑函数,即采用卡诺图化简函数时,可以利用? (或 × )来扩大卡诺圈 。
【 例 2-6】 化简上述交通停车逻辑函数 。
解：根据表 2-14交通停车逻辑函数的真值表画出该函数的卡诺图如图 2-26所示 。 在 K图上圈 1得
BAF
第 2章 逻辑代数基础图 2-26 例 2-6的卡诺图
0
AB
C
00 01 11 10
0
1
1 × 1
0 × × ×
第 2章 逻辑代数基础
【 例 2-7】 试化简逻辑函数 为最简或与式,并用与或非门实现电路 。
解：
① 画出 F的卡诺图如图 2-27(a)所示 。 是约束条件,在卡诺图中相应的位置填 × 。
② 圈 0求得 F 的最简与或式。
0
)8,6,4,2(
DCABCBA
mF
0 DCABCBA
ACABDF
③ 将函数 F变换为最简与或非式。
ACABDFF
第 2章 逻辑代数基础
④ 画出逻辑电路，如图 2-27(b)所示。
图 2-27 例 2-7的卡诺图
×
AB
CD
00 01 11 10
×
1 0 1
0 × 0
0
1
0 0 0
1 0 0
00
01
11
10
( a )
D ≥1&
( b )
B
C
A
F
第 2章 逻辑代数基础拾遗
1.化简方法,
A.代数法 B.卡诺图法
C.表格法 D.迭代一致法
2,5,6变量的函数的卡诺图法化简
3.真值表和卡诺图的深入理解
F,F 最小项 最大项 0 1
4.卡诺图的运算
12,,1 2,1 2,1 2F F F F F F F F F
等等
5.逻辑断语,因果表,真值表,卡诺图,表达式,逻辑图,电路图
6。 关于完全描述函数和非完全描述函数的补函数的注意：例如
(0,1,3,7),( 2,4,5,6 )F m F M
若
( 0,1,3,6 ) ( 7 ),
( 2,4,5,7 ),
( 2,4,5 ) ( 7 )
F m d
FM
F M d
7.卡诺图化简的步骤和要领,大,新全描述第 2章 逻辑代数基础继续
下一章将讨论用指定类型的门来实现一个逻辑函数,一般方法是,
1.若指定用”与 -非”实现
最好选最小项,读 1,得原函数,再两次取反变换即可
2.若指定用”或 -非”实现
最好选最大项,读 0,得原函数,再两次取反变换即可
3.若指定用”与 -或 -非”实现
最好选最小项,读 0,得反函数,取反得原函数
