第十五格与布尔代数

第十五格与布尔代数第一页，共五十二页，2022年，8月28日在介绍格之前，对于我们在前面学过的偏序，我们要补充两个内容：1.哈斯图2.最小上界与最大下界第二页，共五十二页，2022年，8月28日1.哈斯图为了更清楚地描述偏序集合中元素间的层次关系,也为了更快、更有效地画出偏序关系的简化图,下面介绍“盖住”的概念。定义

在偏序集<A,≤>中,对x,yA,x≤y且xy,且A中无任何其它元素z,满足x≤z且z≤y,称y盖住x,或称x是y的直接前趋,y是x的直接后继。盖住关系记作cov(A)={(x,y)|x,yA且y盖住x}。第三页，共五十二页，2022年，8月28日显然盖住关系是唯一确定的,盖住关系是“≤”的子集。盖住关系的关系图称哈斯(Hasse)图,它实际上偏序关系是经过如下简化的关系图:1.省略关系图中的每个结点处的自环,这是因为偏序关系“≤”是自反的。2.若x<y且y盖住x,将代表y的结点放在代表x的结点之上,并在x与y之间连线,省去有向边的箭头,使其成为无向边。 若x<y但y不盖住x,则省去x与y之间的连线。第四页，共五十二页，2022年，8月28日例A={1,2,3,4,5,6,8,10,12,16,24},偏序关系是A上的整除关系“≤”,画出偏序集<A,≤>的哈斯图。我们先画出关系图。注意图中，并没有画出所有关系，否则画面更显凌乱。按照哈斯图的画法，去掉一部分，结果如左图。第五页，共五十二页，2022年，8月28日例以下是偏序集<P(X)，>的哈斯图。第六页，共五十二页，2022年，8月28日利用哈斯图，可以很方便的解决我们在学习偏序集中的一些问题：例偏序集<S,≤>，其中S={2,4,5,10,12,20,25}，≤是整除关系，求此偏序集的极大元和极小元。解：作出哈斯图，从图中看出，12,20和25是极大元，2和5是极小元。第七页，共五十二页，2022年，8月28日例确定下图中每个哈斯图表示的偏序集是否有最大元和最小元。解：a)的最小元是a，无最大元。b)既无最大元也无最小元。c)无最小元，最大元是d。d)的最小元是a，最大元是d。第八页，共五十二页，2022年，8月28日2.最小上界与最大下界定义

设集合X上有一个偏序关系“≤”且设Y是X的一个子集。（1）如果存在一个元素x∈X，对每个y'∈Y都有y'≤x，则称x是Y的上界(upperbound)；如果均有x≤y'，则称x是Y的下界(lowerbound)。（2）如果x∈X是Y的上界且对每一个Y的上界x'均有x≤x'，则称x是Y的最小上界（或上确界LUB，leastupperbound）；如果x∈X是Y的下界且对每一个Y的下界x'均有x'≤x，则称x是Y的最大下界（或下确界GLB，greatestlowerbound）第九页，共五十二页，2022年，8月28日例设有偏序集<A，≤>，其中A={2，4，6，8，12}，偏序关系是整除关系，试求{2，4}的上界和最小上界，{8，12}的下界和最大下界。解：{2，4}的上界是4，8，12，最小上界是4。{8，12}的下界是2，4，最大下界是4。第十页，共五十二页，2022年，8月28日例：找出下图所示哈斯图的偏序集的子集{a,b,c},{j,h}和{a,c,df}的下界和上界。解：{a,b,c}的上界是e,f,j,h，它唯一的下界是a。{j,h}没有上界，它的下界是a,b,c,d,e,f。{a,c,df}的上界是f,h,j，它的下界是a。第十一页，共五十二页，2022年，8月28日例在上图所示偏序集中，如果{b,d,g}的最大下界和最小上界存在，求出这个最大下界和最小上界。解：{b,d,g}的上界是g,h，故它的最小上界是g。{b,d,g}的下界是a,b，故它的最大下界是b。第十二页，共五十二页，2022年，8月28日15.1格(lattice)1．格作为偏序集定义

