第2章布尔开关代数(2)第3章组合逻辑原理(1)

1、数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理上一次课内容复习：上一次课内容复习：一一二进制逻辑函数和符号二进制逻辑函数和符号二二开关代数的性质和定理开关代数的性质和定理三三功能完全操作集功能完全操作集四四用布尔代数简化布尔方程用布尔代数简化布尔方程数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理o运算符：运算符： “( )”，“ * ”，“ ”，或空或空S=x yS=x ys=x s=x y ys=x s=x * * y ys=(x) (y)s=(x) (y)o两个输入变量的真值表两个输入变量的

2、真值表（1 1）与（与（AND）o与运算的逻辑符号与运算的逻辑符号S复习一：二进制逻辑函数和符号复习一：二进制逻辑函数和符号数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理o 运算符：运算符：“+”s=x + ys=x + yo 两个输入变量的真值表两个输入变量的真值表（2 2）或（或（OR）o或运算的逻辑符号或运算的逻辑符号S数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理o 运算符：运算符：“ ” ，“ ”（3 3）非（非（NOT）o非运算的逻辑符号非运算的逻辑符号o 真值表真值表 x= x x

3、= x ，x= xx= x数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理（4 4）与非与非s=(x y) ; s= x ys=(x y) ; s= x y数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理（5 5）或非或非NOR （not or）s=(x+ y) s=(x+ y) ；s=x + ys=x + y数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理（6 6）异或异或EX-OR （exclusive or）s= x ys= x y ；s= s=

4、 xyxy + + xyxy数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理（7 7）异或非异或非EX-NOR （exclusive not or）s= x ys= x y ； s= x s= x y y ； s= s= xyxy + + xyxy数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理XYZXX?&XXYZ+X?Z=XYZ=X+YXYZ1o 各种门各种门IEEE逻辑符号逻辑符号数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理XYZ&XYZ+X

5、YZ=1XYZ=1Z=X YZ=X YXYZ Z=X+YZ=XYo 各种门各种门IEEE逻辑符号逻辑符号数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理 开关开关代数的性质代数的性质（1 1）交换律）交换律：X+Y=Y+X XY=YX（2 2）结合律：）结合律：(X+Y)+Z=X+(Y+Z) (XY) Z=X (YZ)（3 3）分配律：）分配律：X(Y+Z)=XY+XZ X+(YZ)=(X+Y) (X+Z)（4 4）0-10-1律：律：X+0=X X1=XX+1=1 X0=0（5 5）互补律：）互补律：X X=0 X + X=1复习二：开关代数的

6、性质和定理复习二：开关代数的性质和定理数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理 开关开关代数的其它性质和定理代数的其它性质和定理（1 1）二进制变量和常数二进制变量和常数 0+0=0 1+0=1 0+1=1 1+1=1 0 0=0 1 0=0 0 1=0 1 1=1（2 2）等幂律等幂律：X+X=X XX=X（3 3）吸收律吸收律：X+XY=X X(X+Y)=X X+X Y=X+Y X(X+Y)=XY（4 4）德德摩根定理摩根定理：X+Y=X Y X Y=X + Y（5 5）邻接律邻接律：XY+XY=X (X+Y) (X+Y)=X数字逻辑

7、：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理德德摩根定理摩根定理：(X+Y)=X Y互补律：如果满足互补律：如果满足AB=0 和和 A+B=1，则，则A=B。证明：证明： (X Y)+(X+Y)=(X Y+X)+Y(结合结合)=(Y+X)+Y(吸收吸收)=X+(Y+Y) (结合结合)=X+1=1 (X Y) (X+Y)=X Y X+XY Y=0+0=0 (X+Y)=X Y(利用利用)数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理 功能完全操作集（完备运算集）：是一组逻辑函数集，功能完全操作集（完备运算

8、集）：是一组逻辑函数集，它能实现所有的组合逻辑表达式。它能实现所有的组合逻辑表达式。 二进制逻辑函数的功能完全操作集有四类：二进制逻辑函数的功能完全操作集有四类：（1）FC1与、或、非与、或、非（2）FC2或非或非 （3）FC3与非与非（4）FC4异或、与异或、与复习三：功能完全操作集复习三：功能完全操作集数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理 原因：减少数字逻辑门电路的开销。原因：减少数字逻辑门电路的开销。 方法：利用开关代数的性质和定理，进行化简。方法：利用开关代数的性质和定理，进行化简。 布尔方程（逻辑表达式）有布尔方程（逻辑表达

