逻辑代数中的几个概念逻辑代数的基本运算逻辑代

1、2.1 逻辑代数中的几个概念逻辑代数中的几个概念2.2 逻辑代数的基本运算逻辑代数的基本运算2.3 逻辑代数的基本定理及规则逻辑代数的基本定理及规则2.4 逻辑函数的性质逻辑函数的性质2.5 逻辑函数的化简逻辑函数的化简第二章第二章 逻辑代数基础逻辑代数基础第二章第二章 逻辑代数基础逻辑代数基础Fundamentals of Boolean Algebar布尔代数布尔代数 Boolean algebra： 用一种用一种数学运算数学运算的代数系统的代数系统描述描述人的人的逻辑思维规律和推理过程。逻辑思维规律和推理过程。逻辑代数逻辑代数 Switching algebra： 将布尔代数的一些基本前

2、将布尔代数的一些基本前提和定理提和定理应用于继电器应用于继电器的分析与描述的分析与描述，称为，称为二值布尔代数二值布尔代数，或，或开关开关代数代数。继电器是当时最常用的数字逻辑元件，继电器的接触状态。继电器是当时最常用的数字逻辑元件，继电器的接触状态（打开或闭合）用（打开或闭合）用 0 或或 1表示。表示。逻辑代数是二值逻辑运算中的基本数学工具逻辑代数是二值逻辑运算中的基本数学工具逻辑代数广泛应用于数字系统的分析和设计逻辑代数广泛应用于数字系统的分析和设计第二章第二章 逻辑代数基础逻辑代数基础Fundamentals of Boolean Algebar在在现代逻辑分析技术现代逻辑分析技术中，

3、逻辑值对应于各种广泛中，逻辑值对应于各种广泛的物理条件：电压的高或低、灯光的明或暗、电容器的物理条件：电压的高或低、灯光的明或暗、电容器的充电或放电、熔丝的断开或接通，等等。的充电或放电、熔丝的断开或接通，等等。下表给出了下表给出了不同的计算机逻辑和存储技术中表示不同的计算机逻辑和存储技术中表示位值的物理状态位值的物理状态。不同的计算机逻辑和存储技术中表示位值的物理状态不同的计算机逻辑和存储技术中表示位值的物理状态表表 示示 位位 值值 的的 状状 态态技术技术01气动逻辑气动逻辑继电器逻辑继电器逻辑CMOS逻辑逻辑TTL逻辑逻辑光纤光纤动态存储动态存储非易失的可擦存储器非易失的可擦存储器双极

4、只读存储器双极只读存储器磁泡存储器磁泡存储器磁带存储器磁带存储器聚合体存储器聚合体存储器只读压缩盘只读压缩盘可重写压缩盘可重写压缩盘低压流动低压流动电路断开电路断开01.5V00.8V暗暗电容放电电容放电电子捕获电子捕获熔丝烧断熔丝烧断无磁泡无磁泡磁通朝磁通朝“北北”分子处于状态分子处于状态A无凹陷无凹陷晶态染色晶态染色高压流动高压流动电路闭合电路闭合3.55.0V2.05.0V亮亮电容充电电容充电电子释放电子释放熔丝完好熔丝完好有磁泡有磁泡磁通朝磁通朝“南南”分子处于状态分子处于状态B凹陷凹陷非晶态染色非晶态染色2.1 逻辑代数中的几个概念逻辑代数中的几个概念 1. 逻辑状态逻辑状态 Log

5、ic State： 当事物的某些特性表现为两种当事物的某些特性表现为两种互不相容互不相容的状态，即的状态，即 某一时刻必出现且仅出现一种状态某一时刻必出现且仅出现一种状态 一种状态是另一种状态的反状态一种状态是另一种状态的反状态 则用符号则用符号0、1分别表示这两种状态，称逻辑状态。分别表示这两种状态，称逻辑状态。即：即：0 状态状态 (0state) 和和 1 状态状态 (1state) 一般，一般，0状态状态逻辑条件的假或无效，逻辑条件的假或无效， 1状态状态逻辑条件的真或有效。逻辑条件的真或有效。 (两种状态无大小之分两种状态无大小之分)2. 逻辑变量逻辑变量 Logic Value ：

