SZLJ2逻辑代数基础

1、第二章第二章 逻辑代数基础逻辑代数基础Fundamentals of Boolean Algebar布尔代数：布尔代数：用一种数学运算数学运算的代数系统描述人的人的逻辑思 维规律和推理过程。逻辑代数：逻辑代数：将布尔代数的一些基本前提和定理应用于继应用于继 电器电器的分析与描述。成为二值布尔代数，或 开关代数。 逻辑代数是二值逻辑运算中的基本数学工具 逻辑代数广泛应用于数字系统的分析和设计数字逻辑 第二章 第一节2.1 逻辑代数中的几个概念逻辑代数中的几个概念 1. 逻辑状态逻辑状态 Logic State： 当事物的某些特性表现为两种互不相容互不相容的状态，即 某一时刻必出现且仅出现一种状态

2、 一种状态是另一种状态的反状态 则用符号0、1分别表示这两种状态，称逻辑状态。即：0状态状态(0state)和1状态状态(1state) 一般，0状态逻辑条件的假或无效，1状态逻辑条件的真或有效。 (两种状态无大小之分)数字逻辑 第二章 第一节 2. 逻辑变量逻辑变量 Logic Value ： 用于表示事物的逻辑状态随逻辑条件的变化而变化，取值：0 或1 。 逻辑常量逻辑常量 Logic Constant ： 逻辑状态保持不变，取值“0” 或“1”。 3. 逻辑电平逻辑电平 Logic Voltage： 在二值逻辑电路(开关电路)中，将物理器件的物理量离散离散 为两种电平：高电平高电平(用H

3、表示)、低电平低电平(用L表示) 抽象化的高、低电平忽略忽略其物理量值的实际含义，实际上 它们是代表着一定范围一定范围的物理量。参见下页。 在高、低电平之间有一逻辑不确定区，称为“噪音区”。若 电平稳定于噪音区称为逻辑模糊，这在逻辑电路中不允许。表表21不同工艺器件定义的逻辑电平不同工艺器件定义的逻辑电平 工艺 逻辑电平（电源电压为5V） L H TTL 00.40V 3.0 5.0V CMOS 0 0.80V 2.0 5.0V图图2-1 脉冲的逻辑电平表示脉冲的逻辑电平表示 逻辑约定逻辑约定 Logic Assumpsit： 规定规定 逻辑电平逻辑电平（表示（表示物理器件的物理量） 与与 逻

4、辑状态逻辑状态（表示（表示物理器件的功能） 之间的之间的 关系关系，即，即逻辑规定（约定）逻辑规定（约定）。 这一规定过程称为逻辑化过程逻辑化过程。 逻辑规定逻辑规定有两种：正逻辑正逻辑规定（约定） 和 负逻辑负逻辑规定（约定），如下：01LH逻辑状态逻辑状态逻辑电平逻辑电平(a)正逻辑规定（约定）注：本书均采用正逻辑约定。H电平L电平1状态0状态 逻辑电路逻辑电路Logic Circuit： 由实现逻辑变量之间逻辑关系的物理器件所构成的电路称为逻辑电路，即二值逻辑电路。 4. 逻辑代数逻辑代数 Logic Algebar ： 用代数形式表现逻辑变量之间的因果关系。 用代数运算对这些逻辑变量进

5、行逻辑推理。 因此，逻辑代数是一个集合一个集合：逻辑变量集、常量0和1、 “与”、“或”和“非”三种逻辑运算。 运算顺序是：“非”最高，“与”次之，“或”最低 。10LH逻辑状态逻辑电平(b)负逻辑规定（约定）H电平L电平0状态1状态5. 逻辑函数逻辑函数 Logic Function： 输入逻辑变量 A1，A2， , An；输出逻辑变量F；记为：F = f(A1，A2， , An )，关系如下图所示： 图 2-3 F=f(A1,A2,An)实现f(A1，A2， , An )的逻辑网络A1A2 AnF数字逻辑 第二章 第一节6. 逻辑函数的表示法逻辑函数的表示法 Representation：

6、主要有四种 真值表真值表(穷举法穷举法) Truth Tablea bF0 00 11 01 10001真值表例表达式例：F= a b 逻辑表达式逻辑表达式 Algebraic Forms of Switching Functions 卡诺图卡诺图 Karnaugh MAP (文氏图 Venn Diagrams) 时间图时间图 (信号波形图信号波形图 ) Timing引入变量A，将 区域 一分为二Venn图全集 为 1引入变量B，将已有区域再分别一分为二2.2 逻辑代数的基本运算逻辑代数的基本运算（逻辑乘） 图24（a）的串联开关电路是与逻辑的一个实例。只有开关A、B都闭合，灯F才会亮；开关A

