離散數(shù)學(xué)-格與布爾代數(shù)

離散數(shù)學(xué)

DiscreteMathematics主講:郝曉燕二零二一年九月一六日～二零二一年一二月一八日學(xué)時(shí):五六學(xué)分:三.五第七章格與布爾代數(shù)

Lattice&BooleanAlgebra一格二分配格三有補(bǔ)格四布爾代數(shù)第七章格與布爾代數(shù)Lattice&BooleanAlgebra4格論

戴德金(Dedekind,一八三一～一九一六)5德數(shù)學(xué)家數(shù)學(xué)王子高斯地最后一位學(xué)生繼承了庫莫(Kummer)在數(shù)論上地工作主要成就是在代數(shù)理論方面研究過任意域,環(huán),群,結(jié)構(gòu)與模問題在授課時(shí)率先引入了環(huán)（域）地概念,并給理想子環(huán)下了一般定義提出了能與自己地真子集建立一一對(duì)應(yīng)地集合是無窮集地思想布爾代數(shù)地發(fā)展英數(shù)學(xué)家G.布爾為了研究思維規(guī)律(邏輯學(xué),數(shù)理邏輯)于一八四七與一八五四年提出地?cái)?shù)學(xué)模型。此后R.戴德金把它作為一種特殊地格。布爾代數(shù)由于缺乏物理背景,所以研究緩慢,到了二零世紀(jì)三零～四零年代才又有了新地展,在代數(shù)結(jié)構(gòu),邏輯演算,集合論,拓?fù)淇臻g理論,測(cè)度論,概率論,泛函分析數(shù)學(xué)分支均有應(yīng)用。一九六七年后,在數(shù)理邏輯地分支之一地公理化集合論以與模型論地理論研究也起著一定地作用。近幾十年來,布爾代數(shù)在自動(dòng)化技術(shù),電子計(jì)算機(jī)地邏輯設(shè)計(jì)工程技術(shù)領(lǐng)域有重要地應(yīng)用?！炱?一-一格地概念定義七-一.一設(shè)<S,?>是偏序集,如果x,yS,{x,y}都有最小上界與最大下界,那么稱S關(guān)于偏序?構(gòu)成一個(gè)格,或稱<S,?>為偏序格,或簡(jiǎn)稱<S,?>為格（lattice）。七-一示例二S是非空集合,(S)是S地冪集,則<(S),?>是格。因?yàn)锳,B?S,都有A,B地最小上界為A∪B;A,B地最大下界為A∩B。8

{??}{??}{??}{??,??}{??,??}{??,??}{??,??,??}示例三設(shè)N+是所有正整數(shù)集合,定義N+上地整除關(guān)系|。<N+,|>是偏序集。任意兩個(gè)元素地最小公倍數(shù),最大公約數(shù)分別是這兩個(gè)元素地最小上界與最大下界,因此<N+,|>是格。示例四設(shè)集合A={??,??,??},考慮恒關(guān)系=,<A,=>是偏序集,但它不是格。因?yàn)锳任意兩個(gè)元素都是既無最小上界又無最大下界,<A,=>地Hass如下。9示例五設(shè)P={二,三,六,一二,二四,三六},S={一,二,三,一二,一八,三六},<P,|>與<S,|>都不是格。10三二二四一二六三六三六三二一八一二一格誘導(dǎo)地代數(shù)系統(tǒng)定義設(shè)<S,≤>是格,如果在S上定義兩個(gè)二元運(yùn)算∨與∧,使得對(duì)于??,??S,??∨??于??與??地最小上界,??∧??于??與??地最大下界。則稱<S,∨,∧>為由格<S,≤>所誘導(dǎo)地代數(shù)系統(tǒng)。其,二元運(yùn)算∨與∧分別稱為并運(yùn)算與運(yùn)算。11示例一對(duì)給定地集合S={??,??},<(S),?>是格,誘導(dǎo)地代數(shù)系統(tǒng)為<(S),∨,∧>,A,B(S),A∨B=A∪B,A∧B=A∩B。12∨

{??}{??}{??,??}

{??}{??}{??,??}{??}{??}{??}{??,??}{??,??}{??}{??}{??,??}{??}{??,??}{??,??}{??,??}{??,??}{??,??}{??,??}∧

{??}{??}{??,??}

{??}

{??}

{??}{??}

{??}{??}{??,??}

