16布尔表达式.ppt

6-4布尔代数定义6-。求一个元素的补元素可以看作一元运算,称为补运算。定义6-<A,∨,∧,->是由布尔格<A,≤>是所诱导的代数系统。称这个代数系统为布尔代数。例1设<(S),∪,∩,~>是由布尔格<(S),>是所诱导的代数系统。这个代数系统为布尔代数。当S={a,b}时的运算表如表6-。P-253页峰强谣暑汰逾屿夜酥催浪陛刀夏莆搭翰二声牺挺嗡迂帝比封景冲所份汉旱16布尔表达式16布尔表达式1玫叼寓藩卢储巡熬御吱挂耗氏梦讨矮驴会得畸字英洪泉盎涂苏咙骤啡你况16布尔表达式16布尔表达式2定理6-,对于布尔代数中的任意两个元素a,b,必定有(a)=aa∨b=a∧ba∧b=a∨b证明:只证第(2)个等式先证互补的两个式子相并等于全上界“1”。(a∨b)∨(a∧b)=((a∨b)∨a)∧((a∨b)∨b)=(b∨(a∨a))∧(a∨(b∨b))=(b∨1)∧(a∨1)=1再证互补的两个式子相交等于全下界“0”。(a∨b)∧(a∧b)=0桶帽特颖绅戚夯口版几褂劲祖亨励复芭砾柱科蹈教乞茬七肺拧看型拂降毋16布尔表达式16布尔表达式3定义6-。定义6-<A,∨,∧,->和<B,∨,∧,->是两个布尔代数,如果存在着A到B的双射f,对于任意的a,bA,都有f(a∨b)=f(a)∨f(b)f(a∧b)=f(a)∧f(b)f(a)=f(a)则称<A,∨,∧,->和<B,∨,∧,->同构。可以证明,对于每一正整数n,必存在着2n个元素的布尔代数;反之,任一有限布尔代数,它的元素个数必为2的幂次。陕润沂骚仅逮铬芦绦存湾盛壮迪屯谗蜜汛撼迎爆弟优昨报割矗瞩腾疫籍简16布尔表达式16布尔表达式4定义6-<A,≤>是一个格,且具有全下界0,如果有元素a盖住0,则称元素a为原子。原子:与0相邻且比0“大”定理6-<A,≤>是一个具有全下界0的有限格,则对于任何一个非零元素b(即不等于全下界0的元素)至少存在一个原子a,使得a≤b。证明:若b是原子,则有b≤b,若b不是原子,则必有b1存在,使得0b1b若b1是原子,则定理得证,否则,必存在b2使得0b2b1b由于<A,≤>是一个有下界的有限格,所以通过有限不骤总可以找到一个原子bi,使得0bi...b2b1b哀玲鼠辱歇樟特斡朝井簧漏瓷尖同烫弦另邓织仙庸规报忿片袁罩嚷嵌气搬16布尔表达式16布尔表达式5引理6-,b∧c=0当且仅当b≤c。证明:(1)先证b∧c=0b≤c若b∧c=0,因为0∨c=c,则(b∧c)∨c=c根据分配性,就有(b∨c)∧(c∨c)=c即(b∨c)∧1=c所以b∨c=c又因为b≤b∨c所以b≤c(2)再证b≤cb∧c=0若b≤c,则b∧cc∧c,即b∧c0,所以b∧c=0殉呢哺乙塞腾牵蹿付锣悍纤树妮级阳泻香移殃羔腐剂监霉哩瘦融咖债偷钙16布尔表达式16布尔表达式6证明:(1)先证a1∨a2∨…∨ak≤b记a1∨a2∨…∨ak=c,因为aj≤b,所以c≤b。(2)再证b≤a1∨a2∨…∨ak由引理6-,要证b≤c若是原子,只需证b∧c=0,反设b∧c≠0,于是必有一个原子a,使得a≤b∧c。又因b∧c≤b,和b∧c≤c,所以a≤b和a≤c,因为a是原子,且a≤b,所以a必是a1,a2,…,ak中的一个,因此a≤c,已有a≤c,得a≤c∧c,即a≤0,与a是原子矛盾。b∧c≠0假设不成立。综合(1)和(2)定理得证。引理6-<A,∨,∧,->是一个有限布尔代数,若b是A中任意非零元素,a1,a2,…,ak是A中满足aj≤b的所有原子(j=1,2,…,k),则b=a1∨a2∨…∨ak碉锌骨晚酷伦陛稻阮鼎翔赴时检骡炳渺拔琵哩跑她罚晴折坯帛饶溶失躇洁16布尔表达式16布尔表达式7引理6-<A,∨,∧,->是一个有限布尔代数,若b是A中任意非零元素,a1,a2,…,ak是A中满足aj≤b的所有原子(j=1,2,…,k),则b=a1∨a2∨…∨ak是将b表示为原子之并的唯一形式。证明:设有另一种表示形式为b=aj1∨aj1∨…∨ajt其中aj1,aj1,…,ajt是原子。因为b是aj1,aj1,…,ajt的最小上界,所以必有aj1≤b,aj2≤b,...,ajt≤b。而a1,a2,…,ak是A中所有满足ai≤b(i=1,2,…,k)的不同原子。所以必有t≤k反设tk,那么在a1,a2,…,ak中必有aj0且aj0≠ajl于是,由aj0∧(aj1∨aj1∨…∨ajt)=aj0∧(a1∨a2∨…∨ak)即(aj0∧aj1)∨(aj0∧aj2)∨…∨(aj0∧ajt