第二章逻辑代数基础(修改)

1、LOGO数数 字字 逻逻 辑辑河南大学软件学院河南大学软件学院主讲人：胡主讲人：胡 萍萍第第2章逻辑代数基础章逻辑代数基础本本 章章 要要 点点v了解基本概念了解基本概念 ；v掌握基本定理和规则掌握基本定理和规则 ；v掌握逻辑函数的表示形式与变换掌握逻辑函数的表示形式与变换 ；v掌握逻辑函数的化简。掌握逻辑函数的化简。1.1 HTML简介简介2.1逻辑代数的基本概念逻辑代数的基本概念2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算v变量变量逻辑代数和普通代数一样，是用字母表示其值可以变化的量，即变量。变量。不同之处是：v 逻辑变量的取值只有两种可能性：逻辑变量的取值只有两种可能性：0或

2、或1；v 逻辑值逻辑值0和和1是用来表征矛盾的双方和判断事件真伪的是用来表征矛盾的双方和判断事件真伪的形式符号，无大小、正负之分。形式符号，无大小、正负之分。2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算v基本逻辑运算基本逻辑运算逻辑代数中定义了“或或”、“与与” 、“非非”三种基本运算。 1、 “或或”运算运算 v 定义：定义：如果决定某一事件是否发生的多个条件中，只要有一个或一个以上条件成立，事件便可发生，则这种因果关系称之为“或”逻辑。 2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算1、 “或或”运算运算v举例：举例：打开有两个并联开关的灯。 A+uBF2.1.1 逻

3、辑变量及基本逻辑运算逻辑变量及基本逻辑运算1、 “或或”运算运算v表达式：表达式： FAB 或或 FA B 读作：读作：F 等于等于 A 或或 B2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算1、 “或或”运算运算v运算表：运算表：又称为真值表打开有两个并联开关的灯。设开关为A、B，合上为1，断开 为0；灯为F，灯亮为1，灭为0 A0111100BF01011“或或”运算表运算表 2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算1、 “或或”运算运算v运算法则：运算法则： “或或”运算的运算法则：运算的运算法则：0 + 0 = 01 + 0 = 10 + 1 = 11 + 1

4、 = 1实现实现“或或”运算关系的逻辑电路称为运算关系的逻辑电路称为“或或”门。门。 有1出1全0为0 2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算2、 “与与”运算运算 v定义：定义：如果决定某一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之为“与”逻辑。v举例举例：打开有两个串联开关的灯。+uABF2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算2、 “与与”运算运算v表达式：表达式： FAB 或或 FA B 读作：读作：F 等于等于 A 与与 B2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算2、 “与与”运算运算v运算表：运算表：打开有两个

5、串联开关的灯。设开关为A、B，合上为1，断开 为0；灯为F，灯亮为1，灭为0 A0110000BF01011“与与”运算表运算表 2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算2、 “与与”运算运算v运算法则：运算法则： “与与”运算的运算法则：运算的运算法则：0 0 = 01 0 = 00 1 = 01 1 = 1实现实现“与与”运算关系的逻辑电路称为运算关系的逻辑电路称为“与与”门。门。 有0出0全1为1 2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算3、 “非非”运算运算 v定义：定义：如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果

6、关系称为“非”逻辑。v举例举例：如下电路中灯的亮灭。+uAF2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算3、 “非非”运算运算v表达式：表达式： FA 或或 F A读作：读作：F 等于等于 A非非2.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算3、 “非非”运算运算v运算表：运算表：打开上例电路中的灯。设开关为A，合上为1，断开为0；灯为F，灯亮为1，灭为0 “非非”运算表运算表 AF01012.1.1 逻辑变量及基本逻辑运算逻辑变量及基本逻辑运算3、 “非非”运算运算v运算法则：运算法则： “非非”运算的运算法则：运算的运算法则：0 = 11 = 0实现实现“非非”运算关