6、用于表示事物的逻辑状态随逻辑条件的变化而变化，用于表示事物的逻辑状态随逻辑条件的变化而变化，取值取值“0” 或或“1” 。4. 逻辑电平逻辑电平 Logic Voltage：在二值逻辑电路在二值逻辑电路(开关电路开关电路)中，将物理器件的物理量中，将物理器件的物理量离散离散为两种电平：为两种电平：高电平高电平（用用 H 表示）、表示）、低电平低电平（用用 L 表示）表示）抽象化的高、低电平抽象化的高、低电平忽略忽略其物理量值的实际含义，实其物理量值的实际含义，实际上它们是代表着际上它们是代表着一定范围一定范围的物理量。参见下页。的物理量。参见下页。在高、低电平之间有一逻辑不确定区，称为在高、低

7、电平之间有一逻辑不确定区，称为“噪音噪音区区”。若电平稳定于噪音区称为逻辑模糊，这在逻辑。若电平稳定于噪音区称为逻辑模糊，这在逻辑电路中不允许。电路中不允许。3. 逻辑常量逻辑常量 Logic Constant ： 逻辑状态保持不变，取值逻辑状态保持不变，取值“0” 或或“1”。表表21不同工艺器件定义的逻辑电平不同工艺器件定义的逻辑电平 工艺工艺 逻辑电平（电源电压为逻辑电平（电源电压为5V） L H TTL 00.40V 3.0 5.0V CMOS 0 0.80V 2.0 5.0V图图2-1 脉冲的逻辑电平表示脉冲的逻辑电平表示LHLH5. 逻辑约定逻辑约定 Logic Assumpsit

8、：规定规定 逻辑电平逻辑电平（表示物理器件的输入、输出物理量）（表示物理器件的输入、输出物理量） 与与 逻辑状态逻辑状态（表示物理器件的逻辑功能）（表示物理器件的逻辑功能） 之间的之间的 关系关系，即，即逻辑规定（约定）逻辑规定（约定）。这一规定过程称为这一规定过程称为逻辑化过程逻辑化过程。 逻辑约定逻辑约定有两种：有两种：正逻辑正逻辑规定（约定）规定（约定） 和和 负逻辑负逻辑规定（约定），如下：规定（约定），如下：正逻辑正逻辑规定（约定）规定（约定）负逻辑负逻辑规定（约定）规定（约定）01LH逻辑状态逻辑状态逻辑电平逻辑电平(a)(a)正逻辑规定（约定）正逻辑规定（约定）注：本书均采用正逻

9、辑约定。H H电平电平L L电平电平1状态0状态10LH逻辑状态逻辑状态逻辑电平逻辑电平(b)(b)负逻辑规定（约定）负逻辑规定（约定）H H电平电平L L电平电平0状态1状态 逻辑电路逻辑电路Logic Circuit： 由实现逻辑变量之间逻辑关系的物理器件所构成的由实现逻辑变量之间逻辑关系的物理器件所构成的电路称为逻辑电路，即二值逻辑电路。电路称为逻辑电路，即二值逻辑电路。6. 逻辑代数逻辑代数 Logic Algebar ： 用代数形式表现逻辑变量之间的因果关系。用代数形式表现逻辑变量之间的因果关系。 用代数运算对这些逻辑变量进行逻辑推理。用代数运算对这些逻辑变量进行逻辑推理。 因此，逻

10、辑代数是因此，逻辑代数是一个集合一个集合：逻辑：逻辑变量变量集、集、常量常量0和和1、 “与与”、“或或”和和“非非”三种逻辑三种逻辑运算运算。 运算顺序是：运算顺序是：“非非”最高，最高，“与与”次之，次之，“或或”最最低。低。7. 逻辑函数逻辑函数 Logic Function： 输入逻辑变量输入逻辑变量 A1，A2， , An；输出逻辑变量；输出逻辑变量F；记为：记为：F = f (A1，A2， , An )，关系如下图所示：，关系如下图所示：F = f (A1, A2, , An)实现f (A1，A2， , An )的逻辑网络A1A2 AnF8. 逻辑函数的表示法逻辑函数的表示法 Re