{??}{??}{??,??}示例二設(shè)D三六是三六地全部正因子地集合,D三六={一,二,三,四,六,九,一二,一八,三六},"|"表示數(shù)地整除關(guān)系,則<D三六,|>是格,對(duì)??,??D三六,??∨??=l{??,??}最小公倍數(shù),??∧??=gcd{??,??}最大公約數(shù)。代數(shù)系統(tǒng)<D三六,∨,∧>13子格定義設(shè)<L,≤>是格,由<L,≤>誘導(dǎo)地代數(shù)系統(tǒng)為<L,∨,∧>,設(shè)S是L地非空子集,若S關(guān)于L地運(yùn)算∧與∨是封閉地,則稱<S,≤>是<L,≤>地子格。14示例一給出格<N+,|>,由它誘導(dǎo)地代數(shù)系統(tǒng)為<N+,∨,∧>,其,對(duì)??,??N+,??∨??=l{??,??}??∧??=gcd{??,??}<D三六,|>是<N+,|>地子格。E+表示全體正偶數(shù)集,<E+,|>是<N+,|>地子格。示例二設(shè)<L,≤>是格,其L={??,??,??,??,??,??,??,?}。子集L??是<L,≤>地子格嗎？L一={??,??,??,??}TL二={??,??,??,?}TL三={??,??,?}FL四={??,??,??,?,??}F示例三根據(jù)格L地哈斯圖,判斷L一,L二,L三是L地子格嗎？L一={零,??,??}TL二={??,??}TL三={零,??,??,??}F15一????零??格地同態(tài)與同構(gòu)定義設(shè)<L一,一>,<L二,二>都是格,由它們分別誘導(dǎo)地代數(shù)系統(tǒng)<L一,∨一,∧一>與<L二,∨二,∧二>,若存在映射??:L一→L二使得對(duì)??,??L一有??(??∧一??)=??(??)∧二??(??)??(??∨一??)=??(??)∨二??(??)則稱??為從<L一,∨一,∧一>到<L二,∨二,∧二>地格同態(tài),亦稱<??(L一),二>是<L一,一>地格同態(tài)象。定義若??是格同態(tài)且雙射,則稱??是從<L一,∨一,∧一>到<L二,∨二,∧二>地格同構(gòu)。定義設(shè)<P,>,<Q,>是兩偏序集,若存在映射??:PQ使得對(duì)??,??P有??????(??)??(??)則稱??為保序映射。示例一設(shè)L={一,二,三,六},??,??L,有??∧L??=gcd{??,??},??∨L??=l{??,??}S={七,八},??,??S,有??∧S??=min{??,??},??∨S??=max{??,??}映射??:LS,??(一)=??(二)=??(三)=七,??(六)=八,??不是格同態(tài)。17??(一∧L二)=??(一)=七 ??(一)∧S??(二)=min{七,七}=七??(一∧L三)=??(一)=七 ??(一)∧S??(三)=min{七,七}=七??(一∧L六)=??(一)=七 ??(一)∧S??(六)=min{七,八}=七??(二∧L三)=??(一)=七 ??(二)∧S??(三)=min{七,七}=七??(二∧L六)=??(二)=七 ??(二)∧S??(六)=min{七,八}=七??(三∧L六)=??(三)=八 ??(三)∧S??(六)=min{七,八}=七??(一∨L二)=??(二)=七 ??(一)∨S??(二)=max{七,七}=七??(一∨L三)=??(三)=七 ??(一)∨S??(三)=max{七,七}=七??(一∨L六)=??(六)=八 ??(一)∨S??(六)=max{七,八}=八??(二∨L三)=??(六)=八 ??(二)∨S??(三)=max{七,七}=七??(二∨L六)=??(六)=八 ??(二)∨S??(六)=max{七,八}=八??(三∨L六)=??(六)=八 ??(三)∨S??(六)=max{七,八}=八示例二設(shè)L={一,二,三,六},??,??L, ??∧L??=gcd{??,??},??∨L??=l{??,??};S={七,八},??,??S, ??∧S??=min{??,??},??∨S??=max{??,??}映射??:LS,問????是格同態(tài)嗎？??一(一)=七,??一(二)=??一(三)=??一(六)=八;??二(一)=??二(三)=七,??二(二)=??二(六)=八.解:??一不是格同態(tài),??二是格同態(tài)18示例三設(shè)L={一,二,三,六},??,??L, ??∧L??=gcd{??,??},??∨L??=l{??,??};映射??:LL,??(一)=一,??(二)=三,??(三)=二,??(六)=六,??是格同構(gòu)。19??(一∧L二)=??(一)=一 ??(一)∧L??(二)=gcd{一,三}=一??(一∧L三)=??(一)=一 ??(一)∧L??(三)=gcd{一,二}=一??(一∧L六)=??(一)=一 ??(一)∧L??(六)=gcd{一,六}=一??(二∧L三)=??(一)=一 ??(二)∧L??(三)=gcd{三,二}=一??(二∧L六)=??(二)=三 ??(二)∧L??(六)=gcd{三,六}=三??(三∧L六)=??(三)=二 ??(三)∧L??(六)=gcd{二,六}=二??(一∨L二)=??(二)=三 ??(一)∨L??(二)=l{一,三}=三??(一∨L三)=??(三)=二 ??(一)∨L??(三)=l{一,二}=二??(一∨L六)=??(六)=六 ??(一)∨L??(六)=l{一,六}=六??(二∨L三)=??(六)=六 ??(二)∨L??(三)=l{三,二}=六??(二∨L六)=??(六)=六 ??(二)∨L??(六)=l{三,六}=六??(三∨L六)=??(六)=六 ??(三)∨L??(六)=l{二,六}=六§七-一-二格地質(zhì)定理對(duì)于集合S地任何偏序關(guān)系≤,其逆關(guān)系≥也是S地偏序關(guān)系。定理<L,≤>是格,<L,≥>也一定是格。格七-一20格地對(duì)偶原理定義設(shè)P對(duì)任意格都是真命題,如果在命題P把≤換成≥,∨換成∧,∧換成∨,就得到另一命題P',把P'稱為P地對(duì)偶命題,則P'對(duì)任意格也是真命題。21許多格地質(zhì)都是互為對(duì)偶命題地。有了格地對(duì)偶原理,在證明格地質(zhì)時(shí),只需求證明其地一個(gè)命題即可。格地質(zhì)定理在格<L,≤>,對(duì)??,??,??,??L都有(一)??≤??∨??,??≤??∨??,??∧??≤??,??∧??≤??(二)若??≤??且??≤??,則??∨??≤??∨??,??∧??≤??∧??推論在格<L,≤>,對(duì)??,??,??L,若??≤??,則??∨??≤??∨??,??∧??≤??∧??。22運(yùn)算質(zhì)定理設(shè)<L,≤>是一個(gè)格,由格<L,≤>所誘導(dǎo)地代數(shù)系統(tǒng)為<L,∨,∧>,則對(duì)??,??,??L,有23冪律??∨??=??;??∧??=??換律??∨??=??∨??;??∧??=??∧??結(jié)合律??∨(??∨??)=(??∨??)∨??;??∧(??∧??)=(??∧??)∧??吸收率??∨(??∧??)=??;??∧(??∨??)=??分配不式??(????)≤(????)(????);(????)(????)≤??(????)??≤??????=??????=????≤????(????)≤(????)??(????)(????)≤??(??(????));??(??(????))≤(????)(????)運(yùn)算質(zhì)引理設(shè)<L,∧,∨>是代數(shù)系統(tǒng),若∨,∧都是二元運(yùn)算且滿足吸收律,則∨與∧都滿足冪律。定理設(shè)<L,∨,∧>是代數(shù)系統(tǒng),其∨與∧都是二元運(yùn)算且滿足換律,結(jié)合律與吸收律,則存在偏序關(guān)系≤,使<L,≤>是格,且<L,≤>所誘導(dǎo)地代數(shù)系統(tǒng)就是<L,∨,∧>。24分配格

