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

学习要求： 掌握开关代数的基本概念，学会用逻辑函数描述逻 辑问题 掌握逻辑代数的公理、基本定理和重要规则 学会用卡诺图化简逻辑函数 第4章 逻辑代数基础 Date1 第4章 逻辑代数基础（续） 习题 完成下列练习: 5, 9bcde, 10abe, 13ac, 16abc, 19ace, 22ab, 29, 43, 46, 55abcd, 65, 66, 83. Date2 l 逻辑电路的分析、综合与设计 第4章 逻辑代数基础（续） l 分析：从逻辑图开始，得到该电路功能的形式描述，如真值表或逻 辑表达式。 l 综合：与分析相反，从形式描述开始，得到逻辑图。通常可由软件 来完成。 l 设计：从接受用户要求开始，得到逻辑图。 l 将实际问题的非形式描述（语言或想法）转换成形式描述，即定 义电路的输入、输出，并用真值表或表达式说明它的功能特性。 l 综合 l 组合逻辑电路 l 任一时刻的输出仅取决于当时的输入； l 可以含有任意数目的逻辑门电路和反相器，但不包括反馈回路。 Date3 l 公理（5条） 4.1 开关代数 l （A1）如果X1，则X0；（A1）如果X0，则X1。（ 开关变 量X的取值特性） l （A2）如果X0，则X1；（A2）如果X1，则X 0。（ 反相 器的功能特性） “与”和“或” 操作的特性 l （A3） 000 ； （A3） 111 l （A4） 111 ； （A4） 000 l （A5） 01100； （A5） 10011 Date4 4.1 开关代数（续） l 单变量定理 l 可用完备归纳法证明 Date5 4.1 开关代数（续） l 二变量和三变量定理 l 运算优先顺序 l 分配律 l 定理T9和T10广泛地用来简化逻辑函数。 l 在所有的定理中，可以用任意逻辑表达式来替换每个变量。 Date6 l n变量定理 4.1 开关代数（续） l 可用有限归纳法证明 例：证明 XX XX 1、当n2时，X+X=X （T3） 2、设当ni时，X+X+X=X 3、则当ni+1时， X+X+X+X=X+(X+X+X) （T7 ） =X+X =X Date7 l 德摩根定理 4.1 开关代数（续） + 0 1 原变量 反变量 F + 0 1 原变量 反变量 F Date8 l 德摩根定理（续） 4.1 开关代数（续） 使用广义德摩根定理时，要保持原逻辑表示式中运算符号的优先顺序不 变。 Date9 l 对偶性原理 l 对开关代数的任何定理或恒等式，若交换所有的0和1以及“”和“” ，结果仍正确。 4.1 开关代数（续） l 它使要学的东西减了一半！ Date10 4.1 开关代数（续） Date11 Date12 l 逻辑函数表示法 4.1 开关代数（续） 文字：变量或变量的补，如X、Y、X、 Y； 乘积项：单个文字或2个或2个以上文字的逻辑积，如 Z，WXY； “积之和”表达式：乘积项的逻辑和，如 ZWXY； 求和项：单个文字或2个或2个以上文字的逻辑和，如 Z，WXY； “和之积”表达式：求和项的逻辑积，如 Z( WXY)； 标准项：一个乘积项或求和项，其中每个变量只出现一次，如 WXY ，WXY； 非标准项：不是标准项的乘积项或求和项，如WXXY； Date13 最小项m：设一个逻辑函数有n个变量，则一个有n个文字的标准乘积 项称为一个最小项，共有2n个最小项。如4变量最小项m0: WXYZ， m13: WXYZ，m2: WXYZ； 4.1 开关代数（续） 最大项M：设一个逻辑函数有n个变量，则一个有n个文字的标准求和 项称为一个最大项，共有2n个最大项。如4变量最大项M15: WXY Z，M6: WXYZ，M13: WXYZ； Date14 1.真值表 ln个变量的真值表有2n行 4.1 开关代数（续） l 含有n个变量的函数有 个 Date15 2.最小项列表：F(X, Y, Z) = XYZ(0, 3, 4, 6, 7 ) 4.1 开关代数（续） 3.标准积之和式：F(X, Y, Z) =XYZ + XYZ +XYZ +XYZ +XYZ =XYZ+XYZ+XYZ+XYZ+XYZ+XYZ =YZ+XY+YZ Date16 4.最大项列表：F(X, Y, Z) = XYZ(1, 2, 5 ) 4.1 开关代数（续） 5.标准和之积式：F(X, Y, Z) = (X+Y+Z)(X+Y+Z)(X+Y+Z) Date17 l 从电路图得到逻辑函数的形式描述，如真值表、逻辑表达式 。 l 确定电路行为； l 根据代数描述提出逻辑函数的不同电路结构； l 交流与学习。 4.2 组合电路分析 l 穷举法 Date18 4.2 组合电路分析（续） l 代数法 F( (X + Y)Z) + (XYZ)=XZYZXYZ （乘开） Date19 4.2 组合电路分析（续） F( (X + Y )Z) + (XYZ ) (XYX )(XYY)(XYZ )(ZX )(ZY)(ZZ ) 11(XYZ )(XZ)(YZ)1 (XYZ)(XZ)(YZ) （加开） Date20 l 电路描述和设计 l 用真值表对电路进行描述，不容易出现错误，容易用标准和或标准 积表达式直接设计，但当变量数很多时表可能会很大。 4.3 组合电路综合 例：对一个4位素数检测器可作这样的描述：“对于4位输入组合N N3N2N1N0，当N1、2、3、5、7、11、1 3时，函数输出为1，其他情 况输出为0” Date21 l 用连接词“与”、“或”、“非”来描述逻辑函数（可以通过定义辅助变量 简化表达式），比写出完全真值表要容易些（当变量数很多时），但 容易出现错误。 4.3 组合电路设计（续） 例：描述一个报警电路：“当PANIC输入为1，或者当ENABLE输入为1、 EXITING输入为0，并且房子不安全时，ALARM输出为1；当WINDOW、 DOOR、和GARAGE输入都为1时，房子是安全的。” ALARM=PANIC+ENABLE EXITINGSECURE SECURE=WINDOW DOORGARAGE ALARM=PANIC+ENABLE EXITING (WINDOW DOOR GARAGE) Date22 l 电路处理 一般来说，与非门和或非门比与门和或门要快，但多数人不习惯用与 非和或非形式来描述逻辑命题。 4.3 组合电路设计（续） “如果你不整洁或不富有，并且也不聪明或不友好，我就不和你约会。” “如果你整洁且富有，或者你聪明且友好，我就和你约会。” 我们两人去或他 们两人去,一定能 解决这个问题? Date23 4.3 组合电路设计（续） 哪个电路工作速度最快？ Date24 4.3 组合电路设计（续） l 组合逻辑电路的简化：一般来说，逻辑函数表达式越简单，设计出来的 电路也就越简单。 例：化简 解： l 代数化简法：运用逻辑代数的公理、定理和规则对逻辑函数进行推导、 变换而进行化简。没有固定的步骤可以遵循，主要取决于对公理、定理和 规则的熟练掌握及灵活运用的程度。有时很难判定结果是否为最简。 7个门 3个门 2个门 Date25 4.3 组合电路设计（续） l “与或”式化简应满足的两个条件： l 表达式中“与项”的个数最少； l 在满足上面要求的前提下, “与项”中的变量总数最少。 l “或与”式化简应满足的两个条件： l 表达式中“或项”的个数最少； l 在满足上面要求的前提下, “或项”中的变量总数最少。 l 卡诺图化简法：该方法简单、直观、容易掌握，当变量个数小于等于6 时非常有效，在逻辑设计中得到广泛应用。 l 卡诺图的构成：n个变量的卡诺图是一种由2n个方格构成的图形，每 一个方格表示逻辑函数的一个最小项，所有的最小项巧妙地排列成一 种能清楚地反映它们相邻关系的方格阵列。一个函数可用图形中若干 方格构成的区域来表示。 Date26 mo m2 m1 m3 0 1 0 1 A B A B 0 1 0 1 二变量卡诺图 mo m2 m6 m4 m1 m3 m7 m5 00 01 11 10 0 1 AB C 00 01 11 10 0 1 AB C 三变量卡诺图 0 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 00 01 11 10 00 01 11 10 AB CD 00 01 11 10 00 01 11 10 AB CD 四变量卡诺图 Date27 4.3 组合电路设计（续） l 相邻最小项（或与项 ）：彼此只有一个变量不同，且这个不同变量互为反变 量的两个最小项（或与项）称为相邻最小项（或相邻与项），如ABC和ABC。 l 相邻最小项在卡诺图中有几何相邻、相对相邻和重叠相邻三种特征。 0 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 00 01 11 10 00 01 11 10 AB CD 00 01 11 10 00 01 11 10 AB CD 0 4 12 8 1 5 13 9 3 7 15 11 2 6 14 10 00 01 11 10 00 01 11 10 ABC DE 16 20 28 24 17 21 29 25 19 23 31 27 18 22 30 26 00 01 11 10 00 01 11 10 ABC DE Date28 4.3 组合电路设计（续） l 逻辑函数的卡诺图表示：将逻辑函数所对应的最小项在卡诺图的相应方 格中标以1，剩余方格标以0或不标。 l 其它形式的函数要转换成“与或”式后，再在卡诺图上表示。 l卡诺图的性质：根据T10有AB+AB=A，它表明两 个相邻“与项”或相邻“最 小项“可以合并为一项，这一项由两个“与项“中相同的变量组成，可以消去 两个 “与项“中不同的变量。 00 01 11 10 0 1 AB C 1 1111 例如： 可表示为： l “与或”式的卡诺图表示：直接将表达式的“与项”或“最小项”所对应 的方格标以1。 Date29 4.3 组合电路设计（续） l 卡诺圈：在卡诺图上把相邻最小项所对应的小方格“圈“在一起可进行合 并，以达到用一个简单“与项“代替若干最小项的目的。 0 1 0 1 A B 1 1 0 1 0 1 A B 1 1 0 1 0 1 A B 1 1 1 二变量卡诺图合并的典型情况 00 01 11 10 0 1 AB C 1 1 1 1 AB 00 01 11 10 0 1 C 1 1 1 1 1 1 1 1 0 1 AB C 00 01 11 10 三变量卡诺图合并的典型情况 Date30 4.3 组合电路设计（续） l 一个卡诺圈中的小方格满足以下规律： l 卡诺圈中的小方格的数目为2m，m为整数且mn； l 2m个小方格含有m个不同变量和(n-m)个相同变量； l 2m个小方格可用(n-m)个变量的“与项”表示，该“与项”由这 些最小项 中的相同变量构成； l 当m=n时，卡诺圈包围整个卡诺图，可用1表示，即n个变量的全部 最小项之和为1。 1 00 01 11 10 AB CD 11 1 11 11 四变量卡诺图合并的典型情况 00 01 11 10 Date31 4.3 组合电路设计（续） l 蕴涵项（如何画圈） l 蕴涵项：“与或”式中的每一个“与项”称为函数的蕴涵项。 l 质蕴涵项：不被其它蕴涵项所包含的蕴涵项。 l 必要质蕴涵项：质蕴涵项中至少有一个最小项不被其它蕴涵项所包 含。 Date32 4.3 组合电路设计（续） l 用卡诺图化简逻辑函数的一般步骤： l 第一步：作出函数的卡诺图； l 第二步：在卡诺图上圈出函数的全部质蕴涵项（画最大的卡诺圈） ； l 第三步：从全部质蕴涵项中找出所有必要质蕴涵项； l 第四步：若全部必要质蕴涵项尚不能覆盖所有的1 方格，则需从剩 余质蕴涵项中找出最简的所需质蕴涵项，使它们和必要质蕴涵项一起 构成函数的最小覆盖（把它们全部“或”起来）。 Date33 4.3 组合电路设计（续） 例：用卡诺图将下列逻辑函数简化为“与或”表达式 F(A, B, C, D)=m(0, 3, 5, 6, 7, 10, 11, 13, 15) 解： 1 00 01 11 10 00 01 11 10 AB CD 1 1 1 11 111 1 1 00 01 11 10 00 01 11 10 AB CD 1 1 11 111 1* 1* 00 01 11 10 00 01 11 10 AB CD 1 1* 1*1* 111* Date34 4.3 组合电路设计（续） 例：用卡诺图将下列逻辑函数简化为“与或”表达式 F(A, B, C, D)=m(2, 3, 6, 7, 8,10, 12) 解： 1 00 01 11 10 00 01 11 10 AB CD 1 11 11 1 1 00 01 11 10 00 01 11 10 AB CD 1* 1*1* 1 * 1 1 11 00 01 11 10 00 01 11 10 AB CD 1* 1*1* 1*1 11 00 01 11 10 00 01 11 10 AB CD 1* 1*1* 1*1 Date35 4.3 组合电路设计（续） 例：用卡诺图将下列逻辑函数简化为“或与”表达式 F(A, B, C, D)= M( 3, 4, 6, 7, 11, 12, 13, 14,15) 解： CD 1 00 01 11 10 00 01 11 10 AB 0 01 00 10 11 00 1 0 0 1 Date36 4.3 组合电路设计（续） l 没有必要质蕴涵项的情况 Date37 4.3 组合电路设计（续） 例：用卡诺图化简逻辑函数F(A, B, C, D)=m(2, 3, 4, 5, 6, 7, 11, 13, 15) 解： CD 00 01 11 10 00 01 11 10 AB 11 11 1 1 11 1 CD 0 00 01 11 10 00 01 11 10 AB 00 00 0 0 化简后得到的表达式一般为两级“与或式”或“或与式”，可分别由两级“与非门” 或“或非门”来实现，但实际上受扇入系数的影响，电路的级数会增加，影响电路的 速度。为不降低速度，人们设计出更复杂的门来取代简单门完成更复杂的运算。 ?有问题 Date38 4.3 组合电路设计（续） l 包含无关最小项的逻辑函数的化简 l 一般来说，逻辑函数与输入的每一种取值组合均有关系。对于某些 组合（某些最小项）函数的值为0，而对另外一些组合（另外一些最 小项）函数取值为1。 l 无关最小项：一个逻辑函数, 如果它的某些输入取值组合因受特殊 原因制约而不会再现，或者虽然每种输入取值组合都可能出现，但此 时函数取值为1还是为0无关紧要，那么这些输入取值组合所对应的最 小项称为无关最小项。 l 无关最小项可以随意地加到函数表达式中，或者不加到函数表达式 中，并不影响函数所对应逻辑电路的实际逻辑功能。 Date39 4.3 组合电路设计（续） 例：给定某电路的真值表如下，求F的最简“与或“式。 1 00 01 11 10 00 01 11 10 AB CD 1 1 1 1 1 1 1 00 01 11 10 00 01 11 10 AB CD 1 1 1 1 d d dd d d A B C D F 0 0 0 0 d 0 0 0 1 d 0 0 1 0 d 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 d 1 1 1 0 d 1 1 1 1 d Date40 从多输出函数化简的观点来看，它们不是最佳的，应该是： 1 00 01 11 10 0 1 AB C 1 1 F1 1 00 01 11 10 0 1 AB C 1 1 F2 例：多输出函数 对应的卡诺图为： 4.3 组合电路设计（续） l 多输出逻辑函数的化简：如果孤立地将单个输出一一化简，然后直接拼 在一起，通常并不能保证整个电路最简。 l 所有逻辑表达式包含的不同“与项”总数最小； l 在满足上述条件的前提下，各不同“与项“中所含的变量总数最少。 注意红色项 ！ Date41 4.3 组合电路设计（续） l 列表化简法(Q-M法) l 第一步：将函数表示成“最小项之和”形式，并用二进制编码表示每一 个最小项； l 第二步：找出函数的全部质蕴涵项； l 第三步：找出函数的全部必要质蕴涵项； l 第四步：找出函数全部所需质蕴涵项 。 l 最小化“积之和”=必要质蕴涵项+所需质蕴涵项 Date42 4.3 组合电路设计（续） (I)最小项(II)(n1)个变量的“与”项(III)(n2)个变量的“与”项 编号 miABCD 组号mi miABCD Pi ABCDPi 0 1 2 3 4 0000 1000 0101 1001 1010 0111 1011 1110 1111 0 8 5 9 10 7 11 14 15 0 1 2 3 0,8 8,9 8,10 5,7 9,11 10,11 10,14 7,15 11,15 14,15 000 100 100 011 101 101 110 111 111 111 1 2 8,9,10,11 10,11,14,15 10 11 组号Pi p1 p5 p4 p3 p2 例：用列表法化简 F(A, B, C, D)m(0, 5, 7, 8, 9, 10, 11, 14, 15) 解：1、用二进制编码表示函数中的每一个最小项； 质蕴涵项产生表 2、找出函数的全部质蕴涵项； Date43 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)BCD mi pi P1* P2* P3 P4* P5* 057891011 14 15 覆盖情况 必要质蕴涵项产生表3、求必要质蕴涵项 F(A, B, C, D)AC+ AB+ ABD+ BCD Date44 4、求所需质蕴涵项 mi pi P1* P2 P3 P4 P5 P6 P7* 246891012 13 15 覆盖情况 4.3 组合电路设计（续） Date45 mi pi P2 P3 P4 P5 P6 24610 所 需 质 蕴 涵 项 产 生 表 行消去规则：对于所需质蕴涵项产生表中的任意质蕴涵项pi和pj，若pi行中的“ ” 完全包含在pj行中，即pi pj ，则可消去pi行。这是因为选取了pj后不仅可以覆盖pi 所能覆盖的最小项，而且还可覆盖其它最小项。 列消去规则：对于所需质蕴涵项产生表中的任意最小项mi和mj，若mi列中的“ ” 完全包含在mj列中，即mi mj ，则可消去mj列。这是因为选取了覆盖mi的质蕴涵 项后一定能覆盖mj，反之则不一定。 所需质蕴涵项P3, P4（ 二次必要质蕴涵项） 4.3 组合电路设计（续） Date46 4.4 竞争与冒险 l 竞争：信号从某一点出发经不同路径到达某一逻辑门有时间差的现象。 A F d e g tpd 21 电路在时间“1”和“2”出现