第2章 逻辑代数基础

1、1第二章第二章 逻辑代数基础逻辑代数基础Chapter 2 Logic Algebra Basic本章主要内容本章主要内容 第一节第一节 数制与码制数制与码制 第二节第二节 逻辑代数的基本概念与运算逻辑代数的基本概念与运算 第三节第三节 逻辑函数的公式化简法逻辑函数的公式化简法 第四节第四节 逻辑函数的卡诺图化简法逻辑函数的卡诺图化简法 第五节第五节 具有无关项的逻辑函数及其化简具有无关项的逻辑函数及其化简2上次授课内容上次授课内容 回顾回顾2.3 逻辑函数的公式化简法逻辑函数的公式化简法着重讨论着重讨论与或表达式与或表达式的化简。的化简。 一个逻辑函数可以有多种不同的逻辑表达式，一个逻辑函数

2、可以有多种不同的逻辑表达式，如如与与-或或表达式、表达式、或或-与与表达式、表达式、与非与非-与非与非表达式、表达式、或非或非-或非或非表达式以及表达式以及与与-或或-非非表达式。表达式。 乘积项最少且乘积项中变量因子最少。乘积项最少且乘积项中变量因子最少。常用的公式化简方法常用的公式化简方法（1）并项法）并项法 （2）吸收法）吸收法（3）消项法）消项法（4）消因子法）消因子法 （5）配项法）配项法注：公式化简的结果不一定唯一。注：公式化简的结果不一定唯一。3上次授课内容上次授课内容 回顾回顾2.4.1 逻辑函数的两种标准形式逻辑函数的两种标准形式 任何一个逻辑函数均可化成任何一个逻辑函数均可

3、化成“最小项之最小项之和和”与与“最大项之积最大项之积”这两种标准形式。这两种标准形式。一、最小项和最大项定义；一、最小项和最大项定义；二、最小项和最大项的特点；二、最小项和最大项的特点；2.4 逻辑函数的卡诺图化简法逻辑函数的卡诺图化简法具有具有相邻性相邻性的两个最小项的两个最小项之和可以合并成一项并消去一对因子之和可以合并成一项并消去一对因子。只有只有一个因子不同一个因子不同的两个最小项的两个最小项是具有是具有相邻性相邻性的最小项。的最小项。4上次授课内容上次授课内容 回顾回顾最大项与最小项之间存在如下关系：最大项与最小项之间存在如下关系：iiiiMmmM,kikkikikkiMmFmFm

4、F反演定律反演定律 逻辑或运算逻辑或运算：逻辑与运算：逻辑与运算00mABCMABC注意：注意：最小项和最大项的编号规则。最小项和最大项的编号规则。52.4.2 逻辑函数的卡诺图化简逻辑函数的卡诺图化简u 什么是卡诺图？什么是卡诺图？u 卡诺图的特点？卡诺图的特点？u 逻辑函数如何用卡诺图表示？逻辑函数如何用卡诺图表示？u 如何用卡诺图化简逻辑函数？（举例子）如何用卡诺图化简逻辑函数？（举例子） 2.5 具有无关项的逻辑函数及其化简具有无关项的逻辑函数及其化简u 什么是无关项？什么是无关项？u 无关项在逻辑化简中起到什么作用？无关项在逻辑化简中起到什么作用？u 举例说明利用无关项来化简逻辑函数

5、举例说明利用无关项来化简逻辑函数 6 在这个方格图中，将在这个方格图中，将 n 变量的全部变量的全部最小项最小项各用一个小方块表示，而且各用一个小方块表示，而且几何相邻几何相邻的小方格的小方格具有具有逻辑相邻性逻辑相邻性，即两相邻小方格所代表的最即两相邻小方格所代表的最小项只有一个变量取值不同小项只有一个变量取值不同。 所得图形叫所得图形叫 n 变量全部最小项的卡诺图。变量全部最小项的卡诺图。一、逻辑函数的卡诺图表示法一、逻辑函数的卡诺图表示法 （一）卡诺图（一）卡诺图（Karnaugh Diagram) 卡诺图是由美国工程师卡诺首先提出的一卡诺图是由美国工程师卡诺首先提出的一种用来描述逻辑函

