离散数学格与布尔代数

第七章格与布尔代数布尔代数是计算机逻辑设计的基础，它是由格引出的，格又是从偏序集引出的。所以我们先回顾一下偏序集。<A,≤>是偏序集:≤是A上自反,反对称和传递关系(偏序).偏序集中的元素间的次序可以通过它的Hasse图反映出来.例如A={1,2,3,6,12,24,36},≤是A上的整除关系其Hasse图如图所示，BAB≠Φ1.B的极小元与极大元y是B的极小元y∈B∧x(x∈B∧x≤y)y是B的极大元y∈B∧x(x∈B∧y≤x)例如{2,3,6}的极小元:2,3极大元:6６。１。３。12。２。24。36。2.B的最小元与最大元y是B的最小元y∈B∧x(x∈By≤x)y是B的最大元y∈B∧x(x∈Bx≤y){2,3,6}的最小元:无最大元:6B如果有最小元(最大元),则是唯一的。3.B的下界与上界y是B的下界y∈A∧x(x∈By≤x)y是B的上界y∈A∧x(x∈Bx≤y){2,3,6}的下界:1上界:6,12,24,364.B的最大下界(下确界)与最小上界(上确界)y是B的最大下界(下确界)：B的所有下界x,有x≤y。y是B的最小上界(上确界)：B的所有上界x,有y≤x。{2,3,6}下确界:1上确界:6(B若有下(上)确界，则唯一)６。１。３。12。２。24。36。7-1格(Lattice)一.基本概念1.格的定义<A,≤>是偏序集，如果任何a,b∈A,使得{a,b}都有最大下界和最小上界，则称<A,≤>是格。

右图的三个偏序集，<A,≤>不是格，因为{24,36}无最小上界。<B,≤><C,≤>是格。６。１。３。12。２。24。36。30。3。１。2。5。10。１5。6。<A,≤><B,≤>3。4。1。2。<C,≤>这三个偏序集，也都不是格，第一个与第三个是同构的。因为d和e无下界，也无最小上界；b,c虽有下界，但无最大下界。2,3无最大下界，4,5无最小上界。2.平凡格：所有全序都是格，称之为平凡格。因为全序中任何两个元素x,y，要么x≤y,要么y≤x。如果x≤y，则{x,y}的最大下界为x，最小上界为y。如果y≤x，则{x,y}的最大下界为y，最小上界为x。即这{x,y}的最大下界为较小元素，最小上界为较大元素.dabce123456dabce3.由格诱导的代数系统设<A,≤>是格,在A上定义二元运算∨和∧为:a,b∈Aa∨b=LUB{a,b}{a,b}的最小上界.LeastUpperBounda∧b=GLB{a,b}{a,b}的最大下界.GreatestLowerBound称<A,∨,∧>是由格<A,≤>诱导的代数系统.(∨-并,∧-交)例如右边的格中a∧b=ba∨b=ab∧c=e4.子格：设<A,≤>是格,<A,∨,∧>是由<A,≤>诱导的代数系统。B是A的非空子集，如果∧和∨在B上封闭，则称<B,≤>是<A,≤>的子格。<C,≤>是<A,≤>的子格。而<B,≤>不是.b∧c=dB,(运算规则要从格<A,≤>中找)

eabdcbacfe

gbacfe

gd<B,≤><A,≤>acbd<C,≤>二.格的对偶原理设<A,≤>是格，≤的逆关系记作≥，≥也是偏序关系。<A,≥>也是格，<A,≥>的Hasse图是将<A,≤>的Hasse图颠倒180º即可。

格的对偶原理：设P是对任何格都为真的命题，如果将P中的≤换成≥，∧换成∨，∨换成∧，就得到命题P’,

称P’为P的对偶命题，则P’对任何格也是为真的命题。例如：P:a∧b≤aP’:a∨b≥a{a,b}的最大下界≤a{a,b}的最小上界≥a三.格的性质

<A,∨,∧>是由格<A,≤>诱导的代数系统。a,b,c,d∈A1.a≤a∨bb≤a∨ba∧b≤aa∧b≤b

此性质由运算∨和∧的定义直接得证。

2.如果a≤b，c≤d，则a∨c≤b∨d，a∧c≤b∧d。证明：如果a≤b，又b≤b∨d，由传递性得a≤b∨d,

类似由c≤d，d≤b∨d，由传递性得c≤b∨d,这说明b∨d是{a,c}的一个上界，而a∨c是{a,c}的最小上界，所以a∨c≤b∨d。类似可证a∧c≤b∧d。推论：在一个格中，任意a,b,c∈A，如果b≤c，则a∨b≤a∨c，a∧b≤a∧c。

此性质称为格的保序性。3.∨和∧都满足交换律。即a∨b=b∨a，a∧b=b∧a此性质由运算∨和∧的定义直接得证。4.∨和∧都满足幂等律。即a∨a=aa∧a=a证明：由性质1,a≤a∨a

(再证a∨a≤a)又由≤自反有a≤a，这说明a是a的上界，而a∨a是a的最小上界，所以a∨a≤a。

最后由≤反对称得a∨a=a。

由对偶原理得a∧a=a5.∨和∧都满足结合律。即(a∨b)∨c=a∨(b∨c)，(a∧b)∧c=a∧(b∧c)

证明：⑴先证明(a∨b)∨c≤a∨(b∨c)

因a≤a∨(b∨c)，b≤b∨c≤a∨(b∨c)所以a∨b≤a∨(b∨c)又c≤b∨c≤a∨(b∨c)于是有(a∨b)∨c≤a∨(b∨c)

⑵再证a∨(b∨c)≤(a∨b)∨c

因a≤a∨b≤(a∨b)∨c；

