计算机组30补充逻辑代数

1、补充数字逻辑及集成电路补充数字逻辑及集成电路计算机组成原理计算机组成原理 主讲人：陈志勇主讲人：陈志勇 山东大学山东大学 计算机科学与技术学院计算机科学与技术学院作者：唐朔飞作者：唐朔飞高等教育出版社高等教育出版社计算机科学与技术学院计算机科学与技术学院2第一章第一章 逻辑代数逻辑代数l逻辑代数逻辑代数由英国数学家乔治由英国数学家乔治布尔奠定的，布尔奠定的，因此又称为因此又称为布尔代数布尔代数l布尔代数的布尔代数的二值性质二值性质应用于两态元件组应用于两态元件组成的数字电路成的数字电路( (开关电路开关电路) )尤为适合，自尤为适合，自从布尔代数用于开关数字电路之后，又从布尔代数用于开关数字电

2、路之后，又被称为被称为开关代数开关代数。l目前，逻辑代数已成为研究目前，逻辑代数已成为研究数字系统数字系统逻逻辑设计的基础理论。无论何种形式的数辑设计的基础理论。无论何种形式的数字系统，都是由一些基本的逻辑电路所字系统，都是由一些基本的逻辑电路所组成的。为了解决数字系统分析和设计组成的。为了解决数字系统分析和设计中的各种具体问题，必须掌握逻辑代数中的各种具体问题，必须掌握逻辑代数这一重要数学工具。这一重要数学工具。 George BooleGeorge Boole 1815181518641864年年 计算机科学与技术学院计算机科学与技术学院3主要内容主要内容1.1 1.1 基本逻辑基本逻辑1

3、.2 1.2 复合逻辑复合逻辑1.3 1.3 运算规则运算规则1.4 1.4 基本定理基本定理1.5 1.5 逻辑函数的表示法逻辑函数的表示法1.6 1.6 逻辑函数的标准形式逻辑函数的标准形式1.7 1.7 逻辑函数的化简（逻辑函数的化简（重点重点）计算机科学与技术学院计算机科学与技术学院4在数字电路中，我们要研究的是电路在数字电路中，我们要研究的是电路的输入输出之间的逻辑关系，所以数字电的输入输出之间的逻辑关系，所以数字电路又称路又称逻辑电路逻辑电路，相应的研究工具是，相应的研究工具是逻辑逻辑代数（布尔代数）代数（布尔代数）。在逻辑代数中，逻辑函数的变量只能在逻辑代数中，逻辑函数的变量只能

4、取两个值（取两个值（二值变量二值变量），即），即0和和1，中间值，中间值没有意义，这里的没有意义，这里的0和和1只表示两个对立的只表示两个对立的逻辑状态，如电位的高低（逻辑状态，如电位的高低（0表示低电位，表示低电位，1表示高电位）、脉冲的有无等。表示高电位）、脉冲的有无等。1.1 1.1 逻辑代数与基本逻辑关系逻辑代数与基本逻辑关系计算机科学与技术学院计算机科学与技术学院5逻辑代数和普通代数逻辑代数和普通代数l共同点共同点都有变量以及对变量的运算都有变量以及对变量的运算l逻辑代数逻辑代数用字母表示变量，取值只有用字母表示变量，取值只有0 0或或1 1基本运算：与、或、非基本运算：与、或、非计

5、算机科学与技术学院计算机科学与技术学院6（1）“与与”逻辑逻辑A、B条件都具备时，事件条件都具备时，事件F才发生。才发生。EFAB&ABF逻辑符号逻辑符号基本逻辑关系：基本逻辑关系：计算机科学与技术学院计算机科学与技术学院7F=AB 或或 F=AB逻辑式逻辑式逻辑乘法逻辑乘法逻辑与逻辑与真值表真值表AFB000100011110计算机科学与技术学院计算机科学与技术学院8（2）“或或”逻辑逻辑A、B只要一个条件具备时，事件只要一个条件具备时，事件F就发就发生。生。 1ABFAEFB逻辑符号逻辑符号计算机科学与技术学院计算机科学与技术学院9F=A+B 或或 F=AV VB逻辑式逻辑式逻辑加法逻辑加

6、法逻辑或逻辑或真值表真值表AFB000101011111特别注意特别注意: :在逻辑代数中在逻辑代数中1+1=11+1=1 读作读作“A A或或B B”计算机科学与技术学院计算机科学与技术学院10（3）“非非”逻辑逻辑A条件具备时条件具备时 ，事件，事件F不发生；不发生；A不具备不具备时，事件时，事件F发生。发生。逻辑符号逻辑符号AEFR计算机科学与技术学院计算机科学与技术学院11逻辑式逻辑式逻辑非逻辑非逻辑反逻辑反真值表真值表AF AF0110读作读作“A A非非”计算机科学与技术学院计算机科学与技术学院12主要内容主要内容1.1 1.1 基本逻辑基本逻辑1.2 1.2 复合逻辑复合逻辑1.

