数字逻辑课件第二章逻辑代数基础.ppt

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

1、1,逻 辑 代 数 基 础,第 二 章,2,逻辑代数是数字系统逻辑设计的理论基础和重要数学工具！,1847年,英国数学家乔治布尔(G.Boole)提出了用数学分析方法表示命题陈述的逻辑结构，并将形式逻辑归结为一种代数演算，从而诞生了著名的“布尔代数”。1938年，克劳德向农(C.E.Shannon)将布尔代数应用于电话继电器的开关电路，提出了“开关代数”。随着电子技术的发展，集成电路逻辑门已经取代了机械触点开关，故人们更习惯于把开关代数叫做逻辑代数。,3,本章知识要点：基本概念；基本定理和规则；逻辑函数的表示形式；逻辑函数的化简。,4,逻辑代数L是一个封闭的代数系统，它由一个逻辑变量集K，常量

2、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),5,公 理 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,公理是一个代数系统的基本出发点，无需加以证明。,公 理 5 互 补

3、律对于任意逻辑变量A，存在唯一的，使得,6,2.1.1 逻辑变量及基本逻辑运算,逻辑代数和普通代数一样，是用字母表示其值可以变化的量，即变量。所不同的是：,1任何逻辑变量的取值只有两种可能性取值0或取值1。,2逻辑值0和1是用来表征矛盾的双方和判断事件真伪的形式符号，无大小、正负之分。,一、变量,7,二、基本逻辑运算,描述一个数字系统，必须反映一个复杂系统中各开关元件之间的联系，这种相互联系反映到数学上就是几种运算关系。逻辑代数中定义了“或”、“与”、“非”三种基本运算。,1“或”运算 如果决定某一事件是否发生的多个条件中，只要有一个或一个以上条件成立，事件便可发生，则这种因果关系称之为“或”

4、逻辑。,例如，用两个开关并联控制一个灯的照明控制电路。,8,电路中，开关A和B并联控制灯F。可以看出，当开关A、B中有一个闭合或者两个均闭合时，灯F即亮。因此，灯F与开关A、B之间的关系是“或”逻辑关系。可表示为,例如，下图所示电路。,F=A+B 或者F=A B，读作“F等于A或B”。,9,假定开关断开用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实现“或”运算关系的逻辑电路称为“或”门。,10,2“与”运算如果决定某

5、一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之为“与”逻辑。在逻辑代数中，“与”逻辑关系用“与”运算描述。两变量“与”运算关系可表示为F=AB或者F=AB即：若A、B均为1，则F为1；否则，F为0。,11,例如，两个开关串联控制同一个灯。显然，仅当两个开关均闭合时，灯才能亮，否则，灯灭。假定开关闭合状态用1表示，断开状态用0表示，灯亮用1表示，灯灭用0表示，则F和A、B之间的关系“与”运算关系。,数字系统中，实现“与”运算关系的逻辑电路称为“与”门。,“与”运算的运算法则:0 0=01 0=00 1=01 1=1,12,3“非”运算 如果某一事件的发生取决于条件的否定，即事

6、件与事件发生的条件之间构成矛盾，则这种因果关系称为“非”逻辑。在逻辑代数中，“非”逻辑用“非”运算描述。其运算符号为“”，有时也用“”表示。“非”运算的逻辑关系可表示为F=或者 F=A读作“F等于A非”。即：若A为0，则F为1；若A为1，则F为0。,13,例如，下面开关与灯并联的电路中，仅当开关断开时，灯亮；一旦开关闭合，则灯灭。令开关断开用0表示，开关闭合用1表示，灯亮用1表示，灯灭用0表示，则电路中灯F与开关A的关系即为上表所示“非”运算关系。,“非”运算的运算法则：；数字系统中实现“非”运算功能的逻辑电路称为“非”门，有时又称为“反相器”。,14,2.1.2 逻辑函数及逻辑函数间的相等,

