《第六周 卡若图化简和组合逻辑电路设计.pptx》由会员分享，可在线阅读，更多相关《第六周 卡若图化简和组合逻辑电路设计.pptx（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、（3）基本定理）基本定理利用真值表很容易证明这利用真值表很容易证明这些公式的正确性。如证明些公式的正确性。如证明A AB=BB=BA A：第1页/共50页(A+B)(A+C)=AA+AB+AC+BC分配率分配率A(B+C)=AB+AC=A+AB+AC+BC等幂率等幂率AA=A=A(1+B+C)+BC分配率分配率A(B+C)=AB+AC=A+BC0-1率率A+1=1证明分配率：A+BA=(A+B)(A+C)证明：证明：第2页/共50页（4）常用公式）常用公式分配率分配率A+BC=(A+B)(A+C)互补率互补率A+A=10-1率率A1=1第3页/共50页互补率互补率A+A=1分配率分配率A(B+
2、C)=AB+AC0-1率率A+1=1第4页/共50页（2）反反演演规规则则：对对于于任任何何一一个个逻逻辑辑表表达达式式Y，如如果果将将表表达达式式中中的的所所有有“”换换成成“”，“”换换成成“”，“0”换换成成“1”，“1”换换成成“0”，原原原原变变变变量量量量换换换换成成成成反反反反变变变变量量量量，反反反反变变变变量量量量换换换换成成成成原原原原变变变变量量量量，那那么么所所得得到到的的表表达达式式就就是是函函数数Y的的反反函函数数Y（或或称称补补函函数数）。这这个个规规则则称称为为反演规则。例如：反演规则。例如：例如，已知等式例如，已知等式 ，用函数，用函数Y=AC代替等式中的代替
3、等式中的A，根据代入规则，等式仍然成立，即有：，根据代入规则，等式仍然成立，即有：2.基本规则基本规则 （1）代代入入规规则则：任任何何一一个个含含有有变变量量A的的等等式式，如如果果将将所所有有出出现现A的的位位置置都都用用同同一一个个逻逻辑辑函函数数代代替替，则则等等式式仍仍然然成成立立。这这个个规规则则称称为为代代入规则。入规则。第5页/共50页 （3）对对偶偶规规则则：对对于于任任何何一一个个逻逻辑辑表表达达式式Y，如如果果将将表表达达式式中中的的所所有有“”换换成成“”，“”换换成成“”，“0”换换成成“1”，“1”换换成成“0”，而而变变变变量量量量保保保保持持持持不不不不变变变变
4、，则则可可得得到到的的一一个个新新的的函函数数表表达达式式Y，Y称为函数称为函数Y的对偶函数。这个规则称为对偶规则。例如：的对偶函数。这个规则称为对偶规则。例如：对对偶偶规规则则的的意意义义在在于于：如如果果两两个个函函数数相相等等，则则它它们们的的对对偶偶函函数数也也相相等。利用对偶规则等。利用对偶规则,可以使要证明及要记忆的公式数目减少一半。例如：可以使要证明及要记忆的公式数目减少一半。例如：注意注意注意注意：在运用反演规则和对偶规则时，必须按照逻：在运用反演规则和对偶规则时，必须按照逻辑运算的优先顺序进行：先算括号，接着与运算，辑运算的优先顺序进行：先算括号，接着与运算，然后或运算，最后
5、非运算，否则容易出错。然后或运算，最后非运算，否则容易出错。第6页/共50页逻辑函数化简的意义：逻辑表达式越简单，实现它的电路越简单，逻辑函数化简的意义：逻辑表达式越简单，实现它的电路越简单，电路工作越稳定可靠。电路工作越稳定可靠。一个逻辑函数的表达式可以有一个逻辑函数的表达式可以有与或与或表达式、表达式、或与或与表达式、表达式、与非与非-与非与非表达式、表达式、或非或非-或非或非表达式、表达式、与或非与或非表达式表达式5种表示形式。种表示形式。一种形式的函数表达式相应于一种逻辑电路。尽管一个逻辑函数一种形式的函数表达式相应于一种逻辑电路。尽管一个逻辑函数表达式的各种表示形式不同，但逻辑功能是
6、相同的。表达式的各种表示形式不同，但逻辑功能是相同的。任务基础知识四任务基础知识四逻辑函数的化简与变换逻辑函数的化简与变换第7页/共50页（1）最简与或表达式）最简与或表达式乘积项最少、并且每个乘积项中的变量也最少的与或表达式。乘积项最少、并且每个乘积项中的变量也最少的与或表达式。最简与或表达式最简与或表达式一、一、公式法化简公式法化简1.逻辑函数表述式的标准形式和最简式逻辑函数表述式的标准形式和最简式第8页/共50页(2)最简与非最简与非-与非表达式与非表达式非号最少、并且每个非号下面乘积项中的变量也最少的与非非号最少、并且每个非号下面乘积项中的变量也最少的与非-与与非表达式。非表达式。在最
7、简与或表达式的基础上两次取反在最简与或表达式的基础上两次取反用摩根定律去用摩根定律去掉下面的非号掉下面的非号(3)(3)最简或与表达式最简或与表达式括号最少、并且每个括号内相加的变量也最少的或与表达式。括号最少、并且每个括号内相加的变量也最少的或与表达式。求出反函数的求出反函数的最简与或表达式最简与或表达式利用反演规则写出函利用反演规则写出函数的最简或与表达式数的最简或与表达式第9页/共50页(4)(4)最简或非最简或非-或非表达式或非表达式非号最少、并且每个非号下面相加的变量也最少的或非非号最少、并且每个非号下面相加的变量也最少的或非-或非表达或非表达式。式。求最简或非求最简或非-或非表达式
8、或非表达式两次取反两次取反(5)(5)最简与或非表达式最简与或非表达式非号下面相加的乘积项最少、并且每个乘积项中相乘的变量也最非号下面相加的乘积项最少、并且每个乘积项中相乘的变量也最少的与或非表达式。少的与或非表达式。求最简或非求最简或非-或非表达式或非表达式用摩根定律去掉下面的用摩根定律去掉下面的非号非号用用摩摩根根定定律律去去掉掉大大非非号号下下面面的的非非号号第10页/共50页2.常见的公式法简化方法常见的公式法简化方法（1 1）并项法）并项法逻辑函数的公式化简法就是运用逻辑代数的基本公式、定理和规逻辑函数的公式化简法就是运用逻辑代数的基本公式、定理和规则来化简逻辑函数。则来化简逻辑函数
9、。利用公式利用公式1，将两项合并为一项，并消去一个变量。，将两项合并为一项，并消去一个变量。若若两两个个乘乘积积项项中中分分别别包包含含同同一一个个因因子子的的原原变变量量和和反反变变量量，而而其其他他因因子子都都相相同同时时，则则这这两两项项可可以以合合并并成成一一项项，并并消消去去互互为为反反变变量量的的因因子子。第11页/共50页2.2.吸收法吸收法如如果果乘乘积积项项是是另另外外一一个个乘乘积积项项的的因因子子，则则这这另另外外一一个个乘乘积积项项是是多多余余的的。（）利用公式，消去多余的项。（）利用公式，消去多余的项。（）利用公式，消去多余的变量。（）利用公式，消去多余的变量。如如果
10、果一一个个乘乘积积项项的的反反是是另另一一个个乘乘积积项项的的因因子子，则则这这个个因因子子是是多多余余的的。第12页/共50页.配项法配项法（）利用公式（），为某一项配上其所缺的变量，（）利用公式（），为某一项配上其所缺的变量，以便用其它方法进行化简。以便用其它方法进行化简。（）利用公式，为某项配上其所能合并的项。（）利用公式，为某项配上其所能合并的项。第13页/共50页.消去冗余项法消去冗余项法利用冗余律，将冗利用冗余律，将冗余项消去。余项消去。第14页/共50页例例：化简函数：化简函数解解：先求出先求出Y的对偶函数的对偶函数Y，并对其进行化简。，并对其进行化简。求求Y的对偶函数，便得的最
11、简或与表达式。的对偶函数，便得的最简或与表达式。第15页/共50页1.1.逻辑函数的最小项及其性质逻辑函数的最小项及其性质（1）最小项：如果一个函数的某个乘积项包含了函数的全部变量，）最小项：如果一个函数的某个乘积项包含了函数的全部变量，其中每个变量都以原变量或反变量的形式出现，且仅出现一次，则这其中每个变量都以原变量或反变量的形式出现，且仅出现一次，则这个乘积项称为该函数的一个标准积项，通常称为最小项。个乘积项称为该函数的一个标准积项，通常称为最小项。3个变量个变量A、B、C可组成可组成8个最小项：个最小项：（2）最小项的表示方法：通常用符号）最小项的表示方法：通常用符号mi来表示最小项。下
12、标来表示最小项。下标i的的确定：把最小项中的原变量记为确定：把最小项中的原变量记为1，反变量记为，反变量记为0，当变量顺序确定后，当变量顺序确定后，可以按顺序排列成一个二进制数，则与这个二进制数相对应的十进制可以按顺序排列成一个二进制数，则与这个二进制数相对应的十进制数，就是这个最小项的下标数，就是这个最小项的下标i。3个变量个变量A、B、C的的8个最小项可以分别表示为：个最小项可以分别表示为：二、二、卡诺图化简法卡诺图化简法第16页/共50页（3）最小项的性质：）最小项的性质：任意一个最小项，只有一组变量取值使其值为任意一个最小项，只有一组变量取值使其值为1。全部最小项的和必为全部最小项的和
13、必为1。ABCABC任意两个不同的最小项的乘积必为任意两个不同的最小项的乘积必为0。第17页/共50页2.2.逻辑函数的最小项表达式逻辑函数的最小项表达式任何一个逻辑函数都可以表示成唯一的一组最小项之和，称为标任何一个逻辑函数都可以表示成唯一的一组最小项之和，称为标准与或表达式，也称为最小项表达式准与或表达式，也称为最小项表达式对于不是最小项表达式的与或表达式，可利用公式对于不是最小项表达式的与或表达式，可利用公式AA1 和和A(B+C)ABAC来配项展开成最小项表达式。来配项展开成最小项表达式。第18页/共50页如果列出了函数的真值表，则只要将函数值为如果列出了函数的真值表，则只要将函数值为
14、1的那些最小项相加，的那些最小项相加，便是函数的最小项表达式。便是函数的最小项表达式。m1ABCm5ABCm4ABCm2ABC将真值表中函数值为将真值表中函数值为0的那些最小项相加，便可得到反函数的那些最小项相加，便可得到反函数的最小项表达式。的最小项表达式。第19页/共50页3.3.卡诺图的构成卡诺图的构成将逻辑函数真值表中的最小项重新排列成矩阵形式，并且使将逻辑函数真值表中的最小项重新排列成矩阵形式，并且使矩阵矩阵矩阵矩阵的横方向和纵方向的逻辑变量的取值按照格雷码的顺序排列的横方向和纵方向的逻辑变量的取值按照格雷码的顺序排列的横方向和纵方向的逻辑变量的取值按照格雷码的顺序排列的横方向和纵方
15、向的逻辑变量的取值按照格雷码的顺序排列，这样构，这样构成的图形就是卡诺图。成的图形就是卡诺图。卡诺图的特点是任意两个相邻的最小项在图中也是相邻的。（相邻卡诺图的特点是任意两个相邻的最小项在图中也是相邻的。（相邻项是指两个最小项只有一个因子互为反变量，其余因子均相同，又称项是指两个最小项只有一个因子互为反变量，其余因子均相同，又称为逻辑相邻项）为逻辑相邻项）。每每个个两两变变量量的的最最小小项项有有两两个个最最小小项项与与它它相相邻邻每每个个三三变变量量的的最最小小项项有有三三个个最最小小项项与与它它相相邻邻第20页/共50页每个每个4变量的最小项有变量的最小项有4个最小项与它相邻个最小项与它相
16、邻最最左左列列的的最最小小项项与与最最右右列列的的相相应应最最小小项项也也是是相相邻邻的的最最上上面面一一行行的的最最小小项项与与最最下下面面一一行行的的相相应应最最小小项项也也是是相相邻邻的的两个相邻最小项可以合并消去一个变量两个相邻最小项可以合并消去一个变量逻辑函数化简的实质就是相邻最小项的合并逻辑函数化简的实质就是相邻最小项的合并第21页/共50页4.4.逻辑函数在卡诺图中的表示逻辑函数在卡诺图中的表示（1）逻辑函数是以真值表或者以最小项表达式给出：在卡诺图上）逻辑函数是以真值表或者以最小项表达式给出：在卡诺图上那些与给定逻辑函数的最小项相对应的方格内填入那些与给定逻辑函数的最小项相对应
17、的方格内填入1，其余的方格内，其余的方格内填入填入0。m1m4m3m6m7m11m14m15第22页/共50页（2）逻辑函数以一般的逻辑表达式给出：先将函数变换为与或表）逻辑函数以一般的逻辑表达式给出：先将函数变换为与或表达式（不必变换为最小项之和的形式），然后在卡诺图上与每一个乘达式（不必变换为最小项之和的形式），然后在卡诺图上与每一个乘积项所包含的那些最小项（该乘积项就是这些最小项的公因子）相对积项所包含的那些最小项（该乘积项就是这些最小项的公因子）相对应的方格内填入应的方格内填入1，其余的方格内填入，其余的方格内填入0。变变换换为为与与或或表表达达式式的公因子的公因子第23页/共50页
18、BCA0001111001111 BCA0001111001例如例如例如例如：Z的卡诺图：2.卡诺图与逻辑函数的其他几种表示方法之间的互换：1）由真值表画卡诺图：例如例如例如例如：1111第24页/共50页 CDA B00011110000111102）由逻辑函数与或式画卡诺图：例如例如例如例如：111 1111111 11 111 13）由卡诺图写与或式：例如例如例如例如：BCA000111100111111110CBABCAZ+=第25页/共50页5.5.用卡诺图化简逻辑函数用卡诺图化简逻辑函数（1）任何两个（）任何两个（21个）标个）标1的相邻最小项，可以合并为一项，并消的相邻最小项，可
19、以合并为一项，并消去一个变量（消去互为反变量的因子，保留公因子）。去一个变量（消去互为反变量的因子，保留公因子）。第26页/共50页（2）任何）任何4个（个（22个）标个）标1的相邻最小项，可以合并为一项，并消去的相邻最小项，可以合并为一项，并消去2个变量。个变量。第27页/共50页BD第28页/共50页（3）任何）任何8个（个（23个）标个）标1的相邻最小项，可以合并为一项，并消去的相邻最小项，可以合并为一项，并消去3个变量。个变量。B第29页/共50页6.6.化简的基本步骤化简的基本步骤(举例举例)逻辑表达式逻辑表达式或真值表或真值表卡诺图卡诺图 1 1 第30页/共50页合并最小项合并最
20、小项圈圈越越大大越越好好，但但每每个个圈圈中中标标的的方方格格数数目目必必须须为为个个。同同一一个个方方格格可可同同时时画画在在几几个个圈圈内内，但但每每个个圈圈都都要要有有新新的的方方格格，否否则则它它就就是是多多余余的的。不不能能漏漏掉掉任任何何一一个个标标的的方方格格。最简与或表达式最简与或表达式 2 2 3 3 将将代代表表每每个个圈圈的的乘乘积积项项相相加加第31页/共50页用卡诺图法化简逻辑函数一、步骤1.将函数变换为与或式；2.画出卡诺图；3.将2n个有1的相邻小方格圈出（所圈小方格数是2的整次幂，即：1个、2个、4个、8个小方格为一个圈），提出公因子；4.将公因子相加。因卡诺图
21、中的最小项几何相邻必定逻辑相邻，故几何相邻的最小项可以提取公因子，而消去不同项，这样就可以用卡诺图来化简逻辑函数。第32页/共50页二、画圈原则1.圈越大越好（圈大，消去的因子多）。2.圈的个数越少越好（化简后的乘积项少）。3.同一个“1”小方格可以被圈多次。4.每个圈中要有新的“1”。5.画圈时，可先圈大，后圈小。6.不要遗漏任何“1”的小方格；最后还要删除多余圈。第33页/共50页例如例如例如例如：用卡诺图化简下列函数：1.BCA00011110011111112.CDA B0001111000011110111111111第34页/共50页3.BCA0001111001111114.CD
22、A B000111100001111011111111或:多余圈多余圈(删删除除)第35页/共50页练习、练习、用卡诺图化简函数用卡诺图化简函数 解：解：根据最小项的编号规则，得根据最小项的编号规则，得 将这四个最小项填入四变量卡诺图内将这四个最小项填入四变量卡诺图内化简得化简得第36页/共50页例例2.112.11 用卡诺图化简函数用卡诺图化简函数 解：解：从表达式中可以看出此为四变量的逻辑函数，但是有的乘积项中缺少一个从表达式中可以看出此为四变量的逻辑函数，但是有的乘积项中缺少一个变量，不符合最小项的规定。因此，每个乘积项中都要将缺少的变量补上：变量，不符合最小项的规定。因此，每个乘积项中
23、都要将缺少的变量补上：则有则有将这七个最小项填入四变量卡诺图内将这七个最小项填入四变量卡诺图内化简得化简得第37页/共50页练习：判断正确与错误练习：判断正确与错误正确正确错误错误 （多画一个圈）（多画一个圈）例例1 1例例2 2错误（圈的面积不够大）错误（圈的面积不够大）正确正确 第38页/共50页例例3 3错误（圈的面积不够大）错误（圈的面积不够大）正确正确 例例4 4错错误误（有有一一个个圈圈无无新新的的1 1格格）正正确确 第39页/共50页三、卡诺图的性质和运算1、全“0”格对应Y=02、全“1”格对应Y=13、卡诺图相加、相乘、异或对应格相加、相乘、异或。+=4、卡诺图反演“1”格
24、“0”格“0”格“1”格四、用卡诺图合并最小项的规律 2个相邻1格可合并成一个乘积项，消去1个有01变化的变量，保留无变化的变量；4个相邻1格可合并成一个乘积项，消去2个有01变化的变量，保留无变化的变量；8个相邻1格可合并成一个乘积项，消去3个有01变化的变量，保留无变化的变量；2i个相邻1格可合并成一个乘积项，消去i个有01变化的变量，保留无变化的变量。第40页/共50页五、用卡诺图化简逻辑函数1、简化原则（1）圈尽量大；变量数少（2）圈数尽量少；乘积项少（3）每一个“1”格都被圈到，没有“0”格被圈；（4）全部是必要项，没有多余项。必要项：对应圈中至少有一个“1”格只被圈一次。有新“1”
25、格多余项：对应圈中的每一个“1”格都被圈2次或2次以上。2、化简步骤（1）画卡诺图。（2）按简化原则化简函数。先圈只有一种圈法的圈（3）检查是否全部“1”格被圈，没有“0”格被圈。（4）写出相应的简化式。第41页/共50页解解第第一一步步：填填写写卡卡诺诺图图（为为了了叙叙述述方方便便，这这里里填填写写最最小小项项的的编编号号，平平常常应应该在对应最小项方格中填该在对应最小项方格中填1 1）。第二步：第二步：画画包包围圈。围圈。第三步第三步：化：化简简包围圈。包围圈。000111100001ABCD 11101 11 1 1 1 1 1 1第42页/共50页Eg2.化简函数：101101001
26、0110100ABCD卡诺图为：11111111用三个圈覆盖：最简与或式为：1可重复使用要圈两个1(1)第43页/共50页1011010010110100ABCD1010110100ABCY=AB+AB+BC+BC111111卡诺图如右;圈黑圈，得：Y=AB+BC+CA圈篮圈，得：Y=AB+BC+CAY(A,B,C,D)=m1+m5+m6+m7+m11+m12+m13+m1511111111显然，紫圈是多余的。避免画多余圈的方法：1.画完圈后注意检查；2.先圈只有一种方法可圈的1。(2)(3)当最简式不唯一时，画圈的方法也不唯一第44页/共50页(4)Y=AD+BCD+ABC+ACD+A BD
27、1011010010110100ABCD1011010010110100ABCD1111111111=AB+BC+B DY=ACD+CD+AD+AB+ABC111111111111这种情况可通过圈0求Y来解决：Y=ADY=A+D(5)第45页/共50页（6）F=(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+D)F为或与式，可先对F求对偶式F即F=ABCD+ABCD+ABCD+ABCD+AD画出F的卡诺图1011010010110100ABCD11111111F=AD+ADF=(F)=(A+D)(A+D)=AD+AD第46页/共50页 第47页/共50页注：每一项都是必要项构成的函数表达式不一定最简！a)圈圈“1”与或式与或式或与式；或与式；b)反函数圈反函数圈“1”与或式，再求非与或式，再求非或与式；或与式；c)直接圈直接圈“0”格格或与式。或与式。最大项概念最大项概念第48页/共50页第49页/共50页感谢您的观看！第50页/共50页