跳转至

1 逻辑计算与布尔代数

文本统计：约 1413 个字

选择逻辑计算的原因：

  • 不存在进位，可以用硬件实现
  • 通过一定方法实现算数计算

1.1 逻辑计算

1.1.1 相关概念

二元变量：无论是 True or False，还是 0/1， 均采用0和1代表两个值

逻辑运算符：与或非

  • 与(AND)：用 \(\cdot\) 来表示
  • 或(OR)：用 \(+\) 来表示
  • 非(NOT)：用 \(\overline X\) / \(X'\) / \(\sim\) 来表示

1.1.2 硬件表示（逻辑门）

常见的逻辑门

​ 现在使用的是晶体管，与、或、非对应的逻辑电路门的符号：

​ 还有其他常见的逻辑符号：与非，异或，或非，异或非

逻辑门的分类

（1）Basic logic gates（基础逻辑门）：与、或、非，选择这个的原因（相比第二个）：代数性质比较好

（2）Universal logic gates（通用门）：一个门电路可以表示所有布尔函数：与非门，或非门

NAND gate is an universal gate

（3）Other logic gates

门延时（Gate delay）

导线等传输会有实际上的损失，The delay between an input change(s) and the resulting output change is the gate delay，被记为 \(t_G\)

1.1.3 逻辑计算的表达

真值表（唯一）、波形图（唯一）、逻辑等式、逻辑图表。

Note

这里唯一的意思是一个逻辑计算的表示方式唯一。

1.2 布尔代数

1.2.1 基本运算规律

布尔代数的运算律

Identity Expression
Identity Law \(X + 0 = X\)
\(X \cdot 1 = X\)
Null Law \(X + 1 = 1\)
\(X \cdot 0 = 0\)
Idempotent Law \(X + X = X\)
\(X \cdot X = X\)
Complement Law \(X + \overline{X} = 1\)
\(X \cdot \overline{X} = 0\)
Double Negation Law \(\overline{\overline{X}} = X\)
Commutative Law \(X + Y = Y + X\)
\(XY = YX\)
Associative Law \((X + Y) + Z = X + (Y + Z)\)
\((XY)Z = X(YZ)\)
Distributive Law \(X(Y + Z) = XY + XZ\)
\(X + YZ = (X + Y)(X + Z)\)
DeMorgan's Law \(\overline{X + Y} = \overline{X} \cdot \overline{Y}\)
\(\overline{X \cdot Y} = \overline{X} + \overline{Y}\)

优先级：括号、非与或

1.2.2 对偶关系

代数变化的对偶表达：

  • 将AND与OR交换
  • 将0和1交换
  • 并保证运算顺序不变
原式 (F) 对偶式 (dual F)
\(F = (A + \overline{C}) \cdot B + 0\) \(F = (A \cdot \overline{C} + B) \cdot 1 = A \cdot \overline{C} + B\)
\(G = X \cdot Y + (\overline{W + Z})\) \(G = (X + Y) \cdot (\overline{W \cdot Z})\)
\(H = A \cdot B + A \cdot C + B \cdot C\) \(H = (A + B) \cdot (A + C) \cdot (B + C)\)

自对偶：对偶形式与原来的形式相同

\[ A\times B+A\times C+B\times C \]

就是一个自对偶式子

对偶的性质：F与G等价，则F'与G'亦等价

\[ X+XY = X \Leftrightarrow X(X+Y) = X \]

1.2.3 反函数

For logic function F, the inverse function of the original function is obtained by:

  • interchanging AND (+) and OR (·)

  • complementing each constant value and literal

\[ F = \overline A B+C\overline D \Rightarrow \overline F = (A+\overline B)(\overline C+D) \]

或者直接去反，利用DeMorgan定律进行展开

Example

\[ \text{Example: } F = \overline{x}yz + x\overline{y}\overline{z} \]
\[ \begin{aligned} \overline{F} &= \overline{\overline{x}yz + x\overline{y}\overline{z}}\\ &= \overline{\overline{x}yz} \cdot \overline{x\overline{y}\overline{z}}\\ &= (x + \overline{y} + \overline{z})(\overline{x} + y + z) \end{aligned} \]

1.2.4 恒等式的证明

DeMorgan定理的证明

\[ \begin{aligned} \overline{x + y} = \overline{x} \cdot \overline{y}\\ \overline{x \cdot y} = \overline{x} + \overline{y} \end{aligned} \]

  • To show this we need to show that \(A + \overline{A} = 1\) and \(A \cdot \overline{A} = 0\) with \(A = X + Y\) and \(\overline{A} = \overline{X} \cdot \overline{Y}\). This proves that \(\overline{X + Y} = \overline{X} \cdot \overline{Y}\).

  • Part 1: Show \(X + Y + \overline{X} \cdot \overline{Y} = 1\)

  • Part 2: Show \((X + Y) \cdot (\overline{X} \cdot \overline{Y}) = 0\)

或者我们可以直接使用真值表来证明

重要恒等式 mkdocs

Consensus 的证明

\[ \begin{aligned} x\cdot y + \overline x\cdot z + y\cdot z &= x\cdot y + \overline x\cdot z + (x+\overline x)\cdot y\cdot z \\ & = x \cdot y + x \cdot y \cdot z + \overline x\cdot z + \overline x \cdot y \cdot z\\ & = x\cdot y + \overline x\cdot z \end{aligned} \]

1.3 Canonical Forms (规范形式)

1.3.1 相关概念

It is useful to specify Boolean functions in a form that:

  • has a correspondence to the truth tables 与真值表紧密相连

  • allows comparison for equality 可以比较等价性

  • provides a starting point for optimization 给优化提供了起点

两种最为常见的规范形式

  • SOM (sum of min-terms): AND terms 用与连接

  • POM (product of max-terms): OR terms 用或连接

1.3.2 最大项与最小项

index编号区别：最大项与最小项相反

最大项与最小项的关系：\(M_i=\overline m_i\) 和 \(m_i=\overline M_i\)

SOM：就是取1的那些项的最小项

POM：就是取0的那些项的最大项

1.3.3 求解SOM与POM的方法

这里的求解方法是指的是从一般的式子来，并不是从真值得来

补全最小项的方法：列项（把缺的部分列项，然后运用分配律，然后把重复的去掉

\[ X = X (Y + \overline Y) = XY + X \overline Y \]

补全最大项的方法：分配律，加项然后迭代

\[ X + \overline X \overline Y =(X + \overline X)(X + \overline Y)=X+ \overline Y \]
\[ X+ \overline Y +Z \overline Z =(X+ \overline Y+Z)(X+ \overline Y +\overline Z) \]

规范项的反函数

  • SOM，取0的最小项
  • POM，取1的最大项

SOM与POM的转换：\(\sum_m (1,3,5,7) \Rightarrow \prod_M(0,2,4,6)\)

1.3.4 Standard Forms

SOP (sum of products) 与 POS (product of sums)

标准形式允许项里面存在缺项，比如说

\[ \begin{aligned} &\text{SOP: } ABC + \overline {AB} C +B\\ &\text{POS: } (A+B) \cdot (A+\overline B + \overline C)\cdot C \end{aligned} \]

标准形式还能继续优化成非标准形式（既不是 SOP 也不是 POS 的混合形式）,比如说

\[ \begin{aligned} &(AB+C)(A+C)\\ &AB\overline C + AC(A+B)\\ \end{aligned} \]

一个通过规范形式简化的例子

\(F(A, B, C) = Σm(1, 4, 5, 6, 7)\)

Writing the minterm expression:

\[ F = \overline{A} \overline{B} C + \overline{A} B \overline{C} + A \overline{B} \overline{C} + A B \overline{C} + A B C \]

Simplifying:

\[ \begin{aligned} F &= \overline{A} \overline{B} C + (A \overline{B} \overline{C} + A \overline{B}C) + (A B \overline{C} + A B C)\\ &= \overline{A} \overline{B} C + (A \overline{B} + A B)\\ &= \overline{A} \overline{B} C + A\\ &= \overline{B} C + A \end{aligned} \]

Simplified F contains 3 literals compared to 15 in minterm F

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！