离散数学-格与布尔代数.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2026/8/7 周五,Discrete Mathematics,第1页,回头看,R,，,是一个代数系统，,（）,R,，,是一个,Abel,群,（）,R,，,是一个半群,（）,对 满足分配律，即,a,（,b,c,）（,a,b,）（,a,c,）,（,b,c,）,a,（,b,a,）（,a,c,）,整数环、高斯环、模,m,剩下环、,零环,第2页,回头看,有单位元、无零因子交换环称为整环,设,R,是一个有环，,假如,，,是一个群，则称,R,为除环，可交换除环称为域,有限整环必为域,若,p,为素数，则,Z,p,，,p,，,p,为域,第3页,域,F,特征,设,F,，,是一个域，则：,（）在加法群,F,，,中，每个非零元都含有一样周期（阶）,（）假如,F,，,中非零元素周期为有限数,p,，则,p,必为素数,第4页,2026/8/7 周五,Chapter 7,格与布尔代数,Lattices&Boolean Algebra,第5页,输入,A B,输出,S C,0 0,0 0,0 1,1 0,1 0,1 0,1 1,0 1,半加器,half adder,第6页,全加器,Full adder,第7页,全加器,Full adder,Input,A B Cin,Output,S Cout,0 0 0,0 0,0 0 1,1 0,0 1 0,1 0,0 1 1,0 1,1 0 0,1 0,1 0 1,0 1,1 1 0,0 1,1 1 1,1 1,第8页,n,位加法器,n-adder,布尔表示式,布尔代数,Boolean Algebra,第9页,偏序集,Posets,（布尔）代数系统,L,，,，*,格,L,P,，,格与布尔代数,Lattice&Boolean Algebra,第10页,7.1,格,(1),偏序集,Posets,例,1:S,30,=1,2,3,5,6,10,15,30,|=|x,y,S,30,且,x|y,S,6,=1,2,3,6,S,30,S,15,=1,3,5,15,S,30,偏序集,:,第11页,2026/8/7 周五,7.1,格,定义设,L,是一个偏序集，,假如,x,y,L,x,y,必有最小上界和最大下界，则称,L,为格,第12页,2026/8/7 周五,例 集合,S,幂集,P(S),和定义在其上包含关系组成,偏序集,.,对于任意子集,A,B,p(,S),，因为,A,A,B,B,A,B,，,而且若,A,C,B,C,则,A,B,C,。,所以，,A,B,最小上界,A,B=A,B,。,同理,A,B,最大下界,A,*,B=AB,。,于是，,是格,;,(,),。,由集合,S=a,b,c,得到格,Hass,图，以下列图所表示。,7.1,格,第13页,2026/8/7 周五,a,b,c,a,b,b,c,c,a,c,a,b,7.1,格,第14页,2026/8/7 周五,30,6,1,15,5,10,2,3,Example:,7.1,格,第15页,2026/8/7 周五,例,判断图中哈斯图表示偏序集是否组成格,说明为何。,(,b,),(,c,),(,d,),(,e,),a,a,a,a,b,b,b,b,c,c,c,c,d,d,d,d,e,e,e,e,f,(,a,),a,b,c,d,7.1,格,第16页,例,设,Z,+,为正整数集合，对于,a,b,Z,+,，,关系“,”定义为：,ab,当且仅当,a,整除,b,。则偏序集,组成格，,其中,:,a,b,是,a,b,最小公倍数,(,记作,LCM,Least Common Multiple),a,*,b,是,a,b,最大公因数,(,记作,GCD,Greatest Common Divisor),即,a,b=,LCM(,a,b,),，,a,*,b=,GCD(,a,b,),7.1,格,x,yL,x,y,必有最小上界和最大下界,30,6,1,15,5,10,2,3,第17页,并运算与交运算,在格,L,，,中，,a,b,最小上界用,a,b,表示，,a,b,最大下界用,a,*,b,表示,.,a,b,L,，由最小上界、最大下界唯一性，,a,b,，,a,*,b,都在,L,上唯一确定,将,*,视为,L,上两个运算，通常称为,L,，,上并,(Join,),运算与交,(Meet,),运算,第18页,并、交 运算性质,定理设,L,，,是一个格，并运算,与交运算*满足以下性质：,L,1,a,a,a,a,*,a,a,（幂等律）,L,2,a,b,b,a a,*,b,b,*,a,（交换律）,L,3,（,a,b,）,c,a,（,b,c,）,(,a,*,b,)*,c,a,*,（,b,*,c,）,（结合律）,L,4,a,(,a,*,b,),a,a,*,（,a,b,）,a,（吸搜集）,第19页,L,1,：,a,*,a,a,a,a,a,证实,因为,a,a,，故,a,是,a,，,a,下界，又设,c,是,a,，,a,任一下界，则,c,a,，故,a,是,a,，,a,最大下界，即,a,*,a,a,，同理可证,a,a,a,，即,L,1,成立,第20页,L,2,：,a,*,b,b,*,a,，,a,b,b,a,证实,因为,a,，,b,b,，,a,，故,a,*,b,b,*,a,，同理,a,b,b,a,即,L,2,成立,第21页,L,3,：,(,a,*,b,)*,c,a,*,（,b,*,c,）,(,a,*,b,)*,c,a,*,b,a,(,a,*,b,)*,c,a,*,b,b,(,a,*,b,)*,c,c,所以，,(,a,*,b,),*,c,是,b,，,c,下界，从而小于等于其最大下界，即,(,a,*,b,)*,c,b,*,c,(xa,且,xb,则,x,b,c,),所以又知,(,a,*,b,)*,c,是,a,，,b,*,c,下界，从而,(,a,*,b,)*,c,a,*(,b,*,c,),同理,a,*(,b,*,c,)(,a,*,b,)*,c,所以,a,*(,b,*,c,),(,a,*,b,)*,c,第22页,L,4,：,a,*,（,a,b,）,a,因为,a,是,a,，,a,b,下界，,故,a,a,*(,a,b,),，,再由*定义，,a,*(,a,b,),a,，从而,a,*(,a,b,),a,第23页,设,是一个代数系统,和*是,L,上两个二元运算,假如这两个运算满足幂等律（,L,1,）、交换律,(L,2,),、结合律（,L,3,）和吸收律,(L,4,),则称,是一个,格,(Lattice),。,7.1,格,格与代数系统关系,第24页,例,是格,表示为,又可表示为,7.1,格,例,或,第25页,7.2,格,代数系统,格,L,，,中,自然存在,两个运算,和*，从而派生出一个代数系统,L,，,，*,与*满足,L,L,。,反之，若给定一个代数系统,L,，,，*,，其中，运算,与*满足,L,L,，是否一定能找到一个与该代数系统对应格？是，一定能。,第26页,定理设,L,，,是一个格，,则对任意,a,，,b,L,a,b,a,*,b,a,a,b,b,证实：,ab,a*b,a,设,ab,，则,a,是,a,，,b,下界，故,aa*b,，,又,a*ba,，从而,a*b,a,；,反之，设,a*b,a,，则由,a*bb,即知,ab,同理可证,ab,，,a,b,b,a,b,7.2,格,代数系统,第27页,怎样定义偏序？,偏序 必须满足,a,b,a,*,b,a,a,b,b,用,a,b,a,*,b,a,a,b,b,定义偏序,首先要求给定运算,与*满足,a,*,b,a,a,b,b,7.2,格,代数系统,第28页,引理,设,L,，,，*,是一个代数系统，,，*满足,L,L,，则,a,*,b,a,a,b,b,证实设,a,*,b,a,，则,a,b,（,a,*,b,）,b,b,（,b,*,a,）,b,反之，设,a,b,b,则,a,*,b,a,*,（,a,b,）,a,。,7.2,格,代数系统,第29页,引理告诉我们在偏序关系上寻找,*,是可行。,用,a,b,a,*,b,a,（,a,b,b,）,要求关系 是可行,但这么要求关系 是否一定是要求偏序关系呢？,7.2,格,代数系统,第30页,定理,设,L,，,，*,是一个代数系统，运算,与*满足,L,L,令,L,上关系 定义以下：,a,b,a,*,b,a,则 是一个偏序关系，且,a,，,b,L,，,a,*,b,，,a,b,分别为,a,b,在,L,，,中最大下界与最小上界，即,a,*,b,inf,a,，,b,；,a,b,sup,a,，,b,从而,L,，,是一个格，其中并、交运算恰为给定,与*,7.2,格,代数系统,第31页,证实 为偏序关系,(1),自反性,;,a,L,，因为,a,*,a,a,，故,a,a,，即满足自反性；,(2),反对称性,;,a,，,b,L,，设,a,b,，,b,a,，则,a,*,b,a,，,b,*,a,b,，因为,a,*,b,b,*,a,，故,a,b,，即 满足反对称性；,(3),传递性,a,，,b,，,c,L,，设,a,b,，,b,c,，则,a,*,b,a,，,b,*,c,b,，故,a,*,c,（,a,*,b,）*,c,a,*,（,b,*,c,）,a,*,b,a,，即,a,c,，故满足传递性,7.2,格,代数系统,第32页,证,L,，,为要求格,a,，,b,L,，（,a,*,b,）*,a,a,*,（,a,*,b,）（,a,*,a,）*,b,a,*,b,，故,a,*,b,a,，,同理,a,*,b,b,，所以,a,*,b,是,a,，,b,下界，,又设,c,是,a,，,b,任一下界，即,c,a,，,c,b,，则,a,*,c,c,，,b,*,c,c,，于是（,a,*,b,）*,c,a,*,（,b,*,c,）,a,*,c,c,，即,c,a,*,b,，所以,a,*,b,是,a,，,b,最大下界，即,a,*,b,inf,a,，,b,，,同理可证,a,b,sup,a,，,b,，,这就证实了,L,，,是格且其中并、交运算分别为,，*,.,L3,L1,7.2,格,代数系统,第33页,代数格,定义设,L,，,，*,是一个代数系统，假如,，*满足,L,L,，则称,L,，,，*,为格,7.2,格,代数系统,第34页,例,设,N,是自然数集合，对任意,a,，,b,N,，要求,a,b,a,，,b,（即,a,，,b,最小公倍数），,a,*,b,（,a,，,b,）（即,a,，,b,最大公因数），,因为任意两自然数,a,，,b,都有唯一确定最大公因数与最小公倍数，故*，,是,N,上两个运算,L,1,、,L,2,、,L,3,、,L,4,是不是成立？,7.2,格,代数系统,第35页,例设,S,是一个集合，为集合并、交运算，则,P,（,S,），,是格，且其中偏序为集合包含关系,7.2,格,代数系统,第36页,定理设,L,，,是格，,a,，,b,L,，则,（）,a,*,b,a,a,*,b,b,（）,a,a,b,b,a,b,7.2,格,代数系统,第37页,定理设,L,，,是格，,a,，,b,，,c,L,若,c,a,，,c,b,则,c,a,*,b,若,a,c,，,b,c,则,a,b,c,以上两定理由并、交运算定义可得到,7.2,格,代数系统,第38页,定理设,L,，,是一个格，,a,，,a,，,b,，,b,L,，,假如,a,b,，,a,b,，,则,a,*,a,b,*,b,，,a,a,b,b,证实：,a,*,a,a,b,，,a,*,a,a,b,故,(,a,*,a,),b,*,b,又,a,b,b,b,，,a,b,b,b,故,a,a,(,b,b,),7.2,格,代数系统,第39页,推论,设,L,，,是一个格，,a,，,b,，,c,L,，,若,a,b,，则,a,*,c,b,*,c,，,a,c,b,c,7.2,格,代数系统,第40页,定理,设,L,是一个格,，,a,，,b,，,c,L,，则,a,*,（,b,c,）（,a,*,b,）,（,a,*,c,）,a,（,b,*,c,）（,a,b,）*（,a,c,）,b,*,（,c,d,）,b,*,a,b,（,b,*,c,）,（,b,*,d,）,b,e,c*,（,b,d,）,c*a,c,（,c*b,）,（,c*d,）,e,d,d,c,d,7.2,格,代数系统,第41页,证实：,因为,b,b,c,故,a,*,b,a,*,（,b,c,）,-(1),又,c,b,c,故,a,*,c,a,*,（,b,c,）,-(2),所以,（,a,*,b,）,（,a,*,c,）,a,*,（,b,c,）,（依据定理,5,）,即,a,*,（,b,c,）（,a,*,b,）,（,a,*,c,）,同理,a,（,b,*,c,）（,a,b,）*（,a,c,）,7.2,格,代数系统,第42页,2026/8/7 周五,定义,子格,(Sublattice):,设,是一个格,假如,是,子代数,则称,是,子格,Sublattice),。,子格也是一个格,因为当运算,和,*,限制在,S,上时,交换律、结合律和吸收律也是成立。,7.3,子格与格同态,第43页,2026/8/7 周五,不是,子格，这是因为,a,b,d,c,f,e,g,子格,(Sublattice):,例设,是一个格,其中,，以下列图,令,则,和,是,一个子格,第44页,L,，,S,，,S,，,a,，,c,，,S,，,本身是一个格，但它不是,L,，,子格,7.3,子格与格同态,第45页,例,，,，*,对任意,a,，,b,N,，要求,a,*,b,（,a,，,b,）（即,a,，,b,最大公因数），,a,b,a,，,b,令,S,为,N,中全部偶数组成集合,S,是,N,子格,7.3,子格与格同态,第46页,定义,设,L,，,，*,，,L,，,是两个格,f,：,L,L,，假如,a,b,L,，有,f,（,a,b,）,f,（,a,）,f,（,b,）,f,（,a,*,b,）,f,（,a,）,f,（,b,）,则称,f,是格,L,到,L,同态,单、满同态，同构,f,：,L,L,，,f,：,L,L,7.3,子格与格同态,第47页,同态映射一定是,保序映射,。,定理,设,f,是格,L,到,L,同态，,则,f,是偏序集,L,到,L,保序映射，,即,x,，,y,L,，当,x,y,时，,f,（,x,）,f,（,y,）,x,y,x,*,y,x,f(x),*,f(y),f(x,*,y),f(x),f(x),f(y),7.3,子格与格同态,第48页,保序映射未必是同态,f,：,a,|,，,b,|,，,c,|,，,d,|,则,f,是,L,到,L,保序映射，但,f,（,b,*,c,）,f,（,b,）*,f,（,c,）,所以，,f,不是,L,到,L,同态,第49页,定理设,f,是格,L,到,L,双射，则,f,是,L,到,L,同构，当且仅当,a,，,b,L,，,a,b,f,（,a,）,f,（,b,）,7.3,子格与格同态,第50页,证实,（,1,）若,f,（,a,）,f,（,b,），则,a,b,；,若,f,（,a,）,f,（,b,），则,f,（,a,）*,f,（,b,）,f,（,a,），,f,（,a,*,b,）,f,（,a,），故,a,*,b,a,，,a,b,（,2,）,x,，,y,L,x,y,则,x,*,y,x,，,x,*,y,y,，,故,f,（,x,*,y,）,f,（,x,）,，,f,（,x,*,y,）,f,（,y,），,f,（,x,*,y,）,f,（,x,）*,f,（,y,）；,设,f,（,x,）*,f,（,y,）,f,（,z,），,此时必有,，,f,（,z,）,f,（,x,），,f,（,z,）,f,（,y,），,从而,z,x,，,z,y,，,于是,z,x,*,y,，,f,（,z,）,f,（,x,*,y,），,即,f,（,x,）*,f,（,y,）,f,（,x,*,y,）,7.3,子格与格同态,第51页,定义设,L,，,是一个格，假如,L,任意子集都有最小上界和最大下界，则称其为完全格,有限格必为完全格,整数集,Z,在通常数小于等于关系下是一个格，其子集,E,，,既无最小上界也无最大下界,7.4,完全格、有界格、补格,第52页,例,实数闭区间，在通常小于等于关系 下是完全格，实数开区间（，）则不然,例 集合,A,幂集格,P,（,A,），,是完全格,7.4,完全格、有界格、补格,第53页,定义设,L,，,是一个格，假如,L,中存在最大元与最小元，则称,L,是有界格,最大元也称为,全上界,或单位元，用表示；最小元也称为,全下界,或零元，用表示，对应地，有界格也称为有单位元和零元格,有界格,L,*,0,1,完全格必为有界格,.,7.4,完全格、有界格、补格,第54页,例设,A,是集合，,A,幂集格,P,（,A,），,是有界格，其单位元为,A,，零元为,例实数开区间（，）在通常小于等于关系下组成格不是有界格,7.4,完全格、有界格、补格,第55页,定理,设,L,是一个有界格，则对任意,x,L,，有,x,x,，,x,x,*,，,x,*,x,7.4,完全格、有界格、补格,0,1,x,第56页,定义,设,L,是一个有界格，,a,L,，假如存在,b,L,使,a,b,；,a,*,b,则称,b,是,a,补元,7.4,完全格、有界格、补格,第57页,例,P,（,A,），,是,A,幂集格，则对,P,(,A,),中任意元素,S,，,有,A,S,是,S,补元,7.4,完全格、有界格、补格,例,第58页,定理设,L,是有界格，则单位元是零元唯一补元。,7.4,完全格、有界格、补格,0,1,x,第59页,定义设,L,是一个有界格，假如,L,中每个元素都有补元，则称其为,补格,或,有补格,比如：集合,A,幂集格,P,（,A,）是补格,7.4,完全格、有界格、补格,补格,非补格,第60页,完全格、有界格、补格讨论为是元素之间结构关系，并不包括运算之间关系。,7.4,完全格、有界格、补格,定理,设,L,是一个格,，,a,，,b,，,c,L,，则,a,*,（,b,c,）（,a,*,b,）,（,a,*,c,）,a,（,b,*,c,）（,a,b,）*（,a,c,）,a,*,（,b,c,）,=,（,a,*,b,）,（,a,*,c,）,a,（,b,*,c,）,=,（,a,b,）*（,a,c,）,第61页,7.5,分配格与模格,定义设,L,是一个格，假如,L,中并、交运算相互可分配，即对任意,a,，,b,，,c,L,a,*(,b,c,),(,a,*,b,),(,a,*,c),a,(,b,*,c),(,a,b),*,(,a,c),则称,L,是分配格,a,*(,b,c,),a,*1=a,(,a,*,b,),(,a,*,c)=0,a=a,a,(,b,*,c),a,0=a,(,a,b),*,(,a,c)=1,*,a=a,第62页,定理设,L,是一个格，假如,L,中交对并可分配，则并对交必可分配反之亦然,7.5,分配格与模格,证实：,a,*,（,b,c,）（,a,*,b,）,（,a,*,c,）,则,（,a,b,）,*（,a,c,）,（,a,b,）*,a,）,（,a,b,）*,c,）,a,（,a,b,）*,c,）,a,（,（,a,*,c,）,（,b,*,c,）,（,a,（,a,*,c,）,（,b,*,c,）,a,（,b,*,c,）,可分配,吸收率,可分配,结合律,吸收率,第63页,例下列图所表示两个格都不是分配格,7.5,分配格与模格,例集合,A,幂集格,P,（,A,）是分配格,b,*,（,c,d,）,b,*,a,b,（,b,*,c,）,（,b,*,d,）,c*,（,b,d,）,c*a,c,（,c*b,）,（,c*d,）,e,d,d,第64页,定理设,L,，,，*,是一个分配格，,a,，,b,，,c,L,，假如,a,*,b,a,*,c,，,a,b,a,c,则,b,c.,b,b,*,（,b,a,）,b,*,（,a,b,）,b,*,（,a,c,）,（,b,*,a,）,（,b,*,c,）,（,a,*c,）,（,b,*,c,）,（,a,b,）*,c,（,a,c,）*,c,c,证实：,7.5,分配格与模格,交换律,吸收率,代入,分配律,代入,分配律,代入,吸收率,第65页,推论设,L,，,，*,是一个分配格，,a,L,，,a,补元若存在则是唯一,证实设,a,，,a,都是,a,补元，则由补元定义，有,a,*,a,a,*,a,a,a,a,a,由定理,2,可得。,a,a,7.5,分配格与模格,第66页,例,a,*,b,a,*,c,d,a,b,a,c,但,b,c,7.5,分配格与模格,b*,（,a,c,）,b*1,b,（,b*a,）,（,b*c,）,d,c,c,不是分配格。,第67页,定义设,L,，,，*,是一个格，,假如 当,a,b,时必有,L,a,*,（,b,c,）,b,（,a,*,c,）,（模律）,则称,L,为模格 （或,Demekind,格）,7.5,分配格与模格,第68页,定理分配格必是模格,7.5,分配格与模格,证实设,L,，,，*,是一分配格，,a,，,b,，,c,L,若,a,b,，则,a,*,b,b,，从而,a,*(,b,c),=(,a,*,b,),(,a,*,c),=,b,(,a,*,c),所以,L,是模格,第69页,定理,L,是模格当且仅当,由,a,b,，,a,*,c,b,*,c,，,a,c,b,c,，,可推出,a,b,7.5,分配格与模格,证实,:,L,，,，*,是模格，,a,b,，,a,*,c,b,*,c,，,a,c,b,c,则,a,a,*,（,a,c,）,a,*,（,b,c,）,b,（,a,*,c,）,b,（,b,*,c,）,b,（模律）当,a,b,时必有,L,5,a,*,（,b,c,）,=,b,（,a,*,c,）,代入,吸收,吸收,模律,代入,第70页,证实,:,设,a,b,，则,b,（,a,*,c,）,a,（,a,*,c,）,a,所以（,b,（,a,*,c,）*,c,a,*,c,又（,b,（,a,*,c,）,）*,c,（,a,*,c,）*,c,a,*,c,故,（,b,（,a*c,）*,c,a,*,c,另首先,（,a*,（,b,c,）*,c,a,*,（,b,c,）*,c,）,a,*,c,所以 （,a,*,（,b,c,）*,c,（,b,（,a,*,c,）*,c,（）,同理 （,a,*,（,b,c,）,c,（,b,（,a,*,c,）,c,（）,又因为,a,b,，,a,a,*,c ,故,a,b,（,a,*,c,）,又,b,c,b,（,a,*,c,）,所以,a,*,（,b,c,）,b,（,a,*,c,）,注意（），（）及定理条件便知,a,*,（,b,c,）,b,（,a,*,c,）,7.5,分配格与模格,第71页,例 在有界分配格中，全部有补元组成集合为一个子格。,7.5,分配格与模格,第72页,2026/8/7 周五,7.6,布尔代数,布尔格,-,有补分配格,Boolean lattice,定义,:,有补分配格中每元补元唯一,从而可定义一个“取补”一元运算,.,所以,此种格是一个有两个二元运算,一个一元运算和常数,0,1,代数,L,*,0,1,称为,布尔代数,.(比如,幂集,格,(S),S,是布尔代数,.),第73页,2026/8/7 周五,定义,1:布尔代数是,有补分配格,.,7.6,布尔代数,定义,2(公理化定义):有两个二元运算代数,B,*,称为布尔代数,假如对任意元素,a,b,c,B,成立:,第74页,2026/8/7 周五,(,交换律,)a*b=b*a,a,b=b,a;,(,分配律,)a*(b,c)=(a*b),(a*c),a,(b*c)=(a,b)*(a,c);,(,有界,)存在0,1,B,使得,a*1=a,a,0=a,a,B;,(,有补,)B,每一元,a,都有,(,唯一,)a,S,使得,a*a,=0,a,a,=1.,7.6,布尔代数,第75页,2026/8/7 周五,比如,:,1,幂集代数,:,(S),S,;,2,命题代数,:,B,F,T,;,7.6,布尔代数,第76页,2026/8/7 周五,例题：设集合,L=1,，,2,，,5,，,10,，,11,，,22,，,55,，,110,，,是,110,正因子集合，,是整除关系，偏序集,是否组成布尔代数，为何？,7.6,布尔代数,第77页,2026/8/7 周五,布尔表示式,定义：,假设,B,是一个布尔代数，,x,1,x,2,x,n,是,B,上变量，,B,上由,x,1,x,2,x,n,生成布尔表示式归纳定义以下：,(1)B,中元素是,B,上由,x,1,x,2,x,n,生成布尔表示式；,(2)B,上任意变量,x,i,（,i=1,2,n,）,是,B,上由,x,1,x,2,x,n,生成布尔表示式；,(3),假如,，,是,B,上由,x,1,x,2,x,n,生成布尔表示式，则,，,*,，,（,补元）是,B,上由,x,1,x,2,x,n,生成布尔表示式；,(4),只有经过有限次使用,(1),(2),(3),得到符号串是,B,上由,x,1,x,2,x,n,生成布尔表示式。,7.6,布尔代数,第78页,2026/8/7 周五,布尔表示式,例：,假设,B=0,1,是由图,示确定一个布尔代数，,x,y,是,B,上变量。若,B,上布尔表示,式为：,7.6,布尔代数,第79页,2026/8/7 周五,设,B=0,1,，,B,n,=(x,1,x,2,x,n,)|x,i,B,其中,1,i,n,是,n,元有序对集合。函数,f:B,n,B,为布尔函数。,7.6,布尔代数,布尔函数,第80页,2026/8/7 周五,比如：计算由下式表示布尔函数值,。,x,y,x,x,y,x+y,(x+y),y,x,y,f(x,y),0,0,1,0,0,1,1,0,0,0,1,1,1,1,0,0,0,1,1,0,0,0,1,0,1,1,1,1,1,0,0,1,0,0,0,0,7.6,布尔代数,布尔函数,第81页,2026/8/7 周五,例：,假设函数,f(x,y,z),和函数,g(x,y,z),定义,如表所表示。,x,y,z,f(x,y,z),g(x,y,z),0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,0,1,1,0,0,1,1,1,1,0,0,7.6,布尔代数,第82页,2026/8/7 周五,门电路,(1)AND,门,7.6,布尔代数,第83页,2026/8/7 周五,(1)AND,门,7.6,布尔代数,第84页,2026/8/7 周五,(2)OR,门,7.6,布尔代数,第85页,2026/8/7 周五,(3)NOT,门,7.6,布尔代数,第86页,2026/8/7 周五,组合门,7.6,布尔代数,第87页,?,2,b,第88页,