逻辑代数基础

第二章逻辑代数基础§2.1概述§2.2逻辑代数中的三种基本运算§2.3

逻辑代数的基本公式和常用公式§2.5逻辑函数及其表示方法§2.4逻辑代数的基本定理§2.6逻辑函数的化简方法§2.7具有无关项的逻辑函数及其化简1内容提要

本章介绍分析数字电路逻辑功能的数学方法。首先介绍逻辑代数的基本公式、常用公式和重要定理；讲述逻辑函数及其表示方法；介绍如何应用上述公式、定理化简逻辑函数。2§2.1

概述在二值逻辑中，逻辑代数中的逻辑变量取值只有两个：1（逻辑壹）、0（逻辑零）。0和1表示两个对立的逻辑状态。3§2.2逻辑代数中的三种基本运算基本逻辑运算：与

(and)、或

(or)

、非(not)。一、“与”逻辑与逻辑：决定事件发生的各条件中，所有条件都具备，事件才会发生（成立）。规定:

开关合为逻辑“1”

开关断为逻辑“0”

灯亮为逻辑“1”

灯灭为逻辑“0”EYABC4&ABCY逻辑符号：AYBC00001000010011000010101001101111逻辑式：Y=A•B•C逻辑乘法（逻辑与）真值表EYABC真值表特点:有0则0,全1则1与逻辑运算规则：0•0=00•1=01•0=01•1=15二、“或”逻辑AEYBC或逻辑：决定事件发生的各条件中，有一个或一个以上的条件具备，事件就会发生（成立）。规定:

开关合为逻辑“1”

开关断为逻辑“0”

灯亮为逻辑“1”

灯灭为逻辑“0”6AYBC00001001010111010011101101111111真值表1ABCY逻辑符号：逻辑式：Y=A+B+C逻辑加法(逻辑或)AEYBC真值表特点：

有1则1,全0则0。或逻辑运算规则:0+0=00+1=11+0=11+1=17三、“非”逻辑“非”逻辑：决定事件发生的条件只有一个，条件不具备时事件发生（成立），条件具备时事件不发生。规定:

开关合为逻辑“1”

开关断为逻辑“0”

灯亮为逻辑“1”

灯灭为逻辑“0”AEYR8逻辑符号：逻辑非(逻辑反)AY0110真值表AEYR真值表特点:

1则0,0则1。逻辑式：运算规则：AY19四、几种常用的复合逻辑运算“与”、“或”、“非”是三种基本的逻辑运算，任何其它的复杂逻辑运算都可以用与、或、非的组合来实现。与非：条件A、B、C都具备，则Y不发生。&ABCY其他几种常用的逻辑运算如下表：10或非：条件A、B、C任一具备，则Y不发生。1ABCY异或：条件A、B有一个具备，另一个不具备则Y发生。=1ABCY同或：条件A、B相同，则Y发生。=ABCY11图2.2.3复合逻辑的图形符号和运算符号12AYBC00011001010111010011101101111110与非逻辑真值表AYBC00011000010011000010101001101110或非逻辑真值表异或逻辑真值表ABY000110101011同或逻辑真值表ABY10001000111113§2.3逻辑代数的基本公式和常用公式2.3.1基本公式加运算规则:0+0=0，0+1=1，1+0=1，1+1=1乘运算规则:0•0=00•1=01•0=01•1=1非运算规则:一、基本定律14二、交换律三、结合律四、分配律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)普通代数不适用!15求证:

（分配律第2条）A+BC=(A+B)(A+C)证明:右边=(A+B)(A+C)=AA+AB+AC+BC;分配律=A+A(B+C)+BC;结合律,AA=A=A(1+B+C)+BC;结合律=A•1+BC;1+B+C=1=A+BC;A•1=A=左边16五、德摩根定理(反演律）（DeMorgan)证明：真值表法、穷举法推广到多变量：说明：两个（或两个以上）变量的与非（或非）运算等于两个（或两个以上）变量的非或（非与）运算。17用真值表证明摩根定理成立A·B=A+BA+B=A·BAB00011011Y1=A·BY2=A+B11101110相等√18吸收：多余（冗余）项，多余（冗余）因子被取消、去掉

被消化了。1.原变量的吸收：

A+AB=A证明：左式=A(1+B)原式成立口诀：长中含短,留下短。长项短项

