组合逻辑设计原理课件.ppt

1、2022-6-91学习要求：学习要求： 掌握开关代数的基本概念，学会用逻辑函数描述掌握开关代数的基本概念，学会用逻辑函数描述逻辑问题逻辑问题 掌握逻辑代数的公理、基本定理和重要规则掌握逻辑代数的公理、基本定理和重要规则 学会用卡诺图化简逻辑函数学会用卡诺图化简逻辑函数第第4 4章章 逻辑代数基础逻辑代数基础2022-6-92第第4 4章章 逻辑代数基础（续）逻辑代数基础（续）习题习题 完成下列练习完成下列练习:5, 9bcde, 10abe, 13ac, 16abc, 19ace, 22ab, 29, 43, 46, 55abcd, 65, 66, 83.2022-6-93l 逻辑电路的分析、

2、综合与设计第第4 4章章 逻辑代数基础（续）逻辑代数基础（续）l 分析：从逻辑图开始，得到该电路功能的形式描述，如真值表或逻辑表达式。l 综合：与分析相反，从形式描述开始，得到逻辑图。通常可由软件来完成。l 设计：从接受用户要求开始，得到逻辑图。l 将实际问题的非形式描述（语言或想法）转换成形式描述，即定义电路的输入、输出，并用真值表或表达式说明它的功能特性。l 综合l 组合逻辑电路l 任一时刻的输出仅取决于当时的输入；l 可以含有任意数目的逻辑门电路和反相器，但不包括反馈回路。2022-6-94l 公理（5条）4.1 4.1 开关代数开关代数l （A1）如果X1，则X0；（A1）如果X0，则

3、X1。（ 开关变量X的取值特性）l （A2）如果X0，则X1；（A2）如果X1，则X 0。（ 反相器的功能特性）“与”和“或”操作的特性l （A3） 000 ； （A3） 111l （A4） 111 ； （A4） 000l （A5） 01100； （A5） 100112022-6-954.1 4.1 开关代数（续）开关代数（续）l 单变量定理l 可用完备归纳法证明2022-6-964.1 4.1 开关代数（续）开关代数（续）l 二变量和三变量定理l 运算优先顺序l 分配律l 定理T9和T10广泛地用来简化逻辑函数。l 在所有的定理中，可以用任意逻辑表达式来替换每个变量。2022-6-97l n

4、变量定理4.1 4.1 开关代数（续）开关代数（续）l 可用有限归纳法证明例：证明 XX XX 1、当n2时，X+X=X （T3） 2、设当ni时，X+X+X=X3、则当ni+1时， X+X+X+X=X+(X+X+X) （T7）=X+X=X2022-6-98l 德摩根定理4.1 4.1 开关代数（续）开关代数（续）+01原变量反变量F+01原变量反变量F2022-6-99l 德摩根定理（续）4.1 4.1 开关代数（续）开关代数（续）使用广义德摩根定理时，要保持原逻辑表示式中运算符号的优先顺序不变。EDCBAFEDCBAF 2022-6-910l 对偶性原理l 对开关代数的任何定理或恒等式，若

5、交换所有的0和1以及“”和“”，结果仍正确。4.1 4.1 开关代数（续）开关代数（续）l 它使要学的东西减了一半！2022-6-9114.1 4.1 开关代数（续）开关代数（续）2022-6-9122022-6-913l 逻辑函数表示法4.1 4.1 开关代数（续）开关代数（续） 文字：变量或变量的补，如X、Y、X、 Y； 乘积项：单个文字或2个或2个以上文字的逻辑积，如 Z，WXY； “积之和”表达式：乘积项的逻辑和，如 ZWXY； 求和项：单个文字或2个或2个以上文字的逻辑和，如 Z，WXY； “和之积”表达式：求和项的逻辑积，如 Z( WXY)； 标准项：一个乘积项或求和项，其中每个变

