布尔代数及逻辑函数化简

布尔代数及逻辑函数化简第一页，共五十四页，2022年，8月28日但是在变量多了之后，逻辑相邻项会比较难找，而卡诺图正好解决了这个问题：利用图形法找出相邻关系，即在图形上相邻的项也就是逻辑相邻项。二、逻辑函数的标准式1、最小项对于一个给定变量数目的逻辑函数，所有变量参加相“与”的项叫做最小项。每个变量只能以原变量和反变量的形式出现一次一变量最小项：第二页，共五十四页，2022年，8月28日一变量最小项：二变量最小项：个个22N变量最小项：个2N2、最小项标准式全是由最小项组成的与或式。F=ABC+ABC+ABC+ABCF=ABC+BC+AC标准式一般式未必全部最小项第三页，共五十四页，2022年，8月28日最小项具有唯一性，而一般式具有多样性。3、一般式转换为标准式（1）代数法（拆项）第四页，共五十四页，2022年，8月28日（2）真值表法（拆项）ABCABCBCACF00010010010000010000001101011000011101000011000111110101第五页，共五十四页，2022年，8月28日4、最小项表示方法当变量为0时，以反变量的形式出现当变量为1时，以原变量的形式出现第六页，共五十四页，2022年，8月28日5、最小项性质：②任意两个不同的最小项的逻辑乘恒为0，即③n变量的每一个最小项有n个相邻项。例如，三变量的某一最小项有三个相邻项：。这种相邻关系对于逻辑函数化简十分重要。①n变量的全部最小项的逻辑和恒为1，即第七页，共五十四页，2022年，8月28日三、卡诺图结构（K图）图中的一小格对应真值表中的一行，即对应一个最小项，又称真值图AB00011011

m0

m1

m2

m3AABBABBAABABAB1010

m0

m1

m2

m3

miABC01000111100001111000011110

m0

m1

m2

m3

m4

m5

m6

m7

m0

m1

m2

m3

m4

m5

m6

m7

m12

m13

m14

m15

m8

m9

m10

m11ABCD二变量K图三变量K图四变量K图第八页，共五十四页，2022年，8月28日K图具有如下特点：①

n变量的卡诺图有2n个方格，对应表示2n个最小项。每当变量数增加一个，卡诺图的方格数就扩大一倍。②卡诺图中任何几何位置相邻的两个最小项，在逻辑上都是相邻的。由于变量取值的顺序按格雷码排列，保证了各相邻行(列)之间只有一个变量取值不同，从而保证画出来的最小项方格图具有这一重要特点。所谓几何相邻，一是相接，即紧挨着；二是相对，即任意一行或一列的两头；三是相重，即对折起来位置重合。所谓逻辑相邻，是指除了一个变量不同外其余变量都相同的两个与项。第九页，共五十四页，2022年，8月28日0001111000011110

m0

m1

m2

m3

m4

m5

m6

m7

m12

m13

m14

m15

m8

m9

m10

m11ABCD四变量K图第十页，共五十四页，2022年，8月28日四、逻辑函数的卡诺图表示

1、先化为最小项表达式，并在相应的方格内填1，其余填0.2、直接将一般式画在图上。ABC

00011110011111第十一页，共五十四页，2022年，8月28日例：将F(A、B、C、D)用卡诺图表示解：0100011110001110CDABAB111111BCD11

ACD

ABC11AC1111m14,m15两次填10000图形法化简函数第十二页，共五十四页，2022年，8月28日例：图中给出输入变量A、B、C的真值表，填写函数的卡诺图ABCF000

0

0

1

01001110010111011100111000ABC0100011110

1

110

0

0

0

0

010111001110第十三页，共五十四页，2022年，8月28日例：图中给出输入变量A、B、C的真值表，填写函数的卡诺图ABCF000

0

0

1

01001110010111011100111000ABC0100011110

1

110

0

0

0

