第2章 逻辑代数基础

1、逻 辑 代 数 基 础第第 二二 章章逻辑代数是数字系统设计的理论基础和重要数学工具！逻辑代数是数字系统设计的理论基础和重要数学工具！逻辑代数是从哲学领域中的逻辑学发展而来的。逻辑代数是从哲学领域中的逻辑学发展而来的。18471847年年, ,英国数学家乔治英国数学家乔治布尔提出了用数学分析方法表布尔提出了用数学分析方法表示命题陈述的逻辑结构，并成功地将形式逻辑归结为一种代数示命题陈述的逻辑结构，并成功地将形式逻辑归结为一种代数演算，从而诞生了著名的演算，从而诞生了著名的“布尔代数布尔代数”。19381938年，年，克劳德克劳德向农将布尔代数应用于电话继电器的开向农将布尔代数应用于电话继电器的

2、开关电路，提出了关电路，提出了“开关代数开关代数”。随着电子技术的发展，集成电路逻辑门已经取代了机械触随着电子技术的发展，集成电路逻辑门已经取代了机械触点开关，故点开关，故“开关代数开关代数”这个术语已很少使用。为了与这个术语已很少使用。为了与“数字数字系统逻辑设计系统逻辑设计”这一术语相适应，人们更习惯于把开关代数叫这一术语相适应，人们更习惯于把开关代数叫做做逻辑代数。逻辑代数。本章知识要点：本章知识要点： 基本概念基本概念 基本定理和规则基本定理和规则 逻辑函数的表示形式逻辑函数的表示形式 逻辑函数的化简逻辑函数的化简 逻辑代数逻辑代数L L是一个封闭的代数系统，它由一个逻辑变量集是一个封

3、闭的代数系统，它由一个逻辑变量集K K，常量，常量0 0和和1 1以及以及“或或”、“与与”、“非非”三种基本运算所三种基本运算所构成，记为构成，记为L=K,+,L=K,+,-,0,1,-,0,1。该系统应满足下列公理。该系统应满足下列公理。 2.1 2.1 逻辑代数的基本概念逻辑代数的基本概念公公 理理 1 1 交交 换换 律律对于任意逻辑变量对于任意逻辑变量A、B，有，有A + B = B + A；AB = B A公公 理理 2 2 结结 合合 律律对于任意的对于任意的逻辑变量逻辑变量A、B、C，有，有(A + B) + C = A + ( B + C )(A + B) + C = A +

4、 ( B + C )( A( AB )B ) C = A C = A( B( B C ) C )公公 理理 3 3 分分 配配 律律对于任意的逻辑变量对于任意的逻辑变量A、B、C，有，有A + ( BC ) = (A + B)(A + C) ；A( B + C) = AB + AC公公 理理 4 01 4 01 律律对于任意逻辑变量对于任意逻辑变量A，有，有 A + 0 = A A + 0 = A ； A A 1 = A 1 = A A + 1 = 1 A + 1 = 1 ； A A 0 = 0 0 = 0 公理是一个代数系统的基本出发点，无需加以证明。公理是一个代数系统的基本出发点，无需加以

5、证明。0AA 1AAA公公 理理 5 5 互互 补补 律律对于任意逻辑变量对于任意逻辑变量A，存在唯一的，使得，存在唯一的，使得2.1.1 2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算逻辑代数和普通代数一样，是用字母表示其值可以变化逻辑代数和普通代数一样，是用字母表示其值可以变化的量，即变量。所不同的是：的量，即变量。所不同的是：1任何逻辑变量的取值只有两种可能性任何逻辑变量的取值只有两种可能性取值取值0 0或或取值取值1 1。 在普通代数中，变量的取值可以是任意实数，而逻辑代数是 一 种二值代数系统.2逻辑值逻辑值0 0和和1 1是用来表征矛盾的双方和判断事件真伪是用来表征矛盾的

6、双方和判断事件真伪的形式符号，无大小、正负之分。的形式符号，无大小、正负之分。 在数字系统中，开关的接通与断开，电压的高和低，信号的有和无，晶体管的导通与截止等两种稳定的物理状态，均可用1和0这两种不同的逻辑值来表征。一变量一变量二基本逻辑运算二基本逻辑运算 描述一个数字系统，必须反映一个复杂系统中各开关元件之间的联系，这种相互联系反映到数学上就是几种运算关系。逻辑代数中定义了逻辑代数中定义了“或或”、“与与” 、“非非”三种基本三种基本运算。运算。 1 1“或或”运算运算 如果决定某一事件是否发生的多个条件中，只要有一如果决定某一事件是否发生的多个条件中，只要有一个或一个以上条件成立，事件便

7、可发生，则这种因果关系个或一个以上条件成立，事件便可发生，则这种因果关系称之为称之为“或或”逻辑。逻辑。 例如，用两个开关并联控制一个灯的照明控制电路。 上图所示电路中，开关上图所示电路中，开关A和和B并联控制灯并联控制灯F。可以看出，当。可以看出，当开关开关A、B中有一个闭合或者两个均闭合时，灯中有一个闭合或者两个均闭合时，灯F即亮。因此即亮。因此，灯，灯F与开关与开关A、B之间的关系是之间的关系是“或或”逻辑关系。逻辑关系。 并联开关电路并联开关电路 ABF 用两个开关并联控制一个灯的电路如下图所示。用两个开关并联控制一个灯的电路如下图所示。逻辑代数中，逻辑代数中，“或或”逻辑用逻辑用“或