再由b≤a∨b≤(a∨b)∨c，c≤(a∨b)∨c所以b∨c≤(a∨b)∨c于是有a∨(b∨c)≤(a∨b)∨c最后由≤反对称得

(a∨b)∨c=a∨(b∨c)

类似可证(a∧b)∧c=a∧(b∧c)。6.

∨和∧都满足吸收律。即a∨(a∧b)=a，a∧(a∨b)=a。证明：⑴显然有a≤a∨(a∧b)⑵再证a∨(a∧b)≤a因a≤a，a∧b≤a所以a∨(a∧b)≤a最后由≤反对称得a∨(a∧b)=a，类似可证a∧(a∨b)=a。7.

∨和∧不满足分配律。但有分配不等式：

a∨(b∧c)≤(a∨b)∧(a∨c)，(a∧b)∨(a∧c)≤a∧(b∨c)。我们先看右图的例子：d∨(b∧e)=d∨c=d(d∨b)∧(d∨e)=a∧e=e而d≤e即d∨(b∧e)≤(d∨b)∧(d∨e)证明：⑴因a≤a∨b，a≤a∨c所以a≤(a∨b)∧(a∨c)

又因b∧c≤b≤a∨b，b∧c≤c≤a∨c所以b∧c≤(a∨b)∧(a∨c)

于是有a∨(b∧c)≤(a∨b)∧(a∨c)。由对偶原理得a∧(b∨c)≥(a∧b)∨(a∧c)。

即(a∧b)∨(a∧c)≤a∧(b∨c)。cabed8.a≤ba∨b=ba∧b=a证明：⑴先证明a≤ba∧b=a

先证a≤ba∧b=a由a≤b，又a≤a所以a≤a∧b又由a∧b的定义有a∧b≤a由反对称得a∧b=a

再证a∧b=a

a≤b由a∧b=a则a=a∧b≤b。

综上得a≤ba∨b=b⑵下面证明a≤ba∨b=b

先证a≤ba∨b=b由a≤b，又b≤b所以a∨b≤b又因为b≤a∨b由反对称得a∨b=b

再证a∨b=b

a≤b由a∨b=b因a≤a∨b所以a≤b。

综上得a≤ba∨b=b引理：<A,∨,∧>是代数系统，如果∨和∧是满足吸收律的二元运算，则∨和∧必满足幂等律。证明：任取a,b∈A因为∨和∧满足吸收律。于是有a∨(a∧b)=a------⑴a∧(a∨b)=a-------⑵。由于上式中的b是任意的，可以令b=a∨b并代入⑴式得a∨(a∧(a∨b))=a由⑵式得a∨a=a同理可证a∧a=a定理：设<A,∨,∧>是代数系统，如果∨和∧是满足交换律，结合律，和吸收律的二元运算，则A上存在偏序关系≼

，使<A,≼>是一个格，并且该格所诱导的代数系统恰好是<A,∨,∧>。（由代数系统得到格）证明：设在A上定义二元关系≼为：对任意a,b∈A,a≼b当且仅当a∧b=a（1）先证二元关系≼是一个偏序关系（2）再证a∧b是{a,b}的下确界（3）然后证a∨b是{a,b}的上确界见书上238页四.格的同态与同构1.定义：设<A1,≤1>和<A2,≤2>是两个格，由它们诱导的代数系统分别是<A1,∨1,∧1>和<A2,∨2,∧2>，如果存在映射f:A1A2

，使得对任何a,b∈A1，有

f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2f(b)则称f是<A1,∨1,∧1>到<A2,∨2,∧2>的同态映射。也称<f(A1),≤2>是<A1,≤1>的同态像。如果f是双射的，就称f是<A1,∨1,∧1>到<A2,∨2,∧2>，的格同构，也称格<A1,≤1>和<A2,≤2>同构。例：<A抄,≤玻>，A=妈{1梨,2赚,3傅,6且},汁≤是A上整完除关约系。<P遥(E龟),月>，E=追{a异,b锁}它们暂诱导笋的代底数系挥统分感别是<A支,∨,∧汗>和<P氧(E缸),语∪,姿∩>其中∨和∧分别是求膀两个腰数的捕最小玩公倍刊数和肌最大预公约提数.f(底2∨3)嘉=f薄(6当)=破{a途,b够}缠f(墨2)学∪f橡(3仆)=孤{a朗}∪饶{b胜}=剧{a瓦,b展}f(慈2∧很3)临=f练(1押)=甜Φ谦f(席2)岭∩f堤(3廉)=组{a栽}∩龄{b浇}=尸Φf(才2∨6)签=f残(6免)=出{a咸,b枝}券f(佳2)漆∪f基(6寇)=却{a壁}∪茄{a蒙,b丹}=慢{a趋,b腿}f(烦2∧拉6)塔=f灾(2僻)=俗{a路}野f路(2功)∪旧f(均6)书={抗a}冤∪{裤a,役b}畏={济a}……可见晨它们含同构普。格同矮构，芽它们傲的哈轰斯图绢的形逼状一挤定相五同。Φ{b}{a}{a,b}1326f6321{a}{b}{a,b}ΦAP(E)具有1、2、3个元林素的踩格分案别同略构于弯含有遮一、别二、矛三宣个元腊素的坛链。具有4个元芝素的仪格分满别同价构于服下面搜两种游格形冬式之份一：具有5个素健的格量分别牛同构逗于下罗面五屋种格魄形式邮之一既：edabcda

bccdda

bcea

bcea

bdaeb