7、逻辑代数中函数的定义与普通代数中函数的定义类似，即随自变量变化的因变量。但和普通代数中函数的概念相比，逻辑函数具有如下特点：,1逻辑函数和逻辑变量一样，取值只有0和1两种可能；,2函数和变量之间的关系是由“或”、“与”、“非”三种基本运算决定的。,一、逻辑函数的定义,15,图中，F被称为A1，A2，An的逻辑函数，记为F=f(A1，A2，An),逻辑电路输出函数的取值是由逻辑变量的取值和电路本身的结构决定的。,设某一逻辑电路的输入逻辑变量为A1，A2，An，输出逻辑变量为F，如下图所示。,16,设有两个相同变量的逻辑函数F1=f1(A 1,A 2,A n)F2=f2(A 1,A 2,A n)若

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

9、。,4.(A+B)+C或者A+(B+C)可用A+B+C代替；(AB)C或者A(BC)可用ABC代替。,19,二、真值表,依次列出一个逻辑函数的所有输入变量取值组合及其相应函数值的表格称为真值表。一个n个变量的逻辑函数，其真值表有2n行。例如，,真值表由两部分组成：左边一栏列出变量的所有取值组合，为了不发生遗漏，通常各变量取值组合按二进制数码顺序给出；右边一栏为逻辑函数值。,20,三、卡诺图,卡诺图是由表示逻辑变量所有取值组合的小方格所构成的平面图。这种用图形描述逻辑函数的方法，在逻辑函数化简中十分有用，将在后面结合函数化简问题进行详细介绍。,描述逻辑逻辑函数的3种方法可用于不同场合。但针对某个

10、具体问题而言，它们仅仅是同一问题的不同描述形式，相互之间可以很方便地进行变换。,21,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，即可得到上述关系。,如果以1和0代替公理5中的A，则可得到如下推论：,22,证明A+AB=A1+AB 公理4=A(1+B)公理3=A(B+1)公理1=A1公理4=A公理4,定理2A+A=A；A A=A,定理3A+A B=A；A(A+B)=A,23,24,定理6,证明

11、 由于()+(A+B)=(+A)+B 公理2=(+A)+B 定理4=A+(B+)公理1,2=A+1 公理5=1 公理4 而且()(A+B)=A+B 公理3=0+0 公理1,5=0 定理1 所以，根据公理5的唯一性可得,25,定理7AB+A=A(A+B)(A+)=A,证明 AB+A=A(B+)公理3=A 1 公理5=A 公理4,26,定理8 A B+C+B C=A B+C(A+B)(+C)(B+C)=(A+B)(+C),证明 AB+C+BC=AB+C+BC(A+)公理5=AB+C+BCA+BC 公理3=AB+ABC+C+BC 公理1=AB(1+C)+C(1+B)公理3=AB(C+1)+C(B+1

12、)公理1=AB+C 公理4,27,2.2.2 重要规则,例如，将逻辑等式A(B+C)=AB+AC中的C都用(C+D)代替，该逻辑等式仍然成立，即AB+(C+D)=AB+A(C+D)代入规则的正确性是显然的，因为任何逻辑函数都和逻辑变量一样，只有0和1两种可能的取值。,任何一个含有变量A的逻辑等式,如果将所有出现A的位置都代之以同一个逻辑函数F，则等式仍然成立。这个规则称为代入规则。,一、代入规则,28,代入规则的意义：利用代入规则可以将逻辑代数公理、定理中的变量用任意函数代替，从而推导出更多的等式。这些等式可直接当作公式使用，无需另加证明。,注意：使用代入规则时,必须将等式中所有出现同一变量的

