第3章布尔代数基础 布尔代数得名于英国数学家乔治·布尔(George Boole,1815一1864)。为了研究人的 逻辑思维规律，他在1847年发表的《逻辑的数学分析》和1854年发表的《思维规律的研究》 两部著作中，首先提出了这种代数的基本概念和性质。此后，大约经过100年之久，于1938 年才由克劳德·香农(Claude E.Shannon)将布尔代数应用于电话继电器的开关电路中。至 今，布尔代数已成为分析和设计开关电路的重要数学工具。 本章不是从数学的角度去研究布尔代数，而是从应用的角度介绍布尔代数的一些基本 概念、基本定理、布尔函数的基本形式以及布尔函数的化简方法，以使读者掌握分析和设计 数字逻辑网络所需的数学工具。 3.1布尔代数的基本概念 计算机或其他数字系统无论多么复杂，它们都是由若干种最简单的、最基本的电路（如 门电路、触发器等)所组成的。这些电路的工作具有下列基本特点：从电路内部看，或是管 子导通，或是管子截止；从电路的输入输出看，或是电平的高低，或是脉冲的有无。由于这 种电路工作在开关状态，故称为开关电路。开关电路的工作状态可以用二元布尔代数来描 述，故二元布尔代数通常称为开关代数，或称为逻辑代数。因此，逻辑代数只是布尔代数的 一种特例。在本书中，如无特别说明，布尔代数均指逻辑代数。 3.1.1布尔变量及其基本运算 布尔代数和普通代数一样，用字母代表变量，布尔代数的变量称为布尔变量。和普通代 数不同的是，布尔变量只有两种取值，即0或1。并且，常量0和1没有普通代数中的0和1 的意义，它只表示两种可能，即命题的“假”和“真”，信号的“无”和“有”等。 布尔代数中的变量运算只有“或”“与”“非”3种基本运算，任何复杂的逻辑运算都可以 通过这3种基本运算来实现。 1.“或”运算 “或”运算又称为逻辑加。两个变量“或”运算的逻辑关系可表示为 F=A+B 式中，“+”号是“或”运算符。上式读作“F等于A或B”,或者“下等于A加B”,其意思是变 量A和B中只要有一者取值为1，则F就为1：若A和B全为0，则F为0。其逻辑关系可 以用真值表来描述，如表3.1所示
第3章 布尔代数基础 布尔代数得名于英国数学家乔治·布尔(GeorgeBoole,1815—1864)。为了研究人的 逻辑思维规律,他在1847年发表的《逻辑的数学分析》和1854年发表的《思维规律的研究》 两部著作中,首先提出了这种代数的基本概念和性质。此后,大约经过100年之久,于1938 年才由克劳德·香农(ClaudeE.Shannon)将布尔代数应用于电话继电器的开关电路中。至 今,布尔代数已成为分析和设计开关电路的重要数学工具。 本章不是从数学的角度去研究布尔代数,而是从应用的角度介绍布尔代数的一些基本 概念、基本定理、布尔函数的基本形式以及布尔函数的化简方法,以使读者掌握分析和设计 数字逻辑网络所需的数学工具。 3.1 布尔代数的基本概念 计算机或其他数字系统无论多么复杂,它们都是由若干种最简单的、最基本的电路(如 门电路、触发器等)所组成的。这些电路的工作具有下列基本特点:从电路内部看,或是管 子导通,或是管子截止;从电路的输入输出看,或是电平的高低,或是脉冲的有无。由于这 种电路工作在开关状态,故称为开关电路。开关电路的工作状态可以用二元布尔代数来描 述,故二元布尔代数通常称为开关代数,或称为逻辑代数。因此,逻辑代数只是布尔代数的 一种特例。在本书中,如无特别说明,布尔代数均指逻辑代数。 3.1.1 布尔变量及其基本运算 布尔代数和普通代数一样,用字母代表变量,布尔代数的变量称为布尔变量。和普通代 数不同的是,布尔变量只有两种取值,即0或1。并且,常量0和1没有普通代数中的0和1 的意义,它只表示两种可能,即命题的“假”和“真”,信号的“无”和“有”等。 布尔代数中的变量运算只有“或”“与”“非”3种基本运算,任何复杂的逻辑运算都可以 通过这3种基本运算来实现。 1.“或”运算 “或”运算又称为逻辑加。两个变量“或”运算的逻辑关系可表示为 F =A +B 式中,“+”号是“或”运算符。上式读作“F 等于A 或B”,或者“F 等于A 加B”,其意思是变 量A 和B 中只要有一者取值为1,则F 就为1;若A 和B 全为0,则F 为0。其逻辑关系可 以用真值表来描述,如表3.1所示
46 计算机组成原理（第2版） 2.“与”运算 “与”运算又称为逻辑乘。两个变量的“与”运算的逻辑关系可表示为： F=A.B 式中“”号表示“与”运算符。通常，“与”运算符可以省略。上式读作“F等于A与B”,或 者“F等于A乘B”。其含义是只有当变量A与B都为1时：F才为1：否则，F就为0。其 逻辑关系可以用真值表来描述，如表3.2所示 表31“或”运算 表3.2“与"运算 A B F A B F 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 3.“非”运算 “非”运算又称为逻辑取反。对一个变量的“非”运算的逻辑关系可表示为： F=万 表3.3“非”运算 式中“一”号表示“非”运算符。上式读作“℉等 A 于A的非”，其意思是若A为1，则F为0： 0 反之，若A为0，则F为1。“非”运算的逻辑 1 0 关系可以用表3.3所示的真值表米描述。 综合上述对布尔变量及其3个基本运算的定义，我们可以对布尔代数下个定义 布尔代数是一个由布尔变量集K,常量0、1以及“或”“与”“非”3种运算符所构成的代 数系统，记为 B=(K+,-,0,1) 其中，布尔变量集K是指布尔代数中的所有可能变量的集合，它可用任何字母表示，但每 个变量的取值只可能为常量0或1，而且布尔代数中的变量只有“或”“与”“非”3种运算。 3.1.2布尔函数及其表示方法 布尔代数中的函数定义与普通代数中函数定义十分相似，可以叙述如下。 设(x1江：，工)为布尔代数的一组布尔变量，其中每个变量取值为0或1，则当把， 序列(x1,x2,.,x.)映射到B={0,1}时，这个映射就是一个布尔函数。 从另一个角度，把布尔函数与逻辑网络联系起来，布尔函数可以这样叙述 设某一逻辑网铬的输入变量为x1,x2,.,x.,输出变量为F,如图3.1所示。对应于变 量x1x2.,x,的每一组确定值，F就有唯一确定的值，则称F是变量x1x,x的布 尔函数。记为
2.“与”运算 “与”运算又称为逻辑乘。两个变量的“与”运算的逻辑关系可表示为: F =A·B 式中“·”号表示“与”运算符。通常,“与”运算符可以省略。上式读作“F 等于A 与B”,或 者“F 等于A 乘B”。其含义是只有当变量A 与B 都为1时;F 才为1;否则,F 就为0。其 逻辑关系可以用真值表来描述,如表3.2所示。 表3.1 “或”运算 A B F 0 0 0 0 1 1 1 0 1 1 1 1 表3.2 “与”运算 A B F 0 0 0 0 1 0 1 0 0 1 1 1 3.“非”运算 “非”运算又称为逻辑取反。对一个变量的“非”运算的逻辑关系可表示为: F =A 式中“-”号表示“非”运算符。上式读作“F 等 于A 的非”,其意思是若 A 为1,则 F 为0; 反之,若A 为0,则F 为1。“非”运算的逻辑 关系可以用表3.3所示的真值表来描述。 表3.3 “非”运算 A F 0 1 1 0 综合上述对布尔变量及其3个基本运算的定义,我们可以对布尔代数下个定义: 布尔代数是一个由布尔变量集 K,常量0、1以及“或”“与”“非”3种运算符所构成的代 数系统,记为 B =(K,+,· ,-,0,1) 其中,布尔变量集 K 是指布尔代数中的所有可能变量的集合,它可用任何字母表示,但每一 个变量的取值只可能为常量0或1,而且布尔代数中的变量只有“或”“与”“非”3种运算。 3.1.2 布尔函数及其表示方法 布尔代数中的函数定义与普通代数中函数定义十分相似,可以叙述如下。 设(x1,x2,.,xn)为布尔代数的一组布尔变量,其中每个变量取值为0或1,则当把n 序列(x1,x2,.,xn)映射到B={0,1}时,这个映射就是一个布尔函数。 从另一个角度,把布尔函数与逻辑网络联系起来,布尔函数可以这样叙述: 设某一逻辑网络的输入变量为x1,x2,.,xn,输出变量为F,如图3.1所示。对应于变 量x1,x2,.,xn 的每一组确定值,F 就有唯一确定的值,则称F 是变量x1,x2,.,xn 的布 尔函数。记为 46 计算机组成原理(第2版)
第3章布尔代数基础 F=f(x1,x2,x.） 注意，布尔代数中函数的取值也只可能是0或1，这与普通代数 三思#一是不风你 布尔函数的表示方法有3种形式：布尔表达式、真值表利 图3.1布尔函数 卡诺图。这与普通代数中用公式、表格和图解这3种方法来表 示函数十分类似。 1.布尔表达式 布尔表达式是由布尔变量和“或”“与”“非”3种运算符所构成的式子，这是一种用公 式表示布尔函数的方法。例如，要表示这样一个函数关系：当两个变量A和B取值相同 时，函数取值为0；否则，函数取值为1。此函数称为异或函数，可以用下列布尔表达式来 表示： F=(A.B)=AB+AB 显然，只要将A和B的4种可能取值代入这表达式，验证是正确的。 与异或函数相反，当两个变量A和B取值相同时，函数取值为1；否则，函数取值为0 此函数称为同或函数。通常，异或运算用符号⊕表示：同或运算用⊙表示。因此，异或函 数、同或函数可分别表示成： F=IB+AB=A⊕B:F=不B+AB=A⊙B 2.真值表 真值表是由输入变量的所有可能取值组合及其对应的输出函数值所构成的表格，这是 一种用表格表示布尔函数的方法。例如，对于前面的异或函数，可以用表3.4所示的真值表 来表示。 表3.4异或函数的真值表 A B F 0 0 0 0 1 0 1 1 1 0 真值表中的变量为两个，共有2种取值组合，所以该表由4行组成。当变量为”个时。 真值表就由2”行组成。显然，随着变量数日的增加，真值表的行数将急剧增加。因此，一般 当变量数目不超过4个时，用真值表表示函数比较方便。 3.卡诺图 卡诺图是由表示逻辑变量的所有可能取值组合的小方格所构成的图形，如图3.2所示。 图中分别表示了二变量及三变量的卡诺图。 利用卡诺图，可以很方便地表示一个函数。只要在那些使函数值为1的变量取值组合
F =f(x1,x2,.,xn) 图3.1 布尔函数 注意,布尔代数中函数的取值也只可能是0或1,这与普通代数 是不同的。 布尔函数的表示方法有3种形式:布尔表达式、真值表和 卡诺图。这与普通代数中用公式、表格和图解这3种方法来表 示函数十分类似。 1.布尔表达式 布尔表达式是由布尔变量和“或”“与”“非”3种运算符所构成的式子,这是一种用公 式表示布尔函数的方法。例如,要表示这样一个函数关系:当两个变量 A 和B 取值相同 时,函数取值为0;否则,函数取值为1。此函数称为异或函数,可以用下列布尔表达式来 表示: F =f(A,B)=AB +AB 显然,只要将A 和B 的4种可能取值代入这表达式,验证是正确的。 与异或函数相反,当两个变量A 和B 取值相同时,函数取值为1;否则,函数取值为0。 此函数称为同或函数。通常,异或运算用符号表示;同或运算用☉表示。因此,异或函 数、同或函数可分别表示成: F =AB +AB =A B;F =AB +AB =A☉B 2.真值表 真值表是由输入变量的所有可能取值组合及其对应的输出函数值所构成的表格,这是 一种用表格表示布尔函数的方法。例如,对于前面的异或函数,可以用表3.4所示的真值表 来表示。 表3.4 异或函数的真值表 A B F 0 0 0 0 1 1 1 0 1 1 1 0 真值表中的变量为两个,共有2 2 种取值组合,所以该表由4行组成。当变量为n 个时, 真值表就由2 n 行组成。显然,随着变量数目的增加,真值表的行数将急剧增加。因此,一般 当变量数目不超过4个时,用真值表表示函数比较方便。 3.卡诺图 卡诺图是由表示逻辑变量的所有可能取值组合的小方格所构成的图形,如图3.2所示。 图中分别表示了二变量及三变量的卡诺图。 利用卡诺图,可以很方便地表示一个函数。只要在那些使函数值为1的变量取值组合 第3章 布尔代数基础 47
48 计算机组成原理（第2版） 所对应的小方格上标记1，便得该函数的卡诺图。例如，对于异或函数，可以用图3.3所示 的卡诺图来表示。 00011110 00010 0000010110100 001 10111 1001011111101 001 (a)二变量 ()三变量 10 图3.2卡诺图 图3.3异或函数的卡诺图 卡诺图可以看成是真值表的重新排列，真值表的每一行用一个小方格来表示。当变量 为两个时，真值表有4行，相应的卡诺图有4个方格：当变量为”个时，卡诺图有2”个方 格。卡诺图的这种方格排列方式比直值表更紧凑，而且便于进行函数的化简。 3.1.3布尔函数的“相等”概念 布尔函数和普通代数一样，也有函数相等的问题。两个函数相等的定义如下。 设有两个布尔函数 F=f(x1x.） G=g(x1x2.,x) 其变量都为x1x2,x。如果对应于变量x1x2,x。的任何一组变量取值，F和G的 值都相同，则称F和G是相等的，记为F一G。 显然，若两个布尔函数相等，则它们的真值表一定相同：反之，若两个布尔函数的真值 表完全相同，则此两个函数相等。因此，要证明两个布尔函数是否相等，只要分别列出它们 的真值表，看其是否相同。 例如，已知下列两个函数 F=ry.G=r+v 列出F和G的真值表，如表3.5所示。由表可知，它们的真值表完全相同，故F和G是相 等的，即有 ry=T+y 表3.5F=灯和G=F+了的真值表 F=- G=+ 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 0 0
所对应的小方格上标记1,便得该函数的卡诺图。例如,对于异或函数,可以用图3.3所示 的卡诺图来表示。 图3.2 卡诺图 图3.3 异或函数的卡诺图 卡诺图可以看成是真值表的重新排列,真值表的每一行用一个小方格来表示。当变量 为两个时,真值表有4行,相应的卡诺图有4个方格;当变量为n 个时,卡诺图有2 n 个方 格。卡诺图的这种方格排列方式比真值表更紧凑,而且便于进行函数的化简。 3.1.3 布尔函数的“相等”概念 布尔函数和普通代数一样,也有函数相等的问题。两个函数相等的定义如下。 设有两个布尔函数 F =f(x1,x2,.,xn) G =g(x1,x2,.,xn) 其变量都为x1,x2,.,xn。如果对应于变量x1,x2,.,xn 的任何一组变量取值,F 和G 的 值都相同,则称F 和G 是相等的,记为F=G。 显然,若两个布尔函数相等,则它们的真值表一定相同;反之,若两个布尔函数的真值 表完全相同,则此两个函数相等。因此,要证明两个布尔函数是否相等,只要分别列出它们 的真值表,看其是否相同。 例如,已知下列两个函数 F =xy, G =x- +y - 列出F 和G 的真值表,如表3.5所示。由表可知,它们的真值表完全相同,故F 和G 是相 等的,即有 xy=x- +y - 表3.5 F=xy 和G=x -+y - 的真值表 x y xy F=xy x - y - G=x -+y - 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 48 计算机组成原理(第2版)
第3章布尔代数基础 49 3.2布尔代数的公式、定理和规则 3.2.1布尔代数的基本公式 根据布尔变量的取值只有0和1，以及布尔变量仅有的3种运算的定义，不难推出下列 基本公式。 (1)交换律 A+B=B+A A·B=B·A (2)结合律 (A+B)+C=A+(B+C) (A·B)·C=A·(B·C) (3)分配律 A·(B+C)=A·B+A·C A+B·C=(A+B)(A+C) (4)0-1律 A+0=A A+1=1 A·0=0 A.1=A (5)互补律 A+A=1 A.A=0 (6)等幂律 A+A=A A·A=A (7)吸收律 (A+AB=A A+不B=A+B (A(A+B)-A A(A+B)=AB (8)对合律（双重否定律） A-A 以上是布尔代数的基本公式。其中交换律、结合律、分配律、0-1律、互补律和对合律可 以作为布尔代数的公理。公理是代数系统的基本出发点，是客观存在的抽象，它无须证明
3.2 布尔代数的公式、定理和规则 3.2.1 布尔代数的基本公式 根据布尔变量的取值只有0和1,以及布尔变量仅有的3种运算的定义,不难推出下列 基本公式。 (1)交换律 A +B =B +A A·B =B·A (2)结合律 (A +B)+C =A + (B +C) (A·B)·C =A·(B·C) (3)分配律 A·(B +C)=A·B +A·C A +B·C =(A +B)(A +C) (4)0-1律 A +0=A A +1=1 A·0=0 A·1=A (5)互补律 A +A =1 A·A =0 (6)等幂律 A +A =A A·A =A (7)吸收律 A +AB =A A +AB =A +B A(A +B)=A A(A +B)=AB (8)对合律(双重否定律) A = =A 以上是布尔代数的基本公式。其中交换律、结合律、分配律、0-1律、互补律和对合律可 以作为布尔代数的公理。公理是代数系统的基本出发点,是客观存在的抽象,它无须证明, 第3章 布尔代数基础 49
50 计算机组成原理（第2版） 但它可以用客观存在来验证。以此为基础，可以推得布尔代数的等幂律与吸收律。例如，等 幂律的证明如下： A+A=(A+A)·1 (0-1律) =(A+A)(A+A) (互补律) =A+A·A (分配律) =A+0 (互补律) =A (0-1律) 又如，吸收律的证明如下， A+AB=(A+A)(A+B) (分配律) =1·(A+B) (互补律) -A+B (0-1律) 必须指出，上述基本公式中，有些公式与普通代数中的相同，如交换律，结合律，但有些 公式却是布尔代数中所特有的，如分配律。 3.2.2布尔代数的主要定理 定理3.1德·摩根(De Morgan)定理。 (1),+工，+.+工，-1·元：.f 这就是说，”个变量的“或”的“非”等于各变量的“非”的“与”，”个变量的“与”的“非”等 干各变品的“非”的“或”。 当变量数目较少时，该定理可很容易用真值表证明。当变量为”个时，则可以用数学 归纳法证明。 德·摩根定理是布尔代数中一个很重要且经常使用的定理，它提供了一种变换布尔表 达式的简便方法。由于它具有反演特性，即把变量的与运算改成或运算，或运算改成与运 算，所以又称为反演律。 定理3.2香农(Shannon)定理。 f(x1x2,x01,+,)=f(1,2.，.1,0,+) 这就是说，任何函数的反函数（或称补函数），可以通过对该函数的所有变量取反，并将常量 1换为0,0换为1，运算符“+”换为“”，“·”换为“+”而得到 证明根据德·摩根定理，任何函数的反函数可写成 f(x1x2,x.01,十，) =f1(x1x,x.0,1,+,)+f2(x1x2.,x。0,1,+,) -1(x1x2.,x。0,1,+,)·2(x1x2,.x,0,1,+, 或写成 f(x1x2x。0,1,+,) =1(x1x,.x。0,1,+,）·f2(x1x2.,x。0,1,+, =f1(x1x2,.,x0,1,+,)+f2(x1x2,.,x0,1,+,)
但它可以用客观存在来验证。以此为基础,可以推得布尔代数的等幂律与吸收律。例如,等 幂律的证明如下: A +A =(A +A)·1 (0-1律) =(A +A)(A +A) (互补律) =A +A·A (分配律) =A +0 (互补律) =A (0-1律) 又如,吸收律的证明如下: A +AB =(A +A)(A +B) (分配律) =1·(A +B) (互补律) =A +B (0-1律) 必须指出,上述基本公式中,有些公式与普通代数中的相同,如交换律、结合律,但有些 公式却是布尔代数中所特有的,如分配律。 3.2.2 布尔代数的主要定理 定理3.1 德·摩根(DeMorgan)定理。 (1)x1+x2+.+xn=x - 1·x - 2·.·x - n (2)x1·x2·.·xn=x - 1+x - 2+.+x - n 这就是说,n 个变量的“或”的“非”等于各变量的“非”的“与”,n 个变量的“与”的“非”等 于各变量的“非”的“或”。 当变量数目较少时,该定理可很容易用真值表证明。当变量为n 个时,则可以用数学 归纳法证明。 德·摩根定理是布尔代数中一个很重要且经常使用的定理,它提供了一种变换布尔表 达式的简便方法。由于它具有反演特性,即把变量的与运算改成或运算,或运算改成与运 算,所以又称为反演律。 定理3.2 香农(Shannon)定理。 f(x1,x2,.,xn,0,1,+,·)=f(x- 1,x- 2,.,xn,1,0,·,+) 这就是说,任何函数的反函数(或称补函数),可以通过对该函数的所有变量取反,并将常量 1换为0,0换为1,运算符“+”换为“·”,“·”换为“+”而得到。 证明 根据德·摩根定理,任何函数的反函数可写成 f(x1,x2,.,xn,0,1,+,·) =f1(x1,x2,.,xn,0,1,+,·)+f2(x1,x2,.,xn,0,1,+,·) =f1(x1,x2,.,xn,0,1,+,·)·f2(x1,x2,.,xn,0,1,+,·) 或写成 f(x1,x2,.,xn,0,1,+,·) =f1(x1,x2,.,xn,0,1,+,·)·f2(x1,x2,.,xn,0,1,+,·) =f1(x1,x2,.,xn,0,1,+,·)+f2(x1,x2,.,xn,0,1,+,·) 50 计算机组成原理(第2版)
第3章布尔代数基础 51 其中，「1和f了2是∫的两个部分函数。对∫1和∫2重复上述过程，直到使∫中的每个变量 都用德·摩根定理，由于每对f(或f的部分函数)应用一次德·摩根定理，就将部分函数 (或子部分函数)取反，并将“与”“或”运算变换一次，以求得函数∫（或部分函数）的反函数 了，因此，当对∫的每个变量进行德·摩根变换后，其结果必然是f(1,2,.元。，1,0，·，十)， 证毕。 香农定理实际上是德·摩根定理的推广，它可以用在任何复杂函数。 【例3.1】已知函数F-AB+AB(C+),求其反函数F F-AB+AB(C+D)-AB .AB(C+D) =(A+B)·(AB+C+D)=(A+B)(A+B)+CD) 利用香农定理，可以直接写出 F=(A+B)·(不+B+CD) 定理3.3展开定理。 (1)f(x1x2.,x.x.) =x;f(x1x2.,1,.,x,)+五f(x1x,.,0,.,x,) (2)f(x1x2.x） =(x,十f(x1,x2.,0,.,x.)·(E:十f(x1x2,.,1,.,x.) 这就是说，任何布尔函数都可以对它的某一变量x,展开，或展开成(1)所示的“与-或”形 式，或展开为(2)所示的“或-与”形式。 证明将x,=1,x,=0代入上式，再将x,=0,=1代入上式，则两种情况下等式均 成立。证毕。 由展开定理可得下列两个推理。 推理3.1 (a)x:f(x1,xix.)=x,f(x1.,1,.,xn） (b)x,+f(x1.,1.,x)=x,+f(x1.,0,x) 推理3.2 (a)xf(x1,.,x,.,x.)=xf(x1,.,0,.,x.) (b)+f(x1.,x.,x.)=x;+f(x1.,1.） 下面举例说明展开定理的应用。 【例3.2】证明公式AB+AC+BC=AB+AC(包含律). 用展开定理，等号左边可展开成 左边=A(1·B+0·C+BC)+A(0·B+1·C+BC) =A(B+BC)+(C+BC)=AB+AC=右边 证毕 【例3.3】将函数F=万B+AC表示成“或-与”形式。 由展开定理，可得 F-[A+(1·E+0·C)]·[A+(0·B+1·C)]-(A+B)(+C) 3.2.3布尔代数的重要规则 布尔代数有3个重要规则，即代入规则、反演规则和对偶规则，现分别叙述如下
其中,f1 和f2 是f 的两个部分函数。对f1 和f2 重复上述过程,直到使f 中的每个变量 都用德·摩根定理。由于每对f(或f 的部分函数)应用一次德·摩根定理,就将部分函数 (或子部分函数)取反,并将“与”“或”运算变换一次,以求得函数f(或部分函数)的反函数 f -,因此,当对f 的每个变量进行德·摩根变换后,其结果必然是f(x - 1,x - 2,.,x - n,1,0,·,+), 证毕。 香农定理实际上是德·摩根定理的推广,它可以用在任何复杂函数。 【例3.1】 已知函数F=AB+AB(C+D),求其反函数F。 F =AB +AB(C +D)=AB·AB(C +D) =(A +B)·(AB +C +D)=(A +B)((A +B)+CD) 利用香农定理,可以直接写出 F =(A +B)·(A +B +CD) 定理3.3 展开定理。 (1) f(x1,x2,.,xi,.,xn) =xif(x1,x2,.,1,.,xn)+x - if(x1,x2,.,0,.,xn) (2) f(x1,x2,.,xi,.,xn) =(xi+f(x1,x2,.,0,.,xn))·(x - i+f(x1,x2,.,1,.,xn)) 这就是说,任何布尔函数都可以对它的某一变量xi 展开,或展开成(1)所示的“与-或”形 式,或展开为(2)所示的“或-与”形式。 证明 将xi=1,x - i=0代入上式,再将xi=0,x - i=1代入上式,则两种情况下等式均 成立。证毕。 由展开定理可得下列两个推理。 推理3.1 (a)xif(x1,.,xi,.,xn)=xif(x1,.,1,.,xn) (b)xi+f(x1,.,xi,.,xn)=xi+f(x1,.,0,.,xn) 推理3.2 (a)xif(x1,.,xi,.,xn)=xif(x1,.,0,.,xn) (b)xi+f(x1,.,xi,.,xn)=xi+f(x1,.,1,.,xn) 下面举例说明展开定理的应用。 【例3.2】 证明公式AB+AC+BC=AB+AC(包含律)。 用展开定理,等号左边可展开成 左边 =A(1·B +0·C +BC)+A(0·B +1·C +BC) =A(B +BC)+A(C +BC)=AB +AC =右边 证毕 【例3.3】 将函数F=AB+AC 表示成“或-与”形式。 由展开定理,可得 F =[A + (1·B +0·C)]·[A + (0·B +1·C)]=(A +B)(A +C) 3.2.3 布尔代数的重要规则 布尔代数有3个重要规则,即代入规则、反演规则和对偶规则,现分别叙述如下。 第3章 布尔代数基础 51
52 计算机组成原理（第2版） 1.代入规则 任何一个含有变量x的等式，如果将所有出现x的位置，都代之以一个布尔函数F,则 等式仍然成立。这个规则称为代人规则。 由于任何一个布尔函数也和任何一个变量一样，只有0或1两种取值，显然，以上规则 是成立的。 【例34】已知等式A+B-A·B,函数F=B十C,若用F代入此等式中的B,则有 A+(B+C)=万·B+C A+B+C=A.B.C 据此可以证明n变量的德·摩根定理的成立。 2.对偶规则 任何一个布尔函数表达式F,如果将表达式中的所有的“十”改成“·”，“·”改成“+”， “1”改成“0”，“0”改成“1”，而变量保持不变，则可得到一个新的函数表达式F,我们称F。为 F的对偶函数，这一规则称为对偶规则。例如，下列为几个原函数及其对偶函数： F=AB+ABC Fa=(A+B)(A+B+C) F=A(B+CD)+E F,=[A+B(C+D)]·E F=(A+0)·(B+C·1) F=A·1+B·(C+0) F=A+B+C+D+E F4=A·B.c.D.E 需要注意的是，在运用对偶规则求对偶函数时，必须按照先“与”后“或”的顺序，否则容 易写错，如F=不B十AEC,若求出对偶函数F4=万十B·A+B+C,是错误的。因此，要 特别注意原来函数中的“与”项，当这些“与”项变为“或”项时，应加括号。 从上面这些例子可以看出，如果F的对偶函数为F。,则F的对偶函数就是F。也就是 说，F和F互为对偶函数，即(Fa)。=F。 由布尔代数的基本公式可以看出，它们都是成对出现的互为对偶的等式。由此证明一 个规则：如果两个函数的表达式相等，则它们的对偶函数也相等，即如果函数F=G,则其 对偶函数F4=Ga。 3.反演规则 任何一个布尔函数表达式F,如果将表达式中的所有的“+”改成“·”，“·”改成“+” “1”改成“0”，“0”改成“1”，原变量改成反变量，反变量改成原变量，则可得函数F的反函数 (或称补函数)下，这个规则称为反演规则。 实际上，反演规则就是香农定理。运用反演规则可以很方便地求一个函数的补函数 例如，下列为几个原函数及其补函数： F-AB+ABC P=(A+B)(不+B+C) F=A(B+CD)+E F=[不+B(C+D)]·E F=(A+0)·(B+C·1) F=A·1+B·(C十0) F-A+B+C+D+E F-A·B·C.D·E
1.代入规则 任何一个含有变量x 的等式,如果将所有出现x 的位置,都代之以一个布尔函数F,则 等式仍然成立。这个规则称为代入规则。 由于任何一个布尔函数也和任何一个变量一样,只有0或1两种取值,显然,以上规则 是成立的。 【例3.4】 已知等式A+B=A·B,函数F=B+C,若用F 代入此等式中的B,则有 A + (B +C)=A·B +C A +B +C =A·B·C 据此可以证明n 变量的德·摩根定理的成立。 2.对偶规则 任何一个布尔函数表达式F,如果将表达式中的所有的“+”改成“·”,“·”改成“+”, “1”改成“0”,“0”改成“1”,而变量保持不变,则可得到一个新的函数表达式Fd,我们称Fd 为 F 的对偶函数,这一规则称为对偶规则。例如,下列为几个原函数及其对偶函数: F=AB+ABC Fd=(A+B)(A+B+C) F=A(B+CD)+E Fd=[A+B(C+D)]·E F=(A+0)·(B+C·1) Fd=A·1+B·(C+0) F=A+B+C+D+E Fd=A·B·C·D·E 需要注意的是,在运用对偶规则求对偶函数时,必须按照先“与”后“或”的顺序,否则容 易写错,如F=AB+ABC,若求出对偶函数Fd=A+B·A+B+C,是错误的。因此,要 特别注意原来函数中的“与”项,当这些“与”项变为“或”项时,应加括号。 从上面这些例子可以看出,如果F 的对偶函数为Fd,则Fd 的对偶函数就是F。也就是 说,F 和Fd 互为对偶函数,即(Fd)d= F。 由布尔代数的基本公式可以看出,它们都是成对出现的互为对偶的等式。由此证明一 个规则:如果两个函数的表达式相等,则它们的对偶函数也相等,即如果函数F=G,则其 对偶函数Fd=Gd。 3.反演规则 任何一个布尔函数表达式F,如果将表达式中的所有的“+”改成“·”,“·”改成“+”, “1”改成“0”,“0”改成“1”,原变量改成反变量,反变量改成原变量,则可得函数F 的反函数 (或称补函数)F,这个规则称为反演规则。 实际上,反演规则就是香农定理。运用反演规则可以很方便地求一个函数的补函数。 例如,下列为几个原函数及其补函数: F=AB+ABC F=(A+B)(A+B+C) F=A(B+CD)+E F=[A+B(C+D)]·E F=(A+0)·(B+C·1) F=A·1+B·(C+0) F=A+B+C+D+E F=A·B·C·D·E 52 计算机组成原理(第2版)
第3章布尔代数基础 53 与求对偶函数一样，求补函数需要注意的是，在运用反演规则时，必须按照先“与”后 “或”的顺序进行变换。因此，特别要注意原来函数中的“与”项，当这些“与”项变换为“或”项 时，应加括号 把上述补函数的例子与前面对偶函数的例子对照一下，可以看出，补函数和对偶函数之 间在形式上只差变量的“非”。因此，若已求得一函数的对偶函数，只要将所有变量取反便得 该函数的补函数：反之亦然。 3.3布尔函数的基本形式 一个布尔函数的表达式可以有多种表示形式，本节讨论几种基本形式，它们是进行布尔 函数化简的基础。 3.3.1函数的“积之和”与“和之积”形式 根据展开定理，任何一个”变量函数总可以展开成“与或”形式，或者“或与”形式。其 中“与-或”形式又称为“积之和”形式，而“或-与”形式又称为“和之积”形式。 所谓“积之和”，是指一个函数表达式中句含若干个“积”项，其中每个“积”项可有一个成 多个以原变量或反变量形式出现的字母，这些“积”项的“和”就表示了一个函数。例如，一个 三变量函数为 F(A,B,C)-万+BC+ABC 其中，A,BC、ABC均为“积”项。这些积项的和，就表示了函数的“积之和”形式。 所谓“和之积”，是指一个函数表达式中包含若干个“和”项，其中每个“和”项可有一个或 多个以原变量或反变量形式出现的字母，这些“和”项的“积”就表示一个函数。例如，一个四 变量函数为 F(A.B.C.D)=(A+B)(C+D)(+B+C) 其中，(A+B)、(C+D)、(不十B十C)均为“和”项，这些“和”项的“积”就构成了函数的“和 之积”形式。 当然，布尔函数还可表示成其他形式。例如，上述四变量函数还可表示成 F(A.B.C.D)=(AC+B)(CD+D)=(AC+B)CD+(AC+B)D 这种表示形式既不是“积之和”形式，又不是“和之积”形式，但它可以转换成后两种形式。 一个函数可以有多种表示形式，那么能不能找到统一的表示形式呢？有两种统一的标 准形式。 3.3.2函数的“标准积之和”与“标准和之积”形式 1,标准积之和 所谓标准积，是指函数的积项包含了函数的全部变量，其中每个变量都以原变量或反变
与求对偶函数一样,求补函数需要注意的是,在运用反演规则时,必须按照先“与”后 “或”的顺序进行变换。因此,特别要注意原来函数中的“与”项,当这些“与”项变换为“或”项 时,应加括号。 把上述补函数的例子与前面对偶函数的例子对照一下,可以看出,补函数和对偶函数之 间在形式上只差变量的“非”。因此,若已求得一函数的对偶函数,只要将所有变量取反便得 该函数的补函数;反之亦然。 3.3 布尔函数的基本形式 一个布尔函数的表达式可以有多种表示形式,本节讨论几种基本形式,它们是进行布尔 函数化简的基础。 3.3.1 函数的“积之和”与“和之积”形式 根据展开定理,任何一个n 变量函数总可以展开成“与-或”形式,或者“或-与”形式。其 中“与-或”形式又称为“积之和”形式,而“或-与”形式又称为“和之积”形式。 所谓“积之和”,是指一个函数表达式中包含若干个“积”项,其中每个“积”项可有一个或 多个以原变量或反变量形式出现的字母,这些“积”项的“和”就表示了一个函数。例如,一个 三变量函数为 F(A,B,C)=A +BC +ABC 其中,A、BC、ABC 均为“积”项。这些积项的和,就表示了函数的“积之和”形式。 所谓“和之积”,是指一个函数表达式中包含若干个“和”项,其中每个“和”项可有一个或 多个以原变量或反变量形式出现的字母,这些“和”项的“积”就表示一个函数。例如,一个四 变量函数为 F(A,B,C,D)=(A +B)(C +D)(A +B +C) 其中,(A+B)、(C+D)、(A+B+C)均为“和”项,这些“和”项的“积”就构成了函数的“和 之积”形式。 当然,布尔函数还可表示成其他形式。例如,上述四变量函数还可表示成 F(A,B,C,D)=(AC +B)(CD +D)=(AC +B)CD + (AC +B)D 这种表示形式既不是“积之和”形式,又不是“和之积”形式,但它可以转换成后两种形式。 一个函数可以有多种表示形式,那么能不能找到统一的表示形式呢? 有两种统一的标 准形式。 3.3.2 函数的“标准积之和”与“标准和之积”形式 1.标准积之和 所谓标准积,是指函数的积项包含了函数的全部变量,其中每个变量都以原变量或反变 第3章 布尔代数基础 53
54 计算机组成原理（第2版） 量的形式出现，且仅出现一次。标准积项通常称为最小项。 一个函数可以用最小项之和的形式来表示，称为函数的“标准积之和”形式。例如，一个 三变量函数为 F(A.B.C)=ABC +ABC+ABC +ABC 它由4个最小项组成，这是函数的“标准积之和”形式。 由最小项的定义可知，3个变量最多可组成8个最小项：万C、AC,ABC、ABC ABC、ABC、ABC、ABC。为了叙述和书写方便，通常用m,表示最小项，其下标i是这样确 定的：把最小项中原变量记为1，反变量记为0，当变量顺序确定后，可以按顺序排列成一个 二进制数。那么，与这个二进制数相对应的十进制数就是最小项的下标i。表3.6列出了3 个变量的全部最小顶和最大顶 表3.6三变量的所有最小项和最大项 A B C 最小项 最大项 000 M=A+B+C 001 m=ABC M,=A+B+C 010 m:-ABC M:=A+B+C 011 m,-有BC M,-A+B+C 100 m=ABC M=A+B+C 101 m:-ABC M.-A+B+C 110 m:-ABG M=A+B+C 111 m;-ABC M;-++C 因此，上述函数F(A,B,C)可以写成 F(A.B.C)-ABC+ABC+ABC+ABC=m:+m+(2.3.4.7) 其中，符号“∑”表示各最小项求“或”，括号内的十进制数字表示各最小项的下标。 最小项有下列3个主要性质。 (1)对于任意一个最小项，只有一组变量取值使其值为1。 (2)任意两个不同的最小项之积必为0，即 m:·m,=0 (i≠) (3)n变量的所有2”个最小项之和必为1，即 m,=1 用展开定理可以证明，任一个变量的函数都有一个且仅有一个最小项表达式，即“标 准积之和“形式。下面介绍求函数的“标准积之和”的两种常用的方法。 方法一：代数演算法，即通过反复使用公式x十一1和x(y十)一xy十x:而求得“标 准积之和”的方法。例如，设F(A,B,C)=万B十AEC+BC,则得 F(A,B.C)=AB(C+C)+ABC+BC(A+A) -ABC+ABC+ABC+ABC+ABC
量的形式出现,且仅出现一次。标准积项通常称为最小项。 一个函数可以用最小项之和的形式来表示,称为函数的“标准积之和”形式。例如,一个 三变量函数为 F(A,B,C)=ABC +ABC +ABC +ABC 它由4个最小项组成,这是函数的“标准积之和”形式。 由最小项的定义可知,3个变量最多可组成8个最小项:ABC、ABC、ABC、ABC、 ABC、ABC、ABC、ABC。为了叙述和书写方便,通常用mi 表示最小项,其下标i是这样确 定的:把最小项中原变量记为1,反变量记为0,当变量顺序确定后,可以按顺序排列成一个 二进制数。那么,与这个二进制数相对应的十进制数就是最小项的下标i。表3.6列出了3 个变量的全部最小项和最大项。 表3.6 三变量的所有最小项和最大项 A B C 最 小 项 最 大 项 0 0 0 m0=ABC M0=A+B+C 0 0 1 m1=ABC M1=A+B+C 0 1 0 m2=ABC M2=A+B+C 0 1 1 m3=ABC M3=A+B+C 1 0 0 m4=ABC M4=A+B+C 1 0 1 m5=ABC M5=A+B+C 1 1 0 m6=ABC M6=A+B+C 1 1 1 m7=ABC M7=A+B+C 因此,上述函数F(A,B,C)可以写成 F(A,B,C)=ABC +ABC +ABC +ABC =m2 +m3 +m4 +m7 =∑m(2,3,4,7) 其中,符号 “∑”表示各最小项求“或”,括号内的十进制数字表示各最小项的下标。 最小项有下列3个主要性质。 (1)对于任意一个最小项,只有一组变量取值使其值为1。 (2)任意两个不同的最小项之积必为0,即 mi·mj =0 (i≠j) (3)n 变量的所有2 n 个最小项之和必为1,即 ∑ 2 n-1 i=0 mi =1 用展开定理可以证明,任一个n 变量的函数都有一个且仅有一个最小项表达式,即“标 准积之和”形式。下面介绍求函数的“标准积之和”的两种常用的方法。 方法一:代数演算法,即通过反复使用公式x+x -=1和x(y+z)=xy+xz 而求得“标 准积之和”的方法。例如,设F(A,B,C)=AB+ABC+BC,则得 F(A,B,C)=AB(C +C)+ABC +BC(A +A) =ABC +ABC +ABC +ABC +ABC 54 计算机组成原理(第2版)