电子技术基础数字部分第五版(康华光)2 逻辑代数.ppt

1 第2章逻辑代数 2 1逻辑代数2 2逻辑函数的简化 2 教学基本要求 1 熟悉逻辑代数常用基本定律 恒等式和规则 2 掌握逻辑代数的变换和逻辑函数的简化方法 3 2 1 2逻辑代数的基本定律和恒等式 2 1逻辑代数 2 1 4逻辑函数表达式的形式与变换 2 1 3逻辑代数的基本规则 2 1 1逻辑代数的基本概念 4 2 1逻辑代数 逻辑代数是研究数字系统逻辑设计的基础理论 因为任何形式的数字系统都是由一些基本的逻辑电路组成的 而为了描述这些逻辑电路 解决数字系统分析和设计中的各种具体问题 就必须掌握逻辑代数这一重要数学工具 2 1 1逻辑代数的基本概念 逻辑代数是从哲学领域中的逻辑学发展而来的 逻辑学是研究逻辑思维和推理的一门学科 人们为了摆脱逻辑学研究中繁琐的文字描述 使用了一套有效的符号来建立逻辑思维的数学模型 从而将复杂的逻辑问题抽象为一种简单的符号演算 5 这一理论首先是由莱布尼兹 Leibniz 最先提出来的 乔治 布尔 G Boole 总结了前人的研究成果 在1847年进行了系统的论述 这就是有名的 布尔代数 到20世纪初 布尔代数已发展成了一门纯数学的分支学科 此后于1938年 克劳德 向农 C E Shannon 将布尔代数直接应用于电话继电器的开关电路 提出了 开关代数 1952年前后 维奇 Veitch 和卡诺 Karnaugh 先后提出了图解法的概念和方法 产生了卡诺图 这一工程上十分有用的逻辑工具 使布尔代数得到了进一步的丰富和发展 6 随着电子工业技术的发展 集成电路逻辑门已取代了机械触点开关 故 开关代数 已很少用 为了与 数字系统逻辑设计 这一术语相应 人们更习惯将 开关代数 叫做 逻辑代数 可以说 逻辑代数是布尔代数向电子工程领域延伸的结果 目前 逻辑代数已成为研究和设计数字系统的不可缺少的主要数学工具 逻辑代数有一系列的定律 定理和规则 用于对数学表达式进行处理 以完成对逻辑电路的化简 变换 分析和设计 逻辑关系指的是事件产生的条件和结果之间的因果关系 在数字电路中往往是将事情的条件作为输入信号 而结果用输出信号表示 条件和结果的两种对立状态分别用逻辑 1 和 0 表示 7 一 逻辑变量 逻辑代数是由一个逻辑变量集P 常量0 1和 与 或 非 三种运算所构成的代数系统 其中 逻辑变量集是指逻辑代数中的所有变量的集合 它可以用任何字母表示 但每一个变量的取值只可能为常量0或1 8 注意 此处的 0 和 1 不象普通代数那样具有数值大小的意义 而仅仅是表明两种对立的逻辑状态的符号 逻辑代数中的基本逻辑关系只有三种 与 或 非 逻辑代数与普通代数不同 在后者中 变量的取值可以是任意实数 而前者则是一种二值代数 9 二 逻辑运算 共有三种 与 运算 或 运算和 非 运算 10 用开关串联电路实现 图1 5 1与逻辑运算 开关A B控制灯泡L 只有当A和B同时闭合时 灯泡才能点亮 1 与运算 A B 定义 某事件有若干个条件 只有当所有条件全部满足时 这件事才发生 L 11 逻辑表达式 L A AB 12 用开关并联电路实现 只要开关A和B中有一个闭合 或两个都闭合 灯泡就会亮 图1 5 2或逻辑运算 定义 某事件有若干个条件 只要其中一个或一个以上的条件得到满足 这件事就发生 2 或运算 L 13 图1 5 3非逻辑运算 下图表示一个简单的非逻辑电路 当继电器通电 灯泡熄灭 继电器不通电 灯泡点亮 定义 某一事件的产生取决于条件的否定 这种关系称为非逻辑 图1 5 3非逻辑运算 3 非运算 L 14 非逻辑符号 逻辑表达式 15 4 几种常用复合逻辑运算 1 与非运算 16 2 或非运算 17 3 异或逻辑 若两个输入变量的值相异 输出为1 否则为0 18 4 同或运算 若两个输入变量的值相同 输出为1 否则为0 同或逻辑表达式 19 20 三 逻辑函数及逻辑函数间的相等 逻辑函数与普通代数中的函数定义相似 若某一逻辑网络的输入逻辑变量为A1 A2 An 输出逻辑变量为F A1 A2 An的取值确定后 F的值也唯一地被确定下来 则称F是A1 A2 An的逻辑函数 记为 F f A1 A2 An 逻辑电路 A1 A2 An F 21 并且 逻辑函数与普通代数中的函数一样 也存在着相等问题 设有两个逻辑函数 F1 f1 A1 A2 An F2 f2 A1 A2 An 逻辑函数与普通代数相比 有以下两个特点 1 变量只能有 0 1 两种取值 2 各变量之间的运算关系只能是 与 或 和 非 三种基本逻辑运算 22 若对应于逻辑变量A1 A2 An的任何一组取值 F1和F2的值都相等 则称函数F1与F2相等 判断两个逻辑函数是否相等 可用真值表进行比较 也可用逻辑代数的公理 定理和规则进行证明 23 四 逻辑函数的表示法 真值表 表格法 逻辑表达式 公式法 卡诺图逻辑图波形图 常用的表示法有 图形法 24 1 真值表 是由逻辑变量的所有可能取值组合及其对应的逻辑函数值所构成的表格 由于一个逻辑变量只能有 0 和 1 两种取值 故n个逻辑变量一共有2n个取值组合 25 如 F AB AC的真值表为 26 例 右下图所示为一个控制楼梯照明灯的电路 单刀双掷开关A装在楼下 B装在楼上 楼道灯开关示意图 解 逻辑抽象 列出真值表 27 2 逻辑表达式 是由逻辑变量和 与 或 非 三种运算符构成的式子 例如 F f A B 28 书写逻辑表达式时 可按下述规则省略某些括号或运算符号 1 进行 非 运算时 可不加括号 如 等 2 与 运算符一般省略 3 若在一个式中 既有 与 又有 或 运算 则按先 与 后 或 规则去括号 4 与 或 运算均满足结合律 故 A B C可用A B C代替 AB C可用ABC代替 29 3 卡诺图 是由逻辑变量的所有可能取值组合对应的小方格按一定规律构成的平面图 该法在函数化简中十分有用 以上三种逻辑函数的表示法各有其特点 适用于不同的场合 它们之间也存在着内在的联系 故可以方便地相互变换 30 用与 或 非等逻辑符号表示逻辑函数中各变量之间的逻辑关系所得到的图形称为逻辑图 4 逻辑图 将逻辑函数式中所有的与 或 非运算符号用相应的逻辑符号代替 并按照逻辑运算的先后次序将这些逻辑符号连接起来 就得到图电路所对应的逻辑图 31 5 波形图 用输入端在不同逻辑信号作用下所对应的输出信号的波形图 表示电路的逻辑关系 32 1 基本公式 2 1 2逻辑代数的基本定律和恒等式 33 吸收律 摩根定理 34 2 基本公式的证明 列出等式左 右两边函数的真值表 真值表证明法 35 2 1 3逻辑代数的基本规则 代入规则 在包含逻辑变量A的逻辑等式中 如果用另一个函数式代入式中所有A的位置 则等式仍然成立 这一规则称为代入规则 例 B A C BA BC 用A D代替A 得 B A D C B A D BC BA BD BC 代入规则可以扩展所有基本公式或定律的应用范围 36 对于任意一个逻辑表达式L 若将其中所有的与 换成或 或 换成与 原变量换为反变量 反变量换为原变量 将1换成0 0换成1 则得到的结果就是原函数的反函数 2 反演规则 解 按照反演规则 得 37 对于任何逻辑函数式 若将其中的与 换成或 或 换成与 并将1换成0 0换成1 那么 所得的新的函数式就是L的对偶式 记作 例 逻辑函数的对偶式为 3 对偶规则 当某个逻辑恒等式成立时 则该恒等式两侧的对偶式也相等 这就是对偶规则 利用对偶规则 可从已知公式中得到更多的运算公式 38 一 逻辑表达式的基本形式 同一逻辑函数可用不同形式的逻辑函数表达式来描述 而逻辑函数表达式的基本形式有 积之和 表达式 与 或 表达式 和之积 表达式 或 与 表达式 2 1 4逻辑函数表达式的形式与变换 39 积之和 是指一个表达式中包含着若干个 积 项 且每个 积 项中可有一个或多个以原变量或反变量形式出现的字母 所有这些 积 项的 和 就表示一个函数 例 F 也可将上式看成是三个 与 项进行 或 运算形成的 故又称该式为 与 或 表达式 40 例 F 上式也可看作是三个 或 项进行 与 运算形成的 故又称该式为 或 与 表达式 当然 逻辑函数也可能以其他形式出现 如 F 但可以转化为上面的两种基本形式 和之积 表达式是指一个表达式中包含若干个 和 项 每个 和 项中有任意个以原变量或反变量形式出现的字母 所有这些 和 项的 积 表示一个函数 注 每个和项中的变量只能是一个字母 41 2个变量的逻辑函数f A B 最多有4个最小项 3个变量的逻辑函数f A B C 最多有8个最小项 n个变量的逻辑函数f最多有2n个最小项 定义 最小项是一种特殊的乘积项 设有一个n变量的逻辑函数 在n个变量组成的乘积项 与 项 中 每个变量以原变量或反变量的形式出现一次 且仅出现一次 则该乘积项称为n个变量的最小项 1 最小项 最小项是个 与 项 二 逻辑函数表达式的标准形式 为书写方便 常用mi表示最小项 而确定下标i的规则是 当变量按序排列后 令 与 项中的所有原变量用1表示 反变量用0表示 由此得到一个1 0序列组成的二进制数 该二进制数对应的十进制数即为下标i的值 42 例 由A B C三个变量组成的八个最小项可分别用m0 m7表示 000001 110111m0m1 m6m7 43 基本性质 1 对于任一个最小项 只有一组变量取值可使其值为1 2 任意两个最小项mi和mj i j 之积恒等于0 即 mi mj 0 i j 3 n个变量的所有2n个最小项之和恒等于1 即 4 n个变量的最小项有n个相邻最小项 当两项中只有一个变量不同时 且该变量互为反变量时 称这两项为相邻项 显然 n个变量的任何最小项 只要依次将它的每个变量取反一次 便可得到n个相邻最小项 如三变量最小项ABC 其相邻最小项为 这一性质将在后面介绍的卡诺图化简中用到 44 以上这些性质可通过分析一个2变量最小项真值表来进行说明 二变量最小项真值表 45 由表可见 每个最小项的列中只有一个1 且该1出现在变量取值组合对应的十进制数与最小项mi的下标i取值相同的那一行 每一组变量取值对应的行中只有一个1 而该1出现在最小项下标i的值与变量取值组合对应的十进制数相同的那一列 n个变量的任何一种取值组合 都不可能使mi与mj的值都为1 因此 mi mj 0 i j 46 2 最大项 是一个 或 项 定义 若一个具有n个变量的函数的 或 项包含全部n个变量 每个变量都以原变量或反变量形式出现且仅出现一次 则这个 或 项被称为最大项 即 最大项是一个特殊的 或 和 项 47 2个变量的逻辑函数f A B 的最大项最多只有4个 即 n个变量的逻辑函数 最多只有2n个最大项 为方便 常用Mi表示最大项 而Mi的下标i的确定与mi的下标确定相反 即 将 或 项中的原变量用0表示 反变量用1表示 这些0 1按变量排列顺序组成一个二进制数 其对应的十进制数就是最大项下标i的值 48 如 2变量A B构成的四个最大项可分别用M0 M3表示 00011011M0M1M2M3 49 性质 1 对于任意的一个最大项 只有一组变量取值可使其值为0 2 任意两个最大项Mi和Mj i j 之和恒等于1 即 Mi Mj 1 i j 3 n变量的所有2n个最大项之积恒等于 0 即 4 n个变量的最大项有n个相邻最大项 50 以上性质也可举例来加以说明 二变量最大项真值表 51 3 最小项与最大项之间的关系 从上述讨论中可以发现 同一问题中 下标相同的最小项和最大项互为反函数 即 mi 或Mi 也即 相同变量的最小项mi与最大项Mi是互补的 52 4 逻辑函数的标准形式 范式 标准积之和 最小项之和 or 标准 与 或 表达式 标准和之积 最大项之积 or 标准 或 与 表达式 53 由最小项相 或 构成的逻辑表达式 称为标准 与 或 表达式 也称最小项之和 或最小项表达式 如 F A B C 简写为F A B C m2 m4 m7 m 2 4 7 54 由最大项相 与 构成的表达式为标准 或 与 表达式 又称最大项之积表达式或最大项表达式 如 F A B C 可简写为 F A B C M1 M3 M6 M 1 3 6 55 三 逻辑函数表达式的转换 逻辑函数表达式虽然形式多样 但各表达式是可以转换的 且任一逻辑函数 不论其为何种形式 总可以转换为 最小项之和 及 最大项之积 的形式 即标准形式 求一个函数表达式的标准形式有 代数转换法真值表转换法 56 1 代数转换法 利用逻辑代数的基本定律和规则进行逻辑变换 从而得到另一种形式 若要用此法求一函数的 最小项之和 则 1 将函数表达式变换成一般 与 或 式 2 反复使用 互补律 将表达式中所有非最小项的 与 项扩展成最小项 57 例 F A B C 解 1 先将F变换成 与 或 式 F A B C 58 2 再将 与 或 式中的 与 项扩展成最小项 即 若某 与 项缺变量y 则用 乘 该项 并将其拆开成两项 F A B C 用重叠定理得 简写为 F A B C m0 m1 m3 m6 m7 m 0 1 3 6 7 59 类似地 若求 最大项之积 形式的步骤为 1 将表达式转换成一般 或 与 表达式 2 反复利用 将式中的非最大项的 或 项扩展为最大项 60 2 真值表转换法 因为一个逻辑函数的真值表与它的最小项表达式具有一一对应的关系 故可通过列出函数真值表 再据真值表写出最小项表达式 即 假定在函数F的真值表中有K组变量取值使F值为1 其它变量取值下F 0 则函数F的最小项表达式由使F值为1的这K组变量取值对应的K个最小项组成 61 解 先列出真值表 F A B C m 2 4 5 6 例 将F A B C AB BC表示成 最小项之和 形式 62 根据上表可直接写出最小项表达式为 F A B C m 2 4 5 6 同样 一个逻辑函数的真值表与其最大项表达式也具有一一对应的关系 假定在函数F的真值表中有K组变量取值使F为0 其它变量取值下F值为1 则函数F的最大项表达式由使F为0这K组变量取值对应的K个最大项组成 63 F A B C M 0 2 5 6 7 解 先列出真值表 例 求F A B C AC ABC表示为 最大项之积 形式 64 结论 因为函数的真值表与函数的两种标准表达式存在一一对应的关系 而任何一个逻辑函数的真值表是唯一的 所以 任何一个逻辑函数的两种标准形式也是唯一的 65 2 2逻辑函数的简化 2 2 2卡诺图化简法 2 2 1代数化简法 2 2 3含无关项的逻辑函数及其化简 66 在数字系统中 实现某一逻辑功能的逻辑电路的复杂性与描述该功能的逻辑表达式的复杂性直接相关 一般地 函数表达式越简单 据其设计出来的相应逻辑电路就越简单 而从逻辑问题概括出来的逻辑函数往往不是最简的 故必须对其进行简化 这样 可降低系统成本 减少复杂度 从而提高可靠性 将逻辑函数简化成最简形式称为逻辑函数的最小化 一般 与 或 表达式和 或 与 表达式是最基本的形式 说其为最基本的形式是因为通过它们可方便地转换成任何其它所要求的形式 67 因此 我们讨论函数的化简问题 主要从这两种基本形式出发 并将重点放在 与 或 表达式的化简上 有两种方法 代数化简法卡诺图化简法 运用逻辑代数的基本定律和恒等式进行化简的方法 2 2 1代数化简法 公式法 68 1 与 或 表达式的化简 1 表达式中的 与 项个数最少 2 在满足上个条件的前提下 使每个 与 项中变量个数最少 满足以上两个条件意味着相应的逻辑电路中所需门的数量及门的输入端个数均为最少 而使电路最经济 69 吸收法 A AB A 消去法 配项法 并项法 70 例2 1 8已知逻辑函数表达式为 1 最简的与 或逻辑函数表达式 并画出相应的逻辑图 2 仅用与非门画出最简表达式的逻辑图 要求 解 71 解 72 2 或 与 表达式的化简 同 与 或 表达式类似 最简 或 与 表达式也应满足下列两个条件 1 表达式中的 或 项个数最少 2 在条件 1 前提下 每个 或 项的变量个数最少 a 可直接运用公理 定理中的 或 与 形式等进行化简 b 也可采用两次对偶法 即 先对 或 与 形式的函数F求对偶F F 为 与 或 表达式 按 与 或 表达式的化简法求出F 的最简式 再对F 求对偶 即可得到F的最简 或 与 表达式 73 例 化简F 解 F 用消元法 F F 74 1 逻辑代数与普通代数的公式易混淆 化简过程要求对所有公式熟练掌握 2 代数法化简无一套完善的方法可循 它依赖于人的经验和灵活性 3 用这种化简方法技巧强 较难掌握 特别是对代数化简后得到的逻辑表达式是否是最简式判断有一定困难 因此 该方法有较大的局限性 结论 75 1 卡诺图的构成 n个变量的卡诺图有2n个小方格 每个小方格对应于一个最小项 且小方格的标号即为最小项的标号 所有的最小项巧妙地排列成一种能清楚地反映它们的相邻关系的方格阵列 由于任何逻辑函数均可表示成 最小项之和 的形式 因此 一个逻辑函数就可由图形中若干个方格构成的区域来表示 这些方格必须与包含在函数中的各个最小项相对应 2 2 2卡诺图化简法 图解法 76 如 二变量卡诺图 是由4个方格构成的 每个方格表示一个最小项 见下图 a 所示 而图 b 则表明了各个方格与这两个变量间的关系 a b 77 三变量卡诺图 是由23 8个小方格构成的 各最小项的位置可通过卡诺图的每一列和每一行上写着的数字来说明 如 代表m2的方格对应于01列与0行 表示010 其对应的十进制数2即为最小项的下标 00 01 11 10 0 1 78 同样 四变量卡诺图是由24 16个小方格构成的 79 当变量多于4个时 因为方格的数量太多 卡诺图就较复杂 一般将其分开来写 即看作为若干个四变量的卡诺图组成 如五变量的卡诺图可由两个四变量卡诺图构成 而六变量的卡诺图则由四个四变量卡诺图构成 80 五变量卡诺图 81 注 为了表示上的方便 在上面两个卡诺图中的方格内只注明了最小项的下标 六变量卡诺图 B 82 卡诺图上变量的排列是有一定规律的 即 使最小项的相邻关系能在图形上清晰地反映出来 具体地说是 在n个变量的卡诺图中 能从图形上直观 方便地找到每个最小项的n个相邻最小项 任何两个逻辑上相邻的最小项 在卡诺图中的几何位置上也是相邻的 所谓逻辑上相邻的最小项是指这样两个 与 项 若它们都包含n个变量 且这n个变量中仅有一个变量是不同的 则称该两个 与 项是相邻的 83 而几何位置上的相邻则包含以下几种 几何相邻 与该最小项方格共边的若干个小方格 相对相邻 同一列的两端和同一行的两端 重叠相邻 变量多于四个时 有多个四变量卡诺图 每个四变量的卡诺图与另一四变量的卡诺图重叠时 上下重叠或左右重叠 的最小项称为重叠相邻的最小项 84 例 四变量卡诺图中 m5的4个相邻最小项分别为 m1 m4 m7和m13 均为几何相邻 m0为4个相邻最小项为m1和m4 几何相邻 m2和m8 相对相邻 85 五变量卡诺图中 m3的5个相邻最小项为 m1 m2和m7 几何相邻 m11 相对相邻 m19 重叠相邻 六变量卡诺图中 m31的六个相邻最小项为 m23 m27 m29 m30 几何相邻 m15和m63 重叠相邻 86 结论 卡诺图在构造上的两个特点为 1 n个变量的卡诺图由2n个小方格组成 每个小方格代表一个最小项 2 卡诺图上处在相邻 相对 相重位置上的小方格所代表的最小项为相邻最小项 87 2 卡诺图上最小项的合并规律 根据定理和相邻最小项的定义可知 两个相邻最小项可以合并为一项并消去一个变量 由此逻辑依据和卡诺图的特征结合起来 通过对卡诺图上的相邻小方格进行合并 可以得到一个简单的 与 项 而用来将能合并的小方格包围起来的圈 称为卡诺圈 88 卡诺图相邻的小方格合并原则是 1 卡诺图合并小方格时 总是按2的乘幂将2m个小方格圈起来 该圈称为卡诺圈 并消去m个变量 2 卡诺图中的卡诺圈尽可能多的将相邻小方格圈在一起 圈的个数也应最少 这样 使消去的变量最多 与 项的个数也最少 3 卡诺图中的小方格在合并时 可根据需要被圈过多次 但至少得被一个卡诺圈圈过 4 当卡诺圈包围了整个卡诺图时 可用1表示 即 个变量的全部最小项之和为1 89 例 三 四变量卡诺图中 两个小方格连在一起或处于某行 列 的两端时可合并 且消去一个变量 四个小方格组成一个大方格 或组成一行 列 或处于相邻两行 列 的两端 或处于四个角则可合并 且可消去两个变量 八个小方格组成相邻的两行 列 或组成两个边行 列 时 可合并成一项 且可消去三个变量 90 三变量卡诺图 91 两个最小项合并的几种情况 四变量卡诺图 92 93 四个最小项的合并的几种情况 94 八个最小项的合并的几种情况 95 3 逻辑函数在卡诺图上的表示 1 若逻辑函数表达式是最小项之和 则只要在卡诺图上找到与此最小项对应的小方格 并将其标为1 其余小方格标以0即可 并将前者称为1方格而后者称为0方格 96 例 F A B m1 m2 m3则其卡诺图为 为了简便 常将卡诺图中的0省略不填 F 97 例 F A B C 解 先找出三变量卡诺图中AC对应的方格 即 001和011 再找出AB对应的方格010和011 直至表达式中的 与 项全表示出来 并在对应的小方格中标以1 则可得到所求 见下图所示 2 若逻辑函数是 与 或 表达式 则需将各 与 项分别表示在卡诺图上 然后叠加起来 F 98 4 用卡诺图化简逻辑函数 用卡诺图化简可非常方便地求出逻辑函数的最简 与 或 式和最简 或 与 式 a 原式为 与 或 式b 原式为 或 与 式 99 1 用卡诺图化简求最简 与 或 式 原式为 与 或 式 将函数用卡诺图表示 按卡诺图中相邻小方格合并的原则 将填1的相邻小方格圈起来 即画卡诺圈 将卡诺图上所有卡诺圈对应的 与 项相 或 100 例 化简函数F A B C D 解 先作卡诺图 再画卡诺圈 由卡诺图上的卡诺圈得 F A B C D 注 化简得到的 与 或 式并不唯一 F 101 b 原式为 或 与 式 先求 并将用卡诺图表示 将填0的相邻小方格画卡诺圈 将所有卡诺圈对应的 与 项相 或 则得F的最简 与 或 式 102 2 用卡诺图化简求最简 或 与 表达式 a 原式为 与 或 式b 原式为 或 与 式 103 由于卡诺图上的1方格对应原函数F 而0方格对应的最小项组成反函数 故 只需合并卡诺图上的0方格便得的最简 与 或 式 然后再对表达式求反 即可得原函数F的最简 或 与 式 当要求F的最简 或 与 式时 可先求的最简 与 或 式 然后再对取反得到F的最简 或