组合逻辑设计原理课件

学习要求：掌握开关代数的基本概念，学会用逻辑函数描述逻辑问题掌握逻辑代数的公理、基本定理和重要规则学会用卡诺图化简逻辑函数第4章逻辑代数基础8/14/20231学习要求：第4章逻辑代数基础8/1/20231第4章逻辑代数基础（续）习题完成下列练习:5,9bcde,10abe,13ac,16abc,19ace,22ab,29,43,46,55abcd,65,66,83.8/14/20232第4章逻辑代数基础（续）习题8/1/20232逻辑电路的分析、综合与设计第4章逻辑代数基础（续）分析：从逻辑图开始，得到该电路功能的形式描述，如真值表或逻辑表达式。综合：与分析相反，从形式描述开始，得到逻辑图。通常可由软件来完成。设计：从接受用户要求开始，得到逻辑图。将实际问题的非形式描述（语言或想法）转换成形式描述，即定义电路的输入、输出，并用真值表或表达式说明它的功能特性。综合组合逻辑电路任一时刻的输出仅取决于当时的输入；可以含有任意数目的逻辑门电路和反相器，但不包括反馈回路。8/14/20233逻辑电路的分析、综合与设计第4章逻辑代数基础（续）分析公理（5条）4.1开关代数（A1）如果X≠1，则X＝0；（A1'）如果X≠0，则X＝1。（开关变量X的取值特性）（A2）如果X＝0，则X'＝1；（A2'）如果X＝1，则X'＝0。（反相器的功能特性）“与”和“或”操作的特性（A3）0·0＝0；（A3'）1＋1＝1（A4）1·1＝1；（A4'）0＋0＝0（A5）0·1＝1·0＝0；（A5'）1＋0＝0＋1＝18/14/20234公理（5条）4.1开关代数（A1）如果X≠1，则X＝04.1开关代数（续）单变量定理可用完备归纳法证明8/14/202354.1开关代数（续）单变量定理可用完备归纳法证明8/14.1开关代数（续）二变量和三变量定理运算优先顺序分配律定理T9和T10广泛地用来简化逻辑函数。在所有的定理中，可以用任意逻辑表达式来替换每个变量。8/14/202364.1开关代数（续）二变量和三变量定理运算优先顺序8/

n变量定理4.1开关代数（续）可用有限归纳法证明例：证明X＋X＋···＋X＝X1、当n＝2时，X+X=X（T3）2、设当n＝i时，X+X+···+X=X3、则当n＝i+1时，X+X+X+···+X=X+(X+X+···+X)（T7）=X+X=X8/14/20237n变量定理4.1开关代数（续）可用有限归纳法证明3、则德·摩根定理4.1开关代数（续）

+01原变量反变量F

+01原变量反变量F'8/14/20238德·摩根定理4.1开关代数（续）+01原变量反变量F德·摩根定理（续）4.1开关代数（续）使用广义德·摩根定理时，要保持原逻辑表示式中运算符号的优先顺序不变。8/14/20239德·摩根定理（续）4.1开关代数（续）使用广义德·摩根定对偶性原理

对开关代数的任何定理或恒等式，若交换所有的0和1以及“＋”和“·”，结果仍正确。4.1开关代数（续）它使要学的东西减了一半！8/14/202310对偶性原理4.1开关代数（续）它使要学的东西减了一半！4.1开关代数（续）8/14/2023114.1开关代数（续）8/1/2023118/14/2023128/1/202312逻辑函数表示法4.1开关代数（续）

文字：变量或变量的补，如X、Y、X'、Y'；乘积项：单个文字或2个或2个以上文字的逻辑积，如Z'，W·X·Y；“积之和”表达式：乘积项的逻辑和，如Z'＋W·X·Y；求和项：单个文字或2个或2个以上文字的逻辑和，如Z'，W＋X＋Y；“和之积”表达式：求和项的逻辑积，如Z'·(W＋X＋Y)；标准项：一个乘积项或求和项，其中每个变量只出现一次，如W·X·Y'，W＋X'＋Y；非标准项：不是标准项的乘积项或求和项，如W·X·X·Y'；8/14/202313逻辑函数表示法4.1开关代数（续）文字：变量或变量的补

