数字逻辑第2章布尔代数基础

1、第2章 布尔代数基础2.1 逻辑代数基础 2.1.1 逻辑代数的基本概念 2.1.2 基本逻辑运算 2.1.3 IEEE逻辑符号 2.1.4 逻辑代数的公理、定理和规则2.2逻辑函数 2.2.1 逻辑函数表达式的基本形式 2.2.2 逻辑函数的标准形式 2.2.3 逻辑函数表达式的转换2.3 逻辑函数的化简 2.3.1 代数化简法 2.3.2 卡诺图化简法 研究数字系统中逻辑电路设计和分析的数学工具是布尔代数。 布尔代数是由逻辑变量集K(A、B、C、)，常量“0”、“1”以及“与”、“或”、“非”3种基本逻辑运算构成的代数系统。 逻辑变量集K是布尔代数中变量的集合，它可以用任何字母表示，每个变

2、量的取值只能为常量“0”或“1”。 在数字系统中使用布尔变量表示开关电路的输入或输出。这些变量的每一个取值是“0”或“1”两个不相同的值。“0”可以代表低电压，“1”可以代表高电压。F( False )和T( True )也可以用于表示“0”或“1”。 布尔代数把矛盾的一方假设为“1”，另一方假设为“0”，使之数学化。 这样可以使用布尔代数中的公理和定理对物理现象作数学演算，达到逻辑推理的目的。 幸运的是，数字系统中采用的是“0”和“1”两个不同的值。因此布尔代数可以用来作为分析和设计逻辑电路的数学工具。 从应用的角度，布尔代数应用于逻辑电路领域称其为逻辑代数。 本章介绍逻辑代数的基本理论和运

3、算方法，其中包括逻辑代数基本概念，逻辑函数的定义，逻辑代数的公理、定理和规则，小项与大项的概念以及使用小项和大项表达逻辑函数的标准形式。 在此基础上，介绍应用逻辑代数法和卡诺图法化简逻辑函数的原理与方法。2.1.1 逻辑代数的基本概念 逻辑代数包含逻辑变量集K(A、B、C、)，每个变量的取值只可能为常量“0”或“1”。这里的“0”和“1”没有量的概念，是用来表达矛盾双方，是一种形式上的符号。 逻辑代数中逻辑变量之间是逻辑关系。逻辑关系用逻辑运算符表示。使用逻辑运算符连接逻辑变量及常量“0”或“1”构成逻辑代数表达式。 采用逻辑代数表示逻辑电路的输入与输出之间的逻辑关系，称逻辑函数。这种电路称数

4、字逻辑电路。 逻辑函数除了使用逻辑代数表示以外，还可以使用一种称为“真值表”的表格表示。 真值表是由输入变量所有可能取值的组合与这些组合值对应的输出变量的值构成的表格。真值表分为左、右两个部分。 左边部分每一列是输入变量的名字。右边部分的每一列是输出变量的名字。左边部分是输入变量所有的取值的组合。 如果一个逻辑函数有n个变量，则输入变量所有的取值有2n个组合。右边部分是把左边每一行输入变量的取值带到逻辑函数中去运算，把运算的结果“0”或者“1”填进来。这样就完成了把逻辑函数用真值表表示。逻辑函数有的比较简单，有的相当复杂。但是它们都是由“与”、“或”、“非”三种最基本的逻辑运算构成。下面分别介

5、绍这三种逻辑运算符、逻辑表达式、逻辑函数和逻辑函数符号。2.1.2基本逻辑运算1.“与”运算“与”运算的运算符是“”、“*”、“”或是空。在本书中使用“”表示“与”运算符。2.1.2基本逻辑运算2“或”运算“或”运算的运算符是“+”、“”。本书中使用“+”表示“或”运算符。2.1.2基本逻辑运算3“非”运算“非”运算的运算符是“ ”或“ ” ，本书中使用“ ” 表示“非”运算符。2.1.2基本逻辑运算4. “与非”运算“与非”函数是由“非”函数和“与”函数导出。 2.1.2基本逻辑运算5. “或非”运算“或非”函数是由“非”函数和“或”函数导出。2.1.2基本逻辑运算6“异或”运算“异或”运算

6、的运算符是“”。2.1.2基本逻辑运算7“同或”运算“同或”运算也可以称为“异或非”运算，其运算符是“”。“异或”运算表达式与“同或”运算表达式有如下关系： A B A B，A B A B2.1.3 IEEE逻辑符号如前所述，逻辑函数是由“与”、“或”、“非”三种最基本的逻辑运算构成。为了象表示电阻、电容和三极管一样，用图形化的方式表示不同的逻辑函数，美国国家标准学会( the American National Standards Institute, ANSI )和美国电气与电子工程师协会(the Institute of Electrical and Electronic Enginee

7、rs, IEEE) 在1984年制定了一个逻辑函数符号标准。如图2-1所示。图2-2是IEEE标准的“与”、“或”、“非”、“与非”、“或非”、“异或”、“异或非( 同或)”逻辑函数符号。11基本逻辑运算复合逻辑运算2.1.4 逻辑代数的公理、定理和规则逻辑代数系统有它的公理系统，公理系统不需要证明。逻辑代数系统的公理为逻辑代数的定理提供证明的依据。公理和定理也为逻辑代数证明提供演绎的数学基础。1、公理系统公理1 0 - 1律 对于任意的逻辑变量A，有 A + 0 = AA 1 = AA + 1 = 1A 0 = 0公理2互补律 对于任意的逻辑变量A，存在唯一的A,使得 A + A = 1A

