开关电路和布尔代数ppt课件

1、 广州大学数学与信息科学院广州大学数学与信息科学院陈蓉西陈蓉西 l布尔代数又称逻辑代数，正是以它的创立者英国数学家l乔治.布尔G.Boole而命名。 第一章 背景知识介绍l1815年生于伦敦的布尔家境贫寒，父亲是位鞋匠，无力供他读书。他的学问主要来自于自学。年仅12岁，布尔就掌握了拉丁文和希腊语，后来又自学了意大利语和法语。16岁开始任教以维持生活，从20岁起布尔对数学产生了浓厚兴趣，广泛涉猎著名数学家牛顿、拉普拉斯、拉格朗日等人的数学名著，并写下大量笔记。这些笔记中的思想，1847年被用于他的第一部著作之中。l1854年，已经担任柯克大学教授的布尔再次出版思维规律的研究逻辑与概率的数学理论基

2、础。以这两部著作，布尔建立了一门新的数学学科。l 在布尔代数里，布尔构思出一个关于0和1的代数系统，用基础的逻辑符号系统描述物体和概念。这种代数不仅广泛用于概率和统计等领域，更重要的是，它为今后数字计算机开关电路设计提供了最重要数学方法。l布尔一生发表了50多篇科学论文、两部教科书和两卷数学逻辑著作。为了表彰他的成功，都柏林大学和牛津大学先后授予这位自学的成才的数学家荣誉学位，他还被推选为英国皇家学会会员。 ll信息论的创始人克劳德香农C. E. Shannon对现代电子计算机的产生和发展有重要影响，是电子计算机理论的重要奠基人之一1.2 开关电路与布尔代数的关系开关电路与布尔代数的关系l19

3、38年，香农发表了著名的论文继电器和开关电路的符号分析，首次用布尔代数进行开关电路分析，并证明布尔代数的逻辑运算，可以通过继电器电路来实现，明确地给出了实现加，减，乘，除等运算的电子电路的设计方法。这篇论文成为开关电路理论的开端。l 香农在贝尔实验室工作中进一步证明，可以采用能实现布尔代数运算的继电器或电子元件来制造计算机，香农的理论还为计算机具有逻辑功能奠定了基础，从而使电子计算机既能用于数值计算，又具有各种非数值应用功能，使得以后的计算机在几乎任何领域中都得到了广泛的应用。l1840年取得了博士学位，香农在AT&T贝尔实验室里度过了硕果累累的15年。他用实验证实，完全可以采用继电器

4、元件制造出能够实现布尔代数运算功能的计算机。1948年，申龙又发表了另一篇至今还在闪烁光芒的论文通信的数学基础 ， 从而给自己赢来“信息论之父的桂冠。l1956年，他参与发起了达特默斯人工智能会议，成为这一新学科的开山鼻祖之一。他不仅率先把人工智能运用于电脑下棋方面，而且发明了一个能自动穿越迷宫的电子老鼠，以此证明计算机可以通过学习提高智能。l计算机运行的时候，程序就象一系列或真或假的命题，当命题进入电路时，按布尔代数他们将电路打开或关闭，例如当两个真的命题进入一个电路时。电路打开，但是当一个真的命题和一个假的命题进入一个电路时，电路关闭，利用布尔代数，我们就可以把数以百计的电路结合起来，并编

5、写出充满想象力的计算机应用程序。 l今天，布尔代数已成为我们生活中的一部分，因为我们的汽车、音响、电视和其它用具中都有计算机技术，它几乎无处不在，无所不能。实际上大多数人还没有意识到，但是我们的确已经生活在一个数字的时代。l1、布尔代数在数学和计算机科学中的重要地位l2、高度抽象和形式化的数学理论l3、在开关电路和逻辑等问题的应用l4、符合当今数学面向应用的主题，有利于提高学生的学习兴趣l1、计算机科学l2、通信系统l3、电子信息技术l4、电力信息系统l等相关专业的 课程l1 进位记数制进位记数制l 1).数制：日常生活中人们用一组固定的数数制：日常生活中人们用一组固定的数字和一套统一的规则表

6、示数目字和一套统一的规则表示数目l 2).基数基数 数制中所含数字符号的个数数制中所含数字符号的个数l 3).位值位值 位值也叫权位权），任何一个数位值也叫权位权），任何一个数都是由一串数字符号表示，其中每一位所都是由一串数字符号表示，其中每一位所表示的值除其本身的数值外，还与它所处的位表示的值除其本身的数值外，还与它所处的位置有关，由位置决定的值就叫权。置有关，由位置决定的值就叫权。2.2.不同数制间的转换不同数制间的转换 二进制转换八进制、二进制转换十六进制二进制转换八进制、二进制转换十六进制八进制数转换二进制、十六进制转换二进制八进制数转换二进制、十六进制转换二进制八进制转换十六进制、十

7、六进制转换八进制八进制转换十六进制、十六进制转换八进制 掌握数制间的转换的技巧。掌握数制间的转换的技巧。3 3、所有的十进制整数都能准确地转换成二、所有的十进制整数都能准确地转换成二进制整数，十进制小数不一定能精确地转进制整数，十进制小数不一定能精确地转换成二进制小数。换成二进制小数。如果一个二进制数N包含位整数和位小数，即 (N)2 = (bn-1 bn-2 b1 b0 b1 b2 bm)2(N)2 = bn-12n-1 bn-2 2n-2 b121 b0 20b1 2-1b2 2-2 bm2-m 上式是把一个二进制数按权展开，写成权展开式。 由二进制的权展开式很容易将一个二进制数转换为十进