最小项m：设一个逻辑函数有n个变量，则一个有n个文字的标准乘积项称为一个最小项，共有2n个最小项。如4变量最小项m0:W'·X'·Y'·Z'，m13:W·X·Y'·Z，m2:W'·X'·Y·Z'；4.1开关代数（续）

最大项M：设一个逻辑函数有n个变量，则一个有n个文字的标准求和项称为一个最大项，共有2n个最大项。如4变量最大项M15:W'＋X'＋Y'＋Z'，M6:W＋X'＋Y'＋Z，M13:W'＋X'＋Y＋Z'；8/14/202314最小项m：设一个逻辑函数有n个变量，则一个有n个文字的标准真值表n个变量的真值表有2n行4.1开关代数（续）含有n个变量的函数有个8/14/202315真值表4.1开关代数（续）含有n个变量的函数有最小项列表：F(X,Y,Z)=

XYZ(0,3,4,6,7)4.1开关代数（续）标准积之和式：F(X,Y,Z)=X'Y'Z'+X'YZ+XY'Z'+XYZ'+XYZ=X'Y'Z'+XY'Z'+XYZ'+XYZ+X'YZ+XYZ=Y'Z'+XY+YZ8/14/202316最小项列表：F(X,Y,Z)=XYZ(0,3,最大项列表：F(X,Y,Z)=

XYZ(1,2,5)4.1开关代数（续）标准和之积式：F(X,Y,Z)=(X+Y+Z')(X+Y'+Z)(X'+Y+Z')8/14/202317最大项列表：F(X,Y,Z)=XYZ(1,2,从电路图得到逻辑函数的形式描述，如真值表、逻辑表达式。确定电路行为；根据代数描述提出逻辑函数的不同电路结构；交流与学习。4.2组合电路分析穷举法8/14/202318从电路图得到逻辑函数的形式描述，如真值表、逻辑表达式。4.4.2组合电路分析（续）代数法F＝((X+Y')·Z)+(X'·Y·Z')=X·Z＋Y'·Z＋X'·Y·Z'（乘开）8/14/2023194.2组合电路分析（续）代数法F＝((X+Y')4.2组合电路分析（续）F＝((X+Y')·Z)+(X'·Y·Z')＝(X＋Y'＋X')·(X＋Y'＋Y)·(X＋Y'＋Z')·(Z＋X')·(Z＋Y)·(Z＋Z')＝1·1·(X＋Y'＋Z')·(X'＋Z)·(Y＋Z)·1＝(X＋Y'＋Z')·(X'＋Z)·(Y＋Z)（加开）8/14/2023204.2组合电路分析（续）F＝((X+Y')·Z

电路描述和设计用真值表对电路进行描述，不容易出现错误，容易用标准和或标准积表达式直接设计，但当变量数很多时表可能会很大。4.3组合电路综合例：对一个4位素数检测器可作这样的描述：“对于4位输入组合N＝N3N2N1N0，当N＝1、2、3、5、7、11、13时，函数输出为1，其他情况输出为0”8/14/202321电路描述和设计4.3组合电路综合例：对一个4位素数检测用连接词“与”、“或”、“非”来描述逻辑函数（可以通过定义辅助变量简化表达式），比写出完全真值表要容易些（当变量数很多时），但容易出现错误。4.3组合电路设计（续）例：描述一个报警电路：“当PANIC输入为1，或者当ENABLE输入为1、EXITING输入为0，并且房子不安全时，ALARM输出为1；当WINDOW、DOOR、和GARAGE输入都为1时，房子是安全的。”ALARM=PANIC+ENABLE×EXITING'×SECURE'SECURE=WINDOW×DOOR×GARAGEALARM=PANIC+ENABLE×EXITING'×(WINDOW×DOOR×GARAGE)'8/14/202322用连接词“与”、“或”、“非”来描述逻辑函数（可以通过定义电路处理一般来说，与非门和或非门比与门和或门要快，但多数人不习惯用与非和或非形式来描述逻辑命题。

4.3组合电路设计（续）“如果你不整洁或不富有，并且也不聪明或不友好，我就不和你约会。”

“如果你整洁且富有，或者你聪明且友好，我就和你约会。”我们两人去或他们两人去,一定能解决这个问题?8/14/202323电路处理4.3组合电路设计（续）“如果你不整洁或不富有4.3组合电路设计（续）哪个电路工作速度最快？8/14/2023244.3组合电路设计（续）哪个电路工作速度最快？8/1/24.3组合电路设计（续）组合逻辑电路的简化：一般来说，逻辑函数表达式越简单，设计出来的电路也就越简单。例：化简解：代数化简法：运用逻辑代数的公理、定理和规则对逻辑函数进行推导、变换而进行化简。没有固定的步骤可以遵循，主要取决于对公理、定理和规则的熟练掌握及灵活运用的程度。有时很难判定结果是否为最简。7个门3个门2个门8/14/2023254.3组合电路设计（续）组合逻辑电路的简化：一般来说，4.3组合电路设计（续）“与或”式化简应满足的两个条件：表达式中“与项”的个数最少；在满足上面要求的前提下,“与项”中的变量总数最少。“或与”式化简应满足的两个条件：表达式中“或项”的个数最少；在满足上面要求的前提下,“或项”中的变量总数最少。卡诺图化简法：该方法简单、直观、容易掌握，当变量个数小于等于6时非常有效，在逻辑设计中得到广泛应用。卡诺图的构成：n个变量的卡诺图是一种由2n个方格构成的图形，每一个方格表示逻辑函数的一个最小项，所有的最小项巧妙地排列成一种能清楚地反映它们相邻关系的方格阵列。一个函数可用图形中若干方格构成的区域来表示。8/14/2023264.3组合电路设计（续）“与或”式化简应满足的两个条件mo

m2m1

m30101ABAB0101二变量卡诺图mo

m2m6

m4m1

m3m7

m50001111001ABC0001111001ABC三变量卡诺图04

1281

5

1393715112614100001111000011110ABCD0001111000011110ABCD四变量卡诺图8/14/202327mom20101ABAB04.3组合电路设计（续）相邻最小项（或与项）：彼此只有一个变量不同，且这个不同变量互为反变量的两个最小项（或与项）称为相邻最小项（或相邻与项），如ABC和ABC'。相邻最小项在卡诺图中有几何相邻、相对相邻和重叠相邻三种特征。04

1281

5

1393715112614100001111000011110ABCD0001111000011110ABCD04

1281

5

1393715112614100001111000011110ABCDE1620

282417

21

292519233127182230260001111000011110ABCDE8/14/2023284.3组合电路设计（续）相邻最小项（或与项）：彼此只4.3组合电路设计（续）逻辑函数的卡诺图表示：将逻辑函数所对应的最小项在卡诺图的相应方格中标以1，剩余方格标以0或不标。其它形式的函数要转换成“与或”式后，再在卡诺图上表示。卡诺图的性质：根据T10有AB+AB'=A，它表明两个相邻“与项”或相邻"最小项"可以合并为一项，这一项由两个"与项"中相同的变量组成，可以消去两个"与项"中不同的变量。0001111001ABC11111例如：

可表示为：“与或”式的卡诺图表示：直接将表达式的“与项”或“最小项”所对应的方格标以1。8/14/2023294.3组合电路设计（续）逻辑函数的卡诺图表示：将逻辑函4.3组合电路设计（续）卡诺圈：在卡诺图上把相邻最小项所对应的小方格"圈"在一起可进行合并，以达到用一个简单"与项"代替若干最小项的目的。0101AB110101AB110101AB111二变量卡诺图合并的典型情况0001111001ABC1111AB0001111001C1111111101ABC00011110三变量卡诺图合并的典型情况8/14/2023304.3组合电路设计（续）卡诺圈：在卡诺图上把相邻最小项4.3组合电路设计（续）一个卡诺圈中的小方格满足以下规律：卡诺圈中的小方格的数目为2m，m为整数且m

n；2m个小方格含有m个不同变量和(n-m)个相同变量；2m个小方格可用(n-m)个变量的“与项”表示，该“与项”由这些最小项中的相同变量构成；当m=n时，卡诺圈包围整个卡诺图，可用1表示，即n个变量的全部最小项之和为1。100011110ABCD1111111四变量卡诺图合并的典型情况000111108/14/2023314.3组合电路设计（续）一个卡诺圈中的小方格满足以下规4.3组合电路设计（续）蕴涵项（如何画圈）蕴涵项：“与或”式中的每一个“与项”称为函数的蕴涵项。质蕴涵项：不被其它蕴涵项所包含的蕴涵项。必要质蕴涵项：质蕴涵项中至少有一个最小项不被其它蕴涵项所包含。8/14/2023324.3组合电路设计（续）蕴涵项（如何画圈）8/1/204.3组合电路设计（续）用卡诺图化简逻辑函数的一般步骤：第一步：作出函数的卡诺图；第二步：在卡诺图上圈出函数的全部质蕴涵项（画最大的卡诺圈）；第三步：从全部质蕴涵项中找出所有必要质蕴涵项；第四步：若全部必要质蕴涵项尚不能覆盖所有的1方格，则需从剩余质蕴涵项中找出最简的所需质蕴涵项，使它们和必要质蕴涵项一起构成函数的最小覆盖（把它们全部“或”起来）。8/14/2023334.3组合电路设计（续）用卡诺图化简逻辑函数的一般步骤4.3组合电路设计（续）例：用卡诺图将下列逻辑函数简化为“与或”表达式

F(A,B,C,D)=

m(0,3,5,6,7,10,11,13,15)解：10001111000011110ABCD11111111110001111000011110ABCD11111111*1*0001111000011110ABCD11*1*1*111*8/14/2023344.3组合电路设计（续）例：用卡诺图将下列逻辑函数简化为4.3组合电路设计（续）例：用卡诺图将下列逻辑函数简化为“与或”表达式

F(A,B,C,D)=

m(2,3,6,7,8,10,12)解：10001111000011110ABCD11111110001111000011110ABCD1*1*1*1*11110001111000011110ABCD1*1*1*1*1110001111000011110ABCD1*1*1*1*18/14/2023354.3组合电路设计（续）例：用卡诺图将下列逻辑函数简化为4.3组合电路设计（续）例：用卡诺图将下列逻辑函数简化为“或与”表达式

F(A,B,C,D)=

M(3,4,6,7,11,12,13,14,15)

解：CD10001111000011110AB0010010110010018/14/2023364.3组合电路设计（续）例：用卡诺图将下列逻辑函数简化为4.3组合电路设计（续）没有必要质蕴涵项的情况8/14/2023374.3组合电路设计（续）没有必要质蕴涵项的情况8/1/4.3组合电路设计（续）例：用卡诺图化简逻辑函数F(A,B,C,D)=m(2,3,4,5,6,7,11,13,15)解：CD0001111000011110AB111111111CD00001111000011110AB000000化简后得到的表达式一般为两级“与或式”或“或与式”，可分别由两级“与非门”或“或非门”来实现，但实际上受扇入系数的影响，电路的级数会增加，影响电路的速度。为不降低速度，人们设计出更复杂的门来取代简单门完成更复杂的运算。?有问题8/14/2023384.3组合电路设计（续）例：用卡诺图化简逻辑函数F(A,4.3组合电路设计（续）包含无关最小项的逻辑函数的化简一般来说，逻辑函数与输入的每一种取值组合均有关系。对于某些组合（某些最小项）函数的值为0，而对另外一些组合（另外一些最小项）函数取值为1。无关最小项：一个逻辑函数,如果它的某些输入取值组合因受特殊原因制约而不会再现，或者虽然每种输入取值组合都可能出现，但此时函数取值为1还是为0无关紧要，那么这些输入取值组合所对应的最小项称为无关最小项。无关最小项可以随意地加到函数表达式中，或者不加到函数表达式中，并不影响函数所对应逻辑电路的实际逻辑功能。8/14/2023394.3组合电路设计（续）包含无关最小项的逻辑函数的化简4.3组合电路设计（续）例：给定某电路的真值表如下，求F的最简"与或"式。10001111000011110ABCD11111110001111000011110ABCD1111ddddddABCDF0000d0001d0010d001110100101011011000111010000100101010110111110011101d1110d1111d8/14/2023404.3组合电路设计（续）例：给定某电路的真值表如下，求F从多输出函数化简的观点来看，它们不是最佳的，应该是：

10001111001ABC11F110001111001ABC11F2例：多输出函数对应的卡诺图为：4.3组合电路设计（续）多输出逻辑函数的化简：如果孤立地将单个输出一一化简，然后直接拼在一起，通常并不能保证整个电路最简。所有逻辑表达式包含的不同“与项”总数最小；在满足上述条件的前提下，各不同"与项"中所含的变量总数最少。注意红色项！8/14/202341从多输出函数化简的观点来看，它们不是最佳的，应该是：1004.3组合电路设计（续）列表化简法(Q-M法)第一步：将函数表示成“最小项之和”形式，并用二进制编码表示每一个最小项；第二步：找出函数的全部质蕴涵项；第三步：找出函数的全部必要质蕴涵项；第四步：找出函数全部所需质蕴涵项。最小化“积之和”=必要质蕴涵项+所需质蕴涵项8/14/2023424.3组合电路设计（续）列表化简法(Q-M法)8/1/4.3组合电路设计（续）

(I)最小项(II)(n－1)个变量的“与”项(III)(n－2)个变量的“与”项编号miABCD组号

mi

miABCDPiABCDPi01234000010000101100110100111101111101111085910711141501230,88,98,105,79,1110,1110,147,1511,1514,15－000100－10－001－110－1101－1－10－1111－11111－128,9,10,1110,11,14,1510－－1－1－组号Pi

p1p5p4p3p2例：用列表法化简F(A,B,C,D)＝m(0,5,7,8,9,10,11,14,15)解：1、用二进制编码表示函数中的每一个最小项；质蕴涵项产生表2、找出函数的全部质蕴涵项；8/14/2023434.3组合电路设计（续）(I)最4.3组合电路设计（续）P1=m(10,11,14,15)＝AC， P2=m(8,9,10,11)＝AB'P3=m(7,15)＝BCD， P4=m(5,7)＝A'BDP5=m(0,8)＝B'C'D'mipiP1*P2*P3P4*P5*0 5 7 8 9 10 11 14 15

× ×

× ×

× × × ×

×

×

覆盖情况必要质蕴涵项产生表3、求必要质蕴涵项F(A,B,C,D)＝AC+AB'+A'BD+B'C'D'8/14/2023444.3组合电路设计（续）P14、求所需质蕴涵项mipiP1*P2P3P4P5P6P7*2 4 6 8 9 10 12 13 15 ×

× × × × × × × × × × × × ×

覆盖情况4.3组合电路设计（续）8/14/2023454、求所需质蕴涵项mipiP1*2 4 6 8 9 10 1mipiP2P3P4P5P62 4 6 10× ×× × × × × ×所需质蕴涵项产生表行消去规则：对于所需质蕴涵项产生表中的任意质蕴涵项pi和pj，若pi行中的“

”完全包含在pj行中，即pi

pj，则可消去pi行。这是因为选取了pj后不仅可以覆盖pi所能覆盖的最小项，而且还可覆盖其它最小项。列消去规则：对于所需质蕴涵项产生表中的任意最小项mi和mj，若mi列中的“

”完全包含在mj列中，即mi

mj，则可消去mj列。这是因为选取了覆盖mi的质蕴涵项后一定能覆盖mj，反之则不一定。所需质蕴涵项P3,P4（二次必要质蕴涵项）4.3组合电路设计（续）8/14/202346mipiP22 4 6 10× ×所需质蕴涵项产生表行消去4.4竞争与冒险竞争：信号从某一点出发经不同路径到达某一逻辑门有时间差的现象