②学与应用他 电子科学与应用物理学 逻辑代数基础 利用逻辑代数化简逻辑函数 ■概述 ■“与-或"”式及“或-与”式 逻辑代数中的三种基本运算 例如：f(A,B,C)=ABC+BC+ABC ■ 逻辑代数的基本公式和常用公式 “与-或”式：与项的逻辑或构成的逻辑函数 ■ 逻辑代数的基本定理 逻辑函数及其表示方法 例如：f(A,B,C)=(A+B+C)(B+OA+B+C) ■逻辑函数的化简方法 “或-与”式：或项的逻辑与构成的逻辑函数 ■具有无关项的逻辑函数及其化简 这两种形式是逻辑函数最常用形式 ⊙个北三生秋置 ⊙个北51热8 ② 电子科学与应用物理学 电子科学与应用理学 利用逻辑代数化简逻辑函数 利用逻辑代数化简逻辑函数 ■目的：减少实现指定逻辑函数的成本 ■两级实现最简形式： ■成本的度量和其它考虑 (1)项数最少 。门的数量 (2)在项数最少的条件下，项内变量数最少 ·电路级的数量（时延） 1.“与或”式的化简 D"D 。门的扇入和扇出 例1：逻辑函数为： 。互连结构的复杂性 F=AB+C+AC+B ·避免冒险 要求：1.画出逻辑图 ·引线数最少 2.化简函数表达式 ○个化天达 ⊙个也三1法 》电子科学与应用物理学院 用逻辑代数化简逻辑函数 ②电学与应用 利用逻辑代数化简逻辑函数 ■化简步骤： 例2：F=AB+AC+BC+CB+BD+DB+ADE(F+G) F=AB+C+AC+B =ABC+BC+CB+BD+DB+ADE(F+G) =(A+B)C+AC+B =A+BC+CB+BD+DB+ADE(F+G) =AC⑧C+AC(B =A+BC+CB+BD+DB ACHC+AC+B =A+BC(D+D)+CB+BD+DB(C+C) -CKAC+B =A+BCD+BCD+CB+BD+DBC+DBC =A+B+C =A+BD+CD+CB ⊙个工A号 ⊙个s人8 1
1 电子科学与应用物理学院 School of Electronic Science & Applied Physics 逻辑代数基础 概述 逻辑代数中的三种基本运算 逻辑代数的基本公式和常用公式 逻辑代数的基本定理 逻辑函数及其表示方法 逻辑函数的化简方法 具有无关项的逻辑函数及其化简 电子科学与应用物理学院 School of Electronic Science & Applied Physics 利用逻辑代数化简逻辑函数 “与-或”式及“或-与”式 例如：f(A,B,C)=ABC+BC+ABC “与-或”式: 与项的逻辑或构成的逻辑函数 例如：f(A,B,C)=(A+B+C)(B+C)(A+B+C) “或-与”式: 或项的逻辑与构成的逻辑函数 这两种形式是逻辑函数最常用形式 电子科学与应用物理学院 School of Electronic Science & Applied Physics 利用逻辑代数化简逻辑函数 目的：减少实现指定逻辑函数的成本 成本的度量和其它考虑 门的数量 电路级的数量(时延) 门的扇入和扇出 互连结构的复杂性 避免冒险 引线数最少 电子科学与应用物理学院 School of Electronic Science & Applied Physics 利用逻辑代数化简逻辑函数 两级实现最简形式: (1) 项数最少 (2) 在项数最少的条件下，项内变量数最少 1 . “与-或”式的化简 要求：1. 画出逻辑图 2.化简函数表达式 例1：逻辑函数为： F=AB+C+AC+B 电子科学与应用物理学院 School of Electronic Science & Applied Physics 利用逻辑代数化简逻辑函数 化简步骤： F=AB+C+AC+B =(A+B)C+AC+B =AC+BC+AC+B =AC+C+AC+B =C+AC+B =A+B+C 电子科学与应用物理学院 School of Electronic Science & Applied Physics 利用逻辑代数化简逻辑函数 例2：F=AB+AC+BC+CB+BD+DB+ADE(F+G) =A+BC+CB+BD+DB+ADE(F+G) =A+BC(D+D)+CB+BD+DB(C+C) =A+BCD+BCD+CB+BD+DBC+DBC =A+BD+CD+CB =ABC+BC+CB+BD+DB+ADE(F+G) =A+BC+CB+BD+DB
② 电子科学与应用物理学 电子科学与应用物理学标 利用逻辑代数化简逻辑函数 卡诺图化简法 ■布尔代数化简的局限性： 1.逻辑函数的最小项表达式 a.最小项 量小现g码的以 ■化简方法技巧性太强 ABC 000 m。 对于n个变量的逻辑函数，它 的与”项如果包含n个文字， ABC 010 ·难以判断最后结果是否最简 即每个变量以原变量或反变 量的形式出现一次且仅出现 ABC 110 m。 ■卡诺图法可以较简便地得到最简结果 一次，那么这个与项就称为 ABC 011 m 该函数的最小项。 ABC 111 m ⊙个北三生秋誉 e ② 电子科学与应用物理学 电子科学与应用物理学 逻辑函数的最小项表达式 逻辑函数的最小项表达式 如果函数的“与或”式全由最小项组成， 例如：将函数F(A,B,C)=AB+AC 这个“与或”式就叫规范的“与-或"式，或 写成最小项表达形式 叫最小项表达式。 F=AB+AC 例如： =AB(C+C)+AC(B+B) (A.B.C)=ABC+ABC+ABC+ABC+ABC =ABC+ABC+ABC+ABC =m,十，+m。十m3十m =m(1,3,6,7) =∑m0.236,7) 注意：最小项中的变量顺序 ○公化天么营 ⊙个也二1法行 ②子学学 ②电学与应用 真值表与最小项表达式的关系 逻辑函数的最大项表达式 A.B.C)=ABC+ABC+ABC+ABC 最大项： 大1编号 (A.B.C)=ABC+ABC+ABC+ABC 对于n个变量的逻辑函 A+B+C 000M. 行数物入 数，它的或"项如果包含 A+B+C 001 M n个文字，即每个变量以 原变量或反变量的形式 A+B+C 010 M. 出现一次且仅出现一 4+B+C 011 M 次，那么这个或项就称 为该函数的最大项。 万+E+c111M, ⊙个机2A学 ⊙个人香 2
2 电子科学与应用物理学院 School of Electronic Science & Applied Physics 利用逻辑代数化简逻辑函数 布尔代数化简的局限性： 化简方法技巧性太强 难以判断最后结果是否最简 卡诺图法可以较简便地得到最简结果 电子科学与应用物理学院 School of Electronic Science & Applied Physics 卡诺图化简法 1. 逻辑函数的最小项表达式 a. 最小项 对于n个变量的逻辑函数，它 的“与”项如果包含n个文字， 即每个变量以原变量或反变 量的形式出现一次且仅出现 一次，那么这个与项就称为 该函数的最小项。 电子科学与应用物理学院 School of Electronic Science & Applied Physics 逻辑函数的最小项表达式 如果函数的“与-或”式全由最小项组成， 这个“与-或”式就叫规范的“与-或”式，或 叫最小项表达式。 例如： 电子科学与应用物理学院 School of Electronic Science & Applied Physics 逻辑函数的最小项表达式 例如：将函数 F(A,B,C)=AB+AC 写成最小项表达形式 F=AB+AC =AB(C+C)+AC(B+B) =ABC+ABC+ABC+ABC =m(1,3,6,7) 注意：最小项中的变量顺序 3 电子科学与应用物理学院 School of Electronic Science & Applied Physics 真值表与最小项表达式的关系 行 数 输 入 输 出 反函数输出 1 1 电子科学与应用物理学院 School of Electronic Science & Applied Physics 逻辑函数的最大项表达式 对于n个变量的逻辑函 数，它的“或”项如果包含 n个文字，即每个变量以 原变量或反变量的形式 出现一次且仅出现一 次，那么这个或项就称 为该函数的最大项。 最大项：
② 电子科学与应用物理学 逻辑函数的最大项表达式 真值表与最大项表达式的关系 如果函数的“或-与”式全由最大项组成， f(A B C)=(A+B+CX(A+B+C4+B+CX(4+B+C) 这个“或-与”式就叫规范的或-与”式，或 =ABC+ABC +ABC+ABC 叫最大项表达式。 例如： 000 001 0← f(A.B.C)=(A+B+CXA+B+CX+B+C)(+B+C) 010 000 001 100 101 =M。·M,·M,·M5 =1M(0,l4.5) ←A ⊙个北三生秋置 ⊙个北51热8 ② 电子科学与应用物理学份 习题 @ 电子科学与应用尚理学织 卡诺图 2.卡诺图的结构 B P61-62题2.10、2.14、2.15 油 二变量卡诺图 BC 0001110 A ma ms my ma 三变量卡诺图 ⊙个化大人 ⊙个地三法量 ②子程学与应浮 卡诺图 ②学与应用理 卡诺图 CD 0 CDE 0 11 10 AB 000 001011 010 11011 10 00 01 B 1 四变量卡诺图 五变量的卡诺图 ⊙个工A号 3
3 电子科学与应用物理学院 School of Electronic Science & Applied Physics 如果函数的“或-与”式全由最大项组成， 这个“或-与”式就叫规范的“或-与”式，或 叫最大项表达式。 逻辑函数的最大项表达式 例如： 000 001 100 101 电子科学与应用物理学院 School of Electronic Science & Applied Physics 真值表与最大项表达式的关系 f (A, B, C) 行 数 输入 输 出 电子科学与应用物理学院 School of Electronic Science & Applied Physics 习 题 P61-62 题2.10、2.14、2.15 电子科学与应用物理学院 School of Electronic Science & Applied Physics 卡诺图 2.卡诺图的结构 2 3 0 1 B B A A 0 1 0 A 1 B m0 m2 m1 m3 二变量卡诺图 4 5 7 6 0 1 3 2 C C A A A BC m0 m4 m1 m5 m7 m3 m2 m6 00 01 11 10 0 1 B B 三变量卡诺图 电子科学与应用物理学院 School of Electronic Science & Applied Physics 卡诺图 8 9 11 10 12 13 15 14 4 5 7 6 AB 0 1 3 2 CD00 01 11 10 00 01 11 10 A B C D 四变量卡诺图 电子科学与应用物理学院 School of Electronic Science & Applied Physics 卡诺图 五变量的卡诺图 A B C D E E
② 电子科学与应用物理学标 卡诺图 电子科学与应用物理学标 卡诺图 3卡诺图的构成特点： ·每个最大项对应2”-1个小方块，即除去最大项 下标对应的小方块以外的区域。 ·卡诺图是真值表的二维形式。 ·逻辑运算对应卡诺图的关系 ·每个最小项对应一个小方块，其下标对应的方块， 或从变量所属区域直接寻找。 “与”·对应各自函数的公共区域（例如：最小项） ·具有对称性：每个变量以原变量和反变量形式 “或”·对应各自函数区域的总和 将卡诺图各分一半。 ·归属性：最小项对应的方块，一定属于各自组成 “非”-对应函数覆盖之外的区域 的变量区域。 “异或”·除两个函数相交部分，剩余各自和 ⊙个北三生秋置 ⊙个北51热学 ② 电子科学与应用物理学网 卡诺图 电子科学与应用物理学松 卡诺图 4怎样用卡诺图表示逻辑函数： “或-与”式同理可得以上两种对偶方法 「。化函数为规范的“与-或“式，再 “与-或“式 利用下标直接填入卡诺图 5卡诺图的一些重要性质 、·直接填写法 相邻一有共同的边界 例如：F=∑4(2,3,5,7,15) F(A,B,C,D)=AB+AC+D 。小方块的相邻 相对-同行（或列）两端 (可以是大块相邻) 11 相重一两个相邻图对折位置 相同的小方块 以上相邻的小方块只有一个变量不同的最小项，称 为逻辑相邻。对于n个变量函数，每个小方块有n个 10 相邻的小方块。 公机天于长智 ⊙个也二1法行 清电子科学与应用物理学院 ② 电子科学与应用物理学酸 卡诺图的一些重要性质 卡诺图的一些重要性质 。块的合并：两个同一级别的相邻块（三种情况）， ■卡诺图上的极大块 可以合并成一个较大块。 定义：不能再合并的维块称为极大块，也就是说此维 为了反映合并后块的不同级别，引入“维”的概念： 块不被其它维块包含，在卡诺图上用圈圈起来， n螳块包含小方块数相邻块数维与项“与项中变量致 CDE AB 00000101101011D111101100 0:块 20 m-0 0雌与项 -0 00 1块 21 -1 1维与项 2维块 01 1 21 n-2 2维与项 m2 11 1 1 n块 2 0 n与项 0 ① 注：这里n为逻辑函数的变量数 ⊙个机2 4
4 电子科学与应用物理学院 School of Electronic Science & Applied Physics 卡诺图是真值表的二维形式。 卡诺图 3 卡诺图的构成特点： 每个最小项对应一个小方块，其下标对应的方块， 或从变量所属区域直接寻找。 具有对称性：每个变量以原变量和反变量形式 将卡诺图各分一半。 归属性：最小项对应的方块，一定属于各自组成 的变量区域。 电子科学与应用物理学院 School of Electronic Science & Applied Physics 每个最大项对应2n-1个小方块，即除去最大项 下标对应的小方块以外的区域。 逻辑运算对应卡诺图的关系 “与” - 对应各自函数的公共区域（例如：最小项） “或” - 对应各自函数区域的总和 “非” - 对应函数覆盖之外的区域 “异或” - 除两个函数相交部分，剩余各自和 卡诺图 电子科学与应用物理学院 School of Electronic Science & Applied Physics 4 怎样用卡诺图表示逻辑函数： “与-或”式 化函数为规范的“与-或”式，再 利用下标直接填入卡诺图 直接填写法 例如：F=m(2,3,5,7,15) 4 8 9 11 10 12 13 15 14 4 5 7 6 0 1 3 2 AB CD 00 01 11 10 00 01 11 10 1 1 1 1 1 A B C D F(A,B,C,D)=AB+AC+D 1 1 1 1 1 1 1 1 1 1 1 1 卡诺图 电子科学与应用物理学院 School of Electronic Science & Applied Physics “或- 与”式同理可得以上两种对偶方法 5 卡诺图的一些重要性质 小方块的相邻 (可以是大块相邻) 相邻 – 有共同的边界 相对 – 同行(或列)两端 相重 – 两个相邻图对折位置 相同的小方块 以上相邻的小方块只有一个变量不同的最小项，称 为逻辑相邻。对于n个变量函数，每个小方块有n个 相邻的小方块。 卡诺图 电子科学与应用物理学院 School of Electronic Science & Applied Physics 卡诺图的一些重要性质 块的合并：两个同一级别的相邻块(三种情况)， 可以合并成一个较大块。 为了反映合并后块的不同级别，引入“维”的概念： n-0 n-1 n-2 . . 0 0维与项 1维与项 2维与项 . . n维与项 n-0 n-1 n-2 . . 0 20 21 22 . . 2n 0维块 1维块 2维块 . . n维块 n维块 包含小方块数 相邻块数 n维“与”项 “与”项中变量数 注：这里n为逻辑函数的变量数 电子科学与应用物理学院 School of Electronic Science & Applied Physics 卡诺图上的极大块 定义：不能再合并的维块称为极大块，也就是说此维 块不被其它维块包含，在卡诺图上用圈圈起来。 CDE AB 000 001 011 010 110 111 101 100 00 01 11 10 卡诺图的一些重要性质 1 1 1 1 1 1 1 1 1 1 1 1 1
电科学与应用理学 卡诺图的一些重要性质 用卡诺图化简逻辑函数 例如：下列函数为最简“与或”式 ·卡诺图的最小覆盖：用最少的极大块覆盖全部填1的块 F=∑5m(3,79,10,13,14,16,18,20,22,25,26,29) 寻找最小覆盖的原则： CDE ·产生所有的极大块 1 1 ·挑选出唯一包含0维块的所有极大块 1 7 1 ·其次尽量选择维块高的极大块 1 1 ① 1① ·如果选择的极大块已被前面所选极大块覆盖 此块应丢掉 F=ABDE+BDE+ABDE+ABE+ACDE ⊙个化二量 ② 电子科学与应用物理学份 电子科学与应用物理学松 用卡诺图化简逻辑函数 逻辑代数基础 例如：下列函数为最简“与或”式和最简的“或与”式 。概述 F(A,B,C,D)=ABC+BCD+BCD+CD+ABD ■逻辑代数中的三种基本运算 ■ 逻辑代数的基本公式和常用公式 F=AC+BD ■ 逻辑代数的基本定理 11 运用反演规则 ■ 逻辑函数及其表示方法 F=(A+C)(B+D) 逻辑函数的化简方法 具有无关项的逻辑函数及其化简 F=AB+CD+AD+BC ⊙个化大人 ○个也二1法行 电子科学与应用物理学院 @ 电子科学与应用物理学酸 无关最小项 无关最小项化简 包含无关最小项的逻辑化简 例：Y=A'B'CD+A'BCD+AB'CD 给定约来条件为： 在2个最小项中，一部分最小项并不能决定函数 A'B'CD+A'BCD+ABCD'+AB'C'D+ABCD+ABC D'+AB'CD'=0 的值，我们把这些最小项称为无关最小项 CD c 无关最小项发生在两种情况： AB ·输入某些组合不可能出现（约束项） ·所有输入都可能出现，但其中部分输入对其输出 1 并不关心（任意项） B 化简依据：逻辑函数加上或者去掉无关最小项。 对原函数逻辑功能无影响 ⊙个机2A学 5
5 电子科学与应用物理学院 School of Electronic Science & Applied Physics 卡诺图的最小覆盖：用最少的极大块覆盖全部填1的块 寻找最小覆盖的原则： • 产生所有的极大块 • 挑选出唯一包含0维块的所有极大块 • 其次尽量选择维块高的极大块 • 如果选择的极大块已被前面所选极大块覆盖， 此块应丢掉 卡诺图的一些重要性质 电子科学与应用物理学院 School of Electronic Science & Applied Physics 用卡诺图化简逻辑函数 例如：下列函数为最简“与-或”式 F=5 m(3,7,9,10,13,14,16,18,20,22,25,26,29) F=ABDE+BDE +ABE A B C D E E CDE AB 1 1 1 1 1 1 1 1 1 1 1 1 1 +ABDE +ACDE 电子科学与应用物理学院 School of Electronic Science & Applied Physics 例如：下列函数为最简“与-或”式和最简的“或-与”式 F(A,B,C,D)=ABC+BCD+BCD+CD+ABD A B C D 1 1 1 1 1 1 1 1 1 F=AB+CD+AD+BC F=AC+BD 运用反演规则 F=(A+C)(B+D) 用卡诺图化简逻辑函数 电子科学与应用物理学院 School of Electronic Science & Applied Physics 逻辑代数基础 概述 逻辑代数中的三种基本运算 逻辑代数的基本公式和常用公式 逻辑代数的基本定理 逻辑函数及其表示方法 逻辑函数的化简方法 具有无关项的逻辑函数及其化简 电子科学与应用物理学院 School of Electronic Science & Applied Physics 无关最小项 包含无关最小项的逻辑化简 在２n个最小项中，一部分最小项并不能决定函数 的值，我们把这些最小项称为无关最小项 无关最小项发生在两种情况： 输入某些组合不可能出现(约束项) 所有输入都可能出现，但其中部分输入对其输出 并不关心(任意项) 化简依据：逻辑函数加上或者去掉无关最小项， 对原函数逻辑功能无影响 电子科学与应用物理学院 School of Electronic Science & Applied Physics A B CD+ A BC D+AB C D +AB C D+ABCD+ABC D +AB CD =0 Y A B C D A BCD AB C D 给定约束条件为： 例： 无关最小项化简 1 1 1 AB CD A B C D
②子学与色用腰标 ② 电子科学与应用物理学孩 无关最小项化简 无关最小项化简 例：Y=rBCD+ABCD+AB'CD 例：Y=AB'CD+ABCD+ABCD 给定的束条件为： 给定的束条件为： ABCD+A'BCD+ABCD'+ABCD+ABCD+ABCD'+ABCD'=0 A'BCD+ABCD+ABCD'+ABC'D+ABCD+ABCD'+ABCD=0 CD 、CD AB C AB ·AD 01 ×0 0 0 0 1 0 0x1 0 B ×0 XX A 1× 0× A 1八x 0 D AD' ○个化之普 D ② 电子科学与应用物理学网 无关最小项化简 @ 电子科学与应用物理学粉 习题 例：Y(A,B,C,D)=∑m(2,4,68) 约束条项：m,+m。+m.+m:+m+m:+m=0 CD AB 000 P62-64题2.16、2.17、 1 0 2.18、2.22、2.25 A 10 Y=AD'+BD'+CD' ○公化天达营 ○个也三1法行 6
6 电子科学与应用物理学院 School of Electronic Science & Applied Physics 无关最小项化简 1 x 0 x x 0 x x 0 x 1 0 0 1 x 0 AB CD A B C D A B CD+A BC D+ABC D +AB C D+ABCD+ABCD +AB CD =0 Y A B C D A BCD AB C D 给定约束条件为： 例： 电子科学与应用物理学院 School of Electronic Science & Applied Physics 无关最小项化简 1 x 0 x x 0 x x 0 x 1 0 0 1 x 0 AB CD AD AD A B C D A B CD+A BC D+ABC D +AB C D+ABCD+ABCD +AB CD =0 Y A B C D A BCD AB C D 给定约束条件为： 例： 电子科学与应用物理学院 School of Electronic Science & Applied Physics 无关最小项化简 例： 0 2 4 6 8 5 10 11 12 13 14 15 : m m m m m m m Y( A,B,C,D ) m( , , , ) 约束条项 1 0 x x x x x x 1 x 0 1 0 0 0 1 AB CD Y AD BD CD A B C D 电子科学与应用物理学院 School of Electronic Science & Applied Physics 习 题 P62-64 题2.16、2.17、 2.18、2.22、2.25