11、presentation：主要有四种主要有四种 真值表（穷举法）真值表（穷举法） Truth TableA BF0 00 11 01 10001真值表例真值表例表达式例：表达式例：F = A B 逻辑表达式逻辑表达式 Algebraic Forms of Switching Functions 卡诺图卡诺图 Karnaugh MAP （文氏图（文氏图 Venn Diagrams） 时间图时间图 （信号波形图（信号波形图 ） TimingVenn图图全集全集 为为 1又引入变量又引入变量B，将已有区域将已有区域再分别一分再分别一分为二为二引入变量引入变量A，将，将 区域区域 一分为二一分为二2.

12、2 逻辑代数的基本运算逻辑代数的基本运算“与与”运算运算(逻辑逻辑乘乘)Logic Multiplication“或或”运算运算(逻辑逻辑加加)Logic Addition“非非”运算运算(逻辑逻辑非非)Logic Negation运算运算结果结果逻辑逻辑积积 Logic Product逻辑逻辑和和 Logic Sum求求补补Complement示意示意电路电路真值真值表表FABFABFARA BF0 00 11 01 10001A BF0 00 11 01 10111AF0 1 10“与与”运算运算(逻辑逻辑乘乘)Logic Multiplication“或或”运算运算(逻辑逻辑加加)Log

13、ic 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 + 1 = 1 (10)2.3.1 布尔代数的基本公理布尔代数的基本公理 Basic Postulate

14、s 公理是基本的假设，是客观存在，无需证明。可以用公理是基本的假设，是客观存在，无需证明。可以用真值表验证等式真值表验证等式成立，当然等式两边还具有相同的卡诺图，成立，当然等式两边还具有相同的卡诺图，体现了表达式的多样性。体现了表达式的多样性。 运算的优先顺序：括号，非，与，或运算的优先顺序：括号，非，与，或。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结合律结合律

15、 A(BC) = (AB)C A ( B C ) = ( A B ) C Distributivity of the and operations分配律分配律 AB C = (AB)(AC) A (BC) = A BA CA B C（A+B)(A+C) B C A+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

16、) 成立成立。例：证明例：证明 分配律分配律 AB C = (AB)(AC) 成立。成立。 用真值表证明，如下：用真值表证明，如下：重叠律重叠律 Idempotency A + A = A A A = A 互补律互补律 Complement A + A = 1 A A = 0对合律对合律 involution A = A2.3.2 逻辑代数的基本定理逻辑代数的基本定理 Fundamental Theorems右边右边 = A + 1 B （01律）律） = A +（ A + A ) B （互补律）（互补律） = A + AB + A B （分配律）（分配律） = A(1+B) + AB （分配

17、律）（分配律） = 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 ) = A = 左边左边 证明成立证明成立A + B = A B A B = A + B反演律反演律 DeMorgans Theorem (摩根定理摩根定理) = A + 1 （互补律）（互补律） = 1 （01律）律）证明证明 A B = A + B 成立，可以用函

18、数的互补性来证明成立，可以用函数的互补性来证明设：设：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 摩根定理的作用摩根定理的作用：进行函数

19、化简和逻辑变换。：进行函数化简和逻辑变换。N变量的摩根定理：变量的摩根定理：（此定理证明见代入规则。）（此定理证明见代入规则。） = 右边右边 证明成立证明成立 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 + AC （吸收律）（吸收律）包含律包含

20、律 Consensus (也称多余项定理也称多余项定理) = A B + AC + BC（ 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，使等式成立

21、，使等式成立 代入规则成立。代入规则成立。2.3.4 逻辑代数的基本规则逻辑代数的基本规则 Basic FormulasA1 + A2 + + An = A1 A2 An 令令 X = 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 A