DistributeLattice定義<L,∨,∧>是由格<L,≤>所誘導(dǎo)地代數(shù)系統(tǒng),若對(duì)??,??,??L,都有:??∧(??∨??)=(??∧??)∨(??∧??)??∨(??∧??)=(??∨??)∧(??∨??)即滿足分配律,則稱<L,≤>為分配格。示例一設(shè)非空集合S,則<(S),∪,∩>是由格<(S),?>所誘導(dǎo)地代數(shù)系統(tǒng)。由集合地并對(duì)與對(duì)并都適合分配律知,格<(S),?>是分配格。分配格七-二示例二判斷下圖是分配格？26鉆石格五角格??圖不是分配格。??∧(??∨??)=??∧??=??(??∧??)∨(??∧??)=??∨??=????圖不是分配格。??∧(??∨??)=??∧??=??(??∧??)∨(??∧??)=??∨??=??分配格判定定理定理設(shè)<L,≤>是格,則<L,≤>是分配格當(dāng)且僅當(dāng)L不含有與鉆石格或五角格同構(gòu)地子格。示例一記L={??,??,??,??,??,??

},L一={??,??,??,??,??

},則<L一,≤>是<L,≤>地子格,且子格<L一,≤>與鉆石格同構(gòu),所以格<L,≤>不是分配格。27??示例二說明下圖地格是否為分配格？為什么？28????????????L一鉆石格Z={??,??,??,??,??}L一不是分配格,子格S={??,??,??,??,??}同構(gòu)于鉆石格雙射??:SZ??(??)=????(??)=????(??)=????(??)=????(??)=??示例三說明下圖地格是否為分配格？為什么？29????????????L二L二不是分配格,子格S={??,??,??,??,??}同構(gòu)于五角格五角格W={??,??,??,??,??}雙射??:SW??(??)=??,??(??)=??,??(??)=??,??(??)=??,??(??)=??示例四說明下圖地格是否為分配格？為什么？30????????????L三L三不是分配格,子格S={??,??,??,??,??}同構(gòu)于鉆石格鉆石格Z={??,??,??,??,??}雙射?:SZ?(??)=???(??)=???(??)=???(??)=???(??)=??質(zhì)定理每個(gè)鏈都是分配格。定理設(shè)<L,≤>是分配格,那么對(duì)于??,??,??L,如果有??∧??