cddabceaababc2.格同校态的堤保序伸性定理哥：设f是格<A1,≤1>到<A2,≤2>的同态映射视，则扎对任何a,灾b∈A1，如果a≤1b，则f(长a)沿≤2f(脊b)。证明社：令<A1,∨1,∧1>和<A2,∨2,∧2>是格<A1,≤1>和<A2,≤2>诱导验的代架数系到统，恒任取a,致b∈A1，设a≤1b，则a∧1b=鲜a牵f拦(a从∧1b)煮=f辩(a蜡)即f(葡a)劫∧2f(尝b)沫=f合(a屑)而f(诉a)过∧2f(滋b)分≤2f(低b)所以f(得a)依≤2f(直b)屿.3.格同站构的段保序羊性定理谣：设贞两个格为<A1,≤1>和<A2,≤2>，f是A1到A2的双员射，则f是<A1,≤1>到<A2,≤2>的格喝同构喇，当柿且仅疮当对任谷意a,张b∈A1，a≤1b漏纠f州(a个)≤2f(锄b)证明：令<A1,∨1,∧1>和<A2,∨2,∧2>是格<A1,≤1>和<A2,≤2>诱导弊的代僻数系县统，1)必要弟性：已牢知f是格<A1,≤1>到<A2,≤2>的同构映射幅，（往卫证：技任取a,机b∈A1,往a≤1b断李f富(a壳)≤2f(哈b)）a)先证a≤1b穿络f辅(a现)≤2f(顷b)任取a,柴b∈A1,设a≤1b，由格陪同态屿保序全性得f(漆a)眯≤2f(主b)b)再证f犯(a柏)≤2f(医b)a≤1b设f(控a)寺≤2f(伞b)，于是呼有f(跃a)不=娃f(踩a)往∧2f(肾b)咱=f(美a∧1b)因f是双汁射，蒜所以a=租a∧1b所以a≤1b最后偷得a≤1b鼓结f扑(a倾)≤2f(把b)。2)充分姐性：已度知，忠对任碑意a,那b∈A1,怠a护≤1bf军(a帐)≤2f(捐b)(往证f(柔a∧1b)失=f选(a碧)∧2f(晒b)特f竭(a震∨1b)卵=f隔(a宫)∨2f(茂b)贺)a)证f(掏a∧1b)船=f版(a尖)∧2f(挨b)令a∧1b=舰c所以c≤1a耕c≤1b，由已护知得f(锯c)湿≤2f(庭a)和f(僚c)雁≤2f(敞b)，瓣所削以f(蜘c)柔≤2f(万a)彻∧2f(然b)--拔--德--遵-⑴再证f(艇a)戚∧2f(严b)衫≤2f(啊c)：由于f(对a)眼,f侄(b踢)∈A2,又∧2封闭，得f(桃a)键∧2f(字b)∈A2,又由f:努A1A2是双苏射，拒必有d∈A1,使得f(闸a)膝∧2f(搜b)惩=f验(d戴)所以f(弊d)吃≤2f(降a)，f(虏d)层≤2f(拳b)由已锄知得饥：d≤1a，d≤1b，于哀是d≤1a∧1b=但c，即d≤1c，于敏是f(陈d)注≤2f(卷c)即f(驳a)云∧2f(懒b)捎≤2f(傍c)--刮--仪-⑵由⑴⑵得f(隔a)为∧2f(辰b)叨=f陷(c全)，即f(句a∧1b)熟=f岗(a棒)∧2f(凭b)。b)类似束可证f(遥a∨1b)睡=f顷(a顶)∨2f(办b)，所违以f是它恼们的誓同构夏映射。7-更2几个木特殊馒格一.分配酷格前面胁我们摸介绍级一般梯的格迟，∧和∨只满你足分肿配不劫等式订。a∨细(b葬∧c鸡)≤(a拦∨b馒)∧惑(a接∨c装)，(a诸∧b遭)∨姥(a割∧c湖)≤a∧(b∨c)。下面盆介绍村的是菠满足蛙分配液律的疲格--姓--分配纺格。1.定义：<A,∨,∧>是由摧格<A,≤>诱导锋的代榜数系债统。轿如果对a,裳b,岂c∈A，有a∨悉(b飘∧c瓣)=(a剃∨b感)∧金(a听∨c亲)，a∧(b∨c)牧=消(a体∧b畅)∨剂(a预∧c渴)则称<A,≤>是分配夜格。例：<P纤(E车),>所诱菠导的定代数由系统呈为<P晶(E筝),富∪,到∩>所以<P管(E傻),>是分配巷格。2.二个韵重要贞的五革元素止非分课配格：2∧红(3∨5)较=2∧3最0=膏2(2∧3)∨(2∧5)退=1∨1=延1c∧(b∨d)槐=c∧a=烛c(c∧b)∨(c∧d)日=e∨d=残d可见琴它们随都不瞎是分轨配格陈。3.分配后格的翅判定：一个义格是蚀分配扁格的充分伴且必融要条银件是在非该格洽中没搜有任梨何子格堪与上帖述两廉个五浊元素熔非分如配格持之一塘同构国。用此问方法六可以轨判定派下面遮两个罢格不贡是分泻配格徐：3130

25dea

bc416

352fga

dc

e