22、2 A3 Z (摩根定理摩根定理)用代入规则证明用代入规则证明N变量的摩根定理，如下：变量的摩根定理，如下：这是反演律和代入规则的推广使用，是对互补函数的完善说明。这是反演律和代入规则的推广使用，是对互补函数的完善说明。已知原函数已知原函数 f ( x1 , x2 , , xn, 0 , 1, +, ) 则反函数则反函数 f ( x1 , x2 , , xn , 0 , 1, +, ) = f ( x1 , x2 , , xn , 1 , 0, , + ) 2. 反演规则反演规则(香农定理香农定理) Shannons expansion theorem例例： F = A B + (CD + E

23、) G 则反函数则反函数 F = A + B (C+D) E+ G 注意运算顺序并没有变化注意运算顺序并没有变化已知原函数已知原函数 f ( x1 , x2 , , xn, 0 , 1, +, )则对偶函数则对偶函数 f ( x1 , x2 , , xn , 0 , 1, +, ) = f ( x1 , x2 , , xn , 1 , 0, , + ) 结论：结论：1. （f ) = f3. 对偶规则对偶规则 Dual expansion theorem2. 若若 f1 = f2 则则 f1 = f2 2.4 逻辑函数的性质逻辑函数的性质 2.4.1 复合逻辑复合逻辑与与、或或、非非三种基本逻

24、辑运算组合起来可以实现任何三种基本逻辑运算组合起来可以实现任何逻辑函数。逻辑函数。与门、或门、非门三种基本逻辑运算与门、或门、非门三种基本逻辑运算(门门)组合起来可组合起来可以构成实现任何逻辑功能的逻辑电路，称此三门构成以构成实现任何逻辑功能的逻辑电路，称此三门构成了一个了一个逻辑完备组逻辑完备组若实现一个较复杂的逻辑功能，尤其在大规模集成电若实现一个较复杂的逻辑功能，尤其在大规模集成电路快速发展的今天，必须增加门电路的功能，以简化路快速发展的今天，必须增加门电路的功能，以简化电路。电路。1. 与非逻辑与非逻辑(NAND) 逻辑表达式为逻辑表达式为: F = A B CA B CF0 0 00

25、 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&AF1B& 非运算非运算 F2 = AA = A&F2A2. 或非逻辑或非逻辑(NOR) 逻辑表达式为逻辑表达式为: F = A B CA B CF0 0 00 0 10 1 00 1 11 0 01 0 11 1 01

26、 1 110000000或非或非逻辑真值表逻辑真值表 或非门或非门的逻辑符号的逻辑符号11FA B CFBCA可以用可以用或非门或非门实现三种基本运算：实现三种基本运算： 或运算或运算 F2 = AB1F3A非运算非运算 F3 =AA = AAF1B111 与运算与运算 F1 = AA BB = AB = ABAF2B113. 与或非逻辑与或非逻辑(AOI) 逻辑表达式为逻辑表达式为: F = AB CD EF与或非与或非门的逻辑符号门的逻辑符号11FAB CD E F&FBCAFDE4. 异或逻辑异或逻辑(XOR) 逻辑表达式为逻辑表达式为: F = A B = A B A B异或异