7、、B只要有一个不闭合，则灯F就不会亮。 设开关闭合状态为“1”，断开状态为“0”；灯亮状态为“1”，灯灭状态为“0”。则可得到图24（b）的对应逻辑状态关系真值表表示。如用逻辑代数式表示，可记为：F=AB或F=A*B 按此类推，如果电路中有4个开关A、B、C、D串联，则有F=ABCD。“与”运算(逻辑乘)Logic Multiplication“或”运算(逻辑加)Logic Addition“非”运算(逻辑非)Logic Negation运算结果逻辑积 Logic Product逻辑和 Logic Sum求补Complement示意电路真值表FABFABFARA BF0 00 11 01 10

8、001A BF0 00 11 01 10111AF0 1 10“与”运算(逻辑乘)Logic Multiplication“或”运算(逻辑加)Logic Addition“非”运算(逻辑非)Logic Negation代数式F = A B = A BF = ABF = A逻辑符号波形图文氏图(F为阴影)&DABCFDABCF1DABCFFDABC1AFAFABFABFAFA2.3 逻辑代数的基本定理及规则逻辑代数的基本定理及规则基本运算基本运算： 1 = 0 0 = 11 1 = 1 0 + 0 = 00 1 = 1 0 = 0 1 + 0 = 0 + 1 = 10 0 = 0 1 +

9、 1 = 1 (10)2.3.1 布尔代数的基本公理布尔代数的基本公理 Basic Postulates 公理是基本的假设，是客观存在，无需证明。可以用真值表验证等式成立，当然等式两边还具有相同的卡诺图，体现了表达式的多样性。 运算的优先顺序：括号，非，与，或。01 律律 0 and 1 elements for and operators A + 0 = A A 1 = A A + 1 = 1 A 0 = 0 Commutativity of the and operations交换律交换律 A B = B A A B = B A结合律结合律 A(BC) = (AB)C A ( B C )

10、= ( A B ) C Distributivity of the and operations分配律分配律 ABC = (AB)(AC) A (BC) = A BA C数字逻辑 第二章 第三节A B C（A+B)(A+C) B CA+BCA+B A+C0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 10001000100011111001111110101111100011111 可以用同样的方法证明 A (B+C) = A B+ A C 成立。由此证明A+BC = (A+B)(A+C)成立。例：证明分配律分配律 ABC = (AB)(AC) 成立

11、 用真值表证明，如下：重叠律重叠律 Idempotency A + A = A A A = A 上述三条基本公理可以用Venn图验证。如下所示：问题：若 A + B = 1 ，则 A 与 B 互补吗？ 若 A B = 0 ，则 A 与 B 互补吗？互补律互补律 Complement A + A = 1 A A = 0全集 = 1引入变量A，将全集分为两个互补相容的部分： A 区域 和 A 区域AVenn图A对合律对合律 involution A = A数字逻辑 第二章 第三节2.3.2 布尔代数的基本定理布尔代数的基本定理 Fundamental Theorems右边 = A + 1 B （0

12、1律） = A +（ A + A ) B （互补律） = A + AB + A B （分配律） = A + AB （吸收律） = 左边 证明成立例 ：证明 A + A B = A + B ，可以用公理来证明。吸收律吸收律 AbsorptionA + A B = A + B A ( A + B ) = A BA B + A B = A ( A + B )( A+B ) = AA + AB = A A ( A + B ) = AA + B = A B A B = A + B反演律反演律 DeMorgans Theorem (摩根定理摩根定理) = A + 1 （互补律） = 1 （01律）例 ：证