=A=右式1||2.3.2若干常用公式--几种形式的吸收律192.反变量的吸收：

A+AB=A+B证明：=右式口诀：长中含反,去掉反。原(反)变量反(原)变量添冗余项

1||203.混合变量的吸收：

证明：添冗余因子AB+AC+BC=AB+AC互为反变量=右式口诀：正负相对,余全完。（消冗余项）添加21证明：

4.A·A·B=A·BA·A·B=AA·A·B=A·(A+B)=A·BA·A·B=A·A·B=?

A·(A+B)=A

AAA·BA·B

√×××22§

2.4逻辑代数的基本定理2.4.1代入定理内容：在任何一个包含变量A的逻辑等式中，若以另外一个逻辑式代替式中所有的变量A，则等式仍然成立。例：用代入规则证明德摩根定理也适用于多变量的情况。二变量的德摩根定理为：23以（B·C）代入（1）式中B，以（B+C）代入（2）式中B，则得到：注：代入定理还可以扩展其他基本定律的应用范围！242.4.2反演定理内容：将函数式F中所有的++变量与常数均取反1.遵循先括号再乘法后加法的运算顺序。2.不是一个变量上的反号不动。规则:用处：实现互补运算（求反运算）。新表达式：显然：(反函数)25例1：与或式注意括号注意括号26例2：与或式反号不动反号不动272.4.3对偶定理将函数式F中所有的对偶式：++常量取反新表达式：对偶式对偶定理：当某个逻辑恒等式成立时，则其对偶式也成立。若则：28注：证明两个逻辑式相等时，也可以通过证明它们的对偶式相等来完成。29§2.5逻辑函数及其表示方法事物之间的逻辑关系可以通过描述逻辑输入变量和输出变量的变化关系来确定，这是一种函数关系，称为逻辑函数。记为：Y=F（A，B，C，···）例如与非门：Y=A·B就是一个两输入变量A和B，一个输出变量的逻辑函数。逻辑函数的输入和输出取值为0和1。任何一个逻辑因果关系都可以用一个逻辑函数来描述。2.5.1逻辑函数30四种表示方法逻辑函数式

(逻辑表示式,逻辑代数式)11&&≥1ABY逻辑图:波形图n个输入变量种组合。真值表：将逻辑函数输入变量取值的不同组合与所对应的输出变量值用列表的方式一一对应列出的表格。2.5.2逻辑函数的表示方法31逻辑问题：裁判电路问题抽象：输入变量A、B、C分别代表主裁和两个副裁，同意为1；输出变量Y代表运动员成绩，有效为1。问题描述如下：举重比赛中有A、B、C三个裁判，A为主裁，B、C为副裁，规定当主裁和至少一个副裁认定成绩有效时，则运动员成绩Y有效；否则无效。32列真值表的方法：一般按二进制的顺序，输出与输入状态一一对应，列出所有可能的状态。一、真值表33二、逻辑函数式由规定当主裁A和至少一个副裁B、C认定成绩有效时，则运动员成绩Y有效，可知：

Y=A·（B+C）对于较复杂的逻辑问题，往往很难直接写出逻辑函数式，可以通过真值表的帮助来获得逻辑函数式。34把相应的逻辑关系用逻辑符号和连线表示出来，就构成了逻辑图。&AB&CA1Y三、逻辑图35四、波形图ABCYttttt00000010010001101000101111011111波形图：将逻辑函数输入变量每一种可能出现的取值与对应的输出值按时间顺序依次排列起来的图形。36方法：

①找出所有使输出为1的输入组合；

②

将每一种组合以1对应原变量，0对应反变量的方法变换为逻辑符号与的形式；

③

将所有②

的结果相加(或)，得到的函数式就是Y。Y=ABC+ABC+ABC1、由真值表写函数式101110111五、各种表示方法间的相互转换372、由函数式写真值表将输入变量的各种组合一一代入函数式中计算输出变量值，全部完成后得到真值表。01010101C00110011B00001111Y=A+BC+ABCA011···01111例如：Y=A+BC+ABC求它的真值表。38BABY=AB+ABABA1&AB&1≥13、由逻辑图写逻辑函数式Y394、由函数式画逻辑图A1B1C1&≥1&≥1已知逻辑函数为画出对应的逻辑图。402.5.3逻辑函数的两种标准形式