9、式）有2种形式：一种是种形式：一种是And-Or表达式（积之和）形式；另一种是表达式（积之和）形式；另一种是Or-And表达式（和之表达式（和之积）形式。积）形式。复习四：用布尔代数简化布尔方程复习四：用布尔代数简化布尔方程数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理2.5 2.5 开关函数开关函数的实现的实现 开关函数开关函数的三种表达方式：开关方程、真值表、逻辑图的三种表达方式：开关方程、真值表、逻辑图 实现实现组合逻辑功能的组合逻辑功能的5个步骤个步骤问题描述问题描述构造真值表构造真值表求出开关方程（逻辑表达式）求出开关方程（逻辑表达式

10、）用逻辑符号画出逻辑图用逻辑符号画出逻辑图绘制印制板电路绘制印制板电路数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理2.5.l 2.5.l 开关开关方程到逻辑图的转换方程到逻辑图的转换 转换方法：用二进制通用逻辑符号替换开关方程的每转换方法：用二进制通用逻辑符号替换开关方程的每一项，即可得到开关方程的逻辑图。一项，即可得到开关方程的逻辑图。aababab+ababb例例2-122-12：数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理 对于多个输出的开关方程，在转换成逻辑图时，相同对于多个输出的开

11、关方程，在转换成逻辑图时，相同的项可以共享。的项可以共享。例例2-132-13：F1F2F1F2数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理2.5.2 2.5.2 逻辑图的转换为开关方程逻辑图的转换为开关方程 转换方法：与开关方程到逻辑图的转换方法相反，即转换方法：与开关方程到逻辑图的转换方法相反，即根据逻辑图，从输入端开始，逐级写出各个门电路的输出根据逻辑图，从输入端开始，逐级写出各个门电路的输出表达式，最后就得到逻辑图对应的开关方程。表达式，最后就得到逻辑图对应的开关方程。例例2-132-13：函数：函数F1F1F1数字逻辑：第二章数字逻

12、辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理 主要内容：组合逻辑的定义；真值表的确定；从真值主要内容：组合逻辑的定义；真值表的确定；从真值表生成开关方程；卡诺图及其化简；映射变量卡诺图；混表生成开关方程；卡诺图及其化简；映射变量卡诺图；混合逻辑组合电路；多输出函数。合逻辑组合电路；多输出函数。3.l 3.l 组合逻辑组合逻辑的定义的定义 定义：定义：如果逻辑电路中没有从输出到输入的反馈，且如果逻辑电路中没有从输出到输入的反馈，且由功能完全的门电路构成，由功能完全的门电路构成，就称为组合逻辑电路。就称为组合逻辑电路。输入输入X输出输出Y第第3 3章章 组合逻辑原理组

13、合逻辑原理Y=F(X)数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理3.1.1 3.1.1 真值表问题的提出真值表问题的提出例例3-13-1：数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理例例3-23-2：数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理例例3-43-4：数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理 将实际问题描述转换成真值表的过程：将实际问题描述转换成真值表的过程： 确定所包含的

14、输入、输出变量；确定所包含的输入、输出变量； 为每个变量分配变量名；为每个变量分配变量名； 确定真值表的大小：确定真值表的大小：2xy； 构造一个包含所有输入变量组合的真值表；构造一个包含所有输入变量组合的真值表； 确定使给定输出为真的输入组合。确定使给定输出为真的输入组合。数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理例：例：设计一个组合逻辑的真值表，当设计一个组合逻辑的真值表，当3个输入中的多数为个输入中的多数为真时输出为真。真时输出为真。第一步：第一步：3 3个输入，个输入，1 1个输出个输出第二步：第二步：I1、I2、I3，O1第三步：

15、第三步：23=8第四步：第四步：第五步：第五步：数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理3.1.2 3.1.2 导出导出开关方程开关方程1.1.术语术语与定义与定义 乘积项：一个或几个布尔变量的逻辑乘积（与）。乘积项：一个或几个布尔变量的逻辑乘积（与）。 例：例：X、XY、XYZ。 和项：一个或几个布尔变量的逻辑或。和项：一个或几个布尔变量的逻辑或。 例：例：X、X+Y、X+Y+Z。 积之和：几个乘积项的逻辑或。积之和：几个乘积项的逻辑或。 例：例：X+XY+XYZ。 和之积：几个或项的逻辑与。和之积：几个或项的逻辑与。 例：例：(X+Y

16、)(X+Y+Z)。数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理 最小项：是组成一个布尔表达式的包含所有输入变最小项：是组成一个布尔表达式的包含所有输入变量（每个变量出现一次）的乘积项，是特殊情况下量（每个变量出现一次）的乘积项，是特殊情况下的乘积（与）项。的乘积（与）项。 例：例：X、Y、Z的的XY Z 最大项：是组成一个布尔表达式的包含所有输入变最大项：是组成一个布尔表达式的包含所有输入变量（每个变量出现一次）的和项，是特殊情况下的量（每个变量出现一次）的和项，是特殊情况下的和（或）项。和（或）项。 例：例：X、Y、Z的的X+Y+Z数字逻辑