设<L,≤>是一个偏序集，若对任意a,bL，存在最大下界(GLB)和最小上界(LUB)，则称<L,≤>为格。用ab表示LUB{a,b}，ab表示GLB{a,b}，并称和分别为L上的并（或和）和交（或积）运算。这样我们由偏序关系定义了两种二元运算。有时也用∨和∧分别表示和

。因此，格有时也表示成<L,,>或<L,∨,∧>。第十三页，共五十二页，2022年，8月28日显然，对于ab，有：①ab≤a和ab≤b，则表明ab是a和b的下界。②若c≤a和c≤b，则c≤ab，这表明ab是a和b的最大下界。对于ab，有：①a≤ab和b≤ab，则表明ab是a和b的上界。②若a≤c，且b≤c，则ab≤c，这表明ab是a和b的最小上界。第十四页，共五十二页，2022年，8月28日例

设n为正整数，Sn为n的正因子的集合，≤为整除关系，则<Sn，≤>构成格。因为x，y∈Sn，xy就是x，y的最小公倍数，xy是x，y的最大公约数。第十五页，共五十二页，2022年，8月28日例

幂集P(A)上的包含关系定义了一个偏序关系，P(A)中任意两个元素x，y，有xy=x∪yxy=x∩y因此，<P(A),>是一个格。第十六页，共五十二页，2022年，8月28日注意：并非每个偏序集都是格。如，设A＝{2,3,6,8},“整除”关系R={‹2,2›,‹2,6›,‹2,8›,‹3,3›,‹3,6›,‹6,6›,‹8,8›}是A上的一个偏序关系，则<A，R>是一个偏序集，但不是格。因为23不存在，68也不存在。第十七页，共五十二页，2022年，8月28日例确定下图中每个哈斯图表示的偏序集是不是格。解：在a)和c)中的哈斯图表示的偏序集是格。因为每个偏序集中每对元素都有最小上界和最大下界。

b)所示的哈斯图的偏序集不是格，例如元素b和c没有最小上界。只要注意到d,e,f中每一个都是上界，但这3个元素的任何一个关于这个偏序集中的序都不小于其它两个。第十八页，共五十二页，2022年，8月28日练习：确定下图中每个哈斯图表示的偏序集是不是格。除c外，其余都是格。因为c中最下两个元素既没有上确界也没有下确界。第十九页，共五十二页，2022年，8月28日格的对偶性原理是成立的：令<L,≤>是偏序集，且<L,≥>是其对偶的偏序集。若<L,≤>是格，则<L,≥>也是格，反之亦然。这是因为，对于L中任意a和b，<L,≤>中LUB{a,b}等同于<L,≥>中GLB{a,b}，<L,≤>中GLB{a,b}等同于<L,≥>中的LUB{a,b}。若L是有限集，这些性质易从偏序集及其对偶的哈斯图得到验证。第二十页，共五十二页，2022年，8月28日从上讨论中，可知两格互为对偶。互为对偶的两个<L,≤>和<L,≥>有着密切关系，即格<L,≤>中交运算正是格<L,≥>中的并运算，而格<L,≤>中的并运算正是格<L,≥>中的交运算。因此，给出关于格一般性质的任何有效命题，把关系≤换成≥（或者≥换成≤），交换成并，并换成交，可得到另一个有效命题，这就是关于格的对偶性原理。第二十一页，共五十二页，2022年，8月28日定义设<L,∨,∧>是一个格，S是L的非空子集，如果S关于运算∨和∧是封闭的，则称<S,∨,∧>是<L,∨,∧>的子格。显然，子格本身是一个格。

第二十二页，共五十二页，2022年，8月28日例如：设<S,≤>是一个格，其中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}问，其中哪些构成格？哪些是<S,≤>的子格？<S1,≤>,<S2,≤>是<S,≤>的子格，而<S3,≤>虽然是格，但不是<S,≤>的子格，因为b∧d=fS3。hfcbedga第二十三页，共五十二页，2022年，8月28日2．格的基本性质定理1

