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版)