8、或”运算描述。其运算符运算描述。其运算符号为号为“+”+”，有时也用，有时也用“”“”表示。两变量表示。两变量“或或”运算的关系运算的关系可表示为可表示为F = A + B或者或者F = A B读作读作“F等于等于A或或B”。在下图所示开关并联电路中，假定开关断开用在下图所示开关并联电路中，假定开关断开用0表示，开关表示，开关闭合用闭合用1表示；灯灭用表示；灯灭用0表示，灯亮用表示，灯亮用1表示，则灯表示，则灯F与开关与开关A、B的关系如下表所示。的关系如下表所示。 即：A、B中只要有一个为中只要有一个为1，则，则F为为1；仅当；仅当A、B均为均为0时，时，F才为才为0。F 并联开关电路并联开

9、关电路 AB “或或”运算表运算表 A BF 0 0 0 1 1 0 1 10111“或或”运算的运算法则：运算的运算法则：0 + 0 = 01 + 0 = 10 + 1 = 11 + 1 = 1实现“或”运算关系的逻辑电路称为“或或”门门。 2 2“与与” 运算运算如果决定某一事件发生的多个条件必须同时具备，事如果决定某一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之为件才能发生，则这种因果关系称之为“与与”逻辑。逻辑。在逻辑代数中，“与”逻辑关系用“与”运算描述。其运算符号为“”，有时也用“”表示。两变量“与”运算关系可表示为F = AB或者F = AB即：即：若若A A

10、、B B均为均为1 1，则，则F F为为1 1；否则，；否则，F F为为0 0。 ABF 串联开关电路串联开关电路 假定在开关串联电路中，开关闭合状态用1表示，断开状态用0表示，灯亮用1表示，灯灭用0表示，则电路中灯F和开关A、B之间的关系即上表所示的“与”运算关系。 “与”逻辑关系如右表所示。 “或或”运算表运算表 A BF 0 0 0 1 1 0 1 10001“与与”运算的运算法则运算的运算法则:0 0 = 01 0 = 00 1 = 01 1 = 1实现实现“与与”运算关系的逻辑电运算关系的逻辑电路称为路称为“与与”门门。 3 3“非非” 运算运算 如果某一事件的发生取决于条件的否定，

11、即事件与事件如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果关系称为发生的条件之间构成矛盾，则这种因果关系称为“非非”逻辑。逻辑。在逻辑代数中，“非”逻辑用“非”运算描述。其运算符号为“”，有时也用“”表示。“非”运算的逻辑关系可表示为 或者 F = A，读作“F等于A非 ”。即：若若A为为0，则，则F为为1；若；若A为为1，则，则F为为0。AF “非非”逻辑关系可用下表逻辑关系可用下表: “非非”运算表运算表 A F 0 1 10例如，在下图所示电路中，开关与灯并联。显然，仅当开关断开时，灯亮；一旦开关闭合，则灯灭。令开关断开用令开关断开用0表表示，开关闭合

12、用示，开关闭合用1表示，灯亮用表示，灯亮用1表示，灯灭用表示，灯灭用0表示，则电路表示，则电路中灯中灯F与开关与开关A的关系即为上表所示的关系即为上表所示“非非”运算关系。运算关系。 “非非”运算的运算法则：运算的运算法则：实现“非”运算功能的逻辑电路称为“非非”门门，有时又称为“反相器反相器”。1001A开关与灯并联电路 F2.1.2 2.1.2 逻辑函数逻辑函数逻辑代数中函数的定义与普通代数中函数的定义类似，即即随自变量变化的因变量随自变量变化的因变量。但和普通代数中函数的概念相比，逻辑函数具有如下特点特点： 1逻辑函数和逻辑变量一样，取值只有逻辑函数和逻辑变量一样，取值只有0和和1两种两

13、种可能可能 ； 2函数和变量之间的关系是由函数和变量之间的关系是由“或或”、“与与”、“非非”三种基本运算决定的三种基本运算决定的 。 一、逻辑函数的定义一、逻辑函数的定义图中，图中，F被称为被称为A1，A2，An的逻辑函数，记为的逻辑函数，记为F = f( A1，A2，An )逻辑电路输出函数的取值是由逻辑变量的取值和电路本逻辑电路输出函数的取值是由逻辑变量的取值和电路本身的结构决定的身的结构决定的。任何一个逻辑电路的功能都可由相应的逻辑函数完全描述，因此，可借助抽象的代数表达式对电路加以分析研究。 从数字系统研究的角度看，逻辑函数的定义如下从数字系统研究的角度看，逻辑函数的定义如下:设某一

14、逻辑电路的输入逻辑变量为A1，A2，An，输出逻辑变量为F，如下图所示。逻辑函数和普通代数中的函数一样存在是否相等的问题逻辑函数和普通代数中的函数一样存在是否相等的问题。 什么叫做两个逻辑函数相等呢？什么叫做两个逻辑函数相等呢？设有两个相同变量的逻辑函数F1 = f1( A 1,A 2, ,A n)F2 = f2( A 1,A 2, ,A n)若对应于逻辑变量若对应于逻辑变量 A1 ,A2 , , An的任何一组取值，的任何一组取值，F1和和F2的值都相同，则称函数的值都相同，则称函数F1和和F2相等，记作相等，记作F1 = F2 。如何判断两个逻辑函数是否相等？如何判断两个逻辑函数是否相等？

15、通常有两种方法,一种方法是真值表法真值表法，另一种方法是代代数法数法。二、逻辑函数的相等二、逻辑函数的相等三、三、 逻辑函数的表示法逻辑函数的表示法该逻辑表达式描述了一个两变量的逻辑函数F。函数函数F和变量和变量A、B的关系是：的关系是：当变量当变量A和和B取值不同时，函数取值不同时，函数F的值为的值为“1”； 取值相同时，函数取值相同时，函数F的值为的值为“0”。BABABA,fF逻辑表达式是由逻辑变量和“或”、“与”、“非”3种运算符以及括号所构成的式子。例如1 1、逻辑表达式、逻辑表达式 如何对逻辑功能进行描述？如何对逻辑功能进行描述？常用的方法有逻辑表达式、真值表、卡诺图常用的方法有逻

