离散数学-格与布尔代数

离散数学

DiscreteMathematics主讲:郝晓燕二零二一年九月一六日～二零二一年一二月一八日学时:五六学分:三.五第七章格与布尔代数

Lattice&BooleanAlgebra一格二分配格三有补格四布尔代数第七章格与布尔代数Lattice&BooleanAlgebra4格论

戴德金(Dedekind,一八三一～一九一六)5德数学家数学王子高斯地最后一位学生继承了库莫(Kummer)在数论上地工作主要成就是在代数理论方面研究过任意域,环,群,结构与模问题在授课时率先引入了环（域）地概念,并给理想子环下了一般定义提出了能与自己地真子集建立一一对应地集合是无穷集地思想布尔代数地发展英数学家G.布尔为了研究思维规律(逻辑学,数理逻辑)于一八四七与一八五四年提出地数学模型。此后R.戴德金把它作为一种特殊地格。布尔代数由于缺乏物理背景,所以研究缓慢,到了二零世纪三零～四零年代才又有了新地展,在代数结构,逻辑演算,集合论,拓扑空间理论,测度论,概率论,泛函分析数学分支均有应用。一九六七年后,在数理逻辑地分支之一地公理化集合论以与模型论地理论研究也起着一定地作用。近几十年来,布尔代数在自动化技术,电子计算机地逻辑设计工程技术领域有重要地应用。§七-一-一格地概念定义七-一.一设<S,≼>是偏序集,如果x,yS,{x,y}都有最小上界与最大下界,那么称S关于偏序≼构成一个格,或称<S,≼>为偏序格,或简称<S,≼>为格（lattice）。七-一示例二S是非空集合,(S)是S地幂集,则<(S),⊆>是格。因为A,B⊆S,都有A,B地最小上界为A∪B;A,B地最大下界为A∩B。8

{𝑐}{𝑏}{𝑎}{𝑎,𝑏}{𝑎,𝑐}{𝑏,𝑐}{𝑎,𝑏,𝑐}示例三设N+是所有正整数集合,定义N+上地整除关系|。<N+,|>是偏序集。任意两个元素地最小公倍数,最大公约数分别是这两个元素地最小上界与最大下界,因此<N+,|>是格。示例四设集合A={𝑎,𝑏,𝑐},考虑恒关系=,<A,=>是偏序集,但它不是格。因为A任意两个元素都是既无最小上界又无最大下界,<A,=>地Hass如下。9示例五设P={二,三,六,一二,二四,三六},S={一,二,三,一二,一八,三六},<P,|>与<S,|>都不是格。10三二二四一二六三六三六三二一八一二一格诱导地代数系统定义设<S,≤>是格,如果在S上定义两个二元运算∨与∧,使得对于𝑥,𝑦S,𝑥∨𝑦于𝑥与𝑦地最小上界,𝑥∧𝑦于𝑥与𝑦地最大下界。则称<S,∨,∧>为由格<S,≤>所诱导地代数系统。其,二元运算∨与∧分别称为并运算与运算。11示例一对给定地集合S={𝑥,𝑦},<(S),⊆>是格,诱导地代数系统为<(S),∨,∧>,A,B(S),A∨B=A∪B,A∧B=A∩B。12∨

{𝑥}{𝑦}{𝑥,𝑦}

{𝑥}{𝑦}{𝑥,𝑦}{𝑥}{𝑥}{𝑥}{𝑥,𝑦}{𝑥,𝑦}{𝑦}{𝑦}{𝑥,𝑦}{𝑦}{𝑥,𝑦}{𝑥,𝑦}{𝑥,𝑦}{𝑥,𝑦}{𝑥,𝑦}{𝑥,𝑦}∧

{𝑥}{𝑦}{𝑥,𝑦}

{𝑥}

{𝑥}

{𝑥}{𝑦}

{𝑦}{𝑦}{𝑥,𝑦}

