第 12 章 布尔代数
# 第 12 章 布尔函数
# 12.1 布尔函数
# 12.1.1 引言
三个常用的布尔代数运算
布尔代数与逻辑运算之间的关系
# 12.1.2 布尔表达式和布尔函数
n 元布尔函数的定义
与布尔函数相关的运算
n 元布尔函数的个数
# 12.1.3 布尔代数恒等式
布尔恒等式表
# 12.1.4 对偶性
对偶的概念
对偶性原理
# 12.1.5 布尔代数的抽象定义
#
定义 1211
常见的布尔代数
- B={O, 1} 连同 OR、AND 运算及“补”运算
- 一个全集 U 的所有子集构成的集合, 连同并和交运算、 空集和全集以及集合的补运算
- 格的概念也可以用来定义相应的布尔代数
# 12.2 布尔函数的表示
两个问题
- 第一个问题相当于是如何从真值表得到布尔函数
# 12.2.1 积之和展开
#
字面值与极小项的定义
积之和展开式 (析取范式)
合之积展开式 (合取范式)
# 12.2.2 函数完备性
常见的函数完备的集合
NAND 和 NOR 运算
# 12.3 逻辑门电路
# 12.3.1 引言
布尔代数用于为电子装置的电路建立模型
- 这种电子装置输入和输出都可以认为是集合 {O, 1} 中的元素
- 计算机或其他的电子装置就是由许多电路构成的
- 电路可以根据布尔代数的规则来设计
- 电路的基本元件门, 每种类型的门实现一种布尔运算
组合电路或门电路
- 输出都只与输入有关, 而与电路的当前状态无关
- 即电路没有存储能力
一般使用三种基本的元件来构造组合电路
- 分别为反相器(inverter), 或门(OR gate),与门(AND gate)
- 示意图
- 具有
个输入的门
# 12.3.2 门的组合
使用反相器、或门和与门的组合可以构造组合电路
- 示意图
# 12.3.3 电路的例子
多数表决的电路,由多个开头混合控制灯的电路
# 12.3.4 加法器
半加法器
- 半加法器不考虑以前加法产生的进位
全加法器
- 注意全加法器的或门的两个输入不可能同时为 1
- 全加法器可以通过半加法器来构造,其考虑以前加法产生的进位
- 可以通过半加法器和全加法器来构造两个二进制整数的加法器
# 12.4 电路的极小化
# 12.4.1 引言
组合电路的基本设计流程
- 通过真值表,借助积之和表达式获得逻辑表达式
- 化简逻辑表达式
布尔函数的最小化
- 目的是产生等价表示布尔函数的满足下列条件的积之和
- 包含最少的布尔积
- 包含最少的字面值
布尔函数的最小化是一个 NP 完全问题
# 12.4.2 卡诺图 (Karnaugh map)
卡诺图给出了一种化简积之和展开式的可视化方法, 但此方法不适合机械化
2 个变元的卡诺图
- 相邻的极小项可以合并
3 个变元的卡诺图
- 注意能合并的块为
- 注意
块不能合并 - 也就是只有大小为
的幂的块可以合并
- 注意
- 本原素隐含的定义
4 个变元的卡诺图
🔲 待做事项
- n 变元布尔函数的卡诺图处理方法
# 12.4.3 无须在意的条件
无须在意的条件的定义和应用
# 12.4.4 奎因-莫可拉斯基方法
奎因-莫可拉斯基方法的基本流程
奎因-莫可拉斯基方法的实例
编辑 (opens new window)