16、辑表达式、真值表、卡诺图3种种。 逻辑表达式的简写逻辑表达式的简写: 1.“非非”运算符下可不加括号，如运算符下可不加括号，如 ， 等。等。BABA2.“与与”运算符一般可省略，如运算符一般可省略，如AB可写成可写成AB。 高高低低3.在一个表达式中，如果既有在一个表达式中，如果既有“与与”运算又有运算又有“或或”运运算，则按算，则按先先“与与”后后“或或”的规则进行运算，可省去括号的规则进行运算，可省去括号, ,如如(AB)+(CD)可写为可写为AB+CD。注意注意:(A+B)(C+D):(A+B)(C+D)不能省略括号不能省略括号, ,即不能写成即不能写成A+BC+DA+BC+D！ 运算优

17、先法则运算优先法则： ( ) +4. (A+B)+C或者或者A+(B+C)可用可用A+B+C代替；代替；(AB)C或或者者A(BC)可用可用ABC代替。代替。 2 2、真值表、真值表 依次列出一个逻辑函数的所有输入变量取值组合及其相依次列出一个逻辑函数的所有输入变量取值组合及其相应函数值的表格称为真值表。应函数值的表格称为真值表。由于一个逻辑变量有0和1两种可能的取值，n个逻辑变量共有2n种可能的取值组合。因此，一个一个n个变量的逻辑函数，个变量的逻辑函数，其真值表有其真值表有2n行。行。真值表由两部分组成：真值表由两部分组成：左边一栏列出变量的所有取左边一栏列出变量的所有取值组合，为了不发生

18、遗漏，通常各值组合，为了不发生遗漏，通常各变量取值组合按二进制数码顺序给变量取值组合按二进制数码顺序给出；右边一栏为逻辑函数值。出；右边一栏为逻辑函数值。例如，逻辑函数例如，逻辑函数 的真值表如右表所示。的真值表如右表所示。 CABAF 函数函数F的真值的真值表表 A B CF 0 0 0 0 0 1 0 1 0 0 1 11 0 01 0 11 1 01 1 1010111003 3、卡诺图、卡诺图 卡诺图是由表示逻辑变量所有取值组合的小方格卡诺图是由表示逻辑变量所有取值组合的小方格所构成的平面图所构成的平面图。这种用图形描述逻辑函数的方法，在逻辑函数化简中十分有用，将在后面结合函数化简问题

19、进行详细介绍。 描述逻辑逻辑函数的3种方法各有特点,可用于不同场合。但针对某个具体问题而言，它们仅仅是同一问题的不同描述形式，相互之间可以很方便地进行变换。 2.1.3 2.1.3 复合逻辑复合逻辑 实际应用中广泛采用“与非”门、“或非”门、“与或非”门、“异或”门等门电路。这些门电路输出和输入之间这些门电路输出和输入之间的逻辑关系可由的逻辑关系可由3 3种基本运算构成的复合运算来描述，通常将种基本运算构成的复合运算来描述，通常将这种逻辑关系称为这种逻辑关系称为复合逻辑复合逻辑，相应的逻辑门则称为，相应的逻辑门则称为复合门。复合门。 一、与非逻辑一、与非逻辑 与非逻辑是由与、非两种逻辑复合形成

20、的，可用逻辑函数表示为逻辑功能逻辑功能：只要变量只要变量A A、B B、C C、中有一个为中有一个为0 0，则函数，则函数F F为为1 1；仅当变量；仅当变量A A、B B、C C、全部为全部为1 1时，函数时，函数F F为为0 0。实现与非逻辑的门电路称为实现与非逻辑的门电路称为“与非与非”门门。 CBAF 由于与非逻辑又可实现3种基本逻辑，所以，只要有了与非门便可组成实现各种逻辑功能的电路，通常称与非门为通用门通用门。采用与非逻辑可以减少逻辑电路中门的种类，提高标准化程度。 与与: :BABA1BAF 或或: :BABA1B1AF 非非: :A1AF 由定理由定理 不难看出，不难看出，“与

21、与”之之“非非”可以产可以产生生“或或”的关系。因此，实际上只要有了与非逻辑便可实的关系。因此，实际上只要有了与非逻辑便可实现与、或、非现与、或、非3 3种基本逻辑。种基本逻辑。 以两变量与非逻辑为例：以两变量与非逻辑为例： BABA二二、或非逻辑或非逻辑逻辑功能：逻辑功能：只要变量A、B、C中有一个为1，则函数F为0；仅当变量A、B、C全部为0时，函数F为1。实现或非逻辑的门电路称为“或非或非”门门。 或非逻辑是由或、非两种逻辑复合或、非两种逻辑复合形成的，可用逻辑函数表示为 CBAF与：与：BABA0B0AF或或: :BABA0BAF非非: : A0AF 同样，由定理 可知，“或”之“非”

22、可以产生“与”的关系。因此，只要有了或非逻辑也可以实现与、或、非3种基本逻辑。以两变量或非逻辑为例： BABA或非门同样是一种通用门。通用门。三、与或非逻辑三、与或非逻辑逻辑功能：逻辑功能：仅当每一个仅当每一个“与项与项”均为均为0 0时，时，F F才能为才能为1 1，否则否则F F为为0 0。实现与或非功能的门电路称为。实现与或非功能的门电路称为“与或非与或非”门。门。 显然，可以仅用与或非门组成实现各种功能的逻辑电路。但实际应用中这样做一般会很不经济，所以，与或非门主要用来实现与或非形式的函数。必要时可将逻辑函数表达式的形式变换成与或非的形式。 与或非逻辑是由3种基本逻辑复合形成的，逻辑函