17、：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理2.2.标准标准积之和积之和 一个标准积之和是当输出变一个标准积之和是当输出变量为逻辑量为逻辑1（真）时定义的最小（真）时定义的最小项的完整系列。项的完整系列。例例3-1：输出变量输出变量M的标准积之和为：的标准积之和为： M=abms+abms+abms数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理3.3.标准标准和之积和之积 一个标准和之积是当输出变量为一个标准和之积是当输出变量为逻辑逻辑0（假）时定义的最大项的完整系（假）时定义的最大项的完整系列。列。

18、 同例：在例同例：在例3-1题中，题中，输出变量输出变量M的标准和之积为：的标准和之积为： M=(a+b+m+s)(a+b+m+s)(a+b+m+s) (a+b+m+s)(a+b+m+s)(a+b+m+s) (a+b+m+s)(a+b+m+s)(a+b+m+s) (a+b+m+s)(a+b+m+s)(a+b+m+s) (a+b+m+s)数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理4.最小项和最大项的互补特性最小项和最大项的互补特性 miMi，即最小项（小写表示）和最大项（，即最小项（小写表示）和最大项（大写表大写表示示）互补。）互补。数字逻辑

19、：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理3.2 标准形式标准形式 标准形式：任何布尔函数（开关方程）都可以用唯一标准形式：任何布尔函数（开关方程）都可以用唯一的标准积（最小项）之和或者标准和（最大项）之积来表的标准积（最小项）之和或者标准和（最大项）之积来表示。示。1. 将将SOP（Sum of Products）方程转换成标准形式）方程转换成标准形式 转换方法：转换方法：（1）确定每个）确定每个“与与”项中缺少的变量；项中缺少的变量；（2）若某个）若某个“与与”项缺少变量项缺少变量x，则将该项和，则将该项和(x+x)相相“与与”，并用分配律展开

20、；，并用分配律展开；（3）去掉整个表达式中重复的最小项。）去掉整个表达式中重复的最小项。数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理例：例：例例3-5 a： 数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理2.将将POS（Product of Sums）方程转换成标准形式）方程转换成标准形式 转换方法：转换方法：（1）确定每个）确定每个“或或”项中缺少的变量；项中缺少的变量；（2）若某个）若某个“或或”项缺少变量项缺少变量x，则将该项和，则将该项和(xx)相相“或或”，并用分配律展开；，并用分配

21、律展开；（3）去掉整个表达式中重复的最大项。）去掉整个表达式中重复的最大项。例：例： 数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理例例3-5 c：数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理3.3 从真值表生成开关方程从真值表生成开关方程1. 将真值表转换成标准形式的开关方程将真值表转换成标准形式的开关方程 转换方法：将真值表中所有输出变量为逻辑转换方法：将真值表中所有输出变量为逻辑1（真）（真）时的最小项相时的最小项相“或或”，就得到开关方程的标准积之和形式；，就得到开关方程的标准积之和形

22、式；将真值表中所有输出变量为逻辑将真值表中所有输出变量为逻辑0（假）时的最大项相（假）时的最大项相“与与”，就得到开关方程的标准和之积形式。，就得到开关方程的标准和之积形式。数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理例：真值表如表所示。例：真值表如表所示。 标准积之和形式：标准积之和形式： 标准和之积形式标准和之积形式：abcf100000011010101101001101011011110数字逻辑：第二章数字逻辑：第二章 布尔开关代数布尔开关代数第三章第三章 组合逻辑原理组合逻辑原理2. 用求和符号用求和符号、求积符号、求积符号 习惯上可以采用习惯上可以采用求和符号求和符号来表示积之和，采用求积来表示积之和，采用求积符号符号和之积和之积。 对于前面的例子，得到如下关系：对于前面的例子，得到如下关系：o f1(a,b,c) = m(1,2,4,6) 表示求积之和的形式，表示求积之和的形式，m(1,2,4,6)表示最小项有表示最小项有m1, m2, m4, 和和m6。o f1(a