第5章布尔代数.ppt

《第5章布尔代数.ppt》由会员分享，可在线阅读，更多相关《第5章布尔代数.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5 5章章 布尔代数布尔代数5.1 5.1 布尔代数布尔代数5.2 5.2 布尔表达式与布尔函数布尔表达式与布尔函数5.1 5.1 布尔代数布尔代数5.1.1 5.1.1 布尔代数的基本概念布尔代数的基本概念5.1.2 5.1.2 对偶原理对偶原理5.1.3 5.1.3 布尔代数的基本性质布尔代数的基本性质5.1.1 5.1.1 布尔代数的基本概念布尔代数的基本概念定义定义5.15.1 由集合由集合B B及其上定义的二元运算及其上定义的二元运算(布尔加布尔加)和和(布尔乘布尔乘)组成的代数系统，如果对组成的代数系统，如果对B B中任意元素中任意元素a,b,ca,b,c满足满足下列条件：下列

2、条件：(1)(1)结合律结合律:(ab)cab)ca(bca(bc),(),(ab)cab)ca(bca(bc)(2)(2)交换律交换律:ababbaba,ababbaba(3)(3)分配律分配律:a(bca(bc)(ab)(acab)(ac),),a(bca(bc)(ab)(acab)(ac)(4)(4)在集合在集合B B中存在如下两个元素中存在如下两个元素0(0(零元素零元素)和和1(1(单位元素单位元素)，具有如下性质：，具有如下性质：a0a00a0aa,a1a,a11a1aa a(5)(5)互补律：对于互补律：对于B B中任一元素中任一元素a a，存在对应的元素，存在对应的元素a(a(

3、称称作作a a的的补元素补元素)，使得：，使得：aaaa1,1,aaaa0 0 则称该代数系统为则称该代数系统为布尔代数布尔代数。布尔代数通常用序偶布尔代数通常用序偶来表示。来表示。其中其中为一元为一元求补运算求补运算。这种表示并不意味着布尔代数至少有两个不同元这种表示并不意味着布尔代数至少有两个不同元素，当素，当B B只有一个元素只有一个元素0 0时，可以认为时，可以认为仍是布尔代数，这是称它为仍是布尔代数，这是称它为退退化了的布尔代数化了的布尔代数。例例5.15.1 设设A A是任意有限集合，则是任意有限集合，则A A的一切子集所组的一切子集所组成的集合对于并、交、补运算构成布尔代数，空成

4、的集合对于并、交、补运算构成布尔代数，空集和集和A A集合本身分别为它的零元素和单位元素。该集合本身分别为它的零元素和单位元素。该布尔代数系统表示为布尔代数系统表示为P(A),。定义定义5.25.2 具有有限个元素的布尔代数称为具有有限个元素的布尔代数称为有限布尔有限布尔代数代数。定义定义5.35.3 设有布尔代数设有布尔代数，若，若A A是是B B的子集，且的子集，且也是布尔代数，则称也是布尔代数，则称为为的的子布尔代子布尔代数数。定理定理5.15.1 设设为布尔代数，若且为布尔代数，若且A A含含有元素有元素0 0和和1 1，并且对，并且对、运算封闭，那么运算封闭，那么为为的子布尔代的子布

5、尔代数。数。例例5.25.2 对任意布尔代数对任意布尔代数恒有子布恒有子布尔代数尔代数和和，它们被称为，它们被称为B B的的平凡子布尔代数平凡子布尔代数。5.1.2 5.1.2 对偶原理对偶原理对偶公式：对偶公式：把一个布尔表达式中把一个布尔表达式中和和分分别用别用和和代换，代换，0 0和和1 1分别用分别用1 1和和0 0代换，代换，得到的式子就是原式子的对偶公式。得到的式子就是原式子的对偶公式。例：例：写出写出 a(b0)a(b0)和和(a1)(0b)(a1)(0b)的对偶公式。的对偶公式。定理定理5.2(5.2(对偶原理对偶原理)在任一个由布尔代数定在任一个由布尔代数定义中的基本性质所导

6、出的等式中，同时交义中的基本性质所导出的等式中，同时交换换与与以及以及0 0与与1 1所得到的式子也可以从所得到的式子也可以从相应的性质导出。相应的性质导出。5.1.3 5.1.3 布尔代数的基本性质布尔代数的基本性质定理定理5.35.3 零元素是唯一的。零元素是唯一的。定理定理5.45.4 单位元单位元1 1是唯一的。是唯一的。定理定理5.55.5 元素元素a a的补的补aa是唯一的。是唯一的。定理定理5.65.6 对对B B中的任意元素中的任意元素a a，有，有(a)(a)a a。定理定理5.75.7 零元素与单位元素是互补的。零元素与单位元素是互补的。定理定理5.85.8(等幂律等幂律)

7、对于对于B B中元素中元素a a，有，有 aaaaa a，aaaaa a定理定理5.95.9 对于对于B B中每个元素中每个元素a a，有，有 a1a11 1，a0a00 0定理定理5.105.10(吸收律吸收律)对于对于B B中任意元素中任意元素a,ba,b，有，有 a(aba(ab)a a，a(aba(ab)a a定理定理5.115.11(德德摩根律摩根律)对于对于B B中任意元素中任意元素a,ba,b，有，有 (abab)abab，(abab)abab5.2 5.2 布尔表达式与布尔函数布尔表达式与布尔函数5.2.1 5.2.1 布尔表达式与布尔函数布尔表达式与布尔函数5.2.2 5.2

8、.2 布尔表达式的范式布尔表达式的范式5.2.1 5.2.1 布尔表达式与布尔函数布尔表达式与布尔函数定义定义5.45.4 设设是布尔代数，如下是布尔代数，如下递归定义递归定义B B上上布尔表达式布尔表达式：(1)(1)布尔常元和布尔变元布尔常元和布尔变元(取值于布尔代数取值于布尔代数B B的常元的常元和变元和变元)是布尔表达式。通常布尔常元用是布尔表达式。通常布尔常元用a,b,ca,b,c表表示，布尔变元用示，布尔变元用x,y,zx,y,z表示。表示。(2)(2)如果如果e1,e2e1,e2为布尔表达式，那么为布尔表达式，那么(e1),(e1),(e1e2),(e1e2)e1e2),(e1e

9、2)也都是布尔表达式。也都是布尔表达式。(3)(3)除有限次使用条款除有限次使用条款(1)(2)(1)(2)生成的表达式是布尔生成的表达式是布尔表达式外，没有别的布尔表达式。表达式外，没有别的布尔表达式。为了省略括号，我们约定运算为了省略括号，我们约定运算的优先级高于运的优先级高于运算算和和，并约定表达式最外层括号省略。，并约定表达式最外层括号省略。例例 设设是一个布尔代数，是一个布尔代数，那么那么0 x0 x，(1x)y(1x)y，(23)(xy)(xz)(23)(xy)(xz)都是布尔表达式，都是布尔表达式，并分别称为含有一个变元、两个变元、三个变元并分别称为含有一个变元、两个变元、三个变

10、元的布尔表达式。的布尔表达式。常用常用f(xf(x1 1,x,x2 2,x xn n),g(x),g(x1 1,x,x2 2,x xm m)等表示等表示含有含有n n个变元或个变元或m m个变元的布尔表达式。个变元的布尔表达式。给定布尔表达式并确定其中变元的取值后，该表给定布尔表达式并确定其中变元的取值后，该表达式对应于一个确定的达式对应于一个确定的B B中的元素，该元素就是中的元素，该元素就是布布尔表达式的值尔表达式的值.定义定义5.55.5 布尔表达式布尔表达式f(xf(x1 1,x,x2 2,x xn n)所定义的函所定义的函数数f f：B Bn nB B 称为称为布尔函数布尔函数.例例

11、 设设是一个布是一个布尔代数，其上有表达式尔代数，其上有表达式 f(xf(x1 1,x,x2 2)=(x)=(x1 1a)xa)x2 2f(xf(x1 1,x,x2 2,x,x3 3)=(x =(x1 1xx2 2xx3 3)(x)(x1 1xx2 2 xx3 3)则有：则有：f(1,b)=(1a)b=f(1,b)=(1a)b=abab=0=0f(af(a,b,0)=(ab0)(ab 0),b,0)=(ab0)(ab 0)=0(ab)=1 =0(ab)=1 其中其中a=b.(a=b.(否则否则a=0,1,aa=0,1,a都会得到矛盾。都会得到矛盾。)5.2.2 5.2.2 布尔表达式的范式布尔

12、表达式的范式定义定义5.65.6 布尔表达式布尔表达式 a a1 1aa2 2aan n 称为称为n n个变元个变元的的极小项极小项，其中，其中a ai i为变元为变元x xi i或或x xi i。布尔表达式布尔表达式 a a1 1aa2 2aan n 称为称为n n个变元的个变元的极大项极大项，其中，其中a ai i为为变元变元x xi i或或x xi i。n n个变元的极小项和极大项各有个变元的极小项和极大项各有2 2n n个，我们分别用个，我们分别用 m m0 0,m,m1 1,m,m2 2n n-1-1和和M M0 0,M,M1 1,M,M2 2n n-1-1 来表示它们。来表示它们。

13、极小项和极大项满足以下性质：极小项和极大项满足以下性质：(1)i=j(1)i=j时，时，m mi immj j =0=0，M Mi iMMj j =1=1 (2)m (2)m0 0mm1 1mm2 2n n-1-1=1,M=1,M0 0MM1 1MM2 2n n-1-1=0=0定义定义5.75.7 布尔表达式布尔表达式f(xf(x1 1,x,x2 2,x xn n)的的主主析取范式析取范式和和主合取范式主合取范式分别指下列布尔表分别指下列布尔表达式：达式：其中，其中，a ai i为布尔常元，为布尔常元，m mi i和和M Mi i分别是极小项分别是极小项与极大项，且两式对与极大项，且两式对x

14、x1 1,x,x2 2,x xn n一切的一切的取值均与取值均与f(xf(x1 1,x,x2 2,x xn n)等值。等值。求主析取范式和主合取范式的方法：求主析取范式和主合取范式的方法：1.1.将布尔常元看作变元，做同样处理。将布尔常元看作变元，做同样处理。2.2.利用德摩根律将运算符号利用德摩根律将运算符号深入到每个变深入到每个变元元(常元常元)上。上。3.3.利用分配律展开。利用分配律展开。4.4.构成极小项或极大项缺少变元构成极小项或极大项缺少变元x x时，用添加时，用添加合取项合取项(xxxx)或析取项或析取项(xxxx)来处理。来处理。5.5.计算合并常元、变元和表达式计算合并常元

15、、变元和表达式(只要可能，只要可能，这一步骤可随时进行这一步骤可随时进行)。例例 求布尔代数求布尔代数上的布尔函数：上的布尔函数：f(x1,x2)=(ax1)(bx1)(x1x2)的主析取范式和主合取范式。的主析取范式和主合取范式。解法一解法一：首先证明：首先证明 a和和b是互补元素。是互补元素。主析取范式主析取范式:f(x1,x2)=(ax1)(bx1)(x1x2)=(ax1)(x1x2)(ax1)(x1x2)=(ax1)(ax1x2)(ax1x1)(ax1x2)=(ax1)(ax1x2)=(ax1)(x2x2)(ax1x2)=(ax1x2)(ax1x2)(ax1x2)主合取范式：主合取范式

16、：f(x1,x2)=(ax1)(bx1)(x1x2)=(ax1)a)(ax1)x1)(x1x2)=a(ax1)(ax1)(x1x2)=a(x1x2)=(ax1x2)(ax1x2)(ax1x2)(ax1x2)(x1x2)=(x1x2)(ax1x2)(ax1x2)(ax1x2)例例 求布尔代数求布尔代数上的布尔函数：上的布尔函数：f(x1,x2)=(ax1)(bx1)(x1x2)的主析取范式和主合取范式。的主析取范式和主合取范式。解法二解法二：首先证明：首先证明 a和和b是互补元素。是互补元素。f(0,0)=0,f(0,1)=a,f(1,0)=a,f(1,1)=a 假设主析取范式为假设主析取范式为

17、f(x1,x2)=(a0 x1x2)(a1x1x2)(a2x1x2)(a3x1x2)则则f(0,0)=a3=0,f(0,1)=a2=a,f(1,0)=a1=a,f(1,1)=a0=a，所以主析取范式为所以主析取范式为f(x1,x2)=(ax1x2)(ax1x2)(ax1x2)。假设主合取范式为假设主合取范式为f(x1,x2)=(b0 x1x2)(b1x1x2)(b2x1x2)(b3x1x2)则则f(0,0)=b0=0,f(0,1)=b1=a,f(1,0)=b2=a,f(1,1)=b3=a，所以主合取范式为所以主合取范式为f(x1,x2)=(x1x2)(ax1x2)(ax1x2)(ax1x2)布

18、尔代数布尔代数的不同的的不同的n n元主析取元主析取范式和主合取范式分别是范式和主合取范式分别是 个。这就表明，个。这就表明，B B上不同的上不同的n n元布尔函数至多是元布尔函数至多是 个。个。因此并非所有的因此并非所有的B Bn n到到B B的函数都是布尔函数，的函数都是布尔函数，B Bn n到到B B的函数共有个的函数共有个 。当主析取范式中当主析取范式中a ai i(i(i=0,1,2=0,1,2n n-1)-1)均取均取0 0时，该时，该式值为式值为0 0，因此，因此0 0的主析取范式常简单的规定为的主析取范式常简单的规定为0 0，它表示函数，它表示函数f(xf(x1 1,x,x2

19、2,x xn n)=0)=0。同样在主合取范式中同样在主合取范式中a ai i(i(i=0,1,2=0,1,2n n-1)-1)均取均取1 1时，时，该式值为该式值为1 1，因此，因此1 1的主合取范式常简单的规定的主合取范式常简单的规定为为1 1，它表示函数，它表示函数f(xf(x1 1,x,x2 2,x xn n)=1)=1。计算机中的电路就是根据布尔代数的规则来设计计算机中的电路就是根据布尔代数的规则来设计的。电路的基本元件是门，每种类型的门实现一的。电路的基本元件是门，每种类型的门实现一种布尔运算。下图所示是电路设计中的三种基本种布尔运算。下图所示是电路设计中的三种基本门：反相器门：反

20、相器，或门，与门或门，与门用反相器、或门和与门用反相器、或门和与门可以构造组合电路。如右可以构造组合电路。如右图所示构造了图所示构造了(xy)(xyxy)(xy)的输出电路。的输出电路。x xxx反相器反相器x xy yx xy y或门或门x xy yx xy y与门与门(xy)(xy)xy yxxxxy yxy yx xy y例例 对于下表中的函数对于下表中的函数f f求其主析取范式和主合取范式求其主析取范式和主合取范式f0101解解：f:0,12 0,1f(0,0)=0,f(0,1)=1,f(1,0)=0,f(1,1)=1 假设假设f的主析取范式为的主析取范式为f(x1,x2)=(a0 x

21、1 x2)(a1x1x2)(a2x1x2)(a3x1x2)则则f(0,0)=a3=0,f(0,1)=a1=1,f(1,0)=a2=0,f(1,1)=a0=1从而从而 主析取范式为主析取范式为 f(x1,x2)=(1x1 x2)(1x1x2)假设假设f的主合取范式为的主合取范式为f(x1,x2)=(a0 x1x2)(a1x1x2)(a2x1x2)(a3x1x2)则则f(0,0)=a0=0,f(0,1)=a2=1,f(1,0)=a1=0,f(1,1)=a3=1从而从而 主合取范式为主合取范式为 f(x1,x2)=(1x1x2)(1x1x2)第第5 5章章 复习复习布尔代数的基本概念布尔代数的基本概念对偶公式和对偶原理对偶公式和对偶原理布尔代数的基本性质布尔代数的基本性质布尔表达式、布尔函数及其范式的求法布尔表达式、布尔函数及其范式的求法