重庆大学数电复试资料.ppt

第3章逻辑代数 3 1逻辑代数的基本定律 3 2逻辑运算的基本规则 3 3逻辑函数的代数法化简 3 4逻辑函数的卡诺图化简 3 5具有无关项的逻辑函数化简 3 1逻辑代数的基本定律 1 基本 复合逻辑运算和逻辑运算顺序 1 单个逻辑变量的非运算 如 2 逻辑与 3 异或 同或 4 逻辑或 6 使用括号 可改变运算顺序 5 表达式的非运算 如与或非中的表达式AB CD 逻辑表达式 逻辑常量及逻辑变量之间的逻辑运算式称为逻辑表达式 如果2个逻辑表达式恒等 则构成逻辑恒等式 逻辑代数的基本定理常用恒等式表达 2 逻辑代数基本定理 5 3 1 自等律 A 0 A A 1 A 2 0 1律 A 1 1 A 0 0 重叠律 A A A A A A 4 互补律 吸收律 A AB A A A B A 6 交换律 A B B A AB BA 7 结合律 A B C A B C AB C A BC 8 分配律 A B C AB AC A BC A B A C 9 反演律 10 非非律 证明方法 枚举法 按基本逻辑运算 与 或 非 的定义列出真值表进行逻辑运算 例3 1证明反演律 亦称为摩根定理 证明 将变量的各种取值组合分别代入等式的左边和右边进行计算 列出真值表 1 1 1 0 1 1 1 0 3 常用恒等式 1 吸收式1 A AB A A A B A 吸收式2 2 3 合并式 配项式1 4 5 6 证明常用恒等式的方法 用基本定理导出或枚举法 证明 例3 2证明合并式 证明 例3 2 1证明吸收式 注意1 由于逻辑代数中没有逻辑减法及逻辑除法 故初等代数中的移项规则 移加作减 移乘作除 这里不适用 注意2 定理和恒等式反映的是逻辑关系 不是数量之间的关系 例3 3证明配项式 证明 end 3 2逻辑运算的基本规则 1 代入规则 在任何一个逻辑等式中 用一个逻辑函数代替等式两边的某一逻辑变量后 新的等式仍然成立 这个规则称为代入规则 代入规则将逻辑代数的基本定理和常用恒等式推广到多变量的情况 解 得 2 反演规则 在任何一个逻辑函数Y中 同时进行下述3种变换 称为反演变换 后产生的新函数就是原函数Y的反函数 注意 不属于单个变量上的反号应该保留 并保持原表达式中变量间的运算顺序 添加括号 解 解 例3 5已知 求 例3 6已知Y A 0 1 求 1 所有的 换成 换成 3 所有的原变量换成反变量 反变量换成原变量 2 所有的 0 换成 1 1 换成 0 3 对偶规则 注意 必须保持原表达式中变量间的运算顺序 对偶式 在一个逻辑表达式Y中 同时进行下述变换后产生的新表达式称为原式Y的对偶式Y 1 所有的 换成 换成 2 所有的 0 换成 1 1 换成 0 例如 对偶规则使要证明和要记忆的公式减少了一半 表3 1 2和表3 1 4同一行的等式 互为对偶式 对偶规则 任意一个恒等式两边同时作对偶变换导出仍然成立的对偶恒等式 例如 A B C AB AC A BC A B A C end 3 3逻辑函数的代数法化简 1 最简的标准 逻辑函数的表达式可以等效变换为5种形式 例如 同一种类型的表达式中 形式有不同 但最简的形式是唯一的 1 乘积项的个数最少 最简与或表达式的标准 2 在满足 1 的条件下 每个乘积项中变量的个数最少 代数法化简 亦称为公式法化简 就是用逻辑代数的定理和恒等式 对逻辑函数进行化简 求最简与或表达式 2 代数法化简 1 并项法 利用 将两项合并为一项 并消去一个变量 例如 2 吸收法 利用A AB A 消去AB项 例如 3 消项法 利用 消去BC项 例如 4 消因法 利用 消去因子 例如 如果两项分别包含A和 而其余的因子相乘为第3项 则第3项是多余的 如果一项的反是另一项的因子 则此因子是多余的 5 配项法 1 利用 配项化简 代数法化简逻辑函数时 必须综合使用上述技巧 逻辑代数定理和恒等式 才能有效地化简逻辑函数 2 利用 配项化简 end 3 4逻辑函数的卡诺图化简 3 4 1逻辑函数的标准表达式 3 4 2逻辑函数的卡诺图 3 4 3逻辑函数的卡诺图化简 卡诺图法化简的理论基础 标准表达式 最小项和最大项 代数法可以化简任意的逻辑函数 但是否达到最简却较难判断 卡诺图法可以直观 简便地得到最简逻辑表达式 3 4 1逻辑函数标准表达式 1 标准与或式 每个乘积项都包含函数的全部变量的特殊与或式称为标准与或表达式 最小项 标准与或式中每一个乘积项都包含函数Y的全部变量 每个变量以原变量或反变量因子仅出现一次 最小项 标准式 标准与或式 标准或与式 把原变量用1替代 反变量用0替代 按一定的变量排列顺序构成的二进制数就是最小项的编号 通常转换为十进制数 最小项的编号方法 n个变量的逻辑函数有2n个最小项 常用mi或m i 表示 i是最小项的编号 101 2 5 10 记作m5或m 5 3变量的最小项2n 23 8 三变量全部最小项的真值表 Y A B C A BC 任意一个最小项 只有一组变量取值使其为1 其它组取值使其为0 为1的取值组合是最小项的编号 全部最小项之和恒为1 不同的两个最小项之积恒为0 最小项的性质 对于任意一个最小项 只有一组变量取值使其为1 其它组取值使其为0 为1的取值组合是最小项的编号 不同的两个最小项之积恒为0 即 全部最小项之和恒为1 即 逻辑相邻 仅有一个变量不同的2个最小项称为逻辑相邻最小项 简称相邻项 例如 3变量最小项ABC的相邻项是 和 两相邻最小项之和等于它们的相同变量之积 n个变量的最小项有n个相邻项 且两相邻最小项之和等于它们的相同变量之积 n变量表达式 反函数表达式 即任意反函数的标准与或式是函数值为0所对应的最小项之和 3变量表达式 最小项一般表达式 2 标准或与式 一般地 n个变量的逻辑函数有2n个最大项 例如 3变量的逻辑函数有23个最大项 每个和项都包含函数的全部变量 以原或反变量出现 的或与式称为标准或与表达式 这种包含函数的全部变量的和项叫做最大项 常用Mi或M i 表示 i是最大项的编号 最大项的编号方法 原变量用0替换 反变量用1替换 按一定变量排列顺序构成的2进制数就是最大项的编号 通常转换为十进制数 例如 101 2 5 10 记作M5或M 5 相同编号的最大项和最小项互补 即 最大项的性质 对于任意一个最大项 只有变量的一组取值使其为0 其他组取值使其为1 使最大项为1的取值组合的二进制数值是最大项的编号 全部最大项之积恒为0 即 n个变量的最大项有n个相邻项 且两相邻最大项之积等于它们的相同变量之和 两相邻最大项之积等于它们的相同变量之和 例如 例如 3变量最大项A B C的相邻项是 逻辑相邻 仅有一个变量不同的2个最大项称为逻辑相邻最大项 简称为相邻项 不同的两个最大项之和为1 即 最大项一般表达式 即任意逻辑函数的标准或与式是函数值为0所对应的最大项之积 3 实际问题的逻辑函数 例3 7一楼梯间照明电路如下图所示 双控开关A和B一个装在楼上 一个装在楼下 下楼时开灯 上楼后关灯 反之亦然 解 1 列真值表设灯亮Y 1 灯灭Y 0 A或B 1表示拨向1位 A或B 0表示2位 2 写最小项表达式 3 写最大项表达式 由实际逻辑问题导出逻辑函数的方法是 1 根据命题导出真值表 2 由真值表导出标准表达式 3 化简 2 标准或与式 最大项表达式 是函数值为0所对应的最大项之积 由真值表导出标准表达式的方法是 1 标准与或式 最小项表达式 是函数值为1所对应的最小项之和 end 3 4 2逻辑函数的卡诺图 1 卡诺图的形成 3变量卡诺图 4变量卡诺图 边相邻 具有公共边 对称相邻 2个最小项的几何相邻 循环码 每个格代表一个最小项 对称相邻 对称相邻 BC CD AB 几何相邻的最小项是逻辑相邻的 卡诺图就是用平面上相邻的方格表示函数的每一个最小项 几何上相邻的方格所代表的最小项在逻辑上也相邻 变量卡诺图 2 逻辑函数的卡诺图 首先将逻辑函数转换为最小项表达式 然后 在卡诺图上函数包含的最小项所对应的小方格填入 在其他小方格填入 也可 不填写 解 1 由逻辑表达式画卡诺图 1 1 1 1 方法一 转换为最小项表达式 例3 8用卡诺图表示逻辑函数 任何确定的逻辑函数都可以表示为唯一的标准与或式 因此 可以用卡诺图表示逻辑函数 方法二 由表达式直接填入 A BC 00011110 01 1111 1 A 2 由真值表画卡诺图 在卡诺图中 使逻辑函数值为 的最小项填入 使逻辑函数值为 的最小项填入 为了直观和简洁 通常 不填写 例已知逻辑函数Y的真值表 画出Y的卡诺图 解 a 直接填入卡诺图 1 1 1 1 b 写标准表达式 填入卡诺图 end 3 4 3逻辑函数的卡诺图化简 1 化简的依据 CD AB 例 相邻的2个方格合并 消去一个变量 相邻的4个方格合并 消去2个变量 相邻的8个方格合并 消去3个变量 推广到一般情况 两 两相邻的2n个方格合并 消去不同的n个变量 保留公共变量 因为2n个方格合并时 提出公共变量 公因子 后 恰是余下的n个变量的全部最小项之和 其值恒为1 公共变量是卡诺图上2n个最小项具有相同行列编码的变量之积 2 化简的步骤 1 画出逻辑函数的卡诺图 2n个方格 2 画卡诺圈 卡诺圈越少越好 因一个卡诺圈代表一个与项 卡诺圈内值为1的方格越多越好 因圈越大消去的变量越多 与项包含的变量越少 卡诺圈可以交迭 但每个卡诺圈必须至少有与其它卡诺圈不同的 值为1的方格 3 求每个卡诺圈的公共变量之积 与项 并相加 得到最简的与或表达式 卡诺圈 把2n个值为1的逻辑相邻的方格画成一个圈 表示最小项求逻辑和 例3 10化简函数 A B C D m 0 1 2 5 6 7 14 15 解 在画卡诺圈时 注意到卡诺图的对称相邻特性 可以想象将两边粘连 上下粘连 CD AB CD AB a b 因图 a 的卡诺圈比图 b 的多 所以图 b 是正确的卡诺圈 由图 b 函数Y的最简与或式为 解 例3 11已知逻辑函数Y A B C D m 0 1 2 8 9 10 11 13 15 求 函数Y的最简与或式 反函数的最简与或式 函数Y的最简或与式 CD AB CD AB Y的最简与或式 反函数的最简与或式 Y的最简或与式 3 反函数的最简与或式再取反可求函数Y的最简或与式 结论 1 圈1可求函数的最简与或式 2 圈0可求反函数的最简与或式 end 3 5具有无关项的逻辑函数化简 1 无关项概念 对应于函数不确定的最小项称为无关项 约束项和任意项 1 约束项 在n个变量的逻辑函数中 如果对变量的每个取值组合 函数均有确定的值 0或1 与之对应 则称这样的函数为确定的逻辑函数 否则 称为不完全确定的逻辑函数或具有无关项的逻辑函数 对某些逻辑问题 自变量的一些特定取值组合是不允许出现的 函数的取值无定义 它可能是0 也可能是1 对应于这些特定的取值组合 值为1的最小项称为约束项 例如 用2变量A B控制一台电梯 约束方程为AB 0 2 任意项 例如 将8421BCD码转换为余3码 对某些逻辑问题 对应于自变量的一些特定取值组合 函数的取值无关紧要 对逻辑功能没有任何影响 对应这些特定取值组合 值为1的最小项称为任意项 有确定的输出 无确定的输出 约束方程 约束方程的含义是 允许的取值组合满足约束方程 而不允许的取值组合则不满足约束方程 全部无关项之和等于0的方程称为约束方程 无关项在真值表和卡诺图中用 或 d 表示 约束方程可分解为多个方程 例如 每个无关项等于0 2 应用无关项化简函数 对于无关项 函数为任意值d 0或1 意味着在函数表达式中可以包含或者去掉无关项 在卡诺图中 无关项对应的方格可为0也可为1 例3 12用代数法化简函数 解 不完全确定的逻辑函数化简时 可根据需要加上或去掉部分甚至全部无关项 使函数化为最简 例3 13用卡诺图化简逻辑函数Y A B C D m 1 2 5 6 9 d 10 11 12 13 14 15 解 画24 16个格Y的卡诺图 图中无关项用 表示 最简的与或式为 CD AB 1 1 1 1 1 end