7、系的逻辑电路称为运算关系的逻辑电路称为“非非”门。门。 2.1.2逻辑函数及逻辑函数间的相等逻辑函数及逻辑函数间的相等v逻辑函数的定义逻辑函数的定义设某一逻辑电路的输入逻辑变量为A1，A2，An，输出逻辑变量为F，如下图所示。逻辑电路逻辑电路 FA1A2An图中，图中，F被称为被称为A1，A2，An的逻辑函数，记为的逻辑函数，记为F = f ( A1，A2，An )2.1.2逻辑函数及逻辑函数间的相等逻辑函数及逻辑函数间的相等v逻辑函数的相等逻辑函数的相等设有两个相同变量的逻辑函数 F1 = f1( A1,A2, ,An) F2 = f2( A1,A2, ,An) 若对应于逻辑变量A1 ,A2

8、 , , An的任何一组取值，F1和F2的值都相同，则称函数F1和F2相等，记作F1= F2 。如何判断两个逻辑函数是否相等？如何判断两个逻辑函数是否相等？通常有两种方法：真值表法，代数法。2.1.3 逻辑函数的表示法逻辑函数的表示法v逻辑表达式逻辑表达式逻辑表达式是由逻辑变量和“或”、“与”、“非”3种运算符以及括号所构成的式子。例：运算的优先级运算的优先级：非与异或=同或或BABABABAA,BfF2.1.3 逻辑函数的表示法逻辑函数的表示法v真值表真值表依次列出一个逻辑函数的所有输入变量取值组合及其相应函数值的表格称为真值表真值表。例：CABAFABCF00000011010001111

9、0011011110011102.1.3 逻辑函数的表示法逻辑函数的表示法v卡诺图卡诺图卡诺图是由表示逻辑变量所有取值组合的小方格所构成的平面图。这种用图形描述逻辑函数的方法，在逻辑函数化简中十分有用，将在后面结合函数化简问题进行详细介绍。 1.1 HTML简介简介2.2 逻辑代数的基本定理和规则逻辑代数的基本定理和规则 2.2.1 基本定理基本定理 v公理公理v 公理公理 1：交交 换换 律律A + B = B + A AB = B Av 公公 理理 2：结：结 合合 律律(A + B) + C = A + ( B + C )( AB ) C = A( B C )2.2.1 基本定理基本定理

10、 v公理公理v 公理公理 3：分分 配配 律律A + ( BC ) = (A + B)(A + C) A( B + C) = AB + ACv 公公 理理 4： 01 律律A + 0 = A A 1 = AA + 1 = 1 A 0 = 0 2.2.1 基本定理基本定理 v公理公理v 公理公理 5：互互 补补 律律0AA 1AA公理是一个代数系统的基本出发点，无需加以证明。公理是一个代数系统的基本出发点，无需加以证明。2.2.1 基本定理基本定理 v定理定理v 定理定理 1：0 + 0 = 01 + 0 = 10 0 = 01 0 = 00 + 1 = 11 + 1 = 10 1 = 01 1

11、 = 1v 定理定理 2：重：重 叠叠 律律A + A = A ；A A = A2.2.1 基本定理基本定理 v定理定理v 定理定理 3：吸吸 收收 律律A + A B = A；A ( A + B ) = Av 定理定理 4：吸：吸 收收 律律A+AB = A+B ;A(A+B) = ABv 定理定理 5：对：对 合合 律律A = A 2.2.1 基本定理基本定理 v定理定理v 定理定理 6：反反 演演 律律A + B = A B；A B = A + Bv 定理定理 7：AB + A B= A ( A + B ) ( A+ B ) = A 2.2.1 基本定理基本定理 v定理定理v 定理定理

12、8：包：包 含含 律律A B + A C + B C= A B + A C（A + B）（A + C）（B+ C）=（A + B）（A + C）推广之推广之：CAABBCD(G+E)CAABBCCAABBCD (G+E)BCCAAB吸收吸收2.2.2 重要规则重要规则 v代入规则代入规则任何一个含有变量A的逻辑等式,如果将所有出现A的位置都代之以同一个逻辑函数F，则等式仍然成立。这个规则称为代入规则。代入规则。 f (A1, A2, , An)f (A1, A2, , An)1例：由式例：由式 (A+A=1) ，故，故同样有等式：同样有等式：2.2.2 重要规则重要规则 n证明n个变量的反演律