6、数的特殊方格图。种用来描述逻辑函数的特殊方格图。2.4.2 逻辑函数的卡诺图化简逻辑函数的卡诺图化简一、逻辑函数的卡诺图表示法一、逻辑函数的卡诺图表示法 （一）卡诺图（一）卡诺图（Karnaugh Diagram) 卡诺图是由美国工程师卡诺首先提出的一卡诺图是由美国工程师卡诺首先提出的一种用来描述逻辑函数的特殊方格图。种用来描述逻辑函数的特殊方格图。71、一变量全部最小项的卡诺图、一变量全部最小项的卡诺图一变量一变量Y=F（A），），YA01AAYA01m0m1全部最小项：全部最小项：A， A卡诺图：卡诺图：2.4.2 逻辑函数的卡诺图化简逻辑函数的卡诺图化简一、逻辑函数的卡诺图表示法一、逻辑

7、函数的卡诺图表示法8YAB00011011A BA BA BA B2、二变量全部最小项的卡诺图、二变量全部最小项的卡诺图Y= F(A, B)9ABY0101m0m1m2m3YAB00011110A BA BA BA B00011110YABm0m1m3m2YABC0100011110m0m1m4m5m3m2m7m62、二变量全部最小项的卡诺图、二变量全部最小项的卡诺图Y= F(A, B)YABC0001111001m0m1m4m5m3m2m7m63、三变量全部最小项的卡诺图、三变量全部最小项的卡诺图 Y=F(A, B, C)10YABCD0001111000011110m0m1m4m5m3m2

8、m7m6m12m13m8m9m15m14m11m10YABCD00000101101010010111111001m0m1m3m2m4m5m7m6m8m9m11m10m12m13m15m144、四变量全部最小项的卡诺图、四变量全部最小项的卡诺图Y= F(A,B , C, D)注意：注意：左右、上下；左右、上下；在卡诺图中，在卡诺图中，每一行的首尾；每一行的首尾；每一列的首尾；每一列的首尾；的最小项都是逻辑相邻的。的最小项都是逻辑相邻的。115、五变量全部最小项的卡诺图、五变量全部最小项的卡诺图12 1、卡诺图中的、卡诺图中的小方格数等于最小项总数小方格数等于最小项总数，若逻辑，若逻辑函数的变量

9、数为函数的变量数为 n，则小方格数为，则小方格数为2n个。个。 2、卡诺图行列两侧标注的、卡诺图行列两侧标注的0和和1表示使对应方格内表示使对应方格内最小项为最小项为1的变量取值。同时，这些的变量取值。同时，这些0和和1组成的二进组成的二进制数大小就是对应制数大小就是对应最小项的编号最小项的编号。此外，在卡诺图中，。此外，在卡诺图中，几何相邻几何相邻的最小项具有的最小项具有逻辑相邻性逻辑相邻性，因此，变量的取，因此，变量的取值不能按照二进制数的顺序排列，必须按值不能按照二进制数的顺序排列，必须按循环码循环码排列排列。 3、卡诺图是一个、卡诺图是一个上下、左右闭合上下、左右闭合的图形，即不但的图

10、形，即不但紧挨着的方格是相邻的，而且上下、左右相对应的方紧挨着的方格是相邻的，而且上下、左右相对应的方格也是相邻的。格也是相邻的。 (二二) 卡诺图的特点卡诺图的特点13将变量分为行将变量分为行, 列两组，列两组，变量取值按典型格雷码变量取值按典型格雷码排列排列,相邻列相邻列(行行)之间只之间只有一个变量取值不同。有一个变量取值不同。具有循环邻接性。具有循环邻接性。卡诺图的每个格代表了卡诺图的每个格代表了函数的一个最小项。函数的一个最小项。A、B、C、D 取值取值 1A、B、C、D 取值取值 0 (二二) 卡诺图的特点卡诺图的特点14(三三)逻辑函数逻辑函数卡诺图卡诺图Y = AC + AC