6、量只出现一次，如 WXY，WXY；非标准项：不是标准项的乘积项或求和项，如WXXY；2022-6-914 最小项m：设一个逻辑函数有n个变量，则一个有n个文字的标准乘积项称为一个最小项，共有2n个最小项。如4变量最小项m0: WXYZ，m13: WXYZ，m2: WXYZ；4.1 4.1 开关代数（续）开关代数（续） 最大项M：设一个逻辑函数有n个变量，则一个有n个文字的标准求和项称为一个最大项，共有2n个最大项。如4变量最大项M15: WXYZ，M6: WXYZ，M13: WXYZ；2022-6-9151.真值表l n个变量的真值表有2n行4.1 4.1 开关代数（续）开关代数（续）l 含有

7、n个变量的函数有 个n222022-6-9162.最小项列表：F(X, Y, Z) = XYZ(0, 3, 4, 6, 7 )4.1 4.1 开关代数（续）开关代数（续）3.标准积之和式：F(X, Y, Z) =XYZ + XYZ +XYZ +XYZ +XYZ =XYZ+XYZ+XYZ+XYZ+XYZ+XYZ =YZ+XY+YZ2022-6-9174.最大项列表：F(X, Y, Z) = XYZ(1, 2, 5 )4.1 4.1 开关代数（续）开关代数（续）5.标准和之积式：F(X, Y, Z) = (X+Y+Z)(X+Y+Z)(X+Y+Z)XYZXYZZYXF)5 , 2 , 1 ()7 ,