b4.分配肯格的描性质1.在一鞭个格脚中，镇如果∧对∨可分魄配，怀则∨对∧也可分配下。反卷之亦劲然。证明：设<A,∨,∧>是由忍格<A,≤>诱导鼓的代除数系锐统，且∧对∨可分牲配。咽则任镇取a,春b,汇c∈A，(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弄)即∨乒对∧皱也可溜分配同理醋可证:如果∨对∧可分绿配，算则∧对∨也可谈分配.2.所有原链均柄为分配友格。证明：显疯然任利何链都不归会含创有与那两劫个五制元素窄非分葬配格之一维同构徒的子沃格，博所以恢链必欠是分安配格猛。3.设<A,≤>是分删配格喇，对猫任何a,中b,背c∈A，如勇果有a∧b=厦a∧种c及a∨汗b=啦a∨c则必指有b=怠c。证明：任弱取a,驴b,铅c∈A用,设有a∧b=扣a∧两c及a∨狐b=鸣a∨cb=恰b∨(阻a∧b)荐(吸收债律)=b∨(竭a∧c)元(代换)=(b∨a拼)∧(b∨c墙)酷(分配膨)=(a单∨b)∧(b∨c厉)测(交换)=(a蝴∨c)∧(b∨c回)帮(代换)=(a∧b)∨抱c绪(分配掩)=(a∧c)融∨c(代换)=c(吸收新律)二.有界托格1.格的较全上缓界与怠全下泽界1)红.全搂上界鱼:设<A,≤>是格允，如伟果存葡在元宏素a∈A对任雹何x∈俘A,x≤a，则遵称a是格的曲全上沾界，记作痰1。(即县是A的最努大元厉)定理7-窄2.偿4讽一醉个格涂如果黄有全迟上界宽，则奴是唯专一的蓄。(我絮们已疮证明孤过，洞最大缓元如员果有贤，则衫是唯异一的蛾)2)果.全眠下界词:设<A,≤>是格念，如低果存昌在元寒素a∈A对任论何x∈类A,育a≤x扣,则称a是格的商全下惯界,搂记作拐0。(即勒是A的最确小元涝)定理7-商2.蜻5尝一灶个格侧如果遵有全葡下界旋，则味是唯显一的迁。从格纵的图旦形看请：全载上界争1，项就是剑图的床最上海边元作素(靠只一太个)剥，全下年界0听，就尚是图捡的最深下边淋元素质(只奔一个过)。b01

ac1c02.有界役格定锐义：如潜果一科个格喜存在全上荷界1新与全强下界梅0，遣则称此陷格为京有界贫格。设<A,≤>是有界格，乞则对着任何a∈A睁,有因为a≤1暂,所以a∧1欢=a称a∨1霜=10≤a所以a∧0铃=0秆a∨0糕=a是否余所有与格都稠是有界叹格？所有然有限狐个元头素的峰格都劈燕是有税界格争，而无趁限个读元素震的格抱可能盼是无毙界格照。例刘如<I,≤>就既亭无全邻上界也无全下蓬界。三.有补管格回顾合：集辱合的偷补集凯，若A∪B=袄E肾A∩B=附Φ则~A禽=B，~B阿=A如E=饭{a柴,b爸}害~E修=Φ集~迎Φ=漫E~{龙a}垫={还b}科,后~弓{b哀}=浩{a放}1.元素转的补松元：设<A安,≤>是个咱有界树格，a∈匀A,如果殿存在b∈龄A，使得a∨乔b=机1且a∧挠b=扬0，则称a与b互为根补元旦。例：门右边贝的格哭中a的补粗元：c,牢eb的补寄元：无c的补落元：a,蹲dd的补贡元：c荐e的补平元：a0的补把元：仍1蚁1规的补欺元：辛0Φ{a,b}

{a}{b}e01

bc

d

a2.有补衣格的晕定义：一个臣有界殿格中凳，如火果每沃个元榆素都霉有补束元，叹则称没之为膜有补格随。上述铅有界礼格中放，哪民些是吸有补健格？上述反有补句格中旬，有舍些元遥素的谷补元奇不唯桂一，创如(2歼)中的b，那么什谊么样援的有膝补格哗元素书的补缓元唯滥一呢役？有界崖分配鼓格。请看痕下面请定理渔：Φ{a,b}

{a}{b}b01

ace01

bc

d

a1c0(1)(2)(3)(4)定理7－2.摩6在有诞界分似配格教中，厉如果桌元素纸有补知元，惊则补驾元是唯叮一的孔。证明托：设<A杂,≤>是有界反分配主格，疑任取a∈剧A，假设a有两揭个补元b和c，则a∧b熄=0幻玉a∨b省=1倡a∧c杆=0糠a∨c刊=1于是代有a∧b粉=a∧c及a∨b竭=a∨c由分捏配格盟的性坝质3得b=想c，所具以a的补元张是唯漏一的译。四.布尔厌格如果润一个枣格既橡是分姿配格盯又是邻有补正格，睬则称朽之为煌布尔酸格。布尔撒格中箭每个彼元素姿都有乔唯一交补元缺，元永素a的补猎元记臣作。显然<P税(E予),>是布纲尔格自。下面雅介绍何由布小尔格时诱导吼的代叮数系确统－衣－布否尔代溪数。7－3布尔晶代数Bo仰ol陡ea每n贱Al呢ge哑br肠a一.定义由布价尔格<B坚,职≤>诱导尸的代固数系已统<B缝,∨,∧,¯>称之说为布宪尔代俊数。颈其中¯是取尚补元廊运算赔。如果A是有甜限集经合，治则称宫它是祝有限拜布尔碌代数绕。例如：令B＝{F恒,T凳}，∧表示场合取螺，∨怎表示剑析取斩，表显示否定殿，<B露,∨,∧,>就是肚个由右居面格妻所诱效导的布尔抚代数颜。E=市{a,可b},<P畜(E阶),∪,∩,~茅>也是奋个由右蕉面格芬所诱与导的布尔纱代数明。TFΦ{a,b}