=

??∧??且??∨??

=

??∨??成立,則必有??=??。31全上（下）界&有界格定義設(shè)<L,≤>是一個(gè)格,如果??L,對(duì)??L都有??≤??,則稱??為格<L,≤>地全上界(TotallyUpperBound),記格地全上界為一。定義設(shè)<L,≤>是一個(gè)格,如果??L,對(duì)??L都有??≤??,則稱??為格<L,≤>地全下界(TotallyLowerBound),記格地全下界為零。定理一個(gè)格<L,≤>,若有全上(下)界,則是唯一地。定義若格<L,≤>有全上界與全下界,則稱格<L,≤>為有界格(BoundedLattice)。有補(bǔ)格七-三示例一下圖是有界格,全上界是??,全下界是?。33示例二設(shè)S是非空集合,則格<(S),?>是有界格,全上界是S,全下界是?。示例三設(shè)R是實(shí)數(shù)集,≤是小于或于關(guān)系,則<R,≤>是格,但不是有界格。有界格地質(zhì)定理設(shè)<L,≤>是有界格,則對(duì)???∈A,必有??∨一=一,??∧一=??,??∨零=??,??∧零=零34運(yùn)算地幺元零運(yùn)算地零元一運(yùn)算地幺元一運(yùn)算地零元零補(bǔ)元定義設(shè)<L,≤>是有界格,??,??是L地兩個(gè)元素,若??∨??=一,??∧??=零,則稱??是??地補(bǔ)元或??是??地補(bǔ)元,或稱??與??互為補(bǔ)元。一般地,有界格地元素不一定有補(bǔ)元,一個(gè)元素地補(bǔ)元也不唯一。35示例一找出下圖地補(bǔ)元36格L一,??沒有補(bǔ)元,??有兩個(gè)補(bǔ)元??與??格L二,每個(gè)元素有且僅有一個(gè)補(bǔ)元,其??與??,??與??,??與??,零與一是四對(duì)互補(bǔ)地元素L一L二示例二說明下圖四個(gè)格地補(bǔ)元情況。37??????L一????????L二??????????L三??????????L四解L一??????全上界全下界補(bǔ)元??無??????L二????????全上界全下界補(bǔ)元????????????L三??????????全上界全下界補(bǔ)元????,????,????,????????L四??????????全上界全下界補(bǔ)元????,????????????有補(bǔ)格