{𝑥}{𝑦}{𝑥,𝑦}示例二设D三六是三六地全部正因子地集合,D三六={一,二,三,四,六,九,一二,一八,三六},"|"表示数地整除关系,则<D三六,|>是格,对𝑚,𝑛D三六,𝑚∨𝑛=l{𝑚,𝑛}最小公倍数,𝑚∧𝑛=gcd{𝑚,𝑛}最大公约数。代数系统<D三六,∨,∧>13子格定义设<L,≤>是格,由<L,≤>诱导地代数系统为<L,∨,∧>,设S是L地非空子集,若S关于L地运算∧与∨是封闭地,则称<S,≤>是<L,≤>地子格。14示例一给出格<N+,|>,由它诱导地代数系统为<N+,∨,∧>,其,对𝑥,𝑦N+,𝑥∨𝑦=l{𝑥,𝑦}𝑥∧𝑦=gcd{𝑥,𝑦}<D三六,|>是<N+,|>地子格。E+表示全体正偶数集,<E+,|>是<N+,|>地子格。示例二设<L,≤>是格,其L={𝑎,𝑏,𝑐,𝑑,𝑒,𝑓,𝑔,ℎ}。子集L𝑖是<L,≤>地子格吗？L一={𝑎,𝑏,𝑑,𝑓}TL二={𝑐,𝑒,𝑔,ℎ}TL三={𝑒,𝑓,ℎ}FL四={𝑎,𝑑,𝑔,ℎ,𝑒}F示例三根据格L地哈斯图,判断L一,L二,L三是L地子格吗？L一={零,𝑎,𝑏}TL二={𝑎,𝑐}TL三={零,𝑎,𝑏,𝑐}F15一𝑏𝑎零𝑐格地同态与同构定义设<L一,一>,<L二,二>都是格,由它们分别诱导地代数系统<L一,∨一,∧一>与<L二,∨二,∧二>,若存在映射𝑓:L一→L二使得对𝑥,𝑦L一有𝑓(𝑥∧一𝑦)=𝑓(𝑥)∧二𝑓(𝑦)𝑓(𝑥∨一𝑦)=𝑓(𝑥)∨二𝑓(𝑦)则称𝑓为从<L一,∨一,∧一>到<L二,∨二,∧二>地格同态,亦称<𝑓(L一),二>是<L一,一>地格同态象。定义若𝑓是格同态且双射,则称𝑓是从<L一,∨一,∧一>到<L二,∨二,∧二>地格同构。定义设<P,>,<Q,>是两偏序集,若存在映射𝑓:PQ使得对𝑎,𝑏P有𝑎𝑏𝑓(𝑎)𝑓(𝑏)则称𝑓为保序映射。示例一设L={一,二,三,六},𝑎,𝑏L,有𝑎∧L𝑏=gcd{𝑎,𝑏},𝑎∨L𝑏=l{𝑎,𝑏}S={七,八},𝑎,𝑏S,有𝑎∧S𝑏=min{𝑎,𝑏},𝑎∨S𝑏=max{𝑎,𝑏}映射𝑔:LS,𝑔(一)=𝑔(二)=𝑔(三)=七,𝑔(六)=八,𝑔不是格同态。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{七,八}=八示例二设L={一,二,三,六},𝑎,𝑏L, 𝑎∧L𝑏=gcd{𝑎,𝑏},𝑎∨L𝑏=l{𝑎,𝑏};S={七,八},𝑎,𝑏S, 𝑎∧S𝑏=min{𝑎,𝑏},𝑎∨S𝑏=max{𝑎,𝑏}映射𝑔:LS,问𝑔𝑖是格同态吗？𝑔一(一)=七,𝑔一(二)=𝑔一(三)=𝑔一(六)=八;𝑔二(一)=𝑔二(三)=七,𝑔二(二)=𝑔二(六)=八.解:𝑔一不是格同态,𝑔二是格同态18示例三设L={一,二,三,六},𝑎,𝑏L, 𝑎∧L𝑏=gcd{𝑎,𝑏},𝑎∨L𝑏=l{𝑎,𝑏};映射𝑔:LL,𝑔(一)=一,𝑔(二)=三,𝑔(三)=二,𝑔(六)=六,𝑔是格同构。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{二,六}=六§七-一-二格地质定理对于集合S地任何偏序关系≤,其逆关系≥也是S地偏序关系。定理<L,≤>是格,<L,≥>也一定是格。格七-一20格地对偶原理定义设P对任意格都是真命题,如果在命题P把≤换成≥,∨换成∧,∧换成∨,就得到另一命题P',把P'称为P地对偶命题,则P'对任意格也是真命题。21许多格地质都是互为对偶命题地。有了格地对偶原理,在证明格地质时,只需求证明其地一个命题即可。格地质定理在格<L,≤>,对𝑎,𝑏,𝑐,𝑑L都有(一)𝑎≤𝑎∨𝑏,𝑏≤𝑎∨𝑏,𝑎∧𝑏≤𝑎,𝑎∧𝑏≤𝑏(二)若𝑎≤𝑏且𝑐≤𝑑,则𝑎∨𝑐≤𝑏∨𝑑,𝑎∧𝑐≤𝑏∧𝑑推论在格<L,≤>,对𝑎,𝑏,𝑐L,若𝑎≤𝑏,则𝑎∨𝑐≤𝑏∨𝑐,𝑎∧𝑐≤𝑏∧𝑐。22运算质定理设<L,≤>是一个格,由格<L,≤>所诱导地代数系统为<L,∨,∧>,则对𝑎,𝑏,𝑐L,有23幂律𝑎∨𝑎=𝑎;𝑎∧𝑎=𝑎换律𝑎∨𝑏=𝑏∨𝑎;𝑎∧𝑏=𝑏∧𝑎结合律𝑎∨(𝑏∨𝑐)=(𝑎∨𝑏)∨𝑐;𝑎∧(𝑏∧𝑐)=(𝑎∧𝑏)∧𝑐吸收率𝑎∨(𝑎∧𝑏)=𝑎;𝑎∧(𝑎∨𝑏)=𝑎分配不式𝑎(𝑏𝑐)≤(𝑎𝑏)(𝑎𝑐);(𝑎𝑏)(𝑎𝑐)≤𝑎(𝑏𝑐)𝑎≤𝑏𝑎𝑏=𝑎𝑎𝑏=𝑏𝑎≤𝑐𝑎(𝑏𝑐)≤(𝑎𝑏)𝑐(𝑎𝑏)(𝑎𝑐)≤𝑎(𝑏(𝑎𝑐));𝑎(𝑏(𝑎𝑐))≤(𝑎𝑏)(𝑎𝑐)运算质引理设<L,∧,∨>是代数系统,若∨,∧都是二元运算且满足吸收律,则∨与∧都满足幂律。定理设<L,∨,∧>是代数系统,其∨与∧都是二元运算且满足换律,结合律与吸收律,则存在偏序关系≤,使<L,≤>是格,且<L,≤>所诱导地代数系统就是<L,∨,∧>。24分配格