8、制数。 二进制数与十进制数的相互转换 十进制数二进制数基数除法 1. 整数的转换将十进制整数除以基数2，余数便是二进制数的最低位；商再除以2，余数便是次低位；不断除以基数2，直到商为0，最后一次的余数是二进制数的最高位。 2222224 11001012 01 0 5 2 1 0高位低位41=(101001)2l0.392=0.78 0 (k1)l0.78 2=1.56 1 (k1)l0.56 2=1.12 1 (k2)l0.12 2=0.24 0 (k3)l0.24 2=0.48 0 (k4)l0.48 2=0.96 0 (k5)l0.96 2=1.92 1 (k6)(0.39) 10 =(

9、0.0110001)2用二进制用二进制对十进制对十进制数字编码数字编码用四位二进制用四位二进制表达一位十进制表达一位十进制 十进制十进制0 1234567890 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 1计算机只认识二进制，计算机只认识二进制，如何表示声音、图像？如何表示声音、图像？8 4 2 1l1847年,英国数学家乔治布尔(G.Boole)提出了用数学分析方法表示命题陈述的逻辑结构，并成功地将形式逻辑归结为一种代数演算，从而诞生了著名的“布尔代数”1938年，克劳德向农(C.E.Shannon)

10、将布尔代数应用于电话继电器的开关电路，提出了“开关代数”。随着电子技术的发展，集成电路逻辑门已经取代了机械触点开关，故“开关代数这个术语已很少使用。为了与“数字系统逻辑设计这一术语相适应，人们更习惯于把开关代数叫做逻辑代数。 逻辑代数是数子系统逻辑设计的理论基础和重要数学工具！知识要点：知识要点： 基本概念基本概念 ； 基本定理和规则基本定理和规则 ； 逻辑函数的表示形式逻辑函数的表示形式 ；逻辑函数的化简逻辑函数的化简 。 逻辑代数L是一个封闭的代数系统，它由一个逻辑变量集K，常量0和1以及“或”、“与”、“非三种基本运算所构成，记为L= K ,+ , ,- ,0 ,1 。该系统应满足下列公

11、理。 2.1 2.1 逻辑代数的基本概念逻辑代数的基本概念 公公 理理 1 交交 换换 律律 对于任意逻辑变量对于任意逻辑变量A、B，有，有 A + B = B + A ； AB = B A 公公 理理 2 结结 合合 律律 对于任意的逻辑变量对于任意的逻辑变量A、B、C，有，有 (A + B) + C = A + ( B + C ) ( AB ) C = A( B C )公公 理理 3 分分 配配 律律 对于任意的逻辑变量对于任意的逻辑变量A、B、C，有，有 A + ( BC ) = (A + B)(A + C) ； A( B + C) = AB + AC公公 理理 4 01 律律 对于任意

12、逻辑变量对于任意逻辑变量A，有，有 A + 0 = A ； A 1 = A A + 1 = 1 ； A 0 = 0 公理是一个代数系统的基本出发点，无需加以证明。公理是一个代数系统的基本出发点，无需加以证明。公公 理理 5 互互 补补 律律 对于任意逻辑变量对于任意逻辑变量A，存在唯一的，存在唯一的 ，使得，使得A1AA0AA2.1.1 2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算 逻辑代数和普通代数一样，是用字母表示其值可以变化的量，即变量。所不同的是： 1在普通代数中，变量的取值可以是任意实数，而逻辑代数是 一 种二值代数系统，任何逻辑变量的取值只有两种可能性取值0或取值1。

13、2逻辑值0和1是用来表征矛盾的双方和判断事件真伪的形式符号，无大小、正负之分。在数字系统中，开关的接通与断开，电压的高和低，信号的有和无，晶体管的导通与截止等两种稳定的物理状态，均可用1和0这两种不同的逻辑值来表征。一变量一变量二基本逻辑运算二基本逻辑运算 描述一个数字系统，必须反映一个复杂系统中各开关元件之间的联系，这种相互联系反映到数学上就是几种运算关系。 逻辑代数中定义了“或”、“与”、“非三种基本运算。 1 1“或运算或运算 如果决定某一事件是否发生的多个条件中，只要有一如果决定某一事件是否发生的多个条件中，只要有一个或一个以上条件成立，事件便可发生，则这种因果关系个或一个以上条件成立

14、，事件便可发生，则这种因果关系称之为称之为“或逻辑。或逻辑。 例如，用两个开关并联控制一个灯的照明控制电路。 在上图所示电路中，开关在上图所示电路中，开关A和和B并联控制灯并联控制灯F。可以看出，。可以看出，当开关当开关A、B中有一个闭合或者两个均闭合时，灯中有一个闭合或者两个均闭合时，灯F即亮。因即亮。因此，灯此，灯F与开关与开关A、B之间的关系是之间的关系是“或逻辑关系。或逻辑关系。 ABF 并联开关电路并联开关电路 用两个开关并联控制一个灯的电路如下图所示。 逻辑代数中，“或逻辑用“或运算描述。其运算符号为“+”，有时也用“”表示。两变量“或运算的关系可表示为 F = A + B 或者

15、F = A B 读作“F等于A或B”。 在下图所示电路中，假定开关断开用0表示，开关闭合用1表示；灯灭用0表示，灯亮用1表示，则灯F与开关A、B的关系如下表所示。 即：A、B中只要有一个为1，则F为1；仅当A、B均为0时，F才为0。A0111100BF01011 “或运算表或运算表 ABF 并联开关电路并联开关电路 “或运算的运算法则：或运算的运算法则： 0 + 0 = 0 1 + 0 = 1 0 + 1 = 1 1 + 1 = 1 实现实现“或运算关系的逻辑电路称为或运算关系的逻辑电路称为“或门。或门。 2 2“与与” 运算运算 如果决定某一事件发生的多个条件必须同时具备，如果决定某一事件发