11、+ BC + BC 卡诺图：卡诺图：YABC010001111011111100A(B+B)C +(A+A)BC Y=A(B+B)C +(A+A)BC + =(m1 , m2 ,m3 , m4 , m5 , m6 )1、把已知逻辑函数式化为最小项之和形式。、把已知逻辑函数式化为最小项之和形式。2、将函数式中包含的最小项在卡诺图对、将函数式中包含的最小项在卡诺图对应的方格中填应的方格中填 1，其余方格中填，其余方格中填 0。方法一：方法一：解：解：例：例： 用卡诺图表示之。用卡诺图表示之。15对于对于AC有：有：对于对于AC有：有：对于对于BC有：有：对于对于BC有：有：根据函数式直接填卡诺图根

12、据函数式直接填卡诺图方法二：方法二：YABC010001111011111001 1 1Y = AC + AC + BC + BC (三三)逻辑函数逻辑函数卡诺图卡诺图16BAACDDBADCBAY例：例：试用卡诺图表示逻辑函数试用卡诺图表示逻辑函数Y=ABCD+AB(C+C)D+A(B+B)CD+AB(C+C)(D+D)=(m1, m4, m6, m8, m9, m10, m11 , m15 ) YABCD0001111000011110m0m1m4m5m3m2m7m6m12m13m8m9m15m14m11m10YABCD00011110000111100110000100111011(三三

13、) 用卡诺图表示逻辑函数用卡诺图表示逻辑函数17 0 1 00 01 11 1001011010已知真值表已知真值表 每组变量（即最小项）所每组变量（即最小项）所对应的函数值对应的函数值 填入卡诺图中相应方格填入卡诺图中相应方格, 化简得到函数式。化简得到函数式。例：例：已知逻辑函数的卡诺图如图所示，已知逻辑函数的卡诺图如图所示，试写出该函数的逻辑函数式。试写出该函数的逻辑函数式。Y = ABC+ABC+ABC+ABCABC(四四) 由卡诺图得到逻辑函数由卡诺图得到逻辑函数18二、用卡诺图化简逻辑函数二、用卡诺图化简逻辑函数(一一) 用卡诺图化简逻辑函数的依据用卡诺图化简逻辑函数的依据(基本性

14、质基本性质) 基本原理：基本原理：各几何相邻方格的逻辑相邻性各几何相邻方格的逻辑相邻性。 性质性质1：卡诺图中卡诺图中两个相邻两个相邻“1”格格的最小项可以的最小项可以合并成一个与项，并消去合并成一个与项，并消去一个一个变量。变量。 19性质性质2：卡诺图中：卡诺图中四个相邻四个相邻“1”格格的最小项的最小项可以合并成一个与项，并消去可以合并成一个与项，并消去两个两个变量。变量。 例：例：(一一) 用卡诺图化简逻辑函数的依据用卡诺图化简逻辑函数的依据20 性质性质3：卡诺图中卡诺图中八个相邻八个相邻“1”格格的最小的最小项可以合并成一个与项，并消去项可以合并成一个与项，并消去三个三个变量。变量

15、。 (一一) 用卡诺图化简逻辑函数的依据用卡诺图化简逻辑函数的依据21推论：推论：在在n个变量卡诺图中，若有个变量卡诺图中，若有2k个个“1”格相邻格相邻(k = 0, 1, 2, 3,n)，它们可圈，它们可圈在一起加以合并，合并时可以消去在一起加以合并，合并时可以消去 k个个不不同的变量，简化为一个具有同的变量，简化为一个具有(n-k)个变量个变量的的与项。与项。若若k=n，合并时可消去全部变量，合并时可消去全部变量，结果为结果为1。(一一) 用卡诺图化简逻辑函数的依据用卡诺图化简逻辑函数的依据221、得到函数的、得到函数的真值表真值表或将函数化为或将函数化为最小项最小项之和的标准形式；之和

16、的标准形式；2、画出函数的卡诺图；、画出函数的卡诺图；3、合并最小项（即、合并最小项（即“画圈画圈”）；）； “画圈画圈”时应注意的问题：时应注意的问题： 不能漏画。不能漏画。“1”格一个也不能漏，否则表格一个也不能漏，否则表达式与函数不等；达式与函数不等； 可以重画。可以重画。“1”格允许被一个以上的圈包格允许被一个以上的圈包围，因为围，因为A+A=A；(一一) 用卡诺图求最简与或表达式用卡诺图求最简与或表达式步骤：步骤：23圈数要少。圈数要少。圈的个数应尽可能少，因为一个圈的个数应尽可能少，因为一个圈对应一个与项，即与项最少；圈对应一个与项，即与项最少；1101011100110000AB

