基本逻辑电路的化简方法.docx
《基本逻辑电路的化简方法.docx》由会员分享，可在线阅读，更多相关《基本逻辑电路的化简方法.docx（27页珍藏版）》请在冰点文库上搜索。
基本逻辑电路的化简方法
基本逻辑电路的化简方法
第二章逻辑代数基础
2.1逻辑代数运算
提纲：
⏹逻辑变量与逻辑函数，
⏹逻辑代数运算，
⏹逻辑代数的公理和基本公式，
⏹逻辑代数的基本定理（三个），
⏹逻辑代数的常用公式。
2.1.1逻辑变量与逻辑函数
采用逻辑变量表示数字逻辑的状态，逻辑变量的输入输出之间构成函数关系。
逻辑常量：
逻辑变量只有两种可能的取值：
“真”或“假”，习惯上，把“真”记为“1”，“假”记为“0”，这里“1”和“0”不表示数量的大小，表示完全对立的两种状态。
2.1.2逻辑代数运算
基本逻辑运算——与、或、非；复合逻辑运算。
描述方法：
逻辑表达式、真值表、逻辑符号（电路图）。
定义：
真值表——描述各个变量取值组合和函数取值之间的对应关系。
逻辑电平——正逻辑与负逻辑。
2.1.3逻辑代数的公理和基本公式
2.1.3.1逻辑代数公理
有关逻辑常量的基本逻辑运算规则，以及逻辑变量的取值。
（1）常量的“非”逻辑运算
（2~4）常量的与、或逻辑运算
（5）逻辑状态只有”0”和”1”两种取值
2.1.3.2逻辑代数的基本公式（基本定律）
所谓“公式”，即“定律”，如表2.1：
表2.1逻辑代数的公式（基本公式部分）
组
名称
对偶的公式对
备注
1
01律
变量与常量
2
重叠律
同一个变量
3
互补律
原变量与反变量之间的关系
4
还原律
5
交换律
6
结合律
7
分配律
8
反演律
DeMorgan公式
2.1.3.3逻辑代数的三个基本定理
所谓“定理”，即代数运算规则。
基本的三个定理：
⏹代入定理——在任何一个包含逻辑变量A的逻辑等式中，若以另外的逻辑式代入式中的所有A的位置，则等式依然成立。
，
⏹反演定理，
⏹对偶定理。
2.1.3.3.1反演定理
所谓“反演定理”，得到逻辑函数的“反”的定理。
定义（反演定理）：
将函数Y式中的所有…
⏹（基本运算符号）“与”换成“或”，“或”换成“与”；
⏹（逻辑常量）“0”换成“1”，“1”换成“0”；
⏹原变量换成反变量，反变量换成原变量；
注意：
●变换时要保持原式中逻辑运算的优先顺序；
●不属于单个变量上的反号应保持不变；
则，所得到的表达式是
的表达式。
例2.1:
已知
，求。
解：
（利用反演定理）
例2.2:
已知
，求
。
解：
（利用反演定理）
例2.3:
（反演律和反演定理），已知Y=A（B+C）+CD，求
。
解：
（方法一、用反演定理）
解：
（方法二、反复用反演律）
注意：
对等式两端根据反演定理进行操作是整体性的“原子操作”，不允许在进行操作的同时，对局部的逻辑项进行所谓的“代入”、“反演律”等操作。
2.1.3.3.2对偶定理
定义（对偶定理）：
若两个逻辑式相等，则它们的对偶式也相等。
定义（对偶式）：
将逻辑式中的…
⏹（基本运算符号）“与”换成“或”，“或”换成“与”；
⏹（逻辑常量）“0”换成“1”，“1”换成“0”；
⏹变量保持不变；
⏹注意：
原表达式中的运算优先顺序保持不变。
2.1.4逻辑代数常用公式
如表2.2：
表2.2逻辑代数的公式（常用公式部分）
组
杜撰的名称
对偶的公式对
备注和注记标记
9
吸收法
A+AB=A
两个乘积项相或，其中一项以另一项作为因子，则该项是多余的。
吸收冗余项
10
消元法
消除冗余因子
11
推广的消元/吸收法
反用消元法，再用吸收法
12
推广的消元/吸收法
13
另一种形式的吸收法
14
另一种形式的消元法
说明：
（常用公式的语言叙述）
⏹“吸收法”——两个与项（“乘积项”）相或（“加”），如果其中一项中以另一项为因子，则该项为冗余项；
⏹“消元（因子）法”——两个与项相或，如果其中一项取反后为另一项的因子，则该因子是多余的；
⏹推广的消元/吸收法——三个与项相或，其中两个乘积项分别包含原变量与反变量作为因子，并且它们的其余部分作为因子组成第三个乘积项（或作为第三个乘积项的部分因子），则第三个乘积项是多余的。
2.1.4.1案例研究——逻辑代数常用公式的证明
证明的手段：
⏹公理和运算法则，
⏹定理——代入、反演、对偶，
⏹基本公式和常用公式。
例如：
公式（9）“吸收法”
A+AB=A（1+B）=AB，分配律、01律
例如：
公式（10）证法一
采用：
反用或对与的分配律
例如：
公式（10）证法二
的对偶式←→
由：
，AB的对偶式A+B，则根据对偶定理：
成立。
例如：
公式（11）
--（代入定理意义下的吸收律）→=
2.1.5异或代数
⏹三种基本逻辑运算——“与”、“或”、“非”（复合使用）可以表示出任何逻辑问题；
⏹基本的复合逻辑——“与非”、“或非”、“与或非”，用其中的任何一种就能描述任何逻辑问题；
⏹异或代数——“异或”（exclusive-OR）和“同或”（coincidence-OR）逻辑，虽然仅用它们不能描述所有的逻辑问题，但是它们是两种重要的复合逻辑。
2.1.5.1“异或”和“同或”的性质
异或（同或）代数的基本公式：
（1）交换律
（2）结合律
（3）“分配律”
⏹“与”对“异或”的分配律：
⏹“或”对“同或”的分配律：
A+B⊙C=（A+B）⊙（B+C）
（4）反演律
⊙
=A⊙B
A⊙B–（取反）→=
=
（5）调换律（因果互换关系）
两个逻辑变量（可以推广到多个，并且可以是常量）异或（同或）运算得到的输出结果，以另一个逻辑变量表示（即：
“果”），构成逻辑等式，该逻辑变量与异或（同或）运算中的任意逻辑变量的位置相调换，得到的逻辑等式仍成立。
例如：
奇校验的编码端，校验比特为C，
C=bn-1
bn-2
…
b1
1
奇校验的校验端，如果校验成功，应有
1=bn-1
bn-2
…
b1
C
（6）移非律（特例：
“消非律”）
（7）换门律
=A⊙B
⊙B=
不用死记，异或（同或）运算的定义决定，也可使用01律证明。
（8）01律
0
A=A，1
A=
（模2加1相当于求反）
1⊙A=A，0⊙A=
（9）奇偶律
对于异或：
A
A=0
A
A
A=A
……
对于同或
A⊙A=1
A⊙A⊙A=A
……
（10）异或逻辑和同或逻辑的关系
多个逻辑变量进行异或（同或）运算的逻辑表达式，如果将异或（同或）运算符转换为同或（异或）运算符，则：
⏹奇数个逻辑变量，运算符
和⊙互换时，逻辑关系不变；
⏹偶数个逻辑变量，运算符
和⊙互换时，变换后的结果取反。
2.2逻辑函数的表示方法及其标准形式
2.2.1逻辑函数的表示方法
⏹逻辑表达式
⏹真值表
⏹卡诺图（邻接真值表）
⏹逻辑图
⏹波形图*
表示方法之间的转换（如：
图2.1）
图2.1逻辑函数表达方法之间的转换
2.2.2逻辑函数的两种标准形式
⏹标准“与或”表达式（最小项之和）
⏹标准“或与”表达式（最大项之积）
2.2.2.1最小项
定义（最小项）：
在含有n个变量的逻辑函数中，
⏹包含全部n个变量的乘积项（与项），
⏹其中每个变量必须而且只能以原变量或反变量的形式出现一次。
最小项也被称为“标准乘积项”。
最小项的编码——使最小项为1的逻辑变量的取值，即：
将变量的由高到低排列，原变量对应“1”，反变量对应“0”，最小项以变量所对应的自然二进制数编码，记为：
“mi”。
最小项的性质：
⏹每个最小项与变量的一组取值相对应，只有该组取值才能使其为“1”；
⏹全体最小项之和恒为“1”；
⏹任意两个不同的最小项的乘积恒为“0”。
2.2.2.2标准与或表达式
定义（标准与或表达式）：
每个与项都是最小项的与或表达式。
也被称为“最小项之和表达式”。
从真值表，以及一般与或表达式，转换成标准“与或”表达式的方法如图2.2。
图2.2从真值表和一般与或表达式转换为标准与或表达式
对于任意一个逻辑函数，它的标准与或表达式（不考虑与项的顺序）是唯一的。
说明：
熟练后，从一般“与或”表达式转换为标准“与或”表达式，可由最小项的编码规则得到。
例如：
2.2.2.3最大项
定义（最大项）：
在一个有n个变量的逻辑函数中，
⏹包含全部n个变量的和项（或项），
⏹其中每个变量必须并且只能以原变量或反变量的形式出现一次。
最大项的编码与逻辑变量取值的对应关系——使最大项为0的逻辑变量的取值，即：
对于或项，原变量对应取值为“0”，反变量对应取值为“1”。
最大项的性质：
⏹每个最大项与变量的一组取值相对应，只有该组取值才能使其为“0”；
⏹全体最大项之积恒为“0”，即：
；
⏹任意两个不同的最大项之和恒为“1”，即：
，
；
⏹最大项和最小项之间的关系：
。
2.2.2.4标准或与表达式
定义（标准或与表达式）：
每个或项都是最大项的“或与”表达式被称为标准“或与”表达式，也被称为最大项之积表达式。
2.2.2.4.1从真值表求标准或与表达式
步骤（求标准或与表达式）：
1）在真值表中找出使逻辑函数Y为0的行，
2）对于Y=0的行，由变量的取值“0”、“1”对应最大项“原”、“反”变量的关系，写出逻辑变量表达得标准或与表达式，
3）确定最大项的编号——
⏹方法一、由最大项定义，根据最大项编号与变量取值的对应关系，
⏹方法二、真值表中Y=0的行对应的是
，利用
关系，对应得到最大项Mi的编号，。
说明：
真值表中变量取值组合隐含着与最小项的对应关系，得到最大项的编号只不过根据
的对应关系。
说明：
也可以先根据
的对应关系，确定所含最大项的编号，再根据最大项编号和变量取值的对应关系，写出以逻辑变量表达的最大项之积表达式。
2.2.2.4.2从一般逻辑表达式得到标准或与表达式
图2.3从一般逻辑表达式得到标准或与表达式
2.2.2.5标准与或表达式/标准或与表达式的转化
如果函数的标准与或表达式为：
，则函数的标准或与表达式则为：
。
推导：
，由最小项的性质
，则：
1=
由DeMorgan公式，
，可由标准与或表达式，求标准或与表达式。
2.3逻辑函数的化简
⏹逻辑函数的最简形式
⏹公式法化简逻辑函数
⏹卡诺图法化简逻辑函数
●卡诺图
●卡诺图化简法——化简为最简与或表达式
●用卡诺图化简法求最简或与表达式
●具有无关项的逻辑函数的化简
⏹逻辑函数形式的转换
2.3.1逻辑函数的最简形式
与或表达式是最常用的表达式，由它容易推导出其它表达形式。
判别条件——与或表达式为最简的条件：
⏹乘积项（与项）的数目最少，（首要条件）
⏹每个乘积项中的因子（逻辑变量）最少。
2.3.2公式法化简逻辑函数
化简为最简与或式。
公式法化简没有固定的方法，这些方法归纳起来大致可以包括“并项、吸收、消因子、消项、配项”（这些名称是杜撰的，切不可生搬硬套，掌握基本思想即可），化简的方法不是唯一的。
2.3.2.1并项法
利用互补律，将两项合为一项，合并时消去一个逻辑变量（一个原变量，一个反变量）
例如：
2.3.2.2吸收法
利用公式A+AB=A，吸收掉冗余的乘积项。
例如：
2.3.2.3消因子法
利用公式
，消去多余的因子。
例如：
2.3.2.4消项法
利用常用公式
和
，消去多余的乘积项
例如：
例如：
2.3.2.5配项法
根据基本公式A+A=A，在式中重复某项，再化简；或者根据基本公式
，在式中某项乘以
，再化简。
例如：
本例只是演示，实际上如果先对后两项并项，然后消因子，更加简单。
2.3.3卡诺图法化简逻辑函数
2.3.3.1卡诺图
卡诺图是由美国工程师维奇（Veitch）和卡诺（KarnaughM）于1953年分别从不同角度提出的。
定义（卡诺图，最小项卡诺图）将n个变量的所有最小项（miniterm）分别以一个个方格的形式表示，并使具有逻辑相邻性的最小项在几何上也“相邻”地排列，所得的图形被称为最小项卡诺图。
卡诺图也是一种特殊的真值表——邻接真值表：
⏹几何相邻（在几何位置上，应将卡诺图看成上下/左右、四角闭合的图形）的小方格具有逻辑相邻性。
（便于用互补律以作图的方式化简）
定义（最小项的逻辑相邻性）两个最小项只有一个逻辑变量的取值不同。
2.3.3.1.1卡诺图的构成与特点
例如：
（四变量卡诺图，如图2.4）
图2.4四变量卡诺图
例如：
（五变量卡诺图，如图2.5）
图2.5五变量卡诺图
此时，仅用几何图形在二维空间的相邻性来表达逻辑相邻性已经不够了，在五变量卡诺图中，（两个4×4卡诺图的）分界线为轴的轴对称的小方格也具有逻辑相邻性。
卡诺图的特点：
⏹卡诺图中的小方格数等于最小项总数，若逻辑变量的数目为n，则小方格数为2n个——
●纵横两侧标注是逻辑变量的取值组合，“0”和“1”表示使方格对应的最小项为1的变量取值；同时，
●取值组合“0”、“1”的自然二进制数值就是最小项的编号。
⏹任何一个n变量的逻辑函数均可以由n变量最小项卡诺图表示——
●逻辑函数等于卡诺图中填入“1”的小格（即：
“1格”）所对应的最小项之和。
⏹卡诺图是“邻接真值表”，
●变量的取值按照格雷循环码排列，因此
●卡诺图的逻辑相邻性与几何位置相邻性是一致的；
●注意，在几何位置上，应将卡诺图看成上下/左右，四角闭合的图形。
（五变量包括分界轴对称）
2.3.3.1.2根据逻辑函数填写卡诺图
⏹步骤一（得到标准与或表达式）、若已知逻辑函数的表达式，可首先把函数写成最小项之和的形式（标准与或表达式）；然后，
⏹步骤二（填写卡诺图）、在卡诺图上与这些最小项对应的位置上填入1，在其余位置上填入0，这样就可以得到该逻辑函数的卡诺图。
例2.5:
（根据逻辑函数填写卡诺图）
解:
（步骤1-1）反复使用反演律，脱去“非”号，直到最后只有单变量上有非号；
（步骤1-2）用乘对加的分配律，脱去括号，直到最后得到一个“与或”表达式；
（步骤1-3）在“与或”表达式中，若一个乘积项缺少某变量因子，则利用互补律配项，并用所配的项去乘该项；如缺少两个以上的项，则要反复用互补律配项，直到得到最小项之和的表达式（还要删除重复的最小项）。
（步骤2-1）逻辑变量按照位置计数法排列，以自然二进制数对应最小项的编号；
（步骤2-2）最小项为1的取值组合，会使逻辑函数为1，所以在存在的最小项的对应方格中标注“1”（其余方格填“0”）。
说明：
熟练后，可以根据与或表达式“看图说话”地直接填写卡诺图，不仅效率高，而且不容易出错。
例2.6:
（根据逻辑函数填写卡诺图）
解:
2.3.3.1.3由卡诺图得到标准或与表达式
根据卡诺图既可写出标准“与或”表达式，也可写出标准“或与”表达式（参见§2.3.3）。
2.3.3.2卡诺图化简法
卡诺图化简逻辑函数的依据：
由于卡诺图上几何位置的相邻性与逻辑相邻性是一致的，因而从卡诺图上能直观地找出具有相邻性的最小项，并根据互补律将其合并化简。
⏹几何相邻的两个方格（包括上下闭合、左右闭合、轴对称）所代表的最小项只有一个变量不同；
⏹根据互补律，当方格为1（“1”格），且两个“1”格相邻时，对应的最小项就可以加以合并，消去一对原变量与反变量，合并后只剩公共因子。
⏹多于多个相邻的方格，反复利用合并法则，保留相同变量，消除相反变量。
问题：
⏹如何“直观地”找到可以合并的最小项？
⏹如何选择可以合并的最小项，以达到最简？
2.3.3.2.1最小项卡诺图逻辑化简规则
问题1、如何“直观地”找到可以合并的最小项？
理论：
合并化简的理论支持（互补律）。
技巧：
圈定卡诺圈的技巧。
规则1：
卡诺图中两个相邻的“1格”的最小项可以合并成一个与项，并消去一个变量。
例如：
Y=
化简为：
化简为：
化简为：
规则2：
卡诺图中四个相邻“1格”的最小项可以合并成一个与项，并消去两个变量。
规则3：
卡诺图中八个相邻的“1”格的最小项可以合并成一个与项，并消去三个变量。
2.3.3.2.2用最小项卡诺图化简法求最简与或表达式
步骤：
（1）建立逻辑函数的卡诺图；
（2）合并最小项；→关键在于：
如何选择可合并的最小项，以达到最简（问题2）
（3）写出最简与或表达式
问题2：
如何选择可合并的最小项，以达到最简？
理论：
找到实质蕴涵项
技巧：
选择卡诺圈的技巧：
使得
⏹圈的个数尽可能少（首要目标），
⏹圈的面积尽可能大，
⏹每个圈中至少应包含一个新的“1格”（最小项卡诺图）。
例2.7:
（卡诺图化简求最简与或表达式）
Y（A,B,C,D）=Σm（1,2,4,9,10,11,13,15）
例2.8:
（例题并讲解，什么是本源蕴涵项，如何从本源蕴涵项中选择实质蕴涵项）
写出最简与或逻辑表达式
技巧：
圈的个数尽可能少（首要目标）
例2.9:
（例题并讲解：
本源蕴涵项）
技巧：
圈的面积尽可能大
例2.10:
（例题并讲解：
实质蕴涵项）
技巧：
每个圈至少应包含一个新的“1格”
卡诺图化简得到的最简式不一定是唯一的。
2.3.3.3用卡诺图化简法求最简或与表达式
方法：
⏹方法一、合并反函数的最小项，
⏹方法二、合并原函数的最大项（最大项卡诺图，由于最大项卡诺图的编码规则与习惯的正逻辑不同，故而容易出错，主要选用方法一）。
注意：
反函数可以用真值表或者卡诺图中Y=0对应的最小项之和表示。
方法一：
1）画出逻辑函数Y的卡诺图，
2）合并0方格（俗称“0格”），求得反函数的最简与或表达式，
3）对反函数的最简“与或”式进行反演变换（DeMorgan公式），得到函数的最简“或与”式。
例2.11:
（卡诺图化简求最简与或表达式）
Y（A,B,C,D）=Σm（0,1,2,5,8,9,10）
2.3.3.4具有无关项逻辑函数的化简
无关项的概念——无关项包括约束项和任意项，
⏹约束项：
输入逻辑变量的某些取值组合禁止出现（由外部的机制约束，以保证一定不会出现）；
⏹任意项：
一些取值组合出现时，输出逻辑值可以是任意的；
这些取值组合对应的最小项称为约束项或任意项，统称为“无关项”。
在卡诺图的方格中，常使用符号“×”（或“φ”）表示无关项。
无关项在化简逻辑函数中的应用：
⏹合理利用无关项，一般可以得到更加简单的化简结果，
⏹在卡诺图中，无关项“×”可以被作为“1”，也可以被作为“0”，
⏹目的：
加入的无关项应该与函数式尽可能多的最小项具有逻辑相邻性。
例2.10:
（例题并讲解：
具有无关项的逻辑函数化简）
Y（A,B,C,D）=Σm（1,3,7,11,15）+Σd（0,2,5）
Y=
问题：
利用卡诺图合并包含无关项的最小项，如何确定：
⏹卡诺圈包含无关项——将无关项“×”作为“1”，认为函数式包含此无关项；还是，
⏹卡诺圈不包含无关项——将无关项“×”作为“0”，认为函数式不包含此无关项？
卡诺圈包含无关项的原则：
应使——
⏹相邻最小项矩形组合（“卡诺圈”）的面积最大，并且，
⏹组合（“卡诺圈”）的数目最少。
2.3.4逻辑函数形式的转换
常用的复合逻辑：
与非、或非、与或非，其中任一种，都可以表示所有的逻辑问题。
最简与或表达式可用与门和或门实现，但在数字电路系统中，广泛使用的有与非门、或非门，以及与或非门。
问题：
如何求得“与非——与非”、“或非——或非”、“与或非”形式的最简逻辑表达式？
（如图2.6）
图2.6逻辑函数形式的转换
2.3.4.1“与或”到“与非——与非”的转换
将与或表达式二次求反，再使用一次DeMorgan公式，就可以得到“与非——与非”表达式。
例如：
2.3.4.2“与或”到“与或非”的转换
先求其反函数的最简与或表达式，然后再求反，就可以得到“与或非”表达式。
例如：
2.3.4.3“与或”到“或非——或非”的转换
需要先求得最简或与表达式，再求得“或非——或非”表达式。
步骤：
1）作出原函数的卡诺图，用合并“0格”的方法先求出其反函数的最简与或表达式；
2）对所得到的“与或”表达式求反，得到原函数的最简或与表达式；
3）二次求反，对于内层反号利用DeMorgan公式，可以得到原函数的“或非——或非”表达式。
例如：
或者：
对于步骤2）和3），可以改成：
2）与或形式的反函数表达式两端分别求反；
3）在对各个乘积项应用DeMorgan公式（反用）。
如上例：
则有——
例2.11:
已知
，且有（外部）约束条件
，请用最简的“或非”逻辑实现Y的逻辑函数。
2.3.5Q-M列表化简法
发明人QuineW.V.（奎恩）和McCluskeyE.J.（麦克拉斯基）
Q-M列表法的步骤和原理：
⏹第一次列表：
列表分次合并最小项，找到素项（本源蕴涵项）；
⏹第二次列表：
列出“最小项——素项”交叉列表，选定实质蕴涵项。
升级会员 