7、3 1.3 运算规则运算规则1.4 1.4 基本定理基本定理1.5 1.5 逻辑函数的表示法逻辑函数的表示法1.6 1.6 逻辑函数的标准形式逻辑函数的标准形式1.7 1.7 逻辑函数的化简逻辑函数的化简计算机科学与技术学院计算机科学与技术学院131.2 1.2 几种常用的复合逻辑关系几种常用的复合逻辑关系“与与”、“或或”、“非非”是三种基本的是三种基本的逻辑关系，任何其它的逻辑关系都可以逻辑关系，任何其它的逻辑关系都可以以它们为基础表示。以它们为基础表示。CBAF与非：与非：条件条件A、B、C都具都具备，则备，则F 不发不发生。生。&ABCF计算机科学与技术学院计算机科学与技术学院14CB

8、AF或非：或非：条件条件A、B、C任一任一具备，则具备，则F不不 发生。发生。 1ABCF与或非与或非F3=AB+CD计算机科学与技术学院计算机科学与技术学院15异或运算异或运算ABF1 01 10 10 01100逻辑表达式逻辑表达式F=AF=A B=AB+ABB=AB+AB ABF=1逻辑符号逻辑符号ABF1 01 10 10 00011同或运算同或运算逻辑表达式逻辑表达式F=A F=A B= B= A A B B 逻辑符号逻辑符号ABF=1“ ”异或逻辑异或逻辑运算符运算符“”同或逻辑同或逻辑运算符运算符计算机科学与技术学院计算机科学与技术学院16主要内容主要内容l1.1 1.1 基本逻

9、辑基本逻辑l1.2 1.2 复合逻辑复合逻辑l1.3 1.3 运算规则运算规则l1.4 1.4 基本定理基本定理l1.5 1.5 逻辑函数的表示法逻辑函数的表示法l1.6 1.6 逻辑函数的标准形式逻辑函数的标准形式l1.7 1.7 逻辑函数的化简逻辑函数的化简计算机科学与技术学院计算机科学与技术学院17 从三种基本的逻辑关系出发，我们可从三种基本的逻辑关系出发，我们可以得到以下逻辑运算结果：以得到以下逻辑运算结果：0 0=0 1=1 0=01 1=10+0=00+1=1+0=1+1=11001 1.3 1.3 运算规则和基本定律运算规则和基本定律1.3.1 基本运算规则基本运算规则与运算与运

10、算或运算或运算非运算非运算计算机科学与技术学院计算机科学与技术学院18A+0=A A+1=1 A 0 =0 A=0 A 1=AAAA0 AAAAA AA1 AA（补运算）（补运算）说明说明：0 0代表空集，代表空集，1 1代表全集代表全集计算机科学与技术学院计算机科学与技术学院191.3.2 1.3.2 基本代数规律基本代数规律交换律交换律结合律结合律分配律分配律A+B=B+AA B=B AA+(B+C)=(A+B)+C=(A+C)+BA (B C)=(A B) CA(B+C)=A B+A CA+(B C)=(A+B)(A+C)普通代普通代数不适数不适用用!布尔运算符优先级：括号、非、与、异或

