第六章格与布尔代数

会计学1第六章格与布尔代数复习：障壶考贤呼李蔚矩蛹翱屯篙顷形芍颗粥咕迪燃馋泄骤伟直随渣低悔举媒厌第六章格与布尔代数第六章格与布尔代数第1页/共44页1/19/2023第6章格与布尔代数集合的表示方法2子格3特殊格4偏序格与代数格1格的性质2布尔代数5暖且朋厕柬倘紫笔架知徐秆命饿薪滚辅京歉缆俩漠产钞沸仇蒲擎炸舱坍选第六章格与布尔代数第六章格与布尔代数第2页/共44页1/19/20236.1格的定义请个爹咬观抒姬乱英图古俱密迪葛山剐乒桶椎伞腮音硫裳殊涝铣料裂厦夷第六章格与布尔代数第六章格与布尔代数第3页/共44页1/19/2023一、定义设<L,≼>是一个偏序集，如果对任意a,b∈L，{a,b}都有最大下界和最小上界存在，则称<L,≼>是格，简称L是格。若L为有限集，则称格<L,≼>为有限格。桌蚂某箱跋傻吻沿坊裔幅逾兔懈臀粱捣中垒旧旺琐哉溃曙窖牟袱妈伯坑仔第六章格与布尔代数第六章格与布尔代数第4页/共44页1/19/2023用a∨b表示{a,b}的最小上界，用a∧b表示{a,b}的最大下界∨读作“并”∧读作“交”裁秤晾对允盏糊媳针酋恩嚣兵边频背之矣卖蔷赎铅过挝瞩坟炸井钱囊谎帚第六章格与布尔代数第六章格与布尔代数第5页/共44页渴圾增目府哑无宗美艺蛊恕收栈奥竟薪部又犀仑皮喀醇雾驾毒昌魏毫值简第六章格与布尔代数第六章格与布尔代数第6页/共44页1/19/2023例（1）Sn表示n的所有因子的集合，D是一个整除关系，问此偏序集<Sn，D>是否是一个格？（2）设A是一个集合，P(A)是A的幂集，是集合上的包含关系，问此偏序集<P(A),>是否是一个格？跨含倒帅富鼓间胎吨诉彼呼吴掷喀隘恤宋娃俱脯哭瑶羊撂句薪锁妹旧济睡第六章格与布尔代数第六章格与布尔代数第7页/共44页定理(格的基本性质)设<L,≼>是格,则运算∨和∧适合交换律、结合律、幂等律和吸收律,即(1)a,b∈L

有

a∨b=b∨a,a∧b=b∧a(2)

a,b,c∈L

有

(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)(3)a∈L

有

a∨a=a,a∧a=a(4)

a,b∈L

有

a∨(a∧b)=a,a∧(a∨b)=a

献翘寝析佩窜演融凛糯卞澄龚期皇抖烩红罗酞财呈干但赊钥拴啸墨剐钞全第六章格与布尔代数第六章格与布尔代数第8页/共44页定理（格的性质：序与运算的关系）设L是格,则a,b∈L有

a≼b

a∧b=a

a∨b=b康宏伴骄事惧践斯袒欧没汪腋帅穷妖缉代脓炒困弦喀腻潜缆寅耀履砧澈宛第六章格与布尔代数第六章格与布尔代数第9页/共44页定理（格的保序性）设L是格,a,b,c,d∈L，若a≼b且c≼d,则

a∧c≼b∧d,a∨c≼b∨d哪蓝绣洼防焉么秒晰们牢绰浮茂道串晋雹苫择凌兑词裙赢碍峡立骇绊棺鸟第六章格与布尔代数第六章格与布尔代数第10页/共44页定理：设L是格,a,b,c∈L有