17、CD0001010010111011DCABDACBABCYDCADBABCY错误！错误！1101011100110000ABCD0001010010111011正确！正确！“画圈画圈”时应注意的问题时应注意的问题24圈面要大。圈面要大。圈的面积越大越好，但必须为圈的面积越大越好，但必须为 2k个方个方格。这是因为圈越大，消去的变量就越多，与项中格。这是因为圈越大，消去的变量就越多，与项中的变量数就越少的变量数就越少例：例：1111111100000011ABCD0001010010111011CBAAY错误！错误！1111111100000011ABCD0001010010111011CBA

18、Y正确！正确！“画圈画圈”时应注意的问题时应注意的问题25每圈有新每圈有新“”. 每个圈至少应包含一个新的每个圈至少应包含一个新的“1”格，否则这个圈是多余的，即增加了冗余项；格，否则这个圈是多余的，即增加了冗余项；0100011111100010AB0001010010111011错误！错误！0100011111100010ABCD0001010010111011正确！正确！例：例：总之，即总之，即“可以重画，不能漏画，圈数要可以重画，不能漏画，圈数要少，圈面要大，每个圈必有一个新少，圈面要大，每个圈必有一个新1”。 “画圈画圈”时应注意的问题时应注意的问题264、写出最简与或表达式。、写出

19、最简与或表达式。YABC010001111011111001 1 1 上两式的内容不相同，但函数值一定相同。上两式的内容不相同，但函数值一定相同。YABC010001111011111001 1 1 Y1 =B+ABC+ACY1 =C+A+ BCAB将将Y1=AC+AC+BC+BC 化简为最简与或式。化简为最简与或式。此例说明此例说明: 逻辑函数的化简结果可能不唯一。逻辑函数的化简结果可能不唯一。例：例：(一一) 用卡诺图求最简与或表达式用卡诺图求最简与或表达式27Y2 = 例：将例：将Y2=(m0,m2,m4,m6,m8 m15)化简为最简与或式。化简为最简与或式。Y2 = ADY2 = A