13、地方均以同一函数代替，否则代入后的等式将不成立。,29,二、反演规则,例如，已知函数，根据反演规则可得到,若将逻辑函数表达式F中所有的“”变成“+”，“+”变成“”,“0”变成“1”,“1”变成“0”,原变量变成反变量，反变量变成原变量，并保持原函数中的运算顺序不变，则所得到的新的函数为原函数F的反函数。,30,注意:使用反演规则时，应保持原函数式中运算符号的优先顺序不变！,三、对偶规则,如果将逻辑函数表达式F中所有的“”变成“+”,“+”变成“”，“0”变成“1”，“1”变成“0”，并保持原函数中的运算顺序不变，则所得到的新的逻辑表达式称为函数F的对偶式，并记作F。例如，,例如，已知函数，根

14、据反演规则得到的反函数应该是而不应该是！错误,31,注意:求逻辑表达式的对偶式时，同样要保持原函数的运算顺序不变。,显然，利用对偶规则可以使定理、公式的证明减少一半。,若两个逻辑函数表达式F和G相等，则其对偶式F和G也相等。这一规则称为对偶规则。根据对偶规则，当已证明某两个逻辑表达式相等时，即可知道它们的对偶式也相等。,例如，已知AB+C+BC=AB+C，根据对偶规则对等式两端的表达式取对偶式，即可得到等式(A+B)(+C)(B+C)=(A+B)(+C),32,2.2.3 复合逻辑,实际应用中广泛采用“与非”门、“或非”门、“与或非”门、“异或”门等门电路。这些门电路输出和输入之间的逻辑关系可

15、由3种基本运算构成的复合运算来描述，故通常将这种逻辑关系称为复合逻辑，相应的逻辑门则称为复合门。,一、与非逻辑,与非逻辑是由与、非两种逻辑复合形成的，可用逻辑函数表示为逻辑功能：只要变量A、B、C、中有一个为0，则函数F为1；仅当变量A、B、C、全部为1时，函数F为0。实现与非逻辑的门电路称为“与非”门。,33,只要有了与非门便可组成实现各种逻辑功能的电路，通常称与非门为通用门。,与:,或:,非:,使用与非门可以实现与、或、非三种基本运算：,34,二、或非逻辑,逻辑功能：只要变量A、B、C中有一个为1，则函数F为0；仅当变量A、B、C全部为0时，函数F为1。实现或非逻辑的门电路称为“或非”门。

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

17、B取值相异，F为1。实现异或运算的逻辑门称为“异或门”。,1异或逻辑,当多个变量进行异或运算时，可用两两运算的结果再运算，也可两两依次运算。,异或逻辑是一种两变量逻辑关系，可用逻辑函数表示为,根据异或逻辑的定义可知：A 0=AA 1=A A=0A=1,37,注意：在进行异或运算的多个变量中，若有奇数个变量的值为1，则运算结果为1；若有偶数个变量的值为1，则运算结果为0。,例如，F=A B C D=(A B)(C D)(两两运算的结果再运算)=(A B)C D(两两依次运算),2同或逻辑,同或逻辑也是一种两变量逻辑关系，其逻辑函数表达式为,功能逻辑：变量A、B取值相同，F为1；变量A、B取值相异

18、，F为0。实现同或运算的逻辑门称为“同或门”。,F=A B=+AB 式中，“”为同或运算的运算符。,38,同或逻辑与异或逻辑的关系既互为相反，又互为对偶。即有：,由于同或实际上是异或之非，所以实际应用中通常用异或门加非门实现同或运算。,注意：当多个变量进行同或运算时，若有奇数个变量的值为0，则运算结果为0；反之，若有偶数个变量的值为0，则运算结果为1。,39,2.3 逻辑函数表达式的形式与变换,任何一个逻辑函数，其表达式的形式都不是唯一的。下面介绍逻辑函数表达式的基本形式、标准形式及其相互转换。,2.3.1 逻辑函数表达式的两种基本形式,两种基本形式：指“与-或”表达式和“或-与”表达式。,一