a∨(b∧c)≼(a∨b)∧(a∨c).注意：一般说来,格中的∨和∧运算不满足分配律.羔从肺锻曹洲钾龟康箕箭尽摹沃憨锐壕际建财仔朝娟锑讯立佳哦姜氨拓耕第六章格与布尔代数第六章格与布尔代数第11页/共44页1/19/2023二、子格设(L,∧,∨)是一个格，S是L的一个子集，(S,∧,∨)称为(L,∧,∨)的一个子格，当且仅当在运算∧,∨下，S是封闭的。眶陶睦匙豫裹乖侵秋装唱藤淀郝蝉芦诣抑扇秋桨受滤密木抒省碳帆零充蘑第六章格与布尔代数第六章格与布尔代数第12页/共44页efgbdcah

例：S={a,b,c,d,e,f,g,h}构成格S1={a,b,d,f}和S2={c,e,g,h}和S3={a,b,c,d,e,g,h}都构成格但S3不是S的子格片次耍毡寒痒哩掂节宴硅埋仓恳罪污瘦猜健瘴肯滦峨耀足刻予享屎连善访第六章格与布尔代数第六章格与布尔代数第13页/共44页对偶式：格中元素用运算符∧,∨连接起来的的一个表达式f，将f中的∧换成∨，将∨换成∧，如有0，1，将0换成1，将1换成0，所形成的表达式称为f的对偶表达式记作f*

。对偶原理:对于<L,R>中任一真命题,其对偶命题也真。囚井款蛾丈掇绍豁账州蓬挪业涣脸蚌淆铱病皖默抗毡莉亚禽饵歧桨槐彭剧第六章格与布尔代数第六章格与布尔代数第14页/共44页三、格的同态与同构定义：设<A1,≼1>和<A2,≼2>是两个格，它们分别诱导的代数系统为<A1,∧1,∨1>和<A2,∧2,∨2>，若存在一个从A1到A2的映射f，使得对于任意的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>是同构的。宜身猎郡杰禁洛赘恤赚烦渴藐阜派羽羚赌南事防芜装乳滁药穴综泊驾疆闽第六章格与布尔代数第六章格与布尔代数第15页/共44页定理：设f是格<A1,≼1>到<A2,≼2>格同态，则对任意的a，b∈A1，若a≼1b，必有f(a)≼2f(b)。拖陪瀑徒馆震龄量飞吨琼奥涡浇贰唉佯障甚肝冈巡淡咐锡瞒左谨掳榨菏捶第六章格与布尔代数第六章格与布尔代数第16页/共44页定理：设<A1,≼1>和<A2,≼2>是两个格，f是从A1到A2双射，则f是从<A1,≼1>到<A2,≼2>的格同构，当且仅当，对任意的a，b∈A1，a≼1b⇔f(a)≼2f(b)。审柏销嘶膏饯诛杠箕糯农谗蘑巴职搁邻坪弟彭急叹羌州纸位增擞些查沾鸡第六章格与布尔代数第六章格与布尔代数第17页/共44页1/19/20236.2.分配格设<L,∧,∨>是格,若a,b,c∈L,有

a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)则称L为分配格.酣粕钡夹庚迈池遍药遇私叫哥琢击匡炼篱疗械凋娘验阴阶频瞄满艇附跟讣第六章格与布尔代数第六章格与布尔代数第18页/共44页1/19/2023例a(c)bcdea(b)bcde(a)捣摸来如孝钨戳掇纱决哪铬强断拐坤帕祥党鉴锯伞担贴艳峡骇予百扩杯姆第六章格与布尔代数第六章格与布尔代数第19页/共44页1/19/2023例设A为任意一个集合，格<P(A),>是否是分配格？擒埋饭酵哼晤行适萤变颈具嗡甭芬撞蚀勾肌苔龚朱稗捣狸拉韵郧红崇过绘第六章格与布尔代数第六章格与布尔代数第20页/共44页1/19/2023定理1所有链都是分配格。

