CS207 Chapter 2
Chapter 2 布尔代数和逻辑门 Boolean Algebra and Logic Gates
布尔代数和逻辑门 Boolean Algebra and Logic Gates
布尔代数 Boolean Algebra
前面的二元逻辑是双值布尔代数，在一个有两个元素的集上（0和1），用三个逻辑符 + , · 和’。
一般性质 Properties：
- $A+0=A$ and $A·1=A$
- $A+1=A$ and $A·0=0$
- $A+A’=1$ and $A · A’= 0$
- $A+A=A$ and $A · A = A$
- $(A’)’=A$
一些规定 Postulates：
- 运算封闭 Closure：对于一个集S，如果二元运算能确定每一对S中元素都能获得唯一确定的S中的元素，则S对二元运算封闭。
- 结合律 Associative law：$(A+B)+C=A+(B+C)$ and $A(BC)=(AB)C$
- 交换律 Commutative law：$A+B=B+A$ and $AB=BA$
- 身份元素 Identity element：如果存在一个元素$E\in S$ 对于$S$中二元运算∗，其性质为：$E∗A = A∗E = A$则称之为∗的身份元素。例如0是+的身份元素，1是·的身份元素
- 分配律 Distributive law: $A(B+C) = AB+AC$ and $A+BC=(A+B)(A+C)$
- 德摩根 DeMorgan: $(A + B)’= A’B’$ and $ (AB)’= A’+B’$
- 吸收 Absorption: $A+AB = A$ and $A(A+B) = A$
双重性属性 Duality property:
每一个从布尔代数公设中推导出来的代数表达式，如果运算符和身份元素互换，仍然有效。
- 将 + 改为 · ，反之亦然。
- 将0 改为1，反之亦然。
例如：
• $A + A’= 1 → A · A’= 0$
• $A + B = B + A → AB = BA$
• $A(B + C) = AB + AC → A + BC = (A + B)(A + C)$
• $(A + B)’= A’B’→ (AB)’= A’+ B’$
布尔函数 Boolean function:
二元变量有两个值，要么是0，要么是1，布尔函数是一个由二元变量、两个二元运算符AND和OR、一个单元运算符NOT、括号和等号组成的表达式。一个函数的值可能是0或1，这取决于布尔函数或表达式中存在的变量的值。
- 举例来说：$F=AB’C$ 当$A=C=1，B=0$ 时$F = 1$，否则$F =0$
布尔函数也可以用真值表来表示
根据布尔函数的变量的所有可能值，以表格形式表示其数值。n个变量的数量→2 n个1和0的组合，一列代表根据不同组合的函数值。
例如：F = AB + C的真值表
A B C F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1
布尔函数化简
一个代数表达式的布尔函数可以实现为一个由逻辑门组成的逻辑电路图，最大限度地减少字数和术语的数量可以减少复杂的电路和门的数量。我们首先尝试使用布尔代数的公理和定理来进行简化。
- $F = AB + BC + B’C= AB + C(B + B’)= AB + C$
- $F = A’B’C + A’BC + AB’= A’C(B’+ B) + AB’= A’C + AB’$
- $F=XYZ+XY’Z +XYZ’= XZ(Y+Y’)+XY(Z+Z’)= XZ+XY = X(Y + Z)$
每一个布尔函数都只对应一个真值表，但有许多种代数表示形式
代数操作
- 减少项和字符的总数。
- 对于复杂的函数，通常要用计算机来化简函数
布尔函数的补 Boolean function complement
将一个布尔函数从F补到F’：将真值表中的0改为1，反之亦然，然后对多变量使用DeMorgan定理。
例如： $F = x’yz’+ x’y’z$
补函数 Complement: $F’= (x’yz’+x’y’z)’= (x’yz’)’(x’y’z)’= (x + y’+ z)(x + y + z’)$
对偶函数 Dual:
$F^*= (x’+ y + z’)(x’+ y’+ z)$
范式
逻辑函数通常用逻辑变量的不同组合及其真实形式以及补码形式来表达$X$和$X’$，一个任意的逻辑函数可以用以下形式表达，称为范式：
乘积之和(SOP)，和和的乘积(POS)。
- 一个函数所依赖的几个变量的逻辑乘积被认为是一个乘积项，当所有变量都参与时，称为最小项(minterms)。对于$x$和$y$，$xy$,$x’y$, $xy’$, 和$x’y’$都是最小项。
当所有变量都参与时，称为最大项(maxterms)。对于$x$和$y$，$x + y$, $x’+ y,$ $x + y’$ , 以及$x’+ y’$都是最大项(maxterms)。
- SOP：两个或多个逻辑乘积项的逻辑和被称为乘积表达式之和。
- POS：两个或多个逻辑和项的逻辑乘积被称为乘积表达式。
最小项 Minterms
- 在Minterms中，如果变量是真/非补码形式则代表1，补码形式代表0，其对应的二进制数为其编号？在对n个变量输入0，1时，只有一种组合可以拥有值1，其余的$2^n-1$种拥有值0
- SOP范式，又称Sum of minterms，一个布尔函数可被展开为一个真值表中所有拥有值1的的最小项的逻辑和。
- 一个逻辑函数的SOP范式可以通过以下几个步骤来得到：
- 检查给定逻辑函数的每一个项，如果是最小项则保留，继续同样方法检查下一个项。
- 检查每一个不是最小项的乘积缺少的变量（相对最小项），例如缺少X，则将该最小项与$(X+X’)$相乘。例如：$A+B \rightarrow A(B+B’)+B(A+A’) $
- 把所有的乘积乘开，丢掉冗余的项
最大项 Maxterms
- 在Maxterms中，如果变量是真/非补码形式则代表1，补码形式代表0，其对应的二进制数为其编号？在对n个变量输入0，1时，只有一种组合可以拥有值0，其余的$2^n-1$种拥有值1 （与Minterms相反）
- POS范式，又称Product of maxterms，一个布尔函数可被展开为一个真值表中所有拥有值0的的最大项的逻辑和。
从真值表中推导出函数
| A | B | C | F | Minterm | Maxterm |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | $A+B+C$ | |
| 0 | 0 | 1 | 0 | $A+B+C’$ | |
| 0 | 1 | 0 | 1 | $A’BC’$ | |
| 0 | 1 | 1 | 0 | $A+B’+C’$ | |
| 1 | 0 | 0 | 1 | $AB’C’$ | |
| 1 | 0 | 1 | 1 | $AB’C$ | |
| 1 | 1 | 0 | 1 | $ABC’$ | |
| 1 | 1 | 1 | 0 | $A’+B’+C’$ |
- 通过对四个乘积项求和或进行OR运算，可以得到输出F的最终SOP范型，如下所示
- $F = A’BC’+ AB’C’+ AB’C + ABC’= ∑ (2, 4, 5, 6)$
- 通过对四个和项求和或进行AND操作，得到输出F的POS范型，如下所示
- $F = (A + B + C)(A + B + C’)(A + B’+ C’)(A’+ B’+ C’) = ∏ (0, 1, 3, 7)$
- 两种范型的相互转化：Minterms是对应Maxterms的补函数
其他逻辑算子
数字逻辑门
- 由于布尔函数使用AND、OR和NOT操作来表达，所以用这些基本类型的门来实现布尔逻辑比较容易。但我们也可以构建其他类型的逻辑门，需要考虑以下因素：
- 物理参数产生门的可行性和经济性
- 扩展到两个以上输入的可能行
- 二进制运算符的基本属性，如可换性和联想性
- 该门单独或与其他门一起实现布尔函数的能力
多重输入的逻辑门
- 如果一个门的二进制操作是换元和联元的，那么它就可以扩展到有多个输入，AND和OR门都是换元的和联元的。
- NAND和NOR函数分别是AND和OR函数的补充，它们是互换的，但不是关联的。因此我们修改多输入NAND和NOR的定义
- $F = (ABC)’=A’+B’+C’$
- $F = (A+B+C)’=A’B’C’$
- XOR门和等价门都具有交换性和关联性。当偶数的1被施加到输入端时，门的输出为低电平，当1的数量为奇数时，输出为逻辑0。多输入排他性OR和等价门在实践中并不常见。
通用门
- NAND门和NOR门被称为通用门或通用构建块。任何类型的门或逻辑功能都可以通过这些门来实现。
- 通用门更方便使用电子元件来制作，同时减少了门的品种