19、、“与-或”表达式,“与-或”表达式：是指由若干“与项”进行“或”运算构成的表达式。例如，,“与项”有时又被称为“积项”，相应地“或与”表达式又称为“积之和”表达式。,40,二、“或-与”表达式,“或项”有时又被称为“和项”，相应地“或与”表达式又称为“和之积”表达式。,“或-与”表达式：是指由若干“或项”进行“与”运算构成的表达式。例如，,41,该函数既不是“与或”式？也不是“或与”式！,2.3.2 逻辑函数表达式的标准形式,逻辑函数表达式可以被表示成任意的混合形式。例如，,逻辑函数的基本形式都不是唯一的。例如,为了在逻辑问题的研究中使逻辑功能能和唯一的逻辑表达式对应，引入了逻辑函数表达式的

20、标准形式。逻辑函数表达式的标准形式是建立在最小项和最大项概念的基础之上的。,42,一、最小项和最大项,（1）定义：如果一个具有n个变量的函数的“与项”包含全部n个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次，则该“与项”被称为最小项。有时又将最小项称为标准“与项”。,1最小项,（3）简写：用mi表示最小项。下标i的取值规则是：按照变量顺序将最小项中的原变量用1表示，反变量用0表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标i的值。,（2）最小项的数目：n个变量可以构成2n个最小项。,例如，3个变量A、B、C可以构成、A B C共8个最小项。,43,在由n个变量构成的任

21、意“与项”中，最小项是使其值为1的变量取值组合数最少的一种“与项”，这也就是最小项名字的由来。,（4）性质 最小项具有如下四条性质。性质1：任意一个最小项，其相应变量有且仅有一种取值使这个最小项的值为1。并且，最小项不同，使其值为1的变量取值不同。,44,性质3：n个变量的全部最小项相“或”为1。通常借用数学中的累加符号“”，将其记为,性质2：相同变量构成的两个不同最小项相“与”为0。因为任何一种变量取值都不可能使两个不同最小项同时为1，故相“与”为0。即mi mj=0,性质4：n个变量构成的最小项有n个相邻最小项。相邻最小项：是指除一个变量互为相反外，其余部分均相同的最小项。例如，三变量最小

22、项A B C和相邻。,45,定义：如果一个具有n个变量函数的“或项”包含全部n个变量，每个变量都以原变量或反变量形式出现一次，且仅出现一次，则该“或项”被称为最大项。有时又将最大项称为标准“或项”。,2最大项,数目：n个变量可以构成2n 个最大项。例如，3个变量A、B、C可构成、共8个最大项。,46,性质：最大项具有如下四条性质。,性质1 任意一个最大项，其相应变量有且仅有一种取值使这个最大项的值为0。并且，最大项不同，使其值为0的变量取值不同。,在n个变量构成的任意“或项”中，最大项是使其值为1的变量取值组合数最多的一种“或项”，因而将其称为最大项。,47,性质2 相同变量构成的两个不同最大

23、项相“或”为1。因为任何一种变量取值都不可能使两个不同最大项同时为0，故相“或”为1。即 M i+M j=1,性质3 n个变量的全部最大项相“与”为0。通常借用数学中的累乘符号“”将其记为,性质4 n个变量构成的最大项有n个相邻最大项。相邻最大项是指除一个变量互为相反外，其余变量均相同的最大项。,48,两变量最小项、最大项的真值表如下。,真值表反映了最小项、最大项的有关性质。,49,3最小项和最大项的关系,在同一问题中，下标相同的最小项和最大项互为反函数。或者说，相同变量构成的最小项mi和最大项Mi之间存在互补关系。即 或者,例如，由3变量A、B、C构成的最小项m3和最大项M3之间有,50,二

24、、逻辑函数表达式的标准形式,逻辑函数表达式的标准形式有标准“与-或”表达式和标准“或-与”表达式两种类型。,1标准“与-或”表达式,由若干最小项相“或”构成的逻辑表达式称为标准“与-或”表达式，也叫做最小项表达式。,该函数表达式又可简写为 F(A，B，C)=m1+m2+m4+m7=,例如，如下所示为一个3变量函数的标准“与-或”表达式,51,2标准“或-与”表达式,由若干最大项相“与”构成的逻辑表达式称为标准“或-与”表达式，也叫做最大项表达式。,该表达式又可简写为,例如，、为3变量构成的3个最大项，对这3个最大项进行“与”运算，即可得到一个3变量函数的标准“或-与”表达式,52,2.3.3