设<L,≤>是格，对任意a,bL，有 ①ab=ba≤b ②ab=aa≤b ③ab=aab=b亦即a≤bab=bab=a第二十四页，共五十二页，2022年，8月28日定理2

设<L,≤>是格，对任意a,bL，有①aa=a,bb=b （等幂律）②ab=ba,ab=ba （交换律）③a(bc)=(ab)c, a(bc)=(ab)c（结合律）④a(ab)=a, a(ab)=a （吸收律）第二十五页，共五十二页，2022年，8月28日定理3

设<L,≤>是格，对任意a,b,cL，有①若a≤b和c≤d，则ac≤bd，ac≤bd。②若a≤b，则ac≤bc，ac≤bc。（保序性）第二十六页，共五十二页，2022年，8月28日定理4

设<L,≤>是格，对任意的a,b,cL，有①a(bc)≤(ab)(ac)②(ab)(ac)≤a(bc)通常称上二式为格中分配不等式。第二十七页，共五十二页，2022年，8月28日3．特殊的格定义设<L,≤>是格，若L中有最大元和最小元，则称<L,≤>为有界格。由于最大（小）元存在必唯一，故一般把格中最大元记为1，最小元记为0。由定义可知，对任意aL，有①0≤a≤1②a0=0,a0=a③a1=a,a1=1由此可知，0是<L,≤>关于的零元，关于的幺元；1是<L,≤>关于的幺元，关于的零元第二十八页，共五十二页，2022年，8月28日例：试判断下面哪些是有界格？

×√√第二十九页，共五十二页，2022年，8月28日定义：若L是有限集合，称<L,≤>为有限格。定理5