DistributeLattice定义<L,∨,∧>是由格<L,≤>所诱导地代数系统,若对𝑎,𝑏,𝑐L,都有:𝑎∧(𝑏∨𝑐)=(𝑎∧𝑏)∨(𝑎∧𝑐)𝑎∨(𝑏∧𝑐)=(𝑎∨𝑏)∧(𝑎∨𝑐)即满足分配律,则称<L,≤>为分配格。示例一设非空集合S,则<(S),∪,∩>是由格<(S),⊆>所诱导地代数系统。由集合地并对与对并都适合分配律知,格<(S),⊆>是分配格。分配格七-二示例二判断下图是分配格？26钻石格五角格𝑎图不是分配格。𝑏∧(𝑐∨𝑑)=𝑏∧𝑒=𝑏(𝑏∧𝑐)∨(𝑏∧𝑑)=𝑎∨𝑎=𝑎𝑏图不是分配格。𝑐∧(𝑏∨𝑑)=𝑐∧𝑎=𝑐(𝑐∧𝑏)∨(𝑐∧𝑑)=𝑒∨𝑑=𝑑分配格判定定理定理设<L,≤>是格,则<L,≤>是分配格当且仅当L不含有与钻石格或五角格同构地子格。示例一记L={𝑎,𝑏,𝑐,𝑑,𝑒,𝑓

},L一={𝑎,𝑏,𝑐,𝑑,𝑓

},则<L一,≤>是<L,≤>地子格,且子格<L一,≤>与钻石格同构,所以格<L,≤>不是分配格。27𝑓示例二说明下图地格是否为分配格？为什么？28𝑎𝑑𝑐𝑏𝑒𝑓L一钻石格Z={𝑎,𝑏,𝑐,𝑑,𝑒}L一不是分配格,子格S={𝑎,𝑏,𝑐,𝑑,𝑒}同构于钻石格双射𝑓:SZ𝑓(𝑎)=𝑒𝑓(𝑏)=𝑏𝑓(𝑐)=𝑐𝑓(𝑑)=𝑑𝑓(𝑒)=𝑎示例三说明下图地格是否为分配格？为什么？29𝑎𝑑𝑐𝑏𝑒𝑓L二L二不是分配格,子格S={𝑎,𝑏,𝑐,𝑒,𝑓}同构于五角格五角格W={𝑎,𝑏,𝑐,𝑑,𝑒}双射𝑔:SW𝑔(𝑎)=𝑒,𝑔(𝑏)=𝑏,𝑔(𝑐)=𝑑,𝑔(𝑒)=𝑐,𝑔(𝑓)=𝑎示例四说明下图地格是否为分配格？为什么？30𝑎𝑑𝑐𝑏𝑒𝑓L三L三不是分配格,子格S={𝑎,𝑏,𝑐,𝑒,𝑓}同构于钻石格钻石格Z={𝑎,𝑏,𝑐,𝑑,𝑒}双射ℎ:SZℎ(𝑎)=𝑒ℎ(𝑏)=𝑐ℎ(𝑐)=𝑏ℎ(𝑒)=𝑑ℎ(𝑓)=𝑎质定理每个链都是分配格。定理设<L,≤>是分配格,那么对于𝑎,𝑏,𝑐L,如果有𝑎∧𝑏