23、数表达式的形式为 CDABF四、异或逻辑及同或逻辑四、异或逻辑及同或逻辑逻辑功能：逻辑功能：变量变量A A、B B取值相同，取值相同，F F为为0 0；变量；变量A A、B B取值取值相异，相异，F F为为1 1。实现异或运算的逻辑门称为“异或门异或门”。 1 1异或逻辑异或逻辑 当多个变量进行异或运算时，可用两两运算的结果再运两两运算的结果再运算算，也可两两依次运算。两两依次运算。异或逻辑是一种两变量逻辑关系两变量逻辑关系，可用逻辑函数表示为 BABABAF 根据异或逻辑的定义可知：A 0 = AA 0 = AA 1 =A 1 =A A = 0A A = 0A = 1 A = 1 AA特性：

24、特性：在进行异或运算的多个变量中，若有奇数个变量在进行异或运算的多个变量中，若有奇数个变量的值为的值为1 1，则运算结果为，则运算结果为1 1；若有偶数个变量的值为；若有偶数个变量的值为1 1，则运算，则运算结果为结果为0 0。 例如， F = A B C D= (A B) (C D)( (两两运算的结果再运算两两运算的结果再运算) )=(A B) C D( (两两依次运算两两依次运算) ) 2 2同或逻辑同或逻辑功能逻辑功能逻辑：变量变量A A、B B取值相同，取值相同，F F为为1 1；变量；变量A A、B B取值相取值相异，异，F F为为0 0。实现同或运算的逻辑门称为。实现同或运算的逻

25、辑门称为“同或门同或门”。同或逻辑也是一种两变量逻辑关系，其逻辑函数表达式为同或逻辑也是一种两变量逻辑关系，其逻辑函数表达式为 F = A B = + AB 式中，式中，“”为同或运算的运算符。为同或运算的运算符。 BA两者有区别吗两者有区别吗？同或逻辑与异或逻辑的关系既互为相反，又互为对偶同或逻辑与异或逻辑的关系既互为相反，又互为对偶。即即：由于同或实际上是异或之非，所以实际应用中通常用异或门异或门+ +非门非门实现同或运算。 特性：特性：当多个变量进行同或运算时，若有奇数个变量的当多个变量进行同或运算时，若有奇数个变量的值为值为0，则运算结果为，则运算结果为0；反之，若有偶数个变量的值为；

