姜老师带你设计CPU之3

1.3.  布尔代数

计算机能够替代人脑进行工作的另一快基石，是布尔代数的理论和方法。布尔代数是人的思维判断与逻辑推理的一种数学抽象，因而它又叫逻辑代数。布尔代数是只有逻辑值“0”和“1”的代数，也可以说是最简单的代数。人们的逻辑思维活动，主要表现为判断和推理，用布尔代数就可以描述人脑的判断和推理。

1.3.1. 布尔代数的概念

在布尔代数的学习中，将使用系统这个概念。何为系统？严格地说现在尚无定论。一个系统可以认为是所涉及的对象全部，其中包括对象和对对象的各种处理操作。理论研究中，时常将对数据的各种处理操作称为运算。

定义1‑12   在一个非空集合上定义了若干个运算，那么所成的系统叫代数系统，简称代数。

实际当中人们研究的代数系统很多，由于课程的需要，在此只研究逻辑代数，也就是布尔代数。下面给出布尔代数的定义。

定义1‑13   布尔代数是在集合{0，1}上定义了运算：

所构成的系统。其中“＋”、“·”、“’”是“或”、“与”、“非”逻辑运算符。

在布尔代数中的0，1叫逻辑值，它们是逻辑常量。0常用来表示否定，1常用来表示肯定。例如，一盏灯的状态可以用0表示不亮，用1表示亮。再如，电路中某一点的电势相对某一个标准低就用0来表示，而这一点的电势高，就用1来表示。

1.3.2. 布尔代数的基本运算规则

布尔代数中逻辑值有或、与、非三种运算，这些运算是最基本的，通过它们的组合定义出一些新的运算都叫组合运算。就这三种基本运算来说，掌握好它们之间的运算规律，就足以使人们对逻辑代数有一个较全面的了解，特别是掌握这些运算之间的规律，对于进行逻辑运算的化简有着十分重要的意义。

逻辑变量与逻辑表达式

逻辑运算问题将涉及逻辑表达式的有关概念，为此要给出逻辑变量和逻辑表达式的定义。

定义1‑14   在布尔代数中取值0，1的变量就称为逻辑变量。

同一般代数中的变量一样，逻辑代数中的逻辑变量也用英文字母表示。例如，A，B，a，b，a1，b2等都取值0或1，它们都是逻辑变量。逻辑变量之间可以进行基本的逻辑运算，从而组成了各种运算关系式，这些关系式就是逻辑表达式。

定义1‑15   逻辑表达式是把逻辑常量、逻辑变量用逻辑运算符和表明运算顺序的括号连接起来组成的式子。

逻辑表达式的运算最终结果叫逻辑表达式的值。不论什么样的逻辑表达式，运算的最终结果，不是0，就是1，不会出现第三种结果，这种情况的逻辑代数又被称为二元逻辑。

在逻辑表达式中如果没有括号限制，三种基本逻辑运算的优先顺序是“非”、“与”、“或”，如果有括号存在，要从内向外的顺序进行运算。

按照习惯，在逻辑表达式中与运算的“·”号可以不写。

用或运算连接的逻辑表达式，又可以叫逻辑多项式，只包含变量自身或者变量的非的与运算的逻辑表达式，今后称为逻辑项。例如，x、y、z是逻辑变量，那么xy+yz+xz+xyz+x’z’是逻辑多项式，xy、yz、xz、xyz、x’z’都是逻辑项。

在计算机的设计问题讨论中，一个逻辑变量常用一条线来表示。

基本逻辑等式

有了逻辑表达式的概念，容易验证下面的基本逻辑运算规律。假设A、B、C、D为取值0，1的逻辑变量，则

由于变量只是取值0，1，所以上面的诸等式都十分容易验证。这里仅对几个公式进行验证。

【例1‑14】   验证A+（BC）=（A+B）（A+C）。

将变量A、B、C的全部可能值列在表1‑5的左边，而将等式两边的表达式列在右边。从表中可以看出A+（BC）和（A+B）（A+C）不论A、B、C取得何值时都是相等的。如此就证明了等式的正确性。

表1‑5   验证A+（BC）=（A+B）（A+C）

今后，把逻辑变量及逻辑表达式值变化的表叫真值表。

【例1‑15】   验证摩根定理 (A+B)’ =A’ B’ 和(AB)’=A’+B’。

将A、B的可能值和两等式的4个表达式都列成真值表（表1‑6），从表上可以看到，不论A，B取怎样的值，摩根定理的两个等式都是成立的。也就是总有

(A+B)’=A’B’

(AB)’=A’+B’

摩根定理验证完毕。

表1‑6   摩根定理验证

【例1‑16】   化简A’B+AB’+AB。

由【例1‑16】可见，逻辑表达式的化简可以有多种方法，实际当中要能够熟练运用基本公式来化简逻辑表达式。

1.3.3. 异或

异或是一个很有用的逻辑运算，在许多问题当中都会用到。异或实际上是一种特殊的组合逻辑运算，其表达式为A⊙B=A’B+AB’。

逻辑的异或运算表达的是两个互斥事件间的关系，“⊙”是异或运算符。

表1‑7所示的是变量A、B异或值的变化真值表。由表可以看出：A，B的值相同时，A⊙B为0，当A，B的值不相同时，A⊙B的值为1。

表1‑7   异或运算的真值表