2.1 逻 辑 代 数
逻辑代数是由英国数学家乔治·布尔（George Boole）于19世纪提出的，因此又称为布尔代数。逻辑代数是在数字系统中进行分析和设计的重要数学工具。
本章主要内容
& 逻辑代数的基本定理和基本运算规则
& 逻辑函数的标准形式和化简方法
2.1 逻 辑 代 数
2.1.1 基本逻辑运算
逻辑代数和普通代数的共同之处是，它们都有变量和变量的运算。不同之处在于，逻辑代数的变量即逻辑变量只有0和1两种取值，而且它的取值也已经没有数量上的意义了，而是代表两种不同的状态。例如，在逻辑电路中，0和1代表低电位和高电位，开关的断开和接通，晶体管的截止和饱和；在人们的逻辑思维中，0和1代表命题的假和真，条件的无和有。逻辑运算比较简单，基本的逻辑运算只有3种，下面分别介绍。
1．与运算
与运算也称为逻辑乘，它的含义是：只有当决定某一事情的全部条件都成立时，事情才发生，否则不发生。下面我们举个电路的例子来说明。
如图2-1所示，用两个开关A和B串联来控制一盏电灯F，电灯亮即为1，灭即为0，开关闭合为1，断开为0。可见，只有当A和B均闭合时，灯才亮。只要有一个开关不闭合，灯就不会亮。
图2-1 与运算电路图
表2-1 与运算真值表 F 0 0 0 1 1 0 1 1 0 0 0 1
A B
根据电路工作原理，可以列出与运算的真值表，如表2-1所示。
真值表就是把条件的逻辑状态的全部组合和对应的结果的逻辑状态用表格的形式表示出来，从而方便总结出条件与结果的逻辑关系。在今后的学习中，会经常用到真值表。
通常，把A与B的表达式写为：
F=A·B
或简写为：
F=AB
其中“·”代表与运算，除此之外，还可以用∩或∧来表示与运算。根据表2-1，可以总结出与运算的规律如下：
0·0=0
0·1=0
1·0=0
1·1=1
与运算的的概念可以推广到多个变量的情况，规律是不变的，即：只有条件全部为1时，结果才为1，只要有一个条件为0，结果就为0。
2．或运算
或运算也称为逻辑加，它的含义是：只有当决定某一事情的全部条件中有一个或一个以上成立时，事情就发生，只有当全部条件都不成立时，事情才不发生。下面同样举电路的例子来说明。
如图2-2所示，用两个开关A和B并联来控制一盏电灯F，电灯亮即为1，灭即为0，开关闭合为1，断开为0。可见，只要A和B中有闭合的，灯就亮。只有A和B都不闭合，灯才不会亮。
根据电路工作原理，可以列出或运算的真值表，如表2-2所示。
表2-2 或运算真值表 A B F 0 0 0 1 1 0 1 1 0 1 1 1
图2-2 或运算电路图
通常，把A或B的表达式写为：
F=A+B
其中“+”代表或运算，除此之外，还可以用∪或∨来表示或运算。根据表2-2，可以总结出或运算的规律如下：
0+0=0
0+1=1
1+0=1
1+1=1
或运算的的概念同样可以推广到多个变量的情况，规律是不变的，即：只有条件全部为0时，结果才为0，只要有一个条件为1，结果就为1。
3．非运算
非运算称为逻辑反或逻辑补，它的含义是：事情的结果F是对条件A求反，即若A为0，则F为1；若A为1，则F为0。可以用电路来说明。
表2-3 非运算真值表 A F 0 1 1 0
如图2-3所示，当开关A闭合为1时，灯F被短路为0；当开关A断开为0时，灯F接通为1。可见灯F的逻辑状态与A总是相反的。
在本书中，把非运算的表达式写为：
F=A'
其中，右上标“'”代表非运算，除此之外，人们还常用上画线“￣”来表示非运算。根据表2-3，可以总结出非运算的规律如下：
0'=1
1'=0
图2-3 非运算电路图
2.1.2 逻辑代数的基本定理
首先，给出逻辑代数中的5条公理，它们是逻辑代数基本定理的出发点，可以由逻辑代数的3种基本运算直接得出，不需证明。
（1）0·0=0 1+1=1
（2）0·1=1·0=0 1+0=0+1=1
（3）1·1=1 0+0=0
（4）0'=1 1'=0
（5）若A≠0，则A=1 若A≠1，则A=0
根据以上公理，可以推出一系列逻辑代数的基本定理。
（1）交换律
AB=BA A+B=B+A
（2）结合律
A（BC）=（AB）C A+（B+C）=（A+B）+C
（3）分配律
A（B+C）=AB+AC A+BC=（A+B）（A+C）
（4）自等律
A·1=A A+0=A
（5）0-1律
A·0=0 A+1=1
（6）互补律
A·A'=0 A+A'=1
（7）重叠律
AA=A A+A=A
（8）吸收律
A+AB=A A（A+B）=A
（9）非非律
（A'）' =A
（10）反演律（摩根定理）
（AB）'=A'+B' （A+B）' =A'·B'
（11）包含律
AB+A'C+BC=AB+A'C
（A+B）（A'+C）（B+C）=（A+B）（A'+C）
利用以上基本定理，还可以推导出一些常用的公式。
（1）AB+AB' =A
（2）（A+B）（A+B'）=A
（3）AB+A' C+BCD=AB+A'
（4）A+A' B=A+B
下面简单证明一下。
证：（1）AB+AB'
=A（B+B'）........................................................... 根据结合律
=A·1.................................................................... 根据互补律
=A......................................................................... 根据自等律
（2）（A+B）（A+B'）
=A+AB'+BA+BB'.................................................... 根据分配律
=A+A+0'................................................................ 根据互补律和（1）
=A......................................................................... 根据重叠律
（3）AB+A' C+BCD
=AB+A' C+BCD+BC............................................... 根据吸收律
=AB+A' C+BC（D+1）........................................... 根据结合律
=AB+A' C+BC........................................................ 根据0-1律
=AB+A' C............................................................... 根据包含律
（4）A+A' B
=（A+A' ）（A+B）.............................................. 根据分配律
=1·（A+B）......................................................... 根据互补律
=A+B..................................................................... 根据自等律
关于以上定理和常用公式，还应该注意以下4点。
· 将重叠律推广一下，任意多个A相与，结果仍为A。
· 在常用公式（3）中，BCD项换成BCDEF…，结果仍不变。
· 逻辑代数中没有定义减法，所以由A+B=A+C，不能得出B=C。
· 逻辑代数中也没有定义除法，所以由AB=AC，不能得出B=C。
下面介绍一种证明逻辑代数公式的最基本的方法——真值表法。
【例2-1】用真值表法证明包含律。
解：设F=AB+A'C+BC，G=AB+A'C。逻辑变量A﹑B﹑C的23=8种可能和F、G的对应的结果用真值表列示如下：
表2-4 真值表
|
A B C |
F=AB+A' C+BC |
G=AB+A' C |
|
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
0 1 0 1 0 0 1 1 |
0 1 0 1 0 0 1 1 |
可见，对于每一种可能的取值，F和G的结果都相同，显然说明F=G。即包含律得证。
2.1.3 逻辑代数的运算规则
首先，讲一下基本的运算规则。前面讲了逻辑代数的3种基本运算，那么由这3种基本运算可以混合若干复合运算。在复合运算中要遵循的基本运算规则如下所示：
· 在与、或、非混合运算时，按照先非、后与、再或的顺序运算。
· 对于有括号的复合运算，按照先括号内、再括号外的顺序运算。
下面我们讲几个逻辑代数中的特殊规则。
1．反演规则
反演就是由原变量F求反变量F' 的过程，将基本定理中的反演律推广，便可得到反演规则。
· 将原函数中的所有与运算变为或运算，或运算变为与运算。
· 将原函数中的所有原变量变为反变量，反变量变为原变量。
· 将原函数中的0变为1，1变为0。
这样就得到原函数F的反函数F'。下面举例说明。
【例2-2】求函数F=AB+CD的反函数F'。
解：根据反演规则，得
F'=（A'+B'）（C'+D'）
【例2-3】求函数F=（AB'）'+CD的反函数F'。
解：根据反演规则，得
F'=（A'+B）'（C'+D'）
【例2-4】求函数F=（A'B'+CD'E）'的反函数F'。
解：根据反演规则，得
F'=[（A+B）（C'+D+E'）]'
值得注意的是，在反演运算过程中，对包含两个或两个以上变量的非号应该保持不变，不能改变原式的运算顺序。反演规则在求复杂函数的反函数时，可以使运算大大简化。
2．对偶规则
前面在学习逻辑代数的基本定理时，很容易发现，除非非律外，每条定理中都包含两个等式，这两种类型的等式就互为对偶。对偶规则如下：
· 将原函数中的所有与运算变为或运算，或运算变为与运算。
· 将原函数中的0变为1，1变为0。
这样得到的函数Fd就为原函数的对偶式。与反演规则不同的是，各变量保持不变。下面举例说明。
【例2-5】求函数F=A+B（C'+DE'）的对偶式Fd。
解：根据对偶规则，得
Fd=A[B+C'（D+E'）]
注意，本题中的括号是十分必要的，因为在写函数的对偶式时，不能破坏原来的运算顺序。
【例2-6】求函数F=AB+（CD'+E）'的对偶式Fd。
解：根据对偶规则，得
Fd=（A+B）[（C+D'）E]'
函数的对偶式有以下性质。
· 若两个原函数相等，那么它们的对偶式也相等，即若F=G，则Fd=Gd。
· 原函数的对偶式的对偶式，为原函数本身。
【例2-7】求函数F=AB+C' D+（EF）' 的反函数F'和对偶式Fd。
解：根据反演规则，得
F'=（A'+B'）（C+D'）（E'+F'）'
根据对偶规则，得
Fd=（A+B）（C'+D）（E+F）'
2.1.4 基本逻辑电路
逻辑电路是对逻辑函数的实现，逻辑代数中的3种基本逻辑运算与﹑或﹑非对应了3种基本的逻辑电路，与门﹑或门和非门。下面分别来介绍这3种基本逻辑电路。
1．与门
与门电路是用来实现与运算的逻辑电路，其逻辑电路符号如图2-4所示。它实现的逻辑运算表达式为：F=A·B。这里图2-4中的符号和真值表2-5只举了两输入与门的例子，除此以外还有三输入和多输入的与门。
表2-5 与门真值表
图2-4 与门的电路符号及真值表
2．或门
或门电路是用来实现或运算的逻辑电路，其逻辑电路符号及真值表如图2-5和表2-6所示。它实现的逻辑运算表达式为：F=A+B。
或门同样也有两输入或门、三输入或门和多输入或门。这里只举两输入或门的例子。
表2-6 或门真值表
图2-5 或门电路符号
3．非门
非门电路又称反相门电路，是用来实现非运算的逻辑电路，其逻辑电路符号及真值表如图2-6和表2-7所示。它实现的逻辑运算表达式为：F=A'。
表2-7 非门真值表
图2-6 非门电路符号
除了这3种基本的逻辑门以外，还可以将它们构成功能更复杂的逻辑门，常见的有：与非门、或非门、与或非门、异或门、同或门等。下面逐一介绍这些复合门电路的逻辑关系、电路符号及相关特性。
4．与非门
与非门电路是用来实现与非运算的逻辑电路，二输入与非门电路符号及真值表如图2-7和表2-8所示。它实现的逻辑运算表达式为：F=（AB）' 。
表2-8 与非门真值表
图2-7 与非门电路符号
5．或非门
或非门电路是用来实现或非运算的逻辑电路，二输入或非门电路符号及真值表如图2-8和表2-9所示。它实现的逻辑运算表达式为：F=（A+B）'。
表2-9 或非门真值表
图2-8 或非门电路符号
6．与或非门
与或非门电路是实现逻辑表达式F=（AB+CD）'的电路。它的逻辑符号和真值表如图2-9和表2-10所示。
表2-10 与或非门真值表
图2-9 与或非门电路符号
7．异或门
异或门电路是实现逻辑表达式F=A' B+AB' =A?B的电路。它的逻辑符号和真值表如图2-10和表2-11所示。
表2-11 异或门真值表
图2-10 异或门电路符号
由真值表可以看出，当输入的两个状态相同时，输出F=0；当两个输入状态相异时，输出F=1，这就是异或的含义。
异或这种逻辑形式还有很多有用的特性：
（1）A?A=0
（2）A?A'=1
（3）A?0=A
（4）A?1=A'
（5）A?B' =（A?B）' =A?B?1
（6）A?B=B?A
（7）（A?B）?C=A?（B?C）
（8）A·（B?C）=（A·B）?（A·C）
证：（1）（2）可由异或的含义直接得到。
（3）A?0=A'·0+A·0'
=A·1
=A
（4）A?1=A'·1+A·1'
=A'+0
=A'
（5）A?B'=A' B'+AB ；
（A?B）'=（A' B+AB'）'
=（A' B）'·（AB'）'
=（A+B'）·（A'+B）
=AA'+A' B'+AB+B’ B
=A' B'+AB
所以，A?B'=（A?B）'，再根据性质（4），可证性质（5）成立。
（6）A?B=A' B+AB'
=B' A+BA'
=B?A
（7）用真值表来证明性质（7）。
异或运算性质（7）真值如表2-12所示。
表2-12 异或门真值表
A B C |
（A?B）?C |
A?（B?C） |
|
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
0 1 1 0 1 0 0 1 |
0 1 1 0 1 0 0 1 |
显然，性质（7）得证。
（8）A·（B?C）=A（B' C+BC' ）
=AB' C+ABC'
（A·B）?（A·C）=（AB）' AC+AB（AC）'
=（A'+B'）AC+AB（A'+C' ）
=A' AC+B' AC+ABA'+ABC'
=AB' C+ABC'
所以，A·（B?C）=（A·B）?（A·C）。
8．同或门
同或门也称为异或非门。它是实现逻辑表达式F=A⊙B= A' B'+AB的电路。根据对异或运算性质（5）的证明，可知A' B'+AB=（A?B）'，所以同或运算是异或运算的非运算。它的逻辑符号和真值表如图2-11和表2-13所示。
表2-13 同或门真值表
图2-11 同或门电路符号
由真值表可以看出，当输入的两个状态相同时，输出F=1；当两个输入状态相异时，输出F=0，这就是同或的含义。
值得注意的是，异或函数F与同或函数G有如下关系：
（1）F=G'，F'=G
（2）Fd=G，F=Gd
根据异或运算和同或运算的定义以及反演规则和对偶规则即可证明，证明过程略。