25、逻辑函数表达式的转换,将一个任意逻辑函数表达式转换成标准表达式有两种常用方法。,一、代数转换法,1.求标准“与-或”式,一般步骤如下：第一步：将函数表达式变换成一般“与-或”表达式。,所谓代数转换法，就是利用逻辑代数的公理、定理和规则进行逻辑变换，将函数表达式从一种形式变换为另一种形式。,第二步：反复使用将表达式中所有非最小项的“与项”扩展成最小项。,53,例 将逻辑函数表达式 转换成标准“与-或”表达式。,解 第一步：将函数表达式变换成“与-或”表达式。即,第二步：把“与-或”式中非最小项的“与项”扩展成最小项。,54,所得标准“与-或”式的简写形式为,当给出函数表达式已经是“与-或”表达式

26、时，可直接进行第二步。,2.求一个函数的标准“或-与”式,一般步骤：第一步：将函数表达式转换成一般“或-与”表达式。,第二步：反复利用定理把表达式中所有非最大项的“或项”扩展成最大项。,55,解 第一步：将函数表达式变换成“或-与”表达式。即,例 将逻辑函数表达式变换成标准“或-与”表达式。,56,第二步：将所得“或-与”表达中的非最大项扩展成最大项。即,当给出函数已经是“或-与”表达式时，可直接进行第二步。,该标准“或-与”表达式的简写形式为,57,二、真值表转换法,具体：真值表上使函数值为1的变量取值组合对应的最小项相“或”,即可构成一个函数的标准“与-或”式。,逻辑函数的最小项表达式与真

27、值表具有一一对应的关系。假定函数F的真值表中有k组变量取值使F的值为1，其他变量取值下F的值为0，那么，函数F的最小项表达式由这k组变量取值对应的k个最小项相或组成。,1.求标准“与-或”式,58,解:首先，列出F的真值表如下表所示，然后，根据真值表可直接写出F的最小项表达式,例 将函数表达式变换成标准“与-或”表达式。,59,具体：真值表上使函数值为0的变量取值组合对应的最大项相“与”即可构成一个函数的标准“或-与”式。,2.求一个函数的标准“或-与”式 逻辑函数的最大项表达式与真值表之间同样具有一一对应的关系。假定在函数F的真值表中有p组变量取值使F的值为0，其他变量取值下F的值为1，那么

28、，函数F的最大项表达式由这p组变量取值对应的p个最大项“相与”组成。,60,解：首先，列出F的真值表如下表所示。然后，根据真值表直接写出F的最大项表达式,例 将函数表达式 表示成最大项表达式的形式。,61,由于函数的真值表与函数的两种标准表达式之间存在一一对应的关系，而任何个逻辑函数的真值表是唯一的，可见，任何一个逻辑函数的两种标准形式也是唯一的。逻辑函数表达式的唯一性给我们分析和研究逻辑问题带来了很大的方便。,62,2.4 逻辑函数化简,实现某一逻辑功能的逻辑电路的复杂性与描述该功能的逻辑表达式的复杂性直接相关。为了降低系统成本、减小复杂度、提高可靠性，必须对逻辑函数进行化简。,由于“与-或

29、”表达式和“或-与”表达式可以很方便地转换成任何其他所要求的形式。因此，从这两种基本形式出发讨论函数化简问题，并将重点放在“与-或”表达式的化简上。,逻辑函数化简有3种常用方法。即：代数化简法、卡诺图化简法和列表化简法。,63,2.4.1 代数化简法,代数化简法就是运用逻辑代数的公理、定理和规则对逻辑函数进行化简的方法。,一、“与-或”表达式的化简,最简“与-或”表达式应满足两个条件：,1表达式中的“与”项个数最少；,2在满足上述条件的前提下，每个“与”项中的变量个 数最少。,满足上述两个条件可以使相应逻辑电路中所需门的数量以及门的输入端个数均为最少，从而使电路最经济。,64,几种常用方法如下

