第一章 逻辑代数基础 本章的重点： 本章的难点： 1．逻辑代数的基本公式和常用公式。 2．逻辑代数的基本定理。 3．逻辑函数的各种表示方法。

Presentation on theme: "第一章 逻辑代数基础 本章的重点： 本章的难点： 1．逻辑代数的基本公式和常用公式。 2．逻辑代数的基本定理。 3．逻辑函数的各种表示方法。"— Presentation transcript:

1 第一章 逻辑代数基础 本章的重点： 本章的难点： 1．逻辑代数的基本公式和常用公式。 2．逻辑代数的基本定理。 3．逻辑函数的各种表示方法。
4．逻辑函数的化简方法。 5．约束项、任意项、无关项的概论以及无关项在化简逻辑函数中的应用。 6．“最小项”和“任何一个逻辑函数式都有可以化为最小项之和形式”是两个非常重要的概念，在逻辑函数的化简和变换中经常用到。 本章的难点： 稍微难理解一点的是约束、任意项、无关项这几个概念。

2 第一章 逻辑代数基础 第一节 概述 逻辑代数的产生：
1849年英国数学家乔治.布尔(George Boole)首先提出，用来描述客观事务逻辑关系的数学方法——称为布尔代数。 后来被广泛用于开关电路和数字逻辑电路的分析与设计，所以也称为开关代数或逻辑代数。 逻辑代数中用字母表示变量——逻辑变量，每个逻辑变量的取值只有两种可能——0和1。它们也是逻辑代数中仅有的两个常数。0和1只表示两种不同的逻辑状态，不表示数量大小。

3 第二节 逻辑代数的三种基本运算 A B Y 1 A B Y A & Y B 只有输入全为1时，输出才为1 三种基本运算是：与、或、非（反）。
它们都有集成门电路与之对应。 A B Y 1 1.与运算 可用开关图来说明： A B Y 该图代表的逻辑关系是：决定事件的全部条件都满足时，事件才发生——这就是与逻辑关系。 在函数式中，用. 表示与运算，记做 Y=A.B 或Y=AB 逻辑符号： 用1表示开关接通，1表示灯亮，可得如下真值表： A B Y A & Y B

4 + A B Y 1 A A B Y Y B 2.或运算 输入有一个为1时，输出就为1 A B Y 真值表
1 该图代表的逻辑关系是：决定事件的全部条件至少有一个满足时，事件就发生——这就是或逻辑关系。 在函数式中，用＋ 表示或运算，记做 逻辑符号： Y=A＋B A A B Y + 1 Y B

5 A Y 1 A B Y A A 3.非门 真值表 R Y A 在函数式中，用_ 表示非运算，记做
1 在函数式中，用_ 表示非运算，记做 该图代表的逻辑关系是：决定事件的条件满足时，事件不发生——这就是非逻辑关系。 Y=A 国外符号： 逻辑符号： A B Y 与门 非门 或门 A Y 1 A Y