=

𝑎∧𝑐且𝑎∨𝑏

=

𝑎∨𝑐成立,则必有𝑏=𝑐。31全上（下）界&有界格定义设<L,≤>是一个格,如果𝑎L,对𝑥L都有𝑥≤𝑎,则称𝑎为格<L,≤>地全上界(TotallyUpperBound),记格地全上界为一。定义设<L,≤>是一个格,如果𝑏L,对𝑥L都有𝑏≤𝑥,则称𝑏为格<L,≤>地全下界(TotallyLowerBound),记格地全下界为零。定理一个格<L,≤>,若有全上(下)界,则是唯一地。定义若格<L,≤>有全上界与全下界,则称格<L,≤>为有界格(BoundedLattice)。有补格七-三示例一下图是有界格,全上界是𝑎,全下界是ℎ。33示例二设S是非空集合,则格<(S),⊆>是有界格,全上界是S,全下界是∅。示例三设R是实数集,≤是小于或于关系,则<R,≤>是格,但不是有界格。有界格地质定理设<L,≤>是有界格,则对∀𝑎∈A,必有𝑎∨一=一,𝑎∧一=𝑎,𝑎∨零=𝑎,𝑎∧零=零34运算地幺元零运算地零元一运算地幺元一运算地零元零补元定义设<L,≤>是有界格,𝑎,𝑏是L地两个元素,若𝑎∨𝑏=一,𝑎∧𝑏=零,则称𝑎是𝑏地补元或𝑏是𝑎地补元,或称𝑎与𝑏互为补元。一般地,有界格地元素不一定有补元,一个元素地补元也不唯一。35示例一找出下图地补元36格L一,𝑎没有补元,𝑏有两个补元𝑑与𝑐格L二,每个元素有且仅有一个补元,其𝑎与𝑎,𝑏与𝑏,𝑐与𝑐,零与一是四对互补地元素L一L二示例二说明下图四个格地补元情况。37𝑎𝑐𝑏L一𝑏𝑐𝑑𝑎L二𝑎𝑑𝑐𝑏𝑒L三𝑎𝑑𝑐𝑏𝑒L四解L一𝑎𝑏𝑐全上界全下界补元𝑐无𝑎𝑐𝑎L二𝑎𝑏𝑐𝑑全上界全下界补元𝑑𝑐𝑏𝑎𝑑𝑎L三𝑎𝑏𝑐𝑑𝑒全上界全下界补元𝑒𝑐,𝑑𝑏,𝑑𝑏,𝑐𝑎𝑒𝑎L四𝑎𝑏𝑐𝑑𝑒全上界全下界补元𝑒𝑐,𝑑𝑏𝑏𝑎𝑒𝑎有补格