设<L,≤>是有限格，其中L={a1,a2,···,an}，则<L,≤>是有界格。第三十页，共五十二页，2022年，8月28日定义设<L,≤>是格，对任意的a,b,cL，有①a(bc)=(ab)(ac)②(ab)(ac)=a(bc)则称<L,≤>为分配格，称①和②为格中分配律。第三十一页，共五十二页，2022年，8月28日分配格的性质性质1：如果①交对并可分配，则②并对交也一定是可分配的，反之亦然。只证前半部分，即由①推②：(ab)(ac)＝((ab)a)((ab)c)（由①）＝(aa)(ab)(ca)(cb)（由①,交换律）＝a(ab)(ac)(bc)＝a(bc)（吸收律）注：此性质说明，分配格的定义可以简化成只需满足①或②其中之一即可。第三十二页，共五十二页，2022年，8月28日性质2：每个链<L,≤>都是分配格。（|L|≥3）链链第三十三页，共五十二页，2022年，8月28日例：试判断下面两个哈斯图是否表示的是分配格？显然(1)是格，但因为b(cd)=ba=b，而(bc)(bd)=ee=e，故它不是分配格；显然(2)也是格，但因为c(bd)=ca=c，而(cb)(cd)=ed=d，故它也不是分配格，注：上面两个具有五个元素的格是很重要的，因为有这样的定理：一个格是分配格的充要条件是，在该格中没有任何子格与这两个五元素格中的任何一个同构。bcdae(1)bcdea(2)第三十四页，共五十二页，2022年，8月28日我们知道，验证一个格是不是分配格是很复杂的，可以利用上面这个定理判断一个格不是分配格。如(3)中，容易验证<{a,b,c,e,g},≤>是<{a,b,c,d,e,f,g},≤>的子格，且与(1)同构，或者容易验证<{a,b,c,f,g},≤>是<{a,b,c,d,e,f,g},≤>的子格，且与(2)同构，故不是分配格。从而判断它不是分配格。bcdae(1)bcdea(2)abcfgde(3)第三十五页，共五十二页，2022年，8月28日例：证明<Sn,≤>是一个分配格。证：设∧和∨分别为Sn上的交（或积）和并（或和）运算，对于任意a，b，c∈Sn，有a∨(b∧c)=lcm(a,gcd(b,c))=gcd(lcm(a,b),lcm(a,c))=(a∨b∧(a∨c)a∧(b∨c)=gcd(a,lcm(b,c))=lcm(gcd(a,b),gcd(a,c))=(a∧b)∨(a∧c)（事实上，上面是利用“最大公约数对最小公倍数是分配的，最小公倍数对最大公约数也是分配的”这个性质）故<Sn，|>是一个分配格。第三十六页，共五十二页，2022年，8月28日在介绍有补格之前，先介绍补元的定义。定义设<L,≤>是有界格，对于aL，存在bL，使得ab=0，ab=1称b为a的补元，记为a'。由定义可知，若b是a的补元，则a也是b的补元，即a与b互为补元。显然，0'=1和1'=0。一般说来，一个元素可以有其补元，未必唯一，也可能无补元。第三十七页，共五十二页，2022年，8月28日例：试判断下图中每个元素有无补元，若有，写出补元。1,0显然互为补元；a的补元是e，c的补元是d；b没有补元；d的补元是c和e，e的补元是a和d。1acedb0第三十八页，共五十二页，2022年，8月28日关于补元，有下面的性质：定理6

设<L,≤>是有界分配格，若aL，且补元存在，则其补元是唯一的。下面介绍有补格的定义。第三十九页，共五十二页，2022年，8月28日定义设<L,≤>是格，若L中每个元素至少有一补元，则称<L,≤>为有补格。由于补元的定义是在有界格中给出的，可知，有补格一定是有界格。第四十页，共五十二页，2022年，8月28日例：试判断下图中哪些是有补格？√√√×

第四十一页，共五十二页，2022年，8月28日定义若一格既是有补又是分配的，则称该格为有补分配格，或布尔格，或布尔代数。关于有补分配格，有下面几个性质：第四十二页，共五十二页，2022年，8月28日定理7

设<L,≤>是有补分配格，若任意元素aL，则a的补元a'是唯一的。该定理6的直接推论，因为有补分配格当然是有界分配格。由于有补分配格中，每个元素a都有唯一的补元a'，因此可在L上定义一个一元运算—补运算“'”。这样，有补分配格可看作具有两个二元运算和一个一元运算的代数结构，习惯上称它为布尔代数，记为<B,,,',0,1>，其中B=L。第四十三页，共五十二页，2022年，8月28日定理8

设<L,≤>是有补分配格，对任意a,bL，则①(a')'=a②(ab)'=a'b'③(ab)'=a'b'后两式称为格中德·摩根律。第四十四页，共五十二页，2022年，8月28日定理9

设<L,≤>是有补分配格，对任意a,bL，有

a≤bab'=0 a'b=1格同态，格直积等概念可以接下来定义和研究，但这里不打算这样做，因为如此进行会相对较繁，而是将格作为一个代数结构而引入它们。第四十五页，共五十二页，2022年，8月28日4．代数结构所诱导的偏序集确立的格前面我们已知，有补分配格是一个代数结构，叫做布尔代数；反之，由代数结构也可以导出格。定义设<L,,>是一代数结构，其中和是L上满足交换律、结合律和吸收律的二元运算，且对任意a,bL，定义偏序关系≤如下：a≤bab=a则<L,≤>是格，称<L,≤>为代数结构<L,,>所诱导的偏序集确立的格。第四十六页，共五十二页，2022年，8月28日15.2布尔代数前已指出，布尔代数是有补分配格，常记为<B,,,‘,0,1>，因此，它具有格、有界格、分配格、有补格的所有性质。我们把这些性质罗列如下：对任意a,b,cB，有第四十七页，共五十二页，2022年，8月28日①<B,,>是格，且≤为B上由或所定义的偏序关系，满足(L-1)ab=LUB{a,b}，ab=GLB{a,b}(L-2)a≤bab=bab=a(L-3)aa=a，aa=a（等幂律）(L-4)ab=ba，ab=ba（交换律）(L-5)(ab)c=a(bc)，

(ab)c=a(bc)（结合律）(L-6)a(ab)=a，a(ab)=a（吸收律）第四十八页，共五十二页，2022年，8月28日②<B,,>是分配格，满足(D-1)a(bc)=(ab)(ac)，

a(bc)=(ab)(ac)