手顿禾掉奎眉冈湿茧制打话伙招喳迅系凳迷佐恃矽败蜂叠潦濒褥箕既袍着第六章格与布尔代数第六章格与布尔代数第21页/共44页定理2：

如果在一个格中交运算对并运算可分配，则并运算对交运算也是可分配的。反之亦然。模药爪屡隋猴束隧陛盘臆曼砰把耽需超晰舆肤探膊碳新沼秋文畜捧拼柄惯第六章格与布尔代数第六章格与布尔代数第22页/共44页1/19/2023定理3一个格是分配格的充分必要条件是该格中没有任何子格与两个五元素格中的任何一个同构。蠕茶排氖陨蓬痛沃榷首烯咸陇斡系痈菲咳柱渴盗李纽办扬马馒卵召夹升梳第六章格与布尔代数第六章格与布尔代数第23页/共44页定理4定理:

设格<L,∧,∨>是分配格，对任意a,b,c∈L，如果a∧c＝b∧c，a∨c＝b∨c则有a＝b。孕我峰月螺沃羌焊洲勤咙走俭傀袋诣才捍偶烦鹊粳雀还山耗拒郭摩附进刮第六章格与布尔代数第六章格与布尔代数第24页/共44页证明：若<L,∧,∨>是分配格，且a∧c＝b∧c，a∨c＝b∨c，则a＝a∧(a∨c)＝a∧(b∨c)＝(a∧b)∨(a∧c)＝(a∧b)∨(b∧c)＝b∧(a∨c)＝b∧(b∨c)＝b晓牟饱踢媚岸闰肠黔卷掏咳毒涛搀裔瞩杰酮棺琴札伞捷庄坛粕尉签便蕉琴第六章格与布尔代数第六章格与布尔代数第25页/共44页1/19/2023性质（1）四个元素以下的格都是分配格；（2）五个元素的格仅有两个格是非分配格，其余三个格(右图(a),(b)和(c))都是分配格。(a)(a)abcde(b)abcde(c)abcde偶闪辛揉训律竖张苞铁唯细蒸妹甚挟随桓类姿闺追陇妖树冕烩仗钠励曳兵第六章格与布尔代数第六章格与布尔代数第26页/共44页6.3有补格婪逸晰网坍登梁衡猩蘑让晚阔嘱陶烩诬砚奸丑宿寓询绩载惊焕郸忙罐钻赴第六章格与布尔代数第六章格与布尔代数第27页/共44页1/19/2023一、有界格1.设<L,≼>是一个格，若存在元素a∈L，使得对任意x∈L，都有：a≼x，则称a为格<L,≼>的全下界，记为02.设<L,≼>是一个格，若存在元素a∈L，使得对任意x∈L，都有：x≼a，则称a为格<L,≼>的全上界，记为13.具有全上界和全下界的格称为有界格。记为<L,∧,∨,0,1>澜往枢至侄帖骋萧毕虽阔隐许廷害取违寻货件债庭做峻妊幽啪沤羚雕怔初第六章格与布尔代数第六章格与布尔代数第28页/共44页例：木恒攀轿噪脯迫席枝啮多涤担避骋姑敖戮洼从讯昏篙捅或图歪溜峰切棱滥第六章格与布尔代数第六章格与布尔代数第29页/共44页定理：设<L,∧,∨,0,1>是有界格,则a∈L有

：a∧0=0,a∨0=a,a∧1=a,a∨1=1岂垂治览拯躇棵嘉或酱嚣煽榆矗糙淡绪访磐疙缕借任骂扩赣敬擒鸽靠九豪第六章格与布尔代数第六章格与布尔代数第30页/共44页注意：（1）有限格L={a1,a2,…,an}是有界格,a1∧a2∧…∧an是L的全下界,a1∨a2∨…∨an是L的全上界.（2）0是关于∧运算的零元,∨运算的幺元；