{a}{b}二.布尔类代数浩的性若质设<B颂,∨,∧,¯>布尔押代数,任意x,漂y,蕉z∈述B,有⑴交兴换律x∨按y=状y∨悠xx∧y水=y袋∧x⑵结合失律x∨(y∨条z)剃=(棒x∨陈y)环∨zx∧(晴y∧伏z)题=(x∧y烫)∧辆z⑶幂等耕律x∨映x=降xx∧x增=x⑷吸收核律x∨(x∧辞y)窝=xx∨(批x∧叼y)堪=x⑸分配使律x∨(y∧越z)辨=(域x∨撕y)害∧(撑x∨焦z)x∧(观y∨修z)族=(x∧y喂)∨录(x辨∧z)⑹同一倦律x∨走0=翅xx∧1旷=x⑺零律x∨通1=谁1x∧0谋=0⑻互补浇律x∨棋=家1x∧抹=0⑼对合哗律⑽底乏－摩歇根定梦律上述长性质缠都可饰以由万格，荷分配格，寻有界绣格，粪布尔渐格得岔到。梦下面仇只证件明底－穗摩根胃定律心。所以。类惭似可羽证另瞎一个。三.布尔漏代数梁的同早构1.定义：令<B1,∨1,哪∧1,¯>和<B2,∨2,灰∧2,盏~>是两斥个布谊尔代腊数，抵如果攀存在厅映射f:刷B1B2，对任抵何a,谅b∈B1，有f(禁a∨1b)康=自f马(a听)∨2f(梅b)f(平a∧1b)需=掌f炉(a竹)∧2f(监b)f(杯)秀=则称f是<A1,∨1,∧1>到<A2,∨2,∧2>的同马态映逢射。与格教同构奴比较众，多喉了一啄个关碧于补铜运算恋的同秆构关嫂系等式。为了纺引出偏有限坛布尔据代数啄的st映on晌e的定铁理，永下面前介绍职原子探的概烫念。~f(a)2.原子定义1:设设<B桥,∨,∧,¯>布尔日代数,元素a∈淋B,a≠0,对任步何元陪素x∈廊B,有x∧a=此a,或x∧a=些0,则称a是原嘉子。定义匆2:<A,≤>是布秀尔格绝,在春<A,≤>的哈斯配图中忌称盖篮住全羊下界膛0的晒元素窃为原秤子。例如骄：1。e。0。d。f。b。c。a。0。1。01a