8、 6 , 4 , 3 , 0(),(2022-6-918l 从电路图得到逻辑函数的形式描述，如真值表、逻辑表达式。l 确定电路行为；l 根据代数描述提出逻辑函数的不同电路结构；l 交流与学习。4.2 4.2 组合电路分析组合电路分析l 穷举法2022-6-9194.2 4.2 组合电路分析（续）组合电路分析（续）l 代数法F( (X + Y)Z) + (XYZ)=XZYZXYZ （乘开）2022-6-9204.2 4.2 组合电路分析（续）组合电路分析（续） F( (X + Y )Z) + (XYZ ) (XYX )(XYY)(XYZ )(ZX )(ZY)(ZZ ) 11(XYZ )(XZ)(

9、YZ)1 (XYZ)(XZ)(YZ) （加开）2022-6-921l 电路描述和设计l 用真值表对电路进行描述，不容易出现错误，容易用标准和或标准积表达式直接设计，但当变量数很多时表可能会很大。4.3 4.3 组合电路综合组合电路综合例：对一个4位素数检测器可作这样的描述：“对于4位输入组合NN3N2N1N0，当N1、2、3、5、7、11、1 3时，函数输出为1，其他情况输出为0”2022-6-922l 用连接词“与”、“或”、“非”来描述逻辑函数（可以通过定义辅助变量简化表达式），比写出完全真值表要容易些（当变量数很多时），但容易出现错误。4.3 4.3 组合电路设计组合电路设计（续）（续）

10、例：描述一个报警电路：“当PANIC输入为1，或者当ENABLE输入为1、EXITING输入为0，并且房子不安全时，ALARM输出为1；当WINDOW、DOOR、和GARAGE输入都为1时，房子是安全的。”ALARM=PANIC+ENABLE EXITINGSECURESECURE=WINDOW DOORGARAGEALARM=PANIC+ENABLE EXITING (WINDOW DOOR GARAGE)2022-6-923l 电路处理一般来说，与非门和或非门比与门和或门要快，但多数人不习惯用与非和或非形式来描述逻辑命题。 4.3 4.3 组合电路设计组合电路设计（续）（续）“如果你不整洁

11、或不富有，并且也不聪明或不友好，我就不和你约会。”“如果你整洁且富有，或者你聪明且友好，我就和你约会。”我们两人去或他我们两人去或他们两人去们两人去,一定能一定能解决这个问题解决这个问题?2022-6-9244.3 4.3 组合电路设计组合电路设计（续）（续）哪个电路工作速度最快？2022-6-9254.3 4.3 组合电路设计组合电路设计（续）（续）l 组合逻辑电路的简化：一般来说，逻辑函数表达式越简单，设计出来的电路也就越简单。CDDACABCCAF例：化简解：CDACDABACDACABCADDDACCCBCADDACBCCAF)()()()(l 代数化简法：运用逻辑代数的公理、定理和规

12、则对逻辑函数进行推导、变换而进行化简。没有固定的步骤可以遵循，主要取决于对公理、定理和规则的熟练掌握及灵活运用的程度。有时很难判定结果是否为最简。7个门3个门2个门2022-6-9264.3 4.3 组合电路设计组合电路设计（续）（续）l “与或”式化简应满足的两个条件：l 表达式中“与项”的个数最少；l 在满足上面要求的前提下, “与项”中的变量总数最少。l “或与”式化简应满足的两个条件：l 表达式中“或项”的个数最少；l 在满足上面要求的前提下, “或项”中的变量总数最少。l 卡诺图化简法：该方法简单、直观、容易掌握，当变量个数小于等于6时非常有效，在逻辑设计中得到广泛应用。l 卡诺图的

13、构成：n个变量的卡诺图是一种由2n个方格构成的图形，每一个方格表示逻辑函数的一个最小项，所有的最小项巧妙地排列成一种能清楚地反映它们相邻关系的方格阵列。一个函数可用图形中若干方格构成的区域来表示。2022-6-927mo m2m1 m3 0 101ABAB 0 101BA BABA ABBBAA二变量卡诺图mo m2 m6 m4m1 m3 m7 m500 01 11 1001ABC00 01 11 1001ABCCBA CBACABCBA CBA BCAABCCBA AACCBBB三变量卡诺图 0 4 12 8 1 5 13 9 3 7 15 11 2 6 14 1000 01 11 1000

14、011110ABCD00 01 11 1000011110ABCDDCBA ACDCBA DCBA DCBA DCBA DCBA DCBA DCBA DCBA DCBA ABCDCDBADCBA DCBA DABCDCBADB四变量卡诺图2022-6-9284.3 4.3 组合电路设计组合电路设计（续）（续）l 相邻最小项（或与项 ）：彼此只有一个变量不同，且这个不同变量互为反变量的两个最小项（或与项）称为相邻最小项（或相邻与项），如ABC和ABC。l 相邻最小项在卡诺图中有几何相邻、相对相邻和重叠相邻三种特征。 0 4 12 8 1 5 13 9 3 7 15 11 2 6 14 1000

15、01 11 1000011110ABCD00 01 11 1000011110ABCDDCBA ACDCBA DCBA DCBA DCBA DCBA DCBA DCBA DCBA DCBA ABCDCDBADCBA DCBA DABCDCBADB 0 4 12 8 1 5 13 9 3 7 15 11 2 6 14 1000 01 11 1000011110ABCDE 16 20 28 24 17 21 29 25 19 23 31 27 18 22 30 2600 01 11 1000011110ABCDEA2022-6-9294.3 4.3 组合电路设计组合电路设计（续）（续）l 逻辑函数

16、的卡诺图表示：将逻辑函数所对应的最小项在卡诺图的相应方格中标以1，剩余方格标以0或不标。l 其它形式的函数要转换成“与或”式后，再在卡诺图上表示。l卡诺图的性质：根据T10有AB+AB=A，它表明两 个相邻“与项”或相邻最小项可以合并为一项，这一项由两个与项中相同的变量组成，可以消去两个 与项中不同的变量。00 01 11 1001ABC11111例如： 可表示为：CBABCBACACBAF),(l “与或”式的卡诺图表示：直接将表达式的“与项”或“最小项”所对应的方格标以1。2022-6-9304.3 4.3 组合电路设计组合电路设计（续）（续）l 卡诺圈：在卡诺图上把相邻最小项所对应的小方

17、格圈在一起可进行合并，以达到用一个简单与项代替若干最小项的目的。 0 101AB1 1 0 101AB1 1 0 101AB1 11二变量卡诺图合并的典型情况00 01 11 1001ABC1 11 1AB 00 01 11 1001C1 1 1 11 1 1 101ABC00 01 11 10三变量卡诺图合并的典型情况2022-6-9314.3 4.3 组合电路设计组合电路设计（续）（续）l 一个卡诺圈中的小方格满足以下规律：l 卡诺圈中的小方格的数目为2m，m为整数且mn；l 2m个小方格含有m个不同变量和(n-m)个相同变量；l 2m个小方格可用(n-m)个变量的“与项”表示，该“与项”

18、由这 些最小项中的相同变量构成；l 当m=n时，卡诺圈包围整个卡诺图，可用1表示，即n个变量的全部最小项之和为1。100011110ABCD1111111四变量卡诺图合并的典型情况00 01 11 102022-6-9324.3 4.3 组合电路设计组合电路设计（续）（续）l 蕴涵项（如何画圈）l 蕴涵项：“与或”式中的每一个“与项”称为函数的蕴涵项。l 质蕴涵项：不被其它蕴涵项所包含的蕴涵项。l 必要质蕴涵项：质蕴涵项中至少有一个最小项不被其它蕴涵项所包含。2022-6-9334.3 4.3 组合电路设计组合电路设计（续）（续）l 用卡诺图化简逻辑函数的一般步骤：l 第一步：作出函数的卡诺图

19、；l 第二步：在卡诺图上圈出函数的全部质蕴涵项（画最大的卡诺圈）；l 第三步：从全部质蕴涵项中找出所有必要质蕴涵项；l 第四步：若全部必要质蕴涵项尚不能覆盖所有的1 方格，则需从剩余质蕴涵项中找出最简的所需质蕴涵项，使它们和必要质蕴涵项一起构成函数的最小覆盖（把它们全部“或”起来）。2022-6-9344.3 4.3 组合电路设计组合电路设计（续）（续）例：用卡诺图将下列逻辑函数简化为“与或”表达式 F(A, B, C, D)=m(0, 3, 5, 6, 7, 10, 11, 13, 15)解：100 01 11 1000011110ABCD11111111)()()()()(),( CBAB

20、CACDBDDCBACBABCACDBDDCBADCBAF1100 01 11 1000011110ABCD11111111*1*00 01 11 1000011110ABCD11*1*1*111*2022-6-9354.3 4.3 组合电路设计组合电路设计（续）（续）例：用卡诺图将下列逻辑函数简化为“与或”表达式 F(A, B, C, D)=m(2, 3, 6, 7, 8,10, 12)解：100 01 11 1000011110ABCD111111100 01 11 1000011110ABCD1*1*1*1 *111100 01 11 1000011110ABCD1*1*1*1*1DBA

21、DCACADCBAF),(DCBDCACADCBAF),( 或1100 01 11 1000011110ABCD1*1*1*1*12022-6-9364.3 4.3 组合电路设计组合电路设计（续）（续）例：用卡诺图将下列逻辑函数简化为“或与”表达式 F(A, B, C, D)= M( 3, 4, 6, 7, 11, 12, 13, 14,15) 解：)()()()()()(),(),( DBBADCDBBADCDBABCDDCBAFDBABCDDCBAFCD100 01 11 1000011110AB001001011001001 )10, 9 , 8 , 5 , 2 , 1 , 0()()(

22、) )15,14,13,12,11, 7 , 6 , 4 , 3(),(1514131211764315141312117643mmmmmmmmmmMMMMMMMMMMDCBAF2022-6-9374.3 4.3 组合电路设计组合电路设计（续）（续）l 没有必要质蕴涵项的情况2022-6-9384.3 4.3 组合电路设计组合电路设计（续）（续）例：用卡诺图化简逻辑函数F(A, B, C, D)=m(2, 3, 4, 5, 6, 7, 11, 13, 15)解：CDBDBACADCBAF),(CD00 01 11 1000011110AB111111111CD000 01 11 1000011

23、110AB000000)(),(),(DACBCCBAFDACBDCBAF 化简后得到的表达式一般为两级“与或式”或“或与式”，可分别由两级“与非门”或“或非门”来实现，但实际上受扇入系数的影响，电路的级数会增加，影响电路的速度。为不降低速度，人们设计出更复杂的门来取代简单门完成更复杂的运算。?有问题有问题2022-6-9394.3 4.3 组合电路设计组合电路设计（续）（续）l 包含无关最小项的逻辑函数的化简l 一般来说，逻辑函数与输入的每一种取值组合均有关系。对于某些组合（某些最小项）函数的值为0，而对另外一些组合（另外一些最小项）函数取值为1。l 无关最小项：一个逻辑函数, 如果它的某些

24、输入取值组合因受特殊原因制约而不会再现，或者虽然每种输入取值组合都可能出现，但此时函数取值为1还是为0无关紧要，那么这些输入取值组合所对应的最小项称为无关最小项。l 无关最小项可以随意地加到函数表达式中，或者不加到函数表达式中，并不影响函数所对应逻辑电路的实际逻辑功能。2022-6-9404.3 4.3 组合电路设计组合电路设计（续）（续）例：给定某电路的真值表如下，求F的最简与或式。100 01 11 1000011110ABCD11111CBACDBDCBCBADCBAF),(1100 01 11 1000011110ABCD1111ddddddCBCBDCBAF),(A B C D F0

25、 0 0 0 d0 0 0 1 d0 0 1 0 d0 0 1 1 10 1 0 0 10 1 0 1 10 1 1 0 00 1 1 1 01 0 0 0 01 0 0 1 01 0 1 0 11 0 1 1 11 1 0 0 11 1 0 1 d1 1 1 0 d1 1 1 1 d2022-6-941从多输出函数化简的观点来看，它们不是最佳的，应该是： ,),(,),(21CABBCCBAFCABBACBAF100 01 11 1001ABC1 1F1100 01 11 1001ABC1 1F2例：多输出函数 对应的卡诺图为：BCABCBAFCABACBAF),(,),(214.3 4.3

26、 组合电路设计组合电路设计（续）（续）l 多输出逻辑函数的化简：如果孤立地将单个输出一一化简，然后直接拼在一起，通常并不能保证整个电路最简。l 所有逻辑表达式包含的不同“与项”总数最小；l 在满足上述条件的前提下，各不同与项中所含的变量总数最少。注意红色项！注意红色项！2022-6-9424.3 4.3 组合电路设计组合电路设计（续）（续）l 列表化简法(Q-M法)l 第一步：将函数表示成“最小项之和”形式，并用二进制编码表示每一个最小项；l 第二步：找出函数的全部质蕴涵项；l 第三步：找出函数的全部必要质蕴涵项；l 第四步：找出函数全部所需质蕴涵项 。l 最小化“积之和”=必要质蕴涵项+所需

27、质蕴涵项2022-6-9434.3 4.3 组合电路设计组合电路设计（续）（续）(I)最小项(II)(n1)个变量的“与”项 (III)(n2)个变量的“与”项编号miABCD组号mimiABCDPiABCDPi01234000010000101100110100111101111101111085910711141501230,88,98,105,79,1110,1110,147,1511,1514,15000100100011101101110111111111128,9,10,1110,11,14,151011组号Pip1p5p4p3p2例：用列表法化简 F(A, B, C, D)m(0

28、, 5, 7, 8, 9, 10, 11, 14, 15)解：1、用二进制编码表示函数中的每一个最小项；质蕴涵项产生表质蕴涵项产生表 2、找出函数的全部质蕴涵项；2022-6-9444.3 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)ABD P5 = m(0, 8)BCDmipiP1*P2*P3P4*P5*057891011 14 15 覆盖情况必要质蕴涵项产生表必要质蕴涵项产生表3、求必要质蕴涵项F(A, B, C, D)AC+ AB+ A

