格与布尔代数简.pptx

第十五章第十五章 格与布尔代数格与布尔代数15.1 格15.2 布尔代数在介绍格之前，对于我们在前面学过的偏序，我们要补充两个内容：1.哈斯图2.最小上界与最大下界1.哈斯图为了更清楚地描述偏序集合中元素间的层次关系,也为了更快、更有效地画出偏序关系的简化图,下面介绍“盖住”的概念。定义 在偏序集中,对x,yA,xy且x y,且 A中无任何其它元素z,满足xz且zy,称y盖住x,或称x是y的直接前趋,y是x的直接后继。盖住关系记作cov(A)=(x,y)|x,yA且y盖住x。显然盖住关系是唯一确定的,盖住关系是“”的子集。盖住关系的关系图称哈斯(Hasse)图,它实际上偏序关系是经过如下简化的关系图:1.省略关系图中的每个结点处的自环,这是因为偏序关系“”是自反的。2.若xy且y盖住x,将代表y的结点放在代表x的结点之上,并在x与y之间连线,省去有向边的箭头,使其成为无向边。若xy 但y不盖住x,则省去x与y之间的连线。例例 A=1,2,3,4,5,6,8,10,12,16,24,偏序偏序关系是关系是A上的整除关系上的整除关系“”,画出偏序集画出偏序集的哈斯图。的哈斯图。我们先画出关系图。我们先画出关系图。注意图中，并没有注意图中，并没有画出所有关系，否画出所有关系，否则画面更显凌乱。则画面更显凌乱。按照哈斯图的画法，按照哈斯图的画法，去掉一部分，结果去掉一部分，结果如左图。如左图。例 以下是偏序集的哈斯图。利用哈斯图，可以很方便的解决我们在学习偏序集中的一些问题：例 偏序集，其中S=2,4,5,10,12,20,25，是整除关系，求此偏序集的极大元和极小元。解：作出哈斯图，从图中看出，12,20和25是极大元，2和5是极小元。例 确定下图中每个哈斯图表示的偏序集是否有最大元和最小元。解：a)的最小元是a，无最大元。b)既无最大元也无最小元。c)无最小元，最大元是d。d)的最小元是a，最大元是d。2.最小上界与最大下界定义 设集合X上有一个偏序关系“”且设Y是X的一个子集。（1）如果存在一个元素xX，对每个yY都有yx，则称x是Y的上界(upper bound)；如果均有xy，则称x是Y的下界(lower bound)。（2）如果xX是Y的上界且对每一个Y的上界x均有xx，则称x是Y的最小上界（或上确界LUB，least upper bound）；如果xX是Y的下界且对每一个Y的下界x均有xx，则称x是Y的最大下界（或下确界GLB，greatest lower bound）例：找出下图所示哈斯图的偏序集的子集a,b,c,j,h和a,c,d f的下界和上界。解：a,b,c的上界是e,f,j,h，它唯一的下界是a。j,h没有上界，它的下界是a,b,c,d,e,f。a,c,d f的上界是f,h,j，它的下界是a。例 在上图所示偏序集中，如果b,d,g的最大下界和最小上界存在，求出这个最大下界和最小上界。解：b,d,g的上界是g,h，故它的最小上界是g。b,d,g的下界是a,b，故它的最大下界是b。15.1 格格(lattice)1格作为偏序集定义15.1.1 设是一个偏序集，若对任意a,bL，存在 最大下界(GLB)和最小上界(LUB)，则称为格。用ab表示GLBa,b，ab表示LUBa,b，并称和分别为L上的交（或积）和并（或和）运算。这样我们由偏序关系定义了两种二元运算。若L是有限集合，称为有限格。显然，对于ab，有：aba和abb，则表明ab是a和b的下界。若ca和cb，则cab，这表明ab是a和b的最大下界。对于ab，有：aab和bab，则表明ab是a和b的上界。若ac，且bc，则abc，这表明ab是a和b的最小上界。例 设n为正整数，Sn为n的正因子的集合，为整除关系，则构成格。因为x，ySn，xy就是x，y的最小公倍数，xy是x，y的最大公约数。例 幂集P(A)上的包含关系定义了一个偏序关系，P(A)中任意两个元素x，y，有xy=xyxy=xy因此，是一个格。注意：并非每个偏序集都是格。如，设A2,3,6,8,“整除”关系R=2,2,2,6,2,8,3,3,3,6,6,6,8,8是A上的一个偏序关系，则是一个偏序集，但不是格。因为23不存在，68也不存在。例 确定下图中每个哈斯图表示的偏序集是不是格。解：在a)和c)中的哈斯图表示的偏序集是格。因为每个偏序集中每对元素都有最小上界和最大下界。b)所示的哈斯图的偏序集不是格，例如元素b和c没有最小上界。只要注意到d,e,f中每一个都是上界，但这3个元素的任何一个关于这个偏序集中的序都不小于其它两个。格的对偶性原理是成立的：令是偏序集，且是其对偶的偏序集。若是格，则也是格，反之亦然。这是因为，对于L中任意a和b，中LUBa,b等同于中GLB a,b，中GLBa,b等同于中的LUBa,b。若L是有限集，这些性质易从偏序集及其对偶的哈斯图得到验证。从上讨论中，可知两格互为对偶。互为对偶的两个和有着密切关系，即格中交运算正是格中的并运算，而格中的并运算正是格中的交运算。因此，给出关于格一般性质的任何有效命题，把关系换成（或者换成），交换成并，并换成交，可得到另一个有效命题，这就是关于格的对偶性原理。2格的基本性质定理15.1.1 设是格，对任意a,bL，有 ab=bab ab=aab ab=aab=b亦即 abab=bab=a定理15.1.2 设是格，对任意a,bL，有 aa=a,bb=b （等幂律）ab=ba,ab=ba （交换律）a(bc)=(ab)c,a(bc)=(ab)c（结合律）a(ab)=a,a(ab)=a （吸收律）定理15.1.3 设是格，对任意a,b,cL，有若ab和cd，则acbd，acbd。若ab，则acbc，acbc。ca和cb cabac和bc abc定理15.1.4 设是格，对任意的a,b,cL，有a(bc)(ab)(ac)(ab)(ac)a(bc)通常称上二式为格中分配不等式。3特殊的格定义15.1.2 设是格，若L中有最大元和最小元，则称为有界格。由于最大元存在必唯一，故一般把格中最大元记为1，最小元记为0。由定义可知，对任意aL，有 0a1 a0=0,a0=a a1=a,a1=1由此可知，0是关于的零元，关于的幺元；1是关于的幺元，关于的零元定理15.1.5 设是有限格，其中L=a1,a2,an，则是有界格。定义15.1.3 设是格，对任意的a,b,cL，有 a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称为分配格，称和为格中分配律。定义15.1.4 设是有界格，对于aL，存在bL，使得ab=0，ab=1称b为a的补元，记为a。由定义可知，若b是a的补元，则a也是b的补元，即a与b互为补元。显然，0=1和1=0。一般说来，一个元素可以有其补元，未必唯一，也可能无补元。定理15.1.6 设是有界分配格，若aL，且补元存在，则其补元是唯一的。定义15.1.5 设是格，若L中每个元素至少有一补元，则称为有补格。由于补元的定义是在有界格中给出的，可知，有补格一定是有界格。定义15.1.6 若一格既是有补又是分配的，则称该格为有补分配格，或布尔格，或布尔代数。定理15.1.7 设是有补分配格，若任意元素aL，则a的补元a是唯一的。该定理15.1.6的直接推论，因为有补分配格当然是有界分配格。由于有补分配格中，每个元素a都有唯一的补元a，因此可在L上定义一个一元运算补运算“”。这样，有补分配格可看作具有两个二元运算和一个一元运算的代数结构，习惯上称它为布尔代数，记为，其中B=L。定理15.1.8 设是有补分配格，对任意a,bL，则(a)=a(ab)=ab(ab)=ab后两式称为格中德摩根律。定理15.1.9 设是有补分配格，对任意a,bL，有abab=0 ab=1格同态，格直积等概念可以接下来定义和研究，但这里不打算这样做，因为如此进行会相对较繁，而是将格作为一个代数结构而引入它们。4格是代数结构前面我们已知，有补分配格是一个代数结构，叫做布尔代数；反之，由代数结构也可以导出格。定义15.1.7 设是一代数结构，其中和是L上满足交换律、结合律和吸收律的二元运算，且对任意a,bL，定义偏序关系如下：abab=a则是格，称为代数结构所诱导的偏序集确立的格。15.2 布尔代数布尔代数前已指出，布尔代数是有补分配格，常记为。对任意a,b,cB，有 是格，且为B上由或所定义的偏序关系，满足(L-1)ab=LUBa,b，ab=GLBa,b(L-2)abab=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 （吸收律）是分配格，满足(D-1)a(bc)=(ab)(ac)，a(bc)=(ab)(ac)（分配律）(D-2)(ab=ac)(ab=ac)b=c (可约律)(D-3)(ab)(bc)(ca)=(ab)(bc)(ca)是有界格，满足(B-1)0a1(B-2)a0=a，aa=a （幺律）(B-3)a1=1，a0=0 （零律）是有补格，满足(C-1)aa=1，aa=0 （互补律）(C-2)1=0，0=1 是有补分配格，满足(CD-1)(ab)=aa，(ab)=ab （德摩根律）(CD-2)abab=1ab=0ba注意，上述公式并非都是独立的，可从中选出一些公式作为基本公式，用它们推出其余的公式，而且可以用基本公式定义布尔代数。定义15.2.1 设是一代数结构，其中和是B上的二元运算，是B上的一元运算。0,1B。若对任意a,bB，有 ab=ba，ab=ba （交换律）a(bc)=(ab)(ac)，a(bc)=(ab)(ac)（分配律）a0=a，a1=a （幺律）aa=1，aa=0 （互补律）则称是布尔代数，称、和分别是B上的并、交和补运算，0和1分别称为和的幺元和幺元。常记为。事实上，可以由其它定律还可以推出结合律：若x，y，zS，则(xy)z=x(yz)和(xy)z=x(yz)。布尔代数的性质：1.零元是唯一的2.幺元是唯一的3.若xB，则x的补x是唯一的4.(对合律)若xB，则(x)=x5.零元“0”与幺元“1”是互补的，即0=1,1=06.(等幂律)若xB，则x x=x且x x=x7.(零律)若xB，则x 1=1 且x 0=08.(吸收律)若x，yB，则x (x y)=x 且x (x y)=x9.(结合律)若x，y，zB，则(xy)z=x(yz)，(xy)z=x(yz)10.(德摩根律)若x，yB，则(xy)=xy且(xy)=xy11.(可约律)若x，y，zB，则(xy=xz)(xy=xz)y=z12.若x，y，zB，则(xy)(yz)(zx)=(xy)(yz)(zx)13.若x，yB，则xy=x xy=y