30、：,1并项法,2吸收法,利用定理3中A+AB=A，吸收多余的项。例如，,利用定理7中的，将两个“与”项合并成一个“与”项，合并后消去一个变量。例如，,65,3消去法,利用定理4中，消去多余变量。例如，,4配项法,66,例 化简,解,实际应用中遇到的逻辑函数往往比较复杂，化简时应灵活使用所学的公理、定理及规则，综合运用各种方法。,67,例 化简,解,68,二、“或-与”表达式的化简,最简“或-与”表达式应满足两个条件：,1表达式中的“或”项个数最少；,2在满足上述条件的前提下，每个“或”项中的变量个数最少。,用代数化简法化简“或-与”表达式可直接运用公理、定理中的“或-与”形式，并综合运用前面介

31、绍“与-或”表达式化简时提出的各种方法进行化简。,69,例 化简,解,此外，可以采用两次对偶法。具体如下：,第一步：对“或-与”表达式表示的函数F求对偶，得到“与-或”表达式F；,第二步：求出F的最简“与-或”表达式；,第三步：对F再次求对偶,即可得到F的最简“或-与”表达式。,70,例 化简,第二步：化简F；,第三步：对F求对偶,得到F的最简“或-与”表达式。,解 第一步：求F的对偶式F；,71,归纳：,代数化简法的优点是：不受变量数目的约束；当对公理、定理和规则十分熟练时，化简比较方便。,缺点是：没有一定的规律和步骤，技巧性很强，而且在很多情况下难以判断化简结果是否最简。,72,2.4.2

32、 卡诺图化简法,卡诺图化简法具有简单、直观、容易掌握等优点，在逻辑设计中得到广泛应用。,一、卡诺图的构成,卡诺图是一种平面方格图，每个小方格代表一个最小项，故又称为最小项方格图。结构特点：(1)n个变量的卡诺图由2n个小方格构成；(2)几何图形上处在相邻、相对、相重位置的小方格所代表的最小项为相邻最小项。,73,2变量、3变量、4变量卡诺图如图(a)、(b)、(c)所示。,74,例如，四变量卡诺图中，如m5的4个相邻最小项分别是和m5相连的 m1，m4，m7，m13。m2的4个相邻最小项除了与之几何相邻的m3和m6之外，另外两个是处在“相对”位置的m0(同一列的两端)和m10(同一行的两端)。

33、这种相邻称为相对相邻。,从各卡诺图可以看出，在n个变量的卡诺图中，能从图形上直观、方便地找到每个最小项的n个相邻最小项。,75,5变量卡诺图如图（d）所示。,此外，处在“相重”位置的最小项相邻，如五变量卡诺图中的m3，除了几何相邻的m1，m2，m7和相对相邻的m11外，还与m19相邻。这种相邻称为重叠相邻。,76,二、卡诺图的性质,用卡诺图化简逻辑函数的基本原理：把卡诺图上表征相邻最小项的相邻小方格“圈”在一起进行合并，达到用一个简单“与”项代替若干最小项的目的。通常把用来包围那些能由一个简单“与”项代替的若干最小项的“圈”称为卡诺圈。,性质：可以从图形上直观地找出相邻最小项合并。合并的理论依

34、据是并项定理：。,77,三、逻辑函数在卡诺图上的表示,当逻辑函数为标准“与-或”表达式时，只需在卡诺图上找出和表达式中最小项对应的小方格填上1，其余小方格填上0，即可得到该函数的卡诺图。,1给定逻辑函数为标准“与-或”表达式,例如，3变量函数 的卡诺图如下图所示。,78,例如，4变量函数 的卡诺图如右图所示。,为了叙述的方便，通常将卡诺图上填1的小方格称为1方格，填0的小方格称为0方格。0方格有时用空格表示。,2逻辑函数为一般“与-或”表达式,当逻辑函数为一般“与-或”表达式时，可根据“与”的公共性和“或”的叠加性作出相应卡诺图。,79,四、卡诺图上最小项的合并规律,1两个小方格相邻,或处于某