plementedLattice定义符合以下条件地格被称为有补格。是有界格,即有零与一,其零—偏序格地最小元𝑥∧零=零𝑥∨零=𝑥一—偏序格地最大元𝑥∧一=𝑥𝑥∨一=一每个元素均有补元38示例一有补格例子39L一是有补格,其𝑎与𝑏,𝑎与𝑑,𝑐与𝑏,𝑐与𝑑是四对互补地元素L一L二L二是有补格,其𝑎,𝑏,𝑐,𝑑四个元素任意两个都是互补元示例二说明下图地格是否为有补格？为什么？40𝑎𝑑𝑐𝑏𝑒𝑓𝑎𝑑𝑐𝑏𝑒𝑓𝑎𝑑𝑐𝑏𝑒𝑓L一L二L三L一不是有补格,𝑏,𝑐,𝑑,𝑒都不存在补元L二是有补格L三是有补格有补格地质定理设<L,≤>是有界格且是分配格,𝑎L,若𝑎在L有补元,则必是唯一地。有补分配格每个元素有且仅有一个补元若<L,≤>是有补分配格,<L,∨,∧>是它诱导地代数系统在L定义一元运算"补",记为""对L地任意一个元素𝑎,表示𝑎地补元41有补格地质约定有补分配格<L,≤>诱导地代数系统记为<L,∨,∧>或<L,∨,∧,,零,一>,其零,一分别是全下界与全上界。定理设<L,∨,∧,,零,一>是有补分配格<L,≤>诱导地代数系统,则对𝑎,𝑏L,有42布尔格定义有补分配格被称为布尔格。示例设S={𝑥,𝑦},<(S),⊆>与<D三零,|>都是布尔格。43一五三二六一零一五三零布尔代数定义布尔格<B,≤>诱导地布尔代数系统<B,∧,∨,,零,一>,其为求补运算。定义设布尔代数系统<B,∧,∨,,零,一>地B具有有限个元素,则称<B,∧,∨,,零,一>为有限布尔代数布尔代数七-四示例一设S一一零={一,二,五,一零,一一,二二,五五,一一零}是一一零地正因子集合,gcd表示求最大公约数地运算,l表示求最小公倍数地运算,问<S一一零,gcd,l>是否构成布尔代数？为什么？解:一.验证封闭𝑥,𝑦S一一零,有gcd(𝑥,𝑦)S一一零与l(𝑥,𝑦)S一一零二.验证格①换律 gcd(𝑥,𝑦)=gcd(𝑦,𝑥)l(𝑥,𝑦)=l(𝑦,𝑥)②结合律 gcd(gcd(𝑥,𝑦),𝑧)=gcd(𝑥,gcd(𝑦,𝑧)) l(l(𝑥,𝑦),𝑧)=l(𝑥,l(𝑦,𝑧))③吸收律 gcd(𝑥,l(𝑥,𝑦))=𝑥 l(𝑥,gcd(𝑥,𝑦))=𝑥三.验证分配格𝑥,𝑦,𝑧S一一零有gcd(𝑥,l(𝑦,𝑧))=l(gcd(𝑥,𝑦),gcd(𝑥,𝑧))四.验证每个元素地补元,一是全下界,一一零是全上界 一与一一零互为补元,二与五五互为补元, 五与二二互为补元,一零与一一互为补元。所以<S一一零,gcd,l>是布尔代数45一一一五二一零二二五五一一零示例二:集合代数设B为任意集合,证明:<(B),∩,∪,～,,B>构成布尔代数,亦称为集合代数。证明:(一)(B)关于∩与∪构成格,因为∩与∪运算满足换律,结合律与吸收律,称之为B地幂集格。(二)由于∩与∪互相可分配,因此(B)是分配格。(三)全下界是空集,全上界是B。(四)根据绝对补地定义,取全集为B,𝑥(B),～𝑥是x地补元。从而证明(B)是有补分配格,即布尔代数。46示例三一.电路代数[B,∧,∨,′,零,一]其B={零,一},∧,∨,′分别是与或非运算。二.集合代数[(A),∩,∪,′,∅,A]其(A)是A地幂集合,∩,∪,′分别是集合地并补运算。三.开关代数[B𝑛,·,+,′,零,一]其B𝑛=由零与一组成地𝑛元组,·,+,′分别是𝑛元组地乘加补运算。四.代数[U,∩,∪,′,零,一]其U是基