最小项是构成逻辑函数的基本单元，对应于输入变量的每一种组合。n变量的最小项有2n个。一、最大项和最小项

n变量的最小项m是n个因子的乘积，每个变量都以它的原变量或反变量的形式在乘积项m中出现，且仅出现一次。1.最小项：最小项和最大项是构成逻辑函数的基本单元。最小项与最大项是等价的两个概念，虽然从形式上看是互反的，但表达的内容是一致的。412变量最小项2变量(A和B)逻辑函数，A和B两个因子构成的乘积项组合：AB、AB、AB、AB，称为2变量最小项。显然，A，B，A，B不是2变量最小项。42三变量最小项变量赋值为1时用原变量表示；变量赋值为0时用该变量的反变量来表示:可见输入变量的八种状态分别唯一地对应着八个最小项。43最小项的性质1在输入变量的任何取值下必有一个且仅有一个最小项的值为1。ABCABCABCABCABCABCABCABC输入变量取值A=0，B=1，C=0最小项0010000044全体最小项之和为1。ABC+ABC+ABC+ABC+ABC+ABC+ABC+ABCAB+AB+AB+ABA+A1实际上性质2可由性质1推出，想一想，为什么？最小项的性质245任意两个最小项的乘积为0。ABC•ABC=0实际上，性质3也可以由性质1推得，为什么？最小项的性质346具有逻辑相邻性的两个最小项之和可以消去一对因子而合并成一项。最小项的性质4逻辑相邻：若两个最小项只有一个因子以原、反区别，其他因子均相同，则称这两个最小项具有逻辑相邻性。47逻辑相邻的项可以合并且消去一对因子48最小项的编号：以三变量逻辑函数为例：

最小项通常用表示，下标i

即最小项编号，用十进制表示。49*2、最大项定义：在n变量逻辑函数中，若M为n个变量之和，而且这n个变量均以原变量或反变量的形式在M中出现且只出现一次，则称M为该组变量的最大项。n变量有2n个最大项。502变量最大项2变量(A和B)函数，A和B两个因子构成的和式组合有：A+B、A+B、B+A、A+B，称为2变量最大项。显然，A，B，A，B不是2变量最大项。513变量最大项A、B、C三个变量构成的最大项有：

如果把ABC的取值010看成一个二进制数，则它相当于十进制数2，因此我们把最大项A+B+C记为M2。52最大项的性质1在输入变量的任何取值下必有一个且仅有一个最大项的值为0。A+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+C输入变量取值A=0，B=1，C=0最大项1111101153全体最大项之积为0。实际上性质2可由性质1推出，想一想，为什么？最大项的性质254最大项的性质3任意两个最大项的和为1。（A+B+C）+（A+B+C）=1实际上，性质3也可以由最大项定义或者性质1推得。55最大项的性质4相邻的两个最大项之积可以消去一对因子而合并成一项相邻两个最大项只有一个因子不同，称相邻。A+B+CA+B+CA+B+CA+B+C（A+B+C）•（A+B+C）=B+C推论：n变量的最大项有n个相邻项。56最大项与最小项的关系57根据最小项的特点，从真值表可直接用最小项写出逻辑函数式。例如：由左图所示三变量逻辑函数的真值表，可写出其逻辑函数式：验证：将八种输入状态代入该表示式，均满足真值表中所列出的对应的输出状态。二、逻辑函数的最小项之和形式58将下列函数表示为最小项之和的形式：59三、逻辑函数的最大项之积形式结论：任意逻辑函数可以表示为最大项之积的形式（和之积式）。显然，由于最小项与最大项之间的对称关系，可以得到下面的结论：60已知逻辑函数的真值表如下，写出F的最大项表达式。612.5.4逻辑函数形式的变换与-或与非-与非或-与非与非-与或-与或非-或非与或非62§2.6逻辑函数的化简方法◆同一逻辑函数可以有多种不同的逻辑式，一般来讲，逻辑式越简单，它所表示的逻辑关系越明显，越有利于用最少的逻辑器件来实现这个函数。所以化简是必要的。63◆最简的标准与实际应用中能够提供的逻辑器件有关系，要根据实际而定；◆常用的逻辑器件有与非门、或非门、与或非门、异或门、非门等；◆以使用的器件数目最少、成本最低为判断最简的标准；◆默认最简形式为最简与-或式，即用最少的与门和或门来实现函数。642.6.1公式化简法最简与或式：乘积项的项数最少。每个乘积项中变量个数最少。例题：并项法吸收消去（长中含短，留下短）（长中含反，去掉反）（最简与或式）吸收消去65(合并项)（长中含短，留下短）(长中含反,去掉反)吸收消去吸收消去(正负相对,余全完)吸收消去（最简与或式）DEF:冗余因子DEFG:冗余项66添冗余项：(正负相对,余全完)消冗余项（长中含短，留下短）添冗余项：（最简与或式）(正负相对,余全完)合并项：A67添冗余项：（最简与或式）(正负相对,余全完)添冗余项：(正负相对,余全完)消冗余项（长中含短，留下短）合并项：A68