0ABABCF=ABC+AB得：第十四页，共五十四页，2022年，8月28日K图的特点

k图为方形图。n个变量的函数--k图有2n个小方格，分别对应2n个最小项；

k图中行、列两组变量取值按循环码规律排列，使变量各最小项之间具有逻辑相邻性。上下左右几何相邻的方格内，只有一个因子不同有三种几何相邻：邻接、相对（行列两端）和对称（图中以0、1分割线为对称轴）方格均属相邻0001111000011110

m0

m1

m2

m3

m4

m5

m6

m7

m12

m13

m14

m15

m8

m9

m10

m11ABCD四变量K图两个相邻格圈在一起，结果消去一个变量ABD

ADA1四个相邻格圈在一起，结果消去两个变量八个相邻格圈在一起，结果消去三个变量十六个相邻格圈在一起，结果mi=1卡诺图化简函数规则：几何相邻的2i（i=1、2、3…n）个小格可合并在一起构成正方形或矩形圈，消去i个变量，而用含（n-i）个变量的积项标注该圈。第十五页，共五十四页，2022年，8月28日第十六页，共五十四页，2022年，8月28日卡诺图化简的依据

相邻项相加时，反复应用，公式，函数表达式的项数和每项所含的因子数就会减小.第十七页，共五十四页，2022年，8月28日多余圈—不允许出现，否则不是最简形式第十八页，共五十四页，2022年，8月28日五、与或表达式的简化步骤先将函数填入相应的卡诺图中，存在的最小项对应的方格填1，其它填0。合并：按作圈原则将图上填1的方格圈起来，要求圈的数量少、范围大，圈可重复包围但每个圈内必须有新的最小项。每个圈写出一个乘积项。最后将全部积项逻辑加即得最简与或表达式画出逻辑电路图第十九页，共五十四页，2022年，8月28日【例】求F=m(1,3,4,5,10,11,12,13)的最简与或式。解：①画出F的K图∑②画K圈。第二十页，共五十四页，2022年，8月28日③写出最简式。④画出逻辑电路图。第二十一页，共五十四页，2022年，8月28日【例】求的最简与或式。解：①画出F的K图。给出的F为一般与或式，将每个与项所覆盖的最小项都填1，K图如图所示。第二十二页，共五十四页，2022年，8月28日②画K圈化简函数。③写出最简与或式。按图(b)圈法：该例说明，逻辑函数的最简式不是惟一的。本例有两种圈法，都可以得到最简式。按图(a)圈法：第二十三页，共五十四页，2022年，8月28日六、其他逻辑形式化简

1、与非逻辑步骤利用卡诺图法求出最简与或式两次取反，摩根定律画出逻辑电路图第二十四页，共五十四页，2022年，8月28日例：将与或结果用与非门实现。逻辑电路图：&&&&BCABCABDF第二十五页，共五十四页，2022年，8月28日例：将F(A、B、C、D)化为最简与非式解：0100011110001110CDAB111111111111ACADBCBDABC化简得：最简与非式为：第二十六页，共五十四页，2022年，8月28日2、或与逻辑步骤在卡诺图上求反函数得出原函数，摩根定律画出逻辑电路图和与或式相反第二十七页，共五十四页，2022年，8月28日例：将化简为最简或与式。（1）在卡诺图上求反函数1111111110000000(2)原函数第二十八页，共五十四页，2022年，8月28日关于最大项最大项：n个变量的最大项是n个变量的“或项”，其中每个变量必须而且只能以原变量或反变量的形式出现一次两变量A,B的最大项三变量A,B,C的最大项n个变量有2n个最大项第二十九页，共五十四页，2022年，8月28日M7M611111076最大项二进制数十进制数编号最大项的编号：通常用Mi表示最大项，M表示最大项,下标i为最大项编号。第三十页，共五十四页，2022年，8月28日相同变量构成的两个不同最大项的和为1。即Mi+Mj=1(i≠j)全部最大项之积为0，即对于任意一个最大项，仅有一组变量取值使这个最大项值为0，并且，最大项不同，使其值为0的变量取值不同最大项的性质：第三十一页，共五十四页，2022年，8月28日第三十二页，共五十四页，2022年，8月28日任何一个逻辑函数既可以等于其卡诺图上填1的那些最小项之和，也可以等于其卡诺图上填0的那些最大项之积，因此，如果要求出某函数的最简或与式，可以在该函数的卡诺图上合并那些填0的相邻项。这种方法简称为圈0合并，其化简步骤及化简原则与圈1合并类同，只要按圈逐一写出或项，然后将所得的或项相与即可。但需注意，或项由K圈对应的没有变化的那些变量组成，当变量取值为0时写原变量，取值为1时写反变量。第三十三页，共五十四页，2022年，8月28日或与逻辑化简方法2步骤画出卡诺图，圈0项得出最大项表达式画出逻辑电路图第三十四页，共五十四页，2022年，8月28日【例】求的最简或与式。①画出F的K图②圈K圈。圈0合并，其规律与圈1相同，即K圈的数目应最少，K圈所覆盖的0格应尽可能多。