29、BD+ BCD2022-6-9454、求所需质蕴涵项mipiP1*P2P3P4P5P6P7*246891012 13 15 覆盖情况4.3 4.3 组合电路设计组合电路设计（续）（续）2022-6-946mipiP2P3P4P5P624610 所所需需质质蕴蕴涵涵项项产产生生表表行消去规则：对于所需质蕴涵项产生表中的任意质蕴涵项pi和pj，若pi行中的“ ”完全包含在pj行中，即pi pj ，则可消去pi行。这是因为选取了pj后不仅可以覆盖pi所能覆盖的最小项，而且还可覆盖其它最小项。列消去规则：对于所需质蕴涵项产生表中的任意最小项mi和mj，若mi列中的“ ”完全包含在mj列中，即mi mj

30、 ，则可消去mj列。这是因为选取了覆盖mi的质蕴涵项后一定能覆盖mj，反之则不一定。所需质蕴涵项所需质蕴涵项P3, P4（二次必要质蕴涵项）（二次必要质蕴涵项）4.3 4.3 组合电路设计组合电路设计（续）（续）2022-6-9474.4 4.4 竞争与冒险竞争与冒险l 竞争：信号从某一点出发经不同路径到达某一逻辑门有时间差的现象。AFdegtpd21电路在时间“1”和“2”出现了竞争，并在时间“2”产生了冒险。l 冒险：当输入由某一种取值组合变为另一种取值组合时，由于竞争使得电路产生了与稳态输出不同的、暂时的错误输出。注意：竞争和冒险是电路的属性，逻辑函数不存在这样的问题。当B=C=1时F=