化简结果不唯一经过化简得最简与或式:或者:项数,因子数对应相同。讨论:69题1：反变量吸收提出AB=1提出A课堂练习用公式化简法化简下列逻辑函数式：70题2：摩根定律配项被吸收被吸收71结论：异或门可以用4个与非门实现。题3:

证明;摩根定律;展开72用4个与非门实现异或：&&&&ABY732.6.2卡诺图化简法--图形化简法一、逻辑函数的卡诺图表示法1.卡诺图的构成：下面举例说明卡诺图的画法:并且将逻辑相邻的最小项放在相邻的几何位置上，所得到的阵列图就是n变量的卡诺图。将n个输入变量的全部最小项用小方块阵列图表示，卡诺图的思想源于两个逻辑相邻的最小项可以化简的性质。74B01A01m3m0m2m1输入变量二变量卡诺图卡诺图的每一个方块（最小项）代表一种输入组合，并且把对应的输入组合注明在阵列图的上方和左方。一变量卡诺图m0m1L01m0m2m175逻辑相邻：相邻单元输入变量的取值只能有一位不同。0100011110

ABCm0m1m3m2m4m5m7m6输入变量三变量卡诺图注意：m2与m0逻辑相邻。m0m3m5m176ABCD0001111000011110四变量卡诺图m0m1m3m2m4m5m7m6m12m13m15m14m8m9m11m10卡诺图的特点：具有循环邻接的特性。m5m1m4m7m13775变量卡诺图CDEAB00000101101011011110110000m0m1m3m2m6m7m5m401m8m9m11m10m14m15m13m1211m24m25m27m26m30m31m29m2810m16m17m19m18m22m23m21m20m6m7m5m4m14m15m13m12m30m31m29m28m22m23m21m20m20m21m23m22m28m29m31m30m12m13m15m14m4m5m7m678卡诺图的简化表示法：有时为了方便，用对应最小项的编号表示单元格。ABC0001111001简化的三变量卡诺图:简化的四变量卡诺图:ABCD0001111000011110792.已知逻辑函数画卡诺图：BCA000111100m0m1m3m21m4m5m7m600000111方法：先将逻辑函数表示为最小项之和的形式，然后在卡诺图相应最小项位置填1，其它地方填0。ABC802.已知逻辑函数画卡诺图：例1：画出以下逻辑函数的卡诺图：解：根据反演规则，上式化成：81所以，L的卡诺图为：ABCD0001111000011110011111101001111082二、用卡诺图化简逻辑函数原理：相邻的两个最小项可以化简消去一对因子。0100100100101111ABCD000111100001111083化简原则如果两个最小项相邻，可以合并为一项并消去一对因子；如果四个最小项相邻，可以合并为一项并消去两对因子；如果八个最小项相邻，可以合并为一项并消去三对因子；如果2n个最小项相邻，可以合并为一项并消去n对因子。84两个最小项相邻的情况11

1111111185四个最小项相邻的情况11111111111111111111111186八个最小项相邻的情况111111111111111111111111111111111111111187卡诺图法化简步骤(一)布阵（画法规则）(二)填项(用卡诺图表示逻辑函数)(三)勾圈化简(用卡诺图化简)三步曲(一)布阵（画法规则）：1.N=2n

格（n5）:

最小项2.循环码编排循环邻接上下封闭布阵88ABCD00011110000111

10ABDC

m0m1m3m2

m4m5m7m6

m8m9m11m10

m12m13m15m14高位低位89(二)填项：用卡诺图表示逻辑函数填F=1的项1.最小项直接填入；2.刷项（填公因子所包含的项）；3.按（m0,m15)