20、D此例说明，为了使化简结果此例说明，为了使化简结果最简，可以重复利用最小项。最简，可以重复利用最小项。=A+DY2ABCD000111100001111011111100001111111111Y2ABCD0001111000011110111100001111例：用圈例：用圈 0 法化简法化简Y2。解：若卡诺图中解：若卡诺图中1的数目远远的数目远远大于大于0的数目，可用圈的数目，可用圈 0 的方法。的方法。AD+(一一) 用卡诺图求最简与或表达式用卡诺图求最简与或表达式28例例1：试用卡试用卡诺图诺图化简法求逻辑函数化简法求逻辑函数F F（A A，B B，C C，D D）=m =m (1(1

21、，2 2，4 4，9 9，1010，1111，1313，1515）的最简与或表达式。）的最简与或表达式。0101100001100111ABCD0001010010111011DCBADCBADCBADF错误！错误！解解：画出：画出卡诺图卡诺图画圈画圈写出函数表达式写出函数表达式写出最简与或表达式。写出最简与或表达式。More Examples29例例1：试用卡试用卡诺图诺图化简法求逻辑函数化简法求逻辑函数F F（A A，B B，C C，D D）=m =m (1(1，2 2，4 4，9 9，1010，1111，1313，1515）的最简与或表达式。）的最简与或表达式。解：解：画出卡诺图画出卡诺

22、图画圈画圈写出函数表达式写出函数表达式0101100001100111ABCD0001010010111011DCBDCBADCBADF写出最简与或表达式。写出最简与或表达式。30例例3:用卡诺图化简函数用卡诺图化简函数 Y= m(1, 3, 6, 7, 14)YABCACDABCDABC例例2:用卡诺图化简函数用卡诺图化简函数YABCD00011110000111101111111000000000BDACDY=+BCYABCD000111100001111011111注：卡诺图化简得到的最简与或式不一定唯一。注：卡诺图化简得到的最简与或式不一定唯一。Y=ABD+ABC+BCDY=ABD+A

23、CD+BCD写出最简与或表达式。写出最简与或表达式。312.5 具有无关项的逻辑函数及其化简具有无关项的逻辑函数及其化简一、约束项、任意项和逻辑函数式中的无关项一、约束项、任意项和逻辑函数式中的无关项 约束项约束项在某些情况下，输入变量的取值不是任意在某些情况下，输入变量的取值不是任意的。当限制某些输入变量的取值不能出现时，可以用它们的。当限制某些输入变量的取值不能出现时，可以用它们对应的最小项恒等于对应的最小项恒等于0来表示。这些来表示。这些恒等于恒等于0的最小项叫约的最小项叫约束项束项。 任意项任意项有时输入变量的某些取值是有时输入变量的某些取值是1还是还是0皆可，皆可，并不影响电路的功能

24、。并不影响电路的功能。在这些变量取值下，其值等于在这些变量取值下，其值等于1的的那些最小项称为任意项那些最小项称为任意项。 无关项无关项约束项约束项和和任意项任意项统称为逻辑函数中的无关统称为逻辑函数中的无关项。项。“无关无关”指是否将这些最小项写入逻辑函数式无关紧指是否将这些最小项写入逻辑函数式无关紧要，在卡诺图中用要，在卡诺图中用“”， “”或者或者d 表示无关项。表示无关项。在化在化简逻辑函数时，可认为它是简逻辑函数时，可认为它是1，也可认为它是，也可认为它是0。32无关项无关项由由“约束项约束项”和和“任意项任意项”组成，组成，这里只介绍由约束项形成的无关项这里只介绍由约束项形成的无关

25、项. 一个计算机操作码形成电路，一个计算机操作码形成电路，当当ABC=000 时，输出停机码时，输出停机码00；当只有当只有A=1时，输出加法操作码时，输出加法操作码01；当只有当只有B=1时，输出减法操作码时，输出减法操作码10；当只有当只有C=1时，输出乘法操作码时，输出乘法操作码11；其它输入状态不允许出现，其它输入状态不允许出现，试画电路的逻辑图。试画电路的逻辑图。有三个输入端有三个输入端A B C ，有两个输出端，有两个输出端Y1、Y0；331 、 列真值表列真值表ABC+ABC+ABC+ABC=01 11 00 1X XX XX XX X0 0 （m 3 ,m 5,m 6 ,m 7

26、 ）= 0A B C Y1 Y00 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 12、约束项、约束项(无关项无关项)的表示的表示 当限制某些输入变量的取值不当限制某些输入变量的取值不能出现时，可以用它们对应的最能出现时，可以用它们对应的最 小项恒等于小项恒等于0来表示。来表示。本例的约束项为本例的约束项为或：或：或：或：ABC = 0ABC = 0ABC = 0ABC = 03 . 写逻辑函数式写逻辑函数式Y1= m1+ m2Y0= m1+ m4约束项：约束项：m 3+m 5+m 6+m 7 = 034例例: : 判断一位十进制数是否为偶数。判断一位十进制数是否为

27、偶数。不会出现不会出现不会出现不会出现不会出现不会出现不会出现不会出现不会出现不会出现不会出现不会出现 说说 明明1 1 1 100 1 1 11 1 1 010 1 1 01 1 0 100 1 0 11 1 0 010 1 0 01 0 1 100 0 1 11 0 1 010 0 1 001 0 0 100 0 0 111 0 0 010 0 0 0Y A B C DY A B C D35 输入变量输入变量A，B，C，D取值为取值为00001001时，逻时，逻辑函数辑函数Y有确定的值，根据题意，偶数时为有确定的值，根据题意，偶数时为1，奇数，奇数时为时为0。)8 , 6 , 4 , 2

28、, 0(),(mDCBAY0)15,14,13,12,11,10(d无关项：无关项：36( , , , )(0,2,4,6,8)(10,11,12,13,14,15)Y A B C Dmd37 无关项在卡诺图对应的方格中用无关项在卡诺图对应的方格中用 X 表示，为了表示，为了化简逻辑函数化简逻辑函数,能利用到的能利用到的 X 便认为是便认为是1，利用不，利用不到的就认为是到的就认为是0。1 .利用无关项化简上例逻辑函数利用无关项化简上例逻辑函数Y1 = B+C Y0=A+C利用无关项化简逻辑函数利用无关项化简逻辑函数Y1ABC01000111100XX01 XXY0ABC01000111101

29、1XX0XX10已知已知Y1= m1+ m2Y0= m1+ m4约束项：约束项： m 3+m 5+m 6+m 7 = 0382. 画逻辑图画逻辑图 利用无关项化简的逻辑函数是否符合原功能要求利用无关项化简的逻辑函数是否符合原功能要求Y1=B+C Y0=A+C001110 xx01xxxxxxA B C 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 11ABY11Y0C验验 算算39 化简具有无关项的逻辑函数时，如果能合理化简具有无关项的逻辑函数时，如果能合理利用这些无关项，一般都可以得到更加简单的化利用这些无关项，一般都可以得到更加简单的化简结果。简结果。 合并

30、最小项时，究竟把卡诺图上的合并最小项时，究竟把卡诺图上的“”作为作为1还是还是0，应以得到的，应以得到的相邻最小项矩形组合最大，相邻最小项矩形组合最大，而且矩形组合数目最小而且矩形组合数目最小为原则。为原则。DCBADCBADCAY0ABCDDABCDCABDCABCDBADCBA已知约束条件为二、无关项在化简逻辑函数中的应用二、无关项在化简逻辑函数中的应用 例：例：试化简逻辑函数试化简逻辑函数40YABCD00011110000111101011100000 xxxxxxCDBDADY = AD + BD + CDDCBADCBADCAY0ABCDDABCDCABDCABCDBADCBA已知

31、约束条件为41例：例：试用卡诺图化简逻辑函数试用卡诺图化简逻辑函数思考一：思考一：由此例可得出什么结论和启示？由此例可得出什么结论和启示？13 71115(0,2,5)mdF W X Y Z （, , , ）（， ， ，）FWXYZ000111100001111011111xxx00000000F = YZ + WX1&11ZYWX42解答：解答：此例有两种解法，从原理而言，两种解法此例有两种解法，从原理而言，两种解法均正确，但就均正确，但就“最简最简”原则而言，只有一种解法原则而言，只有一种解法最简单、最可取。因此，最简单、最可取。因此，在考虑卡诺图化简不唯在考虑卡诺图化简不唯一性的

32、同时，还应考虑一性的同时，还应考虑“最简最简”原则原则。FWXYZ000111100001111011111xxx00000000F = YZ + WZ1&1ZYW13 71115(0,2,5)mdF W X Y Z （, , , ）（， ， ，）43思考二：思考二： 卡诺图化简法简单易懂，容易掌握，无需记卡诺图化简法简单易懂，容易掌握，无需记忆繁琐的公式；忆繁琐的公式； 而公式化简法需要记忆众多公式，繁琐！而公式化简法需要记忆众多公式，繁琐！ 可不可以只学卡诺图法化简？可不可以只学卡诺图法化简？44第一章第一章 补充题补充题)(GFADECBDBDBCBCAABF要求：要求：1.公式

33、法公式法CAABBCCAABDCCBDBDBCBACBDCDBACAABBCCAABCBDBDBCBAACBCAB)(GFADECBDBDBCBCAABFCAABBCCAABABACBCBDBDBCAACBCBDBDBCAABA公式法结果公式法结果 一一45)(GFADECBDBDBCBCAABFCBDBDBCBACAABBCCAABCAABBCCAABDCCBDBDBCBADBCBDCA要求：要求：1.公式法公式法ABDCDBC公式法结果公式法结果 二二公式法结果公式法结果 一一第一章第一章 补充题补充题46)(GFADECBDBDBCBCAABF要求：方法不限要求：方法不限)(GFADECBDBDBCBCAABFCAABBCCAABABACBCBDBDBCFABCD00011110000111100111111111111110FACDBDBCABDCDBC公式法结果公式法结果 一一ACDBCBD公式法结果公式法结果 二二综合法结果综合法结果 一一第一章第一章 补充题补充题47FABCD00011110000111100111111111111110FACDBCBDACDBDBC综合法结果