16、生的多个条件必须同时具备，事件才能发生，则这种因果关系称之为事件才能发生，则这种因果关系称之为“与逻辑。与逻辑。 在逻辑代数中，在逻辑代数中，“与逻辑关系用与逻辑关系用“与运算描述。与运算描述。其运算符号为其运算符号为“”，有时也用，有时也用“”表示。两变量表示。两变量“与运与运算关系可表示为算关系可表示为 F = AB F = AB 或者或者 F F = AB= AB 即：若即：若A A、B B均为均为1 1，则，则F F为为1 1；否则，；否则，F F为为0 0。 +ABF当输入变量为N个时：F=A+B+C+常用符号表示A0110000BF01011 “与运算表与运算表 ABF 串联开关电

17、路串联开关电路 例如，在右上图所示电路中，两个开关串联控制同一个灯。显然，仅当两个开关均闭合时，灯才能亮，否则，灯灭。 假定开关闭合状态用1表示，断开状态用0表示，灯亮用1表示，灯灭用0表示，则电路中灯F和开关A、B之间的关系即上表所示的“与运算关系。 “与逻辑关系如下表所示。 “与运算的运算法则: 0 0 = 0 1 0 = 0 0 1 = 0 1 1 = 1 数字系统中，实现“与运算关系的逻辑电路称为“与门。 3 3“非非” 运算运算 如果某一事件的发生取决于条件的否定，即事件与如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果关系称为事件发生的条件之间构成

18、矛盾，则这种因果关系称为“非非逻辑。逻辑。 在逻辑代数中，在逻辑代数中，“非逻辑用非逻辑用“非运算描述。其运非运算描述。其运算符号为算符号为“ ”，有时也用，有时也用“”表示。表示。“非运算的逻辑关系可非运算的逻辑关系可表示为表示为 F = F = 或者或者 F = F = A A读作读作“F F等于等于A A非非”。 即：若即：若A A为为0 0，则，则F F为为1 1；若；若A A为为1 1，则，则F F为为0 0。A&ABF常用符号表示ABF常用符号表示 “非运算表非运算表 AF0101 开关与灯并联电路 AF 例如，在右上图所示电路中，开关与灯并联。显然，仅当开关断开时，灯亮；

19、一旦开关闭合，则灯灭。令开关断开用0表示，开关闭合用1表示，灯亮用1表示，灯灭用0表示，则电路中灯F与开关A的关系即为上表所示“非运算关系。 “非逻辑关系可用下表描述 。1001 “非运算的运算法则： 数字系统中实现“非运算功能的逻辑电路称为“非门，有时又称为“反相器”。2.1.2 2.1.2 逻辑函数及逻辑函数间的相等逻辑函数及逻辑函数间的相等 逻辑代数中函数的定义与普通代数中函数的定义类似，即随自变量变化的因变量。但和普通代数中函数的概念相比，逻辑函数具有如下特点： 1逻辑函数和逻辑变量一样，取值只有0和1两种可能 ； 2函数和变量之间的关系是由“或”、“与”、“非三种基本运算决定的 。

20、一、逻辑函数的定义一、逻辑函数的定义 图中，F被称为A1，A2，An的逻辑函数，记为 F = f( A1，A2，An ) 逻辑电路输出函数的取值是由逻辑变量的取值和电路本逻辑电路输出函数的取值是由逻辑变量的取值和电路本身的结构决定的。身的结构决定的。 任何一个逻辑电路的功能都可由相应的逻辑函数完全描述，任何一个逻辑电路的功能都可由相应的逻辑函数完全描述，因此，能够借助抽象的代数表达式对电路加以分析研究。因此，能够借助抽象的代数表达式对电路加以分析研究。 广义的逻辑电路逻辑电路逻辑电路 FA1A2An从数字系统研究的角度看，逻辑函数的定义如下从数字系统研究的角度看，逻辑函数的定义如下: 设某一逻

21、辑电路的输入逻辑变量为A1，A2，An，输出逻辑变量为F，如下图所示。 逻辑函数和普通代数中的函数一样存在是否相等的问题。 什么叫做两个逻辑函数相等呢？ 设有两个相同变量的逻辑函数 F1 = f1( A 1,A 2, ,A n) F2 = f2( A 1,A 2, ,A n) 若对应于逻辑变量 A1 ,A2 , , An的任何一组取值，F1和F2的值都相同，则称函数F1和F2相等，记作F1 = F2 。 如何判断两个逻辑函数是否相等？ 通常有两种方法,一种方法是真值表法，另一种方法是代数法。2.1.3 2.1.3 逻辑函数的表示法逻辑函数的表示法 该逻辑表达式描述了一个两变量的逻辑函数F。函数

22、F和变量A、B的关系是：当变量A和B取值不同时，函数F的值为“1”； 取值相同时，函数F的值为“0”。BABABA,fF 逻辑表达式是由逻辑变量和“或”、“与”、“非3种运算符以及括号所构成的式子。例如一、逻辑表达式一、逻辑表达式 如何对逻辑功能进行描述？ 常用的方法有逻辑表达式、真值表、卡诺图三种。 逻辑表达式的简写逻辑表达式的简写: 1. “非运算符下可不加括号，如非运算符下可不加括号，如 ， 等。等。BABA 2. “与运算符一般可省略，如与运算符一般可省略，如AB可写成可写成AB。 3. 在一个表达式中，如果既有“与运算又有“或运算，则按先“与后“或的规则进行运算，可省去括号，如(AB

23、)+(CD)可写为AB+CD。 留意：(A+B)(C+D)不能省略括号，即不能写成A+BC+D！ 运算优先法则： ( )高高低低 + 4. (A+B)+C或者或者A+(B+C)可用可用A+B+C代替；代替；(AB)C或或者者A(BC)可用可用ABC代替。代替。 二、真值表二、真值表 依次列出一个逻辑函数的所有输入变量取值组合及其相应函数值的表格称为真值表。 由于一个逻辑变量有0和1两种可能的取值，n个逻辑变量共有2n种可能的取值组合。因此，一个n个变量的逻辑函数，其真值表有2n行。真值表由两部分组成：真值表由两部分组成： 左边一栏列出变量的所左边一栏列出变量的所有取值组合，为了不发生遗有取值组