解：③写出最简或与式。④画出逻辑电路图第三十五页，共五十四页，2022年，8月28日【例】

求的最简或与式。解：①画出F的K图。本例给出的F为一般或与式，因此将每个或项所覆盖的最大项都填0.②圈K圈化简函数。③写出最简或与式。④画出电路图。第三十六页，共五十四页，2022年，8月28日3、或非逻辑步骤先求出或与式两次取反，摩根定律画出逻辑电路图第三十七页，共五十四页，2022年，8月28日例：写出最简或非式。第三十八页，共五十四页，2022年，8月28日3、与或非逻辑步骤先求出与或式两次摩根定律，不展开画出逻辑电路图先求出反函数得出原函数画出逻辑电路图方法1方法2多一个反相器第三十九页，共五十四页，2022年，8月28日七、非完全描述逻辑函数的化简逻辑问题分为完全描述和非完全描述两种。如果对于输入变量的每一组取值，逻辑函数都有确定的值，则称这类函数为完全描述逻辑函数。如果输入变量的某些取值不允许出现，那么这类函数称为非完全描述的逻辑函数，此时函数值可以为0，也可以为1(通常将函数值记为Ø或×)。第四十页，共五十四页，2022年，8月28日非完全描述逻辑函数真值表ABCF000001010011100101110111010×0××1无关项第四十一页，共五十四页，2022年，8月28日无关项发生在以下两种情况：①由于某种条件的限制(或约束)使得输入变量的某些组合不可能出现，因而在这些取值下对应的函数值是“无关”紧要的，它可以为1，也可以为0。②某些输入变量取值所产生的输出并不影响整个系统的功能，因此可以不必考虑其输出是0还是1。非完全描述逻辑函数一般用以下方法表示：①在真值表或K图中填Ø或×，表示函数值为0或1均可。②在逻辑表达式中用约束条件来表示。第四十二页，共五十四页，2022年，8月28日例如，十字路口的交通灯规定红灯停，绿灯行，黄灯要注意(即黄灯一亮，未过停车线的车辆也须停车)。若以变量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。式中的最小项就是我们所说的无关项。第四十三页，共五十四页，2022年，8月28日

【例】化简以下逻辑函数。第四十四页，共五十四页，2022年，8月28日例：已知函数：

求其最简与或式0100011110001110CDAB解：填函数的卡诺图111111100000化简不考虑约束条件时：考虑约束条件时：0100011110001110CDAB111111100000第四十五页，共五十四页，2022年，8月28日

【例】试化简逻辑函数为最简或与式，并用与或非门实现电路。解：③将函数F变换为最简与或非式。②圈0求得F

的最简或与式