13、：nnAAAAAA2121.nnAAAAAA.21212.2.2 重要规则重要规则 v反演规则反演规则如果将逻辑函数F中所有的“ ”变成“+”；“+”变成“ ”； “0”变成“1”；“1”变成“0”；原变量变成反变量；反变量变成原变量；所得到的新函数是原函数的反函数F。 即即: “ ”, “+”, “0” , “1”, “原变量”, “反变量” “+” , “ ” , “1” , “0”, “反变量”, “原变量”2.2.2 重要规则重要规则 v反演规则反演规则例例1 已知函数，求其反函数 DCBAFFD)C()B(AF2.2.2 重要规则重要规则 v反演规则反演规则例例2 已知函数 ，求其反

14、函数 F)(EDCBAF)(EDCBAFEDCBAF与变或时与变或时要加括号要加括号2.2.2 重要规则重要规则 v反演规则反演规则例例3：已知：已知 ，求其反函数。，求其反函数。 CBBCAABF)()()(CBCBABAF 长非号不变长非号不变2.2.2 重要规则重要规则 v反演规则反演规则利用反演规则时须注意以下两点：利用反演规则时须注意以下两点：v 使用反演规则时, 应注意保持原函式中运算符号的优先优先顺序不变顺序不变。仍需遵守“先括号，然后乘，最后加”的运算顺序。v 不属于单个变量上的长非号长非号，在利用反演规则时应保持保持不变不变，而长非号下的变量及“”和“”号符号仍按反演规则处理

15、。2.2.2 重要规则重要规则 v反演规则反演规则例例4: 求： 已知： F EDCBA F 解：）ED（CBAF 2.2.2 重要规则重要规则 v反演规则练习反演规则练习CDCBAFCDCBAF)(EDCBAF)(EDCBAF)(2.2.2 重要规则重要规则 v对偶规则对偶规则如果将逻辑函数表达式F中所有的“”变成“+”,“+”变成“”，“0”变成“1”，“1”变成“0”，并保持原函数中的运算顺序不变，则所得到的新的逻辑表达式称为函数F的对偶式，并记作对偶式，并记作F 。即即: “ ”, “+”, “0” , “1”, “变量” “+” , “ ” , “1” , “0”, 不变2.2.2

16、重要规则重要规则 v对偶规则对偶规则若两个逻辑函数表达式F和G相等，则其对偶式F和G 也相等。这一规则称为对偶规则对偶规则。利用对偶规则可以使定理、公式的证明减少一半。2.2.3 复合逻辑复合逻辑 v一、与非逻辑一、与非逻辑 v 表达式：表达式：v 逻辑功能：逻辑功能：只要变量A、B、C、中有一个为0，则函数F为1；仅当变量A、B、C、全部为1时，函数F为0。v 门电路：门电路：与非门 CBAF2.2.3 复合逻辑复合逻辑 v 使用与非门可以实现与、或、非三种基本运算：使用与非门可以实现与、或、非三种基本运算：1 BABABAF11BABABAF1AAF2.2.3 复合逻辑复合逻辑 v或非逻辑

17、或非逻辑v 表达式：表达式：v 逻辑功能：逻辑功能：只要变量A、B、C中有一个为1，则函数F为0；仅当变量A、B、C全部为0时，函数F为1。v 门电路：门电路：或非门 CBAF2.2.3 复合逻辑复合逻辑 v与或非逻辑与或非逻辑v 表达式：表达式：v 逻辑功能：逻辑功能：仅当每一个“与项”均为0时，才能使F为1，否则F为0。v 门电路：门电路：与或非门 CDABF2.2.3 复合逻辑复合逻辑 v异或逻辑异或逻辑v 表达式：表达式：v 逻辑功能：逻辑功能：变量A、B取值相同，F为0；变量A、B取值相异，F为1。v 门电路：门电路：异或门BABABAF2.2.3 复合逻辑复合逻辑 v异或逻辑异或逻

18、辑v 根据异或逻辑的定义可知：根据异或逻辑的定义可知：0010AAAAAAAA2.2.3 复合逻辑复合逻辑 v同或逻辑同或逻辑v 表达式：表达式：v 逻辑功能：逻辑功能：变量A、B取值相同，F为1；变量A、B取值相异，F为0。v 门电路：门电路：同或门v 同或逻辑与异或逻辑既互为相反，又互为对偶同或逻辑与异或逻辑既互为相反，又互为对偶AF ABBAB1.1 HTML简介简介2.3 逻辑函数表达式的形式与变换逻辑函数表达式的形式与变换2.3.1 逻辑函数表达式的两种基本形式逻辑函数表达式的两种基本形式 v“与与-或或”表达式表达式 v 定义：定义：指由若干“与项”进行“或”运算构成的表达式v 举

19、例：举例：CCBABAF(A,B,C)2.3.1 逻辑函数表达式的两种基本形式逻辑函数表达式的两种基本形式 v“或或-与与”表达式表达式 v 定义：定义：指由若干“或项”进行“与”运算构成的表达式v 举例：举例：C)DB)(ACB)(BA(F(A,B,C,D)2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 为了在逻辑问题的研究中使逻辑功能能和唯一的逻辑为了在逻辑问题的研究中使逻辑功能能和唯一的逻辑表达式对应，引入了逻辑函数表达式的标准形式。逻辑函表达式对应，引入了逻辑函数表达式的标准形式。逻辑函数表达式的标准形式是建立在最小项和最大项概念的基础数表达式的标准形式是建立在最小项和最

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

21、最小项 ABC可用 m5 表示。ABC101m5 (5)10 2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 v 最小项的性质：最小项的性质： 只有一组取值使只有一组取值使 mi1； 相同变量构成的两个不同最小项相相同变量构成的两个不同最小项相“与与” 为为0； 全部最小项之和等于全部最小项之和等于1，即，即mi1； n变量构成的最小项有变量构成的最小项有n个相邻最小项。个相邻最小项。当ji 时Y，0jimm2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 v最大项最大项v 定义：定义：如果一个具有n个变量函数的“或项”包含全部n个变量，每个变量都以原变量或反变量形式

22、出现一次，且仅出现一次，则该“或项”被称为最大项。v 最大项的数目：最大项的数目： n个变量可以构成2n个最大项。2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 v 简写：简写：用Mi表示最小项下标下标i的取值规则是：的取值规则是：按照变量顺序将最大项中的原变最大项中的原变量用量用0表示，反变量用表示，反变量用1表示表示，由此得到一个二进制数，与该二进制数对应的十进制数即下标i的值。 例如，3变量A、B、C构成的最大项可用 M5表示。A+B+C101(5)10 M5 2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 v 最大项的性质：最大项的性质： 只有一组取值使只有

23、一组取值使 Mi0 ； 相同变量构成的两个不同最大项相相同变量构成的两个不同最大项相“或或”为为1 ； 全部最大项之积等于全部最大项之积等于0，即，即Mi0； n变量构成的最大项有变量构成的最大项有n个相邻最大项。个相邻最大项。当ji 时，1jiMM。2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 两变量最小项、最大项的真值表如下：两变量最小项、最大项的真值表如下：m2 000101001000M3 M2 M 1 M 0 m 3 m1m 0 001011101101101101110 00 11 01 1A B最最 大大 项项 最最 小小 项项 变变 量量BABABAABBABA

24、BABA真值表反映了最小项、最大项的有关性质。真值表反映了最小项、最大项的有关性质。 2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 v最小项和最大项的关系最小项和最大项的关系 在同一问题中，下标相同的最小项和最大项互为反函数在同一问题中，下标相同的最小项和最大项互为反函数。或者说，相同变量构成的最小项mi和最大项Mi之间存在互补关系。即 或者iiMmiiMm2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 v逻辑函数表达式的标准形式逻辑函数表达式的标准形式 1、标准、标准“与与 - 或或”表达式表达式 由若干最小项相由若干最小项相“或或”构成的逻辑表达式称为规范构成

25、的逻辑表达式称为规范“与与-或或”表达式，也叫做最小项表达式。表达式，也叫做最小项表达式。 例如，如下所示为一个3变量函数的标准“与-或”表达式： ABCCBACBACBACBAF,该函数表达式又可简写为 F(A，B，C) = m1 + m2 + m4 + m7 = 7,4,2, 1m2.3.2 逻辑函数表达式的标准形式逻辑函数表达式的标准形式 2、标准、标准“或或 -与与”表达式表达式 由若干最大项相由若干最大项相“与与”构成的逻辑表达式称为标准构成的逻辑表达式称为标准“或或-与与”表达式，也叫做最大项表达式表达式，也叫做最大项表达式 。例如，A+B+C、A+B+C、A+B+C为3变量构成的

26、3个最大项，即可得到一个3变量函数的规范“或-与”表达式:F= (A+B+C)(A+B+C)(A+B+C) 该表达式又可简写为: M(1,5,7)MMMC)B,F(A,7512.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 v代数转换法代数转换法1 . 求求标准标准“与与-或或” 式（最小项表达式）式（最小项表达式）一般步骤如下：一般步骤如下： v 第一步：将函数表达式变换成一般“与-或”表达式。v 第二步：反复使用X=X(Y+Y)将表达式中所有非最小项的“与项”扩展成最小项。 2.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 例例 将逻辑函数表达式将逻辑函数表达式 转换成标转换成标准

27、准“与与-或或”表达式。表达式。 AB)CBB(AF(A,B,C) 解解 第一步：第一步：将函数表达式变换成“与-或”表达式。ABCBBAABC)BB)(A(ABBCCABAAB)CBB(AF(A,B,C) 2.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 第二步：第二步：把“与-或”式中非最小项的“与项”扩展成最小项。C)CAB (A)BCA(B)BC(AC)C(BAF(A,B,C)ABCCAB ABCBCABCACBACBACBAABCCABBCACBACBA76310mmmmm),(m763102.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 v代数转换法代数转换法2 .求标准求

28、标准“或或-与与” 式（最大项表达式）式（最大项表达式）一般步骤如下：一般步骤如下： v 第一步：将函数表达式变换成一般“或-与”表达式。v 第二步：反复使用A=(A+B)(A+B)将表达式中所有非最大项的“与项”扩展成最大项。 2.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 例例 将逻辑函数表达式将逻辑函数表达式 转换成标转换成标准准“或或-与与”表达式。表达式。 CBC)A(ABF(A,B,C) 解解 第一步：第一步：将函数表达式变换成“或-与”表达式。CBC)A(ABF(A,B,C)CBCAABCB)C(AB)A()()(CCABABCABAC)CC)(ABA)(BC)(ABBA(

29、C)BA)(CB)(ABA(=12.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 第二步：第二步：将所得“或-与”表达中的非最大项扩展成最大项。C)BA)(CB)(ABA(F(A,B,C)C)BA)(CBC)(ABA)(CBA()CBAC)(BA)(CB(A),M(MMMF(A,B,C)7637632.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 v真值表转换法真值表转换法1 . 求求标准标准“与与-或或” 式（最小项表达式）式（最小项表达式）v 逻辑函数的最小项表达式与真值表具有一一对应的关系。v 方法：方法：真值表上使函数值为1的变量取值组合对应的最小项相“或”,即可构成一个函数的

30、标准“与-或”式 。 v例：求 的最小项表达式。CBBAF(A,B,C)2.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 v例：求 的最小项表达式。CBBAF(A,B,C)A B C F0 0 000 0 100 1 010 1 101 0 011 0 111 1 011 1 10)6 , 5 , 4 , 2(),(mCBAF2.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 v真值表转换法真值表转换法2 . 求求标准标准“或或-与与” 式（最大项表达式）式（最大项表达式）v 逻辑函数的最大项表达式与真值表之间同样具有一一对应的关系。v 方法：方法：真值表上使函数值为0的变量取值组合对应

31、的最大项相“与”即可构成一个函数的标准“或-与”式 。 v例：求 的最大项表达式。CBACACBAF),(2.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 v例：求 的最大项表达式。CBACACBAF),(A B C F0 0 000 0 110 1 000 1 111 0 011 0 101 1 001 1 10),M(F(A,B,C)765202.3.3 逻辑函数表达式的转换逻辑函数表达式的转换 v 任何一个逻辑函数的两种标准形式也是唯一的。任何一个逻辑函数的两种标准形式也是唯一的。v 逻辑函数表达式的唯一性给我们分析和研究逻辑问题逻辑函数表达式的唯一性给我们分析和研究逻辑问题带来了很

32、大的方便。带来了很大的方便。 1.1 HTML简介简介2.4 逻辑函数化简逻辑函数化简2.4 逻辑函数化简逻辑函数化简v为了降低系统成本、减小复杂度、提高可靠性，必须对逻辑函数进行化简。v逻辑函数化简有3种常用方法：代数化简法代数化简法、卡卡诺图化简法诺图化简法和列表化简法列表化简法。2.4.1 代数化简法代数化简法v“与与-或或”表达式的化简表达式的化简最简“与-或”表达式应满足两个条件： 表达式中的“与”项个数最少； 在满足上述条件的前提下，每个“与”项中的变量个 数最少。满足上述两个条件可以使相应逻辑电路中所需门的数量以满足上述两个条件可以使相应逻辑电路中所需门的数量以及门的输入端个数均

33、为最少，从而使电路最经济。及门的输入端个数均为最少，从而使电路最经济。“与与-或或”表达式的化简表达式的化简v常用的方法常用的方法（1）并项法）并项法 利用定理AB+AB=A，将两个“与”项合并成一个“与”项，合并后消去一个变量。例如， ABC+ABC=AB“与与-或或”表达式的化简表达式的化简v常用的方法常用的方法（2）吸收法吸收法 利用定理A + AB = A ，吸收多余的项。例如， AB+ABC=AB“与与-或或”表达式的化简表达式的化简v常用的方法常用的方法（3）消去）消去法法 利用定理A+AB=A+B消去多余变量。例如， AB+AC+BC=AB+(A+B)C=AB+C“与与-或或”表

34、达式的化简表达式的化简v常用的方法常用的方法（4）配项法）配项法利用公理A1=A和公理A+A=1，先从函数式中适当选择某些“与”项，并配上其所缺的一个合适的变量，然后再利用并项、吸收和消去等方法进行化简。例如，CBABCACBACBACBBACCBACBAACBBABACBCBBA CACBBA“与与-或或”表达式的化简表达式的化简v例例1：化简：化简解：解：DEEBBDCAABDAADFDEEBBDCAABDAADFDEEBBDCAABADEEBBDCAADEEBBDCAEBBDCA“与与-或或”表达式的化简表达式的化简v例例2：化简：化简解：解：DCABDBCAFDCABDBCAFDCAD

35、BCADCADCACBADCAACBADCCBA“与与-或或”表达式的化简表达式的化简v例例3：化简：化简解：解：ADEDBDBCBCBCAABFADEDBDBCBCBCAABFADEDBDBCBCBCBAADEDBDBCBCBCBAADEDBDBCBCBADBDBCBCBADBCCDBDDCBCBADBDCBCDBDCBDCBCBADBDCCBA“与与-或或”表达式的化简表达式的化简v例例4：化简：化简解：解： CBADCBDDBCF DBCBADDBCCBADBCDBCCBADCBDBCCBADCBDDBCF “与与-或或”表达式的化简表达式的化简v例例3：化简：化简解：解：CBACBAC

36、BAF)( )(CBACCBACACBACBACBACBACBACBACBAF )()( )()( )()(“与与-或或”表达式的化简表达式的化简v练习：练习：CBCAABF2.DCBDCACBAF1.ABDDCABCCDBAACF3.BDADEBEABDBCAF)(4.2.4.2 卡诺图化简法卡诺图化简法v一、卡诺图的构成一、卡诺图的构成v定义：定义：卡诺图是一种平面方格图，每个小方格代表一卡诺图是一种平面方格图，每个小方格代表一个最小项，且几何相邻的方格逻辑相邻。个最小项，且几何相邻的方格逻辑相邻。v结构特点：结构特点： n个变量的卡诺图由个变量的卡诺图由2n个小方格构成个小方格构成 几何

37、图形上处在几何图形上处在相邻、相对、相重相邻、相对、相重位置的小方格所代位置的小方格所代表的最小项为相邻最小项表的最小项为相邻最小项 2.4.2 卡诺图化简法卡诺图化简法v卡诺图的构成卡诺图的构成v 两变量（两变量（A, B）卡诺图：）卡诺图：m0 m2m1 m3 0101ABAB 0101BA BABA ABBBAA2.4.2 卡诺图化简法卡诺图化简法v卡诺图的构成卡诺图的构成v 三变量（三变量（A, B, C）卡诺图：）卡诺图：m0 m2 m6 m4m1 m3 m7 m500 01 11 1001ABC00 01 11 1001ABCCBA CBACABCBA CBA BCAABCCBA

38、AACCBBB2.4.2 卡诺图化简法卡诺图化简法v卡诺图的构成卡诺图的构成v 四变量（四变量（A, B, C, D）卡诺图：）卡诺图：0 4 12 81 5 13 9 3 7 15 11 2 6 14 1000 01 11 1000011110ABCD2.4.2 卡诺图化简法卡诺图化简法v卡诺图的构成卡诺图的构成v 五变量（五变量（A, B, C, D, E）卡诺图：）卡诺图：000 001 011 01000011110ABCDE110 111 101 1001820302610146219233127111573172129259135116202824812402.4.2 卡诺图化简法

39、卡诺图化简法v 卡诺图特点：逻辑相邻的最小项进行或运算可以消去互卡诺图特点：逻辑相邻的最小项进行或运算可以消去互反变量。反变量。三变量卡诺图逻辑相邻举例三变量卡诺图逻辑相邻举例00 01 11 1001ABCCBA CBACABCBA CBA BCAABCCBA 00 01 11 1001ABCCBA CBACABCBA CBA BCAABCCBA 相接相接相对相对2.4.2 卡诺图化简法卡诺图化简法四变量卡诺图逻辑相邻举例四变量卡诺图逻辑相邻举例相接相接相对相对相对相对00 01 11 1000011110ABCDDCBA DCBA DCBA DCBA DCBA DCBA DCBA DCBA

40、 DCBA DCBA ABCDCDBADCBA DCBA DABCDCBA2.4.2 卡诺图化简法卡诺图化简法v归纳起来，卡诺图在构造上具有以下两个特点：归纳起来，卡诺图在构造上具有以下两个特点： n个变量的卡诺图由2n个小方格组成，每个小方格代表一个最小项； 卡诺图上处在相邻、相对、对称位置的小方格所代表的最小项为相邻最小项。 在n个变量的卡诺图中，能从图形上直观、方便地找到每个最小项的n个相邻最小项。2.4.2 卡诺图化简法卡诺图化简法v二、逻辑函数在卡诺图上的表示二、逻辑函数在卡诺图上的表示 v 1、给定逻辑函数为标准、给定逻辑函数为标准“与与-或或”表达式表达式方法：方法：例如，例如，

41、3 3变量函数变量函数 的卡诺图如下图的卡诺图如下图所示。所示。 7 , 3 , 2 , 1,mCBAFm0 m2 m6 m4m1 m3 m7 m500 01 11 1001ABC1 1 1 1 0000在只需卡诺图上找出和表达式中最小项对应的小方格填上1，其余小方格填上0，即可得到该函数的卡诺图。2.4.2 卡诺图化简法卡诺图化简法v二、逻辑函数在卡诺图上的表示二、逻辑函数在卡诺图上的表示 v 2、逻辑函数为一般、逻辑函数为一般“与与-或或”表达式表达式 方法：方法：可根据“与”的公共性和“或”的叠加性作出相应卡诺图。 例如，3变量函数 的卡诺图。 CAABF1 1 1 100 01 11

42、1001ABC00 01 11 1001ABC111 12.4.2 卡诺图化简法卡诺图化简法示例示例:四变量函数四变量函数DCBCDBADBBDF 00 01 11 1000011110ABCD1111111111100 01 11 1000011110ABCD111111 1 112.4.2 卡诺图化简法卡诺图化简法示例示例:四变量函数四变量函数CBACDABDCBAF,0101111100110 0 00 00011110ABCD000111102.4.2 卡诺图化简法卡诺图化简法v三、卡诺图上最小项的合并规律三、卡诺图上最小项的合并规律v规律：规律：根据 ，两个逻辑相邻的最小项可以合并为

43、一项并消去一个变量。v用卡诺图化简逻辑函数的基本原理：用卡诺图化简逻辑函数的基本原理：把卡诺图上相邻最小项的相邻小方格用包围圈“圈”在一起进行合并，达到用一个简单“与”项代替若干最小项的目的。 AAB BA2.4.2 卡诺图化简法卡诺图化简法1 1两个小方格相邻两个小方格相邻, , 或处于某行或处于某行( (列列) )两端时，所代表的两端时，所代表的最小项可以合并，合并后可消去一个变量。最小项可以合并，合并后可消去一个变量。A0110B101001101010BB11011010ABA01000 101 00011110ABC01ABBC2.4.2 卡诺图化简法卡诺图化简法2 2四个小方格组成

44、一个大方格、或组成一行（列）、或四个小方格组成一个大方格、或组成一行（列）、或处于相邻两行（列）的两端、或处于四角时，所代表的最处于相邻两行（列）的两端、或处于四角时，所代表的最小项可以合并，合并后可消去两个变量。小项可以合并，合并后可消去两个变量。11000 101 00011110ABC0100111 010 00011110ABC01BB2.4.2 卡诺图化简法卡诺图化简法4 4变量卡诺图上四个相邻最小项合并的典型情况：变量卡诺图上四个相邻最小项合并的典型情况：00 01 11 10CD1001011001101 0 01AB00011110BDBD00 01 11 10CD011010

45、0110010 1 10AB00011110BDBD00 01 11 10CD0010111100001 0 10AB00011110CDAB2.4.2 卡诺图化简法卡诺图化简法3八个小方格组成一个大方格、或组成相邻的两行八个小方格组成一个大方格、或组成相邻的两行(列列)、或处于两个边行或处于两个边行(列列)时，所代表的最小项可以合并，合并时，所代表的最小项可以合并，合并后可消去三个变量。后可消去三个变量。 1111011001111 0 11 00011110ABCD0001111011111 111 00011110ABC011BD2.4.2 卡诺图化简法卡诺图化简法v画圈的原则：画圈的原

46、则：圈中的方格数是2m个圈尽量大消去的变量多圈尽量少结果乘积项少每个圈中要有新成份没有冗余项圈1得到 F 原函数，圈0得到 F 反函数CDAB0001 11 1000010000010 0011 10 00100 001110不是矩形不是矩形无效圈示例无效圈示例1无效圈示例2CDAB0001 11 1000011111 1111 11111 111101没有新变量无效圈示例无效圈示例2111ABC01 00 01 11 10111ABC01 00 01 11 10合并时只能按 2m 将小方格圈起来，这样才能消去N个变量。无效圈示例无效圈示例31111ABC01 00 01 11 101111ABC01 00 01 11 10无效圈示例无效圈示例411111100011110 00 01 11 10CDAB圈越大越好。圈越大，合并时消去的变量越多，乘积项越简单。ACDDCYADDCY无效圈示