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

逻 辑 代 数 基 础 第 二 章 逻辑代数是数字系统设计的理论基础和重要数学工具！ 逻辑代数是从哲学领域中的逻辑学发展而来的。 1847年 ,英国数学家乔治 布尔提出了用数学分析方法表 示命题陈述的逻辑结构，并成功地将形式逻辑归结为一种代 数演算，从而诞生了著名的 “布尔代数”。 1938年， 克劳德 向农将布尔代数应用于电话继电器的 开关电路，提出了 “开关代数”。 随着电子技术的发展，集成电路逻辑门已经取代了机械 触点开关，故“开关代数”这个术语已很少使用。为了与“ 数字系统逻辑设计”这一术语相适应，人们更习惯于把开关 代数叫做 逻辑代数。 本章知识要点： 基本概念 ； 基本定理和规则 ； 逻辑函数的表示形式 ； 逻辑函数的化简 。 逻辑代数 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 公理是一个代数系统的基本出发点，无需加以证明。 0AA 1AA A 公 理 5 互 补 律 对于任意逻辑变量 A，存在唯一的 ，使得 2.1.1 逻辑变量及基本逻辑运算 逻辑代数和普通代数一样，是用字母表示其值可以变化 的量，即变量。所不同的是： 1在普通代数中，变量的取值可以是任意实数，而逻 辑代数是 一 种二值代数系统， 任何逻辑变量的取值只有两 种可能性 取值 0或取值 1。 2 逻辑值 0和 1是用来表征矛盾的双方和判断事件真伪 的形式符号，无大小、正负之分。 在数字系统中，开关的接 通与断开，电压的高和低，信号的有和无，晶体管的导通与 截止等两种稳定的物理状态，均可用 1和 0这两种不同的逻辑 值来表征。 一变量 二基本逻辑运算 描述一个数字系统 ， 必须反映一个复杂系统中各开关元 件之间的联系 ， 这种相互联系反映到数学上就是几种运算关 系 。 逻辑代数中定义了 “ 或 ” 、 “ 与 ” 、 “ 非 ” 三种基本 运算 。 1 “ 或 ” 运算 如果决定某一事件是否发生的多个条件中 ， 只要有一 个或一个以上条件成立 ， 事件便可发生 ， 则这种因果关系 称之为 “ 或 ” 逻辑 。 例如，用两个开关并联控制一个灯的照明控制电路。 在上图所示电路中 ， 开关 A和 B并联控制灯 F。 可以看出 ， 当开关 A、 B中有一个闭合或者两个均闭合时 ， 灯 F即亮 。 因此 ， 灯 F与开关 A、 B之间的关系是 “ 或 ” 逻辑关系 。 并联开关电路 A B F 用两个开关并联控制一个灯的电路如下图所示。 逻辑代数中 ， “ 或 ” 逻辑用 “ 或 ” 运算描述 。 其运算符 号为 “ +” ， 有时也用 “ ” 表示 。 两变量 “ 或 ” 运算的关系 可表示为 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。 F 并联开关电路 A B “ 或 ” 运算表 A B F 0 0 0 1 1 0 1 1 0 1 1 1 “或 ” 运算的运算法则： 0 + 0 = 0 1 + 0 = 1 0 + 1 = 1 1 + 1 = 1 实现 “ 或 ” 运算关系的逻辑电路称为 “或”门 。 2 “ 与 ” 运算 如果决定某一事件发生的多个条件必须同时具备，事 件才能发生，则这种因果关系称之为“与”逻辑。 在逻辑代数中 ， “ 与 ” 逻辑关系用 “ 与 ” 运算描述 。 其运算符号为 “ ”， 有时也用 “ ” 表示 。 两变量 “ 与 ” 运算关系可表示为 F = AB 或者 F = A B 即： 若 A、 B均为 1，则 F为 1；否则， F为 0。 A B F 串联开关电路 假定开关闭合状态用 1表示，断开状态用 0表示，灯亮用 1 表示，灯灭用 0表示，则电路中灯 F和开关 A、 B之间的关系即 上表所示的“与”运算关系。 “与 ” 逻辑关系如下表所示。 “ 与 ”运算表 A B F 0 0 0 1 1 0 1 1 0 0 0 1 “与”运算的运算法则 : 0 0 = 0 1 0 = 0 0 1 = 0 1 1 = 1 实现 “ 与 ” 运算关系的逻辑电路称为 “ 与 ” 门 。 3 “ 非 ” 运算 如果某一事件的发生取决于条件的否定，即事件与事件 发生的条件之间构成矛盾，则这种因果关系称为“非”逻辑 。 在逻辑代数中，“非”逻辑用“非”运算描述。其运算 符号为 “ ”，有时也用 “” 表示。“非”运算的逻辑关系 可表示为 F = 或者 F = A， 读作“ F等于 A非 ”。 即 ： 若 A为 0，则 F为 1；若 A为 1，则 F为 0。 例如 ， 在右上图所示电路中 ， 开关与灯并联 。 显然 ， 仅当 开关断开时 ， 灯亮；一旦开关闭合 ， 则灯灭 。 令开关断开用 0 表示 ， 开关闭合用 1表示 ， 灯亮用 1表示 ， 灯灭用 0表示 ， 则电 路中灯 F与开关 A的关系即为上表所示 “ 非 ” 运算关系 。 “ 非 ” 运算的运算法则： ； 实现 “ 非 ” 运算功能的逻辑电路称为 “ 非 ” 门 ， 有时又称 为 “ 反相器 ” 。 A 开关与灯并联电路 F “非”逻辑关系可用下表 : “非” 运算表 A F 0 1 1 0 2.1.2 逻辑函数及逻辑函数间的相等 逻辑代数中函数的定义与普通代数中函数的定义类似 ， 即 随自变量变化的因变量 。 但和普通代数中函数的概念 相比 ， 逻辑函数具有如下 特点 ： 1 逻辑函数和逻辑变量一样 ， 取值只有 0和 1两种可 能 ； 2 函数和变量之间的关系是由 “ 或 ” 、 “ 与 ” 、 “ 非 ” 三种基本运算决定的 。 一、逻辑函数的定义 图中， 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) 若对应于逻辑变量 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.“非”运算符下可不加括号，如 ， 等。 2.“与”运算符一般可省略，如 AB可写成 AB。 高 低 3.在一个表达式中 ， 如果既有 “ 与 ” 运算又有 “ 或 ” 运 算 ， 则 按 先 “ 与 ” 后 “ 或 ” 的规则进行运算 ， 可省去括号 ,如 (AB)+(CD)可写为 AB+CD。 注意 :(A+B)(C+D) 不能省略括号 ,即不能写成 A+BC+D ！ 运算优先法则 ： ( ) + 4. (A+B)+C或者 A+(B+C)可用 A+B+C代替； (AB)C或 者 A(BC)可用 ABC代替 。 二、真值表 依次列出一个逻辑函数的所有输入变量取值组合及其相 应函数值的表格称为真值表。 由于一个逻辑变量有 0和 1两种可能的取值， n个逻辑变量 共有 2n种可能的取值组合。因此， 一个 n个变量的逻辑函数， 其真值表有 2n行。 真值表由两部分组成： 左边一栏列出变量的所有取 值组合，为了不发生遗漏，通常各 变量取值组合按二进制数码顺序给 出；右边一栏为逻辑函数值。 例如，逻辑函数 的真值表如右表所示。 函数 F的真值 表 A B C F 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 0 三、卡诺图 卡诺图是由表示逻辑变量所有取值组合的小方格所构 成的平面图 。 这种用图形描述逻辑函数的方法 ， 在逻辑函数化简中十 分有用 ， 将在后面结合函数化简问题进行详细介绍 。 描述逻辑逻辑函数的 3种方法各有特点 ,可用于不同场合 。但针对某个具体问题而言，它们仅仅是同一问题的不同描 述形式，相互之间可以很方便地进行变换。 2 .2 逻辑代数的基本定理和规则 根据逻辑代数的公理，可以推导出逻辑代数的基本定理。 常用的有组定理 。 (对定理中的一个表达式加以证明 ) 2.2.1 基本定理 定理 1 0 + 0 = 0 1 + 0 = 1 0 0 = 0 1 0 = 0 0 + 1 = 1 1 + 1 = 1 0 1 = 0 1 1 = 1 证明 ：在公理 4中 ， A表示集合 K中的任意元素 ， 因而可 以是 0或 1。 用 0和 1代入公理 4中的 A， 即可得到上述关系 。 如果以 1和 0代替公理 5中的 A，则可得到如下推论： 定理 2 A + A = A ； A A = A 定理 3 A + A B = A ； A ( A + B ) = A 4 BA 5 B)1 ( A 3 B)(A)A(ABAA 证 明 公理 公理 公理 AX :5 1AA 0AA 1XA 0XA XA 的唯一性有根据公理 但是 因而 令证明 BA B)A(A BABAA 4定理 4 1 5 1A 21 BB A 4 BAB 2 BABABABA 公理 公理 ，公理）（ 公理）（ 公理）（）（）（由于证明 BABA BABA 6 定理 1 0 51 00 2 BBAABABABA 定理 ，公理 公理）（）（而且 BABA 5 的唯一性可得根据公理 ABABA A BABA 7 ）（）（定理 4 A 5 1A 3 BBA BABA 公理 公理 公理）（证明 ）（）（）（）（ 定理 CABA )(CABA ABAABA 8 CB CCBC 41 CA BA 3 B)C ( 1A C)B ( 1A 1 CBA CACBABA 3 ACBACB CABA 5 )A(ACB CABA CBCABA ，公理 公理 公理 公理 公理 证明 2.2.2 重要规则 3条重要规则 :代入规则、反演规则、对偶规则 例如 ， 给定逻辑等式 A(B+C)=AB+AC， 若等式中的 C都用 (C+D)代替 ， 则该逻辑等式仍然成立 ， 即 A B+(C+D) = AB+A(C+D) 代入规则的正确性是显然的 ， 因为任何逻辑函数都和逻 辑变量一样 ， 只有 0和 1两种可能的取值 。 代入规则： 任何一个含有变量 A的逻辑等式 ,如果将所有 出现 A的位置都代之以同一个逻辑函数 F， 则等式仍然成立 。 一、代入规则 代入规则的意义： 利用代入规则可以将逻辑代数公理 、 定理中的变量用任 意函数代替 ， 从而推导出更多的等式 。 这些等式可直接当作 公式使用 ， 无需另加证明 。 注意： 使用代入规则时 ,必须将等式中所有出现同一变量 的地方均以同一函数代替，否则代入后的等式将不成立。 例如，用逻辑函数 F = f(A1,A2, ， An)代替公理 A + = 1 中 的变量 A，便可得到等式 f(A1,A2, ， An) + (A1,A2, ， An) =1 即一个函数和其反函数进行“或”运算，其结果为 1。 即 :“” “ +”， “0” “ 1”，原变量 反变量 二、反演规则 反演规则实际上是定理 6的推广，可通过定理 6和代入规 则得到证明。 例如 ， 已知函数 ， 根据反演规则有 反演规则： 若将逻辑函数表达式 F中所有的 “ ”变成 “ +” ， “ +”变成 “ ”； “0”变成 “ 1”， “1”变成 “ 0”；原变量变成 反变量 ， 反变量变成原变量 。 并保持原函数中的运算顺序不 变 ， 则所得到的新的函数为原函数 F的反函数 。 F 注意 : 使用反演规则时，应保持原函数式中运算符号的 优先顺序不变。 三、对偶规则 如果将逻辑函数表达式 F中所有的 “ ”变成 “ +”,“+”变 成 “ ”， “ 0”变成 “ 1”， “ 1”变成 “ 0”， 并保持原函数中 的运算顺序不变 ， 则所得到的新的逻辑表达式称为函数 F的 对偶式 ， 并记作 F。 例如 ， 例如 ， 已知函数 ， 根据反演规则 得到的反函数应该是 而不应该是 ！ 错误 注意： 1、 如果 F的对偶式是 F， 则 F的对偶式就是 F。 即 ， (F)=F,可见 F和 F互为对偶式 。 2、 一般来说 ， F与对偶式 F 是不相等的 ！ 但不排除特 殊 ！ 若逻辑函数表达式的对偶式就是原函数表达式本身 ， 即 F=F， 则称函数 F为 自对偶函数 。 3、 求逻辑表达式的对偶式时 ， 同样要保持原函数的运 算顺序不变 。 根据对偶规则 ， 当已证明某两个逻辑表达式相等时 ， 即可知道它们的对偶式也相等 。 显然 ， 利用对偶规则可以 使定理 、 公式的证明减少一半 。 对偶规则： 若两个逻辑函数表达式 F和 G相等，则其对 偶式 F和 G也相等。 例如 ， 已知 根据对偶规则对等式两端的表达式取对偶式 ， 即可得 到等式 ABAABA CCBC ）（）（）（）（ CABA )(CABA CB 2.2.3 复合逻辑 实际应用中广泛采用 “ 与非 ” 门 、 “ 或非 ” 门 、 “ 与或 非 ” 门 、 “ 异或 ” 门等门电路 。 这些门电路输出和输入之间 的逻辑关系可由 3种基本运算构成的复合运算来描述 ， 通常将 这种逻辑关系称为 复合逻辑 ， 相应的逻辑门则称为 复合门 。 一、与非逻辑 与非逻辑是由与 、 非两种逻辑复合形成的 ， 可用逻辑函 数表示为 逻辑功能 ： 只要变量 A、 B、 C、 中有一个为 0， 则函数 F为 1；仅当变量 A、 B、 C、 全部为 1时 ， 函数 F为 0。 实现与非逻辑的门电路称为 “ 与非 ” 门 。 由于与非逻辑又可实现 3种基本逻辑 ， 所以 ， 只要有了 与非门便可组成实现各种逻辑功能的电路 ， 通常称与非门 为 通用门 。 采用与非逻辑可以减少逻辑电路中门的种类 ， 提高标准化程度 。 由定理 AB=A+B 不难看出 ， “ 与 ” 之 “ 非 ” 可以产生 “ 或 ” 的关系 。 因此 ， 实际上只要有了与非逻辑便可实现 与 、 或 、 非 3种基本逻辑 。 以两变量与非逻辑为例： 与 : 或 : 非 : 二 、 或非逻辑 逻辑功能： 只要变量 A、 B、 C 中有一个为 1， 则函数 F为 0；仅当变量 A、 B、 C 全部为 0时 ， 函数 F为 1。 实 现或非逻辑的门电路称为 “ 或非 ” 门 。 或非逻辑是由 或 、 非两种逻辑复合 形成的 ， 可用逻辑 函数表示为 与： 或 : 非 : 同样 ， 由定理 可知 ， “ 或 ” 之 “ 非 ” 可 以产生 “ 与 ” 的关系 。 因此 ， 只要有了或非逻辑也可以实 现与 、 或 、 非 3种基本逻辑 。 以两变量或非逻辑为例： 或非门 同样 是一种 通用门 。 三、与或非逻辑 逻辑功能： 仅当每一个 “ 与项 ” 均为 0时 ， F才能为 1， 否则 F为 0。 实现与或非功能的门电路称为 “ 与或非 ” 门 。 显然，可以仅用与或非门组成实现各种功能的逻辑电路。 但实际应用中这样做一般会很不经济，所以，与或非门主要用 来实现与或非形式的函数。必要时可将逻辑函数表达式的形式 变换成与或非的形式。 与或非逻辑是由 3种基本逻辑复合形成的 ， 逻辑函数表达 式的形式为 四、异或逻辑及同或逻辑 逻辑功能： 变量 A、 B取值相同 ， F为 0；变量 A、 B取值 相异 ， F为 1。 实现异或运算的逻辑门称为 “ 异或门 ” 。 1异或逻辑 当多个变量进行异或运算时 ， 可用 两两运算的结果再运 算 ， 也可 两两依次运算 。 异或逻辑是一种 两变量逻辑关系 ， 可用逻辑函数表示为 根据异或逻辑的定义可知： A 0 = A A 1 = A A = 0 A = 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。 实现同或运算的逻辑门称为 “ 同或门 ” 。 同或逻辑也是一种两变量逻辑关系，其逻辑函数表达式为 F = A B = + AB 式中 ， “ ” 为同或运算的运算符 。 两者有区别吗 ？ 同或逻辑与异或逻辑的关系既互为相反 ， 又互为对偶 。 即 ： 由于同或实际上是异或之非 ， 所以实际应用中通常用 异或门 +非门 实现同或运算 。 特性： 当多个变量进行同或运算时 ， 若有奇数个变量的 值为 0， 则运算结果为 0；反之 ， 若有偶数个变量的值为 0， 则运算结果为 1。 2.3 逻辑函数表达式的形式与变换 任何一个逻辑函数的表达式形式都不是唯一的。从应用 的角度出发，讨论 基本形式、标准形式及其相互转换。 2.3.1 逻辑函数表达式的 两种 基本形式 两种基本形式： 指 “ 与 -或 ” 表达式和 “ 或 -与 ” 表达式 。 一 、 “ 与 -或 ” 表达式 “与 -或 ” 表达式： 是指由若干 “ 与项 ” 进行 “ 或 ” 运算 构成的表达式 。 每个 “ 与项 ” 可以是单个变量的原变量或者 反变量 ， 也可由多个原变量或者反变量相 “ 与 ” 组成 。 例如 ， 均为 “ 与项 ” ， 将这 3个 “ 与项 ” 相 “ 或 ” 便可构成一个 3变量函数的 “ 与或 ” 表达式 。 即 二 、 “ 或 -与 ” 表达式 注意： “与项 ” 有时又被称为 “ 积项 ” ， 相应地 “ 与 -或 ” 表达式 又称为 “ 积之和 ” 表达式 。 “或项 ” 有时又被称为 “ 和项 ” ， 相应地 “ 或 与 ” 表达 式又称为 “ 和之积 ” 表达式 。 “或 -与 ” 表达式： 是指由若干 “ 或项 ” 进行 “ 与 ” 运算构 成的表达式 。 每个“或项”可以是单个变量的原变量或者反变量，也可 以由多个原变量或者反变量相“或”组成。 例如 ， 、 、 、 D 均为 “ 或项 ” ， 将这 4 个 “ 或项 ” 相 “ 与 ” 便可构成一个 4变量函数的 “ 或 -与 ” 表达 式 。 即 该逻辑函数是 “ 与 或 ” 式 ？ 不是 ！ 是 “ 或 与 ” 式 ？ 也不是 ！ 但不论什么形式都可以变换成两种基本形式 。 2.3.2 逻辑函数表达式的标准形式 逻辑函数表达式可以被表示成任意的混合形式。 例如： 逻辑函数的两种基本形式都不是唯一的 。 例如 为了在逻辑问题的研究中使逻辑功能能和唯一的逻辑表达 式对应 ， 引入了逻辑函数表达式的 标准形式 。 逻辑函数表达式 的标准形式是建立在 最小项 和 最大项 概念的基础之上的 。 请问逻辑函 数的基本形 式是否唯一？ 一、最小项和最大项 定义 ： 如果一个具有 n个变量的函数的“与项”包含全 部 n个变量，每个变量都以原变量或反变量形式出现一次， 且仅出现一次，则该“与项”被称为 最小项 。有时又将最小 项称为 标准“与项” 。 数目： n个变量可以构成 2n个最小项。 例如 ， 3个变量 A、 B、 C可以构成 、 、 A B C共 8个最小项 。 1最小项 （掌握 4点：定义、数目、简写、性质！） 简写： 用 mi表示最小项。 下标 i的取值规则是： 按照变量顺序将最小项中的原变 量用 1表示，反变量用 0表示，由此得到一个二进制数，与 该二进制数对应的十进制数即下标 i的值。 例如， 3变量 A、 B、 C构成的最小项 可用 m5 表 示。因为 m5 (5)10 1 0 1 A C 在由 n个变量构成的任意 “ 与项 ” 中 ， 最小项是使其值为 1的变量取值组合数最少的一种 “ 与项 ” ， 这也就是最小项 名字的由来 。 （ 4） 性质 - 最小项具有四条性质 性质 1 任意一个最小项 ， 其相应变量有且仅有一种取值 使这个最小项的值为 1。 并且 ， 最小项不同 ， 使其值为 1的变 量取值不同 。 性质 2 相同变量构成的两个不同最小项相“与” 为 0。 因为任何一种变量取值都不可能使两个不同最小项同时 为 1，故相“与”为 0。 即 mi mj = 0 性质 3： n个变量的全部最小项相“或”为 1。 通常借用数学中的累加符号“ ”，将其记为 性质 4： n个变量构成的最小项有 n个相邻最小项。 相邻最小项： 是指除一个变量互为相反外，其余部分均 相同的最小项。例如 ，三变量最小项 A B C和 。 定义 ： 如果一个具有 n个变量函数的 “ 或项 ” 包含全部 n个变量 ， 每个变量都以原变量或反变量形式出现一次 ， 且 仅出现一次 ， 则该 “ 或项 ” 被称为最大项 。 有时又将最大 项称为标准 “ 或项 ” 。 2最大项 数目： n个变量可以构成 2n 个最大项。 例如， 3个变量 A、 B、 C可构成 、 、 、 共 8个最大项。 性质： 最大项具有 4条性质。 性质 1 任意一个最大项，其相应变量有且仅有一种取值 使这个最大项的值为 0。并且，最大项不同，使其值为 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个变量构成的最大项有 n个相邻最大项 。 相邻最大项是指除一个变量互为相反外 ， 其余变量均相 同的最大项 。 两变量最小项、最大项的真值表如下 : m2 0 0 0 1 0 1 0 0 1 0 0 0 M3 M2 M 1 M 0 m 3 m1 m 0 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 1 1 A B 最 大 项 最 小 项 变 量 2变量最小项、最大项真值表 该真值表反映了最小项 、 最大项的有关性质 。 3最小项和最大项的关系 在同一问题中，下标相同的最小项和最大项互为反函数。 或者说，相同变量构成的最小项 mi和最大项 Mi之间存在互补 关系。即 或者 例如 ， 由 3变量 A、 B、 C构成的最小项 m3和最大项 M3之间有 二、逻辑函数表达式的标准形式 逻辑函数表达式的标准形式有 标准 “ 与 -或 ” 表达式 和 标准 “ 或 -与 ” 表达式 两种类型 。 1标准“与 - 或”表达式 由若干最小项相 “ 或 ” 构成的逻辑表达式称为标准 “ 与 -或 ” 表达式 ， 也叫做最小项表达式 。 该函数表达式又可简写为 F(A， B， C) = m1 + m2 + m4 + m7 = 例如 ， 一个 3变量函数的标准 “ 与 -或 ” 表达式 2标准“或 -与”表达式 由若干最大项相 “ 与 ” 构成的逻辑表达式称为标准 “ 或 -与 ” 表达式 ， 也叫做最大项表达式 。 例如 ， 、 、 为 3变量构成的 3 个最大项 ， 对这 3个最大项进行 “ 与 ” 运算 ， 即可得到一个 3 变量函数的标准 “ 或 -与 ” 表达式 该表达式又可简写为 2.3.3 逻辑函数表达式的转换 将一个任意逻辑函数表达式转换成标准表达式有两种 常用方法 : 代数转换法 ， 真值表转换法 。 一、代数转换法 1 . 求标准“与 -或” 式 一般步骤如下： 第一步 ： 将函数表达式变换成一般 “ 与 -或 ” 表达式 。 所谓代数转换法，就是利用逻辑代数的公理、定理和规 则进行逻辑变换，将函数表达式从一种形式变换为另一种形 式。 第二步： 反复使用 将表达式中所有非 最小项的 “ 与项 ” 扩展成最小项 。 例如 ， 将逻辑函数表达式 转 换成标准 “ 与 -或 ” 表达式 。 解 第一步： 将函数表达式变换成“与 -或”表达式。即 第二步： 把 “ 与 -或 ” 式中非最小项的 “ 与项 ” 扩展 成最小项 。 具体地说 ， 若某 “ 与项 ” 缺少函数变量 Y， 则 用 ( )和这一项相与 ， 并将其拆开成两项 。 即 所得标准“与 -或”式的简写形式为 当给出函数表达式已经是 “ 与 -或 ” 表达式时 ， 可直接 进行第二步 。 一般步骤： 第一步： 将函数表达式转换成一般 “ 或 -与 ” 表达式 。 第二步： 反复利用定理 把表达式中 所有非最大项的 “ 或项 ” 扩展成最大项 。 2 . 求一个函数的标准“或 -与” 式 （ 详见教材中举例。 ） 二、真值表转换法 具体： 真值表上使函数值为 1的变量取值组合对应的最 小项相 “ 或 ” ,即可构成一个函数的标准 “ 与 -或 ” 式 。 逻辑函数的最小项表达式与真值表具有一 一对应的关系！ 假定函数 F的真值表中有 k组变量取值使 F的值为 1，其他变 量取值下 F的值为 0，那么，函数 F的最小项表达式由这 k组变量 取值对应的 k个最小项相或组成。 因此，可以通过函数的真值表写出最小项表达式。 1 . 求标准“与 -或” 式 1 0 0 1 1 0 1 1 0 1 1 0 A B C F 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 函数 F的真值表 解 : 首先 ， 列出 F的真值表如下表所示 ， 然后 ， 根据真 值表可直接写出 F的最小项表达式 例如 ， 将函数表达式 变换成标准 “ 与 -或 ” 表达式 。 具体： 真值表上使函数值为 0的变量取值组合对应的最 大项相 “ 与 ” 即可构成一个函数的标准 “ 或 -与 ” 式 。 2 . 求一个函数的标准“或 -与” 式 逻辑函数的最大项表达式与真值表之间同样具有一一对应 的关系。 假定在函数 F的真值表中有 p组变量取值使 F的值为 0，其他 变量取值下 F的值为 1，那么，函数 F的最大项表达式由这 p组 变量取值对应的 p个最大项“相与”组成。 解： 首先 ， 列出 F的真值表如下表所示 。 然后 ， 根据真 值表直接写出 F的最大项表达式 函数 F的真值表 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 1 1 1 0 1 1 0 0 A B C F 0 0 0 0 0 0 1 1 例如 ， 将函数表达式 表示成最 大项表达式的形式 。 由于函数的真值表与函数的两种标准表达式之间存在 一一对应的关系。 任何个逻辑函数的真值表是唯一的！ 任何一个逻辑函数的两种标准形式也是唯一的！ 逻辑函数表达式的唯一性给我们分析和研究逻辑问题 带来了很大的方便。 2.4 逻辑函数化简 实现某一逻辑功能的逻辑电路的复杂性与描述该功能的 逻辑表达式的复杂性直接相关。一般说，逻辑函数表达式越 简单，设计出来的相应逻辑电路也就越简单。 为了降低系统成本、减小复杂度、提高可靠性，必须对 逻辑函数进行化简。 由于 “ 与 -或 ” 表达式 和 “ 或 -与 ” 表达式 可以很方便地 转换成任何其他所要求的形式 。 因此 ， 从这两种基本形式出 发讨论函数化简问题 ， 并将重点放在 “ 与 -或 ” 表达式的化 简上 。 逻辑函数化简有 3种常用方法： 代数化简法 、 卡诺图化 简法 、 列表化简法 。 2.4.1 代数化简法 代数化简法就是运用逻辑代数的公理、定理和规则对逻 辑函数进行化简的方法 。 无固定的步骤可以遵循，主要取决于对逻辑代数中公理 、定理和规则的熟练掌握及灵活运用的程度。 一、“与 -或”表达式的化简 最简“与 -或”表达式应满足两个条件： 1表达式中的“与”项个数最少； 2 在满足上述条件的前提下 ， 每个 “ 与 ” 项中的变量 个数最少 。 满足上述两个条件可以使相应逻辑电路中所需门的数 量以及门的输入端个数均为最少 ， 从而使电路最经济 。 几种常用方法如下： 1并项法 2吸收法 利用定理 3中 A + AB = A ， 吸收多余的项 。 例如 ， 利用定理 7中的 ， 将两个 “ 与 ” 项合并 成一个 “ 与 ” 项 ， 合并后消去一个变量 。 例如 ， AAB BA 3消去法 利用定理 4中 消去多余变量 。 4配项法 利用公理 4和公理 5中的 A1=A及 ， 先从函数式 中适当选择某些 “ 与 ” 项 ， 并配上其所缺的一个合适的变量 ， 然后再利用并项 、 吸收和消去等方法进行化简 。 1AA 例如， 例 1 化简 解： 实际应用中遇到的逻辑函数往往比较复杂，化简时应 灵活使用所学的公理、定理及规则，综合运用各种方法 。 例 2 化简 解 定理 7 二、“或 -与”表达式的化简 最简“或 -与”表达式应满足两个条件： 1表达式中的“或”项个数最少； 2 在满足上述条件的前提下 ， 每个 “ 或 ” 项中的变量 个数最少 。 用代数化简法化简 “ 或 -与 ” 表达式可直接运用公理 、 定理中的 “ 或 -与 ” 形式 ， 并综合运用前面介绍 “ 与 -或 ” 表 达式化简时提出的各种方法进行化简 。 例如， 化简 当对公理、定理中的“或 -与”形式不太熟悉时，可以 采用两次对偶法。 具体如下： 第一步： 对“或 -与”表达式表示的函数 F求对偶，得 到“与 -或”表达式 F； 第二步： 求出 F的最简 “ 与 -或 ” 表达式； 第三步： 对 F再次求对偶 ,即可得到 F的最简 “ 或 -与 ” 表达式 。 解 定理 3 定理 8 例如， 化简 第二步： 化简 F ； 第三步： 对 F求对偶 , 得到 F的最简“或 -与”表达式 解： 第一步： 求 F的对偶式 F； 归纳： 代数化简法的优点是： 不受变量数目的约束；当对公理 、 定理和规则十分熟练时 ， 化简比较方便 。 缺点是： 没有一定的规律和步骤 ， 技巧性很强 ， 而且在 很多情况下难以判断化简结果是否最简 。 2.4.2 卡诺图化简法 卡诺图化简法的 优点：简单、直观、容易掌握 。 一、卡诺图的构成 卡诺图是一种平面方格图，每个小方格代表一个最小项 ，故又称为最小项方格图。 构造特点： (1) n个变量的卡诺图由 2n个小方格构成； (2) 几何图形上处在 相邻、相对、相重 位置的小方格所代 表的最小项为相邻最小项。 卡诺图中最小项的排列方案不是唯一的 ， 但任何一种排 列方案都必须具备以上特点 。 2变量 、 3变量 、 4变量卡诺图如图 (a)、 (b)、 (c)所示： m3 m1 m2 m0 A B 0 1 1 0 ( a ) 0 m5 m4 m7 m6 m3 m1 m2 m0 1 00 01 11 10 AB C ( b ) m10 m14 m6 m2 m11 m15 m7 m3 m9 m8 m13 m12 m5 m1 m4 m0 00 01 11 10 AB CD 00 01 11 10 ( c ) 例如，四变量卡诺图中， 每个最小项有 4个相邻最小项。 m5的 4个相邻最小项分别 是哪些？ m2的 4个相邻最小项？ m2和 m10( 同一行的两端 )， 这种相邻称为 相对相邻 。 m10 m14 m6 m2 m11 m15 m7 m3 m9 m8 m13 m12 m5 m1 m4 m0 00 01 11 10 AB CD 00 01 11 10 在 n个变量的卡诺图中 ， 能从图形上直观 、 方便地找到每 个最小项的 n个相邻最小项 。 10 14 6 2 11 15 7 3 9 8 13 12 5 1 4 0 26 30 22 18 27 31 23 19 25 24 29 28 21 17 20 16 00 01 11 10 000 001 011 010 100 101 111 110 ABC DE ( d ) 5变量卡诺图 此外， 处在“ 相重 ”位置的最小项相邻，如五变量卡诺图 中的 m3，除了几何相邻的 m1， m2， m7和相对相邻的 m11外，还 与 m19相邻。这种相邻称为 重叠相邻 。 注意：卡诺图在构造上具有以下两个特点！ (1) n个变量的卡诺图由 2n个小方格组成 ， 每个小方 格代表一个最小项； (2) 卡诺图上处在相邻 、 相对 、 相重位置的小方格所 代表的最小项为相邻最小项 。 二卡诺图的性质 用卡诺图化简逻辑 函数的 方法： 将卡诺图 上表征相邻最小项的相 邻小方格 “ 圈 ” 在一起 进行合并，用一个简单 “ 与 ” 项代替若干最小 项。 通常把用来包围那 些能由一个简单 “ 与 ” 项代替的若干最小项的 “ 圈 ” 称为 卡诺圈。 性质 ： 可以从图形上直观地找出相邻最小项合并 。 合并 的理论依据是并项定理 。 三、逻辑函数在卡诺图上的表示 当逻辑函数为标准 “ 与 -或 ” 表达式时 ， 只需在卡诺图 上找出和表达式中最小项对应的小方格 填上 1， 其余小方格 填上 0， 即可得到该函数的卡诺图 。 1给定逻辑函数为标准“与 -或”表达式 例如 ， 3变量函数 的卡诺图如下图 所示 。 0 0 0 1 0 1 1 1 0 1 00 01 11 10 AB C F(A,B,C)=m(1,2,3,7) 的卡诺图 例如， 4变量函数 的卡诺图如右图所示。 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 00 01 11 10 AB CD 00 01 11 10 为了表达方便，通常将卡诺图上填 1的小方格称为 1方 格 ，填 0的小方格称为 0方格 。 0方格有时用空格表示。 2逻辑函数为一般“与 -或”表达式 当逻辑函数为一般“与 -或”表达式时，可根据 “与” 的公共性 和 “或”的叠加性 作出相应卡诺图。 四 、 卡诺图上最小项的合并规律 1 两个小方格相邻 , 或处于某行 (列 )两端时 ， 所代表 的最小项可以合并 ， 合并后可消去一个变量 。 例如 ， 2、 3变量卡诺图上两个相邻最小项合并的典型 情况 。 一个函数用卡诺图表示后， 究竟哪些最小项可以合并 呢？ 下面以 2、 3、 4变量卡诺图为例予以说明。 两个相邻最小项合并的情况 A 0 1 1 0 B 1 0 1 0 B 1 1 0 1 B 1 0 1 0 A B A 0 1 0 0 0 1 0 1 00 01 11 10 AB C 0 1 AB BC 注意： 21个最小项合并后的与项可以减少 1个变量 ！ 2 四个小方格组成一个大方格 、 或组成一行 （ 列 ） 、 或 处于相邻两行 （ 列 ） 的两端 、 或处于四角时 ， 所代表的最小 项可以合并 ， 合并后可消去两个变量 。 例如 , 3变量卡诺图上四个相邻最小项合并的典型情况 。 0 0 1 1 1 0 1 0 00 01 11 10 AB C 0 1 B B 1 1 0 0 0 1 0 1 00 01 11 10 AB C 0 1 注意： 22个最小项合并后的与项可以减少 2个变量 ！ 四个相邻最小项合并的几种情况 00 01 11 10 CD 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 AB 00 01 11 10 BD BD 00 01 11 10 CD 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 AB 00 01 11 10 BD BD 00 01 11 10 CD 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 AB 00 01 11 10 CD AB 4变量卡诺图上四个相邻最小项合并的典型情况的。 注意： 22个最小项合并后的与项可以减少 2个变量 ！ 3 八个小方格组连成一体 、 或处于两个边行 (列 )时 ， 所 代表的最小项可以合并 ， 合并后可消去三个变量 。 例如， 3、 4变量卡诺图上八个相邻最小项合并的典型 情况的。 8个相邻最小项合并的两种情况 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 00 01 11 10 AB CD 00 01 11 10 (b) B D 1 1 1 1 1 1 1 1 00 01 11 10 AB C 0 1 1 (a) 注意： 23个最小项合并后的与项可以减少 3个变量 ！ 依此类推，可归纳出 n个变量卡诺图中最小项的合并规 律如下： (1) 卡诺圈中小方格的个数必须为 2m个 ， m为小于或等 于 n的整数 。 (2) 卡诺圈中的 2m个小方格有一定的排列规律 ， 具体地 说 ， 它们含有 m个不同变量 ， (n-m)个相同变量 。 (3) 卡诺圈中的 2m个小方格对应的最小项可用 (n-m)个 变量的 “ 与 ” 项表示 ， 该 “ 与 ” 项由这些最小项中的相同 变量构成 。 (4) 当 m = n 时 ， 卡诺圈包围了整个卡诺图 ， 可用 1表 示 ， 即 n个变量的全部最小项之和为 1。 蕴涵项 :在函数的 “ 与 -或 ” 表达式中 ， 每个 “ 与 ” 项被 称为该函数的蕴涵项 (Implicant)。 显然 ， 在函数卡诺图中 ， 任何一个 1方格所对应的最小 项或者卡诺圈中的 2m个 1方格所对应的 “ 与 ” 项都是函数的 蕴涵项 。 五、卡诺图化简逻辑函数的步骤 1几个定义 质蕴涵项 :若函数的一个蕴涵项不是该函数中其他蕴涵 项的子集 ， 则此蕴涵项称为质蕴涵项 (Prime Implicant),简 称为质项 。 显然，在函数卡诺图中，按照最小项合并规律，如果某 个卡诺圈不可能被其他更大的卡诺圈包含，那么，该卡诺圈 所对应的“与”项为质蕴涵项。 在函数卡诺图中 ， 若某个卡诺圈包含了不可能被任何 其他卡诺圈包含的 1方格 ， 那么 ， 该卡诺圈所对应的 “ 与 ” 项为必要质蕴涵项 。 必要质蕴涵项： 若函数的一个质蕴涵项包含有不被函 数的其他任何质蕴涵项所包含的最小项，则此质蕴涵项被 称为 必要质蕴涵项 (Essential Prime Implicant)，简称为 必 要质项 。 第一步：作出函数的卡诺图； 第二步：在卡诺图上圈出函数的全部质蕴涵项； 2求逻辑函数最简“与 -或”表达式的一般步骤 第三步：从全部质蕴涵项中找出所有必要质蕴涵项； 第四步：求函数的最简质蕴涵项集。 注意： 求函数的最简质蕴涵项集是指当函数的所有必 要质蕴涵项尚不能覆盖卡诺图上的所有 1方格时 ， 则从剩余 质蕴涵项中找出最简的所需质蕴涵项 ， 使它和必要质蕴涵 项一起构成函数的最小覆盖 。 解 用卡诺图化简给定函数的过程如下： 例 1 用卡诺图化简逻辑函数 该题中 ， 5个必要质蕴涵项已将函数的全部最小项覆 盖 ， 故将各卡诺圈对应的与项相或即可得到函数 F的最简 “ 与 -或 ” 表达式为 解 用卡诺图化简给定函数的过程如下： 例 2 用卡诺图化简逻辑函数 即 或者 这里 ， 两个 “ 与 -或 ” 式的复杂程度相同 。 由此可见 ， 一个函数的最简 “ 与 -或 ” 表达式不一定是唯一的 。 请你动手化 简一下这道题 好吗？ 解 用卡诺图化简给定函数的过程如下： 例 3 用卡诺图化简逻辑函数 函数 F的最简 “ 与 -或 ” 表达式为 卡诺图 ? 用卡诺图化简总的原则是： 在满足合并规律的前题下卡诺圈应尽可能大； 根据合并的需要，每个最小项可以被多个卡诺圈包围。 在覆盖函数中所有最小项的前提下，卡诺圈的个数应尽 可能少； 作出 F的卡诺图 ， 求出反函数 的最简 “ 与 -或 ” 表 达式 (合并卡诺图上的 0方格 )； F 对 的最简“与 -或”表达式取反，得到函数 F的最 简“或 -与”表达式。 F 3. 求逻辑函数最简“或 -与”表达式的一般步骤 具体如下： (1) 当给定逻辑函数为“与 或”表达式时，通常采用 “ 两次取反法” 。 例如， 用卡诺图求逻辑函数 的最简 “ 或 -与 ” 表达式 。 解 化简给定函 数的卡诺图如右图 所示 。 1 0 0 1 0 0 0 0 1 1 0 0 1 1 0 1 00 01 11 10 AB CD 00 01 11 10 BD AB CD 图中 ， F的 0方格即反函数 的 1方格 ， 它们代表 的各 个最小项 ， 将全部 0方格合并就可得到反函数 的最简 “ 与 - 或 ” 表达式 再对反函数 的最简 “ 与 -或 ” 表达式 两边取反 ， 即可求得函数的最简 “ 或 -与 ” 表达式 (2) 当给定逻辑函数为“或 与”表达式时，通常采 用 “两次对偶法” 。具体如下： 作出 F对偶式 F 的卡诺图，并求出 F的最简“与 - 或”表达式； 对 F的最简“与 -或”表达式取对偶，得到函数 F 的最简“或 -与”表达式。 例如， 用卡诺图求逻辑函数 的最简 “ 或 -与 ” 表达式 。 F的最简“与 -或”表达式为 首先求出逻辑函数