布尔代数
Since the final exam is upcoming, there should be some review of the basic math. Boolean Algebra is the most fundamental math behind the Application and Design of Digital Logic (ADDL) course. In the pure math's aspect, Boolean Algebra is only one topic in the algebraic structures. However, in the perspective of computer science, Boolean Algebra is the base of all digital logic. Here this paper will give a very brief overview of Boolean Algebra in pure math in the beginning. Following that will be its properties. Specifically, the mathematical tricks will be introduced, turning one expression into its simplest forms, including the sum of products (SoP) and the product of sums (PoS). A powerful device in the simplification will also be introduced in the end, the Karnaugh map. Few digital logic circuits will also be given, serving as vivid examples.
目录这篇写得比较水, 主要因为, 多数内容在实际设计中, 要不用不上, 要不太过基础, 写着没啥感觉.
1 布尔代数的两种定义方式
1.1 由格(Lattice)定义
Spark & Shine老师关于代数结构的笔记链接: 这里.
DEF1: 布尔代数属于格, 格是一种具有两个二元运算的代数系统. 布尔代数属于格中的有补分配格. 这里有补格保证每个元素有补元, 分配格保证每个元素的补元的唯一性.
1.2 由性质定义
DEF2: 一个布尔代数是一个集合\(B\), 它有两个二元运算\(\or\)和\(\and\), 元素\(0\)和\(1\), 以及一个一元运算\(^-\), 且对\(B\)中所有元素\(x,y\)和\(z\), 下列性质都成立:
\[\begin{align} &\textit{同一律} \begin{cases}x\or 0 = x\\ x\and 1 =x \end{cases}\\ &\textit{补律} \begin{cases}x\or \overline{x} = 1\\ x\and \overline{x} =0 \end{cases}\\ &\textit{结合律} \begin{cases}(x\or y)\or z = x\or (y \or z)\\ (x\and y)\and z =x\and( y\and z) \end{cases}\\ &\textit{交换律} \begin{cases}x\or y = y\or x\\ x\and y = y\and x \end{cases}\\ &\textit{分配律} \begin{cases}x\or (y\and z) = (x\or y)\and(x\or z)\\\ x\and (y\or z) =(x\and y)\or(x\and z) \end{cases}\\ \end{align} \]1.3 布尔代数提供的布尔运算
布尔代数提供的是集合\(\{0,1\}\)上的运算和规则, 这个集合及布尔代数的规则还可以用来研究电子和光学开关. 最基本的有三个布尔代数运算:
| 名称 | 符号 | C语言符号 | 性质 | |||
|---|---|---|---|---|---|---|
| 补运算 | \(\overline b\) |
~, bitwise inverting |
\(\overline 0=1\) | \(\overline 1 = 0\) | ||
| 布尔和 | \(OR/SUM,\ +\) |
|, bitwise inclusive \(OR\) |
\(1+1=1\) | \(1+0=1\) | \(0+1=1\) | \(0+0=0\) |
| 布尔积 | \(AND,\ \cdot\) |
&, bitwise \(AND\) |
\(1\cdot 1= 1\) | \(1\cdot 0=0\) | \(0\cdot1 =0\) | \(0\cdot0=0\) |
用以上三种运算可以组合出其它所有的逻辑运算. 其中常用的组合逻辑运算有 与非(NAND), 或非(NOR), 与或非(AND-NOR), 异或(EXCLUSIVE OR), 同或(EXCLUSIVE NOR).
C语言的位运算除了表中三种外, 还支持
^, 按位异或 (bitwise exclusive \(OR\)).
NAND是AND取反, NOR是OR取反;
AND-NOR是四输入, 两两与后再或, 再取反;
XOR(异或)是相同取0, 不同取1, NXOR(同或)则是异或取反.
2 布尔函数和数字逻辑
1854年, 乔治 布尔在书The Laws of Thought一书中第一次给出了逻辑的基本规则. 1938年, 克劳德-香农揭示了怎么用逻辑的基本规则来设计电路, 这些基本规则形成了布尔代数的基础.
这里重点在于布尔代数怎么用.
2.1 布尔函数
数学定义 | 设\(B=\{0,1\}\), 则\(B^n=\{x_1,x_2,\cdots,x_n|x_i\in B, 1\le i\le n\}\)是由\(0\)和\(1\)所能构成的所有\(n\)元有序列的集合.变元\(x\)如果仅从\(B\)中取值, 则称该变元为布尔变元, 即它的值只可能为\(0\)或者\(1\). 从\(B^n\)到\(B\)的函数称为\(n\)度布尔函数.
数电定义 | 布尔函数就是数字逻辑. 有一堆取值为0或1的输入, 经由这个数字逻辑后, 输出取值为0或1.
2.2 布尔函数的表示
- 数学函数的方式
- 真值表的方式
e.g.
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
- 逻辑图的方式
e.g.
- 波形图(waveform/ timing diagram)的方式
e.g.
不同表达方式之间可以相互转换.
2.3 布尔函数的最简表达式
最大项和最小项参考https://zhuanlan.zhihu.com/p/153395073
注意最小项的编号和最大项的编号是反着的.
2.3.1 积之和/ 最小项之和
e.g.
\[Y = \sum(0, 2, 5) \]2.3.2 和之积/ 最大项之积
e.g.
\[Y = \prod(1, 3, 4, 6, 7) \]2.3.3 任何布尔函数都可以只用与非, 或者只用或非门实现
2.4 布尔函数的化简
2.4.1 利用公式化简
两个定理得注意一下,
-
反演定理: 对于一个布尔函数\(Y\), 将其中所有的\(\cdot\)换成\(+\). \(+\)换成\(\cdot\), \(0\)换成\(1\), \(1\)换成\(0\), 原变量换成反变量, 反变量换成原变量, 其得到的结果就是\(Y'\). (德摩根就是反演的特例)
-
对偶定理(Duality): 若俩布尔表达式相等, 则它俩的对偶形式也相等.
对偶形式: \(Y\)的对偶形式\(Y^D\)为: 将\(Y\)所有的\(\cdot\)换成\(+\). \(+\)换成\(\cdot\), \(0\)换成\(1\), \(1\)换成\(0\). --> 变量不取反.
\[F = \sum_{ABC}(1,5,7)\\ F^D = \prod_{ABC}(6,2,0)=\sum_{ABC}(1,3,4,5,7) \]\(( A'B'C ) ^ D = A' + B' + C\), 即从原来\(1\)表示的\(001\)转为了最大项的\(110\), 即\(6\).
其实一般也不用公式化简, 这里随便再列了几个常用公式.
吸收律
\[\begin{align} x+xy&=x\\ x(x+y)&=x \end{align} \]合并律
\[\begin{align} xy + xy'&=x\\ (x+y)(x+y')&=x \end{align} \]添加律
\[\begin{align} xy + x'z + yz &= xy + x'z\\ (x+y)(x'z)(y+z) &= (x+y)(x'+z) \end{align} \]N-variable Theory
\[\begin{align} x+x+x+\cdots&=x\\ xxxxx\cdots&=x \end{align} \]2.4.2 利用卡诺图化简
不喜欢文档插很多图, 参考: https://blog.csdn.net/hahasusu/article/details/88244155
2.4.3 奎因-莫克拉司机方法(Q-M方法)
计算机逻辑化简使用的方法.