b下面妖先介宏绍原候子的念判定定理7-华3.河1设<B汽,∨,骨∧,¯>是布拼尔代臣数，a∈亩B,且a≠0喜,则a是原跑子的估充分课且必袄要条碗件是圣对尿任何y∈五B，如果y≤a岸,则y=淘0或y=县a。证明:必要织性.设a是原壳子,衡且假对任驴何y∈水B，有y≤a(往证y=邻0或y=再a)沸,由原简子定闻义得y∧a=成a,或y∧a=端0,而由y≤a得y∧a=急y,所以给有y=脱0或y=橡a.充分进性.已知对任雕何y∈恶B，如果y≤a毅,则y=纲0或y=驳a。(往证a是原迟子,锅即捡证出援对任牛何x∈B有x∧a=牧a,或x∧a=0砖),任取x∈B些,令y=x∧a弊,因x∧a≤雷a,所以y≤a农,由已描知条件得y=铲0或y=御a腹,所以念有x∧a=团a,或x∧a=宋0,所以a是原子.定理7-膛3.至2设a,妹b是布戚尔代青数<B誉,∨,益∧,¯>中的屿原子，如湿果a≠b,则a∧b=缺0,霞(如果a∧b≠0,则a=狡b)即奋不同够两个赚原子返的下饰确界字为0证明:设a和b是B中原音子,(由惊原子少定义锻得:暗对任系何x∈B有x∧a=改a,或x∧a=肯0,晚)因为a是原董子,岭而b∈B日,所以b∧a=南a∧b=尘a,或b∧a=填a∧b=捕0,于是:如果a∧b≠0,必有a∧b=关a.类似凑地,b是原道子,鸽而a∈B旱,所以a∧b=示b,或a∧b=飘0,于是:如果a∧b≠0,必有a∧b=可b,最后滤得a=币b.所以员得出,如果a∧b≠0,则a=杨b.等价句的如果a≠b,则a∧b=屯0鞭.定理7-客3.胃3设a,我b1,b2…bn是滤布尔织代数<B足,∨,菜∧,¯>中的志原子，则a≤幅b1∨b2∨…∨bn的充分漂且必银要条浑件为卖对炕于某榆个i(1≤i京≤n),有a=禽bi.证明:充分记性显然谋成立,因为对于师某个i(历1≤i承≤n),有a=零bi.必有a≤冒b1∨b2∨…∨bn必要待性,已知a≤垂b1∨b2∨…∨bn,则a∧(b1∨b2∨…∨bn)=懒a(a∧b1)∨(a∧b2)∨…∨(a∧bn)=企a如果仙每个(a∧bi)=达0重(饲1≤淹i≤绞n)则(a∧b1)∨(a∧b2)∨…∨(a∧bn)=债0这与a是原栋子矛底盾.所以运至少锐有某个i闭(桶1≤i贫≤n),使得(a∧bi)≠顶0因为a和bi都是躁原子紫,切由定贵理7苦-3.2弱得a=瘦bi.定理7-赏3.卖4设b是有妙限布碧尔代爬数<B途,∨,毙∧,¯>中的仔非0元素慢，则必盾存在蓝原子a，使得a≤付b.证明:1)碑.如果b是原店子,册则宽令b=椒a尾,则a≤步b.2)坐.如果b不是磨原子灿,窑则必休存在b1∈B使得你0<b1<b芽,如果b1不是敏原子疗,听则必锤存在b2∈B使得饲0舞<b2<b1<b食,如此壮下去寨,峡由于B是有醋限集武合,承上设述过它程经芝过有薪限步丹后而最终坊结束篮,狂最后存得到捡原子bk,使得0<bk<…b2<b1<b令bk=a漫,于是a≤盼b.1。e。0。d。f。b。c。a。定理7-羡3.软5有限更布尔忽代数贝中，b∧狮=需0，当且捐仅当b≤c。例如持右图斧中,2走∧索=秒0竿2≤6证明:充分谱性.已航知b≤c又定于叠是因为0是全下下界,所以b∧羞=扫0必要纳性.已知b∧臭=寄0(往证b≤c,即b∨欢c=揉c)b∨锣c=运(b少∨c涉)∧杨1=份(b刑∨c沈)∧猴(堵c∨防)=荐(b∧)∨身c独=0疼∨c依=c所以b∨滑c=塑c,即b≤c30。3。1。2。5。10。15。6。定理7-条3.未6设<B孝,∨,玻∧,¯>是有掠限布医尔代运数，b非0元素穷，a1,a2…ak是B中满善足aj≤b的所社有原匆子(j=叉1,哲2,寄…k见),则b＝a1∨a2∨…∨ak且除松原子蓝次序充不同赶外，上述没表达械式是崖唯一伙的。证明:(迹1)爱令a1∨a2∨…∨ak＝c园(往证b=绍c即证b≤拆c且c≤豪b)a)嚼.证c≤贪b显然高成立,因为芽每个ai≤b,伶(耐j=骡1,么2,喊…k衡)所以a1∨a2∨…∨ak≤b即c≤灰b宇.b)棕.证b≤界c.(由定午理7骑-3.5遵可知造,抗只要服证出b∧搁=枪0即可柴)假设b∧守≠赤0,由定雪理7-常3.努4得,必存佣在原市子a,使得a≤b∧录,而b∧宵≤bb∧木≤由≤的传梢递性辫得a≤雄b,灶a底≤秩.因为a是原仅子,辅且a≤龟b,滔b晨≠0叮,由题顾意a必是a1,a2,…嗓,ak中之拿一,于是a≤饶a1∨a2∨…∨ak即a≤附c,又a≤织,得a≤须c∧所以a≤泻0，这与a是原桥子矛俗盾.所以惩只有b∧堪=俘0，所以b≤c。本综上b=享ca1a2bak...0即得b＝a1∨a2∨…∨ak……泥.①(2铲)证明灯上式锦是唯晚一的.假设帝还有锹原子b1,b2,…皇,bm∈B,使得b＝b1∨b2∨…∨bm……似.②(下面腰证{b1,b2,…速,bm}=谊{a1,a2,.火..腥,ak})a)时.任取bi∈{状b1,b2,…甜,bm}尾,由②式得{b1,b2,…茧,bm}中每中个bj≤b(1先≤j良≤m白)芒,又b＝a1∨a2∨…∨ak所以bi≤b即bi≤a1∨a2∨…∨ak,由于bi及每集个aj(1膛≤j跪≤k朽)都是令原子协,定由定琴理7驻-3作.3幼得,{a1,a2,.岔..屯,ak}中必内存在率一个aj,使得bi=aj于是bi∈{画a1,a2,…砌,ak}所以{b1,b2,…暮,bm}{a1,a2,.泼..乌,ak}类似默可以返证明{a1,a2,.桶..您,ak}{b1,b2,…毁,bm}最后衫得{b1,b2,…爸,bm}={a1,a2,.安..澡,ak}所以仔上述棉表达同式在抄不考女虑原勾子次池序时,形式狠是唯牙一的.定理7-位3.缺7在布武尔代承数<B孟,∨,幸∧,¯>中，对B中任缺何原门子a和任辩何非蓝0元挥素b,民a哀≤b和a≤两式掩中有广且仅乏有一珠个成何立。证明:假浸设上狂述两料个式迅子都随成立替,宽即a≤将b和a≤贴,则有a≤轻b∧篮=0洞,这与a是原减子矛抵盾.下面搞证明得两个罢式中廊必有待一个承成立述.因为a∧醉b≤肤a翠,而a是原控子,斤所翻以只表能有a∧b=猫a或a∧b=黑0如果a∧b=瞎0,即乓,炼由定课理7氏-3水.5甩得,a≤,如果a∧b=别a,则a≤织b.于是裂这两个脉式中街必有滤一个懂成立着.定理7-纯3.旧8卵(S饮to架ne定理除)设<B蜜,∨,纤∧,¯>是有恒限布肚尔代吗数，M是B中所响有原何子构嫩成的龙集合援，则<B欣,∨,坊∧,¯>与<P老(M寺),∪,∩,坡~>同构仗。证明:构般造映袋射f:揭BP际(M追)对于x∈B先通格过下矛边例彼子了绕解映氧射f的形绕式:f(x)={Φx=0{a|a∈M,a≤x}x≠030。3。1。2。5。10。15。6。12356101530Φ{2}{3}{5}{2,3}{2,5}{3,5}{2,3,5}BP(M)f1)叹.先董证明f是双击射.a)挡.证明f是入负射:生只铃有x=广0时,换才今有f(粒x)狸=Φ.任取x1,展x2∈B朵,x1≠0x1≠0且x1≠x2,由定晃理3堤-7彩.6黑得,x1,疗x2可以债写成业如下敢形式赖:x1=父a1∨a2∨…∨ak其中ai≤川x1(1≤祝i≤k)x2=卡b1∨b2∨…∨bm其中bj≤左x2(1≤j甘≤m)因为烧每个菌非0腊元素弱写成卸上述嚷表达历式的训形式症是唯垦一的辟,碗又因为x1≠x2,所以{a1,a2,.围..矿,ak}≠{b1,b2,…兆,bm}.由f定义穗得f(x1)={a1,a2,.机..个,ak}鸟f(x2)=好{b1,b2,…剧,bm}故f(x1)≠f(x2)听f入射忍.b)地.证明f满射纽奉:浇任取M1∈P线(M迅)如果M1为Φ,则f(栋0)江=M1,如果M1≠Φ,令M1={a1,a2,.障..棍,ak}们,由∨的封蚁闭性否得,必存千在x∈辛B踏,使得a1∨a2∨…∨ak=x速,显然掉每个ai≤x(1≤i甩≤k),故f(损x)偶=M1,所以f是满薪射的载.最后挽由a)山b)得f是双乘射的赚.2)畜.证明f满足检三个搁同构坏关系释式.任取x1,帮x2∈B雪,因为f是双牲射,亲必桂有M1,稼M2∈P编(M蒙),使得f(炮x1)=M1,报f(悔x2)=奏M2,a)采.证明f(绢x1∧x2)=遮f(马x1)∩壁f(订x2)=M1∩M2,令f(的x1∧x2)=M3,即证肥明M3=M1∩M2先证M3M1∩M2如果M3=Φ显然恩有M3M1∩M2如果M3≠Φ,任取a∈枪M3,由f定义攻得a≤x1∧x2,又因们为x1∧x2≤x1,x1∧x2≤x2,所以a≤x1a≤x2由f定义薪得a∈广f(仪x1)鸡a∈极f(摩x2)即a∈M1a∈使M2,故a∈M1∩M2,所以M3M1∩M2再证M1∩M2M3如果M1∩M2=Φ显然各有M1∩M2M3如果M1∩M2≠Φ,任取a∈M1∩M2a∈M1a∈乳M2所以a是满暖足a≤x1与a≤x2的原混子,a≤x1∧x2由f定义投得,a∈f(挺x1∧x2),即a∈M3所以M1∩M2M3所以M3=M1∩M2即f(井x1∧x2)=模f(乘x1)∩秃f(棵x2)b)这.证明f(极x1∨x2)=蚀f(仔x1)∪娇f(近x2)=M1∪M2,令f(筑x1∨x2)=M4,即证铅明M4=M1∪M2先证M4M1∪M2如果M4=Φ显然莫有M4M1∪M2如果M4≠Φ,任取a∈牢M4,由f定义懂得a≤x1∨x2,则必站有a≤x1,或者a≤x2,(因为隶如果a≤x1与a≤x2都不堂成立,由定志理7-些3.篇7得轿必有与a是原笔子矛稼盾,葵所午以a≤x1或a≤x2)由f定义钻得a∈寻f(源x1)即a∈M1或a∈阿f(构x2)即a∈跟M2所以a∈M1∪M2,所以M4M1∪M2再证M1∪M2M4如果M1∪M2=Φ显然配有M1∪M2M4如果M1∪M2≠Φ,任取a∈M1∪M2a∈M1或者a∈笋M2如果a∈M1则a≤x1a≤x1≤x1∨x2∴a∈f(切x1∨x2),僚a蒜∈M4如果a∈M2则a≤x2a≤x2≤x1∨x2∴a∈f(岭x1∨x2),检a寒∈M4所以M1∪M2M4M4=M1∪M2与a≤x2的原巡寿子,刺由f定义集得,即所以M1∩M2M4所以M4=M1∩M2即f(占x1∨x2)=五f(宣x1)∪摸f(卧x2)3)由.证明于是避有x1∨x2=1x1∧x2=0f(x1∨x2)=冲M暑f忆(x1∧x2)=砖Φf(x1∨x2)=工f(x1)∪f(x2)=谊M1∪M2=Mf(x1∧x2)=戴f(x1)∩f(x2)=手M1∩M2=Φ所以M2=~耐M1即由1乘).侄2)刑.3之)得f(护x1∧x2)=易f(申x1)∩顿f(塌x2)f(x1∨x2)=扛f(x1)∪f(x2)所以<B烦,∨,反∧,¯>与<P晕(M状),∪,∩,逮~>同构狭。推论剧1.捉任何支有限糟布尔贤代数丢的元灰素个己数为偏2n(n健=1摔,2鉴,3裙,…本)因为救|P(主M)窗|=丸2n推论百2.争两个羡有限丘布尔燥代数乔同构奶的充易分且料必要享条件团是其元素译个数际相同产。1。e。0。d。f。b。c。a。0。1。01a

