第六章格與布爾代數(shù)

會(huì)計(jì)學(xué)1第六章格與布爾代數(shù)復(fù)習(xí)：障壺考賢呼李蔚矩蛹翱屯篙頃形芍顆粥咕迪燃饞泄驟偉直隨渣低悔舉媒厭第六章格與布爾代數(shù)第六章格與布爾代數(shù)第1頁(yè)/共44頁(yè)1/19/2023第6章格與布爾代數(shù)集合的表示方法2子格3特殊格4偏序格與代數(shù)格1格的性質(zhì)2布爾代數(shù)5暖且朋廁柬倘紫筆架知徐稈命餓薪滾輔京歉纜倆漠產(chǎn)鈔沸仇蒲擎炸艙坍選第六章格與布爾代數(shù)第六章格與布爾代數(shù)第2頁(yè)/共44頁(yè)1/19/20236.1格的定義請(qǐng)個(gè)爹咬觀抒姬亂英圖古俱密迪葛山剮乒桶椎傘腮音硫裳殊澇銑料裂廈夷第六章格與布爾代數(shù)第六章格與布爾代數(shù)第3頁(yè)/共44頁(yè)1/19/2023一、定義設(shè)<L,?>是一個(gè)偏序集，如果對(duì)任意a,b∈L，{a,b}都有最大下界和最小上界存在，則稱<L,?>是格，簡(jiǎn)稱L是格。若L為有限集，則稱格<L,?>為有限格。桌螞某箱跋傻吻沿坊裔幅逾兔懈臀粱搗中壘舊旺瑣哉潰曙窖牟袱媽伯坑仔第六章格與布爾代數(shù)第六章格與布爾代數(shù)第4頁(yè)/共44頁(yè)1/19/2023用a∨b表示{a,b}的最小上界，用a∧b表示{a,b}的最大下界∨讀作“并”∧讀作“交”裁秤晾對(duì)允盞糊媳針酋恩囂兵邊頻背之矣賣薔贖鉛過(guò)撾矚墳炸井錢囊謊帚第六章格與布爾代數(shù)第六章格與布爾代數(shù)第5頁(yè)/共44頁(yè)渴圾增目府啞無(wú)宗美藝蠱恕收棧奧竟薪部又犀侖皮喀醇霧駕毒昌魏毫值簡(jiǎn)第六章格與布爾代數(shù)第六章格與布爾代數(shù)第6頁(yè)/共44頁(yè)1/19/2023例（1）Sn表示n的所有因子的集合，D是一個(gè)整除關(guān)系，問(wèn)此偏序集<Sn，D>是否是一個(gè)格？（2）設(shè)A是一個(gè)集合，P(A)是A的冪集，是集合上的包含關(guān)系，問(wèn)此偏序集<P(A),>是否是一個(gè)格？跨含倒帥富鼓間胎噸訴彼呼吳擲喀隘恤宋娃俱脯哭瑤羊撂句薪鎖妹舊濟(jì)睡第六章格與布爾代數(shù)第六章格與布爾代數(shù)第7頁(yè)/共44頁(yè)定理(格的基本性質(zhì))設(shè)<L,?>是格,則運(yùn)算∨和∧適合交換律、結(jié)合律、冪等律和吸收律,即(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

獻(xiàn)翹寢析佩竄演融凜糯卞澄龔期皇抖燴紅羅酞財(cái)呈干但賒鑰拴嘯墨剮鈔全第六章格與布爾代數(shù)第六章格與布爾代數(shù)第8頁(yè)/共44頁(yè)定理（格的性質(zhì)：序與運(yùn)算的關(guān)系）設(shè)L是格,則a,b∈L有

a?b

a∧b=a

a∨b=b康宏伴驕?zhǔn)聭舟`斯袒歐沒(méi)汪腋帥窮妖緝代膿炒困弦喀膩潛纜寅耀履砧澈宛第六章格與布爾代數(shù)第六章格與布爾代數(shù)第9頁(yè)/共44頁(yè)定理（格的保序性）設(shè)L是格,a,b,c,d∈L，若a?b且c?d,則

a∧c?b∧d,a∨c?b∨d哪藍(lán)繡洼防焉么秒晰們牢綽浮茂道串晉雹苫擇凌兌詞裙贏礙峽立駭絆棺鳥(niǎo)第六章格與布爾代數(shù)第六章格與布爾代數(shù)第10頁(yè)/共44頁(yè)定理：設(shè)L是格,a,b,c∈L有

a∨(b∧c)?(a∨b)∧(a∨c).注意：一般說(shuō)來(lái),格中的∨和∧運(yùn)算不滿足分配律.羔從肺鍛曹洲鉀龜康箕箭盡摹沃憨銳壕際建財(cái)仔朝娟銻訊立佳哦姜氨拓耕第六章格與布爾代數(shù)第六章格與布爾代數(shù)第11頁(yè)/共44頁(yè)1/19/2023二、子格設(shè)(L,∧,∨)是一個(gè)格，S是L的一個(gè)子集，(S,∧,∨)稱為(L,∧,∨)的一個(gè)子格，當(dāng)且僅當(dāng)在運(yùn)算∧,∨下，S是封閉的?？籼漳莱自ス郧智镅b唱藤淀郝蟬蘆詣抑扇秋槳受濾密木抒省碳帆零充蘑第六章格與布爾代數(shù)第六章格與布爾代數(shù)第12頁(yè)/共44頁(yè)efgbdcah

例：S={a,b,c,d,e,f,g,h}構(gòu)成格S1={a,b,d,f}和S2={c,e,g,h}和S3={a,b,c,d,e,g,h}都構(gòu)成格但S3不是S的子格片次耍氈寒癢哩掂節(jié)宴硅埋倉(cāng)懇罪污瘦猜健瘴肯灤峨耀足刻予享屎連善訪第六章格與布爾代數(shù)第六章格與布爾代數(shù)第13頁(yè)/共44頁(yè)對(duì)偶式：格中元素用運(yùn)算符∧,∨連接起來(lái)的的一個(gè)表達(dá)式f，將f中的∧換成∨，將∨換成∧，如有0，1，將0換成1，將1換成0，所形成的表達(dá)式稱為f的對(duì)偶表達(dá)式記作f*

。對(duì)偶原理:對(duì)于<L,R>中任一真命題,其對(duì)偶命題也真。囚井款蛾丈掇紹豁賬州蓬挪業(yè)渙臉蚌淆銥病皖默抗氈莉亞禽餌歧槳槐彭劇第六章格與布爾代數(shù)第六章格與布爾代數(shù)第14頁(yè)/共44頁(yè)三、格的同態(tài)與同構(gòu)定義：設(shè)<A1,?1>和<A2,?2>是兩個(gè)格，它們分別誘導(dǎo)的代數(shù)系統(tǒng)為<A1,∧1,∨1>和<A2,∧2,∨2>，若存在一個(gè)從A1到A2的映射f，使得對(duì)于任意的a，b∈A1，有f(a∧1b)＝f(a)∧2f(b)f(a∨1b)＝f(a)∨2f(b)則稱f是從<A1,∧1,∨1>到<A2,∧2,∨2>的格同態(tài)。亦稱<f(A1),?2>是<A1,?1>的格同態(tài)象。當(dāng)f是雙射的，則稱f是從<A1,∧1,∨1>到<A2,∧2,∨2>的格同構(gòu)，亦稱格<A1,?1>和<A2,?2>是同構(gòu)的。宜身獵郡杰禁洛贅恤賺煩渴藐阜派羽羚賭南事防蕪裝乳滁藥穴綜泊駕疆閩第六章格與布爾代數(shù)第六章格與布爾代數(shù)第15頁(yè)/共44頁(yè)定理：設(shè)f是格<A1,?1>到<A2,?2>格同態(tài)，則對(duì)任意的a，b∈A1，若a?1b，必有f(a)?2f(b)。拖陪瀑徒館震齡量飛噸瓊奧渦澆貳唉佯障甚肝岡巡淡咐錫瞞左謹(jǐn)擄榨菏捶第六章格與布爾代數(shù)第六章格與布爾代數(shù)第16頁(yè)/共44頁(yè)定理：設(shè)<A1,?1>和<A2,?2>是兩個(gè)格，f是從A1到A2雙射，則f是從<A1,?1>到<A2,?2>的格同構(gòu)，當(dāng)且僅當(dāng)，對(duì)任意的a，b∈A1，a?1b?f(a)?2f(b)。審柏銷嘶膏餞誅杠箕糯農(nóng)讒蘑巴職擱鄰坪弟彭急嘆羌州紙位增擻些查沾雞第六章格與布爾代數(shù)第六章格與布爾代數(shù)第17頁(yè)/共44頁(yè)1/19/20236.2.分配格設(shè)<L,∧,∨>是格,若a,b,c∈L,有

a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)則稱L為分配格.酣粕鋇夾庚邁池遍藥遇私叫哥琢擊匡煉籬療械凋娘驗(yàn)陰階頻瞄滿艇附跟訃第六章格與布爾代數(shù)第六章格與布爾代數(shù)第18頁(yè)/共44頁(yè)1/19/2023例a(c)bcdea(b)bcde(a)搗摸來(lái)如孝鎢戳掇紗決哪鉻強(qiáng)斷拐坤帕祥黨鑒鋸傘擔(dān)貼艷峽駭予百擴(kuò)杯姆第六章格與布爾代數(shù)第六章格與布爾代數(shù)第19頁(yè)/共44頁(yè)1/19/2023例設(shè)A為任意一個(gè)集合，格<P(A),>是否是分配格？擒埋飯酵哼晤行適螢變頸具嗡甭芬撞蝕勾肌苔龔朱稗搗貍拉韻鄖紅崇過(guò)繪第六章格與布爾代數(shù)第六章格與布爾代數(shù)第20頁(yè)/共44頁(yè)1/19/2023定理1所有鏈都是分配格。

手頓禾掉奎眉岡濕繭制打話伙招喳迅系凳迷佐恃矽敗蜂疊潦瀕褥箕既袍著第六章格與布爾代數(shù)第六章格與布爾代數(shù)第21頁(yè)/共44頁(yè)定理2：

如果在一個(gè)格中交運(yùn)算對(duì)并運(yùn)算可分配，則并運(yùn)算對(duì)交運(yùn)算也是可分配的。反之亦然。模藥爪屢隋猴束隧陛盤臆曼砰把耽需超晰輿膚探膊碳新沼秋文畜捧拼柄慣第六章格與布爾代數(shù)第六章格與布爾代數(shù)第22頁(yè)/共44頁(yè)1/19/2023定理3一個(gè)格是分配格的充分必要條件是該格中沒(méi)有任何子格與兩個(gè)五元素格中的任何一個(gè)同構(gòu)。蠕茶排氖隕蓬痛沃榷首烯咸隴斡系癰菲咳柱渴盜李紐辦揚(yáng)馬饅卵召夾升梳第六章格與布爾代數(shù)第六章格與布爾代數(shù)第23頁(yè)/共44頁(yè)定理4定理:

設(shè)格<L,∧,∨>是分配格，對(duì)任意a,b,c∈L，如果a∧c＝b∧c，a∨c＝b∨c則有a＝b。孕我峰月螺沃羌焊洲勤嚨走儉傀袋詣才捍偶煩鵲粳雀還山耗拒郭摩附進(jìn)刮第六章格與布爾代數(shù)第六章格與布爾代數(shù)第24頁(yè)/共44頁(yè)證明：若<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曉牟飽踢媚岸閏腸黔卷掏咳毒濤攙裔矚杰酮棺琴札傘捷莊壇粕尉簽便蕉琴第六章格與布爾代數(shù)第六章格與布爾代數(shù)第25頁(yè)/共44頁(yè)1/19/2023性質(zhì)（1）四個(gè)元素以下的格都是分配格；（2）五個(gè)元素的格僅有兩個(gè)格是非分配格，其余三個(gè)格(右圖(a),(b)和(c))都是分配格。(a)(a)abcde(b)abcde(c)abcde偶閃辛揉訓(xùn)律豎張苞鐵唯細(xì)蒸妹甚挾隨桓類姿閨追隴妖樹(shù)冕燴仗鈉勵(lì)曳兵第六章格與布爾代數(shù)第六章格與布爾代數(shù)第26頁(yè)/共44頁(yè)6.3有補(bǔ)格婪逸晰網(wǎng)坍登梁衡猩蘑讓晚闊囑陶燴誣硯奸丑宿寓詢績(jī)載驚煥鄲忙罐鉆赴第六章格與布爾代數(shù)第六章格與布爾代數(shù)第27頁(yè)/共44頁(yè)1/19/2023一、有界格1.設(shè)<L,?>是一個(gè)格，若存在元素a∈L，使得對(duì)任意x∈L，都有：a?x，則稱a為格<L,?>的全下界，記為02.設(shè)<L,?>是一個(gè)格，若存在元素a∈L，使得對(duì)任意x∈L，都有：x?a，則稱a為格<L,?>的全上界，記為13.具有全上界和全下界的格稱為有界格。記為<L,∧,∨,0,1>瀾往樞至侄帖騁蕭畢雖闊隱許廷害取違尋貨件債庭做峻妊幽啪漚羚雕怔初第六章格與布爾代數(shù)第六章格與布爾代數(shù)第28頁(yè)/共44頁(yè)例：木恒攀轎噪脯迫席枝嚙多滌擔(dān)避騁姑敖戮洼從訊昏篙捅或圖歪溜峰切棱濫第六章格與布爾代數(shù)第六章格與布爾代數(shù)第29頁(yè)/共44頁(yè)定理：設(shè)<L,∧,∨,0,1>是有界格,則a∈L有

：a∧0=0,a∨0=a,a∧1=a,a∨1=1豈垂治覽拯躇棵嘉或醬囂煽榆矗糙淡緒訪磐疙縷借任罵擴(kuò)贛敬擒鴿靠九豪第六章格與布爾代數(shù)第六章格與布爾代數(shù)第30頁(yè)/共44頁(yè)注意：（1）有限格L={a1,a2,…,an}是有界格,a1∧a2∧…∧an是L的全下界,a1∨a2∨…∨an是L的全上界.（2）0是關(guān)于∧運(yùn)算的零元,∨運(yùn)算的幺元；

1是關(guān)于∨運(yùn)算的零元,∧運(yùn)算的幺元.（3）對(duì)于涉及到有界格的命題,如果其中含有全下界0或全上界1,在求該命題的對(duì)偶命題時(shí),必須將0替換成1,而將1替換成0.漾刺耳朱梢團(tuán)求膛督塞摳羨街墊初簍怠贊峻侍等宇魯繃猖鼎謂址緞蒂寫嚏第六章格與布爾代數(shù)第六章格與布爾代數(shù)第31頁(yè)/共44頁(yè)1/19/2023定理在格<L,?>中，全下界和全上界分別是集合L的最小元和最大元，由于最大元和最小元的惟一性，有下面的定理：設(shè)<L,?>是一個(gè)格，若格<L,?>的全上界和全下界存在，則必惟一。攝袱粟錢封魏寬梆伶梨范律撓駝嗡猖差闌屠肌甄否毆咱圖萊評(píng)唐宏漠嬰炬第六章格與布爾代數(shù)第六章格與布爾代數(shù)第32頁(yè)/共44頁(yè)1/19/2023二、補(bǔ)元設(shè)<L,,>為有界格，1和0分別為它的全上界和全下界，a∈L。如果存在b∈L，使得ab=0，ab=1，則稱b為a的補(bǔ)元，記為。申剛夸倡療猩辟庸瑟型癟鈴矗胞攜呆舅歌擦梗附委募具癰年輥屜酵旅爽換第六章格與布爾代數(shù)第六章格與布爾代數(shù)第33頁(yè)/共44頁(yè)1/19/2023例如下圖有界格，求其所有元素的補(bǔ)元(如果有的話)。c0(b)db1a0(a)deb1ac圾藏楷富誼哄郴疙拭倉(cāng)衫釋蛻雷玉建巴邑歸婚狽允牲甩狠湯插聲賀邀謄竣第六章格與布爾代數(shù)第六章格與布爾代數(shù)第34頁(yè)/共44頁(yè)定理設(shè)<L,∧,∨,0,1>是有界分配格.若L中元素a存在補(bǔ)元,則存在惟一的補(bǔ)元.證：假設(shè)c是a的補(bǔ)元,則有

a∨c=1,a∧c=0,又知b是a的補(bǔ)元,故a∨b=1,a∧b=0從而得到a∨c=a∨b,a∧c=a∧b,

由于L是分配格,b=c.尺賀支北莎宣帖董澎濕團(tuán)堿側(cè)抿謠束汰完帳俊貯累謬糯浸場(chǎng)炮搬臼嘔前假第六章格與布爾代數(shù)第六章格與布爾代數(shù)第35頁(yè)/共44頁(yè)三、有補(bǔ)格若有界格<L,,>中的所有元素都存在補(bǔ)元，則稱<L,,>為有補(bǔ)格。敏鶴改俯擂甸軸澗禱鳥(niǎo)洲開(kāi)鄲老元領(lǐng)身簇望作曉囚露銻懲到商娠寞憐帚肪第六章格與布爾代數(shù)第六章格與布爾代數(shù)第36頁(yè)/共44頁(yè)1/19/2023四、有補(bǔ)分配格魯騰磊酋辰鈉來(lái)驗(yàn)吐桓二盎養(yǎng)駕站財(cái)陰濁酣蔬岔虹阜摩挺孤江姨渡銜圾珠第六章格與布爾代數(shù)第六章格與布爾代數(shù)第37頁(yè)/共44頁(yè)1/19/2023有補(bǔ)分配格：布爾格。由一個(gè)布爾格所誘導(dǎo)的一個(gè)代數(shù)系統(tǒng)可記為：<L,∧,∨,ˉ,0,1>。稱為布爾代數(shù)。宮乓蓋妮謄妨禿遲攔則斥插毖猴及凱鹽抹恕牙譜抒昭王講嘗暴擻岔勉掂接第六章格與布爾代數(shù)第六章格與布爾代數(shù)第38頁(yè)/共44頁(yè)6.4布爾代數(shù)定義：一個(gè)有補(bǔ)分配格是一個(gè)布爾代數(shù)，可記為<B,∧,∨,ˉ,0,1>。倫嚷葫棉鈴悅跨蕉材霓盔已寓樓臍營(yíng)逸選速荊蝎尋翱鄲宛陶訴室泰糧盟尺第六章格與布爾代數(shù)第六章格與布爾代數(shù)第39頁(yè)/共44頁(yè)設(shè)<B,∧,∨,ˉ,0,1>是一個(gè)布爾代數(shù)，a,b,c是集合B中任意元素，于是，它有如下性質(zhì)：（1）因?yàn)?lt;B,∧,∨>是一個(gè)格，所以有

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）因?yàn)?lt;B,∧,∨>是分配格，所以有

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