27、或逻辑真值表逻辑真值表 异或异或门门的逻辑符号的逻辑符号A BF0 00 11 01 101101 1FA BFBAFA B5. 同或逻辑同或逻辑 逻辑表达式为逻辑表达式为: F = A B = A B A B同或同或逻辑真值表逻辑真值表 同或同或门门的逻辑符号的逻辑符号A BF0 00 11 01 110011 1FA BFBAFA B异或运算与同或运算的关系异或运算与同或运算的关系1. A B = A B A B = A B 2. (A B) = A B (A B) = A B 3. A B C = A B C例：证明例：证明 A B = A B A B = A B A B = ( A B

28、 )( 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 ABC 由上式可知，任意个变量的异或运算，只要输入为由上式可知，任意个变量的异或运算，只要输入为 1 的个数是奇数时，输出必为的个数是奇数时，输出必为1，即为，即为奇校验逻辑奇校验逻辑。证明证明 A B C = A ( B C ) A

29、 ( 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 ABC 所以：所以：当当变量个数为变量个数为2时，时，同或运算同或运算与与异或运算异或运算具有具有互补互补关系；关系；当当变量个数为变量个数为3时，时，同或运算同或运算与与异或运算异或运算具有具有相等相等关系。关系。由代入规则可以证明：由代入规则可以证明：A1 A2 A3 An = A1 A2 A3 An n 为偶数为偶数A1 A2 A3 An = A1 A2 A3 An n 为奇数为奇数当当变量为偶数变量为偶数时，时，同或运算同或运算与

30、与异或运算异或运算之间具有之间具有互补互补关系关系；当当变量为奇数变量为奇数时，时，同或运算同或运算与与异或运算异或运算之间具有之间具有相等关系相等关系。即：即：异或运算和同或运算的基本代数性质异或运算和同或运算的基本代数性质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 =

31、C则则 A C = B ， C B = A (b) 若若A B = C则则 A C = B ， C B = A 依照逻辑运算的规则，一个逻辑命题可以用多种形式依照逻辑运算的规则，一个逻辑命题可以用多种形式的逻辑函数来描述，而这些逻辑函数的真值表都是相同的。的逻辑函数来描述，而这些逻辑函数的真值表都是相同的。2.4.2 逻辑函数的基本表达式逻辑函数的基本表达式 Algebraic Forms of Switching Functions = A B AB 与非式与非式= ( AB ) ( AB ) 或非式或非式= A B A B 与或非式与或非式= = ( AB )( AB ) 或与式或与式=

32、A B A B 与或式与或式如：如： F = A B2.4.3 逻辑函数的标准形式逻辑函数的标准形式 Canonical Forms of Switching Functions 一个逻辑命题的三种表示法：一个逻辑命题的三种表示法：真值表真值表 表达式表达式 卡诺图卡诺图三者之间的关系：三者之间的关系：真值表是逻辑函数最基本的表达方式，具有唯一性；真值表是逻辑函数最基本的表达方式，具有唯一性；由真值表可以导出逻辑表达式和卡诺图；由真值表可以导出逻辑表达式和卡诺图；由真值表导出逻辑表达式的两种标准形式：由真值表导出逻辑表达式的两种标准形式： 最小项之和最小项之和 The canonical SO

33、P(the Sum Of Products) 最大项之积最大项之积 The canonical POS(Product Of Sums)1. 最小项最小项 minterm设有设有 n 个变量，它们组成的个变量，它们组成的与项与项中每个变量或以原中每个变量或以原变量或以反变量形式出现一次，且仅出现一次，此与项称变量或以反变量形式出现一次，且仅出现一次，此与项称之为之为 n 个变量的最小项。个变量的最小项。对于对于 n 个变量就可构成个变量就可构成 2n个最小项，个最小项，分别记为分别记为 mi 。其中：其中：下标值下标值 i的取值为当各个最小项变量按一定顺的取值为当各个最小项变量按一定顺序排好后

34、，用序排好后，用 1 代替其中的原变量，代替其中的原变量， 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 个逻辑变量，它们组成的个逻辑变量，它们组

35、成的或项或项中，每个变量中，每个变量或以原变量形式或以反变量形式出现一次，且仅出现一或以原变量形式或以反变量形式出现一次，且仅出现一次，此或项称为次，此或项称为 n 变量的最大项。变量的最大项。对于对于 n 个变量可以构成个变量可以构成2n个最大项，分别记为个最大项，分别记为 Mi 。其中：其中：下标值下标值 i的取值规则与最小项中的取值规则与最小项中 i的取值规则的取值规则相反，即将各变量按一定次序排好后，用相反，即将各变量按一定次序排好后，用 0 代替其中的代替其中的原变量，用原变量，用 1 代替其中的反变量，得到一个代替其中的反变量，得到一个二进制数二进制数，该二进制数的该二进制数的等值

36、十进制等值十进制即为即为 i 的值。的值。 例如，三变量的最大项记为：例如，三变量的最大项记为：ABC = M0 ABC = M1 ABC = M2 ABC = M3 ABC = M4 ABC = M5ABC = M6 ABC = M7 为区别不同为区别不同 n 值的相同值的相同 Mi ，可记为：，可记为： M i n3.最小项与最大项具有如下性质：最小项与最大项具有如下性质： 对于任意对于任意最小项最小项，只有一组只有一组变量组合取值可使其值变量组合取值可使其值为为1；对于任意对于任意最大项最大项，只有一组只有一组变量组合取值可使其值变量组合取值可使其值为为0。（i对应的二进制取值时）对应的

37、二进制取值时） 任意两个最小项之积必为任意两个最小项之积必为0，即，即： mi mj = 0 ( ij ) 任意两个最大项之和必为任意两个最大项之和必为1，即，即： MiMj=1 ( ij ) n变量的所有最小项之和必为变量的所有最小项之和必为1，记为：，记为： n变量的所有最大项之积必为变量的所有最大项之积必为0，记为：，记为： m i = = 12n -1i = 0 M i = = 02n -1i = 0由上表可知，最小项与最大项具有如下性质由上表可知，最小项与最大项具有如下性质 同变量数下标相同的最小项和最大项互为反函数同变量数下标相同的最小项和最大项互为反函数 即：即： m i = M

38、 i M i = m i 则：则： m i M i = 0 且且 m iM i = 1例 ABC=A+B+CABCmiMi00000001000100001100100001011111000111004. 函数的最小项标准式函数的最小项标准式逻辑函数被表达成一系列逻辑函数被表达成一系列乘积项之和乘积项之和，则称之为，则称之为积积之和之和表达式表达式(SOP)，或称为，或称为与或表达式与或表达式。如果构成函数的积之和表达式中如果构成函数的积之和表达式中每一个乘积项每一个乘积项(与项与项)均为最小项均为最小项时，则这种表达式称之为时，则这种表达式称之为最小项标准式最小项标准式(The canon

39、ical SOP)，且这种表示是且这种表示是唯一唯一的。的。如如：F(A,B,C) = AC + AB + BC =A(B+B)C+A(C+C)B+(A+A)BC = ABC + ABC + ABC + ABC = m2 m3 m5 m7 = m3(2,3,5,7)写出逻辑函数的最小项标准式的方法：写出逻辑函数的最小项标准式的方法： 如果给定的函数为如果给定的函数为一般的与或表达式一般的与或表达式，可以反复应用，可以反复应用公式公式X=X ( YY ) 代入缺少某变量代入缺少某变量(Y)的与项中，形的与项中，形成最小项之和的形式。成最小项之和的形式。 例例： F = AC AB BC = AC

40、( BB ) AB( CC ) ( AA )BC = ABCABCABCABCABCABC = ABCABCABCABC = m3(3,4,5,7) 如果给定函数用真值表表示，显然如果给定函数用真值表表示，显然真值表每一行真值表每一行变量变量的组合的组合对应一个最小项对应一个最小项。如果对应该行的。如果对应该行的函数值为函数值为 1 ，则函数的最小项表达式中则函数的最小项表达式中应包含应包含该行对应的最小项；该行对应的最小项；如果该行的如果该行的函数值为函数值为 0，则函数的最小项表达式中，则函数的最小项表达式中不包不包含含对应该行的最小项。对应该行的最小项。前例题：前例题：AC=1 （m5+

41、m7） AB=1 (m4+m5) BC=1(m3+m7) 所以所以 m3+m4+m5+m7例：最小项表达式应为：例：最小项表达式应为： 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 ，则函数的最小项表达式中应包含该区域对应的最小项；则函数的最小项表达式中应包含该区域对应的最小项；如果该区域的函数值为

42、如果该区域的函数值为 0，则函数的最小项表达式中，则函数的最小项表达式中不包含对应该区域的最小项。不包含对应该区域的最小项。最小项与原函数、反函数的关系最小项与原函数、反函数的关系 对于对于 n 个变量的函数个变量的函数 F ，它共有，它共有2n个最小项，这些个最小项，这些最小项不是包含在原函数最小项不是包含在原函数 F 的最小项表达式中，就是包的最小项表达式中，就是包含在反函数含在反函数 F的最小项表达式中。的最小项表达式中。 用逻辑代数可以证明：用逻辑代数可以证明：F(x1,x2,x3, ,xn) F(x1,x2,x3, ,xn) = m i = = 12n -1i = 05. 函数的最大

43、项标准式函数的最大项标准式 逻辑函数被表达成一系列逻辑函数被表达成一系列和项之积和项之积，则称为，则称为和之积和之积表达式表达式(POS)，或称为，或称为或与表达式或与表达式。 如果构成函数的或与表达式中的如果构成函数的或与表达式中的每一个和项每一个和项均为均为最最大项大项，则这种表达式称为，则这种表达式称为最大项标准式最大项标准式 ( 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,

44、5 )写出逻辑函数的最大项标准式的方法：写出逻辑函数的最大项标准式的方法： 如果给定的函数是如果给定的函数是一般的或与表达式一般的或与表达式，可以反复应用，可以反复应用公公式：式：X = X + YY = (X +Y)(X +Y) 代入缺少某变量代入缺少某变量(Y)的的和项中以形成最大项之积的形式。和项中以形成最大项之积的形式。例：例： F = (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 )如果给定函数用真值表表示，显然如果

45、给定函数用真值表表示，显然真值表每一行变量真值表每一行变量的的组合对应组合对应一个最大项一个最大项。如果对应该行的。如果对应该行的函数值为函数值为 0 ，则，则函数的最大项表达式中函数的最大项表达式中应包含应包含该行对应的最大项；如果该行对应的最大项；如果该行的该行的函数值为函数值为 1 ，则函数的最大项表达式中，则函数的最大项表达式中不包含不包含对对应该行的最大项。应该行的最大项。(注意与最小项规则相反注意与最小项规则相反)例：例：F(A,B,C)，其最大项表达式应为：，其最大项表达式应为： F(A,B,C) = M1 M2 M5 = M3( 1,2,5 )显然显然 F(A,B,C) = M

46、0 M3 M4 M6 M7 = M3( 0,3,4,6,7 ) 如果给定函数用卡诺图表示，则函数的最大项表达式如果给定函数用卡诺图表示，则函数的最大项表达式可以通过卡诺图得到。可以通过卡诺图得到。最大项与原函数、反函数的关系最大项与原函数、反函数的关系对于对于 n 个变量的函数个变量的函数 F ，它共有，它共有2n个最大项，这些个最大项，这些最大项不是包含在原函数最大项不是包含在原函数 F 的最大项表达式中，就是包的最大项表达式中，就是包含在反函数含在反函数 F 的最大项表达式中。的最大项表达式中。可以证明：可以证明：F(x1,x2,x3, ,xn) F(x1,x2,x3, ,xn) = M

47、i = = 02n -1i = 0同一函数的最小项标准式与其最大项标准式的关系同一函数的最小项标准式与其最大项标准式的关系:同一逻辑函数的一种标准式变换成另一种标准式时，同一逻辑函数的一种标准式变换成另一种标准式时，互换互换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 m7F = F

48、 = m1 m4 m5 m6 m7 = m1 m4 m5 m6 m7 = M1 M4 M5 M6 M7 = M 3( 1,4,5,6,7 )2.5 逻辑函数的化简逻辑函数的化简 Simplification of Switching Expression一个逻辑函数对应着一个实现其逻辑功能的逻辑电路，一个逻辑函数对应着一个实现其逻辑功能的逻辑电路，当使该函数最简意味着使这个电路也最简。当使该函数最简意味着使这个电路也最简。最简逻辑电路：最简逻辑电路：门数最少；门的输入端最少；门的级门数最少；门的输入端最少；门的级 数最少。数最少。最简与或式：最简与或式：与项的数目最少；每个与项的变量个数与项的

49、数目最少；每个与项的变量个数 最少。最少。最简或与式：最简或与式：或项的数目最少；每个或项的变量个数或项的数目最少；每个或项的变量个数 最少。最少。例： F = AB ( BC ) AC BC = AB C对应两种逻辑电路图，如下11111ABCCABABB+CACB CAB(B+C)F=AB(B+C)+AC+BC&1ABABF=AB+C&C2.5.1 代数化简法：代数化简法：一、与或式的化简一、与或式的化简与或式化简常用的公式主要有四个：与或式化简常用的公式主要有四个： A + A = 1 A + AB = A + BAB + AB = A AB + AC + BC = AB

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

51、 B 消去反变量消去反变量。例：。例： F = AB + AC + BC = AB + (A + B)C = AB + AB C = AB + C 3. 消去法消去法利用公式：利用公式：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

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

53、C + BC + AB + AC = AB + BC + BC + AC = AB + BC + AC5. 综合法综合法 在一个函数的化简中同时用几种方法。例：在一个函数的化简中同时用几种方法。例： 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

54、 = A + BC + CB + BD + DB + CD = A + BC + CB + DB + CD = A + BC + DB + CD二、或与式的化简二、或与式的化简 或与式化简有两种方法：或与式化简有两种方法：例：例：F = A ( A + B )( A + D )( B + D )( A + C + E + H ) = A ( A + D )( B + D ) = AD ( B + D ) = AD1. 常规法常规法 常规法化简方式类似于与或式的化简，化简中常用的常规法化简方式类似于与或式的化简，化简中常用的公式主要有：公式主要有： ( A + B )( A + B ) = A

55、A ( A + B ) = A A ( A + B ) = AB ( A + B )( A + C )( B + C ) = ( A + B ) ( A + C )2. 利用最简与或式得到最简或与式利用最简与或式得到最简或与式 二次对偶法二次对偶法利用对偶规则，先求出利用对偶规则，先求出F的对偶式的对偶式F，再将对偶式，再将对偶式F 化简为化简为最简与或式最简与或式，最后再求一次对偶，最后再求一次对偶(F ) = F，则得到，则得到 F 最简或与式。最简或与式。例：例：F = (A + B)(A + B)(B + C)(C + D)(B + D) F = AB + AB + BC + CD +

56、 BD = A + BC + CD + BD = A + BC + CD则则 F = (F ) = A (B + C)(C + D) 二次求反法二次求反法利用反演规则，先求出利用反演规则，先求出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

57、 + ABC)(B + D) = AB + ABCD则则 F = F = (A + B)(A + B + C + D)2.5.2 卡诺图（卡诺图（Karnaugh MAP）法）法卡诺图逻辑函数卡诺图逻辑函数真值表的一种图形表示真值表的一种图形表示，利用卡诺，利用卡诺图可以有规律地化简逻辑函数表达式，并能直观地写出图可以有规律地化简逻辑函数表达式，并能直观地写出逻辑函数的最简式。逻辑函数的最简式。 一、卡诺图的构成一、卡诺图的构成 卡诺图是一种卡诺图是一种平面方格阵列图平面方格阵列图，下页给出了二变量、，下页给出了二变量、三变量、四变量、五变量和六变量的卡诺图。三变量、四变量、五变量和六变量的卡

58、诺图。单变量的卡诺图单变量的卡诺图二变量的卡诺图二变量的卡诺图分别对应着四个最小项分别对应着四个最小项 m0 = AB，m1 = AB， m2 = AB，m3 = AB。引入变量引入变量A，将区域分为两块，将区域分为两块AA分别对应着两个最小项分别对应着两个最小项 m0 = A m1 = A01A BA BA BA B再引入变量再引入变量B，将区域分为四块，将区域分为四块0123三变量的卡诺图三变量的卡诺图再引入变量再引入变量C，将区域分为八块，分别对应着，将区域分为八块，分别对应着8 个最小项个最小项：C=1A=102641375B=1m0=ABC，m1=ABC，m2=ABC，m3=ABC

59、, m4=ABC，m5=ABC，m6=ABC，m7=ABC。四变量的卡诺图四变量的卡诺图四变量四变量(A、B、C、D)的卡诺图，分别对应着的卡诺图，分别对应着16个最小项：个最小项：0412815139371511261410ABCDm0 = ABCD， m1 = ABCD， m2 = ABCD， m3 = ABCD, m4 = ABCD， m5 = ABCD， m6 = ABCD， m7 = ABCD, m8 = ABCD， m9 = ABCD， m10= ABCD, m11= ABCDm12= ABCD， m13= ABCD, m14= ABCD， m15= ABCD五变量的卡诺图五变量的

60、卡诺图五变量五变量(A、B、C、D、E)的卡诺图，分别对应着的卡诺图，分别对应着32个个最小项最小项。0412815139371511261410BCE16202824172129251923312718223026CDBA六变量的卡诺图六变量的卡诺图:有有64个最小项个最小项0412815139371511261410DF32364440333745413539474334384642ECB16202824172129251923312718223026D48526056495361575155635950546258CEFA卡诺图的构成特点：卡诺图的构成特点： 整个卡诺图总是被整个卡诺图总是被每个变量逐次地分成两半每个变量逐次地分成两半：原变量，：原变量，反变