《数字电路第二章逻辑代数基础.ppt》由会员分享,可在线阅读,更多相关《数字电路第二章逻辑代数基础.ppt(79页珍藏版)》请在金锄头文库上搜索。
1、 第二章第二章 逻辑代数基础逻辑代数基础 要求:熟练掌握逻辑代数的基本定理和常用公式;逻辑问要求:熟练掌握逻辑代数的基本定理和常用公式;逻辑问 题的描述方法;逻辑函数的化简与变换。题的描述方法;逻辑函数的化简与变换。 逻辑是指事物因果之间所遵循的规律。逻辑代数逻辑是指事物因果之间所遵循的规律。逻辑代数( (布布尔代数)是按一定逻辑规律进行运算的尔代数)是按一定逻辑规律进行运算的代数代数。 在逻辑代数中,变量的取值只有两种,即逻辑在逻辑代数中,变量的取值只有两种,即逻辑0 0和逻和逻辑辑1 1。但必须指出,这里的逻辑。但必须指出,这里的逻辑0 0和和1 1本身并没有数值的本身并没有数值的意义,它
2、代表事物矛盾双方的两种状态,意义,它代表事物矛盾双方的两种状态,是是与与非非等。等。在逻辑代数中,在逻辑代数中,等号等号只表示逻辑功能上的相同,而不只表示逻辑功能上的相同,而不表示数值相等。表示数值相等。 逻辑代数的三种基本运算逻辑代数的三种基本运算 一、逻辑变量与逻辑函数一、逻辑变量与逻辑函数1 1、逻辑变量:、逻辑变量: 逻辑代数中的变量称为逻辑变量,一般用大写字逻辑代数中的变量称为逻辑变量,一般用大写字母母A A、B B、C C、表示,逻辑变量的取值只有两种,即逻表示,逻辑变量的取值只有两种,即逻辑辑0 0和逻辑和逻辑1 1。 0 0和和1 1称为逻辑常量称为逻辑常量。2 2、逻辑函数:
3、、逻辑函数: 逻辑函数与普通代数中的函数相似,它是逻辑函数与普通代数中的函数相似,它是随自变量随自变量的变化而变化的因变量。的变化而变化的因变量。因此,如果用自变量和因因此,如果用自变量和因 变变量分别表示某一事件发生的量分别表示某一事件发生的条件和结果条件和结果,那么该事件的,那么该事件的因果关系就可以用逻辑函数来描述。因果关系就可以用逻辑函数来描述。 若若输输入入逻逻辑辑变变量量A A、B B、C C、 的的取取值值确确定定后后,其其输输出出逻逻辑辑变变量量F F的的值值也也被被惟惟一一地地确确定定了了,则则可可以以称称F F是是A A、 B B、C C、 的逻的逻辑函数,辑函数, 并记为
4、:并记为: 二、三种基本运算二、三种基本运算( (与、或、非)与、或、非) 1 1、与运算、与运算( (逻辑乘逻辑乘) ) 只只有有当当决决定定一一事事件件结结果果的的所所有有条条件件同同时时具具备备时时,结结果果才才能能发发生生。例例如如串串联联开开关关电电路路中中,只只有有在在开开关关A A和和B B都都闭闭合合的的条条件件下下,灯灯F F才才亮亮,这这种种灯灯亮亮与与开开关关闭闭合合的的关系就称为关系就称为“与与”逻辑逻辑。 A A、真值表:(输入与输出的关系表格真值表:(输入与输出的关系表格) )设设开开关关A A、B B闭闭合合为为1 1,断断开开为为0 0,设设灯灯F F亮亮为为1
5、 1,灭灭为为0 0,则,则F F与与A A、B B的与逻辑关系可用真值表来描述。的与逻辑关系可用真值表来描述。 B B、与逻辑表达式与逻辑表达式 : F=AB 注:符号注:符号“”表示逻辑乘,常省去符号表示逻辑乘,常省去符号“”。有些。有些 也采用也采用、 及及& &等符号来表示逻辑乘。等符号来表示逻辑乘。C C、逻辑符号:逻辑符号:实现与逻辑的单元电路称为与门,其逻辑符号实现与逻辑的单元电路称为与门,其逻辑符号如图所示:如图所示:2 2、或或运算运算( (逻辑逻辑加加) ) 决决定定某某一一结结果果的的所所有有条条件件中中,只只要要有有一一个个成成立立,结结果果就会发生。就会发生。例如并联
6、开关电路中,只要有一个开例如并联开关电路中,只要有一个开关关A A 或或B B闭闭合合的的条条件件下下,灯灯F F就就亮亮,这这种种灯灯亮亮与与开开关关闭闭合合的的关关系就称为系就称为“或或”逻辑。逻辑。 A A、真值表:(输入与输出的关系表格真值表:(输入与输出的关系表格) )设设开开关关A A、B B闭闭合合为为1 1,断断开开为为0 0,设设灯灯F F亮亮为为1 1,灭灭为为0 0,则,则F F与与A A、B B的或逻辑关系可用真值表来描述。的或逻辑关系可用真值表来描述。 B B、或逻辑表达式:或逻辑表达式: F F =A+B=A+B 注:或逻辑也称或运算或逻辑加。符号注:或逻辑也称或运
7、算或逻辑加。符号“+ +”表示逻表示逻 辑加。有些也采用辑加。有些也采用、等符号表示逻辑加。等符号表示逻辑加。 C C、逻辑符号:逻辑符号:实现或逻辑的单元电路称为或门,其逻辑符号实现或逻辑的单元电路称为或门,其逻辑符号如图所示:如图所示:3. 3. 非运算非运算( (逻辑反逻辑反) ) 非非运运算算( (逻逻辑辑反反) )是是逻逻辑辑的的否否定定:当当条条件件具具备备时时,结结果果不不会会发发生生;而而条条件件不不具具备备时时,结结果果一一定定会会发发生生。例例,在在图图示示的的开开关关电电路路中中,只只有有当当开开关关A A断断开开时时,灯灯F F才才亮亮。这种结果总是同条件相反的这种结果
8、总是同条件相反的逻辑关系称为非逻辑。逻辑关系称为非逻辑。 A A、真值表真值表: : B B、逻辑表达式逻辑表达式: : 通常称通常称A A为原变量,为原变量,A A为反变量。为反变量。C C、逻辑符号:逻辑符号:实现非逻辑的单元电路称为非门,其逻辑符号实现非逻辑的单元电路称为非门,其逻辑符号如图所示:如图所示: 2 2 逻辑代数的基本定律和规则逻辑代数的基本定律和规则一、基本定律一、基本定律 1 1、变量和常量的关系式、变量和常量的关系式 逻辑变量的取值只有逻辑变量的取值只有0 0和和1 1,根据三种基本运算的,根据三种基本运算的定义,可推得以下关系式。定义,可推得以下关系式。 0-10-1
9、律律: A0 =0 A+1 =1自等律自等律: A1 =A A+0 =A重叠律重叠律: AA =A A+A =A互补律互补律: AA =0 A+A =1 2 2、与普通代数相似的定律与普通代数相似的定律 交换律交换律: AB=BA A+B=B+A 结结合合律律: (AB)C=A(BC) (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) =AA+A
10、B+AC+BC =A+AB+AC+BC =A(1+B+C)+BC=A+BC 因此有因此有 A+BC=(A+B)(A+C)3 3、逻辑代数中的特殊定律逻辑代数中的特殊定律 反演律:反演律: 还原律:还原律:反演律证明反演律证明二、三个重要规则二、三个重要规则 1. 1. 代入规则代入规则 任任何何一一个个逻逻辑辑等等式式,如如果果将将等等式式两两边边所所出出现现的的某某一一变变量量都都代代之之以以同同一一逻逻辑辑函函数数,则则等等式式仍仍然然成成立立,这这个个规规则则称称为为代代入入规规则则。因因为为逻逻辑辑函函数数与与逻逻辑辑变变量量一一样,只有样,只有0 0、1 1两种取值。两种取值。AB0
11、 00 11 01 11110111010001000 例如:已知例如:已知A+B=AB( (反演律反演律) ),若用,若用F F= =B+CB+C代替等式代替等式 中的中的B B,则可以则可以得到适用于多变量的反演律。得到适用于多变量的反演律。 即:即: 2 2、反演规则、反演规则 如如果果将将逻逻辑辑函函数数式式F F中中所所有有的的算算符符“”换换成成“+ +”, “+ +”换换成成“”,常常量量“0 0”换换成成“1 1”,“1 1”换换成成“0 0”,原原变变 量量换换成成反反变变量量,反反变变量量换换成成原原变变量量,则则所所得得到到的的就就是是F F。F F 称称为为原原函函数数
12、F F的的反反函函数数,或或称称为补函数。为补函数。 反反演演规规则则是是反反演演律律的的推推广广,运运用用它它可可以以简简便便地地求求出出一个函数的反函数。一个函数的反函数。 例A、 B、 注:运用反演规则时应注意两点:注:运用反演规则时应注意两点:A A、不能破坏原式的运算顺序不能破坏原式的运算顺序先算括号里的,先算括号里的, 然后然后 按按“先与后或先与后或”、从左到右的原则运算。、从左到右的原则运算。B B、在两个或两个以上变量上面的非号应保持不变。在两个或两个以上变量上面的非号应保持不变。 3 3、对偶规则、对偶规则 A A、 如如果果将将逻逻辑辑函函数数表表达达式式F F中中所所有
13、有的的算算符符“”换换成成“+ +”, “+ +”换换 成成 “”, 常常 量量 “0 0”换换 成成 “1 1”,“1 1”换换成成“0 0”,而而变变量量保保持持不不变变,则则得得出出的的逻逻辑辑函函数数式就是式就是F F的对偶的对偶 式,记为式,记为F F(或或F F * *) )。 例如例如: B B、任何逻辑函数式都存在着对偶式。若任何逻辑函数式都存在着对偶式。若原等式成立,原等式成立, 则对偶式也一定成立则对偶式也一定成立。即,如果。即,如果F F= =G G ,则,则F F=G G 。 注意:由原式求对偶式时,运算的优先顺序不能改变,注意:由原式求对偶式时,运算的优先顺序不能改变
14、, 且式中的非号也保持不变。且式中的非号也保持不变。 用用公公式式法法化化简简与与或或式式较较方方便便,但但化化简简或或与与式式较较困困难难。此时可利用对偶规则来进行化简。此时可利用对偶规则来进行化简。三、若干常用公式三、若干常用公式 1 1、合并律:、合并律: A+ABA+AB= =A A证:证: A+AB=A(A+AB=A(1 1+B)=A+B)=A1 1=A=A 2 2、吸收律:、吸收律: A+AB=A+B A+AB=A+B 证:证: A+B=(A+A)(A+B)A+B=(A+A)(A+B) =A+AB +AB=A +AB=A+AB +AB=A +AB 在在一一个个与与或或表表达达式式中
15、中,如如果果一一个个乘乘积积项项( (如如A A) )取取反反后后是是另一个乘积项另一个乘积项( (如如AB)AB)的因子,则此因子的因子,则此因子(A)(A)是多余的。是多余的。 C、AB+AC+BC=AB+AC 证证: AB+AC+BC= AB+AC+(A+A)BC =AB+AC+ABC+ABC= AB+AC AB+AC+BCD=AB+AC 在在一一个个与与或或表表达达式式中中,如如果果两两个个乘乘积积项项中中的的部部分分因因 子子互互补补( (如如ABAB项项和和ACAC项项中中的的A A和和A)A),而而这这两两个个乘乘积积项项中中的的其其余余因因子子( (如如B B和和C)C)都都是
16、是第第三三个个乘乘积积项项中中的的因因子子,则则这这个个第三项是多余的。第三项是多余的。 推广:推广: AB+AC+BCDEF =AB+AC 3 3 复复 合合 逻逻 辑辑一、复合逻辑运算和复合门一、复合逻辑运算和复合门1 1、与非、与非、 或非、或非、 与或非逻辑运算与或非逻辑运算 F=AB F=A+B F=AB+CD2 2、异或和同或逻辑运算、异或和同或逻辑运算 A A、异或逻辑:当两个输入变量相异时,输出为异或逻辑:当两个输入变量相异时,输出为1 1; 相同时输出为相同时输出为0 0。 逻辑表达式:逻辑表达式: B B、同或逻辑:当两个输入变量相同时输出为同或逻辑:当两个输入变量相同时输
17、出为1 1; 相异时输出为相异时输出为0 0。 逻辑表达式:逻辑表达式:注:异或等价于注:异或等价于 真值表:真值表: 同或的非,同或的非, 反之也成立。反之也成立。 C C、异或门和同或门的逻辑符号:异或门和同或门的逻辑符号: ( (a a) ) 异或门;异或门; ( (b b) ) 同或门同或门 D D、常用异或和同或运算公式:常用异或和同或运算公式: (A(A的个数为偶数的个数为偶数) )1)、 (A(A的个数为奇数的个数为奇数) ) 2 2)、)、常用异或和同或运算公式常用异或和同或运算公式(非常重要)(非常重要)3 3)实际:异或(同或)门只有)实际:异或(同或)门只有2 2个引脚,
18、因此在由多个引脚,因此在由多个变量构成的异或(同或)式中,必须两两运算。个变量构成的异或(同或)式中,必须两两运算。4 4)异或门的特殊应用:)异或门的特殊应用: 可以做传输门(可以做传输门(a)a)及非门(及非门(b)b)。 二、逻辑运算符的完备性二、逻辑运算符的完备性 1 1、n n变量的所有逻辑函数都可以用变量的所有逻辑函数都可以用n n个变量及一组逻辑个变量及一组逻辑 运算符运算符“、 + +、 - -”来构成,来构成, 因此称因此称“、 + +、 - -”运算符是一组完备集。运算符是一组完备集。 “与非与非”、 “或非或非”、 “与或非与或非”运算中的任何一种都能单独实现运算中的任何
19、一种都能单独实现“与、或、与、或、非非”运算,这三种复合运算每种都是完备集,而且实现运算,这三种复合运算每种都是完备集,而且实现函数只需要一函数只需要一种规格的逻辑门。种规格的逻辑门。2 2、逻辑函数式的五种形式:、逻辑函数式的五种形式: A A、与或式与或式B B、或与式或与式C C、与非与非式与非与非式D D、或非或非式或非或非式E E、与或非式与或非式 3 3、逻辑函数的五种形式逻辑电路、逻辑函数的五种形式逻辑电路 4 4 逻辑函数的两种标准形式逻辑函数的两种标准形式 一、最小项和最小项表达式一、最小项和最小项表达式 1 1、最小项、最小项 n n个个变变量量的的最最小小项项是是n n个
20、个变变量量的的“与与项项”,其其中中每每个个变变量量都都以以原原变变量量或或反反变变量量的的形形式式出出现现一一次次,n n个个变变量量的的最最小小项项共共有有2 2n n个个。原原变变量量用用“1”1”表表示示,反反变变量量用用“0”0”表示。表示。A A、三变量逻辑函数的最小项三变量逻辑函数的最小项真值表:真值表: B B、最小项具有以下性质:最小项具有以下性质: 1 1) n n变量的全部最小项的逻辑和变量的全部最小项的逻辑和 恒为恒为1 1。 2 2)任意两个不同的最小项的逻辑)任意两个不同的最小项的逻辑 乘恒为乘恒为0 0。 3 3)n n变量的每一个最小项有变量的每一个最小项有n
21、n个相邻项。个相邻项。 2 2、最小项表达式、最小项表达式标准与或式标准与或式 如如果果在在一一个个与与或或表表达达式式中中,所所有有与与项项均均为为最最小小项项, 则则称称这这种种表表达达式式为为最最小小项项表表达达式式,或或称称为为标标准准与与或或式、标准积之和式。式、标准积之和式。最小项最小项用用m mi i表示。表示。 确定原则:原变量用确定原则:原变量用1 1表示,反变量用表示,反变量用0 0表示。表示。 例如:例如: 可简写为:可简写为: 注:任何一个逻辑函数都可以注:任何一个逻辑函数都可以 表示为最小项之和的形式,表示为最小项之和的形式, 只要将真值表中使函数值只要将真值表中使函
22、数值 为为1 1的各个最小项相或,的各个最小项相或, 便可得出该函数的最小项便可得出该函数的最小项 表达式。表达式。 从真值表可知从真值表可知 最最小项表达式为小项表达式为:A B CF0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 101101011二、最大项和最大项表达式二、最大项和最大项表达式 1 1、最大项、最大项 n n个个变变量量的的最最大大项项是是n n个个变变量量的的“或或项项”,其其中中每每一一个变量都以原变量或反变量的形式出现一次。个变量都以原变量或反变量的形式出现一次。 n n个个变变量量可可以以构构成成2 2n n个个最最大大项项。最最大大
23、项项用用M Mi i表表示示, 对对于于任任何何一一个个最最大大项项,只只有有一一组组变变量量取取值值使使它它为为0 0,而而变量的其余取值均使它为变量的其余取值均使它为1 1。 A A、三变量逻辑函数的最大项三变量逻辑函数的最大项真值表真值表:B B、最大项具有以下性质:、最大项具有以下性质: 1 1)n n变量的全部最大项的逻辑乘恒为变量的全部最大项的逻辑乘恒为0 0。 2 2)n n变量的任意两个不同最大项的变量的任意两个不同最大项的 逻辑和必等于逻辑和必等于1 1。 3 3)n n变量的每个最大项有变量的每个最大项有n n个相邻项。个相邻项。 确定原则:原变量用确定原则:原变量用0 0
24、表示,反变量用表示,反变量用1 1表示。表示。 三变量逻辑函数的最大项三变量逻辑函数的最大项真值表:真值表: 2 2、最小项与最大项之间的关系、最小项与最大项之间的关系 变量数相同,变量数相同,编号相同的最小项和最大项之间存在编号相同的最小项和最大项之间存在互补关系。互补关系。 例如:例如: 3 3、最大项表达式、最大项表达式标准或与式标准或与式 在在一一个个或或与与式式中中,如如果果所所有有的的或或项项均均为为最最大大项项,则则称称这这种种表表达达式式为为最最大大项项表表达达式式,或或称称为为标标准准或或与与式式、标标准和之积表达式。准和之积表达式。 例由真值表求出该函数例由真值表求出该函数
25、最大项表达式。最大项表达式。 1: 2: 3: A B C F F0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 11 01 00 10 11 01 00 10 14 4、最小项与最大项的关系、最小项与最大项的关系1 1)对于)对于N N个逻辑变量的最小项与最大项,若其项号个逻辑变量的最小项与最大项,若其项号i i相同,则二者互补。相同,则二者互补。 即: 或2 2)提到最小项与最大项时,)提到最小项与最大项时,一定要说明变量的数目一定要说明变量的数目,否则最小项与最大项这一术语,否则最小项与最大项这一术语将失去意义。将失去意义。例:5 5 逻辑函数的代数法化简逻
26、辑函数的代数法化简 一、逻辑函数化简的必要性一、逻辑函数化简的必要性从逻辑问题概括出来的逻辑函数式,从逻辑问题概括出来的逻辑函数式, 不一定是最简不一定是最简式。式。 化简电路,化简电路, 就是为了降低系统的成本,提高电路就是为了降低系统的成本,提高电路的可靠性,的可靠性, 以便用最少的门实现它们。以便用最少的门实现它们。1 1、例如函数:、例如函数: 如直接由该函数式得到电路图,则如图所示。如直接由该函数式得到电路图,则如图所示。 2、如果将函数化简后其函数式为:如果将函数化简后其函数式为: F=AC+B 则只要用两个门就够了,则只要用两个门就够了, 如图所示:如图所示: 二、逻辑函数化简的
27、原则二、逻辑函数化简的原则 逻辑函数化简,逻辑函数化简, 并没有一个严格的原则,并没有一个严格的原则, 通常遵循以下几条原则:通常遵循以下几条原则: 1 1、 逻辑电路所用的门(种类)最少;逻辑电路所用的门(种类)最少; 2 2、 各个门的输入端要少(输入端的变量数少各个门的输入端要少(输入端的变量数少);); 3 3、 逻辑电路所用的级数要少;逻辑电路所用的级数要少; 4 4、 逻辑电路能可靠地工作。逻辑电路能可靠地工作。三、逻辑函数代数化简的方法三、逻辑函数代数化简的方法1 1、消元法消元法利用公式:利用公式:A+AB=AB 消去多消去多余余因子。因子。例例:AB+B+BC=B+B(A+C
28、)=B+(A+C) =A+B+C AB+AC+BC=AB+(A+B)C=AB+ABC =AB+C2 2、并项法并项法 利用公式利用公式AB+AB=A将两项合并成一项,消去一变量将两项合并成一项,消去一变量。 例: 3 3、吸收法、吸收法 利利用用公公式式: A A+ +ABAB= =A A 吸吸收收多多余余的的乘乘积积项项或或多多余余因因子子。 例:例: 4 4、配项法配项法 利用重叠律利用重叠律A+A=AA+A=A、互补律互补律A A+ +A A=1=1和吸收律和吸收律 先先配配项项或或添添加加多多余余项项,然然后后 再逐步化简。再逐步化简。 例1: 例例2 2: 例例3 3:例例4 4、解
29、:解: 注:用代数法化简,常有多种化简方法,所得的结果注:用代数法化简,常有多种化简方法,所得的结果 也可能不尽相同。但只要方法和结果正确,其逻也可能不尽相同。但只要方法和结果正确,其逻 辑功能不会改变。辑功能不会改变。例例5 5、解解(北理工)(北理工)5 5 逻辑函数的卡诺图化简逻辑函数的卡诺图化简 在真值表中,输入变量的每一种组合都和一个最在真值表中,输入变量的每一种组合都和一个最小项相对应,所以真值表也称小项相对应,所以真值表也称最小项真值表。最小项真值表。卡诺图卡诺图就是根据最小项真值表按一定规则排列的方格图。就是根据最小项真值表按一定规则排列的方格图。定义:输入逻辑变量分为两组标注
30、在图形的两侧,定义:输入逻辑变量分为两组标注在图形的两侧,第第 一组一组变量的所有组合排列在图形的变量的所有组合排列在图形的最左列最左列,第第 二组二组变量的所有组合排列在图形的变量的所有组合排列在图形的最上边最上边,由,由 行和列两组变量取值组合所构成的每一个小方行和列两组变量取值组合所构成的每一个小方 格,代表了逻辑函数的一个最小项。格,代表了逻辑函数的一个最小项。一、卡诺图的构成一、卡诺图的构成 1 1、卡诺图具有如下特点:卡诺图具有如下特点: A A、n n变量变量的卡诺图有的卡诺图有2 2n n个个小方格小方格,对应表示,对应表示2 2n n个最小项。个最小项。B B、各个小方格之间
31、按逻辑上的各个小方格之间按逻辑上的“循环相邻性循环相邻性”原则排列原则排列。逻逻辑辑相相邻邻:指指彼彼此此之之间间除除有有一一个个变变量量相相反反外外,其其余余变变量量均均相同的两个方格或最小项。相同的两个方格或最小项。循循环环相相邻邻:在在卡卡诺诺图图中中,几几何何位位置置上上直直接接相相邻邻和和相相对对的的方方格或最小项在逻辑上都相邻。格或最小项在逻辑上都相邻。C C 、卡诺图中卡诺图中任何几何位置相邻的两个最小项,在逻任何几何位置相邻的两个最小项,在逻 辑辑上上都都是是相相邻邻的的。由由于于卡卡诺诺图图的的变变量量标标注注均均采采用用循循环环码码,保保证证了了各各相相邻邻行行( (列列)
32、 )之之间间只只有有一一个个变变量量取取值值不不同同,从从而而保证画出来的最小项方保证画出来的最小项方格图具有这一重要特点。格图具有这一重要特点。2 2、三变量四变量、三变量四变量、 五变量卡诺图五变量卡诺图二、逻辑函数的卡诺图表示法二、逻辑函数的卡诺图表示法 1 1、给出逻辑函数的最小项表达式、给出逻辑函数的最小项表达式 只只要要将将构构成成逻逻辑辑函函数数的的最最小小项项在在卡卡诺诺图图上上相相应应的的方方 格中填格中填1 1,其余的方格填,其余的方格填0 0,则可以得到该函数的卡,则可以得到该函数的卡 诺图。诺图。 例:例: 2 2、给出逻辑函数的、给出逻辑函数的一般一般与或式(非标准式
33、)与或式(非标准式) 用卡诺图表示函数用卡诺图表示函数: A、 :在卡诺图上在卡诺图上对应两个方格对应两个方格( (m10、m11) )处填处填1 1。B、 :在卡诺图上对应两个方格在卡诺图上对应两个方格( (m2、m3) )处填处填1 1。 C C、D D:在卡诺图上对应八个方格在卡诺图上对应八个方格( (m1、m3、m5、m7、 m9、m11、m13、m15) )处填处填1 1。 D D、ADAD:在卡诺图上对应四个方格在卡诺图上对应四个方格( (m9、 m11、m13、 m15 ) )处填处填1 1。 注:某些最小项重复,只需填一次即可。注:某些最小项重复,只需填一次即可。3 3、 给出
34、逻辑函数的最大项表达式给出逻辑函数的最大项表达式 只只要要将将构构成成逻逻辑辑函函数数的的最最大大项项在在卡卡诺诺图图相相应应的的方方格格中中填填0 0,其其余余的的方方格格填填1 1即即可可。必必须须注注意意,在在卡卡诺诺图图中中最最大大项项的的编编号号与与最最小小项项编编号号是是一一致致的的,但但对对应应输输入入变变量量的的取值是相反的。取值是相反的。 例:例: 函数函数 卡诺图如图所示。卡诺图如图所示。 4 4、给出逻辑函数的、给出逻辑函数的一般一般或与式(非标准式)或与式(非标准式) 用卡诺图表示函数:用卡诺图表示函数: A+BC=(A+B)(A+C) A A、 :在卡诺图上:在卡诺图
35、上对应两个方格对应两个方格( (M4、M6) )处填处填0 0。B B、 :在在卡卡诺诺图图上上对对应应两两个个方方格格( (M2、M6) )处处填填0 0。 注:注:某些最大项重复,填一次即可。某些最大项重复,填一次即可。 三、最小项化简规律三、最小项化简规律 在卡诺图中,在卡诺图中,2 2n n个个排列成排列成矩阵结构矩阵结构的的对称相邻对称相邻“1”1”单元,可以合并成一个复合单元,合并的结果可消去单元,可以合并成一个复合单元,合并的结果可消去n n个个不同不同的变量,只留下的变量,只留下相同相同的变量。合并得到的复合单的变量。合并得到的复合单 元,在卡诺图中一般用一个圈表示,叫卡诺圈。
36、元,在卡诺图中一般用一个圈表示,叫卡诺圈。A A、若若两两个个最最小小项项相相邻邻,则则合合并并为为一一项项并并消消去去一一对对因因子子,留下公共因子。例:留下公共因子。例:B B、若若四四个个最最小小项项相相邻邻并并排排成成一一个个矩矩阵阵,则则合合并并为为一一项项并并消去消去两对因子两对因子,留下公共因子。,留下公共因子。C C、D D、若若2 2n-1n-1个个最最小小项项相相邻邻并并排排成成一一个个矩矩阵阵,则则合合并并为为一一项项并并消去消去n-1n-1对因子对因子,留下公共因子。,留下公共因子。1、由上述化简规律可知,要并成一个卡诺圈必须满足下由上述化简规律可知,要并成一个卡诺圈必
37、须满足下 列条件:列条件:A A、必须是必须是2 2n n个个“1”1”单元;单元;B B、这些这些“1”1”单元必须排列成矩阵结构;单元必须排列成矩阵结构;C C、这些这些“1”1”单元必须是对称相邻;单元必须是对称相邻; a.a.相接:紧挨着的方格相邻。相接:紧挨着的方格相邻。 b.b.相对:即一行相对:即一行( (一列一列) )的两头、两边、四角相邻。的两头、两边、四角相邻。 c.c.相重:以对称轴为中心对折起来重合的位置相邻。相重:以对称轴为中心对折起来重合的位置相邻。D D、允许重复圈,允许重复圈,但每个卡诺圈但每个卡诺圈至少应有一个未被其它圈至少应有一个未被其它圈包围过的最小项,包
38、围过的最小项,否则合并后的与项会是冗余项;否则合并后的与项会是冗余项;E E、孤立(无相邻项)的最小项单独画卡诺圈。孤立(无相邻项)的最小项单独画卡诺圈。2 2、卡诺图化简的原则:卡诺图化简的原则:A A、在圈住所有在圈住所有“1 1”单元的前提下,应使用最少的圈;单元的前提下,应使用最少的圈;B B、应、应尽量把圈画得最大,即使大到相应重叠也无妨;尽量把圈画得最大,即使大到相应重叠也无妨;C C、当当卡诺图中含有卡诺图中含有无关项无关项时,为了获得最简结果,应充时,为了获得最简结果,应充分利用无关项。根据需要可以把分利用无关项。根据需要可以把无关项视为无关项视为“1”1”或或“0”0”。 需
39、要指出:需要指出:(1 1)、上上述述最最小小项项的的化化简简规规则则,对对最最大大项项的的合合并并同同样样是是适适用用的的。只只是是因因为为最最大大项项是是同同函函数数的的0 0值值相相对对应应,在在卡卡诺诺图图中中则则与与0 0格格对对应应,因因此此,最最大大项项的的合合并并在在卡卡诺诺图图中中是相邻是相邻的的0 0格圈在一起。格圈在一起。(2 2)、同同一一函函数数在在卡卡诺诺图图上上可可能能有有多多种种化化简简方方法法,得得到到的的最最简简式式不不一一定定相相同同,但但逻逻辑辑功功能能是是相相同同的的。原原则则上上,只要圈的范围大、圈的个数少就是较好的化简方法。只要圈的范围大、圈的个数
40、少就是较好的化简方法。 3 3、例:、例: A A、m(1,3)m(1,3)合并为合并为AC AC B B、m(0,4)m(0,4)合并为合并为BC BC C C、m(0,1,4,5)m(0,1,4,5)合并为合并为AC AC D D、m(0,2,8,10)m(0,2,8,10)合并为合并为BDBD m(5,7,13,15) m(5,7,13,15)合并为合并为BDBD m(12,13,14,15) m(12,13,14,15)合并为合并为ABAB E E、m(8,9,10,11,12,13,14,15)m(8,9,10,11,12,13,14,15)合并为合并为A A m(1,3,5,7,9
41、,11,13,15) m(1,3,5,7,9,11,13,15)合并为合并为D D四、用卡诺图化简逻辑函数四、用卡诺图化简逻辑函数 1 1、求最简与或式、求最简与或式 A A、化简步骤:化简步骤: 1 1)画出逻辑函数的)画出逻辑函数的卡诺图卡诺图。 2 2)先从只有一种圈法的最小项开始圈起,)先从只有一种圈法的最小项开始圈起,卡诺卡诺圈的圈的 数目应最少数目应最少( (与项的项数最少与项的项数最少) ),卡诺圈应尽量大卡诺圈应尽量大 ( (对应与项中变量数最少对应与项中变量数最少) )。 3 3)将每个)将每个卡诺卡诺圈写成相应的与项,并将它们相或,圈写成相应的与项,并将它们相或, 便得到最
42、简与或式。便得到最简与或式。 B B、圈圈卡诺卡诺圈时应注意点:圈时应注意点: 根根据据重重叠叠律律( (A A+ +A A= =A A) ),任任何何一一个个1 1格格可可以以多多次次被被圈圈用用,但但如如果果在在某某个个卡卡诺诺圈圈中中所所有有的的1 1格格均均已已被被别别的的卡卡诺诺圈圈圈圈过过,则则该该圈圈为为多多余余圈圈。为为了了避避免免出出现现多多余余圈圈,应应保保证证每每个卡诺圈内至少有一个个卡诺圈内至少有一个1 1格只被圈一次。格只被圈一次。 C C例:例: 1)1)、求、求F F= = m m(1,3,4,5,10,11,12,13)(1,3,4,5,10,11,12,13)
43、的最简与或式。的最简与或式。 解:解:a.a.画出画出F F的的K K图图 b.b.画画K K圈。圈。 c. c. 写出最简式。写出最简式。 2)、求 的的最最简简与与或或式式。 解:解: a. a. 画出画出F F的的K K图。图。 b. b. 画画K K圈。圈。 c. c. 写出最简式。写出最简式。 注:本例有两种圈法,注:本例有两种圈法, 可得到两种最简式。可得到两种最简式。 3)3)、求下式最简与或式。、求下式最简与或式。解:解: a.a.画画F F的的K K图图( (五变量五变量) ) b. b.画画K K圈化简函数。圈化简函数。 c.c.写出最简式。写出最简式。 5 D D、从蕴含
44、项的概念讨论最简式问题:从蕴含项的概念讨论最简式问题: 1 1)蕴含项蕴含项(Implicant)。组成逻辑函数的每一个与组成逻辑函数的每一个与 项项 ( (积项积项) )称为该函数的蕴含项。它称为该函数的蕴含项。它可以是最小项,也可以是最小项,也 可以是合并项。可以是合并项。 2 2)本本原原蕴蕴含含项项( (Prime Implicant)。如如果果逻逻辑辑函函数数的的一一个个 蕴蕴含含项项再再也也不不能能同同该该函函数数的的其其它它蕴蕴含含项项合合并并组组成成变变量量数数更更少少的的蕴蕴含含项项,则则称称该该蕴蕴含含项项为为本本原原蕴蕴含含项项。实实际际上上它它对对应应着着卡卡诺诺图图中
45、中不不能能再再扩扩大大的的合合并并项项,即即最大卡诺圈。最大卡诺圈。 3 3)实实质质本本原原蕴蕴含含项项(Essential (Essential Prime Prime ImplicantImplicant) )。不不能能被被其其它它蕴蕴含含项项所所包包含含的的本本原原蕴蕴含含项项称称为为实实质质本本原原蕴蕴含含项项。它它对对应应着着卡卡诺诺图图中中必必不不可可少少的的最最大大卡卡诺诺圈圈,该该圈圈至至少包含了少包含了一个只有一种圈法的最小项。一个只有一种圈法的最小项。4 4)例:)例:逻辑函数逻辑函数F F1 1、F F2 2的卡诺图分别如图所示,的卡诺图分别如图所示,a. a. 化化简
46、简F F1 1时时只只需需用用 3 3 个个最最大大的的K K圈圈就就可可以以覆覆盖盖全全部部 1 1格,如果用四个格,如果用四个K K圈肯定有一个多余圈。从图圈肯定有一个多余圈。从图 中中 看出,看出,合并项合并项ACAC为多余项,因为该圈中每个为多余项,因为该圈中每个“1” 1” 格被圈了两次。因此可得出最简与或式为:格被圈了两次。因此可得出最简与或式为: b. b. 化简化简F F2 2,只用六个最大的只用六个最大的K K圈覆盖所有的圈覆盖所有的 1 1 格,格, 观察每一个观察每一个K K圈都有一个圈都有一个 1 1 格只被圈过一次,格只被圈过一次, 因此这六个因此这六个K K圈都必须
47、存在,最简与或式为:圈都必须存在,最简与或式为:2 2、求最简、求最简或与式或与式 如如果果要要求求出出某某函函数数的的最最简简或或与与式式,可可以以在在该该函函数数的的卡诺图上合并那些卡诺图上合并那些填填0 0的相邻项的相邻项。A A、化简步骤及化简原则化简步骤及化简原则与与圈圈1 1合合并并类类同同(圈圈0 0),只只要要按按圈圈逐逐一一写写出出或或项项,然然后将所得的或项相与即可。后将所得的或项相与即可。 B B、注意:(最大项、最小项卡诺图的区别)注意:(最大项、最小项卡诺图的区别) 最最大大项项卡卡诺诺图图对对应应的的卡卡诺诺圈圈由由圈圈0 0的的那那些些变变量量组组成成,当变量取值
48、为当变量取值为0 0时写原变量,取值为时写原变量,取值为1 1时写反变量。时写反变量。 1)1)、求、求最简或与式。最简或与式。 解:解:a.a.画出画出F F的的K K图图 b.b.画画K K圈。圈。 c.c.写出最简式。写出最简式。 2)2)、求、求最简或与式。最简或与式。 解:解:a.a.画出画出F F的的K K图图 b.b.画画K K圈。圈。 c. c. 写出最简式。写出最简式。 6 6 非完全描述逻辑函数的化简非完全描述逻辑函数的化简 一、基本概念一、基本概念1 1、无关项:包括约束项和任意项。、无关项:包括约束项和任意项。2 2、约束项:指在某些实际问题中,那些受到约束(限、约束项
49、:指在某些实际问题中,那些受到约束(限 制)的变量取值所对应的最小项。制)的变量取值所对应的最小项。3 3、任意项:在某些输入变量取值下,函数值是、任意项:在某些输入变量取值下,函数值是“1”1”还是还是 “ “0”0”无所谓,不影响电路的功能。这些变量无所谓,不影响电路的功能。这些变量 取值所对应的最小项也叫多余项。取值所对应的最小项也叫多余项。4 4、无关项在真值表或卡诺图中通常用、无关项在真值表或卡诺图中通常用“”或或“X”X”或或“d”d”表表 示。示。例:用例:用A A、B B、C C三个变量描述电机的正转、反转和停止。三个变量描述电机的正转、反转和停止。 设:设:A A1 1 正转
50、正转、B B1 1 反转反转、C C1 1 停止停止。 因为电机在任何时候只能执行其中的一种工作状态,因为电机在任何时候只能执行其中的一种工作状态,所以不允许两个以上的变量同时为所以不允许两个以上的变量同时为“1”1”或同时为或同时为“0”0”,这样,这样A A、B B、C C三个变量的取值可能是:三个变量的取值可能是:001001,010010,100100当中的某一个。而不能是:当中的某一个。而不能是:000000,011011,101101,110110,111111当中的任何一个。即:当中的任何一个。即: 上述最小项就叫上述最小项就叫约束项约束项。 在存在约束项的情况下,由于约束项的值
51、始终为在存在约束项的情况下,由于约束项的值始终为0 0,所以可以将约束项写进逻辑函数式中,也可以将约束,所以可以将约束项写进逻辑函数式中,也可以将约束项从函数式中删除,而不影响函数值。项从函数式中删除,而不影响函数值。二、非完全描述的逻辑函数二、非完全描述的逻辑函数 如如果果对对于于输输入入变变量量某某些些取取值值的的组组合合逻逻辑辑函函数数值值不不确确定定,即即函函数数值值可可为为0 0,也也可可为为1(1(通通常常将将函函数数值值记记为为或或或或d)d),那么这那么这类函数称为非完全描述的逻辑函数。类函数称为非完全描述的逻辑函数。 1 1、无关项发生在以下两种情况:、无关项发生在以下两种情
52、况: A A、由于某种条件的限制由于某种条件的限制( (或约束或约束) )使得输入变量的某使得输入变量的某 些些 组合组合不可能出现不可能出现,因而在这些取值下对应的函数值,因而在这些取值下对应的函数值 是是“无关无关”紧要的,它可为紧要的,它可为1 1,也可为,也可为0 0。 B B、某些输入变量取值所某些输入变量取值所产生的输出并不影响整个系产生的输出并不影响整个系 统的功能统的功能,因此可以不必考虑其输出是,因此可以不必考虑其输出是0 0还是还是1 1。2 2、非完全描述逻辑函数用以下方法表示、非完全描述逻辑函数用以下方法表示: A A、 在真值表或在真值表或K K图中填图中填或或或或d
53、 d ,表示函数值为表示函数值为0 0 或或1 1均可。均可。 B B、在逻辑表达式中用约束条件来表示。在逻辑表达式中用约束条件来表示。 C C、例例: 也可简写为也可简写为:三、非完全描述逻辑函数的化简三、非完全描述逻辑函数的化简 充分利用无关项来化简逻辑函数充分利用无关项来化简逻辑函数,即采用卡诺图化,即采用卡诺图化简函数时,可以利用简函数时,可以利用 ( (或或) )来扩大卡诺圈。来扩大卡诺圈。 1 1、 化简逻辑函数:化简逻辑函数: 化简得:化简得:2 2、化简逻辑函数:、化简逻辑函数:化简得化简得( (圈圈0)0)( (圈圈1)1) 结论:结论: 最小项卡诺图:圈最小项卡诺图:圈“1
54、”1”F F;圈圈“0”0” 最大项卡诺图:圈最大项卡诺图:圈“0”0”F F;圈圈“1”1”3 3、化简:、化简: 化简得:化简得:小 结 一、 本章内容提要:1、三种基本运算:与或非真值表、逻辑表达式、逻辑符号2、逻辑代数的基本定律和规则A、 0-1律: A0 =0 A+1 =1自等律: A1=A A+0=A重叠律: AA=A A+A=A互补律: AA=0 A+A=1交换律: AB=BA A+B=B+A结合律: (AB)C=A(BC) (A+B)+C=A+(B+C) 分配律: A(B+C)=AB+AC A+BC=(A+B)(A+C)反演律:还原律: B、 三个重要规则 1)、 代入规则任何
55、一个逻辑等式,如果将等式两边所出现的某一变量都代之以同一逻辑函数,则等式仍然成立。 2)、反演规则 如果将逻辑函数式F中所有的算符“”换成“+”, “+”换成“”,常量“0”换成“1”,“1”换成“0”,原 变量换成反变量,反变量换成原变量,则所得到的就是F。F 称为原函数F的反函数,或称为补函数。 3)、对偶规则 如果将逻辑函数表达式F中所有的算符“”换成“+”, “+”换成“”,常量“0”换成“1”,“1”换成“0”,而变量保持不变,则得出的逻辑函数式就是F的对偶式。若原等式成立,则对偶式也一定成立。C、若干常用公式合并律 : 3、 复合逻辑运算和复合门A、与非、 或非、 与或非逻辑运算、
56、B、异或和同或逻辑运算C、逻辑函数式的五种形式: A、与或式B、或与式C、与非与非式D、或非或非式E、与或非式 4、逻辑函数的两种标准形式 A、最小项和最小项表达式 1)、 n变量的全部最小项的逻辑和恒为1。 2)、任意两个不同的最小项的逻辑乘恒为0。 3)、n变量的每一个最小项有n个相邻项。 4)、任一逻辑函数都可以表示为最小项之和的形式, 只要将真值表中使函数值为1的各个最小项相或。 B、最大项和最大项表达式 1)、n变量的全部最大项的逻辑乘恒为0。 2)、n变量的任意两个不同的最大项的逻辑和必等于1。 3)、n变量的每个最大项有n个相邻项。 4)、编号相同的最小项和最大项之间存在互补关系
57、。5、 逻辑函数的代数法化简A、逻辑函数化简的原则 1)、 逻辑电路所用的门最少; 2)、 各个门的输入端要少; 3)、 逻辑电路所用的级数要少; 4)、 逻辑电路能可靠地工作。B、逻辑函数代数化简的方法.消元法、并项法、吸收法、配项法6、逻辑函数的卡诺图化简 A、圈圈时应注意点:根据重叠律(A+A=A),任何一个1格可以多次被圈用,但如果在某个K圈中所有的1格均已被别的K圈圈过,则该圈为多余圈。为了避免出现多余圈,应保证每个K圈内至少有一个1格只被圈一次。 B、可以充分利用这些无关项来化简逻辑函数,即采用卡诺图化简函数时, 可以利用 (或)来扩大卡诺圈。 二、举例:二、举例:1 1、试用卡诺
58、图判断下列两个逻辑函数试用卡诺图判断下列两个逻辑函数Y Y和和Z Z有何关系。有何关系。根根据据Y Y和和Z Z的的逻逻辑辑表表达达式式,画画出出其其相相应应的的卡卡诺诺图图如如图图(a)(a)和和(b)(b)示。示。比较图比较图(a)(a)和和(b)(b)可知,可知,Y Y和和Z Z互为反函数。互为反函数。 2 2、试证明下列逻辑恒等式。、试证明下列逻辑恒等式。(1) (2) A A、采用真值表法证明采用真值表法证明(1)(1):列列出出等等式式(1)(1)两两边边表表达达式式的的真真值值表表,如如表表所所示示。可可见见,等号两边表达式的真值表相同,故等式等号两边表达式的真值表相同,故等式(
59、1)(1)成立。成立。B B、采用公式法证明采用公式法证明(2)(2): 1)1)、方法、方法1 1: 2)2)、方法、方法2 2:令令 求求F F和和G G两函数的对偶函数:两函数的对偶函数: 显然,显然,F F* *=G=G* *,故有故有F=GF=G。 说明:本小题采用了两种方法证明给定的逻辑等说明:本小题采用了两种方法证明给定的逻辑等式。由于式。由于原式是用或与形式表示,所以用对偶原式是用或与形式表示,所以用对偶定理证明较为简便定理证明较为简便。对偶定理有一个重要的推。对偶定理有一个重要的推论,即论,即若两逻辑函数相等,则其对偶函数式必若两逻辑函数相等,则其对偶函数式必 然相等然相等。
60、因此可将等式两边同时对偶成与或。因此可将等式两边同时对偶成与或式,然后证明等式成立。式,然后证明等式成立。(3)解:令:3、试试用用卡卡诺诺图图法法将将函函数数F F化化简简为为最最简简与与或或式式、或或与与式式、与与非非与与非非式、或非或非式、与或非式。式、或非或非式、与或非式。解:解: (1)(1)最简与或式:最简与或式:(2)(2)最简或与式:最简或与式:(3)(3)与非与非式:与非与非式:(4)(4)或非或非式:或非或非式:(5)(5)与或非式:与或非式: ( (圈圈0 0的非的非) )4 4、试试用用卡卡诺诺图图法法将将下下列列具具有有约约束束条条件件的的逻逻辑辑函函数数化化为为最最
61、简简与与或函数式。或函数式。解:解: A A、画出、画出F F的卡诺图的卡诺图 B B、合并相邻的最小项。、合并相邻的最小项。C C、写出函数的最简与、写出函数的最简与或式:或式:5 5、将函数将函数F F化简为最简与或式及最简或与式:化简为最简与或式及最简或与式:分分析析:这这里里介介绍绍一一种种简简易易的的求求解解方方法法:因因为为F F是是或或与与式式形形式式,所所以以可可先先对对F F求求对对偶偶式式F F* *,然然后后用用卡卡诺诺图图法法对对F F* *化化简简。将将化化简简后后的的F F* *再再求求其其对对偶偶式式即即得得F F的的最最简简或或与与式式。利利用用摩摩根定律便求得
62、最简与或式。根定律便求得最简与或式。解:解: 由由F F求得求得画出画出F F* *的卡诺图如图示,经化简可得的卡诺图如图示,经化简可得 据此可得据此可得F F的最简或与式为的最简或与式为 再根据摩根定律得再根据摩根定律得F F的最简与或式为的最简与或式为 6 6、已知函数已知函数 试求:试求: 的最简与的最简与或表达式。或表达式。分分析析: 函函数数在在进进行行与与、或或、异异或或的的运运算算时时,只只要要将将图图中编号相同的方块,按运算规则进行运算即可。中编号相同的方块,按运算规则进行运算即可。卡诺图化简,求得:卡诺图化简,求得: 7 7、将逻辑函数、将逻辑函数 化简为最简与或非式。化简为
63、最简与或非式。( (北理工北理工9898)分分析析:利利用用卡卡诺诺图图化化简简函函数数为为最最简简与与或或非非式式时时,可可考考虑虑在卡诺图中先圈在卡诺图中先圈0 0,得到,得到 的最简与或式,再在的最简与或式,再在 此此最简式上加反,即得最简式上加反,即得F F的最简与或非式。的最简与或非式。A A、画出函数画出函数F F的卡诺图,如图示。的卡诺图,如图示。B B、合并相邻的最小项(圈合并相邻的最小项(圈0 0)C C、写出函数写出函数 的最简与或表达式。的最简与或表达式。D D、对对 函数求反,得原函数的最简函数求反,得原函数的最简 与或非式:与或非式:结论:最小项卡诺图:圈结论:最小项卡诺图:圈“1”1”F F;圈圈“0”0” 最大项卡诺图:圈最大项卡诺图:圈“0”0”F F;圈圈“1”1”8 8、将最小项表达式变换为最大项表达式。、将最小项表达式变换为最大项表达式。解:因为:解:因为:9 9、证明、证明(1 1)如果)如果 则则 反之亦成立。反之亦成立。证明:证明:(2 2)如果)如果 则则 证明:证明: