数字电路与逻辑设计第二章逻辑代数基础.ppt

《数字电路与逻辑设计第二章逻辑代数基础.ppt》由会员分享，可在线阅读，更多相关《数字电路与逻辑设计第二章逻辑代数基础.ppt（104页珍藏版）》请在三一办公上搜索。

1、,逻 辑 代 数 基 础,第 二 章,逻辑代数是数字系统设计的理论基础和重要数学工具！,逻辑代数是从哲学领域中的逻辑学发展而来的。1847年,英国数学家乔治布尔提出了用数学分析方法表示命题陈述的逻辑结构，并成功地将形式逻辑归结为一种代数演算，从而诞生了著名的“布尔代数”。1938年，克劳德向农将布尔代数应用于电话继电器的开关电路，提出了“开关代数”。随着电子技术的发展，集成电路逻辑门已经取代了机械触点开关，故“开关代数”这个术语已很少使用。为了与“数字系统逻辑设计”这一术语相适应，人们更习惯于把开关代数叫做逻辑代数。,本章知识要点：基本概念；基本定理和规则；逻辑函数的表示形式；逻辑函数的化简。

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

3、数系统的基本出发点，无需加以证明。,公 理 5 互 补 律对于任意逻辑变量A，存在唯一的，使得,2.1.1 逻辑变量及基本逻辑运算,逻辑代数和普通代数一样，是用字母表示其值可以变化的量，即变量。所不同的是：,1在普通代数中，变量的取值可以是任意实数，而逻辑代数是 一 种二值代数系统，任何逻辑变量的取值只有两种可能性取值0或取值1。,2逻辑值0和1是用来表征矛盾的双方和判断事件真伪的形式符号，无大小、正负之分。在数字系统中，开关的接通与断开，电压的高和低，信号的有和无，晶体管的导通与截止等两种稳定的物理状态，均可用1和0这两种不同的逻辑值来表征。,一变量,二基本逻辑运算,描述一个数字系统，必须反

4、映一个复杂系统中各开关元件之间的联系，这种相互联系反映到数学上就是几种运算关系。逻辑代数中定义了“或”、“与”、“非”三种基本运算。,1“或”运算 如果决定某一事件是否发生的多个条件中，只要有一个或一个以上条件成立，事件便可发生，则这种因果关系称之为“或”逻辑。,例如，用两个开关并联控制一个灯的照明控制电路。,在上图所示电路中，开关A和B并联控制灯F。可以看出，当开关A、B中有一个闭合或者两个均闭合时，灯F即亮。因此，灯F与开关A、B之间的关系是“或”逻辑关系。,用两个开关并联控制一个灯的电路如下图所示。,逻辑代数中，“或”逻辑用“或”运算描述。其运算符号为“+”，有时也用“”表示。两变量“或

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

6、：若A、B均为1，则F为1；否则，F为0。,假定开关闭合状态用1表示，断开状态用0表示，灯亮用1表示，灯灭用0表示，则电路中灯F和开关A、B之间的关系即上表所示的“与”运算关系。,“与”逻辑关系如下表所示。,“与”运算的运算法则:0 0=01 0=00 1=01 1=1实现“与”运算关系的逻辑电路称为“与”门。,3“非”运算 如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果关系称为“非”逻辑。在逻辑代数中，“非”逻辑用“非”运算描述。其运算符号为“”，有时也用“”表示。“非”运算的逻辑关系可表示为F=或者 F=A，读作“F等于A非”。即：若A为0，则F为1；若

7、A为1，则F为0。,例如，在右上图所示电路中，开关与灯并联。显然，仅当开关断开时，灯亮；一旦开关闭合，则灯灭。令开关断开用0表示，开关闭合用1表示，灯亮用1表示，灯灭用0表示，则电路中灯F与开关A的关系即为上表所示“非”运算关系。,“非”运算的运算法则：；实现“非”运算功能的逻辑电路称为“非”门，有时又称为“反相器”。,“非”逻辑关系可用下表:,2.1.2 逻辑函数及逻辑函数间的相等,逻辑代数中函数的定义与普通代数中函数的定义类似，即随自变量变化的因变量。但和普通代数中函数的概念相比，逻辑函数具有如下特点：,1逻辑函数和逻辑变量一样，取值只有0和1两种可能；,2函数和变量之间的关系是由“或”、

8、“与”、“非”三种基本运算决定的。,一、逻辑函数的定义,图中，F被称为A1，A2，An的逻辑函数，记为F=f(A1，A2，An),逻辑电路输出函数的取值是由逻辑变量的取值和电路本身的结构决定的。任何一个逻辑电路的功能都可由相应的逻辑函数完全描述，因此，可借助抽象的代数表达式对电路加以分析研究。,从数字系统研究的角度看，逻辑函数的定义如下:,设某一逻辑电路的输入逻辑变量为A1，A2，An，输出逻辑变量为F，如下图所示。,逻辑函数和普通代数中的函数一样存在是否相等的问题。什么叫做两个逻辑函数相等呢？设有两个相同变量的逻辑函数F1=f1(A 1,A 2,A n)F2=f2(A 1,A 2,A n)若

9、对应于逻辑变量 A1,A2,An的任何一组取值，F1和F2的值都相同，则称函数F1和F2相等，记作F1=F2。,如何判断两个逻辑函数是否相等？通常有两种方法,一种方法是真值表法，另一种方法是代数法。,2.1.3 逻辑函数的表示法,该逻辑表达式描述了一个两变量的逻辑函数F。函数F和变量A、B的关系是：当变量A和B取值不同时，函数F的值为“1”；取值相同时，函数F的值为“0”。,逻辑表达式是由逻辑变量和“或”、“与”、“非”3种运算符以及括号所构成的式子。例如,一、逻辑表达式,如何对逻辑功能进行描述？常用的方法有逻辑表达式、真值表、卡诺图3种。,逻辑表达式的简写:,1.“非”运算符下可不加括号，如

10、，等。,2.“与”运算符一般可省略，如AB可写成AB。,4.(A+B)+C或者A+(B+C)可用A+B+C代替；(AB)C或者A(BC)可用ABC代替。,二、真值表,依次列出一个逻辑函数的所有输入变量取值组合及其相应函数值的表格称为真值表。由于一个逻辑变量有0和1两种可能的取值，n个逻辑变量共有2n种可能的取值组合。因此，一个n个变量的逻辑函数，其真值表有2n行。,真值表由两部分组成：左边一栏列出变量的所有取值组合，为了不发生遗漏，通常各变量取值组合按二进制数码顺序给出；右边一栏为逻辑函数值。例如，逻辑函数 的真值表如右表所示。,三、卡诺图,卡诺图是由表示逻辑变量所有取值组合的小方格所构成的平

11、面图。这种用图形描述逻辑函数的方法，在逻辑函数化简中十分有用，将在后面结合函数化简问题进行详细介绍。,描述逻辑逻辑函数的3种方法各有特点,可用于不同场合。但针对某个具体问题而言，它们仅仅是同一问题的不同描述形式，相互之间可以很方便地进行变换。,2.2 逻辑代数的基本定理和规则,根据逻辑代数的公理，可以推导出逻辑代数的基本定理。常用的有组定理。(对定理中的一个表达式加以证明),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，即可得到上述关系。,如果

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

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

14、变成原变量。并保持原函数中的运算顺序不变，则所得到的新的函数为原函数F的反函数。,注意:使用反演规则时，应保持原函数式中运算符号的优先顺序不变。,三、对偶规则,如果将逻辑函数表达式F中所有的“”变成“+”,“+”变成“”，“0”变成“1”，“1”变成“0”，并保持原函数中的运算顺序不变，则所得到的新的逻辑表达式称为函数F的对偶式，并记作F。例如，,例如，已知函数，根据反演规则得到的反函数应该是而不应该是！错误,注意：1、如果F的对偶式是F，则F的对偶式就是F。即，(F)=F,可见F和F互为对偶式。,2、一般来说，F与对偶式F是不相等的！但不排除特殊！若逻辑函数表达式的对偶式就是原函数表达式本身

15、，即F=F，则称函数F为自对偶函数。,3、求逻辑表达式的对偶式时，同样要保持原函数的运算顺序不变。,根据对偶规则，当已证明某两个逻辑表达式相等时，即可知道它们的对偶式也相等。显然，利用对偶规则可以使定理、公式的证明减少一半。,对偶规则：若两个逻辑函数表达式F和G相等，则其对偶式F和G也相等。,2.2.3 复合逻辑,实际应用中广泛采用“与非”门、“或非”门、“与或非”门、“异或”门等门电路。这些门电路输出和输入之间的逻辑关系可由3种基本运算构成的复合运算来描述，通常将这种逻辑关系称为复合逻辑，相应的逻辑门则称为复合门。,一、与非逻辑,与非逻辑是由与、非两种逻辑复合形成的，可用逻辑函数表示为逻辑功

16、能：只要变量A、B、C、中有一个为0，则函数F为1；仅当变量A、B、C、全部为1时，函数F为0。实现与非逻辑的门电路称为“与非”门。,由于与非逻辑又可实现3种基本逻辑，所以，只要有了与非门便可组成实现各种逻辑功能的电路，通常称与非门为通用门。采用与非逻辑可以减少逻辑电路中门的种类，提高标准化程度。,二、或非逻辑,逻辑功能：只要变量A、B、C中有一个为1，则函数F为0；仅当变量A、B、C全部为0时，函数F为1。实现或非逻辑的门电路称为“或非”门。,或非逻辑是由或、非两种逻辑复合形成的，可用逻辑函数表示为,同样，由定理 可知，“或”之“非”可以产生“与”的关系。因此，只要有了或非逻辑也可以实现与、

17、或、非3种基本逻辑。以两变量或非逻辑为例：,或非门同样是一种通用门。,三、与或非逻辑,逻辑功能：仅当每一个“与项”均为0时，F才能为1，否则F为0。实现与或非功能的门电路称为“与或非”门。,显然，可以仅用与或非门组成实现各种功能的逻辑电路。但实际应用中这样做一般会很不经济，所以，与或非门主要用来实现与或非形式的函数。必要时可将逻辑函数表达式的形式变换成与或非的形式。,与或非逻辑是由3种基本逻辑复合形成的，逻辑函数表达式的形式为,四、异或逻辑及同或逻辑,逻辑功能：变量A、B取值相同，F为0；变量A、B取值相异，F为1。实现异或运算的逻辑门称为“异或门”。,1异或逻辑,当多个变量进行异或运算时，可

18、用两两运算的结果再运算，也可两两依次运算。,异或逻辑是一种两变量逻辑关系，可用逻辑函数表示为,根据异或逻辑的定义可知：A 0=AA 1=A A=0A=1,特性：在进行异或运算的多个变量中，若有奇数个变量的值为1，则运算结果为1；若有偶数个变量的值为1，则运算结果为0。,例如，F=A B C D=(A B)(C D)(两两运算的结果再运算)=(A B)C D(两两依次运算),2同或逻辑,功能逻辑：变量A、B取值相同，F为1；变量A、B取值相异，F为0。实现同或运算的逻辑门称为“同或门”。,两者有区别吗？,同或逻辑与异或逻辑的关系既互为相反，又互为对偶。即：,由于同或实际上是异或之非，所以实际应用

19、中通常用异或门+非门实现同或运算。,特性：当多个变量进行同或运算时，若有奇数个变量的值为0，则运算结果为0；反之，若有偶数个变量的值为0，则运算结果为1。,2.3 逻辑函数表达式的形式与变换,任何一个逻辑函数的表达式形式都不是唯一的。从应用的角度出发，讨论基本形式、标准形式及其相互转换。,2.3.1 逻辑函数表达式的两种基本形式,两种基本形式：指“与-或”表达式和“或-与”表达式。,一、“与-或”表达式,“与-或”表达式：是指由若干“与项”进行“或”运算构成的表达式。每个“与项”可以是单个变量的原变量或者反变量，也可由多个原变量或者反变量相“与”组成。例如，均为“与项”，将这3个“与项”相“或

20、”便可构成一个3变量函数的“与或”表达式。即,二、“或-与”表达式,注意：“与项”有时又被称为“积项”，相应地“与-或”表达式又称为“积之和”表达式。“或项”有时又被称为“和项”，相应地“或与”表达式又称为“和之积”表达式。,“或-与”表达式：是指由若干“或项”进行“与”运算构成的表达式。每个“或项”可以是单个变量的原变量或者反变量，也可以由多个原变量或者反变量相“或”组成。,例如，、D 均为“或项”，将这4个“或项”相“与”便可构成一个4变量函数的“或-与”表达式。即,该逻辑函数是“与或”式？不是！是“或与”式？也不是！但不论什么形式都可以变换成两种基本形式。,2.3.2 逻辑函数表达式的标

21、准形式,逻辑函数表达式可以被表示成任意的混合形式。例如：,逻辑函数的两种基本形式都不是唯一的。例如 为了在逻辑问题的研究中使逻辑功能能和唯一的逻辑表达式对应，引入了逻辑函数表达式的标准形式。逻辑函数表达式的标准形式是建立在最小项和最大项概念的基础之上的。,请问逻辑函数的基本形式是否唯一？,一、最小项和最大项,定义：如果一个具有n个变量的函数的“与项”包含全部n个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次，则该“与项”被称为最小项。有时又将最小项称为标准“与项”。,数目：n个变量可以构成2n个最小项。,例如，3个变量A、B、C可以构成、A B C共8个最小项。,1最小项,（掌握4

22、点：定义、数目、简写、性质！）,简写：用mi表示最小项。下标i的取值规则是：按照变量顺序将最小项中的原变量用1表示，反变量用0表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标i的值。,在由n个变量构成的任意“与项”中，最小项是使其值为1的变量取值组合数最少的一种“与项”，这也就是最小项名字的由来。,（4）性质-最小项具有四条性质 性质1 任意一个最小项，其相应变量有且仅有一种取值使这个最小项的值为1。并且，最小项不同，使其值为1的变量取值不同。,性质2 相同变量构成的两个不同最小项相“与”为0。因为任何一种变量取值都不可能使两个不同最小项同时为1，故相“与”为0。即 mi mj=0

23、,性质3：n个变量的全部最小项相“或”为1。通常借用数学中的累加符号“”，将其记为,性质4：n个变量构成的最小项有n个相邻最小项。相邻最小项：是指除一个变量互为相反外，其余部分均相同的最小项。例如，三变量最小项A B C和。,定义：如果一个具有n个变量函数的“或项”包含全部n个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次，则该“或项”被称为最大项。有时又将最大项称为标准“或项”。,2最大项,数目：n个变量可以构成2n 个最大项。例如，3个变量A、B、C可构成、共8个最大项。,性质：最大项具有4条性质。,性质1 任意一个最大项，其相应变量有且仅有一种取值使这个最大项的值为0。并且，

24、最大项不同，使其值为0的变量取值不同。,简写：用Mi表示最大项。下标i的取值规则是：将最大项中的原变量用0表示，反变量用1表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标 i 的值。例如，3变量A、B、C构成的最大项 可用 M5 表示。,在n个变量构成的任意“或项”中，最大项是使其值为1的变量取值组合数最多的一种“或项”，因而将其称为最大项。,性质2 相同变量构成的两个不同最大项相“或”为1。因为任何一种变量取值都不可能使两个不同最大项同时为0，故相“或”为1。即 M i+M j=1,性质3 n个变量的全部最大项相“与”为0。通常借用数学中的累乘符号“”将其记为,性质4 n个变量构

25、成的最大项有n个相邻最大项。相邻最大项是指除一个变量互为相反外，其余变量均相同的最大项。,两变量最小项、最大项的真值表如下:,该真值表反映了最小项、最大项的有关性质。,3最小项和最大项的关系,在同一问题中，下标相同的最小项和最大项互为反函数。或者说，相同变量构成的最小项mi和最大项Mi之间存在互补关系。即 或者,例如，由3变量A、B、C构成的最小项m3和最大项M3之间有,二、逻辑函数表达式的标准形式,逻辑函数表达式的标准形式有标准“与-或”表达式和标准“或-与”表达式两种类型。,1标准“与-或”表达式,由若干最小项相“或”构成的逻辑表达式称为标准“与-或”表达式，也叫做最小项表达式。,该函数表

26、达式又可简写为 F(A，B，C)=m1+m2+m4+m7=,例如，一个3变量函数的标准“与-或”表达式,2标准“或-与”表达式,由若干最大项相“与”构成的逻辑表达式称为标准“或-与”表达式，也叫做最大项表达式。,例如，、为3变量构成的3个最大项，对这3个最大项进行“与”运算，即可得到一个3变量函数的标准“或-与”表达式,该表达式又可简写为,2.3.3 逻辑函数表达式的转换,将一个任意逻辑函数表达式转换成标准表达式有两种常用方法:代数转换法，真值表转换法。,一、代数转换法,1.求标准“与-或”式,一般步骤如下：第一步：将函数表达式变换成一般“与-或”表达式。,所谓代数转换法，就是利用逻辑代数的公

27、理、定理和规则进行逻辑变换，将函数表达式从一种形式变换为另一种形式。,第二步：反复使用将表达式中所有非最小项的“与项”扩展成最小项。,例如，将逻辑函数表达式 转换成标准“与-或”表达式。,解 第一步：将函数表达式变换成“与-或”表达式。即,第二步：把“与-或”式中非最小项的“与项”扩展成最小项。具体地说，若某“与项”缺少函数变量Y，则用()和这一项相与，并将其拆开成两项。即,所得标准“与-或”式的简写形式为,当给出函数表达式已经是“与-或”表达式时，可直接进行第二步。,一般步骤：第一步：将函数表达式转换成一般“或-与”表达式。,第二步：反复利用定理把表达式中所有非最大项的“或项”扩展成最大项。

28、,2.求一个函数的标准“或-与”式,（详见教材中举例。）,二、真值表转换法,具体：真值表上使函数值为1的变量取值组合对应的最小项相“或”,即可构成一个函数的标准“与-或”式。,逻辑函数的最小项表达式与真值表具有一 一对应的关系！假定函数F的真值表中有k组变量取值使F的值为1，其他变量取值下F的值为0，那么，函数F的最小项表达式由这k组变量取值对应的k个最小项相或组成。因此，可以通过函数的真值表写出最小项表达式。,1.求标准“与-或”式,解:首先，列出F的真值表如下表所示，然后，根据真值表可直接写出F的最小项表达式,例如，将函数表达式变换成标准“与-或”表达式。,具体：真值表上使函数值为0的变量

29、取值组合对应的最大项相“与”即可构成一个函数的标准“或-与”式。,2.求一个函数的标准“或-与”式 逻辑函数的最大项表达式与真值表之间同样具有一一对应的关系。假定在函数F的真值表中有p组变量取值使F的值为0，其他变量取值下F的值为1，那么，函数F的最大项表达式由这p组变量取值对应的p个最大项“相与”组成。,解：首先，列出F的真值表如下表所示。然后，根据真值表直接写出F的最大项表达式,例如，将函数表达式 表示成最大项表达式的形式。,由于函数的真值表与函数的两种标准表达式之间存在一一对应的关系。任何个逻辑函数的真值表是唯一的！任何一个逻辑函数的两种标准形式也是唯一的！逻辑函数表达式的唯一性给我们分

30、析和研究逻辑问题带来了很大的方便。,2.4 逻辑函数化简,实现某一逻辑功能的逻辑电路的复杂性与描述该功能的逻辑表达式的复杂性直接相关。一般说，逻辑函数表达式越简单，设计出来的相应逻辑电路也就越简单。为了降低系统成本、减小复杂度、提高可靠性，必须对逻辑函数进行化简。,由于“与-或”表达式和“或-与”表达式可以很方便地转换成任何其他所要求的形式。因此，从这两种基本形式出发讨论函数化简问题，并将重点放在“与-或”表达式的化简上。,逻辑函数化简有3种常用方法：代数化简法、卡诺图化简法、列表化简法。,2.4.1 代数化简法,代数化简法就是运用逻辑代数的公理、定理和规则对逻辑函数进行化简的方法。无固定的步

31、骤可以遵循，主要取决于对逻辑代数中公理、定理和规则的熟练掌握及灵活运用的程度。,一、“与-或”表达式的化简,最简“与-或”表达式应满足两个条件：,1表达式中的“与”项个数最少；,2在满足上述条件的前提下，每个“与”项中的变量个数最少。,满足上述两个条件可以使相应逻辑电路中所需门的数量以及门的输入端个数均为最少，从而使电路最经济。,几种常用方法如下：,1并项法,2吸收法,利用定理3中 A+AB=A，吸收多余的项。例如，,3消去法,利用定理4中 消去多余变量。,4配项法,利用公理4和公理5中的 A1=A及，先从函数式中适当选择某些“与”项，并配上其所缺的一个合适的变量，然后再利用并项、吸收和消去等

32、方法进行化简。,例1 化简,解：,实际应用中遇到的逻辑函数往往比较复杂，化简时应灵活使用所学的公理、定理及规则，综合运用各种方法。,例2 化简,解 定理7,二、“或-与”表达式的化简,最简“或-与”表达式应满足两个条件：,1表达式中的“或”项个数最少；,2在满足上述条件的前提下，每个“或”项中的变量个数最少。,用代数化简法化简“或-与”表达式可直接运用公理、定理中的“或-与”形式，并综合运用前面介绍“与-或”表达式化简时提出的各种方法进行化简。,例如，化简,当对公理、定理中的“或-与”形式不太熟悉时，可以采用两次对偶法。具体如下：,第一步：对“或-与”表达式表示的函数F求对偶，得到“与-或”表

33、达式F；,第二步：求出F的最简“与-或”表达式；,第三步：对F再次求对偶,即可得到F的最简“或-与”表达式。,例如，化简,第二步：化简F；,第三步：对F求对偶,得到F的最简“或-与”表达式,解：第一步：求F的对偶式F；,归纳：,代数化简法的优点是：不受变量数目的约束；当对公理、定理和规则十分熟练时，化简比较方便。,缺点是：没有一定的规律和步骤，技巧性很强，而且在很多情况下难以判断化简结果是否最简。,2.4.2 卡诺图化简法,卡诺图化简法的优点：简单、直观、容易掌握。,一、卡诺图的构成,卡诺图是一种平面方格图，每个小方格代表一个最小项，故又称为最小项方格图。构造特点：(1)n个变量的卡诺图由2n

34、个小方格构成；(2)几何图形上处在相邻、相对、相重位置的小方格所代表的最小项为相邻最小项。卡诺图中最小项的排列方案不是唯一的，但任何一种排列方案都必须具备以上特点。,2变量、3变量、4变量卡诺图如图(a)、(b)、(c)所示：,例如，四变量卡诺图中，每个最小项有4个相邻最小项。m5的4个相邻最小项分别是哪些？m2的4个相邻最小项？m2和m10(同一行的两端)，这种相邻称为相对相邻。,在n个变量的卡诺图中，能从图形上直观、方便地找到每个最小项的n个相邻最小项。,此外，处在“相重”位置的最小项相邻，如五变量卡诺图中的m3，除了几何相邻的m1，m2，m7和相对相邻的m11外，还与m19相邻。这种相邻

35、称为重叠相邻。,注意：卡诺图在构造上具有以下两个特点！,(1)n个变量的卡诺图由2n个小方格组成，每个小方格代表一个最小项；,(2)卡诺图上处在相邻、相对、相重位置的小方格所代表的最小项为相邻最小项。,二卡诺图的性质,用卡诺图化简逻辑函数的方法：将卡诺图上表征相邻最小项的相邻小方格“圈”在一起进行合并，用一个简单“与”项代替若干最小项。通常把用来包围那些能由一个简单“与”项代替的若干最小项的“圈”称为卡诺圈。,性质：可以从图形上直观地找出相邻最小项合并。合并的理论依据是并项定理。,三、逻辑函数在卡诺图上的表示,当逻辑函数为标准“与-或”表达式时，只需在卡诺图上找出和表达式中最小项对应的小方格填

36、上1，其余小方格填上0，即可得到该函数的卡诺图。,1给定逻辑函数为标准“与-或”表达式,例如，3变量函数 的卡诺图如下图所示。,例如，4变量函数 的卡诺图如右图所示。,为了表达方便，通常将卡诺图上填1的小方格称为1方格，填0的小方格称为0方格。0方格有时用空格表示。,2逻辑函数为一般“与-或”表达式,当逻辑函数为一般“与-或”表达式时，可根据“与”的公共性和“或”的叠加性作出相应卡诺图。,四、卡诺图上最小项的合并规律,1两个小方格相邻,或处于某行(列)两端时，所代表的最小项可以合并，合并后可消去一个变量。,例如，2、3变量卡诺图上两个相邻最小项合并的典型情况。,一个函数用卡诺图表示后，究竟哪些

37、最小项可以合并呢？下面以2、3、4变量卡诺图为例予以说明。,注意：21个最小项合并后的与项可以减少1个变量！,2四个小方格组成一个大方格、或组成一行（列）、或处于相邻两行（列）的两端、或处于四角时，所代表的最小项可以合并，合并后可消去两个变量。,例如,3变量卡诺图上四个相邻最小项合并的典型情况。,注意：22个最小项合并后的与项可以减少2个变量！,4变量卡诺图上四个相邻最小项合并的典型情况的。,注意：22个最小项合并后的与项可以减少2个变量！,3八个小方格组连成一体、或处于两个边行(列)时，所代表的最小项可以合并，合并后可消去三个变量。,例如，3、4变量卡诺图上八个相邻最小项合并的典型情况的。,

38、注意：23个最小项合并后的与项可以减少3个变量！,依此类推，可归纳出n个变量卡诺图中最小项的合并规律如下：,(1)卡诺圈中小方格的个数必须为2m个，m为小于或等于n的整数。,(2)卡诺圈中的2m个小方格有一定的排列规律，具体地说，它们含有m个不同变量，(n-m)个相同变量。,(3)卡诺圈中的2m个小方格对应的最小项可用(n-m)个变量的“与”项表示，该“与”项由这些最小项中的相同变量构成。,(4)当m=n 时，卡诺圈包围了整个卡诺图，可用1表示，即n个变量的全部最小项之和为1。,蕴涵项:在函数的“与-或”表达式中，每个“与”项被称为该函数的蕴涵项(Implicant)。,显然，在函数卡诺图中，

39、任何一个1方格所对应的最小项或者卡诺圈中的2m个1方格所对应的“与”项都是函数的蕴涵项。,五、卡诺图化简逻辑函数的步骤,1几个定义,质蕴涵项:若函数的一个蕴涵项不是该函数中其他蕴涵项的子集，则此蕴涵项称为质蕴涵项(Prime Implicant),简称为质项。,显然，在函数卡诺图中，按照最小项合并规律，如果某个卡诺圈不可能被其他更大的卡诺圈包含，那么，该卡诺圈所对应的“与”项为质蕴涵项。,在函数卡诺图中，若某个卡诺圈包含了不可能被任何其他卡诺圈包含的1方格，那么，该卡诺圈所对应的“与”项为必要质蕴涵项。,必要质蕴涵项：若函数的一个质蕴涵项包含有不被函数的其他任何质蕴涵项所包含的最小项，则此质蕴

40、涵项被称为必要质蕴涵项(Essential Prime Implicant)，简称为必要质项。,第一步：作出函数的卡诺图；,第二步：在卡诺图上圈出函数的全部质蕴涵项；,2求逻辑函数最简“与-或”表达式的一般步骤,第三步：从全部质蕴涵项中找出所有必要质蕴涵项；,第四步：求函数的最简质蕴涵项集。,注意：求函数的最简质蕴涵项集是指当函数的所有必要质蕴涵项尚不能覆盖卡诺图上的所有1方格时，则从剩余质蕴涵项中找出最简的所需质蕴涵项，使它和必要质蕴涵项一起构成函数的最小覆盖。,解 用卡诺图化简给定函数的过程如下：,例1 用卡诺图化简逻辑函数,该题中，5个必要质蕴涵项已将函数的全部最小项覆盖，故将各卡诺圈对

