逻辑代数的基本运算23 逻辑代数的基本定理及规则24 逻辑.ppt

2.1 逻辑代数中的几个概念2.2 逻辑代数的基本运算2.3 逻辑代数的基本定理及规则2.4 逻辑函数的性质2.5 逻辑函数的化简,第二章 逻辑代数基础,第二章 逻辑代数基础,Fundamentals of Boolean Algebar,布尔代数 Boolean algebra： 用一种数学运算的代数系统描述人的逻辑思维规律和推理过程。 逻辑代数 Switching algebra： 将布尔代数的一些基本前提和定理应用于继电器的分析与描述，称为二值布尔代数，或开关代数。继电器是当时最常用的数字逻辑元件，继电器的接触状态（打开或闭合）用 0 或 1表示。,逻辑代数是二值逻辑运算中的基本数学工具 逻辑代数广泛应用于数字系统的分析和设计,第二章 逻辑代数基础,Fundamentals of Boolean Algebar,在现代逻辑分析技术中，逻辑值对应于各种广泛的物理条件：电压的高或低、灯光的明或暗、电容器的充电或放电、熔丝的断开或接通，等等。 下表给出了不同的计算机逻辑和存储技术中表示位值的物理状态。,不同的计算机逻辑和存储技术中表示位值的物理状态,2.1 逻辑代数中的几个概念,1. 逻辑状态 Logic State： 当事物的某些特性表现为两种互不相容的状态，即 某一时刻必出现且仅出现一种状态 一种状态是另一种状态的反状态 则用符号0、1分别表示这两种状态，称逻辑状态。 即：0 状态 (0state) 和 1 状态 (1state) 一般，0状态逻辑条件的假或无效， 1状态逻辑条件的真或有效。 (两种状态无大小之分),2. 逻辑变量 Logic Value ：,用于表示事物的逻辑状态随逻辑条件的变化而变化，取值“0” 或“1” 。,4. 逻辑电平 Logic Voltage： 在二值逻辑电路(开关电路)中，将物理器件的物理量离散为两种电平：高电平（用 H 表示）、低电平（用 L 表示） 抽象化的高、低电平忽略其物理量值的实际含义，实际上它们是代表着一定范围的物理量。参见下页。 在高、低电平之间有一逻辑不确定区，称为“噪音区”。若电平稳定于噪音区称为逻辑模糊，这在逻辑电路中不允许。,3. 逻辑常量 Logic Constant ： 逻辑状态保持不变，取值“0” 或“1”。,表21不同工艺器件定义的逻辑电平,图2-1 脉冲的逻辑电平表示,5. 逻辑约定 Logic Assumpsit：,规定 逻辑电平（表示物理器件的输入、输出物理量） 与 逻辑状态（表示物理器件的逻辑功能） 之间的 关系，即逻辑规定（约定）。 这一规定过程称为逻辑化过程。 逻辑约定有两种：正逻辑规定（约定） 和 负逻辑规定（约定），如下：,正逻辑规定（约定）,负逻辑规定（约定）,逻辑电路Logic Circuit： 由实现逻辑变量之间逻辑关系的物理器件所构成的电路称为逻辑电路，即二值逻辑电路。,6. 逻辑代数 Logic Algebar ： 用代数形式表现逻辑变量之间的因果关系。 用代数运算对这些逻辑变量进行逻辑推理。 因此，逻辑代数是一个集合：逻辑变量集、常量0和1、 “与”、“或”和“非”三种逻辑运算。 运算顺序是：“非”最高，“与”次之，“或”最低。,7. 逻辑函数 Logic Function：,输入逻辑变量 A1，A2， , An；输出逻辑变量F； 记为：F = f (A1，A2， , An )，关系如下图所示：,F = f (A1, A2, , An),8. 逻辑函数的表示法 Representation：主要有四种, 真值表（穷举法） Truth Table,真值表例,表达式例：F = A B, 逻辑表达式 Algebraic Forms of Switching Functions, 卡诺图 Karnaugh MAP （文氏图 Venn Diagrams）, 时间图 （信号波形图 ） Timing,Venn图,2.2 逻辑代数的基本运算,A,B,F,A,B,F,2.3 逻辑代数的基本定理及规则,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 ) = ( A B ) C,Distributivity of the and operations分配律 AB C = (AB)(AC) A (BC) = A BA C,例：证明 分配律 AB C = (AB)(AC) 成立。 用真值表证明，如下：,重叠律 Idempotency A + A = A A A = A,互补律 Complement A + A = 1 A A = 0,2.3.2 逻辑代数的基本定理 Fundamental Theorems,右边 = A + 1 B （01律）,= A + AB,例 ：证明 A + A B = A + B ，可以用公理来证明。,吸收律 Absorption,= 左边 证明成立,反演律 DeMorgans Theorem (摩根定理),摩根定理的作用：进行函数化简和逻辑变换。,N变量的摩根定理：,（此定理证明见代入规则。）,= 右边 证明成立,包含律 Consensus (也称多余项定理),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，使等式成立, 代入规则成立。,2.3.4 逻辑代数的基本规则 Basic Formulas,令 X = A2 + Y 代入,令 Y = A3 + Z 代入,依次类推，则推出 N 变量的摩根定理。,证明N变量的摩根定理：,用代入规则证明N变量的摩根定理，如下：,这是反演律和代入规则的推广使用，是对互补函数的完善说明。,2. 反演规则(香农定理) Shannons expansion theorem,注意运算顺序并没有变化,已知原函数 f ( x1 , x2 , , xn, 0 , 1, +, ),则对偶函数 f ( x1 , x2 , , xn , 0 , 1, +, ) = f ( x1 , x2 , , xn , 1 , 0, , + ),结论：1. （f ) = f,3. 对偶规则 Dual expansion theorem,2. 若 f1 = f2 则 f1 = f2 ,2.4 逻辑函数的性质,2.4.1 复合逻辑 与、或、非三种基本逻辑运算组合起来可以实现任何逻辑函数。 与门、或门、非门三种基本逻辑运算(门)组合起来可以构成实现任何逻辑功能的逻辑电路，称此三门构成了一个逻辑完备组 若实现一个较复杂的逻辑功能，尤其在大规模集成电路快速发展的今天，必须增加门电路的功能，以简化电路。,1. 与非逻辑(NAND) 逻辑表达式为: F = A B C,与非逻辑真值表 与非门的逻辑符号,可以用与非门实现三种基本运算：, 与运算 F1 = AB,2. 或非逻辑(NOR) 逻辑表达式为: F = A B C,或非逻辑真值表 或非门的逻辑符号,可以用或非门实现三种基本运算：, 或运算 F2 = AB,3. 与或非逻辑(AOI) 逻辑表达式为: F = AB CD EF,与或非门的逻辑符号,4. 异或逻辑(XOR) 逻辑表达式为: F = AB = A B A B,异或逻辑真值表 异或门的逻辑符号,5. 同或逻辑 逻辑表达式为: F = AB = A B A B,同或逻辑真值表 同或门的逻辑符号,异或运算与同或运算的关系,1. AB = AB AB = AB 2. (AB) = AB (AB) = AB 3. AB C = AB C,例：证明 AB = A B A B = A B A B = ( A B )( A B) = A B A B = A B,证明 AB C = A ( BC ) A ( B C ) = A ( BC ) 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 ( B C ) = A ( BC ) A ( B C ) = A ( B C BC ) A ( B C BC ) = A B C A B C A B C ABC,所以： 当变量个数为2时，同或运算与异或运算具有互补关系； 当变量个数为3时，同或运算与异或运算具有相等关系。,由代入规则可以证明：,A1A2A3 An = A1A2A3 An n 为偶数 A1A2A3 An = A1A2A3 An n 为奇数,当变量为偶数时，同或运算与异或运算之间具有互补关系；当变量为奇数时，同或运算与异或运算之间具有相等关系。即：,异或运算和同或运算的基本代数性质,01律 (a) A0 =A A1 =A (b) A0 =A A1 =A 交换律 (a) AB =BA (b) AB =BA 分配律 (a) A(BC) =ABAC (b) A(BC) =(AB)(AC) 结合律 (a) A(BC) = (AB)C (b) A(BC) =(A B )C 调换律 (a)若 AB = C则 AC = B ， CB = A (b) 若AB = C则 AC = B ， CB = A,依照逻辑运算的规则，一个逻辑命题可以用多种形式的逻辑函数来描述，而这些逻辑函数的真值表都是相同的。,2.4.2 逻辑函数的基本表达式 Algebraic Forms of Switching Functions,= ,如： F = AB,2.4.3 逻辑函数的标准形式 Canonical Forms of Switching Functions,一个逻辑命题的三种表示法：真值表 表达式 卡诺图,三者之间的关系： 真值表是逻辑函数最基本的表达方式，具有唯一性； 由真值表可以导出逻辑表达式和卡诺图； 由真值表导出逻辑表达式的两种标准形式： 最小项之和 The canonical SOP(the Sum Of Products) 最大项之积 The canonical POS(Product Of Sums),1. 最小项 minterm,设有 n 个变量，它们组成的与项中每个变量或以原变量或以反变量形式出现一次，且仅出现一次，此与项称之为 n 个变量的最小项。 对于 n 个变量就可构成 2n个最小项，分别记为 mi 。 其中：下标值 i的取值为当各个最小项变量按一定顺序排好后，用 1 代替其中的原变量， 0 代替其中的反变量，便得到一个二进制数，该二进制数的等值十进制即为 i 的值。,2. 最大项 maxterm,设有 n 个逻辑变量，它们组成的或项中，每个变量或以原变量形式或以反变量形式出现一次，且仅出现一次，此或项称为 n 变量的最大项。 对于 n 个变量可以构成2n个最大项，分别记为 Mi 。 其中：下标值 i的取值规则与最小项中 i的取值规则相反，即将各变量按一定次序排好后，用 0 代替其中的原变量，用 1 代替其中的反变量，得到一个二进制数，该二进制数的等值十进制即为 i 的值。,3.最小项与最大项具有如下性质：, 对于任意最小项，只有一组变量组合取值可使其值为1；对于任意最大项，只有一组变量组合取值可使其值为0。（i对应的二进制取值时）, 任意两个最小项之积必为0，即： mi mj = 0 ( ij ) 任意两个最大项之和必为1，即： MiMj=1 ( ij ),由上表可知，最小项与最大项具有如下性质, 同变量数下标相同的最小项和最大项互为反函数 即： m i = M i M i = m i 则： m i M i = 0 且 m iM i = 1,例 ABC=A+B+C,4. 函数的最小项标准式,逻辑函数被表达成一系列乘积项之和，则称之为积之和表达式(SOP)，或称为与或表达式。 如果构成函数的积之和表达式中每一个乘积项(与项)均为最小项时，则这种表达式称之为最小项标准式(The canonical SOP)，且这种表示是唯一的。,写出逻辑函数的最小项标准式的方法：, 如果给定的函数为一般的与或表达式，可以反复应用公式X=X ( YY ) 代入缺少某变量(Y)的与项中，形成最小项之和的形式。, 如果给定函数用真值表表示，显然真值表每一行变量,的组合对应一个最小项。如果对应该行的函数值为 1 ，则函数的最小项表达式中应包含该行对应的最小项；如果该行的函数值为 0，则函数的最小项表达式中不包含对应该行的最小项。 前例题：AC=1 （m5+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 ), 如果给定函数用卡诺图表示，则卡诺图上的每一块区,域对应一个最小项。如果对应该区域的函数值为 1 ，则函数的最小项表达式中应包含该区域对应的最小项；如果该区域的函数值为 0，则函数的最小项表达式中不包含对应该区域的最小项。,最小项与原函数、反函数的关系,对于 n 个变量的函数 F ，它共有2n个最小项，这些最小项不是包含在原函数 F 的最小项表达式中，就是包含在反函数 F的最小项表达式中。 用逻辑代数可以证明：,5. 函数的最大项标准式,逻辑函数被表达成一系列和项之积，则称为和之积表达式(POS)，或称为或与表达式。 如果构成函数的或与表达式中的每一个和项均为最大项，则这种表达式称为最大项标准式 ( The Canonical POS)，且这种表示是唯一的。,写出逻辑函数的最大项标准式的方法：, 如果给定的函数是一般的或与表达式，可以反复应用公式：X = X + YY = (X +Y)(X +Y) 代入缺少某变量(Y)的和项中以形成最大项之积的形式。,如果给定函数用真值表表示，显然真值表每一行变量的,组合对应一个最大项。如果对应该行的函数值为 0 ，则函数的最大项表达式中应包含该行对应的最大项；如果该行的函数值为 1 ，则函数的最大项表达式中不包含对应该行的最大项。(注意与最小项规则相反),例：F(A,B,C)，其最大项表达式应为： F(A,B,C) = M1 M2 M5 = M3( 1,2,5 ), 如果给定函数用卡诺图表示，则函数的最大项表达式,可以通过卡诺图得到。,最大项与原函数、反函数的关系,对于 n 个变量的函数 F ，它共有2n个最大项，这些最大项不是包含在原函数 F 的最大项表达式中，就是包含在反函数 F 的最大项表达式中。 可以证明：,同一函数的最小项标准式与其最大项标准式的关系:,同一逻辑函数的一种标准式变换成另一种标准式时，互换mn 和 Mn 的符号，并在符号后列出原式中缺少的那些数字。而且这两种标准式都是唯一的。 例： F = m3( 0,2,3 ) = M 3( 1,4,5,6,7 ),2.5 逻辑函数的化简 Simplification of Switching Expression,一个逻辑函数对应着一个实现其逻辑功能的逻辑电路，当使该函数最简意味着使这个电路也最简。,最简逻辑电路：门数最少；门的输入端最少；门的级 数最少。 最简与或式：与项的数目最少；每个与项的变量个数 最少。 最简或与式：或项的数目最少；每个或项的变量个数 最少。,例： F = AB ( BC ) AC BC = AB C对应两种逻辑电路图，如下,2.5.1 代数化简法：,一、与或式的化简,与或式化简常用的公式主要有四个： A + A = 1 A + AB = A + B AB + AB = A AB + AC + BC = AB + 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. 消去法利用公式：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. 配项法,当无法发现直接应用公式时，可先增加一些与项，再利用增加项消除多余项，即“先繁后简”。, 利用公式： ABAC = ABACBC 增加项数。 例： F = AB + BC + BC + AB = AB + BC + BC + AB + AC = AB + BC + BC + AC = 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 + BC + CB + BD + DB + CD = A + BC + CB + DB + CD = A + BC + DB + CD,二、或与式的化简,或与式化简有两种方法：,2. 利用最简与或式得到最简或与式, 二次对偶法 利用对偶规则，先求出F的对偶式F，再将对偶式F 化简为最简与或式，最后再求一次对偶(F ) = F，则得到 F 最简或与式。, 二次求反法,利用反演规则，先求出F的反函数 F，再将反函数 F 化简为最简与或式，最后再求一次反 F = F，则得到 F 最简或与式。,2.5.2 卡诺图（Karnaugh MAP）法,卡诺图逻辑函数真值表的一种图形表示，利用卡诺图可以有规律地化简逻辑函数表达式，并能直观地写出逻辑函数的最简式。,一、卡诺图的构成 卡诺图是一种平面方格阵列图，下页给出了二变量、三变量、四变量、五变量和六变量的卡诺图。,单变量的卡诺图,二变量的卡诺图,0,1,2,3,三变量的卡诺图,再引入变量C，将区域分为八块，分别对应着8 个最小项：,四变量的卡诺图,四变量(A、B、C、D)的卡诺图，分别对应着16个最小项：,五变量的卡诺图,五变量(A、B、C、D、E)的卡诺图，分别对应着32个最小项。,六变量的卡诺图:有64个最小项,卡诺图的构成特点：, 整个卡诺图总是被每个变量逐次地分成两半：原变量，反变量各占一半。任一变量的原变量和反变量所占的区域又被其他变量分成两半。,卡诺图的行和列按照变量的组合标注方法，其变量顺序遵从真值表中变量从左至右的顺序。,卡诺图的构成特点：, n 变量卡诺图有2n个小方格(或称为单元)，每个小方格内左上角标注小方格名称或号，小方格名称由各行各列所对应的变量字母组成，小方格号的十进制数就是它对应的最小项的下标值；,卡诺图的构成特点：, 若干个小方格将对应一个逻辑函数，即一个逻辑函数可以图示于卡诺图上。,例：F = m1 + m2 + m5 + m7 ，其真值表和卡诺图标注如下：,A B,C,1,1,1,1, 在行和列上相邻的小方格，其名称仅有一个变量状态不同。,卡诺图的构成特点：, 除掉某个小方格(即最小项)以外的整个卡诺图区域对应一个最大项，最大项下标值就是应被除去的小方格号。,m7 M7,两个函数相“与”，表示两个函数在卡诺图上所占两个区域的公共区域； 两个逻辑函数相“或”，表示两个函数所覆盖的全部区域； 一个逻辑函数的“非”，就是求该函数覆盖之外的区域。,上述卡诺图构成的特点及最小项与最大项在卡诺图上的表示，可以进一步说明逻辑运算的几何含义：,二、逻辑函数在卡诺图上的表示, 把给定的逻辑函数化为最小项标准式 按变量数画出相应卡诺图 在对应于最小项标准式中各最小项的小方格内标以“1” 所有标有“1”的小方格的合成区域就表示该函数。,F1= m3 (1,4,5,6,7)的卡诺图表示,例：F2 = ABC + AC + BC 直接按与、或的几何含义将函数标注到卡诺图上。,AB,C,A,C,B,1,1,1,1,1,1,1,1,1,BC,例：F3 = (A + B)(C + B)(A + B),求出反函数的与或式，直接按与、或的共同区域将函数标注到卡诺图上，此时小方格应标注“0”，其余的标“1”，则标“1”小方格的集合就是原函数。,1,1,1,0,0,0,0,0,三、用卡诺图化简逻辑函数的基本原理,1. “相邻”的判断,在 n 变量的卡诺图上，每个小方格具有n个相邻的小方格，它们是： 具有共同边界的小方格(几何相邻) 同一幅卡诺图中分别处于行(或列)两端的小方格 (相对相邻) 在相邻两幅卡诺图中，处于相同位置的两个小方格 (相重相邻) 例如5变量卡诺图, 相邻最小项：任意两个最小项中只有一个变量不同（同一变量名但一个为原变量，另一个为反变量），其余变量完全相同，在图上反映的是两个相邻的小方格。 卡诺图相邻小方格：是指只隔一条边界的两个小方格。,n 变量卡诺图的每一个小方格都有 n 个相邻块，,以m0为例说明如下：,n=1,n=2,n=3,n=4,n=5,n 变量卡诺图的每一个小方格都有 n 个相邻块，,以m0为例说明如下：,n=6,在真值表上，不易直观地理解最小项的相邻关系，而在卡诺图上则相邻关系一目了然。,2. 画卡诺圈的规则,寻找相邻块的目的是为了在图上进行函数化简。,标1/标0的相邻同维块可画在一个卡诺圈内；,任何2i个（i n）标1的相邻小方格均可画在一个卡诺圈内； 任何2i个标1的非相邻的小方格不能画入一个卡诺圈内，它们至少画在两个圈内。,标1/标0的非相邻同维块不能画入一个卡诺圈内，它们至少画在两个圈内。,例：五变量的卡诺图, 0维块：m7 = ABCDE，是五变量的与项。,例：五变量的卡诺图,2维块：由四个相邻的 0 维块构成的一个卡诺圈， m8+m9 +m12+m13= A B D m0+m2+ m8 +m10= A C E m9+m13 +m25+m29 = B D E 是三变量的与项。,对 n 变量而言，2i个(in)标1的相邻小方格所构成的一个卡诺圈表示一个(n-i)变量的与项，即：使 2i 个相邻的最小项被化简为一个(n-i)变量的与项。,用卡诺圈化简是有其特点和规律的。,蕴函项 ( Implicant )：,在函数的与或表达式中，每一个与项称为该函数的蕴涵项，它对应着卡诺图中的一个卡诺圈。 卡诺圈越大，它所包含的相邻标1小方格越多，则对应此蕴涵项的变量数就越少。 卡诺圈既包含某变量的原变 量区域，又包括它的反变量 区域，则这个变量就不出现 在此圈所对应的蕴涵项中。,实质最小项：,质蕴函 ( Prime implicant )：,必要质蕴函( Essential prime implicant )：包含实质最小项的质蕴涵即为必要质蕴涵。,1,1,1,1,若蕴涵项不是其他蕴涵项的子集，则称为质蕴涵，又称为素项，在卡诺图中称为极大圈。,只被一个质蕴涵所覆盖的最小项称为实质最小项。,用卡诺圈化简是有其特点和规律的：,卡诺图上的最小覆盖：,挑选数目最少的必要质蕴涵，它们覆盖了图上全部标1的小方格，这就是最小覆盖。 最小覆盖所对应的逻辑表达式就是最简的表达式。,四、用卡诺图化简逻辑函数,1. 用卡诺图法化简逻辑函数的基本步骤, 将逻辑函数表示在卡诺图上； 根据实质最小项确定所有的必要极大圈； 如果所选出的所有必要极大圈已覆盖卡诺图上全部标1小方格，那么这些必要极大圈的集合就是卡诺图上的最小覆盖； 如果还有标1的小方格未被上述的必要极大圈覆盖，那么再加上选择最少的极大圈覆盖剩余的标1小方格，即获得最小覆盖； 写出最小覆盖所对应的逻辑表达式，即最简与或式。,2. 将逻辑函数化简成最简与或表达式,例1 化简 F1=m4(1,3,4,5,9,11,12,13,14,15),第二步：选择出必要极大圈，它们是 a、b、c，确定所包含的实质最小项分别是 m3 、m4、m14；,第三步：确定 a、b、c 这三个必要极大圈已覆盖全部标1小方格；,1,1,1,第一步：将函数F1表示在卡诺图中；,第四步：写出函数最简表达式 F1= a+b+c = BD+BC+AB,例2 化简F2=m4(0,1,2,3,4,5,7,14,15),函数最简表达式 F2= a + c + d + b = AB + AC + AD + ABC,1,1,1,1,例3 化简F3=m4(1,5,7,9,11,15),函数F3的两种表达式，如图和所示。,例4 化简F4=m5(0,2,4,10,12,13,15,18,26,28,29,31),函数的最简与或式 F4 = a + b +c + d = BCD + BCE + CDE + ABDE,3. 将逻辑函数化简成最简或与式,从代数法或与式的化简中已得知，如果求出反函数的最简与或式，则按反演规则可得到原函数的最简或与式。,原函数在卡诺图上标0小方格的集合正好是反函数在卡诺图上的表示，故： 按原函数在卡诺图中标0小方格的相邻情况，即可求出反函数的最简与或式； 将反函数求反，则得到原函数的最简或与式。,例1 化简 F1=m4(0,8,9,10,11,12,13,14,15),第一步：将F1表示在卡诺图上，即标1小方格；,第二步：将未填1的小方格均填上0；,第三步：对所有标0小方格选出必要极大圈；,4. 同一函数的最简与或式 和 最简或与式 对应的电路比较,例： F1的卡诺图表示如右：,d,e,比较上述两种电路,图(b)比图(a)少用两个门，如果电路可任选，则应优先选用图(b)电路； 这两种电路形式上看都是三级；,2.5.3 利用无关项输入(dont care input) 简化函数表达式,例如：一位BCD码输入的求偶电路。,分析： 当输入为偶数时，输出 F 为1，否则输出 F 为0。, 假设其输入为 A8 A4 A2 A1 ，在正常情况下，输出 表达式可以写为： F(A8 A4 A2 A1) = m(0,2,4,6,8),无关最小项的未使用和使用的电路比较:,无关项(dont care terms) 也称任意项、约束项，构成的函数为不完全给定函数(Incompletely Specified functions),定义：当函数输出与某些输入组合无关时，这些输入的 组合称为无关项。,产生原因： 这些输入组合在正常操作中不会出现（即输入具有约束条件）； 即使这些输入可能出现（即输入不具有约束条件） ，但实际上输出与它们无关。,作用： 当输入出现这些无关组合 d 时， d 可以随意加入或不加入其对应的函数 F 中（既可使 F 为 1，也可使确F 为 0），并不影响 F 原有的逻辑功能，但为函数 F 的化简提供了帮助。,例1：一个BCD码输入质数检测器。 假设输入为N3 N2 N1 N0 ，输出表达式可以写为： F =m4 (1,2,3,5,7) +d4 (10,11,12,13,14,15) 这里d（)项列出的即为无关项。,化简的第一步： 给出函数的初始卡诺图；,第二步： 按前述的方法找出必要质蕴涵，区别是： 画覆盖标 1 小方格的极大圈时，应把相邻的 “d” 包含在内（相当于使 d = 1），使画出的极大圈尽可能地大，可减少该质蕴涵的变量数； 不圈任何仅包含 d 的圈； 不圈任何标 0 的小方格；,例2： F = m4(4,5,13,15) + d 4 (2,3,7,9,14),最简与或式 F = BD + ABC,例3：一个2421码输入四舍五入判别电路。 F =m4 (11,12,13,14,15) +d4 (5,6,7,8,9,10),最简与或式 F = A,2.5.4 输入无反变量的函数的化简,在电路中为减少连线数目，对其外部输入变量只有原变量没有反变量，电路要通过非门来实现反变量。,下图是两式对应的电路，后者可减少一个非门。,(a) F= AB 不共享非门,(b) F= AB 共享非门,对于与或式，共享的门是与非门。,当反变量较多时，如果每个反变量都加个非门太不经济，考虑能否共享非门，即寻找把多个单输入非门合并成一个多输入与非门的方法可以减少非门的个数。,化简的出发点是函数已经为最简与或式； 化简的主要方法有以下两种： 1. 替代尾因子法 定义：每个与项中原变量部分称为头因子，反变量部分称为尾因子。 特点：把头因子中的任何变量放入任一个尾因子中，该与项不变，即头因子是不变的，尾因子是可变的 。,化简步骤为： 把最简式中具有相同头因子的与项合并成一个与项。, 列出最简与或式中所有与项的头因子、尾因子及替代尾因子。,选择共享的替代尾因子，选择的原则如下：,替代尾因子共享数尽可能多。 在共享数相等时选择最简单的一个。,该电路图如下。,2. 禁止逻辑法,任何函数利用不属于它的最小项之非乘之，其逻辑功能不变。即： F = F mi (mi不在F中),任何函数如用属于它的最小项之和的非乘之，则相当 于从该函数中扣去了这几个最小项，称禁止逻辑。,例：F = m1 + m3 + m5 + m7,禁止逻辑（又称阻塞逻辑），上式中m5 + m7 称为禁止项，G 是 F 被 m5 + m7 禁止后的函数。,禁止逻辑的几何意义：,F = m1 + m3 + m5 + m7,禁止逻辑法化简函数的步骤： 把函数中各与项或部分与项共享的标 0 单元画入极大圈； 把这些 0 单元作为禁止项，从极大圈禁止掉，原函数保持不变。,例 F1 = m1 + m3 + m5 + m6,第一步：找出共享的 0 单元m7 作为禁止项； 第二步：画出相应的极大圈；,从卡诺图可知，是最简与或式，电路实现需要10个与非门。,实现需要7个与非门(书P60图2-37b)。,3. 输入无反变量的或与式函数的化简,根据对偶规则： F 给出或与式函数 F 得到与或式函数，寻求共享的与非项 F = ( F) 得到或与式原函数，含有共享的或非项。,电路由五个或非门实现(书P61图2-38)。,2.72.82.13 2.142.152.18 2.192.202.21 2.26,第二章 作业,