13、明 A B = A + B，可以用函数的互补性证明。设：X = A B Y = A + B X + Y = AB + A + B = A + B + B （吸收律）又 X Y = AB（ A + B） = A B A + AB B (分配律） = 0 A + 0 B (互补律） = 0 + 0 (01律） = 0 (基本运算） X 与 Y 互补，X = Y，Y = X 。证明摩根定理成立。A1 + A2 + + An = A1 A2 An A1 A2 An = A1 + A2 + + An 摩根定理的作用：进行函数化简和逻辑变换。N变量的摩根定理：变量的摩根定理：数字逻辑 第二章 第三节 =

14、右边 证明成立 A B + AC + BC = AB + AC (A + B) (A + C) (B + C) = (A + B) (A + C) 例 ：证明 A B + AC + BC = AB + AC左边 = A B + AC + BC 1 （01律） = AB + AC + ABC + ABC （分配律） = AB + ABC + AC + ACB （交换律） = AB（1+C） + AC（1+B） （分配律） = AB 1 + AC 1 （ 01律） = AB + AC （ 01律）包含律包含律 Consensus (也称多余项定理也称多余项定理 ) = A B + AC + BC（

15、 A + A ) （互补律）1. 代入规则：代入规则：又 逻辑函数 h 取值取值仅有 0 或 1已知 f ( x1 , x2 , , xi , , xn ) = g ( x1 , x2 , , xi , , xn ) 有任意函数 h ，令： xi = h则 f ( x1 , x2 , , h , , xn ) = g ( x1 , x2 , ,h , , xn ) 依然成立。证明： xi 取值只有 0 或 1，使等式成立 代入规则成立。用代入规则证明N变量的摩根定理，如下：2.3.4 基本规则基本规则 Basic FormulasA1 + A2 + + An = A1 A2 An 令 X =

16、A2 + Y 代入 A1 + X = A1 X 令 Y = A3 + Z 代入则 A1 + A2 + A3 + Z = A1 A 2 (A3 + Z) 依次类推，则推出N变量的摩根定理。证明N变量的摩根定理： 则 A1 + A2 + Y = A1 ( A 2 + Y ) = A1 A2 Y (摩根定理)= A1 A2 A3 Z (摩根定理)数字逻辑 第二章 第三节 这是反演律和代入规则的推广使用。是对互补函数的完善说明。已知原函数 f ( x1 , x2 , , xn, 0 , 1, +, ) 则反函数 f ( x1 , x2 , , xn , 0 , 1, +, ) = f ( x1 , x

17、2 , , xn , 1 , 0, , + ) 3. 对偶规则对偶规则已知原函数 f ( x1 , x2 , , xn, 0 , 1, +, )则对偶函数 f ( x1 , x2 , , xn , 0 , 1, +, ) = f ( x1 , x2 , , xn , 1 , 0, , + ) 借助对偶规则可以减少记忆公式的数目(见公式) 。2. 反演规则反演规则(香农定理香农定理) Shannons expansion theorem2.4 逻辑函数的性质逻辑函数的性质2.4.1 复合逻辑复合逻辑与、或、非三种基本逻辑运算组合起来可以实现任何逻辑函数与门、或门、非门三种基本逻辑运算(门)组合起

18、来可以构成实现任何逻辑功能的逻辑电路，称此三门构成了一个逻辑完备组若实现一个较复杂的逻辑功能，尤其在大规模集成电路快速发展的今天, 必须增加门电路的功能,以简化电路.数字逻辑 第二章 第四节1. 与非逻辑与非逻辑(NAND) 逻辑表达式为: F = A B CA B CF0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 111111110&FA B CFB CA与非逻辑真值表 与非门的逻辑符号数字逻辑 第二章 第四节可以用与非门实现三种基本运算： 与运算 F1 = AB&AF3B& 或运算 F3= AA BB = A B = A B&

19、AF1B& 非运算 F2 = AA = A&F2A数字逻辑 第二章 第四节2. 或非逻辑或非逻辑(NOR) 逻辑表达式为: F = A B CA B CF0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 110000000或非逻辑真值表 或非门的逻辑符号11FA B CFB CA数字逻辑 第二章 第四节可以用或非门实现三种基本运算： 或运算 F2 = AB1F3A非运算F3 =AA = AAF1B111 与运算 F1=AA BB = AB = ABAF2B113. 与或非逻辑与或非逻辑(AOI) 逻辑表达式为: F = AB CD EF与或非门的逻辑

20、符号11FAB CD EF&FBCAFDE4. 异或逻辑异或逻辑(XOR) 逻辑表达式为: F = A B = A B A B异或逻辑真值表 异或门的逻辑符号A BF0 00 11 01 101101 1FABFBAFAB数字逻辑 第二章 第四节4. 同或逻辑同或逻辑 逻辑表达式为: F = A B = A B A B.同同或逻辑真值表 同或门的逻辑符号A BF0 00 11 01 110011 1FABFBAFAB数字逻辑 第二章 第四节异或运算与同或运算的关系异或运算与同或运算的关系1. A B = A B A B = A B 2. (A B)= A B (A B)= A B 3.

21、 A B C = A B C例：证明 A B = A B A B = A B A B = ( A B )( A B) = A B A B = A B 证明 (A B) = (A B A B) = ( A B )( A B ) = A B A B = A B西安交通大学 毛文林主讲证明 A B C = A ( B C ) A ( B C ) = A ( B C ) A ( B C ) = A ( B C BC ) A ( B C BC ) = A B C A B C A B C A B C 由上式可知，任意个变量的异或运算，只要输入为 1的个数是奇数时，输出必为1，即为奇校验逻辑。证明 A B

22、C = A ( B C ) A ( B C ) = A ( B C ) A ( B C ) = A ( B C BC ) A ( B C BC ) = A B C A B C A B C A B C 所以：当变量为变量为2时，同或运算同或运算与异或运算异或运算的之间具有互补互补关系； 当变量为变量为3时，同或运算同或运算与异或运算异或运算的之间具有相等相等关系。由代入规则可以证明： 当变量为偶数时，同或运算与异或运算之间具有互补关系；当变量为奇数时，同或运算与异或运算之间具有相等关系。即A1 A2 A3 An = A1 A2 A3 An n 为偶数A1 A2 A3 An = A1 A2 A3

23、An n 为奇数数字逻辑 第二章 第四节异或运算和同或运算的基本代数性质异或运算和同或运算的基本代数性质01律 (a) A 0 =A A 1 =A (b) A 0 =A A 1 =A交换律 (a) A B =B A (b) A B =B A分配律 (a) A(B C) =AB AC (b) A(B C) =(AB) (AC)结合律 (a) A (B C) = (A B) C (b) A (B C) =(A B ) C调换律 (a)若 A B = C 则 A C = B ， C B = A (b) 若A B = C 则 A C = B ， C B = A 依照逻辑运算的规则，一个逻辑可以用多种形

24、式的逻辑函数来描述，而这些逻辑函数的真值表都是相同的。如：F= A B2.4.2 逻辑函数的基本表达式逻辑函数的基本表达式 Algebraic Forms of Switching Functions = A B A B 与或式 SOP= ( AB )( AB ) 或与式 POS= A B A B 与非式= ( AB ) ( AB ) 或非式= A B A B 与或非式= 西安交通大学 毛文林主讲2.4.3 逻辑函数的标准形式逻辑函数的标准形式 Canonical Forms of Switching Functions 一个逻辑命题的三种表示法：真值表 表达式 卡诺图关系：真值表是逻辑函数最

25、基本的表达方式，具有 唯一性； 由真值表可以导出逻辑表达式和卡诺图； 由真值表导出逻辑表达式的两种标准形式： 最小项之和最小项之和 The canonical SOP(the Sum Of Products) 最大项之积最大项之积 The canonical POS(Product Of Sums)数字逻辑 第二章 第四节1. 最小项最小项 minterm 设有 n 个变量，它们组成的与项中每个变量或以原变量或以反变量形式出现一次，且仅出现一次，此与项称之为 n 个变量的最小项。对于 n 个变量就可构成 2n个最小项，分别记为 mi ； 其中下标值 i：当各最小项变量按一定顺序排好后，用 1

26、代替其中的原变量， 0 代替其中的反变量，便得一个二进制数，该二进制数的等值十进制即为 i 的值。 例如： 3 变量的 8 个最小项可以表示为：ABC = m0 ABC = m1 ABC = m2 ABC = m3ABC = m4 ABC = m5 ABC = m6 ABC = m7 为区别不同 n 值的相同 mi ，可记为： m i n2. 最大项最大项 maxterm 设有 n 个逻辑变量，它们组成的或项中，每个变量或以原变量形式或以反变量形式出现一次，且仅出现一次，此或项称为 n 变量的最大项。对于 n 个变量可以构成2n个最大项，分别记为 Mi ； 其中下标值 i的取值规则与最小项中

27、i的取值规则相反，即将各变量按一定次序排好后，用 0 代替其中的原变量，用 1 代替其中的反变量，得到一个二进制数，该二进制数的等值十进制即为 i 的值。 例如，三变量的最大项记为：ABC = M0 ABC = M1 ABC = M2 ABC = M3 ABC = M4 ABC = M5ABC = M6 ABC = M7 为区别不同 n 值的相同 Mi ，可记为： M i n3. 最小项与最大项的性质最小项与最大项的性质 例：一个三变量函数 F(A，B，C)，它的真值表及其最小项及最大项的对应关系如下表。行号A B CF(A，B，C) 最小项及代号 最大项及代号0123456700000101

28、0011100101110111F( 0,0,0)=1F( 0,0,1)=0F( 0,1,0)=0F( 0,1,1)=1F( 1,0,0)=1F( 1,0,1)=0F( 1,1,0)=1F( 1,1,1)=1A B C = m0A B C = m1A B C = m2A B C = m3A B C = m4A B C = m5A B C = m6A B C = m7A+B+C = M0A+B+C = M1A+B+C = M2A+B+C = M3A+B+C = M4A+B+C = M5A+B+C = M6A+B+C = M7西安交通大学 毛文林主讲最小项与最大项具有如下性质：最小项与最大项具有如

29、下性质： 对于任意最小项最小项，只有一组只有一组变量组合取值可使其值为为1；对于任意最大项最大项，只有一组只有一组变量组合取值可使其值为为0。(用Venn图示意出m i 和M i 的区域) 任意两个最小项之积必为0，即：mi mj = 0(ij) 任意两个最大项之和必为1，即：MiMj=1(ij) n变量的所有最小项之和必为1，记为： n变量的所有最大项之积必为0，记为：m i = = 12n -1i = 0M i = = 02n -1i = 0由上表可知，最小项与最大项具有如下性质由上表可知，最小项与最大项具有如下性质 同变量数下标相同的最小项和最大项互为反函数 即： m i = M i M

30、 i = m i 则： m i M i = 0 且且 m iM i =1数字逻辑 第二章 第四节4. 函数的最小项标准式函数的最小项标准式 逻辑函数被表达成一系列乘积项之和乘积项之和，则称之为积积之和之和表达式(SOP)，或称为与或表达式与或表达式。 如果构成函数的积之和表达式中每一个乘积项每一个乘积项(与与项项)均为最小项均为最小项时，则这种表达式称之为最小项标准式最小项标准式(The canonical SOP)，且这种表示是唯一唯一的。如：F(A,B,C) = AC + AB + BC = ABC + ABC + ABC + ABC = m2 m3 m5 m7 = m3(2,3,5,7)

31、数字逻辑 第二章 第四节写出逻辑函数的最小项标准式的方法：写出逻辑函数的最小项标准式的方法： 如果给定的函数为一般的与或表达式一般的与或表达式，可以反复应 用公式：公式：X=X(YY) 代入缺少某变量(Y)的与项中， 形成最小项之和的形式。 例： F = AC AB BC = AC( BB ) AB( CC ) ( AA )BC = ABCABCABCABCABCABC = ABCABCABCABC = m3(3,4,5,7)数字逻辑 第二章 第四节 如果给定函数用真值表表示，显然真值表每一行真值表每一行变量的组合对应一个最小项对应一个最小项。如果对应该行的函函数值为数值为 1 ，则函数的最小

32、项表达式中应包含应包含该行对应的最小项；如果该行的函数值为函数值为 0，则函数的最小项表达式中不包含不包含对应该行的最小项。例：对应前表(向前翻四页,P39 表2.6 )中的F(A,B,C)，其最小项表达式应为： F(A,B,C) = m0 m3 m4 m6 m7 = m3( 0,3,4,6,7 )显然 F(A,B,C) = m1 m2 m5 = m3( 1,2,5 ) 如果给定函数用卡诺图表示，则卡诺图上的每一块区域对应一个最小项。如果对应该区域的函数值为 1 ，则函数的最小项表达式中应包含该区域对应的最小项；如果该区域的函数值为 0，则函数的最小项表达式中不包含对应该区域的最小项。例：参见

33、2.5.2 “卡诺图法”。数字逻辑 第二章 第四节最小项与原函数、反函数的关系最小项与原函数、反函数的关系 对于 n 个变量的函数 F ，它共有2n个最小项，这些最小项不是包含在原函数 F 的最小项表达式中，就是包含在反函数 F的最小项表达式中。 用逻辑代数可以证明：F(x1,x2,x3, ,xn) F(x1,x2,x3, ,xn) =m i = = 12n -1i = 0数字逻辑 第二章 第四节5. 函数的最大项标准式函数的最大项标准式 逻辑函数被表达成一系列和项之积和项之积，则称为和之和之积表达式积表达式(POS)，或称为或与表达式或与表达式。 如果构成函数的或与表达式中的每一个和项每一个

34、和项均为最大项最大项，则这种表达式称为最大项标准式最大项标准式 ( The Canonical POS)，且这种表示是唯一的。如：F(A,B,C) = (A + C) (A + B) = (A+B+C) (A+B+C) (A+B+C) (A+B+C) = M0 M2 M4 M5 = M3( 0,2,4,5 )数字逻辑 第二章 第四节写出逻辑函数的最大项标准式的方法：写出逻辑函数的最大项标准式的方法： 如果给定的函数是一般的或与表达式一般的或与表达式，可以反复应 用公式：公式：X = X + YY = (X +Y)(X +Y) 代入缺少某变 量(Y)的和项中以形成最大项之积的形式。例： F =

35、(A + C) (A + B) = (A + C + B B) (A + B + C C) = (A+B+C) (A+B+C) (A+B+C) (A+B+C) = M0 M2 M4 M5 = M3( 0,2,4,5 )数字逻辑 第二章 第四节如果给定函数用真值表表示，显然真值表每一行变真值表每一行变量量的组合对应一个最大项一个最大项。如果对应该行的函数值为函数值为 0 ，则函数的最大项表达式中应包含应包含该行对应的最大项；如果该行的函数值为函数值为 1 ，则函数的最大项表达式中不包含对应该行的最大项。例：对应前表(向前翻八页,P39 表2.6)中的F(A,B,C)，其最大项表达式应为： F(A

36、,B,C) = M1 M2 M5 = M3( 1,2,5 )显然 F(A,B,C) = M0 M3 M4 M6 M7 = M3( 0,3,4,6,7 ) 如果给定函数用卡诺图表示，则函数的最大项表达式可以通过卡诺图得到。例：参见2.5.2 “卡诺图法”。数字逻辑 第二章 第四节最大项与原函数、反函数的关系最大项与原函数、反函数的关系 对于 n 个变量的函数 F ，它共有2n个最大项，这些最大项不是包含在原函数 F 的最大项表达式中，就是包含在反函数 F 的最大项表达式中。 可以证明：F(x1,x2,x3, ,xn) F(x1,x2,x3, ,xn) =M i = = 02n -1i = 0数字

37、逻辑 第二章 第四节同一函数的最小项标准式与其最大项标准式的关系同一函数的最小项标准式与其最大项标准式的关系: 同一逻辑函数的一种标准式变换成另一种标准式时，互换mn 和Mn 的符号，并在符号后列出列出原式中缺少缺少的那些数字。且这两种标准式都是唯一唯一的。例： F = m3( 0,2,3 ) = M 3( 1,4,5,6,7 )证明： F = m3( 0,2,3 ) 则 F = m3 ( 1,4,5,6,7 ) = m1 m4 m5 m6 m7 F = F = m1 m4 m5 m6 m7 = m1 m4 m5 m6 m7 = M1 M4 M5 M6 M7 = M 3( 1,4,5,6,7

38、)2.5 逻辑函数的化简逻辑函数的化简 Simplification of Switching Expression 一个逻辑函数对应着一个实现其逻辑功能的逻辑电路，当使该函数最简意味着使这个电路也最简。 最简逻辑电路：最简逻辑电路：门数最少；门的输入端最少； 门的级数最少。 最简与或式：最简与或式：与项的数目最少；每个与项的变量 个数最少。 最简或与式：最简或与式：或项的数目最少；每个或项的变量 个数最少。数字逻辑 第二章 第五节例： F = AB ( BC ) AC BC = AB C对应两种逻辑电路图，如下11111ABCCABABB+CACB CAB(B+C)F=AB(B+C)+AC+

39、BC&1ABABF=AB+C&C2.5.1 代数化简法：代数化简法： 要求熟记熟记化简公式公式、定理定理； 技巧性强技巧性强，可谓熟能生巧。特别是采用“配项法”， 要先找出“配项” ，使表达式 “由简变繁”，再消除 多余项，以达到化简。 代数化简的过程和结果呈多样性过程和结果呈多样性，且不易发现出 错，也不易判断是否最简。 上述问题在用卡诺图法化简卡诺图法化简时，均可得到较好的解决。数字逻辑 第二章 第五节一、与或式的化简一、与或式的化简与或式化简常用的公式主要有四个： A + A = 1 A + AB = A + BAB + AB = A AB + AC + BC = AB

40、+ AC 所谓化简过程就是运用代入规则，把某一子函数看成一个变量，进而应用公式简化，在这一过程中经常需要变换子函数的形式，以便能够应用公式进行简化，最终将函数化简为最简与或式最简与或式 (minimizing SOP) ，常用的方法有如下几种：数字逻辑 第二章 第五节1. 吸收法吸收法 利用公式：A+AB=A 消去多余变量消去多余变量。例： F AB+AB (C+D) E AB 利用公式： A + AB = A + B 消去反变量消去反变量。例： F = AB + AC + BC = AB + (A + B)C = AB + AB C = AB + C数字逻辑 第二章 第五节 3. 消去法消去

41、法利用公式：ABACBCAB AC 消去多余项消去多余项。 例：F = AC + ADE + CD = AC + CD + AD + ADE = AC + CD 2. 合并项法合并项法 利用公式： AB + AB = A ，两项合并合并为一项且消去消去一个变量一个变量。例： F = m4 (5,7,13,15) = ABCD + ABCD + ABCD + ABCD = ABD + ABD = BD 数字逻辑 第二章 第五节4. 配项法配项法解法解法2： F = AB + BC + BC + AB = AB(C+C) + BC (A+A) + BC + AB = ABC+AB C + ABC+

42、A BC + BC+AB = AC + BC + AB 当无法发现直接应用公式时，可先增加一些与项，再利用增加项消除多余项，即“先繁后简”。利用公式：1 A A 增加项数增加项数。例： F = AB + BC + BC + AB = AB + BC + BC(A+A) + AB(C+C) = (AB+ABC) + (BC+ABC) + (ABC+ABC) = AB + BC + AC利用公式： ABAC = ABACBC 增加项数增加项数。例： F = AB + BC + BC + AB = AB + BC + BC + AB + AC = AB + BC + AC解法解法2： F = AB

43、+ BC + BC + AB = AB + BC + AC + BC + AB = AB + BC + AC数字逻辑 第二章 第五节5. 综合法综合法 在一个函数的化简中同时用几种方法。例： F = AB + AC + BC + CB + BD + DB + ADE ( F + G ) = A(B + C) + BC + CB + BD + DB + ADE ( F + G ) = ABC + BC + CB + BD + DB + ADE ( F + G ) = A + BC + CB + BD + DB + ADE ( F + G ) = A + BC + CB + BD + DB = A

44、 + BC + CB + BD + DB + CD = A + BC + DB + CD数字逻辑 第二章 第五节二、或与式的化简二、或与式的化简 或与式化简有两种方法： 1. 常规法常规法 常规法化简方式类似于与或式的化简，化简中常用的公式主要有： ( A + B )( A + B ) = A A ( A + B ) = A A ( A + B ) = AB ( A + B )( A + C )( B + C ) = ( A + B )( A + C )例：F = A ( A + B )( A + D )( B + D )( A + C + E + H ) = A ( A + D )( B +

45、 D ) = AD ( B + D ) = AD数字逻辑 第二章 第五节2. 利用最简与或式得到最简或与式利用最简与或式得到最简或与式 二次对偶法二次对偶法 利用对偶规则，先求出F的对偶式F，再将对偶式F 化简为最简与或式最简与或式，最后再求一次对偶(F) = F，则得到 F 最简或与式。例： F = (A + B)(A + B)(B + C)(C + D)(B + D) F = AB + AB + BC + CD + BD = A + BC + CD + BD = A + BC + CD则 F = (F) = A (B + C)(C + D)数字逻辑 第二章 第五节2二次求反法二次求反法 利

46、用反演规则，先求出F的反函数 F，再将反函数 F 化简为最简与或式最简与或式，最后再求一次反 F = F，则得到 F 最简或与式。例： F = AB + AB + AC + BD F = (A + B)(A + B)(A + C)(B + D) = (AB + AB)(A + C)(B + D) = (AB + ABC + ABC)(B + D) = (AB + ABC)(B + D) = AB + ABCD则 F = F = (A + B)(A + B + C + D)数字逻辑 第二章 第五节代数化简的特点代数化简的特点 从上述的代数化简法可以看出，它主要是应用逻辑代数中的基本公式和法则，以

47、及一定的技巧，没有严格的规则可循，得到的化简结果是否是最简的也很难以判断。 下面讨论用卡诺图化简卡诺图化简的方法，采用这种方法可以有规律地、直观地有规律地、直观地写出最简逻辑表达式。数字逻辑 第二章 第五节2.5.2 卡诺图卡诺图(Karnaugh MAP)法法 卡诺图和文氏图(Venn MAP )一样，是逻辑函数真值表的一种图形表示真值表的一种图形表示，但在变量个数超过3个以上时，文氏图就不便表示了。而卡诺图原则上不受变量个数的限制。利用卡诺图可以有规律地化简逻辑函数表达式，并能直观地写出逻辑函数的最简式。 一、卡诺图的构成一、卡诺图的构成 卡诺图是一种平面方格阵列图平面方格阵列图，下页给出

48、了二、三、四、五、六变量的卡诺图。 数字逻辑 第二章 第五节单变量的卡诺图单变量的卡诺图二变量的卡诺图二变量的卡诺图全集“1”引入变量A，将区域分为两块AA分别对应着四个最小项 m0 = AB，m1 = AB， m2 = AB，m3 = AB。分别对应着两个最小项 m0 = A m1 = A再引入变量B，将区域分为四块A BA BA BA B010123三变量的卡诺图三变量的卡诺图 再引入变量C，将区域分为八块，分别对应着8 个最小项个最小项： m0=ABC，m1=ABC，m2=ABC，m3=ABC , m4=ABC，m5=ABC，m6=ABC，m7=ABC。CA02641375B四变量的卡诺

49、图四变量的卡诺图四变量(A、B、C、D)的卡诺图，分别对应着16个最小项个最小项：m0 = ABCD， m1 = ABCD， m2 = ABCD， m3 = ABCD, m4 = ABCD， m5 = ABCD， m6 = ABCD， m7 = ABCD, m8 = ABCD， m9 = ABCD， m10= ABCD, m11= ABCD，m12= ABCD， m13= ABCD, m14= ABCD， m15= ABCD0412815139371511261410ABCD五变量的卡诺图五变量的卡诺图五变量(A、B、C、D、E)的卡诺图，分别对应着32个最小项个最小项。04128151393

50、71511261410BCE16202824172129251923312718223026CDBA数字逻辑 第二章 第五节六变量的卡诺图六变量的卡诺图:有有64个最小项个最小项0412815139371511261410DF32364440333745413539474334384642ECB16202824172129251923312718223026D48526056495361575155635950546258CEFA卡诺图的构成特点：卡诺图的构成特点： n 变量变量卡诺图有2n个小方格个小方格(或称为单元)，每个小方 格内标注的十进制数就是它对应的最小项的下标值； 若干个小方格将

51、对应一个逻辑函数，即一个逻辑函数一个逻辑函数 可以图示于卡诺图上可以图示于卡诺图上。例：F = m1 + m2 + m5 + m7 ，其真值表和卡诺图标注如下：行号ABCFmi012345670 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 101100101m0m1m2m3m4m5m6m702641375A BC1111卡诺图的构成特点：卡诺图的构成特点： 整个卡诺图总是被每个变量分成两半每个变量分成两半：原变量，反变量各占一半。任一变量的原变量和反变量所占的区域又被其他变量分成两半。 在行和列上相邻相邻的小方格，其名称仅有一个变量状态不同。04128151393

52、71511261410ABCD思考： Gray码(模16、模10)在卡诺图上的表示。在卡诺图上的在卡诺图上的Gray码与码与Hamilton回路的关系回路的关系 每一种循环Gray码码对应着一条Hamilton回路回路 n 位位二进制Gray码的编码可以在 n 变量变量的卡诺图上表示出来 模模L的循环Gray码在卡诺图上对应着的是那条路径长路径长度为度为L 的Hamilton回路。例1. 典型Gray码及其 Hamilton回路0000010011001000000101011101100100110111111110110010011011101010例2. 另一个模16的Gray码编码及其

53、Hamilton回路0000010011001000000101011101100100110111111110110010011011101010数字逻辑 第二章 第五节例3. 两个模10的Gray码编码及其Hamilton回路00000100110010000001010111011001001101111111101100100110111010100000010011001000000101011101100100110111111110110010011011101010数字逻辑 第二章 第五节卡诺图的构成特点：卡诺图的构成特点： 除掉某个小方格(即最小项最小项)以外以外的整个卡诺图

54、区域 对应一个最大项对应一个最大项，最大项下标值就是应被除去的小 方格号。02641375A m7 M7BC02641375ABC 两个函数相“与与”，表示两个函数在卡诺图上所占两个区域的公共区域公共区域； 两个逻辑函数相“或或”，表示两个函数所覆覆盖的全部区域盖的全部区域； 一个逻辑函数的“非非”，就是求该函数覆盖覆盖之外的区域之外的区域。 上述卡诺图构成的特点及最小项与最大项在卡诺图上的表示，可以进一步说明逻辑运算的几何含逻辑运算的几何含义义：二、逻辑函数在卡诺图上的表示二、逻辑函数在卡诺图上的表示 把给定的逻辑函数化为最小项标准式最小项标准式 按变量数画出相应卡诺图卡诺图 在对应于最小项

55、标准式中各最小项的小方格内标以标以“1” 所有标有“1”的小方格的合成区域合成区域就表示该函数。 例：F1 = AC + ABC + BC 将函数化为标准式，即： F1 = ABC + ABC + ABC + ABC + ABC = m1 + m4 + m5 + m6 + m7 = m3 (1,4,5,6,7) F1的卡诺图见下页。数字逻辑 第二章 第五节F1= m3 (1,4,5,6,7)的卡诺图表示例：F2 = ABC + AC + BC 直接按与与、或或的几何含义将函数标注到卡诺图上。ABC A CB0264137511111026413751111BCACABC例：F3 = (A +

56、B)(C + B)(A + B) 求出反函数的与或式反函数的与或式，直接按与、或的共同区域将函数标注到卡诺图上，此时小方格应标注标注“0”，其余的标“1”，则标“1”小方格的集合就是原函数。则 F3 = AB + CB + AB 反函数在卡诺图上标0。ABC A02641375B C11100000思考：特殊函数(如同或和异或运算)在图上的表示。同或运算和异或运算在卡诺图上的表示同或运算和异或运算在卡诺图上的表示异或运算异或运算同或运算同或运算A BA BA B CA B CA B C DA B C D11111111111111111111111111110 0=01 1=10 0 0 =0

57、1 1 1 =10 0 0 0=01 1 1 1=1三、用卡诺图化简逻辑函数的基本原理三、用卡诺图化简逻辑函数的基本原理 1. “相邻相邻”的判断的判断相邻最小项相邻最小项：任意两个最小项中只有一个变量不同只有一个变量不同(同一变量名但一个为原变量，另一个为反变量)，其余变量完全相同，在图上反映的是两个相邻的小方格。卡诺图相邻小方格卡诺图相邻小方格：是指只隔一条边界的两个小方格。 在 n 变量的卡诺图上，每个小方格具有具有n个相邻个相邻的小方格，它们是：具有共同边界的小方格(几何相邻几何相邻)同一幅卡诺图中分别处于行(或列)两端的小方格 (相对相邻相对相邻)在相邻两幅卡诺图中，处于相同位置的两

58、个小方格 (相重相邻相重相邻) n 变量卡诺图变量卡诺图的每一个小方格都有的每一个小方格都有 n 个相邻块，个相邻块，以m0为例说明如下：010213026413750412815139371511261410041281513937151126141016202824172129251923312718223026n=1n=2n=3n=4n=5n 变量卡诺图变量卡诺图的每一个小方格都有的每一个小方格都有 n 个相邻块，个相邻块，以m0为例说明如下：0412815139371511261410162028241721292519233127182230263236444033374541353

59、947433438464248526056495361575155635950546258n=6 在真值表上，不易直观地理解最小项的相邻关系，在真值表上，不易直观地理解最小项的相邻关系，而在卡诺图上则相邻关系一目了然。而在卡诺图上则相邻关系一目了然。 2. 画卡诺圈的规则画卡诺圈的规则 寻找相邻块相邻块的目的是为了在图上进行函数化简函数化简。 任何2i个（个（i n）标）标1的相邻小方格的相邻小方格均可画在一个卡诺圈内； 任何2i个标个标1的非相邻的小方格的非相邻的小方格不能画入一个卡诺圈内，它们至少画在两个圈内。 数字逻辑 第二章 第五节162028241721292519233127182

60、230260 412815139371511261410 例：五变量的卡诺图 0维块：m7=ABCDE，是五变量的与项1111111111111ABCDE 1维块：由两个相邻的 0 维块构成的一个卡诺圈， m0 +m16=A B C D E + A B C D E=B C D E m22+m30=A B C D E + A B C D E=A C D E m25+m29=A B C D E + A B C D E=A B D E 是四变量的与项162028241721292519233127182230260 412815139371511261410 例：五变量的卡诺图2维块：由四个相邻的 0 维块构成的一个卡诺圈， m8+m9 +m12+m13= A B D