8、A = 0公理3交换律 对于任意的逻辑变量A和B，有 A + B = B + A A B = B A公理4结合律 对于任意的逻辑变量A、B和C，有 ( A + B ) + C = A + ( B + C ) ( A B ) C = A ( B C )公理5分配律 对于任意的逻辑变量A、B和C，有 A + ( B C ) = ( A + B )( A + C ) A ( B + C ) = A B + A C2、基本定理根据逻辑代数的公理，推导出逻辑代数的基本定理。定理1 0 + 0 = 01 + 0 = 1 0 + 1 = 11 + 1 = 1 00 = 010 = 0 01 = 011 =

9、13、逻辑代数的重要规则： 逻辑代数有三条重要规则，它们是代入规则、反演规则和对偶规则。这三条规则常常使用在逻辑表达式的运算和变换中1 ) 逻辑函数的相等逻辑函数的相等 如果两个逻辑函数： F1 = f1 (A1,A2,，An), F2 = f2 ( A1,A2,An) 对于逻辑变量A1，A2，An的任何一组取值，分别代入到逻辑函数F1、F2中去。逻辑函数F1、F2如果都同时为“0”或者同时为“1”，则称逻辑函数F1与F2相等。2）代入规则 任何一个含有逻辑变量A的逻辑等式，如果将所有出现逻辑变量A的地方都用一个逻辑函数F代入，则该逻辑等式仍然成立，这个规则称为代入规则。 根据上面逻辑函数的定

10、义，对于某一个具体的逻辑电路，输出变量F的值取决于由输入变量A1, A2, ，An构成的2n个组合的取值。 另外，输出逻辑变量F的值还取决于逻辑电路的结构。 也就是，输出逻辑变量F的值取决于：1、输入变量A1A2，An的取值，2、逻辑电路的结构，3、逻辑电路使用的门电路类型。 逻辑函数的定义说明一个逻辑电路能够用一个逻辑函数F = f ( A1, A2, ，An )表示，即： 一个逻辑电路对应一个逻辑函数。 讨论逻辑函数也就是讨论这个逻辑函数对应的逻辑电路。 逻辑函数的定义实现了将一个具体的逻辑电路采用抽象的逻辑函数表示，这样可以使用数学工具来研究逻辑电路。 在数字逻辑中使用逻辑函数研究逻辑电

11、路从两个方面： 1、对某一个具体的逻辑电路进行分析，使用逻辑函数写出它的表达式，分析逻辑函数即分析相应的逻辑电路； 2、使用逻辑函数进行逻辑电路的设计。 逻辑电路的设计：一般是用文字表述的。根据文字表述，使用设计方法进行逻辑电路设计，得到的是按要求设计的逻辑电路的逻辑函数。最后根据逻辑函数画出按要求设计的逻辑电路。 因此，逻辑函数是逻辑电路分析和设计的重要数学工具。2.2.1逻辑函数表达式的基本形式1.“积之和”表达式“积之和”表达式是指表达式中的项是“与项”，项之间是“或”运算。一个“与项”可以是由多个原变量或者反变量通过“与”运算组成。在特殊的情况下“与项”是单个原变量或者反变量。例如，A

12、 B、A B C、C都是“与项”。A B + A B C + C是“积之和”表达式。2.“和之积”表达式“和之积”表达式是指表达式中的项是“或项”，项之间是“与”运算。一个“或项”可以是由多个原变量或者反变量通过“或”运算组成。例如，(A + B )、(A + B + C )都是“或项”。(A + B )(A + B + C )是“和之积”表达式。2.2.2 逻辑函数的标准形式 在逻辑函数的“与项”或者“或项”中，有些逻辑变量的个数与逻辑函数的变量个数相同，有些缺少其中的某些变量。另外在“与项”、“或项”中有些逻辑变量全部以原变量出现，有些全部以反变量出现，还有一些以原变量和反变量混合出现。

13、逻辑函数的标准形式是在逻辑函数表达式中全部的“与项”用“小项”组成。逻辑函数的另一种标准形式是在逻辑函数中全部的“或项”用“大项”组成。在逻辑电路的分析和设计中，逻辑函数时常用小项或者大项表示。 另外，逻辑函数有时也需要用小项或者大项表示。下面分别介绍小项与大项的概念，以及用小项或者大项表示的逻辑函数，即逻辑函数的标准形式。1.小项的定义和性质 一个有n个变量的逻辑函数F，它的一个“与项”包含有n个变量，每个变量以原变量或者反变量的形式出现在这个“与项”中，且仅出现一次，则这个“与项”称为该逻辑函数F的一个小项。 一个逻辑函数完全用小项表示，则称该逻辑函数是小项标准形式。2.2.3逻辑函数表达