31、1 例如：F=AB+AC1&BCAF&1dgeG1G2G3G42022-6-9484.4 4.4 竞争与冒险（续竞争与冒险（续）l 按输入变化前后输出是否相等分为静态和动态冒险； 按错误输出的极性分为0型和1型冒险，故有静态0型, 静态1型, 动态0型, 动态1型4种情况。静态1型动态1型静态0型动态0型输入变化前的输出输入变化后的输出2022-6-9494.4 4.4 竞争与冒险（续竞争与冒险（续）l 冒险的判断l 代数法：检查是否存在某个变量X，它同时以原变量和反变量的形式出现在函数表达式中，而且表达式在一定条件下可变成X+X或者XX 的形式，若能则说明与函数表达式对应的电路可能产生冒险。

32、解：变量A和C具备竞争的条件，应分别进行检查。 C发生变化时不会产生险象.11100100ABABABABCFCFFCF1 检查C：例：试判断电路 是否可能产生冒险。ACBACAF2022-6-9504.4 4.4 竞争与冒险（续竞争与冒险（续） 检查A：11100100BCBCBCBCAAFAFAFAF 当B=C=1时，A的变化可能使电路产生冒险。l 卡诺图法：当描述电路的逻辑函数为“与或”式时，可采用卡诺图来判断电路是否存在冒险，其方法是观察是否存在“相切”的卡诺圈，若存在则会产生冒险。例：00 01 11 1000011110ABCD11111111CABCADAF2022-6-9514.4 4.4 竞争与冒险（续竞争与冒险（续）l 用增加冗余项的方法消除冒险利用定理T11（XYXZYZXYXZ）在原表达式中加上多余的“与项”或者乘以多余的“或项”，使原函数不可能在任何条件下出现X+X或者XX的形式，从而消除冒险。例：用增加冗余项的方法消除电路F=AB+AC中的冒险。解：增加冗余项BC，则有F=AB+AC +BC。当B=C=1时, 函数由FA+A变成了F1。1100 01 11 1001ABC1 1BBAC&1&1F