35、行(列)两端时，所代表的最小项可以合并，合并后可消去一个变量。,例如，下图给出了2、3变量卡诺图上两个相邻最小项合并的典型情况的。,当一个函数用卡诺图表示后，究竟哪些最小项可以合并呢？下面以2、3、4变量卡诺图为例予以说明。,80,2四个小方格组成一个大方格、或组成一行（列）、或处于相邻两行（列）的两端、或处于四角时，所代表的最小项可以合并，合并后可消去两个变量。,例如,下图给出了3变量卡诺图上四个相邻最小项合并的典型情况的。,81,4变量卡诺图上四个相邻最小项合并的典型情况：,82,3八个小方格组成一个大方格、或组成相邻的两行(列)、或处于两个边行(列)时，所代表的最小项可以合并，合并后可消

36、去三个变量。,例如，下图给出了3、4变量卡诺图上八个相邻最小项合并的典型情况的。,83,n个变量卡诺图中最小项的合并规律归纳如下：,(1)卡诺圈中小方格的个数必须为2m个，m为小于或等于n的整数。,(2)卡诺圈中的2m个小方格有一定的排列规律，具体地说，它们含有m个不同变量，(n-m)个相同变量。,(3)卡诺圈中的2m个小方格对应的最小项可用(n-m)个变量的“与”项表示，该“与”项由这些最小项中的相同变量构成。,(4)当m=n 时，卡诺圈包围了整个卡诺图，可用1表示，即n个变量的全部最小项之和为1。,84,蕴涵项:在函数的“与-或”表达式中，每个“与”项被称为该函数的蕴涵项(Implican

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

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

39、诺圈对应的与项相或即可得到函数F的最简“与-或”表达式为,88,解 用卡诺图化简给定函数的过程如下图所示。,例 用卡诺图化简逻辑函数,这里，两个“与-或”式的复杂程度相同。由此可见，一个函数的最简“与-或”表达式不一定是唯一的。,89,解 用卡诺图化简给定函数，如下图所示。,例用卡诺图化简逻辑函数,函数F的最简“与-或”表达式为,90,用卡诺图化简总的原则是：,(2)在满足合并规律的前题下卡诺圈应达到最大；,(3)根据合并的需要，每个最小项可以被多个卡诺圈包围。,(1)在覆盖函数中所有最小项的前提下，卡诺圈的个数 应达到最少；,91,(1)作出F的卡诺图，求出反函数 的最简“与-或”表达式(合

40、并卡诺图上的0方格)；,(2)对的最简“与-或”表达式取反，得到函数F的最简“或-与”表达式。,3.求逻辑函数最简“或-与”表达式的一般步骤 当给定逻辑函数为“与或”表达式或标准“与或”表达式时，通常采用“两次取反法”。具体如下：,92,解用卡诺图化简给定函数的过程如右图所示，得到：,再对反函数的最简“与-或”表达式两边取反，即可求得函数的最简“或-与”表达式,93,当给定逻辑函数为“或与”表达式或标准“或与”表达式时，通常采用“两次对偶法”。具体如下：,(1)作出F对偶式F 的卡诺图，并求出F的最简“与-或”表达式；(2)对F的最简“与-或”表达式取对偶，得到函数F的最简“或-与”表达式。,94,卡诺图化简逻辑函数具有方便、直观、容易掌握等优点。但受到变量个数的约束，当变量个数大于6时，画图以及对图形的识别都变得相当复杂。,为了克服卡诺图的不足，引入了另一种化简方法列表化简法。（详见教材有关内容）,