b本节伶重点态掌握布尔记代数劫的性肢质，独同构打概念呆，St给on当e定理盏及其推漫论。作业P2啊60（2）Φ{c}{b}{d}{a}{a,c,d}{a,b,d}{b,c,d}{a,b,c}{b,c}{a,d}{b,d}{a,c}{a,b,c,d}{c,d}{a,b}7-焰4.布尔途表达娃式一.纷布湖尔表排达式戏概念1.尊定义：设<B浪,∨,借∧,¯>是布倦尔代吹数，著其上杨的布件尔表弹达式递归港定义哗如下勒：1)B中任呀何元筐素是安个布歉尔表丈达式城。2)任何难变元x是个耀布尔搭表达出式。3)如果E1,E2是个起布尔授表达康式,踩则,(E1∧E2),帆(绣E1∨E2)也是布皱尔表泼达式谊。4)有限连次地希应用浊规则服1)2)3)蒜得到似的符己号串跨都是孟布尔籍表达衔式。例如寄令B=粗{0械,1凳,a锦,b予}指(抛a∨),敢(储(x∧y)∨),*表达咬式的块最外督层括言号可语以省迎略.E1¯b¯(x1∨)———2.对布该尔表趣达式黄赋值：设<B汽,∨,萌∧,¯>是布乡丰尔代姥数，惯含有变元x1,x2…xn的布楼尔表迎达式疼记作E(是x1,x2,…xn),对变谱元x1,x2,…域,xn分别默用B中元岩素代筑替的强过程开，称受之为望对布叙尔表达式面赋值尖。例如B=绢{0跪,1划,a拥,b雕}E(挪x1,x2)=E(裹a,岸b)梯=倚=因=串=家b一个的布冤尔表绩达式E(率x1,x2,…xn),经过利赋值环以后奸，就吸得到一个决值(即是B中一高个元浩素)。3.两个币布尔辨表达跌式相忠等:设<B涂,∨,篇∧,¯>是布跳尔代乒数，体含有变元x1,x2,…xn的两灾个布泉尔表锡达式E1(x1,x2,…xn)和E2(x1,x2,…xn),如果董不论余对变案元x1,x2…xn分别誉用B中任易何元臂素赋伴值,都使退得E1和E2的值峡相同态,则撕称这寨两个胁表达膏式相者等,劝记作E1(x1,x2,…贼,xn)=蝴E2(x1,x2,…络,xn)01a

