逻辑代数基础.ppt

1 第二章逻辑代数基础 2 1概述 2 2逻辑代数中的三种基本运算 2 3逻辑代数的基本公式和常用公式 2 5逻辑函数及其表示方法 2 4逻辑代数的基本定理 2 6逻辑函数的化简方法 2 7具有无关项的逻辑函数及其化简 2 8用Multisim进行逻辑函数的化简与变换 2 内容提要 本章介绍分析和设计数字逻辑电路时使用的数学工具 重点内容有 1 逻辑代数的基本公式和常用公式 2 逻辑代数的基本定理 3 逻辑函数的各种表示方法及相互转换 4 逻辑函数的化简方法 5 约束项 任意项 无关项的概念以及无关项在化简逻辑函数中的应用 3 2 1概述 在二值逻辑中 逻辑代数中的逻辑变量取值只有两个 1 逻辑壹 0 逻辑零 0和1表示两个对立的逻辑状态 4 2 2逻辑代数中的三种基本运算 基本逻辑运算 与 and 或 or 非 not 一 与 逻辑 与逻辑 决定事件发生的各条件中 所有条件都具备 事件才会发生 成立 规定 开关合为逻辑 1 开关断为逻辑 0 灯亮为逻辑 1 灯灭为逻辑 0 5 逻辑符号 逻辑式 Y A B C 逻辑乘法 逻辑与 真值表 真值表特点 任0则0 全1则1 与逻辑运算规则 0 0 00 1 01 0 01 1 1 6 二 或 逻辑 或逻辑 决定事件发生的各条件中 有一个或一个以上的条件具备 事件就会发生 成立 规定 开关合为逻辑 1 开关断为逻辑 0 灯亮为逻辑 1 灯灭为逻辑 0 7 真值表 逻辑符号 逻辑式 Y A B C 逻辑加法 逻辑或 真值表特点 任1则1 全0则0 或逻辑运算规则 0 0 00 1 11 0 11 1 1 8 三 非 逻辑 非 逻辑 决定事件发生的条件只有一个 条件不具备时事件发生 成立 条件具备时事件不发生 规定 开关合为逻辑 1 开关断为逻辑 0 灯亮为逻辑 1 灯灭为逻辑 0 9 逻辑符号 逻辑非 逻辑反 真值表特点 1则0 0则1 逻辑式 运算规则 图2 2 2与 或 非的图形符号 11 图2 2 3复合逻辑的图形符号和运算符号 四 几种常用的复合逻辑运算 12 与非逻辑真值表 或非逻辑真值表 13 2 3逻辑代数的基本公式和常用公式 2 3 1基本公式 加运算规则 表中11 12 13 14 乘运算规则 表中1 2 3 4 非运算规则 表中9 10 一 基本定律 见表2 3 1 14 二 交换律 表中5 15 三 结合律 表中6 16 四 分配律 表中7 17 A B B A A B B A A B C A B C A C B A B C A B C A B C A B A C A B C A B A C 15 求证 分配律第2条 A BC A B A C 证明 右边 A B A C AA AB AC BC 分配律 A A B C BC 结合律 AA A A 1 B C BC 结合律 A 1 BC 1 B C 1 A BC A 1 A 左边 16 五 德 摩根定理 反演律 表中8 18 De Morgan 证明 真值表法 穷举法 推广到多变量 说明 两个 或两个以上 变量的与非 或非 运算等于两个 或两个以上 变量的非或 非与 运算 17 用真值表证明摩根定理成立 1110 1110 相等 18 吸收 多余 冗余 项 多余 冗余 因子被取消 去掉 被消化了 1 原变量的吸收 A AB A 证明 左式 A 1 B 原式成立 长中含短 留下短 长项 短项 A 右式 2 3 2若干常用公式 几种形式的吸收律 见表2 3 3 19 2 反变量的吸收 证明 右式 长中含反 去掉反 20 3 混合变量的吸收 证明 右式 正负相对 余全完 消冗余项 21 证明 22 2 4逻辑代数的基本定理 2 4 1代入定理 内容 在任何一个包含变量A的逻辑等式中 若以另外一个逻辑式代替式中所有的变量A 则等式仍然成立 例 用代入规则证明德 摩根定理也适用于多变量的情况 二变量的德 摩根定理为 23 以 B C 代入 1 式中B 以 B C 代入 2 式中B 则得到 注 代入定理还可以扩展其他基本定律的应用范围 24 2 4 2反演定理 内容 将函数式F中所有的 变量与常数均取反 1 遵循先括号 再乘法 后加法的运算顺序 2 不是一个变量上的反号不动 规则 用处 实现互补运算 求反运算 新表达式 显然 反函数 25 例1 与或式 注意括号 注意括号 26 例2 与或式 反号不动 反号不动 27 2 4 3对偶定理 将函数式F中所有的 对偶式 常量取反 新表达式 对偶式 对偶定理 当某个逻辑恒等式成立时 则其对偶式也成立 若 则 28 注 证明两个逻辑式相等时 也可以通过证明它们的对偶式相等来完成 29 2 5逻辑函数及其表示方法 事物之间的逻辑关系可以通过描述逻辑输入变量和输出变量的变化关系来确定 这是一种函数关系 称为逻辑函数 记为 Y f A B C 例如与逻辑式 Y A B就是一个两输入变量 一输出变量的逻辑函数 逻辑函数的输入和输出取值为0和1 2 5 1逻辑函数 30 四种表示方法 逻辑函数式 逻辑表示式 逻辑代数式 逻辑图 波形图 真值表 将逻辑函数输入变量取值的不同组合与所对应的输出变量值用列表的方式一一对应列出的表格 2 5 2逻辑函数的表示方法 31 逻辑问题 裁判电路 问题抽象 输入变量A B C分别代表主裁和两个副裁 同意为1 输出变量Y代表运动员成绩 有效为1 问题描述如下 举重比赛中有A B C三个裁判 A为主裁 B C为副裁 规定当主裁和至少一个副裁认定成绩有效时 则运动员成绩Y有效 否则无效 32 列真值表的方法 一般按二进制的顺序 输出与输入状态一一对应 列出所有可能的状态 一 真值表 33 二 逻辑函数式 由规定当主裁A和至少一个副裁B C认定成绩有效时 则运动员成绩Y有效 可知 Y A B C 对于较复杂的逻辑问题 往往很难直接写出逻辑函数式 可以通过真值表的帮助来获得逻辑函数式 34 把相应的逻辑关系用逻辑符号和连线表示出来 就构成了逻辑图 三 逻辑图 35 四 波形图 波形图 将逻辑函数输入变量每一种可能出现的取值与对应的输出值按时间顺序依次排列起来的图形 36 方法 找出所有使输出为1的输入组合 将每一种组合以1对应原变量 0对应反变量的方法变换为逻辑符号与的形式 将所有 的结果相加 或 得到的函数式就是Y 1 由真值表写函数式 五 各种表示方法间的相互转换 37 2 由函数式写真值表 将输入变量的各种组合一一代入函数式中计算输出变量值 全部完成后得到真值表 0 1 1 1 38 AB 1 A B 1 1 3 由逻辑图写逻辑函数式 Y 39 4 由函数式画逻辑图 已知逻辑函数为画出对应的逻辑图 40 2 5 3逻辑函数的两种标准形式 最小项是构成逻辑函数的基本单元 对应于输入变量的每一种组合 n变量的最小项有2n个 一 最小项和最大项 n变量的最小项m是n个因子的乘积 每个变量都以它的原变量或反变量的形式在乘积项m中出现 且仅出现一次 1 最小项 最小项和最大项是构成逻辑函数的基本单元 最小项与最大项是等价的两个概念 虽然从形式上看是互反的 但表达的内容是一致的 41 2变量最小项 42 三变量最小项 变量赋值为1时用原变量表示 变量赋值为0时用该变量的反变量来表示 可见输入变量的八种状态分别唯一地对应着八个最小项 43 最小项的性质1 在输入变量的任何取值下必有一个且仅有一个最小项的值为1 44 全体最小项之和为1 1 实际上性质2可由性质1推出 想一想 为什么 最小项的性质2 45 任意两个最小项的乘积为0 实际上 性质3也可以由性质1推得 为什么 最小项的性质3 46 具有逻辑相邻性的两个最小项之和可以消去一对因子而合并成一项 最小项的性质4 逻辑相邻 若两个最小项只有一个因子以原 反区别 其他因子均相同 则称这两个最小项具有逻辑相邻性 47 逻辑相邻的项可以合并且消去一对因子 48 最小项的编号 以三变量最小项为例 最小项通常用表示 下标i即最小项编号 用十进制表示 49 2 最大项 定义 n变量的最大项M为n个变量之和 而且这n个变量均以原变量或反变量的形式在M中出现且只出现一次 n变量有2n个最大项 50 2变量最大项 51 3变量最大项 A B C三个变量构成的最大项有 52 最大项的性质1 在输入变量的任何取值下必有一个且仅有一个最大项的值为0 53 全体最大项之积为0 实际上性质2可由性质1推出 想一想 为什么 最大项的性质2 54 最大项的性质3 任意两个最大项的和为1 实际上 性质3也可以由最大项定义或者性质1推得 55 最大项的性质4 相邻的两个最大项之积可以消去一对因子而合并成一项 相邻 两个最大项只有一个因子不同 称相邻 推论 n变量的最大项有n个相邻项 56 最大项与最小项的关系 57 根据最小项的特点 从真值表可直接用最小项写出逻辑函数式 例如 由左图所示三变量逻辑函数的真值表 可写出其逻辑函数式 验证 将八种输入状态代入该表示式 均满足真值表中所列出的对应的输出状态 二 逻辑函数的最小项之和形式 58 将下列函数表示为最小项之和的形式 59 三 逻辑函数的最大项之积形式 结论 任意逻辑函数可以表示为最大项之积的形式 和之积式 显然 由于最小项与最大项之间的对称关系 可以得到下面的结论 60 已知逻辑函数的真值表如下 写出F的最大项表达式 61 2 5 4逻辑函数形式的变换 与 或 与非 与非 或 与非 与非 与 或 与 或非 或非 与或非 62 2 6逻辑函数的化简方法 同一逻辑函数可以有多种不同的逻辑式 一般来讲 逻辑式越简单 它所表示的逻辑关系越明显 越有利于用最少的逻辑器件来实现这个函数 所以化简是必要的 63 最简的标准与实际应用中能够提供的逻辑器件有关系 要根据实际而定 常用的逻辑器件有与非门 或非门 与或非门 异或门 非门等 以使用的器件数目最少 成本最低为判断最简的标准 默认最简形式为最简与 或式 即用最少的与门和或门来实现函数 64 2 6 1公式化简法 最简与或式 乘积项的项数最少 每个乘积项中变量个数最少 例题 并项法 吸收消去 长中含短 留下短 长中含反 去掉反 最简与或式 65 合并项 长中含短 留下短 长中含反 去掉反 吸收消去 正负相对 余全完 最简与或式 DEF 冗余因子DEFG 冗余项 66 添冗余项 正负相对 余全完 消冗余项 长中含短 留下短 添冗余项 最简与或式 正负相对 余全完 67 添冗余项 最简与或式 正负相对 余全完 68 化简结果不唯一 经过化简得最简与或式 或者 项数 因子数对应相同 讨论 69 题1 课堂练习 用公式化简法化简下列逻辑函数式 70 题2 摩根定律 71 结论 异或门可以用4个与非门实现 题3 证明 摩根定律 展开 72 用4个与非门实现异或 73 2 6 2卡诺图化简法 图形化简法 一 逻辑函数的卡诺图表示法 1 卡诺图的构成 下面举例说明卡诺图的画法 并且将逻辑相邻的最小项放在相邻的几何位置上 所得到的阵列图就是n变量的卡诺图 将n个输入变量的全部最小项用小方块阵列图表示 卡诺图的思想源于两个逻辑相邻的最小项可以化简的性质 74 输入变量 二变量卡诺图 卡诺图的每一个方块 最小项 代表一种输入组合 并且把对应的输入组合注明在阵列图的上方和左方 一变量卡诺图 m0 m2 m1 75 输入变量 三变量卡诺图 注意 m2与m0逻辑相邻 m0 m3 m5 m1 76 四变量卡诺图 卡诺图的特点 具有循环邻接的特性 m5 m1 m4 m7 m13 77 5变量卡诺图 78 2 已知逻辑函数画卡诺图 方法 先将逻辑函数表示为最小项之和的形式 然后在卡诺图相应最小项位置填1 其它地方填0 79 2 已知逻辑函数画卡诺图 例1 画出以下逻辑函数的卡诺图 解 根据反演规则 上式化成 80 所以 L的卡诺图为 81 二 用卡诺图化简逻辑函数 原理 相邻的两个最小项可以化简消去一对因子 82 化简原则 如果两个最小项相邻 可以合并为一项并消去一对因子 如果四个最小项相邻 可以合并为一项并消去两对因子 如果八个最小项相邻 可以合并为一项并消去三对因子 如果2n个最小项相邻 可以合并为一项并消去n对因子 83 两个最小项相邻的情况 84 四个最小项相邻的情况 85 八个最小项相邻的情况 86 卡诺图法化简步骤 一 布阵 画法规则 二 填项 用卡诺图表示逻辑函数 三 勾圈化简 用卡诺图化简 一 布阵 画法规则 87 m0m1m3m2 m4m5m7m6 m8m9m11m10 m12m13m15m14 高位 低位 88 二 填项 用卡诺图表示逻辑函数 填F 1的项 1 最小项直接填入 2 刷项 填公因子所包含的项 按F 1的与或式填项 方法 89 例1 有重复 1 者 只填一个 1 90 1 1 有重复 1 者 只填一个 1 刷项 填公因子包含的项 例1 91 1111 1111 例1 92 F 1的项全部填完以后 填项结束 不填者自动为 0 例1 93 三 勾圈化简 1 尽量勾大 2i个格消i个变量 i n 3 每个圈至少有一个独立格 4 圈必须覆盖所有的 1 即不能遗漏取值为 1 的小方块 勾圈原则 最后 把各个圈的公因子相加 得到最简与或式 2 1 可以重复利用 94 A B D C 1111 1111 11 11 D 消取值不同的变量 合理重叠 1 可以重复使用 例1 95 也可以取F 0的项化简 96 1111 11 填项 97 1111 11 11 F 1的项全部填完以后 其它补零 98 冗余项 勾圈化简 99 例2 用公式化简法得到下式 问是否最简 若不是 请化简之 A BC 01 00011110 11 11 填项 100 例2 用公式化简法得到下式 问是否最简 若不是 请化简之 1 1 F 1的项全部填完以后 填项结束 0 0 101 勾圈化简 0 0 102 0 0 103 说明 化简结果不唯一 0 0 0 0 104 F4 A B C D m 0 1 2 5 6 7 8 10 11 12 13 15 F4 m0 m1 m2 m5 m6 m7 m8 m10 m11 m12 m13 m15 1 1 1 1 1 1 1 1 1 1 1 1 高位 低位 0 0 0 0 105 F4 A B C D m 0 1 2 5 6 7 8 10 11 12 13 15 每次勾圈时 应包含尽量多的独立格 0 0 0 0 106 0 0 0 0 107 每次勾圈时 应包含尽量多的独立格 以避免出现冗余项 化简结果不唯一 说明一 说明二 0 0 0 0 0 0 0 0 108 2 7具有无关项的逻辑函数及其化简 在分析某些具体的逻辑函数时 n个变量的2n种组合中有一些变量取值不会出现 或不允许出现 对输入变量取值所加的限制称为约束 这些取值所对应的最小项称为约束项 约束项的值恒等于0 在真值表和卡诺图中 用 或 表示无关项 在逻辑式中 用 d来表示无关项之和 另一种情况是输入变量的某些取值下函数是1还是0皆可 并不影响电路功能 这些变量取值下 其值为1的那些最小项称为任意项 约束项和任意项统称为无关项 2 7 1约束项 任意项和逻辑函数式中的无关项 109 六个约束项 m10 m11 m12 m13 m14 m15 110 例题 将下列具有无关项的逻辑函数化为最简与或式 2 7 2无关项在化简逻辑函数中的应用 111