14、式的转换 逻辑函数表达式的转换是把逻辑函数表达式的基本形式转换成标准形式。转换方法是采用逻辑代数方法。在转换中使用逻辑代数中的公理、定理和规则。1. “积之和”表达式转换成小项表达式 “积之和”表达式转换成用小项表示的标准形式，首先要将被转换的逻辑函数转换成“积之和”表达式。然后，在“积之和”表达式中使用X = X(Y + Y)，用以扩充被转换表达式中每一个“与项”中缺少的逻辑变量，使得每一个“与项”是小项。式中的X是某个“与项”中已有的逻辑变量，Y是扩充的逻辑变量。在扩充中如果有相同的小项产生出来，进行合并。被转换的表达式就是用小项表示的标准形式。 如果被转换的逻辑函数是“和之积”表达式，则

15、需要首先把“和之积”表达式转换成“积之和”表达式，然后再使用上述方法进行转换。2. “和之积”表达式转换成大项表达式 “和之积”表达式转换成大项的标准形式，首先要将被转换的逻辑函数转换成“和之积”表达式，然后在“和之积”表达式中使用X =(X + Y) ( X + Y )，用以扩充被转换表达式中的每一个“和之积”项中缺少的逻辑变量，使得每一个“和之积”是大项。式中X是某个“和之积”项中已有的变量，Y是扩充的逻辑变量。在扩充中如果有相同大项产生进行合并。被转换的表达式就是用大项表示的标准形式。 如前所述，一个逻辑函数的表达式有不同的形式。由于一个逻辑函数对应一个逻辑电路，逻辑函数表达式的形式不同

16、，它们所代表的逻辑电路的结构就不相同，但是在功能上又是相同的。逻辑函数表达式的形式越简单，它所对应的逻辑电路就越简单。这是逻辑电路设计中要考虑的问题。为了减少逻辑电路的复杂性，降低成本，对逻辑函数表达式存在化简的问题。逻辑函数的化简是去掉表达式中多余的“与项”或者是“或项”，求得最简的逻辑函数。所谓最简的逻辑函数，一是逻辑函数表达式中的“与项”、“或项”个数最少，二是“与项”、“或项”中的逻辑变量的个数最少。 对逻辑函数化简目前使用最多的方法是代数化简法和卡诺图化简法，下面分别进行介绍。 2.2.1代数化简法 使用代数化简逻辑函数，需要熟记和灵活运用逻辑代数中的公理、定理和规则。采用代数化简逻

17、辑函数的过程无一定的规律可循，化简过程中每一步的进展取决于对公理、定理和规则熟练使用的程度。1.“积之和”表达式的化简；下面归纳了几种化简 “积之和”表达式的方法，可以在逻辑函数化简中参考。2.3.2卡诺图化简法3.卡诺图化简原理 使用卡诺图化简逻辑函数，关键是如何把卡诺图中的小项，即填“1”的方格进行化简，直到把逻辑函数转换成最简的“与或”表达式。因此，在卡诺图上对逻辑函数进行化简是找出一种方法对卡诺图中的小项进行化简。对卡诺图中小项进行化简使用到前面介绍的小方格相邻的概念。 下面以三变量（A，B，C）为例说明卡诺图化简的原理。5.卡诺图化简逻辑函数举例 例2-7 用卡诺图将逻辑函数F（A,

18、 B, C, D） = m(0, 3, 5, 6, 7, 9, 11, 13, 15) 化简为最简“积之和”表达式。 解：第1步，画出该逻辑函数的卡诺图，把逻辑函数表示在卡诺图上，如图2-13所示。第2步，根据图2-13把尽量满足相邻关系的2m个小方格作为一个卡诺圈。该逻辑函数有5个卡诺圈，它们都是质蕴涵项。然后检查每一个质蕴涵项是不是首要蕴涵项。对于是首要蕴涵项。对于，它有一个m3不被覆盖，因此是首要蕴涵项。对于它有一个m6不被任何其他的质蕴涵项覆盖，因此是首要蕴涵项。同理也是首要蕴涵项。因此，所求的最简逻辑函数为例2-8 用卡诺将图逻辑函数F（A，B，C，D）= m(0,2,4,10,11

19、,14,15) 化简为最简“积之和”表达式。 解：第1步，画出该函数的卡诺图，把逻辑函数表示在卡诺图上，如图2-14所示。 解：这是一个用大项表示的逻辑函数。对于一个用大项表示的逻辑函数，它化简的结果应当是最简“和之积”式。为了在卡诺图上把用大项表示的逻辑函数化简成最简“和之积”式，首先把用大项表示的逻辑函数转换成用小项表示，即F（A, B, C, D）= m (1, 3, 5, 7, 8, 10, 11, 13,15)，将其表示在卡诺图中，如图2-15所示。然后在卡诺图上对填“0”的小方格进行化简，求出最简反函数F。再对最简反函数F使用反演规则，得到由“和之积”形式的最简逻辑函数。ABCD00 01 11 10000111101111111110000000 例2-9 使用卡诺图将逻辑函数F（A，B，C，D）= M（0，2，4