41、应的与项相或即可得到函数F的最简“与-或”表达式为,解 用卡诺图化简给定函数的过程如下：,例2 用卡诺图化简逻辑函数,这里，两个“与-或”式的复杂程度相同。由此可见，一个函数的最简“与-或”表达式不一定是唯一的。,请你动手化简一下这道题好吗？,解 用卡诺图化简给定函数的过程如下：,例3用卡诺图化简逻辑函数,函数F的最简“与-或”表达式为,卡诺图?,用卡诺图化简总的原则是：,在满足合并规律的前题下卡诺圈应尽可能大；,根据合并的需要，每个最小项可以被多个卡诺圈包围。,在覆盖函数中所有最小项的前提下，卡诺圈的个数应尽 可能少；,作出F的卡诺图，求出反函数 的最简“与-或”表达式(合并卡诺图上的0方格

42、)；,对的最简“与-或”表达式取反，得到函数F的最简“或-与”表达式。,3.求逻辑函数最简“或-与”表达式的一般步骤,具体如下：,(1)当给定逻辑函数为“与或”表达式时，通常采用“两次取反法”。,解化简给定函数的卡诺图如右图所示。,图中，F的0方格即反函数 的1方格，它们代表 的各个最小项，将全部0方格合并就可得到反函数 的最简“与-或”表达式,再对反函数的最简“与-或”表达式两边取反，即可求得函数的最简“或-与”表达式,(2)当给定逻辑函数为“或与”表达式时，通常采用“两次对偶法”。具体如下：,作出F对偶式F 的卡诺图，并求出F的最简“与-或”表达式；对F的最简“与-或”表达式取对偶，得到函

43、数F的最简“或-与”表达式。,F的最简“与-或”表达式为,首先求出逻辑函数 的对偶函数F，并用卡诺图进行化简；,对F的最简“与-或”表达式取对偶，得到函数F的最简“或-与”表达式为,例4 已知逻辑函数,函数G和H的最简“与-或”表达式分别为,用卡诺图求逻辑函数 G=F1F2和H=F1+F2的最简与-或式。,首先求出G和H的标准与-或式为,解用卡诺图化简法求给定函数的过程如下：,用卡诺图化简函数G和H。,G的卡诺图?,H的卡诺图?,分别求出F1 F2 和 F1+F2的最简与-或表达式和或-与表达式。,卡诺图化简逻辑函数具有方便、直观、容易掌握等优点。但受到变量个数的约束，当变量个数大于6时，画图

44、以及对图形的识别都变得相当复杂。为了克服卡诺图的不足，引入了另一种化简方法列表化简法。,列表化简法和卡诺图化简法的类似，也是通过找出函数F的全部质蕴涵项、必要质蕴涵项以及最简质蕴涵项集来求得最简表达式。但列表化简法是通过约定的表格形式，按照一定规则逐步完成化简过程的。,具体步骤如下：,第一步：将函数表示成“最小项之和”形式，并用二进 制码表示每一个最小项；,第二步：作质蕴涵项产生表，找出函数的全部质蕴涵项；,第三步：作必要质蕴涵项产生表,找出函数的必要质蕴涵项；,第四步：当必要质蕴涵项不能覆盖所有最小项时，作所需 质蕴涵项产生表,找出函数的最小覆盖。,2.4.3 列表化简法,例如用列表法化简逻

45、辑函数,解第一步：将函数中的每一个最小项用二进制代码表示，如下表所示。,第二步：作质蕴涵项产生表，找出函数的全部质蕴涵项。该函数的质蕴涵项产生表如下表所示。,该函数的全部质蕴涵项为：,质蕴涵项产生表中凡是没有打“”标记的“与”项，即函数的质蕴涵项，用Pi表示。,第三步：作必要质蕴涵项产生表,找出函数的必要质蕴涵项。本例的必要质蕴涵项产生表如下表所示。,第四步：找出函数的最小覆盖选取必要质蕴涵项p1、p2、p4、p5后即可覆盖函数的全部最小项。化简的最终结果为：,列表法的优点是规律性强，对变量数较多的函数，尽管工作量很大，但总可经过反复比较、合并得到最简结果。适用于计算机处理。,当给定函数的必要质蕴涵项集不能覆盖该函数的全部最小项时，还需进一步从剩余质蕴涵项集中找出所需质蕴涵项，以构成函数的最小质蕴涵项集。（详见教材.）,本章作业:,2.12.2(4)2.4(2)、(4)2.52.6(4)2.7(1)2.8(2)、(3)2.9(1)2.10,