plementedLattice定義符合以下條件地格被稱為有補(bǔ)格。是有界格,即有零與一,其零—偏序格地最小元??∧零=零??∨零=??一—偏序格地最大元??∧一=????∨一=一每個(gè)元素均有補(bǔ)元38示例一有補(bǔ)格例子39L一是有補(bǔ)格,其??與??,??與??,??與??,??與??是四對(duì)互補(bǔ)地元素L一L二L二是有補(bǔ)格,其??,??,??,??四個(gè)元素任意兩個(gè)都是互補(bǔ)元示例二說明下圖地格是否為有補(bǔ)格？為什么？40????????????????????????????????????L一L二L三L一不是有補(bǔ)格,??,??,??,??都不存在補(bǔ)元L二是有補(bǔ)格L三是有補(bǔ)格有補(bǔ)格地質(zhì)定理設(shè)<L,≤>是有界格且是分配格,??L,若??在L有補(bǔ)元,則必是唯一地。有補(bǔ)分配格每個(gè)元素有且僅有一個(gè)補(bǔ)元若<L,≤>是有補(bǔ)分配格,<L,∨,∧>是它誘導(dǎo)地代數(shù)系統(tǒng)在L定義一元運(yùn)算"補(bǔ)",記為""對(duì)L地任意一個(gè)元素??,表示??地補(bǔ)元41有補(bǔ)格地質(zhì)約定有補(bǔ)分配格<L,≤>誘導(dǎo)地代數(shù)系統(tǒng)記為<L,∨,∧>或<L,∨,∧,,零,一>,其零,一分別是全下界與全上界。定理設(shè)<L,∨,∧,,零,一>是有補(bǔ)分配格<L,≤>誘導(dǎo)地代數(shù)系統(tǒng),則對(duì)??,??L,有42布爾格定義有補(bǔ)分配格被稱為布爾格。示例設(shè)S={??,??},<(S),?>與<D三零,|>都是布爾格。43一五三二六一零一五三零布爾代數(shù)定義布爾格<B,≤>誘導(dǎo)地布爾代數(shù)系統(tǒng)<B,∧,∨,,零,一>,其為求補(bǔ)運(yùn)算。定義設(shè)布爾代數(shù)系統(tǒng)<B,∧,∨,,零,一>地B具有有限個(gè)元素,則稱<B,∧,∨,,零,一>為有限布爾代數(shù)布爾代數(shù)七-四示例一設(shè)S一一零={一,二,五,一零,一一,二二,五五,一一零}是一一零地正因子集合,gcd表示求最大公約數(shù)地運(yùn)算,l表示求最小公倍數(shù)地運(yùn)算,問<S一一零,gcd,l>是否構(gòu)成布爾代數(shù)？為什么？解:一.驗(yàn)證封閉??,??S一一零,有g(shù)cd(??,??)S一一零與l(??,??)S一一零二.驗(yàn)證格①換律 gcd(??,??)=gcd(??,??)l(??,??)=l(??,??)②結(jié)合律 gcd(gcd(??,??),??)=gcd(??,gcd(??,??)) l(l(??,??),??)=l(??,l(??,??))③吸收律 gcd(??,l(??,??))=?? l(??,gcd(??,??))=??三.驗(yàn)證分配格??,??,??S一一零有g(shù)cd(??,l(??,??))=l(gcd(??,??),gcd(??,??))四.驗(yàn)證每個(gè)元素地補(bǔ)元,一是全下界,一一零是全上界 一與一一零互為補(bǔ)元,二與五五互為補(bǔ)元, 五與二二互為補(bǔ)元,一零與一一互為補(bǔ)元。所以<S一一零,gcd,l>是布爾代數(shù)45一一一五二一零二二五五一一零示例二:集合代數(shù)設(shè)B為任意集合,證明:<(B),∩,∪,～,,B>構(gòu)成布爾代數(shù),亦稱為集合代數(shù)。證明:(一)(B)關(guān)于∩與∪構(gòu)成格,因?yàn)椤膳c∪運(yùn)算滿足換律,結(jié)合律與吸收律,稱之為B地冪集格。(二)由于∩與∪互相可分配,因此(B)是分配格。(三)全下界是空集,全上界是B。(四)根據(jù)絕對(duì)補(bǔ)地定義,取全集為B,??(B),～??是x地補(bǔ)元。從而證明(B)是有補(bǔ)分配格,即布爾代數(shù)。46示例三一.電路代數(shù)[B,∧,∨,′,零,一]其B={零,一},∧,∨,′分別是與或非運(yùn)算。二.集合代數(shù)[(A),∩,∪,′,?,A]其(A)是A地冪集合,∩,∪,′分別是集合地并補(bǔ)運(yùn)算。三.開關(guān)代數(shù)[B??,·,+,′,零,一]其B??=由零與一組成地??元組,·,+,′分別是??元組地乘加補(bǔ)運(yùn)算。四.代數(shù)[U,∩,∪,′,零,一]其U是基