11、布尔运算符优先级：括号、非、与、异或/ /同或、或同或、或计算机科学与技术学院计算机科学与技术学院201.3.3 1.3.3 吸收规律吸收规律1.原变量的吸收：原变量的吸收：A+AB=A证明：证明：A+AB=A(1+B)=A1=A利用运算规则可以对逻辑式进行化简。利用运算规则可以对逻辑式进行化简。例如：例如：CDABFEDABCDAB)(被吸收被吸收计算机科学与技术学院计算机科学与技术学院212.反变量的吸收：反变量的吸收：BABAA证明：证明：BAABABAABAAABA)(例如：例如：DCBCADCBCAA 被吸收被吸收计算机科学与技术学院计算机科学与技术学院223.混合变量的吸收：混合变

12、量的吸收：CAABBCCAAB证明：证明：BCAACAABBCCAAB)(CAABBCAABCCAAB例如：例如：CAABBCDAABCDCAABBCDAACAABBCDCAAB)(1吸收吸收利用了互补利用了互补率和重叠率率和重叠率计算机科学与技术学院计算机科学与技术学院234. 反演律（摩根定律）：反演律（摩根定律）：BABABABABAABBA可以用列真值表的方法证明：可以用列真值表的方法证明：计算机科学与技术学院计算机科学与技术学院24主要内容主要内容1.1 1.1 基本逻辑基本逻辑1.2 1.2 复合逻辑复合逻辑1.3 1.3 运算规则运算规则1.4 1.4 基本定理基本定理1.5 1

13、.5 逻辑函数的表示法逻辑函数的表示法1.6 1.6 逻辑函数的标准形式逻辑函数的标准形式1.7 1.7 逻辑函数的化简逻辑函数的化简计算机科学与技术学院计算机科学与技术学院25在任何一个包含变量在任何一个包含变量A A的逻辑等式中，若以另外一个逻辑的逻辑等式中，若以另外一个逻辑式代入式中所有式代入式中所有A A的位置，则等式仍然成立。的位置，则等式仍然成立。1.4 1.4 逻辑代数基本定理逻辑代数基本定理例如：例如：BABADCBADCBA则则由此反演律能推广到由此反演律能推广到n n个变量：个变量：n 21n 21n 21n 21AAAAAAAAAA A A 1 1、代入定理、代入定理计算

14、机科学与技术学院计算机科学与技术学院26例如：例如： 2 2、对偶定理、对偶定理 若两逻辑式相等，则它们的对偶式也相等。若两逻辑式相等，则它们的对偶式也相等。定义定义：对于任意一个逻辑式：对于任意一个逻辑式Y Y，若将其中的，若将其中的“ ”换成换成“+ +”， “+ +”换成换成“ ”， “1 1”换成换成“0 0”， “0 0”换成换成“1 1”，则得到的结果就是，则得到的结果就是Y Y的对偶式的对偶式Y YA(B+C)=A B+A CA+(B C)=(A+B)(A+C)基本定理基本定理计算机科学与技术学院计算机科学与技术学院27基本定理基本定理 求对偶式时求对偶式时运算顺序不变运算顺序不

15、变，且它只，且它只变变换运算符和常量换运算符和常量，其，其变量是不变变量是不变的。的。注意：注意： 函数式中有函数式中有“ ”和和“”运算符，求运算符，求反函数及对偶函数时，要将运算符反函数及对偶函数时，要将运算符“ ”换成换成“”， “”换成换成“ ”。 B1CAABF 其对偶式其对偶式)B 0() CA ()BA(F例：例：计算机科学与技术学院计算机科学与技术学院28对于任意一个逻辑式对于任意一个逻辑式Y Y，若将其中的，若将其中的“ ”换换成成“+ +”， “+ +”换成换成“ ”，原变量换成反原变量换成反变量变量，反变量换成原变量反变量换成原变量，“1 1”换成换成“0 0”， “0

16、0”换成换成“1 1”，则得到的结果就是其，则得到的结果就是其反函反函数式数式例如：例如：YCDCBAY)()(DCCBAY 3 3、反演定理、反演定理计算机科学与技术学院计算机科学与技术学院29基本定理基本定理注：注： 保持原函数的运算次序保持原函数的运算次序-先与后或先与后或，必要时，必要时适当地加入括号。适当地加入括号。 不属于单个变量上的非号要保留不属于单个变量上的非号要保留。F(AF(A，B B，C)C)CBAB )C A(BA )CBA(BCA)BA(F)CBA(B)CA()BA(F例如：例如：或者：或者：计算机科学与技术学院计算机科学与技术学院30小结小结1.1 1.1 基本逻辑

17、基本逻辑 与与: :A A B B 或或: :A A+ +B B 非非: :1.2 1.2 复合逻辑复合逻辑 1.3 1.3 运算规则运算规则 1 1 1=1 0+1=1+0=1+1=11=1 0+1=1+0=1+1=1 交换律交换律 结合律结合律 分配律分配律 吸收规律吸收规律 反演规律反演规律1.4 1.4 基本定理基本定理 代入定理代入定理 对偶定理对偶定理 反演定理反演定理AF CBAFCBAFF3=AB+CDF=AF=A B BF=AF=AB B计算机科学与技术学院计算机科学与技术学院31主要内容主要内容1.1 1.1 基本逻辑基本逻辑1.2 1.2 复合逻辑复合逻辑1.3 1.3

18、运算规则运算规则1.4 1.4 基本定理基本定理1.5 1.5 逻辑函数的表示法逻辑函数的表示法1.6 1.6 逻辑函数的标准形式逻辑函数的标准形式1.7 1.7 逻辑函数的化简逻辑函数的化简计算机科学与技术学院计算机科学与技术学院32四种四种表示方法表示方法Y=AB + ABY=AB + AB逻辑代数式逻辑代数式( (逻辑表示式逻辑表示式, , 逻辑函数式逻辑函数式) )1 11 1& & &1 1A AB BY Y 逻辑电路图逻辑电路图: :卡诺图卡诺图 将逻辑函数输入变量取值的将逻辑函数输入变量取值的所有组合所有组合与与所对应的输出变量值用列表的方式所对应的输出变量值用列表的方式一一对应

19、一一对应列出列出的表格。的表格。n2n n个输入变量个输入变量 种组合种组合。真值表：真值表： 1.5 1.5 逻辑函数的表示法逻辑函数的表示法计算机科学与技术学院计算机科学与技术学院33真值表真值表：将输入、输出的所有可能：将输入、输出的所有可能 状态一一状态一一对应地列出。对应地列出。ABCF01000110000000101000101111011111设设A、B、C为输入变量，为输入变量，F为输出变量。为输出变量。计算机科学与技术学院计算机科学与技术学院34真值表真值表 A B Y 0 0 1 0 1 1 1 0 1 1 1 0A B C Y0 0 0 0 0 0 1 00 1 0 0

20、0 1 1 01 0 0 01 0 1 11 1 0 11 1 1 10 10 11 01 0A YA Y一输入变一输入变量，二种量，二种组合组合二输入变二输入变量，四种量，四种组合组合三输入变三输入变量，八种量，八种组合组合计算机科学与技术学院计算机科学与技术学院35 n个变量可以有个变量可以有2n个组合，个组合，一般按二进制的顺序，输出与一般按二进制的顺序，输出与输入状态一一对应，列出所有输入状态一一对应，列出所有可能的状态。可能的状态。计算机科学与技术学院计算机科学与技术学院36作业（课下练习）作业（课下练习）l1.1.写出下列函数的反函数写出下列函数的反函数: :l2.2.写出下列函数

21、的对偶函数写出下列函数的对偶函数: :l3.3.利用公式法证明下列各式利用公式法证明下列各式: :()FABABD BCDFA AB B AB()()ABABAB ABABBDADDCABD计算机科学与技术学院计算机科学与技术学院37主要内容主要内容1.1 1.1 基本逻辑基本逻辑1.2 1.2 复合逻辑复合逻辑1.3 1.3 运算规则运算规则1.4 1.4 基本定理基本定理1.5 1.5 逻辑函数的表示法逻辑函数的表示法1.6 1.6 逻辑函数的标准形式逻辑函数的标准形式1.7 1.7 逻辑函数的化简逻辑函数的化简计算机科学与技术学院计算机科学与技术学院381.6 1.6 逻辑函数的标准形式

22、逻辑函数的标准形式计算机科学与技术学院计算机科学与技术学院39逻辑函数的标准形式逻辑函数的标准形式l对于一个任意的逻辑函数通常有对于一个任意的逻辑函数通常有“积之和积之和”与与“和和之积之积”两种基本表达形式，且其表达形式并不是唯两种基本表达形式，且其表达形式并不是唯一的。一的。 如如 是是“积之和积之和”的形式，又称的形式，又称“与或与或”表达式表达式； 而而 则是则是“和之积和之积”的形式，的形式，又称又称“或与或与”表达式表达式。l一个逻辑函数的标准形式却是唯一的一个逻辑函数的标准形式却是唯一的，逻辑函数标，逻辑函数标准形式的唯一性为用图表方法化简函数提供了方准形式的唯一性为用图表方法化

23、简函数提供了方便，并且建立了逻辑函数与真值表的对应关系。便，并且建立了逻辑函数与真值表的对应关系。CCBAABF)(CBBAF计算机科学与技术学院计算机科学与技术学院401.6.1 1.6.1 最小项及最小项及“与或与或”标准形式标准形式l逻辑函数的最小项逻辑函数的最小项 1 1） 最小项定义最小项定义 在一个具有在一个具有n n个个变量的逻辑函数中，如果一个变量的逻辑函数中，如果一个与与项包含了所有项包含了所有n n个的变量个的变量，而且每个变量都是以原变量，而且每个变量都是以原变量或反变量的形式或反变量的形式作为因子仅出现一次作为因子仅出现一次，那么这样的，那么这样的与与项项就称为该逻辑函

24、数的一个最小项。就称为该逻辑函数的一个最小项。 对于对于n n个变量的全部最小项共有个变量的全部最小项共有2 2n n个。个。例如：例如：n=2n=2ABBABABA（1-41） 例如，在三变量的逻辑函数例如，在三变量的逻辑函数F（A、B、C）中，中，它们组成的八个乘积项它们组成的八个乘积项即即 、 、 、 、 、 、 、 都符合最小项的定义。因此，我们把这都符合最小项的定义。因此，我们把这八个八个与项与项称为三变量逻辑函数称为三变量逻辑函数F（A、B、C）的最小项。的最小项。 除此之外除此之外 ，还有，还有 、 等与项，都不满等与项，都不满足最小项的定义，所以，都不是三变量逻辑函足最小项的定

25、义，所以，都不是三变量逻辑函数数F（A、B、C）的最小项。的最小项。CBACBACBABCACBACBACABABCABCA计算机科学与技术学院计算机科学与技术学院42l为了表达方便，人们通常用mi表示最小项，其下标i为最小项的编号。l编号的方法是：最小项中的原变量取1，反变量取0，则最小项取值为一组二进制数，其对应的十进制数便为该最小项的编号。 例如：三变量最小项 对应的变量取值为100，它对应的十进制数为4，因此，最小项 的编号为m4。其余最小项的编号以此类推。l值得注意的是，在规定n变量最小项的编号时，对变量的排列顺序是重要的。例如，把 记作m4。其中隐含了A是最高位，而C是最低位这一排

26、列顺序。CBACBACBA2 2）最小项编号）最小项编号计算机科学与技术学院计算机科学与技术学院43A AB BC CABCABC0 00 00 01 10 00 00 00 00 00 00 00 00 01 10 01 10 00 00 00 00 00 00 01 10 00 00 01 10 00 00 00 00 00 01 11 10 00 00 01 10 00 00 00 00 00 00 00 00 00 00 01 10 00 00 01 10 01 10 00 00 00 00 01 10 00 01 11 10 00 00 00 00 00 00 01 10 01 11

27、 11 10 00 00 00 00 00 00 01 1最小项编号最小项编号m m0 0m m1 1m m2 2m m3 3m m4 4m m5 5m m6 6m m7 7CBACBABCACBACBACABCBA3 3）最小项的性质）最小项的性质 （1 1）对于任意一个最小项，有且仅有一组变量取值使其值为对于任意一个最小项，有且仅有一组变量取值使其值为1 1，而其余，而其余各种变量取值均使它的值为各种变量取值均使它的值为0 0。 （2 2）不同最小项，使其值为不同最小项，使其值为1 1的变量取值也不相同。的变量取值也不相同。 （3 3）对于变量的任意一组取值，任意两个不同最小项的乘积均为对

28、于变量的任意一组取值，任意两个不同最小项的乘积均为0 0。 （4 4）对于变量的任意一组取值，全体最小项的和恒为对于变量的任意一组取值，全体最小项的和恒为1 1 。计算机科学与技术学院计算机科学与技术学院44由最小项的逻辑或的形式所构成的逻辑函数表达式称之为由最小项的逻辑或的形式所构成的逻辑函数表达式称之为逻辑函数的逻辑函数的最小项之和的标准形式最小项之和的标准形式。如：。如： BCACBACABCBAF),(=m6+m4+m3又记为：又记为：)6 , 4 , 3(m)C,B,A(F这是一个三变量逻辑函数，其变量按这是一个三变量逻辑函数，其变量按（A，B，C）排列，函数本身由排列，函数本身由3

29、个最小项构成。上述表达式即个最小项构成。上述表达式即为逻辑函数的最小项之和的标准形式。为逻辑函数的最小项之和的标准形式。 4 4）最小项之和的标准形式）最小项之和的标准形式计算机科学与技术学院计算机科学与技术学院451.6.2 1.6.2 最大项及最大项及“或与或与”标准形式标准形式 1 1）最大项定义）最大项定义 在一个具有在一个具有n n变量的逻辑函数中，如果变量的逻辑函数中，如果一个或项包一个或项包含了所有含了所有n n个的变量个的变量，而且每个变量都是以原变量或反，而且每个变量都是以原变量或反变量的形式作为一个因子变量的形式作为一个因子仅出现一次仅出现一次，那么这样的或，那么这样的或项

30、就称为该逻辑函数的一个项就称为该逻辑函数的一个最大项最大项。对于。对于n n个变量的全个变量的全部最大项共有部最大项共有2 2n n个。个。 说明：说明： 任何一个逻辑函数除可以用最小项之和来表示任何一个逻辑函数除可以用最小项之和来表示外，也可用最大项之积来表示，其逻辑表达式采用外，也可用最大项之积来表示，其逻辑表达式采用“先或后与先或后与”的形式。由于和目前大量应用的可编程逻的形式。由于和目前大量应用的可编程逻辑器件不相适应，因此，应用较少。辑器件不相适应，因此，应用较少。 关于最大项及其标准形式，简单介绍，感兴趣的关于最大项及其标准形式，简单介绍，感兴趣的同学可自学。不做硬性要求。同学可自

31、学。不做硬性要求。计算机科学与技术学院计算机科学与技术学院46例如，在三变量的逻辑函数例如，在三变量的逻辑函数F（A、B、C）中，它们组成中，它们组成的八个和项即的八个和项即 CBACBACBACBACBACBACBACBA都符合最大项的定义。因此，我们把这八个都符合最大项的定义。因此，我们把这八个或项称为三变量逻辑函数或项称为三变量逻辑函数F（A、B、C）的的最大项最大项。除此之外，还有除此之外，还有 、 等或项，都不等或项，都不满足最大项的定义，所以，都不是三变量逻辑满足最大项的定义，所以，都不是三变量逻辑函数函数F F（A A、B B、C C）的的最大项。最大项。 BACA1.6.2 1

32、.6.2 最大项及或与标准形式最大项及或与标准形式计算机科学与技术学院计算机科学与技术学院47 逻辑函数的逻辑函数的最大项最大项具有下列具有下列性质性质： （1 1）对于任意一个最大项，有且仅有一组变量取值使其对于任意一个最大项，有且仅有一组变量取值使其值为值为0 0，而其余各种变量取值均使它的值为，而其余各种变量取值均使它的值为1 1。 （2 2）不同最大项，使其值为不同最大项，使其值为0 0的变量取值也不相同。的变量取值也不相同。 （3 3）对于变量的任意一组取值，任意两个不同最大项的对于变量的任意一组取值，任意两个不同最大项的和均为和均为1 1。 （4 4）对于变量的任意一组取值，全体最

33、大项的积恒为对于变量的任意一组取值，全体最大项的积恒为0 0。 2 2）最大项的性质）最大项的性质计算机科学与技术学院计算机科学与技术学院48l 最大项编号用最大项编号用M Mi i表示最大项，其下标表示最大项，其下标i i为最大项的为最大项的编号。编号。编号的方法是编号的方法是：最大项中的：最大项中的原变量取原变量取0 0，反变量，反变量取取1 1，则最大项取值为一组二进制数，其对应的十进制，则最大项取值为一组二进制数，其对应的十进制数便为该最大项的编号。数便为该最大项的编号。 如如 三变量最大项对应的变量取值为三变量最大项对应的变量取值为011011，它对应的十进制数为，它对应的十进制数为

34、3 3， 因此，因此， 最大项的编号为最大项的编号为M M3 3。其余最大项。其余最大项的编号以此类推的编号以此类推 CBACBA3 3）最大项编号）最大项编号计算机科学与技术学院计算机科学与技术学院49由最大项的由最大项的逻辑与的形式逻辑与的形式所构成的逻辑函数表达式称之所构成的逻辑函数表达式称之为逻辑函数的最大项之积的标准形式。如：为逻辑函数的最大项之积的标准形式。如：)()(),(CBACBACBACBAF=M1M3M4又记为：又记为：) 4 , 3 , 1 (),(MCBAF是一个三变量逻辑函数，其变量按是一个三变量逻辑函数，其变量按（A，B，C）排列，函数本身由排列，函数本身由3个最

35、大项构成。上述表达式个最大项构成。上述表达式即为逻辑函数的即为逻辑函数的最大项之积的标准形式最大项之积的标准形式。4 4）最大项之积的标准形式）最大项之积的标准形式计算机科学与技术学院计算机科学与技术学院501.6.3 1.6.3 将逻辑函数展开为两种标准形式的方法将逻辑函数展开为两种标准形式的方法(1) (1) 利用公式利用公式1 XX与与0 XX将函数将函数展开为两种标准形式展开为两种标准形式我们通过求解下面的例题来学习该方法的我们通过求解下面的例题来学习该方法的具体应用。具体应用。 将函数将函数)(),(CABACBAF展开为两种标准形式。展开为两种标准形式。计算机科学与技术学院计算机科

36、学与技术学院51l解：解：（1 1）求最小项之和的标准形式）求最小项之和的标准形式)(),(CABACBAF)(CABABCABCAABCA 将函数式变换为一般的将函数式变换为一般的“与与或或”表达式表达式 )()(CCABCBBA 运用公式运用公式1 XX变换为变换为最小项之和的形式最小项之和的形式CABABCCBABCA =m1+m3+m6+m7 =)7 , 6 , 3 , 1 (m6 67 71 13 3计算机科学与技术学院计算机科学与技术学院52（2 2）求最大项之积的标准形式）求最大项之积的标准形式)(),(CABACBAF)(CABA)(CBBACCBA)()()(CBACBACB

37、ACBA)5 , 4 , 2 , 0(M0 XX= 将函数式变换为将函数式变换为 一般一般 “或或与与”表达表达式式=M0M2M4M5公式公式 变换为最大项之积的形式变换为最大项之积的形式分配律分配律CCXCCCXXCXCXCX)(计算机科学与技术学院计算机科学与技术学院53l同样，我们通过例题来学习该方法的具体步骤。同样，我们通过例题来学习该方法的具体步骤。 将函数将函数 展开为两种标准形式。展开为两种标准形式。解：解：（1 1）求最小项之和的标准形式）求最小项之和的标准形式作函数的真值表，如作函数的真值表，如所示。所示。BCACBCACBAF),(2) (2) 利用真值表展开为两种标准形式