b(x1∨)———(a∨)———a∨a____a¯我们欧可以向通过跑布尔宾代数董的性诉质(失10持个)眠得到摔很多疮等式导.如,E1(x僵,y薪)=艰x∨(y∧油)讽E2(x博,y担)=吃x∨yE1(x咱,y笛)=兰x∨(y∧肝)识=萍(x司∨y何)∧书(x爸∨复)=膨(x厦∨y龙)∧滑1斧=厌x∨y=醒E2(x矛,y璃)二.滥布鬼尔函说数设<B记,∨,登∧,¯>是一个布尔默代数根，一个沃从BnB的函偏数被勺称为n元布耳尔函结数。含有哭变元x1,x2,…范,xn的布犯尔表魂达式E(吊x1,x2,…xn),可以春看成肢是一吗个BnB的布尔还函数价.布尔牛函数葛有两型种表示纷方法鸭:1.表达烂式方吩法:封例如B=首{0亦,1友}迈<B托,∨,娇∧,¯>是布喝尔代秘数，即是昂表达跟式表聋示法滚.2.函数革表法:演见下释面:例：B=齐{0替,1婆,2朝,3帅}，<B脸,∨,呢∧,¯>是布湖尔代怀数在其扶上定彻义的火一个查布尔倍函数f(台x,圆y)的函嗽数表万如右监图所炭示:<x,y>f(x,y)<x,y>f(x,y)<0,0>1<2,0>2<0,1>0<2,1>0<0,2>0<2,2>1<0,3>3<2,3>1<1,0>1<3,0>3<1,1>1<3,1>0<1,2>0<3,2>2<1,3>3<3,3>3三.纪布猪尔表妖达式析的范骨式1.秒两徒元素纳布尔僚代数喇的布衔尔表页达式欢的范始式:<{亦0,光1}钩,∨,博∧,¯>是两孝个元滴素的穴布尔摩代数1)认.门析取夕范式(1惹).尾小项:巧含有n个变此元的气小项周形式华为:其中例如每都策是小记项.(2痰).弦布尔指表达蔑式的逝析取拔范式锦:含有挥变元x1,x2,…套,xn的布杨尔表详达式E(吓x1,x2,…xn),如果府写成如下残形式纤:A1∨A2∨.誉..刑∨Am(m浇≥1标)其中忘每个Ai(1阁≤i镇≤m店)都是脸有n个变纠元的震小项愚.聪则称意此式秃是E(损x1,x2,…xn)的析邮取范蚁式.北例销如:2)砌.合取仓范式(1棍).大项:含有n个变育元的袄大项煤形式虚为:其中例如馒都坛是大剩项.(2凑).贫布尔菠表达挽式的螺合取幸范式袄:含有纤变元x1,x2,…臂,xn的布柳尔表纺达式E(拾x1,x2,…xn),如果累写成如下细形式目:A1∧A2∧.稿..杰∧抬Am(m撒≥1针)其中玩每个Ai(1回≤i砖≤m短)都是攻有n个变虾元的纹大项定.限则称满此式压是E(邻x1,x2,…xn)的合绘取范凡式.嘉例返如:3)洋.析取扛范式团与合圾取范答式的斯写法:方法1:列真约值表方法2:表达器式的辅等价旅变换.方法1.用真府值表州求析械取范志式:先介覆绍小扑项的说性质,以两吓个变关元x1,x2为例每一争组赋过值,有且削仅有填一个哈小项锅为1.根据厨一组血赋值,求值寺为1的小多项:如果域变元x,被赋艺值为姑0,冠则在此朴小项美中,x以最形式躬出现醋;粱如果抱变元x,被赋宽值为洪1,巨则在此小贼项中僚,x以原醉形x形式音出现悟.求E(文x1,x2,…xn)的析绿取范泳式:先汽列出只它的通真值禾表,田找出椒表中每个妇1对彼应的岸小项锅,然弄后用∨连接莲上述滩小项.001000010100100010110001例如,求布尔曲代数<{妄0,志1}疯,∨,足∧,¯>上的布狱尔表暂达式E(膊x1,x2,x3)=眯x1∧(太x2∨论)的析芬取范讲式.E(丢x1,x2,x3)=煎(x1∧指∧篮)∨梅(x1∧子x2∧描)牲∨(文x1∧废x2∧x3)x3¯x1x2x3E(x1,

x2,

x3)00100100011010011010110100001111x3¯x3¯x2¯方法1.用真音值表叨求合饭取范摩式:先介晴绍大截项的把性质,以两宏个变喉元x1,x2为例每一丽组赋茄值,有且抖仅有芒一个叫大项让为0.根据磨一组朝赋值,求值踏为0的大梨项:如果脖变元x,被赋驶值为挪1,太则在此侵小项鸦中,x以瓦形式左出现嗽;壳如果溪变元x,被赋况值为炼0,缴则在此小笔项中致,x以原决形x形式尸出现让.求E(耍x1,x2,…xn)的合仙取范桌式:先哈列出剪它的街真值夏表,予找出潜表中每个才0对环应的魂大项慢,然青后用∧连接胖上述橡大项.000111011011101101111110例如,求布尔启代数<{浅0,例1}厘,∨,瞎∧,¯>上的布仗尔表线达式E(接x1,x2,x3)=x1∧(能x2∨射)的合范取范陆式.E(揉x1,x2,x3)=免(x1∨x2∨x3)∧妈(x1∨x2∨紫)惕∧矩(x1∨表∨梯x