[工学]第2章逻辑代数的基本运算.ppt

第2章 逻辑代数的基本运算,2.1 逻辑代数 2.2 逻辑函数及其表示方法 2.3 逻辑代数的基本定律和恒等式 2.4 逻辑函数的卡诺图化简法,2.1 逻辑代数,逻辑代数又称布尔代数，其基本思想是19世纪英国数学家乔治布尔首先提出的。所谓逻辑就是事物因果之间所遵循的规律。为了避免用冗繁的文字来描述逻辑问题，逻辑代数采用逻辑变量和一套运算符组成逻辑函数表达式来描述事物的因果关系。它是用数学的方法来研究、证明、推理逻辑问题的一种数学工具。逻辑代数虽然和普通代数一样也是用字母表示变量，但是这两种代数中的变量含义是完全不同的，逻辑代数中的每个变量(逻辑变量)只有0和1两种取值,0和1不再表示数量的大小，而是表示对立的两种逻辑状态。例如，电灯的亮与灭、电动机的工作与停止。,下一页,返回,2.1 逻辑代数,在数字电路中，输入的信号是“条件”，输出的信号是“结果”，因此输入、输出信号之间存在一定的因果关系，这种因果关系称为逻辑关系。描述逻辑关系可以用语句、逻辑表达式、图形和表格等，描述逻辑关系的表格又称为真值表。表示逻辑运算所用的规定的图形符号称为逻辑符号。逻辑代数中有3种基本运算:“与”运算、“或”运算和“非”运算。下面就分别讨论这3种基本逻辑运算。,下一页,返回,上一页,2.1 逻辑代数,2.1.1 与运算 首先，我们来看一个具体的电路试验，电路如图2-1所示，电源E通过A,B两个串联的开关给电灯Y供电。 从图2-1(a)可以看出，只有开关A,B同时闭合，灯泡Y才会亮，A,B中有一个或两个断开，灯泡Y就不亮。其逻辑关系如表2-1所示，当开关的闭合用1表示、断开用0表示，灯泡的亮用1表示、不亮用0表示时，表2-1的逻辑关系就可以写成表2-2的形式，表2-2就是该逻辑的真值表。以上试验说明了这样一种逻辑关系:“只有当一个事件的几个条件全部具备之后，这个事件才会发生。”这种逻辑关系称为与逻辑与逻辑的表达式可以用下式来描述:,下一页,返回,上一页,2.1 逻辑代数,Y=AB或Y=AB (2-1) 式中的小圆点“”表示A,B的与运算，又叫逻辑乘。在不致引起混淆的前提下乘号“”可以被省略，而写成Y = AB。在有些文献里，用符号、表示与运算请读者注意。在电路中，与逻辑的逻辑符号如图2-1(b)所示。,下一页,返回,上一页,2.1 逻辑代数,2.1.2 或运算 当决定事件结果的几个条件中，只要有一个或一个以上的条件得到满足，结果就会发生时，这种逻辑关系称为或逻辑。如图2-2 (a)所示就是或逻辑模型电路，图中A,B是两个并联开关，Y是灯泡，E是电源。当A,B均不通时，则灯泡Y不亮;只要开关A或B有一个接通或两个均接通，则灯泡Y亮。可以看出，该电路满足或逻辑关系，其逻辑关系如表2-3所示。,下一页,返回,上一页,2.1 逻辑代数,仿照前面的方法，用0和1表示的或逻辑真值表如表2-4所示，用逻辑表达式描述可写为 Y=A+B (2-2) 式中的符号“+”表示A,B的或运算，也称为逻辑加。在有些文献里，用符号, 表示或运算，请读者注意。在电路中或逻辑的逻辑符号如图2-2(b)所示。,下一页,返回,上一页,2.1 逻辑代数,2.1.3 非运算 另外一种基本的逻辑运算就是非运算，即“一件事情(灯泡)的发生是以其相反的条件为依据”。这种逻辑关系称为非逻辑，其逻辑电路如图2-3(a)所示。图中E是电源，R是限流电阻。开关A闭合时，灯泡Y不亮;开关A断开时，灯泡Y则亮。,下一页,返回,上一页,2.1 逻辑代数,其逻辑关系如表2-5所示，同样也可写成真值表的形式，如表2-6所示，从真值表中可以看出，非逻辑的运算规律为:输入。则输出1;输入1则输出0,即“输入、输出始终相反”。非运算的逻辑表达式可写 (2-3) 式中，字母A上方的“-”表示非运算在某些文献里，也有用“”或“”来表示非运算的。用非逻辑门电路实现非运算，其逻辑符号如图2-3(b)所示。,下一页,返回,上一页,2.1 逻辑代数,2.1.4 几种常见的复合逻辑关系 与、或、非运算是逻辑代数中最基本的3种运算，任何复杂的逻辑关系都可以通过与、或、非组合而成。常见的几种复合逻辑关系的逻辑表达式、逻辑符号以及逻辑真值表分别介绍如下。,下一页,返回,上一页,2.1 逻辑代数,1.与非运算 逻辑表达式为 （2-4） 逻辑符号如图2-4所示。 真值表如表2-7所示 从表2-7中可以看出，只有A,B全为1时，Y才为0，与非逻辑和与逻辑正好相反，即“当一件事情的几个条件全部具备之后，这件事情才不发生”。,下一页,返回,上一页,2.1 逻辑代数,2.或非运算 逻辑表达式为 (2-5) 逻辑符号如图2-5所示。 真值表如表2-8所示。 同样从表2-8中可以看出，或非逻辑与或逻辑也正好相反。它的逻辑关系读者可以自己整理一下。,下一页,返回,上一页,2.1 逻辑代数,3.异或运算 逻辑表达式为 或者 (2-6) 逻辑符号如图2-6所示。 真值表如表2-9所示。 异或逻辑的特点是:输入相同时，输出为0;输入相异时，输出为1。,下一页,返回,上一页,2.1 逻辑代数,4.同或运算 逻辑表达式为 或者 (2-7) 逻辑符号如图2-7所示。 真值表如表2-10所示。,下一页,返回,上一页,2.1 逻辑代数,5.与或非运算 这是一个很典型的组合逻辑运算，从字面上也可以看出，它是与运算、或运算和非运算3种逻辑运算的组合。如图2-8所示是其逻辑符号，如图2-9所示是其等效逻辑电路图 逻辑表达式为 (2-8) 真值表如表2-11所示。 根据实际需要，可以选用不同数量输入端的与或非逻辑电路。,返回,上一页,2.2 逻辑函数及其表示方法,2.2.1 逻辑函数 一般地，函数是由自变量、因变量和对应法则构成的，自变量A,B,C,的取值确定以后，因变量Y的值也就唯一确定了。Y称为A,B,C,的函数。逻辑函数也是如此，但其变量取值只有0和1逻辑函数的一般表达式可写为 Y=F(A，B，C，) (2-9) 与、或、非是3种基本的逻辑运算，即3种基本的逻辑函数。但在实际的逻辑问题中，往往是由3种基本逻辑运算组合起来，构成一种复杂的运算形式。,下一页,返回,2.2 逻辑函数及其表示方法,2.2.2 逻辑函数的表示方法 逻辑函数可以用逻辑真值表、逻辑表达式、逻辑图、波形图等方法来表示。其中，逻辑图是用逻辑符号连接构成的图形下面说明各方法之间的转换。 例2-1 已知逻辑函数的表达式为 。要求:列出相应的真值表;已知输入波形;画出输出波形;画出逻辑图。,下一页,返回,上一页,2.2 逻辑函数及其表示方法,解:根据逻辑表达式，画出逻辑图如图2-10所示。 将A,B,C的所有组合代入逻辑表达式中进行计算，得到真值表如表2-12所示。 根据真值表画出的波形图如图2-11所示。,下一页,返回,上一页,2.2 逻辑函数及其表示方法,例2-2 已知函数Y的逻辑图如图2-12所示，写出函数Y的逻辑表达式。 解:根据逻辑图逐级写出输出端函数表达式如下: 最后得到函数Y的表达式为,下一页,返回,上一页,2.2 逻辑函数及其表示方法,通过真值表也可以直接写出逻辑表达式，方法是将真值表中Y为1的输入变量相与，取值为1的用原变量表示，为0的用反变量表示，将这些与项相加，就得到逻辑表达式例如.对于异或逻辑关系，根据真值表可以直接写出 。,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,2.3.1 逻辑代数的基本定律和恒等式 常用的逻辑代数定律和恒等式如下。 自等律 0-1律 重叠律 互补律,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,还原律 交换律 结合律 分配律 反演律,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,反演律公式或以推广到多个变量(摩尔根定律) 吸收率 其他常用恒等式有：,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,这些基本定律可以直接利用真值表证明，如果等式两边的真值表相同，则等式成立。 例2-3 证明反演率 证明:列举A,B的所有取值，并计算出 。其真值表如表2-13所示。,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,从表2-13可以直接看出反演率 是成立的。 几个常用公式的证明如下。 证明,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,2.3.2 逻辑代数的3个规则 1.代入规则 在任何一个逻辑等式中，如果将某个变量用同一个函数式来代换，则等式仍然成立。 例2-4 已知等式A+AB=A，若令Y=C+D代替等式中的A，试证明新等式(C+D)+(C+D)B=C+D成立。 证明:(C+D)+(C+D)B=(C+D)(1+B)=(C+D) 1=C+D,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,2.反演规则 对于任意一个逻辑函数Y，如果要求其反函数Y，只要将Y表达式中的所有“”换成“+”，“+”换成“”, “0”换成“1” , “1”换成“0”，原变量换成反变量，反变量换成原变量，即可求出函数Y的反函数。 注意: 要注意运算符号的优先顺序，不应改变原式的运算顺序。,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,不是一个变量上的“非”号应保持不变,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,3.对偶规则 对于函数Y，若把其表达式中的“”换成“+”，“+”换成“”，“0”换成“1”换成“0”，就可得到一个新的逻辑函数Y,Y就是Y的对偶式。,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,若两个逻辑式相等，则它们的对偶式也一定相等这就是对偶规则 例如:A+BCD=(A+B)(A+C)(A+D)，则A(B+C+D) =AB+AQ+AD。 使用对偶规则时，同样要注意运算符号的先后顺序和不是一个变量上的“非”号应保持不变。 利用对偶规则，可以从已知的公式中得到更多的运算公式，例如，吸收律 成立， 则它的对偶式也是成立的。,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,2.3.3 逻辑函数化简法 1.化简的意义 逻辑函数的简化意味着实现这个逻辑函数的电路元件少，从而降低成本，提高电路的可靠性例如:,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,逻辑函数表达式的表达形式大致可分为5种:“与或”式、“与非-与非”式“与或非”式、“或与”式、“或非-或非”式。它们可以相互转换。例如:,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,逻辑函数的化简，通常指的是化简为最简与或表达式。因为任何一个逻辑函数表达式都比较容易展开成与或表达式，一旦求得最简与或式，又比较容易变换为其他形式的表达式。 所谓最简与或式，是指式中含有的乘积项最少，并且每一个乘积项包含的变量也是最少的。,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,2.逻辑函数的化简法 代数化简法就是运用逻辑代数的基本定律、规则和常用公式化简逻辑函数。代数化简法经常采用下列几种方法。 (1)合并项法 利用公式 ，将两项合并为一项，消去一个变量。,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,(2)吸收法,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,(3)消去法,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,(4)配项法 利用公式 ，给某个乘积项配项，以达到进一步简化的目的。,下一页,返回,上一页,2.3 逻辑代数的基本定律和恒等式,使用配项法时要有一定的经验，否则越配越繁。通常对逻辑表达式进行化简要综合使用上述技巧例如: 在数字电路中，经常大量使用与非门，所以如何把一个化简了的与或表达式转换为与非-与非式，并用与非门去实现它，是十分重要的。一般来讲，用两次求反法可以将一个化简了的与或式转换成与非-与非式,返回,上一页,2.4 逻辑函数的卡诺图化简法,2.4.1 最小项的定义和性质 1.最小项的定义 对于N个变量，如果P是一个含有万个因子的乘积项，而在P中每一个变量都以原变量或反变量的形式出现一次，且仅出现一次，那么就称P是万个变量的一个最小项。例如 是3个变量A,B,C的最小项而 则不是 。 因为每个变量都有以原变量和反变量两种形式出现的可能，所以N个变量有2N个最小项。,下一页,返回,2.4 逻辑函数的卡诺图化简法,2.最小项的性质 每个最小项仅有一组变量的取值会使它的值为1,而其他变量取值都使它的值为0。 任意两个不同的最小项的乘积恒为0。 全部最小项之和恒为1。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,为了分析最小项的性质，下面列出3个变量的所有最小项的真值表，如表2-14所示。 由逻辑函数的真值表可以很容易地写出其标准与或式，此外，利用逻辑代数的定律、公式，可以将任何逻辑函数式展开或变换成标准与或式。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,3.最小项编号及表达式 为便于表示，要对最小项进行编号。编号的方法是:把与最小项对应的那一组变量取值组合当成二进制数，与其对应的十进制数就是该最小项的编号。代表符号如表2-15所示。 在标准与或式中，常用最小项的编号来表示最小项。例如: 常写成 或 。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,利用逻辑代数的基本公式，可以把任一个逻辑函数化成一种典型的表达式，这种典型的表达式是一组最小项之和，称为最小项表达式。下面举例说明把逻辑表达式展开为最小项表达式的方法。 例如:要将 化成最小项表达式，这时可以利用 的基本运算关系，将逻辑函数中的每一项都化成包含所有变量A,B,C的项，即: 此式是由4个最小项构成的，它是一组最小项之和，因此是一个最小项表达式。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,对照表2-15，上式中各最小项可分别表示为m7、m6、m3、m1、，所以又可写为 由此可见，任何一个逻辑函数都可以化为唯一的最小项表达式。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,2.4.2 逻辑函数的卡诺图表达法 1.逻辑变量卡诺图 卡诺图也叫最小项方格图，它将最小项按一定的规则排列成方格阵列。根据变量的数目n，则应有2n个小方格，每个小方格代表一个最小项。 卡诺图中将n;个变量分成行变量和列变量两组，行变量和列变量的取值决定了小方格的编号，也即最小项的编号。行、列变量的取值顺序一定要按格雷码排列。如图2-13所示分别列出了二变量、三变量和四变量的卡诺图。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,卡诺图的特点是形象地表达了各个最小项之间在逻辑上的相邻性。图中任何几何位置相邻的最小项，在逻辑上也是相邻的。 所谓逻辑相邻，是指两个最小项只有一个是互补的，而其余的变量都相同。 所谓几何相邻，不仅包括卡诺图中相接小方格的相邻，还包括方格间具有对称相邻性。对称相邻性是指以方格阵列的水平或垂直中心线为对称轴，彼此对称的小方格间也是相邻的。也就是说，各小方格上下左右在几何上相邻的方格内只有一个因子不同，有些文献中称此特点为循环邻接，这个重要特点成为卡诺图化简逻辑函数的主要依据。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,卡诺图的主要缺点是随着变量数目的增加，图形迅速复杂化，当逻辑变量在5个以上时，很少使用卡诺图。 2.逻辑函数的卡诺图表达法 根据逻辑函数的最小项表达式画函数卡诺图时，只要将表达式中包含的最小项对应的小方格内填上1，没有包含的最小项填上0(或不填)，就可以得到函数的卡诺图。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,(2)画出其卡诺图(见图2-14)。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,(2)画出其卡诺图(见图2-15),下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,2.4.3 利用卡诺图化简逻辑函数 1.化简的依据 我们知道，卡诺图具有循环邻接的特性，若图中两个相邻的方格均为1，则这两个相邻最小项的和将消去一个变量，如图2-13(c)所示四变量卡诺图中的m5和方格m7，它们的逻辑加是 ,消去了变量C，即消去了相邻方格中不相同的那个因子若卡诺图中4个相邻的方格为则这4个相邻的最小项的和将消去两个变量，如图2-13(c)所示四变量卡诺图中的m2,m3,m6,m7自们的逻辑加是:,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,从式中可以看出，消去了变量B和D,即消去相邻4个方格中不相同的那两个因子，这样反复应用 的关系，就可使逻辑表达式得到化简。这就是利用卡诺图法化简逻辑函数的基本原理。 2.化简的步骤 用卡诺图化简逻辑函数的步骤如下。 将逻辑函数写成最小项表达式。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,按最小项表达式填卡诺图，凡式中包含了的最小项，其对应方格填1，其余方格填0(或不填)。 合并最小项，即将相邻的1方格圈成一组，每一组含2n个方格，对应每个组写成一个新的乘积项(消去不同的变量，相同的变量写成与项)。 将所有组对应的乘积项相加。 有时也可以由真值表直接填卡诺图，以上的、两步骤就可合为一步。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,注意:画卡诺图的包围圈时应遵循以下原则。 包围圈内的方格数必定为2n个，n等于。,1 ,2 ,3 , 相邻方格包含上下底相邻，左右边相邻和四角相邻。 同一方格可以被不同的包围圈重复包围，但新增包围圈中一定要有新的方格，否则该包围圈是多余的。 包围圈内的方格数要尽可能多，包围圈的数目要尽可能少。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,化简后，一个包围圈对应一个与项(乘积项)，包围圈越大，所得乘积项中的变量越少。实际上，如果做到了使每个包围圈尽可能大，结果包围圈个数也就会少，使得消失的乘积项个数也越多，就可以获得最简的逻辑函数表达式。下面通过例子来熟悉用卡诺图化简逻辑函数的方法。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,例2-8 化简 。 解：(1)画出函数的卡诺图，如图2-16所示。 (2)按合并最小项的规律画出卡诺图圈。 (3)写出化简后的逻辑表达式。 例2-9 化简 解：画函数的卡诺图，化简过程如同图2-17所示。 合并最小项得到逻辑表达式为,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,3.具有约束项的逻辑函数的化简 在解决实际逻辑问题时，经常会遇到一些变量是任意的或者是不允许的、不可能的、不应该出现的，这些取值对应的最小项称为约束项，有些文献中也称为任意项、无关项、禁止项。这样一来，约束项在卡诺图化简时，我们对它的取值就是任意的了，也就是说它既可以取0，也可以取1，可以根据使函数尽量得到简化而定。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,具有约束项的逻辑函数的化简步骤如下。 填入具有约束项的逻辑函数的卡诺图。 画卡诺圈合并(约束项画“”，使化简结果简化的视为1，否则视为0。 写出化简结果。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,例2-10 设计一个逻辑电路，能够判断为奇数时，电路输出1;当十进制数为偶数时1位十进制数的奇偶性，当十进制数，电路输出0。 解:写出真值表。用8421 BCD码表示十进制数，4位码即为输入变量，当对应的十进制数为奇数时，函数值为1，反之为0，得到如表2-16所示的真值表。 我们知道，8421 BCD码只有10个，表中4位二进制码的后6种组合是无效的，是无关项，根本不会出现，它们对应的函数值可以任意假设，为0、为1都可以，通常以表示。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法,将真值表的内容填入4变量卡诺图，如图2-18所示。 画包围圈，此时应利用约束项(无关项)，显然，将m11,m13 ,m15对应的方格视为1，可以得到最大的包围圈。 写出结果:Y= D。若不利用约束项，则 ，结果将复杂很多。,下一页,返回,上一页,2.4 逻辑函数的卡诺图化简法