38、利用真值表展开为两种标准形式计算机科学与技术学院计算机科学与技术学院54表表 1.11 1.11 函数函数F F的真值表的真值表A B CA B CF FA B CA B CF F0 0 00 0 01 11 0 01 0 01 10 0 10 0 10 01 0 11 0 10 00 1 00 1 00 01 1 01 1 01 10 1 10 1 11 11 1 11 1 10 0BCACBCACBAF),(=m0+m3+m4+m6)6 , 4 , 3 , 0(m由表可知由表可知：BCACBCACBAF),(计算机科学与技术学院计算机科学与技术学院55l（2 2）求最大项之积的标准形式）求

39、最大项之积的标准形式因为因为iimM ，iiMm l即：即：n变量的变量的同一编号同一编号的最小项与最大项互为的最小项与最大项互为反函数反函数（可自行证明）。（可自行证明）。l又因为：又因为：ABCCBACBACBACBAF),(由真值表可得由真值表可得)=m1+m2+m5+m7所以所以7521),(),(mmmmCBAFCBAF)7 , 5 , 2, 1 (M=M1M2M5M7很明显，很明显，每个最大项对应真值表为每个最大项对应真值表为0的某项的某项。计算机科学与技术学院计算机科学与技术学院56l结论：结论： （1 1）利用真值表求最小项之和标准形式的方法：观利用真值表求最小项之和标准形式的

40、方法：观察真值表，察真值表，找出函数找出函数F F为为1 1的各项的各项，作函数对应这些项，作函数对应这些项的最小项，对于输入变量为的最小项，对于输入变量为1 1，则取输入变量本身，若，则取输入变量本身，若输入变量为输入变量为0 0，则取其反变量，再取这些最小项之和，则取其反变量，再取这些最小项之和，即为所求函数的最小项之和标准形式。即为所求函数的最小项之和标准形式。 （2 2）利用真值表求最大项之积标准形式的方法：观利用真值表求最大项之积标准形式的方法：观察真值表，察真值表，找出函数找出函数F F为为0 0的各项的各项，作函数对应这些项，作函数对应这些项的最大项，对于输入变量为的最大项，对于

41、输入变量为0 0，则取输入变量本身，若，则取输入变量本身，若输入变量为输入变量为1 1，则取其反变量，再取这些最大项之积，则取其反变量，再取这些最大项之积，即为所求函数的最大项之积标准形式。即为所求函数的最大项之积标准形式。计算机科学与技术学院计算机科学与技术学院57主要内容主要内容1.1 1.1 基本逻辑基本逻辑1.2 1.2 复合逻辑复合逻辑1.3 1.3 运算规则运算规则1.4 1.4 基本定理基本定理1.5 1.5 逻辑函数的表示法逻辑函数的表示法1.6 1.6 逻辑函数的标准形式逻辑函数的标准形式1.7 1.7 逻辑函数的化简逻辑函数的化简计算机科学与技术学院计算机科学与技术学院58

42、 1.7 1.7 逻辑函数的化简逻辑函数的化简l先看一个例子，化简如下表达式：先看一个例子，化简如下表达式：AB+A(B+C)+B(B+C)AB+A(B+C)+B(B+C) =AB+AB+AC+BB+BC=AB+AB+AC+BB+BC=AB+AC+B+BC =B(A+1+C)+AC =AB+AC+B+BC =B(A+1+C)+AC =B+ACB+AC化简前电路结构化简前电路结构化简后电路结构化简后电路结构计算机科学与技术学院计算机科学与技术学院59函数的化简依据函数的化简依据 逻辑电路所用门的数量少逻辑电路所用门的数量少 每个门的输入端个数少每个门的输入端个数少 逻辑电路构成级数少逻辑电路构成

43、级数少 逻辑电路可靠性提高逻辑电路可靠性提高降低成本降低成本提高电路的工作提高电路的工作速度和可靠性速度和可靠性 1.7 1.7 逻辑函数的化简逻辑函数的化简计算机科学与技术学院计算机科学与技术学院60逻辑函数的化简逻辑函数的化简l逻辑函数的化简逻辑函数的化简就是要将从实际问题中得到的就是要将从实际问题中得到的复杂逻辑函数式变换成复杂逻辑函数式变换成与之等效的与之等效的最简单的逻最简单的逻辑表达式辑表达式, ,使之更趋于合理使之更趋于合理. .常用的方法有常用的方法有代数代数化简法化简法和和卡诺图法卡诺图法。计算机科学与技术学院计算机科学与技术学院61最简式的标准最简式的标准 首先是式中首先是

44、式中乘积项最少乘积项最少 乘积项中含的变量少乘积项中含的变量少 与或表达式的简化与或表达式的简化代数法化简函数代数法化简函数与门的输入端个数少与门的输入端个数少 实现电路的与门少实现电路的与门少 下级或门输入端个数少下级或门输入端个数少方法：方法： 并项：利用并项：利用ABAAB将两项并为一项，将两项并为一项，且消去一个变量且消去一个变量B B。 消项：消项： 利用利用A + AB = AA + AB = A消去多余的项消去多余的项ABAB。 配项：利用配项：利用CAABBCCAAB即利用互补律、即利用互补律、重叠律先增添项，再消去多余项重叠律先增添项，再消去多余项BCBC。 消元：利用消元：

45、利用BABAA 消去多余变量消去多余变量A A。计算机科学与技术学院计算机科学与技术学院62例：例：ABACBCABCBAABCBACCABCBAABCCABCBAF)()()(反变量吸收反变量吸收提出提出AB=1提出提出A代数法化简函数代数法化简函数计算机科学与技术学院计算机科学与技术学院63 结论：结论：用布尔代数法化简应使得逻辑用布尔代数法化简应使得逻辑函数式包含的项数以及变量数最少为原则函数式包含的项数以及变量数最少为原则；对于化简的结果，尤其较为复杂的结果，对于化简的结果，尤其较为复杂的结果，通常通常难于判断是否最简难于判断是否最简，因此我们还常常，因此我们还常常使用使用卡诺图卡诺图

46、的方法来化简逻辑函数。稍后的方法来化简逻辑函数。稍后介绍的介绍的卡诺图法可以较简便地得到最简化卡诺图法可以较简便地得到最简化逻辑表达式逻辑表达式。代数法化简函数代数法化简函数计算机科学与技术学院计算机科学与技术学院641.7.2 逻辑函数的卡诺图化简逻辑函数的卡诺图化简卡诺图的构建（卡诺图的构建（美国工程师美国工程师Karnaugh提出）提出）将将n个输入变量的个输入变量的全部最小项全部最小项用小方块阵用小方块阵列图表示，并且将列图表示，并且将逻辑相临逻辑相临 的最小项放在相的最小项放在相邻的几何位置上，所得到的阵列图就是邻的几何位置上，所得到的阵列图就是n变变量的量的卡诺图卡诺图。 卡诺图的

47、每一个方块（卡诺图的每一个方块（最小项最小项）代表一）代表一种输入组合，并且把对应的输入组合注明在种输入组合，并且把对应的输入组合注明在阵列图的上方和左方。阵列图的上方和左方。计算机科学与技术学院计算机科学与技术学院65最小项最小项: : 输入变量的每一种组合。输入变量的每一种组合。 1 1、卡诺图的画法：、卡诺图的画法：（二输入变量）（二输入变量） A B Y 0 0 1 0 1 1 1 0 1 1 1 0AB01010111输出变量输出变量Y Y的值的值输入变量输入变量1.7.2 逻辑函数的卡诺图化简逻辑函数的卡诺图化简计算机科学与技术学院计算机科学与技术学院66卡诺图的画法卡诺图的画法（

48、三输入变量）（三输入变量）逻辑相邻逻辑相邻：相邻单：相邻单元输入变量的取值元输入变量的取值只能有一位不同。只能有一位不同。0 01 10000010111111010 A ABCBC0 00 00 00 00 01 11 11 1输入变量输入变量输出变量输出变量Y Y的值的值A B C Y0 0 0 0 0 0 1 00 1 0 00 1 1 01 0 0 01 0 1 11 1 0 11 1 1 1计算机科学与技术学院计算机科学与技术学院67只有一只有一位不同位不同四输入变量卡诺图四输入变量卡诺图逻辑相邻逻辑相邻有时为了方便，用二进制对应的十进制表示单有时为了方便，用二进制对应的十进制表示单

49、元格的编号。单元格的值用函数式表示。元格的编号。单元格的值用函数式表示。F( A , B , C )= m( 1 , 2 , 4 , 7 )ABC00011110010 1 3 2 4 5 7 7 6 A B C 十进制数十进制数0 0 0 0 0 0 1 10 1 0 20 1 1 31 0 0 41 0 1 51 1 0 61 1 1 7ABC00011110010 1 0 1 10 1 1 0 ABCD0001111000011110四变量卡诺图单四变量卡诺图单元格的编号元格的编号 A B C D 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1

50、 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 A B C D 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1 F(A,B,C,D)= m(0,2,3,5,6,8,9,10,11, 12,13,14,15)AB0 10101112 2、真值表、真值表卡诺图卡诺图 A B Y 0 0 1 0 1 1 1 0 1 1 1 0二变量卡诺图二变量卡诺图四种表示方式的相互转换四种表示方式的相互转换真值表真值表3 3、真值表、卡诺图、真值表、卡诺图逻辑代数式逻辑

51、代数式方法方法: :将真值表或卡诺图中为将真值表或卡诺图中为1 1的项相加的项相加, ,写成写成 “与或式与或式”。Y=AB+AB+AB 真值表真值表 A B Y 0 0 1 0 1 1 1 0 1 1 1 0AB0 1010111AB几种表示方式的相互转换几种表示方式的相互转换此逻辑代数式并非是最简单的形式，实际上此真此逻辑代数式并非是最简单的形式，实际上此真值表是值表是与非门与非门的真值表，其逻辑代数式为的真值表，其逻辑代数式为Y=AB因此，有一个化简问题。因此，有一个化简问题。ABAB计算机科学与技术学院计算机科学与技术学院72ABC00011110010010001 11ABCBCAB

52、CBCAABC卡诺图卡诺图化简函数化简函数ABCCBACBACBACBAF逻辑相邻逻辑相邻CBCBACBA逻辑相邻的项可以逻辑相邻的项可以合并，消去一个因子合并，消去一个因子若两个最小项中只有一个变量以原、反状若两个最小项中只有一个变量以原、反状态相区别，则称它们为态相区别，则称它们为逻辑相邻逻辑相邻。 计算机科学与技术学院计算机科学与技术学院74ABC00011110010010001 11AB?计算机科学与技术学院计算机科学与技术学院75ABC00011110010010001 11ABBCF=AB+BC化简过程：化简过程：计算机科学与技术学院计算机科学与技术学院76利用卡诺图利用卡诺图化

53、简的规则化简的规则：（1）相邻单元的个数是）相邻单元的个数是2N个，并组成矩形个，并组成矩形时，可以合并。时，可以合并。ABCD0001 11 1000010000001 1001 11 10111 101110AD规律规律1：相邻相邻单元的个数单元的个数是是2N个，个，N=?就能消掉？就能消掉？个因子；个因子；规律规律2：消掉消掉的因子是的因子是以以原、反状态原、反状态相区别的变相区别的变量量计算机科学与技术学院计算机科学与技术学院77ABCD0001 11 1000010000010 0011 10 00100 001110不是矩形不是矩形利用卡诺图利用卡诺图化简的规则化简的规则：计算机科

54、学与技术学院计算机科学与技术学院78（2）先找）先找面积尽量大面积尽量大的组合进行化简，可以的组合进行化简，可以 减少更多的因子。减少更多的因子。（3）各最小项可以）各最小项可以重复使用重复使用。（4）注意）注意利用无关状态利用无关状态，可以使结果大大，可以使结果大大 简化。简化。（5）所有的）所有的1都被圈过后，化简结束。都被圈过后，化简结束。（6）化简后的逻辑式是）化简后的逻辑式是各化简项的逻辑和各化简项的逻辑和。利用卡诺图利用卡诺图化简的规则化简的规则：例：化简例：化简 F(A,B,C,D)= m(0,2,3,5,6,8,9,10,11, 12,13,14,15)ABCD0001 11

55、1000011110ADCCBDBDCBDCBDBCBDCAF计算机科学与技术学院计算机科学与技术学院80如何最简：如何最简： 圈的数目越少越简；圈内的最小项越多越简。圈的数目越少越简；圈内的最小项越多越简。特别注意：卡诺图中所有的特别注意：卡诺图中所有的 1 都必须圈到，都必须圈到， 不能合并的不能合并的 1 必须单独画必须单独画 圈。圈。YABC010001111011111001 1 1 上两式的内容不相同，但函数值一定相同。上两式的内容不相同，但函数值一定相同。YABC010001111011111001 1 1 Y1 =B+ABC+ACY1 =C+A+ BCAB将将Y1=AC+AC+BC+BC 化简为最简与或式。化简为最简与或式。此例说明，一逻辑函数的化简结果可能不唯一。此例说明，一逻辑函数的化简结果可能不唯一。例：例：利用卡诺图进行化简：利用卡诺图进行化简：Y2 = 例：将例：将Y2= (m0 m2 m4 m6