第二章 逻辑代数基础.ppt

第二章逻辑代数基础 第二章逻辑代数基础 教学要求 1 理解逻辑代数的基本概念 2 掌握逻辑代数的运算 3 掌握逻辑函数的表达 4 熟练掌握卡诺图对逻辑函数的化简 第二章逻辑代数基础 教学要求 第一节逻辑代数基本概念 第二节逻辑代数 第四节硬件描述语言基础 第三节逻辑函数的卡诺图化简法 第二章逻辑代数基础 目录 第一节逻辑代数基本概念 2 1 1逻辑常量和逻辑变量 常量 变量 逻辑变量 原变量A B Z反变量 只有0 1两种取值 常常不是数 反映状态 例如 电位高低 开关断合脉冲有无等 2 1 2基本逻辑和复合逻辑 真值表 符号 图例 条件A无效 则Y有效 A或者B有效 则Y有效 条件A B同时有效 则Y有效 意义 Y Y A B Y AB 表达式 备注 非 或 与 基本逻辑 图1 图2 图3 表2 表1 表3 与 符号 非 符号 或 符号 基本逻辑 逻辑运算 1 与运算 逻辑乘 or 1 概念 只有当决定某一事件的条件全部具备时 这一事件才会发生 这种因果关系称为与逻辑 2 真值表用 0 1 分别表示不同状态而列出的输入与输出关系的表格 A 0 断 1 合B 0 断 1 合Y 0 灭 1 亮 3 逻辑函数表达式Y A B AB A B 4 运算规则0 0 0 0 1 0 1 0 0 1 1 1 一般地 A 0 0 A 1 A A A A 5 逻辑符号GB旧GB美国 2 或运算 逻辑加 or 1 概念在决定某一事件的各种条件中 只要有一个或一个以上条件得到满足 这一事件就会发生 这种因果关系称或逻辑 2 真值表 3 表达式Y A B A B 4 运算规则0 0 0 0 1 1 1 0 1 1 1 1 一般地 A 0 A A 1 1 A A A 5 逻辑符号GB旧GB美国 3 非运算 逻辑非 1 概念事件发生的条件具备时 事件不会发生 条件不具备时 事件发生 这种因果关系称为逻辑非 2 真值表 3 表达式Y 4 运算规则一般地 5 逻辑符号GB旧GB美国 复合逻辑 Y A B 表4 表5 表6 表7 表8 符号4 符号5 符号6 符号7 符号8 复合逻辑运算 1 与非运算 2 或非运算 3 与或非运算 4 异或和同或运算 Y A B 运算优先顺序 括号 非 与 或 如果一个逻辑变量Z由其他一个或多个逻辑变量 如 A B C 的取值所决定 当A B C 确定后 Z也就唯一的确定了 则把Z称为A B C 的逻辑函数 表示为Z F A B C 2 1 3逻辑函数的表示方法 Y AB 在数字电路中 逻辑函数的表示方法有五种 真值表 函数表达式 卡诺图 逻辑图 波形图 逻辑函数表达式的书写 最小项法由真值表推导函数表达式的方法有 最大项法 2 1 4逻辑函数的相等 假设F A1 A2 An 为变量A1 A2 An的逻辑函数 G A1 A2 An 为变量A1 A2 An的另一逻辑函数 如果对应于A1 A2 An的任意一组状态组合 F和G的值都相同 则称F和G是相等的 记作F G 亦即 真值表相同的逻辑函数相等 例 设F A B C A B C G A B C AB AC 证明 F G 形式不同功能相同 2 2逻辑代数的运算法则 2 2 1逻辑代数的基本公式一 常用公式 1 1 00 1 2 1 1 10 0 0 3 1 0 0 1 00 1 1 0 1 4 0 0 01 1 1 5 A 0 则A 1A 1 则A 0 6 重叠 同一 律A A AA A A 7 反演律 德 摩根定理 A B A BA B A B 8 还原律A A 二 基本定律 1 交换律AB BAA B B A 2 结合律A BC AB CA B C A B C 3 分配律A B C AB ACA BC A B A C 4 01律1 A A0 A A0 A 01 A 1 5 互补律A A 0A A 1 2 2 2三个规则 定理 1 代入规则在任何逻辑等式中 如果等式两边所有出现某一变量的地方都代之以一个函数 则等式仍然成立 e g 已知A B A B 以Z AC代A 则有 A C B A C B A B C 扩大了公式的应用范围 2 反演规则 互补规则 3变2不变 对于任意一个逻辑表达式Y 如果Y中所有的 换成 换成 0 换成 1 1 换成 0 原变量换成反变量 反变量换成原变量 则得到的表达式就是Y的反函数Y 3变 换成 换成 0 换成 1 1 换成 0 原变量换成反变量 反变量换成原变量 2不变 大非号不变 包含两个或者两个以上的变量的非号 运算的顺序不变 例 已知Y A B C D 求YY A B C D Y A B C D E则Y A B C D E Y A B C D 0则Y A B C D 1注意 1 优先顺序 先括号内 后括号外 先乘后加 2 包含两个变量或以上的非号在变换中不变 3 对偶规则 2变2不变 对于任意一个逻辑表达式Y 如果Y中所有的 换成 换成 0 换成 1 1 换成 0 则得到一新的表达式Y 或Y Y 称为Y的对偶式 例 Y A B C Y A B CY A B CY A B C Y A B CY ABC练习 Y ABCY A B C注意 优先顺序和大非号 一般地 Y Y推论 若F A B C G A B C 则F G 2变 换成 换成 0 换成 1 1 换成 0 2不变 大非号不变 包含两个或者两个以上的变量的非号 运算的顺序不变 对偶变化规则 2 2 3常用公式 1 A AB A 消乘积项 A A B A证 A AB A 1 B A 有一个乘积项的部分因子是另一个乘积项的全部 则该乘积项是多余的 2 AB AB A 合并公式 A B A B A证 AB AB A B B A 1 A 乘积项有公有因子 不同的因子互补 则合并为由公有因子组成的乘积项 3 A AB A B消反公式 A A B AB证 A AB A A A B 1 A B A B 分配律 A BC A B A C 证2 A AB A AB AB A B 一个乘积项的部分因子恰好是另一个乘积项的补 则该乘积项的这部分因子是多余的 4 AB AC BC AB AC A B A C B C A B A C 证 左 消第三项的公式 AB AC BC A A AB AC ABC ABC AB 1 C AC 1 B 右推论 AB AC BCDE AB AC 两个乘积项部分的因子互补 其余的因子都是第三项的因子 则第三项是多余的 2 2 4异或运算的公式 1 交换律A B B A 2 结合律 A B C A B C 3 分配律A B C AB AC证 A B C A BC BC ABC ABCAB AC ABAC ABAC A B AC AB A C ABC ABC 4 常量与变量之间的异或运算 由定义直接推出 A 1 AA 0 AA A 0A A 1 5 因果互换若A B C 则 A C B B C A证 把A B C两边同时异或A A B A C A则 0 B A C A C B 同理可证B C A 6 多变量异或运算在多变量异或运算中 若 1 的个数为奇数 则结果为 1 若 1 的个数为偶数 则结果为 0 与变量为 0 的个数无关 2 2 5逻辑函数的表达式 一 逻辑函数常用表达式逻辑函数的常用表达式包括与或式 与非与非式 或与式 或非或非式和或非式 1 与或式F AB CD2 与非与非式 3 或与式F A B C D 4 或非或非式5 与或非式 2 2 6逻辑函数的公式化简法 一 化简的意义和方法1 意义 设备简单 成本低 2 方法 1 公式法 适于任意多个变量的函数的化简 没有统一的步骤 靠灵活熟练 难于判定是否最简 2 卡诺图法 图解法 适于6个以下变量的函数简化 直观 简单 3 系统化简法 Q M 适于任意多变量的函数的简化 繁琐 但有一定规律可循 适于计算机辅助 3 最简与或式的含义常用五种类型表达式 以Y AB AC 与或表达式与门和或门或与表达式或门和与门与或式对偶 展开 对偶与非与非式与非门与或式两次取反或非或非式或非门与或式 或与式 两次取反与或非式与或非门或非或非式 反演律 对于不同类型的表达式 最简的标准不同 最简与或式 1 乘积项最少 门数少 2 每一个乘积项中的因子最少 输入端数少 针对中小规模门电路 CPLD 与或阵列结构 输入端数不是主要问题 FPGA 常用四输入数据选择器结构 以与或式为例 任何F可化为与或式 最简与或式可变换为任何其它形式 二 公式化简法 代数法 公式化简常用的5个公式 分配律 A BC A B A C 反演律 常用公式3 A AB A B常用公式4 AB AC BC AB AC推论 1 常用方法 1 合并项法 并项法 二合一e g 2 吸收法消去多余项e g 3 消去法 消因子法 消去多余因子e g 4 配项法一拆二 增加BCe g 另 2 举例e g 1 合并和吸收 吸收 消去 e g 2 吸收 消去 合并 吸收 e g 3 配项 试探性 e g 4e g 5 用对偶公式直接化简 不熟练 先展开后化简 繁琐 2 3卡诺图化简 1 最小项和标准与或表达式 1 最小项定义对于n个变量 若m为包含n个因子的乘积项 在m中每一个变量都以原变量或者反变量的形式作为一个因子出现且仅出现一次 则称m为该组变量的一个最小项 n个变量一共有2n个最小项 2 3 1逻辑函数的两种标准形式 逻辑函数的表达式不是唯一的 2 最小项的性质a 只有一组变量取值组合使其值为 1 等于 1 的机会最小 b 任意两个最小项之积恒为 0 c 全体最小项之和恒为 1 3 最小项的编号把使最小项为 1 的那一组变量取值组合当成二进制数 与其对应的十进制数即为该最小项的编号 m0 m1 m2 对于三个变量A B C 有 4 标准与或表达式 最小项表达式 标准积之和 全部由最小项相加构成的函数与或表达式 任何逻辑函数都可以表示成标准与或表达式 且是唯一的 可由真值表得出 或由表达式变换得到 e g 1 e g 2 2 最大项和标准或与表达式 1 最大项定义对于n个变量 若M为n个变量之和 在M中每一个变量都以原变量或者反变量的形式作为一项出现且仅出现一次 则称M为该组变量的一个最大项 n个变量一共有2n个最大项对于三个变量A B C 有 2 最大项的性质a 只有一组变量取值组合使其值为 0 等于 1 的机会最大 b 任意两个最大项之和恒为 1 c 全体最大项之积恒为 0 3 最大项的编号把使最大项为 0 的那一组变量取值组合当成二进制数 与其对应的十进制数即为该最大项的编号 M0 M1 M2 4 标准或与表达式 最大项表达式 全部由最大项相乘构成的函数或与表达式 任何逻辑函数都可以表示成标准或与表达式 且是唯一的 e g 最小项法 输出为1的输入组合写成乘积项的形式 其中取值为1的输入用原变量表示 取值为0的输入用反变量表示 然后把这些乘积项相加即可 最大项法 输出为0的输入组合写成和项的形式 其中取值为0的输入用原变量表示 取值为1的输入用反变量表示 然后把这些和项相乘即可 真值表与表达式楼梯路灯控制问题 开关 A B 上 1 下 0 灯 Y 亮 1 灭 0 或 例题 三人表决器 用A B C代表三个人 用1表示同意用0表示反对用F表示最后表决结果 用1表示通过用0表示否决遵守 少数服从多数 的原则 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 F C B A 写真值表 用最小项写表达式输出为1的输入组合项 011 101 110 111输入为1的用原变量表示 输入为0的用反变量表示 则有 ABC ABC ABC ABC 所以 F ABC ABC ABC ABC 逻辑图 以最小项表达式为例 F ABC ABC ABC ABC 画逻辑图时 应遵守 先括号 然后乘 最后加 的运算优先次序 波形图 用最大项写表达式输出为0的输入组合项 000 001 010 100输入为0的用原变量表示 输入为1的用反变量表示 则有 A B C A B C A B C A B C 所以 F A B C A B C A B C A B C 例 设计一个奇较验电路 假设输入端有4位代码 要求输入用A B C D表示 输出用F表示 输入端的取值选择只有0 1两种 输出端用 0 表示输入有偶数个1 用 1 表示输入有奇数个1 函数表达式 最小项表达式 最大项表达式 练习 设计一位全加器 要求写出真值表 最小项表达式 最大项表达式 并将S的最小项表达式化简 最小项表达式 最大项表达式 2 3逻辑函数的卡诺图化简法一 卡诺图由真值表按一定规则画出的方格图 变量取值 两两相邻 首尾相邻 按循环码排列 特点 1 几何相邻 逻辑相邻 便于化简 2 对于变量数n 5的逻辑函数 复杂少用 二 用卡诺图表示逻辑函数 1 给出真值表 在对应变量取值组合的每一个小方格中 函数值为 1 的填 1 为 0 填 0 8421码 循环码 e g 或 2 给出最小项表达式在对应于函数的每一个最小项的小方格中填 1 其它填 0 e g Y A B C D 0 3 5 6 9 10 12 15 0格可为空 3 给出非标准形式 1 配项 标准表达式 填图 繁琐 2 观察法e g 4 给出其它形式表达式 先变换 与或式 填图e g 三 卡诺图的性质和运算1 全 0 格对应Y 02 全 1 格对应Y 13 卡诺图相加 相乘 异或 对应格相加 相乘 异或 4 卡诺图反演 1 格 0 格 0 格 1 格四 用卡诺图合并最小项的规律2个相邻1格可合并成一个乘积项 消去1个有01变化的变量 保留无变化的变量 4个相邻1格可合并成一个乘积项 消去2个有01变化的变量 保留无变化的变量 8个相邻1格可合并成一个乘积项 消去3个有01变化的变量 保留无变化的变量 2i个相邻1格可合并成一个乘积项 消去i个有01变化的变量 保留无变化的变量 五 用卡诺图化简逻辑函数 1 简化原则 1 圈尽量大 变量数少 2 圈数尽量少 乘积项少 3 每一个 1 格都被圈到 没有 0 格被圈 4 全部是必要项 没有多余项 必要项 对应圈中至少有一个 1 格只被圈一次 有新 1 格多余项 对应圈中的每一个 1 格都被圈2次或2次以上 2 化简步骤 1 画卡诺图 2 按简化原则化简函数 先圈只有一种圈法的圈 3 检查是否全部 1 格被圈 没有 0 格被圈 4 写出相应的简化式 e g 1Y A B C D 0 2 5 6 7 9 10 14 15 解第一步 填写卡诺图 为了叙述方便 这里填写最小项的编号 平常应该在对应最小项方格中填1 第二步 画包围圈 第三步 化简包围圈 00 01 11 10 00 01 AB CD 11 10 Eg2 化简函数 卡诺图为 1 1 1 1 1 1 1 1 用三个圈覆盖 最简与或式为 1可重复使用 要圈两个1 1 1 1 1 1 1 1 卡诺图如右 圈黑圈 得 圈篮圈 得 Y A B C D m1 m5 m6 m7 m11 m12 m13 m15 1 1 1 1 1 1 1 1 显然 紫圈是多余的 避免画多余圈的方法 1 画完圈后注意检查 2 先圈只有一种方法可圈的1 2 3 当最简式不唯一时 画圈的方法也不唯一 4 1 1 1 1 5 6 F A B C D A B C D A B C D A B C D A D F为或与式 可先对F求对偶式F 画出F 的卡诺图 1 1 1 1 1 1 1 1 e g 3 e g 4Y A B C D 0 2 5 6 7 8 9 10 11 14 15 注 每一项都是必要项构成的函数表达式不一定最简 圈 1 与或式 或与式 反函数圈 1 与或式 再求非 或与式 直接圈 0 格 或与式 最大项概念 对于输入变量的每一组取值组合 逻辑函数都有确定的值 则这类逻辑函数称为完全描述的逻辑函数 对于输入变量的某些取值组合 逻辑函数值不确定 可以为1 也可以为0 这类逻辑函数称为非完全描述的逻辑函数 对应输出函数值没有确定值的最小项 最大值 称为无关项 任意项或约束项 函数值可以为1 也可以为0 记为 或 六 具有无关项的逻辑函数及其化简 无关项 在一个逻辑函数中 变量的某些取值组合不会出现 约束项 或者函数在变量的某些取值组合时 输出可以是 0 也可以时 1 任意项 有些教材不区分约束项和任意项 统称为任意项 约束项 随意项 含无关项的逻辑函数 非完全描述的逻辑函数 无关项的表示 d AB AC 0 d AB AC 无关项在化简时取 0 还是 1 依据对化简是否有利 一 无关项 无关项是约束项和任意项的总称 1 约束项 是最小项 若使该最小项的值为1的输入变量取值不允许输入 则称该最小项为约束项 例如 四舍五入函数 用A B C D组成的四位二进制数表示1位十进制数 当该数大于4时输出为1 真值表为 1010 1111六个值不允许输入 将m10 m15称为约束项 在真值表和卡诺图中都用表示 在函数式中约束项的表示方法 m10 m11 m12 m13 m14 m15 0 也可用求和符号表示上式 因此四舍五入函数可表示为 把这类逻辑函数称为有约束的逻辑函数 1 1 1 1 1 2 任意项 是最小项 若使其值为1的变量取值输入时 函数值可为0 也可为1 则称该最小项为任意项 任意项很少遇到 这里不作讨论 二 约束项在化简中的应用 约束项对应的函数值可为0 也可为1 原则是将函数化到最简 1 1 1 1 1 解填写卡诺图 画包围圈 化简 化简结果为 经比较 合理利用任意项 确实能使逻辑函数的表达式进一步化简 Eg6 化简Y A B C D m 1 4 9 13 d 5 6 7 10 画出卡诺图 标出多余项 1 1 1 1 七 多变量卡诺图的化简 0101101111 对应格相邻 e g 7Y A B C D E