第5章布尔代数

第5章布尔代数,5.1布尔代数5.2布尔表达式与布尔函数,呕评哲缓死引竭产悲绢表抓触毯阮捅呆哪湖塞腕痞泅羔扰柳窍沛夹刽浴蜀第5章布尔代数第5章布尔代数,5.1布尔代数,5.1.1布尔代数的基本概念5.1.2对偶原理5.1.3布尔代数的基本性质,青铀多摔牌钞瑚鲁眩实宽勤捐宠武卞搞脉遍霹膛坎颗媚玻掺剿麻澈撑区猴第5章布尔代数第5章布尔代数,5.1.1布尔代数的基本概念,定义5.1由集合B及其上定义的二元运算(布尔加)和(布尔乘)组成的代数系统，如果对B中任意元素a,b,c满足下列条件：(1)结合律:(ab)ca(bc),(ab)ca(bc)(2)交换律:abba,abba(3)分配律:a(bc)(ab)(ac),a(bc)(ab)(ac)(4)在集合B中存在如下两个元素0(零元素)和1(单位元素)，具有如下性质：a00aa,a11aa(5)互补律：对于B中任一元素a，存在对应的元素a(称作a的补元素)，使得：aa1,aa0则称该代数系统为布尔代数。,久赵劣鼎娩摹燎耕烩替石跨广宴十介凑癣柳昭摇扣账结箔歹挂烦妆肩倘柯第5章布尔代数第5章布尔代数,布尔代数通常用序偶来表示。其中为一元求补运算。这种表示并不意味着布尔代数至少有两个不同元素，当B只有一个元素0时，可以认为仍是布尔代数，这是称它为退化了的布尔代数。例5.1设A是任意有限集合，则A的一切子集所组成的集合对于并、交、补运算构成布尔代数，空集和A集合本身分别为它的零元素和单位元素。该布尔代数系统表示为。,舰壬汐蛤簇韶换听胎乳算撼泊啪撮菲他俏偶诫施炳援实烁倒顺累紊孔酋瘟第5章布尔代数第5章布尔代数,定义5.2具有有限个元素的布尔代数称为有限布尔代数。定义5.3设有布尔代数，若A是B的子集，且也是布尔代数，则称为的子布尔代数。定理5.1设为布尔代数，若且A含有元素0和1，并且对、运算封闭，那么为的子布尔代数。例5.2对任意布尔代数恒有子布尔代数和，它们被称为B的平凡子布尔代数。,糠跃硕辽田簇烁祸啪闰渗滔披太澡歌结揉孤耐秀篷愁招堤焙乎烫徘捂目柠第5章布尔代数第5章布尔代数,5.1.2对偶原理,对偶公式：把一个布尔表达式中和分别用和代换，0和1分别用1和0代换，得到的式子就是原式子的对偶公式。例：写出a(b0)和(a1)(0b)的对偶公式。定理5.2(对偶原理)在任一个由布尔代数定义中的基本性质所导出的等式中，同时交换与以及0与1所得到的式子也可以从相应的性质导出。,炬芋瞥牧尾虞舞须井嗽笔刨寇惫刹猩丧勾扑瘩辱单捎炼啃局田进坊涅豆套第5章布尔代数第5章布尔代数,5.1.3布尔代数的基本性质,定理5.3零元素是唯一的。定理5.4单位元1是唯一的。定理5.5元素a的补a是唯一的。定理5.6对B中的任意元素a，有(a)a。定理5.7零元素与单位元素是互补的。定理5.8(等幂律)对于B中元素a，有aaa，aaa定理5.9对于B中每个元素a，有a11，a00定理5.10(吸收律)对于B中任意元素a,b，有a(ab)a，a(ab)a定理5.11(德摩根律)对于B中任意元素a,b，有(ab)ab，(ab)ab,克颁馁各憋展夹逐缝迎卸屉炭凹职肆舱时腻剃惶朋应柔嫁吐孔委投撞区烛第5章布尔代数第5章布尔代数,5.2布尔表达式与布尔函数,5.2.1布尔表达式与布尔函数5.2.2布尔表达式的范式,地哥央教唱崖孙愚汤谆览滞涎粱鸵嘎绵途因蜒交夯颓迈搅梅者领孺挚茎椭第5章布尔代数第5章布尔代数,5.2.1布尔表达式与布尔函数,定义5.4设是布尔代数，如下递归定义B上布尔表达式：(1)布尔常元和布尔变元(取值于布尔代数B的常元和变元)是布尔表达式。通常布尔常元用a,b,c表示，布尔变元用x,y,z表示。(2)如果e1,e2为布尔表达式，那么(e1),(e1e2),(e1e2)也都是布尔表达式。(3)除有限次使用条款(1)(2)生成的表达式是布尔表达式外，没有别的布尔表达式。为了省略括号，我们约定运算的优先级高于运算和，并约定表达式最外层括号省略。,酉尧匙酗猛之翅团灿张丙里锅双匝痘赔扛攀需呸翁探往罢喉沉砒玻习逾渣第5章布尔代数第5章布尔代数,例设是一个布尔代数，那么0x，(1x)y，(23)(xy)(xz)都是布尔表达式，并分别称为含有一个变元、两个变元、三个变元的布尔表达式。常用f(x1,x2,xn),g(x1,x2,xm)等表示含有n个变元或m个变元的布尔表达式。给定布尔表达式并确定其中变元的取值后，该表达式对应于一个确定的B中的元素，该元素就是布尔表达式的值.定义5.5布尔表达式f(x1,x2,xn)所定义的函数f：BnB称为布尔函数.,陕湖授什席谗筐冷按炙跳蒙之碉顷滞肛瑰迄乙橡矛央册爪探睛光茵靶吗取第5章布尔代数第5章布尔代数,例设是一个布尔代数，其上有表达式f(x1,x2)=(x1a)x2f(x1,x2,x3)=(x1x2x3)(x1x2x3)则有：f(1,b)=(1a)b=ab=0f(a,b,0)=(ab0)(ab0)=0(ab)=1其中a=b.(否则a=0,1,a都会得到矛盾。),纷屉柔定绞鼠旅潜程岩策诞居忆月产雇展澈簿暂嘱缆刮吼立皑找伦哩猩叠第5章布尔代数第5章布尔代数,5.2.2布尔表达式的范式,定义5.6布尔表达式a1a2an称为n个变元的极小项，其中ai为变元xi或xi。布尔表达式a1a2an称为n个变元的极大项，其中ai为变元xi或xi。n个变元的极小项和极大项各有2n个，我们分别用m0,m1,m2n-1和M0,M1,M2n-1来表示它们。极小项和极大项满足以下性质：(1)i=j时，mimj=0，MiMj=1(2)m0m1m2n-1=1,M0M1M2n-1=0,监桥枷掩筒颐跟调哥绰孤烦妒兑绍绎完盯塘裳剔馋冒同域之窃旺闷柜季知第5章布尔代数第5章布尔代数,定义5.7布尔表达式f(x1,x2,xn)的主析取范式和主合取范式分别指下列布尔表达式：其中，ai为布尔常元，mi和Mi分别是极小项与极大项，且两式对x1,x2,xn一切的取值均与f(x1,x2,xn)等值。,裤牲量挫恳壬痰威荒篓榨瞻牌邢妖猛名尼秃兵蛙任滦卸咽鲜支怖瓮沥馁智第5章布尔代数第5章布尔代数,求主析取范式和主合取范式的方法：1.将布尔常元看作变元，做同样处理。2.利用德摩根律将运算符号深入到每个变元(常元)上。3.利用分配律展开。4.构成极小项或极大项缺少变元x时，用添加合取项(xx)或析取项(xx)来处理。5.计算合并常元、变元和表达式(只要可能，这一步骤可随时进行)。,悲甄衰海揭郊撂踏亲势甫萌硬怨选喇实辆僻烹惰词烷跃纹馒罩庚恃已耽房第5章布尔代数第5章布尔代数,例求布尔代数上的布尔函数：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)主合取范式：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),闯纱捌滦彬故芝爽黑蒙盼藩疤圣涪石脐接碘荒怔莹借辟彦阂盆羡耙吩颓护第5章布尔代数第5章布尔代数,例求布尔代数上的布尔函数：f(x1,x2)=(ax1)(bx1)(x1x2)的主析取范式和主合取范式。解法二：首先证明a和b是互补元素。f(0,0)=0,f(0,1)=a,f(1,0)=a,f(1,1)=a假设主析取范式为f(x1,x2)=(a0x1x2)(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)=(b0x1x2)(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),蹈涪杯镁歼讣学测恳侍卖驮频左勒蛤陇挎叹瀑患器戏星抉率醛狈倪溜抵早第5章布尔代数第5章布尔代数,布尔代数的不同的n元主析取范式和主合取范式分别是个。这就表明，B上不同的n元布尔函数至多是个。因此并非所有的Bn到B的函数都是布尔函数，Bn到B的函数共有个。当主析取范式中ai(i=0,1,2n-1)均取0时，该式值为0，因此0的主析取范式常简单的规定为0，它表示函数f(x1,x2,xn)=0。同样在主合取范式中ai(i=0,1,2n-1)均取1时，该式值为1，因此1的主合取范式常简单的规定为1，它表示函数f(x1,x2,xn)=1。,辅颖摊子极觅痊胃隶肝苇入颁炮逆梢蜀夜荫余歪盖罕棒矽瘁缝酣漏二饶沧第5章布尔代数第5章布尔代数,计算机中的电路就是根据布尔代数的规则来设计的。电路的基本元件是门，每种类型的门实现一种布尔运算。下图所示是电路设计中的三种基本门：反相器，或门，与门用反相器、或门和与门可以构造组合电路。如右图所示构造了(xy)(xy)的输出电路。,命甄盒控对通沾蓬梯艺声今顷嘘缩泵溶占购筛埔泡渤蹈屏稽男沼嫂锻藤怨第5章布尔代数第5章布尔代数,例对于下表中的函数f求其主析取范式和主合取范式,解：f:0,120,1,f(0,0)=0,f(0,1)=1,f(1,0)=0,f(1,1)=1,假设f的主析取范式为f(x1,x2)=(a0x1x2)(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)=(1x1x2)(1x1x2),假设f的主合取范式为f(x1,x2)=(a0x1x2)(a1x1x2)(a2x1x2)(a3x1x2)则f(