24、合，为了不发生遗漏，通常各变量取值组合按漏，通常各变量取值组合按二进制数码顺序给出；右边二进制数码顺序给出；右边一栏为逻辑函数值。一栏为逻辑函数值。例如，逻辑函数例如，逻辑函数 的真值表如右表所示。的真值表如右表所示。 CABAF 函数函数 的真值表的真值表 CABAF1 0 1 1 0 1 1 1 A B C F 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 三、卡诺图三、卡诺图 卡诺图是由表示逻辑变量所有取值组合的小方格所构成的平面图。 这种用图形描述逻辑函数的方法，在逻辑函数化简中十分有用，将在后面结合函数化简问题进行详细介绍。 描述逻辑

25、逻辑函数的3种方法各有特点,可用于不同场合。但针对某个具体问题而言，它们仅仅是同一问题的不同描述形式，相互之间可以很方便地进行变换。 2 .2 2 .2 逻辑代数的基本定理和规则逻辑代数的基本定理和规则 根据逻辑代数的公理，可以推导出逻辑代数的基本定理。根据逻辑代数的公理，可以推导出逻辑代数的基本定理。 下面给出常用的组定理下面给出常用的组定理,并对定理中的一个表达加以证并对定理中的一个表达加以证明明,另一个留给读者自己证明。另一个留给读者自己证明。2.2.1 2.2.1 基本定理基本定理 定理定理1 0 + 0 = 0 1 + 0 = 1 0 0 = 0 1 0 = 0 0 + 1 = 1

