逻辑代数

发表于 更新于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

0x00 定义

逻辑代数是代数的一个分支，与普通代数相比，逻辑代数主要定义了与，或，非三种运算，是用普通代数描述数字之间关系的方式来描述逻辑关系的形式主义[^wikipedia]。

逻辑代数是乔治·布尔（George Boole）在他的第一本书《逻辑的数学分析》（1847年）中引入的，并在他的《思想规律的研究》（1854年）中更充分的提出了逻辑代数。[^BooleGeorge]

0x01 起因

在学习 CS:APP 这本书的第2章时，常常用到位级运算，甚至它的习题还有只允许使用部分位级逻辑运算的规矩。当时在笔记上记下了要复习数字逻辑电路的知识，不过一直没有行动。今天在做 CS:APP 的 DataLab 时，更是感觉数字逻辑电路中常用的组合逻辑函数十分有用。在后悔大学数字电路没有好好学习而且没有笔记之后，还是得重新学习这方面的知识。

逻辑代数与计算机电子电路的行为紧密相关，实际上，香农在它的硕士学位论文中证明了两者之间的等价性[^Shannon]。在非硬件的场合，也非常有用，可以用它对复合条件表达式化简，写出最高效的逻辑表达式；或者可以作为完成CS:APP作业的后备知识。

由于课本早已丢失，以下的内容均来自互联网。具体来说，主要来自这篇博客。

0x02 基本规律

在逻辑代数中，我们使用大写字母 A, B, C... 等作为基本单元，它们可以是变量或者逻辑表达式。在编程语言中，常用 &, |, ~ 来表示位级的与，或，非，在逻辑代数中，AB 代表 A & B；A + B 代表 A | B；A' 则代表 ~A。

0/1律

  • 0 + A = A
  • 0·A = 0
  • 1 + A = 1
  • 1·A = A

这几条十分简单，不多解释。但是其常用于复杂表达式的化简过程中。

还原律/重叠律/互补律

  • A'' = A
  • A + A = A, A·A = A
  • A + A' = 1, A·A' = 0

交换律/结合律/分配律

将与和或看作普通代数中的乘和加，这些规律也与普通代数中具有的类似。

  • A + B = B + A
  • A·B = B·A
  • (A + B) + C = A + (B + C)
  • (AB)·C = A·(BC)
  • A(B + C) = AB + AC
  • A + BC = (A + B)(A + C)

较为特殊的是最后一条或对与的分配律，它与倒数第二条与对或的分配律形式上同构，但是与普通代数差异较大。

证明：(A + B)(A + C) = A + AB + AC + BC = A(1 + B + C) + BC = A + BC

摩根定律

  • (A + B)' = A'B'
  • (AB)' = A' + B'

这一规律可以总结为：或的非是非的与，与的非是非的或，或者用集合的概念讲：

并集的补集是补集的交集，交集的补集是补集的并集

这个公式十分重要，在逻辑函数化简和逻辑转换中必不可缺。例如，可以使用它将与逻辑转换为或逻辑和非逻辑——AB = (A' + B')'，也可以反过来——A + B = (A'B')'

根据这一定律的思想可以推出两条规则

  1. 反演规则：在对逻辑函数取反时，或变为与，与变为或，然后对每个量取反，但要保留组合量的非号。
    如：(((A + B)C + D)(E + F))' = ((A'B' + C')D') + E'F'
  2. 对偶规则：这个规则是上面提到的与或逻辑转换的一个严谨定义。它的内容是：若两个逻辑式F1=F2F_1 = F_2成立，那么它们的对偶式F1D=F2DF_1^D = F_2^D也成立。
    如：A(B + C) = AB + AC，分别求左右两边的对偶式：A + BC = (A + B)(A + C)。
    取对偶式的规则是：或变与，与变或，保证运算顺序不变；常数项0变1，1变0

常用公式

这一部分中的公式是根据上面基本公式推导而来，在逻辑函数化简时经常用到。

  • 吸收公式：A + AB = A
  • 消因子公式：A + A'B = A + B
  • 并项公式：AB + AB' = A
  • 消项公式：AB + A'C + BC = AB + A'C

其中消因子公式利用了或对与的分配律，吸收公式和并项公式利用了与对或的分配律的逆运算，消项公式的证明如下：

1
2
3
4
5
AB + A'C + BC
= AB + A'C + (A + A')BC
= AB + A'C + ABC + A'BC
= AB(1 + C) + A'C(1 + B)
= AB + A'C

逻辑函数化简与卡诺图

（这部分等到需要用了再写…

0xFF 参考

[^wikipedia] 维基百科-逻辑代数
[^BooleGeorge] Boole, George. An Investigation of the Laws of Thought. Prometheus Books. 2003 [1854]. ISBN 978-1-59102-089-9.
[^Shannon] Shannon C E. A symbolic analysis of relay and switching circuits[J]. Electrical Engineering, 1938, 57(12): 713-723.