编号填入。按F=1的与或式填项方法90例1:ABCD00011110000111

10ABDC1直接填入1公因子:有重复“1”者，只填一个“1”。91ABCD00011110000111

10ABDC1111公因子:BD有重复“1”者，只填一个“1”。刷项：填公因子包含的项例1:92ABCD00011110000111

10ABDC111111111111有重复“1”者，只填一个“1”。刷项：填公因子包含的项例1:93ABCD00011110000111

10ABDC11111111

11

11F=1的项全部填完以后,填项结束;不填者自动为“0”。例1:000094(三)勾圈化简：1.尽量勾大，2i个格消i个变量(in);3.每个圈至少有一个独立格；4.圈必须覆盖所有的“1”，即不能遗漏取值为“1”的小方块。勾圈原则得到最简与或式。2.“1”可以重复利用；95ABCD00011110000111

10ABDC11111111

11

11D保留公因子：消取值不同的变量：B保留公因子：合理重叠（“1”可以重复使用）。例1:000096也可以取F=0的项化简:ABCD00011110000111

1011111111

11

11000097BABCD00011110000111

10ACD

111111填项：98BABCD00011110000111

10ACD

111111111F=1的项全部填完以后,其它补零。000000099BABCD00011110000111

10ACD

111111111冗余项勾圈化简0000000100例2：用公式化简法得到下式，问是否最简，若不是,请化简之。ABC01000111101111BC填项：101例2：用公式化简法得到下式，问是否最简，若不是,请化简之。ABC0100011110111111BCF=1的项全部填完以后,填项结束。00102ABC0100011110111111勾圈化简：00103ABC0100011110

111111

00104ABC0100011110111111ABC0100011110111111说明：化简结果不唯一。0000105F4(A,B,C,D)=m(0,1,2,5,6,7,8,10,11,12,13,15)F4=（m0,m1,m2,m5,m6,m7,m8,m10,m11,m12,m13,m15)BABCD00011110000111

10ACD111111111111高位低位(A,B,C,D)0000106BABCD00011110000111

10ACD111111111111F4(A,B,C,D)=m(0,1,2,5,6,7,8,10,11,12,13,15)每次勾圈时，应包含尽量多的独立格。0000107BABCD00011110000111

10ACD111111111111

F4(A,B,C,D)=m(0,1,2,5,6,7,8,10,11,12,13,15)0000108BABCD00011110000111

10ACD111111111111BABCD00011110000111

10ACD111111111111每次勾圈时，应包含尽量多的独立格,以避免出现冗余项。化简结果不唯一。说明一：说明二：00000000109§2.7具有无关项的逻辑函数及其化简

在分析某些具体的逻辑函数时，n个变量的2n种组合中有一些变量取值不会出现(或不允许出现)，对输入变量取值所加的限制称为约束。这些取值所对应的最小项称为约束项，约束项的值恒等于0。在真值表和卡诺图中，用或表示无关项;在逻辑式中,用d

来表示无关项之和。

另一种情况是输入变量的某些取值下函数是1还是0皆可，并不影响电路功能。这些变量取值下，其值为1的那些最小项称为任意项。约束项和任意项统称为无关项。2.7.1约束项、任意项和逻辑函数式中的无关项110六个约束项：m10,m11,m12,m13,m14,m15二十进制编码（8421BCD)例：四变量A,B,C,D取：111例题:

将下列具有无关项的逻辑函数化为

最简与或式。2.7.2无关项在化简逻辑函数中的应用112解:由于无关项是否写入逻辑函数式无关紧要，因此，用卡诺图法利用无关项进行化简时无关项的值可以当“0”处理，也可以当“1”处理；必要时当“1”处理,这样可以使逻辑函数化得更简单（可以尽量勾大）。113BABCD00011110000111

10ACD11111高位低位0000000114BABCD00011110000111

10ACD1111111100115课堂练习1：化简F(A,B,C,D)=m(0,2,3,5,6,8,9,10,11,12,13,14,15)ABCD0001111000011110A116ABCD00011110000100011001xxxx10xx11102：化简117二、逻辑代数：1.基本运算法则：结合律、交换律、分配律等；2.几种形式的吸收律；3.几个定理：德摩根定理、反演定理。逻辑代数：数字