26、1 + 1 = 1 0 1 = 0 1 1 = 1 证明：在公理证明：在公理4中，中，A表示集合表示集合K中的任意元素，因而可中的任意元素，因而可以是以是0或或1。用。用0和和1代入公理代入公理4中的中的A，即可得到上述关系。，即可得到上述关系。 如果以如果以1和和0代替公理代替公理5中的中的A，则可得到如下推论：，则可得到如下推论： 0110 定理定理2 A + A = A ； A A = A 证明证明 A+A = (A+A) 1 公理公理4 = (A+A) 公理公理5 = A+ 公理公理3 = A+0 公理公理5 = A 公理公理4 )A(A)A(A定理定理3 A + A B = A ；

27、A ( A + B ) = A 定理定理4 A + B = A + B ; A ( + B ) = A B AA 证明 A + B = (A + )(A + B) 公理3 = 1(A+B) 公理5 = A+B 公理4 AA定理定理5 = A A证明证明 令令 = X 因此因此 X = 0 + X = 1 公理公理5 但是但是 A = 0 + A = 1 公理公理5 由于由于X和和A都满足公理都满足公理5。因此，根据公理。因此，根据公理5的唯一的唯一性，得到性，得到A = X。AAAAA定理定理6BABABABA证明证明 由于由于 ( ) + ( A + B )=( + A )+B 公理公理2

28、=( + A )+B 定理定理4 =A + ( B + ) 公理公理1,2 =A+1 公理公理5 =1 公理公理4 而且而且 ( )( A+B ) = A + B 公理公理3 = 0 + 0 公理公理1,5 =0 定理定理1 所以，根据公理所以，根据公理5的唯一性可得的唯一性可得BABABABABABABABB定理定理7 AB + A = A ( A + B ) ( A+ ) = A BB定理定理8 A B + C + B C = A B + C (A + B) ( + C) (B + C) = (A + B) ( + C) AAAAA 证明证明 AB + C + BC = AB + C +

29、BC( A + ) 公理公理5 = AB + C + BCA + BC 公理公理3 = AB + ABC + C + BC 公理公理1 = AB(1+C) + C(1+B) 公理公理3 = AB(C+1) + C(B+1) 公理公理1 = AB + C 公理公理4 AAAAAAAAAA2.2.2 2.2.2 重要规则重要规则 逻辑代数有3条重要规则，即代入规则、反演规则和对偶规则。 例如，给定逻辑等式A(B+C)=AB+AC，若等式中的C都用(C+D)替代，则该逻辑等式仍然成立，即 AB+(C+D)= AB+A(C+D) 代入规则的正确性是显然的，因为任何逻辑函数都和逻辑变量一样，只有0和1两

30、种可能的取值。 任何一个含有变量A的逻辑等式，如果将所有出现A的位置都代之以同一个逻辑函数F，则等式仍然成立。这个规则称为代入规则。 一、代入规则一、代入规则 代入规则的意义：代入规则的意义： 利用代入规则可以将逻辑代数公理、定理中的变量用任意利用代入规则可以将逻辑代数公理、定理中的变量用任意函数代替，从而推导出更多的等式。这些等式可直接当作公函数代替，从而推导出更多的等式。这些等式可直接当作公式使用，无需另加证明。式使用，无需另加证明。 留意：使用代入规则时,必须将等式中所有出现同一变量的地方均以同一函数代替，否则代入后的等式将不成立。 例如，若用逻辑函数F = f(A1,A2,，An)代替

31、公理A + = 1 中的变量A，便可得到等式 f(A1,A2,，An) + (A1,A2,，An) = 1即一个函数和其反函数进行“或运算，其结果为1。Af二、反演规则二、反演规则 反演规则实际上是定理6的推广，可通过定理6和代入规则得到证明。显然，运用反演规则可以很方便地求出一个函数的反函数。 例如，已知函数 ，根据反演规则可得到 D)C()B(AFDCBAF 若将逻辑函数表达式F中所有的“”变成“+”，“+”变成“”，“0变成“1”，“1变成“0”，原变量变成反变量，反变量变成原变量，并保持原函数中的运算顺序不变 ，则所得到的新的函数为原函数F的反函数 。这一规则称为反演规则。 F即： “

32、” “+”， “0” “1”，原变量 反变量 留意留意: 使用反演规则时，应保持原函数式中运算符号的使用反演规则时，应保持原函数式中运算符号的优先顺序不变。优先顺序不变。三、对偶规则三、对偶规则 如果将逻辑函数表达式F中所有的“”变成“+”，“+”变成“”，“0变成“1”，“1变成“0”，并保持原函数中的运算顺序不变，则所得到的新的逻辑表达式称为函数F的对偶式，并记作F。例如， 例如，已知函数 ，根据反演规则得到的反函数应该是 而不应该是 ！错误)ED(CBAFE)D(CBAFEDCBAF F = A B + ( C + 0) ; F= (A + B)( + C1) BB 留意：如果F的对偶式

33、是F，则F的对偶式就是F。即，(F)=F,可见F和F互为对偶式。 若逻辑函数表达式的对偶式就是原函数表达式本身，即F=F，则称函数F为自对偶函数。)CBA(B)C(AF例如，函数 是一自对偶函数。由于F)CBA(B)C(A )C(AB)ACB( )C)(ACBB()CA)(ACB( )C)(ACB(B)C)(ACBA( )C)(ACB(B)CBA( )C)(ACB)(B(A )C)(AB)(ABC)(B(A )CB)(ABC(AF， 留意:求逻辑表达式的对偶式时，同样要保持原函数的运算顺序不变。 显然，利用对偶规则可以使定理、公式的证明减少一半。 若两个逻辑函数表达式F和G相等，则其对偶式F和

34、G也相等。这一规则称为对偶规则。 根据对偶规则，当已证明某两个逻辑表达式相等时，即可知道它们的对偶式也相等。 例如，已知AB+ C+BC=AB+ C，根据对偶规则对等式两端的表达式取对偶式，即可得到等式(A+B)( +C)(B+C)=(A+B)( +C) AAAA2.2.3 2.2.3 复合逻辑复合逻辑 实际应用中广泛采用“与非门、“或非门、“与或非门、“异或门等门电路。这些门电路输出和输入之间的逻辑关系可由3种基本运算构成的复合运算来描述，故通常将这种逻辑关系称为复合逻辑，相应的逻辑门则称为复合门。 一、与非逻辑一、与非逻辑 与非逻辑是由与、非两种逻辑复合形成的，可用逻辑函与非逻辑是由与、非

35、两种逻辑复合形成的，可用逻辑函数表示为数表示为 逻辑功能：只要变量逻辑功能：只要变量A A、B B、C C、中有一个为中有一个为0 0，则函数，则函数F F为为1 1；仅当变量；仅当变量A A、B B、C C、全部为全部为1 1时，函数时，函数F F为为0 0。 实现与非逻辑的门电路称为实现与非逻辑的门电路称为“与非门。与非门。 CBAF 由于与非逻辑又可实现3种基本逻辑，所以，只要有了与非门便可组成实现各种逻辑功能的电路，通常称与非门为通用门。采用与非逻辑可以减少逻辑电路中门的种类，提高标准化程度。 由定理 AB=A+B 不难看出，“与之“非可以产生“或的关系。因此，实际上只要有了与非逻辑便

36、可实现与、或、非3种基本逻辑。以两变量与非逻辑为例： 与:BABA1BAF 或:BABA1B1AF 非:A1AF二、或非逻辑二、或非逻辑 逻辑功能：只要变量逻辑功能：只要变量A A、B B、CC中有一个为中有一个为1 1，则函数，则函数F F为为0 0；仅当变量；仅当变量A A、B B、CC全部为全部为0 0时，函数时，函数F F为为1 1。 实现或非逻辑的门电路称为实现或非逻辑的门电路称为“或非门。或非门。 或非逻辑是由或、非两种逻辑复合形成的，可用逻辑函数表示为 CBAF 同样，由定理 可知，“或之“非可以产生“与的关系。因此，只要有了或非逻辑也可以实现与、或、非3种基本逻辑。以两变量或非

37、逻辑为例： BABA 与：BABA0B0AF 或:BABA0BAF 非: A0AF 或非门同样可实现各种逻辑功能，是一种通用门。三、与或非逻辑三、与或非逻辑 逻辑功能：仅当每一个逻辑功能：仅当每一个“与项均为与项均为0 0时，才能使时，才能使F F为为1 1，否则否则F F为为0 0。 实现与或非功能的门电路称为实现与或非功能的门电路称为“与或非门。与或非门。 显然，可以仅用与或非门去组成实现各种功能的逻辑电路。但实际应用中这样做一般会很不经济，所以，与或非门主要用来实现与或非形式的函数。必要时可将逻辑函数表达式的形式变换成与或非的形式。 与或非逻辑是由3种基本逻辑复合形成的，逻辑函数表达式的

38、形式为 CDABF四、异或逻辑及同或逻辑四、异或逻辑及同或逻辑 逻辑功能：变量逻辑功能：变量A A、B B取值相同，取值相同，F F为为0 0；变量；变量A A、B B取值相取值相异，异，F F为为1 1。 实现异或运算的逻辑门称为实现异或运算的逻辑门称为“异或门异或门” 。 1 1异或逻辑异或逻辑 当多个变量进行异或运算时，可用两两运算的结果再运算，也可两两依次运算。 异或逻辑是一种两变量逻辑关系，可用逻辑函数表示为 BABABAF 根据异或逻辑的定义可知： A 0 = A A 1 = A A = 0 A = 1 AA 留意：在进行异或运算的多个变量中，若有奇数个变量的值为1，则运算结果为1

39、；若有偶数个变量的值为1，则运算结果为0。 例如， F = A B C D = (A B) (C D) (两两运算的结果再运算) =(A B) C D (两两依次运算)2 2同或逻辑同或逻辑 同或逻辑也是一种两变量逻辑关系，其逻辑函数表达式为 功能逻辑：变量功能逻辑：变量A A、B B取值相同，取值相同，F F为为1 1；变量；变量A A、B B取值相取值相异，异，F F为为0 0。实现同或运算的逻辑门称为。实现同或运算的逻辑门称为“同或门同或门” 。 F = A B = + AB 式中，“”为同或运算的运算符。 BA 同或逻辑与异或逻辑的关系既互为相反，又互为对偶。同或逻辑与异或逻辑的关系既

40、互为相反，又互为对偶。即有：即有： 由于同或实际上是异或之非，所以实际应用中通常用异或门加非门实现同或运算。 留意：当多个变量进行同或运算时，若有奇数个变量的值为0，则运算结果为0；反之，若有偶数个变量的值为0，则运算结果为1。 BAABBA B)A)(B(A B)ABA(B)(ABABAAB )BB)(AA( BABA BA ，2.3 2.3 逻辑函数表达式的形式与变换逻辑函数表达式的形式与变换 任何一个逻辑函数，其表达式的形式都不是唯一的。下面从分析与应用的角度出发，介绍逻辑函数表达式的基本形式、标准形式及其相互转换。 2.3.1 2.3.1 逻辑函数表达式的两种基本形式逻辑函数表达式的两

41、种基本形式 两种基本形式：指“与-或表达式和“或-与表达式。 一、一、“与与- -或表达式或表达式 “与与-或表达式：是指由若干或表达式：是指由若干“与项进展与项进展“或运算或运算构成的表达式。每个构成的表达式。每个“与项可以是单个变量的原变量或者与项可以是单个变量的原变量或者反变量，也可以由多个原变量或者反变量相反变量，也可以由多个原变量或者反变量相“与组成。与组成。 例如，例如， 均为均为“与项与项”，将这，将这3个个“与项相与项相“或便可构成一个或便可构成一个3变量函数的变量函数的“与或表达式。即与或表达式。即 CCBABA、CCBABAF “与项有时又被称为“积项”，相应地“与-或表达

42、式又称为“积之和表达式。 二、二、“或或- -与表达式与表达式 “或项有时又被称为“和项”，相应地“或与表达式又称为“和之积表达式。 C)DB)(ACB)(BA(D)C,B,F(A, “或或-与表达式：是指由若干与表达式：是指由若干“或项进展或项进展“与运算构成与运算构成的表达式。的表达式。 每个每个“或项可以是单个变量的原变量或者反变量，也可或项可以是单个变量的原变量或者反变量，也可以 由 多 个 原 变 量 或 者 反 变 量 相以 由 多 个 原 变 量 或 者 反 变 量 相 “ 或 组 成 。或 组 成 。 例如，例如， 、 、 、D 均为均为“或项或项”，将这，将这4个个“或项相或

43、项相“与便可构成一个与便可构成一个4变量函数的变量函数的“或或-与表达式。与表达式。即即BA CB CBA 该逻辑函数是该逻辑函数是“与与或式？不是！是或式？不是！是“或或与式？也与式？也不是！但不论什么形式都可以变换成两种基本形式。不是！但不论什么形式都可以变换成两种基本形式。 2.3.2 2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 逻辑函数表达式可以被表示成任意的混合形式。例如， B)CBC)(AB(AC)B,F(A, 逻辑函数的两种基本形式都不是唯一的。例如逻辑函数的两种基本形式都不是唯一的。例如 为了在逻辑问题的研究中使逻辑功能可和唯一的逻辑表达式对为了在逻辑问题的研

44、究中使逻辑功能可和唯一的逻辑表达式对应，引入了逻辑函数表达式的标准形式。逻辑函数表达式的标应，引入了逻辑函数表达式的标准形式。逻辑函数表达式的标准形式是建立在最小项和最大项概念的基础之上的。准形式是建立在最小项和最大项概念的基础之上的。 CAABBCCAABF一、最小项和最大项一、最小项和最大项 （1定义：如果一个具有定义：如果一个具有n个变量的函数的个变量的函数的“与项包含与项包含全部全部n个变量，每个变量都以原变量或反变量形式出现一次，个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次，则该且仅出现一次，则该“与项被称为最小项。有时又将最小与项被称为最小项。有时又将最小项称为标准

45、项称为标准“与项与项”。 1最小项最小项 （3简写：用简写：用mi表示最小项。表示最小项。 下标下标i的取值规则是：按照变量顺序将最小项中的原变的取值规则是：按照变量顺序将最小项中的原变量用量用1表示，反变量用表示，反变量用0表示，由此得到一个二进制数，与表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标该二进制数对应的十进制数即下标i的值。的值。 （2最小项的数目：最小项的数目：n个变量可以构成个变量可以构成2n个最小项。个最小项。 例如，3个变量A、B、C可以构成 、 、 A B C共8个最小项。 CBACBA 在由n个变量构成的任意“与项中，最小项是使其值为1的变量取值组合数最

46、少的一种“与项”，这也就是最小项名字的由来。 （4） 性质 最小项具有如下四条性质。 性质1： 任意一个最小项，其相应变量有且仅有一种取值使这个最小项的值为1。并且，最小项不同，使其值为1的变量取值不同。 例如，3变量A、B、C构成的最小项 A C 可用 m5 表示。由于 m5 (5)10 101ACBB 性质3： n个变量的全部最小项相“或为1。 通常借用数学中的累加符号“”，将其记为1n20i1mi 性质2： 相同变量构成的两个不同最小项相“与” 为0。 因为任何一种变量取值都不可能使两个不同最小项同时为1，故相“与为0。 即 mi mj = 0 性质4： n个变量构成的最小项有n个相邻最

47、小项。 相邻最小项：是指除一个变量互为相反外，其余部分均相同的最小项。例如 ，三变量最小项A B C和 。 BCA 定义：如果一个具有定义：如果一个具有n个变量函数的个变量函数的“或项包含全部或项包含全部n个变量，每个变量都以原变量或反变量形式出现一次，且仅个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次，则该出现一次，则该“或项被称为最大项。有时又将最大项称或项被称为最大项。有时又将最大项称为标准为标准“或项或项”。 2 最大项最大项CBACBACBA 数目：n个变量可以构成2n 个最大项。 例如，3个变量A、B、C可构成 、 、 共8个最大项。 性质：最大项具有如下四条性质。性

48、质：最大项具有如下四条性质。 性质1 任意一个最大项，其相应变量有且仅有一种取值使这个最大项的值为0。并且，最大项不同，使其值为0的变量取值不同。 简写：用Mi表示最大项。 下标i的取值规则是：将最大项中的原变量用0表示，反变量用1表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标 i 的值。例如，3变量A、B、C构成的最大项 可用 M5 表示。由于 M5 (5)10 101CBACBA 在n个变量构成的任意“或项中，最大项是使其值为1的变量取值组合数最多的一种“或项”，因而将其称为最大项。 性质2 相同变量构成的两个不同最大项相“或为1。因为任何一种变量取值都不可能使两个不同最大项

49、同时为0，故相“或为1。 即 M i + M j = 1 性质3 n个变量的全部最大项相“与为0。通常借用数学中的累乘符号“将其记为 010ii2nM 性质4 n个变量构成的最大项有n个相邻最大项。相邻最大项是指除一个变量互为相反外，其余变量均相同的最大项。 两变量最小项、最大项的真值表如下。m2 000101001000M3 M2 M 1 M 0 m 3 m1m 0 001011101101101101110 00 11 01 1A B最最 大大 项项 最最 小小 项项 变变 量量 2变量最小项、最大项真值表变量最小项、最大项真值表 BABABAABBABABABA真值表反映了最小项、最大项

50、的有关性质。 3最小项和最大项的关系最小项和最大项的关系 在同一问题中，下标相同的最小项和最大项互为反函数。或者说，相同变量构成的最小项mi和最大项Mi之间存在互补关系。即 或者iiMm iiMm 例如，由3变量A、B、C构成的最小项m3和最大项M3之间有 33MCBABCAm33mBCACBAM二、逻辑函数表达式的标准形式二、逻辑函数表达式的标准形式 逻辑函数表达式的标准形式有标准“与-或表达式和标准“或-与表达式两种类型。 1规范规范“与与 - 或表达式或表达式 由若干最小项相“或构成的逻辑表达式称为标准“与-或表达式，也叫做最小项表达式。 该函数表达式又可简写为 F(A，B，C) = m

51、1 + m2 + m4 + m7 = m(1,2,4,7) 例如，如下所示为一个3变量函数的标准“与-或表达式 ABCCBACBACBAC)B,F(A,2规范规范“或或-与表达式与表达式 由若干最大项相“与构成的逻辑表达式称为标准“或-与表达式，也叫做最大项表达式 。CBA 例如， 、 、 为3变量构成的3个最大项，对这3个最大项进行“与运算，即可得到一个3变量函数的标准“或-与表达式 CBACBA)CBA)(CBA)(CB(AC),B,F(A 该表达式又可简写为 M(1,5,7)MMMC)B,F(A,7512.3.3 2.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 将一个任意逻辑函数表

52、达式转换成标准表达式有两种常用方法，一种是代数转换法，另一种是真值表转换法。 一、代数转换法一、代数转换法 1 . 求标准求标准“与与-或或” 式式 一般步骤如下：一般步骤如下： 第一步：将函数表达式变换成一般第一步：将函数表达式变换成一般“与与-或表达式。或表达式。 所谓代数转换法，就是利用逻辑代数的公理、定理和规所谓代数转换法，就是利用逻辑代数的公理、定理和规则进行逻辑变换，将函数表达式从一种形式变换为另一种形则进行逻辑变换，将函数表达式从一种形式变换为另一种形式。式。 第二步：反复使用第二步：反复使用 将表达式中所有非最将表达式中所有非最 小项的小项的“与项扩展成最小项。与项扩展成最小项

53、。 )YX(YX 例如，将逻辑函数表达式例如，将逻辑函数表达式 转转换成标准换成标准“与与-或表达式。或表达式。 AB)CBB(AC)B,F(A, 第二步：把第二步：把“与与-或式中非最小项的或式中非最小项的“与项扩展成最与项扩展成最小项。具体地说，若某小项。具体地说，若某“与项缺少函数变量与项缺少函数变量Y，则用，则用( )和这一项相与，并把它拆开成两项。即和这一项相与，并把它拆开成两项。即 YY C)C( ABA)BCA(B)BC(AC)C(BAC)B,F(A,ABCC ABABCBCABCACBACBACBAABCCABBCACBACBA 解解 第一步：将函数表达式变换成第一步：将函数表

54、达式变换成“与与-或表达式。或表达式。即即ABCBBAABC)BB)(A(ABBCCABAAB)CBB(A C)B,F(A, 所得标准“与-或式的简写形式为 当给出函数表达式已经是“与-或表达式时，可直接进行第二步。 2 . 求一个函数的标准求一个函数的标准“或或-与与” 式式 一般步骤：一般步骤： 第一步：将函数表达式转换成一般第一步：将函数表达式转换成一般“或或-与表达式。与表达式。 第二步：反复利用定理第二步：反复利用定理 把表达式中把表达式中所有非最大项的所有非最大项的“或项扩展成最大项。或项扩展成最大项。 )BB)(A(AA76310mmmmmC)B,F(A,)(0,1,3,6,7m

55、 解 第一步：将函数表达式变换成“或-与表达式。即 例如，将逻辑函数表达式例如，将逻辑函数表达式 变变换成标准换成标准“或或-与表达式。与表达式。 CBC)A(ABC)B,F(A,CBC)A(ABC)B,F(A,CBCAABCB)C(AB)A(C)C)(ABA(B)C)(ABA(C)CC)(ABA)(BC)(ABBA(C)BA)(CB)(ABA(=1 第二步：将所得第二步：将所得“或或-与表达中的非最大项扩展成最大与表达中的非最大项扩展成最大项。即项。即 当给出函数已经是“或-与表达式时，可直接进行第二步。 该标准“或-与表达式的简写形式为 M(3,6,7)MMMC)B,F(A,763C)BA

56、)(CB)(ABA(C)B,F(A,C)BA)(CBC)(ABA)(CBA()CBAC)(BA)(CB(A二、真值表转换法二、真值表转换法 详细：真值表上使函数值为详细：真值表上使函数值为1的变量取值组合对应的最的变量取值组合对应的最小项相小项相“或或”,即可构成一个函数的标准即可构成一个函数的标准“与与-或式或式 。 逻辑函数的最小项表达式与真值表具有一一对应的关系。 假定函数F的真值表中有k组变量取值使F的值为1，其他变量取值下F的值为0，那么，函数F的最小项表达式由这k组变量取值对应的k个最小项相或组成。 因此，可以通过函数的真值表写出最小项表达式。 1 . 求标准求标准“与与-或或”

57、式式 解解: 首先，列出首先，列出F的真值表如下表所示，然后，根据真值的真值表如下表所示，然后，根据真值表可直接写出表可直接写出F的最小项表达式的最小项表达式 m(2,4,5,6)C)B,F(A,1 0 1 1 0 1 1 0 A B C F 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0 函数函数 的真值表的真值表 CBBAC)B,F(A,)6 , 5 , 4 , 2(),(mCBAF 例如，将函数表达式例如，将函数表达式 变换成标准变换成标准“与与-或表达式。或表达式。 CBBAC)B,F(A, 详细：真值表上使函数值为详细：真值表上使函数值

58、为0的变量取值组合对应的最的变量取值组合对应的最大项相大项相“与即可构成一个函数的标准与即可构成一个函数的标准“或或-与式与式 。 2 . 求一个函数的标准“或-与” 式 逻辑函数的最大项表达式与真值表之间同样具有一一对应的关系。 假定在函数F的真值表中有p组变量取值使F的值为0，其他变量取值下F的值为1，那么，函数F的最大项表达式由这p组变量取值对应的p个最大项“相与组成。 解：首先，列出解：首先，列出F的真值表如下表所示。然后，根据真的真值表如下表所示。然后，根据真值表直接写出值表直接写出F的最大项表达式的最大项表达式 )7 , 6 , 5 , 2 , 0(),(MCBAF) 7 , 6

59、, 5 , 2 , 0 (),(MCBAFCBACAC)B,F(A, 函数函数 的真值表的真值表 1 0 1 0 0 1 1 1 A B C F 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 例如，将函数表达式例如，将函数表达式 表示成最表示成最大项表达式的形式。大项表达式的形式。 CBACACBAF),( 由于函数的真值表与函数的两种标准表达式之间存在一一对应的关系，而任何个逻辑函数的真值表是唯一的，可见，任何一个逻辑函数的两种标准形式也是唯一的。 逻辑函数表达式的唯一性给我们分析和研究逻辑问题带来了很大的方便。 2.4 2.4 逻辑函数化简

60、逻辑函数化简 实现某一逻辑功能的逻辑电路的复杂性与描述该功能的逻辑表达式的复杂性直接相关。一般说，逻辑函数表达式越简单，设计出来的相应逻辑电路也就越简单。 为了降低系统成本、减小复杂度、提高可靠性，必须对逻辑函数进行化简。 由于“与-或表达式和“或-与表达式可以很方便地转换成任何其他所要求的形式。因此，从这两种基本形式出发讨论函数化简问题，并将重点放在“与-或表达式的化简上。 逻辑函数化简有3种常用方法。即：代数化简法、卡诺图化简法和列表化简法。 2.4.1 2.4.1 代数化简法代数化简法 代数化简法就是运用逻辑代数的公理、定理和规则对逻辑函数进行化简的方法。 这种方法没有固定的步骤可以遵循，主要取决于对