26、反之，若有偶数个变量的值为0，则运算结果为则运算结果为1。 BAABBA B)A)(B(A B)ABA(B)(ABABAAB )BB)(AA( BABA BA e?2.2 2.2 逻辑代数的基本定理和规则逻辑代数的基本定理和规则 2.2.1 2.2.1 基本定理基本定理 定理定理10 + 0 = 01 + 0 = 10 0 = 01 0 = 00 + 1 = 11 + 1 = 10 1 = 01 1 = 1证明证明：在公理4中，A表示集合K中的任意元素，因而可以是0或1。用0和1代入公理4中的A，即可得到上述关系。 如果以如果以1和和0代替公理代替公理5中的中的A，则可得到如下推论：，则可得到

27、如下推论： 0110 定理定理2A + A = A ；A A = A 定理定理3A + A B = A；A ( A + B ) = A4 A 5 0A3 )A(AA5 )A(AA)(A4 1A)(AAA 公理公理公理公理公理证明4 A 4 1A1 1)(BA3 B)(1A4 BA1ABAA 公理公理公理公理公理证明 4 BA5 B)1(A3 B)(A)A(ABAA 证明公理公理公理AX :51AA 0AA 1XA 0XA XA 的唯一性有根据公理但是因而令证明AA 5定理BA B)A(A BABAA 4定理4 15 1A21 BB A4 BAB 2 BABABABA 公理公理，公理）（公理）（

28、公理）（）（）（由于证明 BABA BABA 6定理1 051 00 2 BBAABABABA 定理，公理公理）（）（而且 BABA 5的唯一性可得根据公理ABABA A BABA 7）（）（定理 4 A 5 1A3 BBA BABA 公理公理公理）（证明）CA(）B(A C)(B）CA(）BA（ CABACBCABA 8定理 41 CA BA3 B)C(1A C)B(1A 1 CBA CACBABA 3 ACBACB CABA 5 )A(ACB CABA CBCABA ，公理公理公理公理公理证明2.2.2 2.2.2 重要规则重要规则 3 3条重要规则条重要规则: :代入规则、反演规则、对偶

29、规则代入规则、反演规则、对偶规则例如例如，给定逻辑等式A(B+C)=AB+AC，若等式中的C都用(C+D)代替，则该逻辑等式仍然成立，即AB+(C+D)= AB+A(C+D)代入规则的正确性是显然的，因为任何逻辑函数都和逻辑变量一样，只有0和1两种可能的取值。 代入规则：代入规则：任何一个含有变量任何一个含有变量A的逻辑等式的逻辑等式,如果将所有如果将所有出现出现A的位置都代之以同一个逻辑函数的位置都代之以同一个逻辑函数F，则等式仍然成立。，则等式仍然成立。一、代入规则一、代入规则 代入规则的意义：代入规则的意义：利用代入规则可以将逻辑代数公理、定理中的变量用任意函数代替，从而推导出更多的等式

30、。这些等式可直接当作公使用，无需另加证明。注意：注意：使用代入规则时,必须将等式中所有出现同一变量的地方均以同一函数代替，否则代入后的等式将不成立。例如，用逻辑函数 代替公理 中的变量A，便可得到等式 即一个函数和其反函数进行“或”运算，其结果为1。1AA1= )A ,A ,(Af + )A ,A,(A fn21n21)A，,A,f(A = Fn21二、反演规则二、反演规则 反演规则实际上是定理反演规则实际上是定理6的推广，可通过定理的推广，可通过定理6和代入规和代入规则得到证明。则得到证明。例如，已知函数，根据反演规则有 D)C()B(AFDCBAF反演规则：反演规则：若将逻辑函数表达式F中

31、所有的“”变成“+”，“+”变成“”；“0”变成“1”，“1”变成“0”；原变量变成反变量，反变量变成原变量。并保持原函数中的运算顺序不变，则所得到的新的函数为原函数F的反函数 。F即:“” “+”，“0” “1”，原变量，原变量 反变量反变量注意注意: 使用反演规则时，应保持原函数式中运算符号的优先顺序不变。三、对偶规则三、对偶规则如果将逻辑函数表达式F中所有的“”变成变成“+”,“+”变变成成“”，“0”变成变成“1”，“1”变成变成“0”，并保持原函数中，并保持原函数中的运算顺序不变的运算顺序不变，则所得到的新的逻辑表达式称为函数F的对偶式，并记作F。例如，例如，已知函数，根据反演规则得

32、到的反函数应该是 而不应该是！错误！错误E)D(CBAFEDCBAF)ED(CBAF 注意：注意： 1、如果、如果F的对偶式是的对偶式是F，则，则F的对偶式就是的对偶式就是F。即，。即，(F)=F,可见可见F和和F互为对偶式。互为对偶式。 2 2、一般来说，一般来说，F F与对偶式与对偶式FF是不相等的！但不排除特是不相等的！但不排除特殊！殊！ 若逻辑函数表达式的对偶式就是原函数表达式本身，若逻辑函数表达式的对偶式就是原函数表达式本身，即即F=F，则称函数则称函数F为为自对偶函数自对偶函数。3 3、求逻辑表达式的对偶式时，同样要保持原函数的运、求逻辑表达式的对偶式时，同样要保持原函数的运算顺序

33、不变。算顺序不变。 根据对偶规则，当已证明某两个逻辑表达式相等时，即可知道它们的对偶式也相等。显然，利用对偶规则可以使定理、公式的证明减少一半。 对偶规则：对偶规则：若两个逻辑函数表达式若两个逻辑函数表达式F和和G相等，则其对相等，则其对偶式偶式F和和G也相等。也相等。例如，已知 根据对偶规则对等式两端的表达式取对偶式，即可得到等式 ABAABACCBC）（）（）（）（CABA )(CABA CB2.3 2.3 逻辑函数表达式的形式与变换逻辑函数表达式的形式与变换 任何一个逻辑函数的表达式形式都不是唯一的。从应用任何一个逻辑函数的表达式形式都不是唯一的。从应用的角度出发讨论基本形式、标准形式及

34、其相互转换。的角度出发讨论基本形式、标准形式及其相互转换。 2.3.1 2.3.1 逻辑函数表达式的逻辑函数表达式的两种两种基本形式基本形式 两种基本形式：两种基本形式：指指“与与- -或或”表达式和表达式和“或或- -与与”表达式表达式。 一一、“与与- -或或”表达式表达式 “与与-或或”表达式：是指由若干表达式：是指由若干“与项与项”进行进行“或或”运算运算构成的表达式。构成的表达式。每个每个“与项与项”可以是单个变量的原变量或者可以是单个变量的原变量或者反变量，也可由多个原变量或者反变量相反变量，也可由多个原变量或者反变量相“与与”组成。组成。 例如，例如， 均为均为“与项与项”，将这

35、，将这3个个“与项与项”相相“或或”便可构成一个便可构成一个3变量函数的变量函数的“与或与或”表达式。即表达式。即 CCBABA、CCBABAF二二、“或或- -与与”表达式表达式 注意：注意： “与项与项”有时又被称为有时又被称为“积项积项”，相应地，相应地“与与-或或”表达式表达式又称为又称为“积之和积之和”表达式。表达式。 “或项或项”有时又被称为有时又被称为“和项和项”，相应地，相应地“或或与与”表达表达式又称为式又称为“和之积和之积”表达式。表达式。 “或或-与与”表达式：是指由若干表达式：是指由若干“或项或项”进行进行“与与”运算构运算构成的表达式。成的表达式。 每个每个“或项或项

36、”可以是单个变量的原变量或者反变量，也可可以是单个变量的原变量或者反变量，也可以由多个原变量或者反变量相以由多个原变量或者反变量相“或或”组成。组成。C)DB)(ACB)(BA(D)C,B,F(A, 例如， 、 、 、D 均为“或项”，将这4个“或项”相“与”便可构成一个4变量函数的“或-与”表达式。即BA CB CBA 该逻辑函数是该逻辑函数是“与与或或”式？式？不是！不是！是是“或或与与”式？式？也不是！也不是！但不论什么形式都可以变换成两种基本形式。但不论什么形式都可以变换成两种基本形式。 2.3.2 2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 逻辑函数表达式可以被表示

37、成任意的混合形式。逻辑函数表达式可以被表示成任意的混合形式。例如： B)CBC)(AB(AC)B,F(A, 逻辑函数的两种基本形式都不是唯一的。逻辑函数的两种基本形式都不是唯一的。例如例如 为了在逻辑问题的研究中使逻辑功能能和唯一的逻辑表达为了在逻辑问题的研究中使逻辑功能能和唯一的逻辑表达式对应，引入了逻辑函数表达式的式对应，引入了逻辑函数表达式的标准形式标准形式。逻辑函数表达式。逻辑函数表达式的标准形式是建立在的标准形式是建立在最小项最小项和和最大项最大项概念的基础之上的。概念的基础之上的。 CAABBCCAABF一、最小项和最大项一、最小项和最大项 定义定义 ：如果一个具有如果一个具有n个

38、变量的函数的个变量的函数的“与项与项”包含全包含全部部n个变量，每个变量都以原变量或反变量形式出现一次，个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次，则该且仅出现一次，则该“与项与项”被称为被称为最小项最小项。有时又将最小。有时又将最小项称为项称为标准标准“与项与项” 。 数目：数目： n个变量可以构成个变量可以构成2n个最小项。个最小项。 例如，3个变量A、B、C可以构成、 、 A B C共8个最小项。 CBACBA1 1最小项最小项（掌握（掌握4 4点：定义、数目、简写、性质！）点：定义、数目、简写、性质！）简写：简写：用用mi表示最小项。表示最小项。下标下标i i的取值规

39、则是：的取值规则是：按照变量顺序将最小项中的原变按照变量顺序将最小项中的原变量用量用1 1表示，反变量用表示，反变量用0 0表示，由此得到一个二进制数，与表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标该二进制数对应的十进制数即下标i i的值。的值。 例如，例如，3变量变量A、B、C构成的最小项构成的最小项 可用可用 m5 表表示。因为示。因为 m5 (5)10 1 0 1ACCBAB 在由在由n个变量构成的任意个变量构成的任意“与项与项”中，最小项是使其值为中，最小项是使其值为1的变量取值组合数最少的一种的变量取值组合数最少的一种“与项与项”，这也就是最小项，这也就是最小项名字的

40、由来。名字的由来。 （4） 性质性质- 最小项具有四条性质 性质性质1 任意一个最小项，其相应变量有且仅有一种取值任意一个最小项，其相应变量有且仅有一种取值使这个最小项的值为使这个最小项的值为1。并且，最小项不同，使其值为。并且，最小项不同，使其值为1的变的变量取值不同。量取值不同。 性质性质2 相同变量构成的两个不同最小项相相同变量构成的两个不同最小项相“与与” 为为0。 因为任何一种变量取值都不可能使两个不同最小项同时因为任何一种变量取值都不可能使两个不同最小项同时为为1，故相，故相“与与”为为0。 即即 mi mj = 0 性质性质3： n个变量的全部最小项相个变量的全部最小项相“或或”

41、为为1。 通常借用数学中的累加符号通常借用数学中的累加符号“”，将其记为，将其记为1n20i1mi性质性质4： n个变量构成的最小项有个变量构成的最小项有n个相邻最小项。个相邻最小项。 相邻最小项：相邻最小项：是指除一个变量互为相反外，其余部分均相同的最小项。例如 ，三变量最小项A B C和 。 BCA 定义定义：如果一个具有如果一个具有n个变量函数的个变量函数的“或项或项”包含全部包含全部n个变量，每个变量都以原变量或反变量形式出现一次，且个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次，则该仅出现一次，则该“或项或项”被称为最大项。有时又将最大被称为最大项。有时又将最大项称为标

42、准项称为标准“或项或项”。 2 2最大项最大项 数目：数目：n个变量可以构成个变量可以构成2n 个最大项。个最大项。 例如，3个变量A、B、C可构成、 共8个最大项。 CBACBACBA性质：性质：最大项具有4条性质。 性质性质1 任意一个最大项，其相应变量有且仅有一种取值任意一个最大项，其相应变量有且仅有一种取值使这个最大项的值为使这个最大项的值为0 0。并且，最大项不同，使其值为。并且，最大项不同，使其值为0 0的变的变量取值不同。量取值不同。 简写：简写：用用Mi表示最大项。表示最大项。下标下标i i的取值规则是的取值规则是：将最大项中的原变量用将最大项中的原变量用0 0表示，反表示，反

43、变量用变量用1 1表示，由此得到一个二进制数，与该二进制数对应的表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标十进制数即下标 i i 的值。例如，的值。例如，3 3变量变量A A、B B、C C构成的最大项构成的最大项 可用可用 M M5 5 表示。CBA在n个变量构成的任意“或项”中，最大项是使其值为1的变量取值组合数最多的一种“或项”，因而将其称为最大项。最大项。 性质性质2 相同变量构成的两个不同最大项相同变量构成的两个不同最大项相相“或或”为为1。 因为任何一种变量取值都不可能使两个不同最大项同时为0，故相“或”为1。即 M i + M j = 1 性质性质3 n个变量的

44、全部最大项相个变量的全部最大项相“与与”为为0。通常借用数学中的累乘符号“”将其记为 010ii2nM性质性质4 n个变量构成的最大项有个变量构成的最大项有n个相邻最大项。个相邻最大项。 相邻最大项是指除一个变量互为相反外，其余变量均相同的最大项。 两变量最小项、最大项的真值表如下两变量最小项、最大项的真值表如下: : m2 000101001000M3 M2 M 1 M 0 m 3 m1m 0 001011101101101101110 00 11 01 1A B最最 大大 项项 最最 小小 项项 变变 量量2变量最小项、最大项真值表变量最小项、最大项真值表 BABABAABBABABABA

45、该真值表反映了最小项、最大项的有关性质。该真值表反映了最小项、最大项的有关性质。 3最小项和最大项的关系最小项和最大项的关系 在同一问题中，下标相同的最小项和最大项互为反函数。在同一问题中，下标相同的最小项和最大项互为反函数。或者说，相同变量构成的最小项mi和最大项Mi之间存在互补关系。即 或者 iiMm iiMm 例如，由例如，由3 3变量变量A A、B B、C C构成的最小项构成的最小项m m3 3和最大项和最大项M M3 3之间有之间有 33MCBABCAm33mBCACBAM二、逻辑函数表达式的标准形式二、逻辑函数表达式的标准形式 逻辑函数表达式的标准形式有标准标准“与与-或或”表达式

46、表达式和和标准标准“或或-与与”表达式表达式两种类型两种类型。 1标准标准“与与 - 或或”表达式表达式 由若干最小项相由若干最小项相“或或”构成的逻辑表达式称为标准构成的逻辑表达式称为标准“与与-或或”表达式，也叫做最小项表达式。表达式，也叫做最小项表达式。 该函数表达式又可简写为 F(A，B，C) = m1 + m2 + m4 + m7 = m(1,2,4,7)例如，一个3变量函数的标准“与-或”表达式 ABCCBACBACBAC)B,F(A,2标准标准“或或-与与”表达式表达式 由若干最大项相由若干最大项相“与与”构成的逻辑表达式称为标准构成的逻辑表达式称为标准“或或-与与”表达式，也叫

47、做最大项表达式表达式，也叫做最大项表达式 。CBA 例如， 、 、 为3变量构成的3个最大项，对这3个最大项进行“与”运算，即可得到一个3变量函数的标准“或-与”表达式 CBACBA)CBA)(CBA)(CB(AC),B,F(A 该表达式又可简写为 M(1,5,7)MMMC)B,F(A,7512.3.3 2.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 将一个任意逻辑函数表达式转换成标准表达式有两种常用方法: 代数转换法代数转换法，真值表转换法真值表转换法。 一、代数转换法一、代数转换法 1 . 求标准求标准“与与-或或” 式式一般步骤如下：一般步骤如下： 第一步第一步：将函数表达式变换成

48、一般“与-或”表达式。 所谓代数转换法，就是利用逻辑代数的公理、定理和规所谓代数转换法，就是利用逻辑代数的公理、定理和规则进行逻辑变换，将函数表达式从一种形式变换为另一种形则进行逻辑变换，将函数表达式从一种形式变换为另一种形式。式。 第二步：第二步：反复使用将表达式中所有非最小项的“与项”扩展成最小项。 )YX(YX例如，例如，将逻辑函数表达式将逻辑函数表达式 转转换成标准换成标准“与与-或或”表达式。表达式。 AB)CBB(AC)B,F(A,C)C( ABA)BCA(B)BC(AC)C(BAC)B,F(A,ABCC ABABCBCABCACBACBACBAABCCABBCACBACBA解解

49、第一步：第一步：将函数表达式变换成将函数表达式变换成“与与- -或或”表达式。即表达式。即ABCBBAABC)BB)(A(ABBCCABAAB)CBB(A C)B,F(A,第二步：第二步：把把“与与- -或或”式中非最小项的式中非最小项的“与项与项”扩展扩展成最小项。具体地说，若某成最小项。具体地说，若某“与项与项”缺少函数变量缺少函数变量Y Y，则，则用用( () )和这一项相与，并将其拆开成两项。即和这一项相与，并将其拆开成两项。即 YY所得标准所得标准“与与-或或”式的简写形式为式的简写形式为 当给出函数表达式已经是“与-或”表达式时，可直接进行第二步。 一般步骤：一般步骤：第一步：第一

50、步：将函数表达式转换成一般“或-与”表达式。 第二步：第二步：反复利用定理把表达式中所有非最大项的“或项”扩展成最大项。 )BB)(A(AA76310mmmmmC)B,F(A,)(0,1,3,6,7m 2 . 求一个函数的标准求一个函数的标准“或或-与与” 式式 例如例如 将逻辑函数表达式 变换成标准或与表达式。FABBCAC解解 第一步：第一步：将函数表达式变换成将函数表达式变换成“或或- -与与”表达式。即表达式。即FABBCAC(AB)(BC)AC(AB)(BC)A(AB)(BC)C(ABA)(B)(ABC)(BCC)(ABC)(ABC)(BC)CA第二步：第二步：将所得或将所得或与表达

51、中的非最大项扩展成最大项。即与表达中的非最大项扩展成最大项。即F(ABC)(ABC)(BC)(ABC)(ABC)(ABC)(ABC)(ABC)(ABC)M(2,6)二、真值表转换法二、真值表转换法 具体：具体：真值表上使函数值为真值表上使函数值为1的变量取值组合对应的最的变量取值组合对应的最小项相小项相“或或”,即可构成一个函数的标准即可构成一个函数的标准“与与-或或”式式 。 逻辑函数的最小项表达式与真值表具有一逻辑函数的最小项表达式与真值表具有一 一对应的关系！一对应的关系！ 假定函数假定函数F的真值表中有的真值表中有k组变量取值使组变量取值使F的值为的值为1，其他变，其他变量取值下量取值

52、下F的值为的值为0，那么，函数，那么，函数F的最小项表达式由这的最小项表达式由这k组变量组变量取值对应的取值对应的k个最小项相或组成。个最小项相或组成。 因此，可以通过函数的真值表写出最小项表达式。 1 . 求标准求标准“与与-或或” 式式1 0 0 1 1 0 1 1 0 1 1 0 A B C F 1 1 0 11 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 函数函数F的真值表的真值表 解解:首先，列出首先，列出F的真值表如下表所示，然后，根据真的真值表如下表所示，然后，根据真值表可直接写出值表可直接写出F的最小项表达式的最小项表达式 m(2,4,5,6)C)B,F(A,)

53、6 , 5 , 4 , 2(),(mCBAF例如，例如，将函数表达式变换成标准将函数表达式变换成标准“与与-或或”表达式。表达式。 CBBAC)B,F(A, 具体：具体：真值表上使函数值为真值表上使函数值为0的变量取值组合对应的最的变量取值组合对应的最大项相大项相“与与”即可构成一个函数的标准即可构成一个函数的标准“或或-与与”式式 。 2 . 2 . 求一个函数的标准求一个函数的标准“或或- -与与” ” 式式 逻辑函数的最大项表达式与真值表之间同样具有一一对应逻辑函数的最大项表达式与真值表之间同样具有一一对应的关系。的关系。 假定在函数假定在函数F的真值表中有的真值表中有p组变量取值使组变

54、量取值使F的值为的值为0，其他，其他变量取值下变量取值下F的值为的值为1，那么，函数，那么，函数F的最大项表达式由这的最大项表达式由这p组组变量取值对应的变量取值对应的p个最大项个最大项“相与相与”组成。组成。解：解：首先，列出F的真值表如下表所示。然后，根据真值表直接写出F的最大项表达式 )7 , 6 , 5 , 2 , 0(),(MCBAF) 7 , 6 , 5 , 2 , 0 (),(MCBAF 函数F的真值表 1010 0111 0100 1001 1110 1100 ABC F 0000 0011 例如，例如，将函数表达式 表示成最大项表达式的形式。 CBACACBAF),(由于函数

55、的真值表与函数的两种标准表达式之间存在由于函数的真值表与函数的两种标准表达式之间存在一一对应的关系。一一对应的关系。 任何个逻辑函数的真值表是唯一的！任何个逻辑函数的真值表是唯一的！任何一个逻辑函数的两种标准形式也是唯一的！任何一个逻辑函数的两种标准形式也是唯一的！逻辑函数表达式的唯一性给我们分析和研究逻辑问题逻辑函数表达式的唯一性给我们分析和研究逻辑问题带来了很大的方便。带来了很大的方便。 2.4 2.4 逻辑函数化简逻辑函数化简 实现某一逻辑功能的逻辑电路的复杂性与描述该功能的实现某一逻辑功能的逻辑电路的复杂性与描述该功能的逻辑表达式的复杂性直接相关。一般说，逻辑函数表达式越逻辑表达式的复

56、杂性直接相关。一般说，逻辑函数表达式越简单，设计出来的相应逻辑电路也就越简单。简单，设计出来的相应逻辑电路也就越简单。 为了降低系统成本、减小复杂度、提高可靠性，必须对为了降低系统成本、减小复杂度、提高可靠性，必须对逻辑函数进行化简。逻辑函数进行化简。 由于由于“与与-或或”表达式表达式和和“或或-与与”表达式表达式可以很方便地可以很方便地转换成任何其他所要求的形式。因此，从这两种基本形式出转换成任何其他所要求的形式。因此，从这两种基本形式出发讨论函数化简问题，并将重点放在发讨论函数化简问题，并将重点放在“与与-或或”表达式的化表达式的化简上。简上。 逻辑函数化简有逻辑函数化简有2种常用方法：

57、种常用方法：代数化简法、卡诺图化代数化简法、卡诺图化简法。简法。 2.4.1 2.4.1 代数化简法代数化简法 代数化简法就是运用逻辑代数的公理、定理和规则对逻代数化简法就是运用逻辑代数的公理、定理和规则对逻辑函数进行化简的方法辑函数进行化简的方法。 无固定的步骤可以遵循，主要取决于对逻辑代数中公理无固定的步骤可以遵循，主要取决于对逻辑代数中公理、定理和规则的熟练掌握及灵活运用的程度。、定理和规则的熟练掌握及灵活运用的程度。 一、一、“与与-或或”表达式的化简表达式的化简 最简最简“与与-或或”表达式应满足两个条件：表达式应满足两个条件： 1表达式中的表达式中的“与与”项个数最少；项个数最少；

58、 2在满足上述条件的前提下，每个在满足上述条件的前提下，每个“与与”项中的变量项中的变量个数最少。个数最少。 满足上述两个条件可以使相应逻辑电路中所需门的数量以及门的满足上述两个条件可以使相应逻辑电路中所需门的数量以及门的输入端个数均为最少，从而使电路最经济。输入端个数均为最少，从而使电路最经济。 化简举例化简举例例例1 化简化简 CBCAABF解：解： C)BA(ABCBCAABFCABC ABAB例例2 化简化简 CBADCBDDBCF解：解： CBADCBDBCCBADCBDDBCF CBADBCDBC DBCBADDBC 例例3 化简化简 CBACBACBAF)( )(解解 CBACC

59、BACACBACBACBACBACBACBACBAF )()( )()( )()(二、二、“或或-与与”表达式的化简表达式的化简 最简最简“或或-与与”表达式应满足两个条件：表达式应满足两个条件： 1表达式中的表达式中的“或或”项个数最少；项个数最少； 2在满足上述条件的前提下，每个在满足上述条件的前提下，每个“或或”项中的变量项中的变量个数最少。个数最少。 用代数化简法化简用代数化简法化简“或或-与与”表达式可直接运用公理、表达式可直接运用公理、定理中的定理中的“或或-与与”形式进行化简。形式进行化简。 当对公理、定理中的当对公理、定理中的“或或-与与”形式不太熟悉时，可以形式不太熟悉时，可

60、以采用两次对偶法。采用两次对偶法。具体如下：具体如下： 第一步：第一步：对对“或或-与与”表达式表示的函数表达式表示的函数F求对偶，得求对偶，得到到“与与-或或”表达式表达式F； 第二步：第二步：求出求出F的最简的最简“与与-或或”表达式；表达式； 第三步：第三步：对对F再次求对偶再次求对偶,即可得到即可得到F的最简的最简“或或-与与”表达式。表达式。 例如，例如，化简化简 )DCC)(AC)(BB)(AA(F解解 C)B)(AA(C)C)(BB)(AA()DCC)(AC)(BB)(AA(F例如，例如，化简化简 )()()()CACBBABAF （ 第二步：第二步：化简化简F ； CBABA