6 用两个以上基本运算构成的逻辑运算。包括与非、或非、与或非、异或和同或运算。和三个基本运算一样，它们都有集成门电路与之对应。
4.一些常用的复合逻辑运算 用两个以上基本运算构成的逻辑运算。包括与非、或非、与或非、异或和同或运算。和三个基本运算一样，它们都有集成门电路与之对应。 互为非逻辑关系 真值表：(除与或非运算外） 1 1 1 1 0 0 1 0 0 A B A B A+B AB A B 逻辑符号： & =1 = A B Y Y B A 国外符号：

7 Y=AB+AB Y=A B + A B & A B C D Y 异或的逻辑式： 同或的逻辑式： A B C D 与或非逻辑 函数式形如：
1 Y=AB+AB Y=A B + A B 与或非逻辑 函数式形如： Y= AB + CD A与B等于1，或者C与D等于1，Y等于0。 真值表： 逻辑符号： & A B C D Y

8 第三节 逻辑代数的基本公式和常用公式 0.A=0 1+A=1 1.A=A 0+A=A A.A=A A+A=A A.A=0 A+A=1 A=A
一、基本公式 关于常数之间的运算在真值表中已给出。下面的公式中都有变量： ＋ 0.A=0 1+A=1 1.A=A 0+A=A A.A=A A+A=A 重叠律 A.A=0 A+A=1 互补律 还原律 A=A A.B=B.A 交换律 A＋B=B＋A A.(B.C )=(A.B).C 结合律 A＋(B＋C)=(A＋B)+C A.(B+C )=A.B+AC 分配律 A＋BC=(A＋B)(A+C) 摩根定理 A＋B=A.B A.B=A+B 我们用真值表证明分配律的第二个公式：

9 A＋BC=(A＋B)(A+C) A B C B.C A+ BC A+B A+C (A+B)(A+C) 0 0 0 0 0 1 1 0 1 0
1 其他公式的证明请同学自己完成。

10 A + AB = A A + AB = A+B A B+AB = A A B+AC+BC = AB+AC =AB+AC+ABC+ABC=右
二、若干常用公式 A + AB = A 吸收律1 证：左＝A(1+B)=A .1=A 证：左＝ (A+A)(A+B)=A+B A + AB = A+B 吸收律2 证：左＝A(B+B)=A .1=A A B+AB = A A B+AC+BC = AB+AC 冗余项定理 证： 左＝ A B+AC+BC(A+A) =AB+AC+ABC+ABC=右 推论： A B+AC+BCD = AB+AC A AB =A B A AB =A A B+AC =A B+A C 证： 左＝AB A C 摩根定理 =(A+B)(A+C) =A B+AC+B C =右

11 第四节 逻辑代数的基本定理 A.B=A+B B用C.D代入，有 A.B=A.CD =A+CD=A+C+D
一、代入定理 定理：在任何一个包含逻辑变量A的等式中，若以另外一个逻辑式代入式中所有A的位置，则等式仍然成立。 例如：将摩根定理 中 A.B=A+B B用C.D代入，有 A.B=A.CD =A+CD=A+C+D 上式说明摩根定理可推广到3个变量。当然也可推广到任意个变量。 二、反演定理 定理： 对于任意一个逻辑式Y，若将其中所有的 和＋交换， 和1交换，原变量和反变量交换， 得到的结果就是Y。 注：称A为原变量，A为反变量。 该定理可简单记为： ， ，A A 。

12 注意事项： 1.逻辑运算的优先顺序：括号，与，或, 异或。 2.多个变量上的非号的处理：可保持不变；也可用代入法处理。 例如： 已知：Y=A(B+C)+ CD 则： Y=(A + B C) C+D =(A + B C) CD = A CD 或者，令E=CD 代入上式 Y=(A + B C) E 所以： Y=(A + B C) CD

13 Z=AB+AC =(A+B)(A+C) = 即 A+BC=(A+B)(A+C) 三、对偶定理 对偶式的定义：
定义： 对于任意一个逻辑式Y，若将其中所有的 和＋交换，0和1交换，得到的结果就是Y的对偶式，记做 。 很明显Y 也是 的对偶式。 例如： Y=A(B+C) =A+BC Z=AB+AC =(A+B)(A+C) 对偶定理：若两逻辑式相等，则它们的对偶式也相等。 在上面的例子中，根据分配律 Y=Z，再根据对偶定理有： = 即 A+BC=(A+B)(A+C) 这就从分配律的第一个公式直接推出第二个公式。 从对偶定理可看出，只要一个逻辑函数式的变量数不少于两个（含反变量），它就一定存在对偶式。

14 第五节 逻辑函数及其表示方法 Y=A(B+C) 一、逻辑函数 事务间的因果关系是一种逻辑关系，可用逻辑函数表示。
如：前面介绍的灯与开关间的逻辑关系。 又如举重裁判的例子：设有三个裁判，分别用A,B,C表示，其中A是主裁判。规定至少有两个裁判确认（其中必须包含主裁判）时，运动员的试举才算成功。当用Y表示举重结果时，Y与A,B,C的逻辑关系可表示为： Y=A(B+C) 这就是一个逻辑函数的例子。 又如，三变量多数表决逻辑。也是逻辑函数的例子。 二、逻辑函数的表示方法 常用的有四种： 真值表；逻辑函数式；逻辑图；卡诺图。

15 本节介绍前三种，将卡诺图留在下节介绍。 A B C Y 1 1.真值表 左侧是输入变量的所有取值，右侧是输出变量的值，即函数值。 举重裁判的真值表： 当输入变量个数为n时，真值表共有2n行。 特点： 描述逻辑问题方便； 直观； 较繁琐。 2.函数式 举重裁判的函数式：Y=A(B+C) 特点： 便于运算、化简； 便于画逻辑图； 不便从逻辑问题直接得到。

16 A & Y B C 3.逻辑图 举重裁判函数的逻辑图： 特点： 便于用电路实现。 4.各种表示方法间的相互转换 Y=A(B+C) 真值表
函数式 逻辑图 黑箭头容易实现。篮箭头不能直接实现，可借助函数式实现。下面要重点介绍红箭头，即由真值表求函数式。 三、逻辑函数的两种标准形式 逻辑函数的两种标准形式分别是与或式和或与式，我们重点 介绍与或式。首先，介绍最小项和最大项。

17 （一）最小项和最大项 我们只介绍最小项。最大项留给同学自己看。 m7 7 A B C m6 6 m5 5 m4 4 m3 3 m2 2 m1 1 m0 A B C 编号 对应十进制数 使最小项为1的值 最小项 1.最小项的定义： 在n变量逻辑函数中，若m为包含n个因子的与项，且这些变量均以原变量或反变量的形式出现一次，则称m为该组变量的最小项。 以三变量为例，如表。 此时AB、A都不是最小项。

18 ABC.ABC=0 ABC+ABC=AB 2.最小项的性质： （1）对应输入变量的任何取值，都会有一个最小项，且仅有一个最小项的值为1；
（2）全体最小项之和为1； ABC.ABC=0 （3）任意两个最小项之积为0； （4）两个逻辑相邻的最小项之和可合并成一项，且消去一对因子。 定义：如两个最小项只有一个变量不相同，则称之为逻辑相邻。 例： ABC和ABC是逻辑相邻的最小项，当它们相加时，会消去变量C ： 有链接 ABC+ABC=AB 下面要介绍的卡诺图就是利用最小项的这一性质化简逻辑函数的。 利用性质（1）可以从真值表求出逻辑函数的标准与或式。 关于最大项和逻辑函数的标准或与式留给同学自学。

19 （二）逻辑函数的最小项之和标准形式 A B C Y 1 操作方法：将函数值为1的行对应的最小项取出相加。 以举重裁判逻辑为例。Y=1对应m5、m6、m7三个最小项，固有： Y= ABC + ABC + ABC 简写成 Y=m5+m6+m7 Y= 或 或 将非标准形式化成标准形式： 规律： Y=AB+AC 少1个变量，化成2个最小项之和； =AB(C+C)+AC(B+B) 少2个变量，化成4个最小项之和； =ABC+ABC+ABC 少n个变量，化成2n个最小项之和。

20 第六节 逻辑函数的公式化简法 化简的意义：将逻辑函数化成最简形式便于在用电路实现时节省器件。 一、 逻辑函数式最简的标准
逻辑函数式有多种形式，如与或式，或与式，与非与非式，或非或非式等等。 AB+AC 与或式 两次取反 =AB AC 与非与非式 =A(B+C) 或与式 两次取反 =A＋B+C 或非或非式 与或式使用最多，因此我们只讨论与或式的最简标准： 1.包含的与项最少； 2.在满足1项的前提下，每个与项包含的变量个数最少。

21 A + AB = A A + AB = A+B A B+AB = A A B+AC+BC = AB+AC A B+AC =A B+A C
二、化简方法 常用公式 A + AB = A A B+AB = A A B+AC+BC = AB+AC A + AB = A+B A B+AC =A B+A C 1. 2. 3. 4. 5. 我们通过一些例子说明如何应用这些公式进行化简。 吸收法 消因子法 Y=AB+A(C+D)B 并项法 =AB 1式 Y=AC+AD+CD =AC+AC D =AC+ D 2式 消项法 Y=ABC+AC+B C Y=AB+AB+BC+BC =AB+AB+BC +BC + AC =ABC+A B C =C 3式 =AB+BC +AC Y=AC+AD+C+D 或 Y=AB+AB+BC+BC + AC =AC+AD+C D =AB+BC +AC 4式 本例说明最简式不一定是唯一的。 =AC+C D

22 A + AB = A A + AB = A+B A B+AB = A A B+AC+BC = AB+AC A B+AC =A B+A C
函数式中的任一与项都可重复使用： 常用公式 1. A + AB = A Y=ABC+ABC+ABC 2. A + AB = A+B =ABC+ABC+ABC+ABC =ABC+ABC+ABC+ABC 3. A B+AB = A 3式 =AB+BC 4. A B+AC+BC = AB+AC 5. A B+AC =A B+A C Y=AB C+CD .A 5式 =(AB C+CD) .A =A C D B C Y=AC+BC+BD+CD+A(B+C)+ABCD+ABDE =BC+BD+A 注意： 1.当有长非号时，应先化简非号下的式子，然后脱掉非号。 2.要十分注意冗余项公式的应用。

23 第七节 逻辑函数的卡诺图化简法 1 10 11 01 卡诺图是用来化简逻辑函数的。由英国工程师Karnaugh首先提出的。也称卡诺图为K图。
一、逻辑函数的卡诺图表示法 （一）表示最小项的卡诺图 将真值表画成矩形表格。遵循的原则是逻辑相邻的最小项在卡诺图上对应的小方格要几何位置相邻。 几何位置相邻：1.有公共边；2.位置对称。 循环码 画法： 1 10 11 01 00 A BC 1 A B m0 m1 m0 m1 m3 m2 ABC m2 m3 m4 m5 m7 m6 ABC 二变量 ABC ABC ABC 三变量

24 00 01 11 10 四变量 D 五变量以上的卡诺图不作要求。 AB CD
卡诺图上每个变量取1和取0的方格数各占总格数的一半。所以卡诺图还有另一种标法： ABCD m0 m1 m3 m2 m4 m5 m7 m6 B m12 m13 m15 m14 A m8 m9 m11 m10 C （二）用卡诺图表示逻辑函数 显然，只要在每个小方格里填上函数值（0或1）即可。 具体操作还要分两种情况： 第一种，已知逻辑函数的真值表； 第二种，已知逻辑函数的函数式；

25 1.已知真值表 1 10 11 01 00 A BC 真值表和卡诺图有一一对应关系，可直接填。如举重裁判： 我们已知道它的真值表中包含5，6，7号三个最小项。 1 1 1 由于函数值只有0，1两种取值，故可将0省略。 2.已知函数式 当已知最小项标准形式时，与1中情况相同。如Y=m5+m6+m7 当已知一般与或式时，可将其化成最小项标准形式。如： 1 10 11 01 00 A BC Y=AB+AC =AB(C+C)+AC(B+B) =ABC+ABC+ABC 1 1 1 也可直接将每个与项填进卡诺图： 与项AB填入A、B都等于1的方格。 即6号和7号最小项。 与项AC填入A、C都等于1的方格。 即5号和7号最小项。

26 10 11 01 00 1 1 1 1 1 1 1 1 这说明： 少1个变量的与项，在卡诺图上占2个相邻的小方格。
我们在四变量卡诺图上作进一步研究。 与项AB少两个变量，用AB(C+C)(D+D)方法可得，它包含4个最小项，编号是12，13，14，15，它们组成一个矩形。 10 11 01 00 AB CD 易证明AD所占的4个格组成正方形。 与项A少3个变量，用A(B+B)(C+C)(D+D)方法可得，它包含8个最小项，编号是8，9，10，11，12，13，14，15，它们组成一个矩形。 1 1 1 1 1 1 1 1 结论： 与项少k个变量，在卡诺图上占2k个的小方格，且组成矩形。 将这个结论反过来用于化简，就是合并最小项的规律。

27 00 01 1 11 10 二、用卡诺图化简逻辑函数 ——图形法 （一）合并最小项的规律 将：
与项少k个变量，在卡诺图上占2k个的小方格，且组成矩形。 反过来用： 在卡诺图上合并组成矩形的2k个小方格，得到的与项少k个变量。 红框合并2个最小项，对应与项ABC少1（k）个变量。 篮（绿）框合并4个最小项，对应与项AB（AC）少2（k）个变量。 10 11 01 00 AB CD 1 紫框合并8个最小项，对应与项A少3（k）个变量。 注意： 1.只能合并2k个小方格； 2.边上方格的相邻性。

28 10 11 01 00 1 1 1 1 1 1 1 1 AB CD 图中黑框对应与项A B D。 图中篮框对应与项A D。
（二）卡诺图化简法 1 1 由于每个与项在卡诺图上对应1个函数值为1 的矩形区，因此可用一个“圈”（也称为矩形组）将其包围。 1 1 逻辑函数的最简式有几个与项，就一定对应同样多的圈。 将 最简的原则与画圈对比： 1 与项最少 ——对应圈最少； 与项中的变量最少 ——对应每个圈最大； 因此，化简的原则是： 用最少的圈（矩形组）覆盖所有的1，1可以重复使用； 每一个圈（矩形组）覆盖2k个1，且k要取最大值；

29 10 11 01 00 1 1 1 1 1 1 1 1 综上所述，化简的步骤是： 1.将逻辑函数化成与或式，然后画出其卡诺图；
2.按最简原则画出必要的圈； 1可重复使用 3.求出每个圈对应的与项，然后相加。 举例说明： 10 11 01 00 AB CD Y=(A+B)CD+(A+B)(A+B+C+D) =ACD+BCD+AB+ABCD 1 1 1 1 卡诺图为： 1 用三个圈覆盖： 要圈两个1 1 1 最简与或式为： 1 Y=CD+A B+ABD 当最简式不唯一时，画圈的方法也不唯一：

30 Y=AB+BC+CA 1 10 11 01 00 A BC Y=AB+AB+BC+BC 卡诺图如右; 1 1 1 圈黑圈，得： Y=AB+BC+CA 1 1 1 圈篮圈，得： Y=AB+BC+CA 冗余项公式在这个卡诺图上看得非常清楚。 Y(A,B,C,D)=m1+m5+m6+m7+m11+m12+m13+m15 10 11 01 00 AB CD 显然，紫圈是多余的。 1 避免画多余圈的方法： 1 1 1 1.画完圈后注意检查； 1 1 1 2.先圈只有一种方法可圈的1。 1

31 00 01 11 10 00 01 11 10 举两个例子： AB CD Y=AD+BCD+ABC+ACD+A BD =AB+BC+B D
Y=ACD+CD+AD+AB+ABC 10 11 01 00 AB CD 这种情况可通过圈0求Y来解决： Y=AD 1 1 Y=A+D 1 1 1

32 第八节 具有无关项的逻辑函数及其化简 A B C D （一）无关项 无关项是约束项和任意项的总称。
Y 1 （一）无关项 无关项是约束项和任意项的总称。 1.约束项：是最小项，若使该最小项的值为1的输入变量取值不允许输入，则称该最小项为约束项。 例如，四舍五入函数——用A,B,C,D组成的四位二进制数表示1位十进制数，当该数大于4时输出为1。 真值表为： 1010——1111六个值不允许输入。将m10～m15称为约束项。在真值表和卡诺图中都用 表示。 在函数式中约束项的表示方法： 将约束项之和等于0称为约束条件 m10+m11+m12+m13+m14+m15=0 也可用求和符号表示上式：

33 10 11 01 00 1 1 1 1 1 因此四舍五入函数可表示为 AB CD 约束条件：
m10+m11+m12+m13+m14+m15=0 或 或 AB+AC=0 1 1 1 也可这样表示： 把这类逻辑函数称为有约束的逻辑函数。 1 1 2.任意项：是最小项，若使其值为1的变量取值输入时，函数值可为0，也可为1，则称该最小项为任意项。 任意项很少遇到，这里不作讨论。 若将m8和m9改为0，则10，11，12号约束项就按0处理了。 （二）约束项在化简中的应用 约束项对应的方格可填为0，也可填为1。 原则是将函数化到最简。

34 请注意，被圈进去的约束项在方格中表示1，未圈进去的约束项表示0。
注意：有约束项时，一定要用卡诺图化简。不要用公式法，除非变量太多，无法用卡诺图化简。 10 11 01 00 AB CD 1 举两个例子： 1 Y(A,B,C,D)=m1+m7+m8 约束条件为 m3+m5+m9+m10+m12+m14+m15=0 1 Y(A,B,C,D)=A D +A D 10 11 01 00 AB CD Y =ACD+ABCD+ABCD 约束条件为 1 AB+AC=0 Y=AD+BD+CD 1 1 请注意，被圈进去的约束项在方格中表示1，未圈进去的约束项表示0。 1