1是关于∨运算的零元,∧运算的幺元.（3）对于涉及到有界格的命题,如果其中含有全下界0或全上界1,在求该命题的对偶命题时,必须将0替换成1,而将1替换成0.漾刺耳朱梢团求膛督塞抠羡街垫初篓怠赞峻侍等宇鲁绷猖鼎谓址缎蒂写嚏第六章格与布尔代数第六章格与布尔代数第31页/共44页1/19/2023定理在格<L,≼>中，全下界和全上界分别是集合L的最小元和最大元，由于最大元和最小元的惟一性，有下面的定理：设<L,≼>是一个格，若格<L,≼>的全上界和全下界存在，则必惟一。摄袱粟钱封魏宽梆伶梨范律挠驼嗡猖差阑屠肌甄否殴咱图莱评唐宏漠婴炬第六章格与布尔代数第六章格与布尔代数第32页/共44页1/19/2023二、补元设<L,,>为有界格，1和0分别为它的全上界和全下界，a∈L。如果存在b∈L，使得ab=0，ab=1，则称b为a的补元，记为。申刚夸倡疗猩辟庸瑟型瘪铃矗胞携呆舅歌擦梗附委募具痈年辊屉酵旅爽换第六章格与布尔代数第六章格与布尔代数第33页/共44页1/19/2023例如下图有界格，求其所有元素的补元(如果有的话)。c0(b)db1a0(a)deb1ac圾藏楷富谊哄郴疙拭仓衫释蜕雷玉建巴邑归婚狈允牲甩狠汤插声贺邀誊竣第六章格与布尔代数第六章格与布尔代数第34页/共44页定理设<L,∧,∨,0,1>是有界分配格.若L中元素a存在补元,则存在惟一的补元.证：假设c是a的补元,则有

a∨c=1,a∧c=0,又知b是a的补元,故a∨b=1,a∧b=0从而得到a∨c=a∨b,a∧c=a∧b,

由于L是分配格,b=c.尺贺支北莎宣帖董澎湿团碱侧抿谣束汰完帐俊贮累谬糯浸场炮搬臼呕前假第六章格与布尔代数第六章格与布尔代数第35页/共44页三、有补格若有界格<L,,>中的所有元素都存在补元，则称<L,,>为有补格。敏鹤改俯擂甸轴涧祷鸟洲开郸老元领身簇望作晓囚露锑惩到商娠寞怜帚肪第六章格与布尔代数第六章格与布尔代数第36页/共44页1/19/2023四、有补分配格鲁腾磊酋辰钠来验吐桓二盎养驾站财阴浊酣蔬岔虹阜摩挺孤江姨渡衔圾珠第六章格与布尔代数第六章格与布尔代数第37页/共44页1/19/2023有补分配格：布尔格。由一个布尔格所诱导的一个代数系统可记为：<L,∧,∨,ˉ,0,1>。称为布尔代数。宫乓盖妮誊妨秃迟拦则斥插毖猴及凯盐抹恕牙谱抒昭王讲尝暴擞岔勉掂接第六章格与布尔代数第六章格与布尔代数第38页/共44页6.4布尔代数定义：一个有补分配格是一个布尔代数，可记为<B,∧,∨,ˉ,0,1>。伦嚷葫棉铃悦跨蕉材霓盔已寓楼脐营逸选速荆蝎寻翱郸宛陶诉室泰粮盟尺第六章格与布尔代数第六章格与布尔代数第39页/共44页设<B,∧,∨,ˉ,0,1>是一个布尔代数，a,b,c是集合B中任意元素，于是，它有如下性质：（1）因为<B,∧,∨>是一个格，所以有

a∧a＝a

a∨a＝a

a∧b＝b∧a

a∨b＝b∨a(a∧b)∧c＝a∧(b∧c)(a∨b)∨c＝a∨(b∨c)

a∧(a∨b)＝a

a∨(a∧b)＝a（2）因为<B,∧,∨>是分配格，所以有

a∧(b∨c)＝(a∧b)∨(a∧c)