离散数学第十五章格与布尔代数简

第十五章第十五章 格与布尔代数格与布尔代数在介绍格之前，对于我们在前面学过的偏序，我们要补充两个内容：1. 哈斯图2. 最小上界与最大下界1.哈斯图为了更清楚地描述偏序集合中元素间的层次关系, 也为了更快、更有效地画出偏序关系的简化图, 下面介绍“盖住”的概念定义 在偏序集中, 对x, yA, x≤y且x  y, 且 A中无任何其它元素z, 满足x≤z且z≤y, 称y盖住x, 或称x是y的直接前趋, y是x的直接后继盖住关系记作cov(A) = {(x, y) | x, yA且y盖住x}显然盖住关系是唯一确定的, 盖住关系是“≤”的子集盖住关系的关系图称哈斯(Hasse)图, 它实际上偏序关系是经过如下简化的关系图:1. 省略关系图中的每个结点处的自环, 这是因为偏序关系“≤”是自反的2. 若x的的哈斯图。

哈斯图我们先画出关系图我们先画出关系图注意图中，并没有注意图中，并没有画出所有关系，否画出所有关系，否则画面更显凌乱则画面更显凌乱按照哈斯图的画法，按照哈斯图的画法，去掉一部分，结果去掉一部分，结果如左图例 以下是偏序集的哈斯图利用哈斯图，可以很方便的解决我们在学习偏序集中的一些问题：例 偏序集，其中S={2,4,5,10,12,20,25}，≤是整除关系，求此偏序集的极大元和极小元解：作出哈斯图，从图中看出，12,20和25是极大元，2和5是极小元例 确定下图中每个哈斯图表示的偏序集是否有最大元和最小元解：a)的最小元是a，无最大元b)既无最大元也无最小元c)无最小元，最大元是dd)的最小元是a，最大元是d2.最小上界与最大下界定义 设集合X上有一个偏序关系“≤”且设Y是X的一个子集1）如果存在一个元素x∈X，对每个y'∈Y都有y'≤x，则称x是Y的上界(upper bound)；如果均有x≤y'，则称x是Y的下界(lower bound)2）如果x∈X是Y的上界且对每一个Y的上界x'均有x≤x'，则称x是Y的最小上界（或上确界LUB，least upper bound）；如果x∈X是Y的下界且对每一个Y的下界x'均有x'≤x，则称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,bL，存在 最大下界(GLB)和最小上界(LUB)，则称为格用ab表示GLB{a,b}，ab表示LUB{a,b}，并称和分别为L上的交（或积）和并（或和）运算这样我们由偏序关系定义了两种二元运算若L是有限集合，称为有限格显然，对于ab，有：①ab≤a和ab≤b，则表明ab是a和b的下界②若c≤a和c≤b，则c≤ab，这表明ab是a和b的最大下界对于ab，有：①a≤ab和b≤ab，则表明ab是a和b的上界②若a≤c，且b≤c，则ab≤c，这表明ab是a和b的最小上界例 设n为正整数，Sn为n的正因子的集合，≤为整除关系，则构成格。

因为x，y∈Sn， xy就是x，y的最小公倍数，xy是x，y的最大公约数例 幂集P(A)上的包含关系定义了一个偏序关系，P(A)中任意两个元素x，y，有xy =x∪yxy =x∩y因此，是一个格注意：并非每个偏序集都是格如， 设A＝{2,3,6,8}, “整除”关系R={‹2,2›, ‹2,6›, ‹2,8›, ‹3,3›, ‹3,6›, ‹6,6›, ‹8,8›}是A上的一个偏序关系，则是一个偏序集，但不是格因为23不存在，68也不存在例 确定下图中每个哈斯图表示的偏序集是不是格解： 在a)和c)中的哈斯图表示的偏序集是格因为每个偏序集中每对元素都有最小上界和最大下界 b)所示的哈斯图的偏序集不是格，例如元素b和c没有最小上界只要注意到d,e,f中每一个都是上界，但这3个元素的任何一个关于这个偏序集中的序都不小于其它两个格的对偶性原理是成立的：令是偏序集，且是其对偶的偏序集若是格，则也是格，反之亦然这是因为，对于L中任意a和b，中LUB{a,b}等同于中GLB {a,b}，中GLB{a,b}等同于中的LUB{a,b}。

若L是有限集，这些性质易从偏序集及其对偶的哈斯图得到验证从上讨论中，可知两格互为对偶互为对偶的两个和有着密切关系，即格中交运算正是格中的并运算，而格中的并运算正是格中的交运算因此，给出关于格一般性质的任何有效命题，把关系≤换成≥（或者≥换成≤），交换成并，并换成交，可得到另一个有效命题，这就是关于格的对偶性原理–2．格的基本性质定理15.1.1 设是格，对任意a,bL，有① ab=ba≤b② ab=aa≤b③ ab=aab=b亦即 a≤bab=bab=a定理15.1.2 设是格，对任意a,bL，有① aa=a, bb=b （等幂律）② 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 （吸收律）定理15.1.3 设是格，对任意a,b,cL，有①若a≤b和c≤d，则ac≤bd，ac≤bd。

②若a≤b，则ac≤bc，ac≤bc③c≤a和c≤b c≤ab④a≤c和b≤c ab≤c定理15.1.4 设是格，对任意的a,b,cL，有a(bc)≤(ab)(ac)(ab)(ac)≤a(bc)通常称上二式为格中分配不等式–3．特殊的格定义15.1.2 设是格，若L中有最大元和最小元，则称为有界格由于最大元存在必唯一，故一般把格中最大元记为1，最小元记为0由定义可知，对任意aL，有① 0≤a≤1② a0=0, a0=a③ a1=a, a1=1由此可知，0是关于的零元，关于的幺元；1是关于的幺元，关于的零元定理15.1.5 设是有限格，其中L={a1,a2,···,an}，则是有界格定义15.1.3 设是格，对任意的a,b,cL，有① a(bc)=(ab)(ac)② a(bc)=(ab)(ac)则称为分配格，称①和②为格中分配律定义15.1.4 设是有界格，对于aL，存在bL，使得ab=0，ab=1称b为a的补元，记为a'。

由定义可知，若b是a的补元，则a也是b的补元，即a与b互为补元显然，0'=1和1'=0一般说来，一个元素可以有其补元，未必唯一，也可能无补元定理15.1.6 设是有界分配格，若aL，且补元存在，则其补元是唯一的定义15.1.5 设是格，若L中每个元素至少有一补元，则称为有补格由于补元的定义是在有界格中给出的，可知，有补格一定是有界格定义15.1.6 若一格既是有补又是分配的，则称该格为有补分配格，或布尔格，或布尔代数定理15.1.7 设是有补分配格，若任意元素aL，则a的补元a'是唯一的该定理15.1.6的直接推论，因为有补分配格当然是有界分配格由于有补分配格中，每个元素a都有唯一的补元a'，因此可在L上定义一个一元运算—补运算“ ' ”这样，有补分配格可看作具有两个二元运算和一个一元运算的代数结构，习惯上称它为布尔代数，记为，其中B=L定理15.1.8 设是有补分配格，对任意a,bL，则① (a')'=a② (ab)'=a'b'③ (ab)'=a'b'后两式称为格中德·摩根律定理15.1.9 设是有补分配格，对任意a,bL，有a≤bab'=0 a'b=1格同态，格直积等概念可以接下来定义和研究，但这里不打算这样做，因为如此进行会相对较繁，而是将格作为一个代数结构而引入它们。

–4．格是代数结构前面我们已知，有补分配格是一个代数结构，叫做布尔代数；反之，由代数结构也可以导出格定义15.1.7 设是一代数结构，其中和是L上满足交换律、结合律和吸收律的二元运算，且对任意a,bL，定义偏序关系≤如下：a≤bab=a则是格，称为代数结构所诱导的偏序集确立的格15.2 布尔代数布尔代数前已指出，布尔代数是有补分配格，常记为对任意a,b,cB，有① 是格，且≤为B上由或所定义的偏序关系，满足(L-1) ab=LUB{a,b}， ab=GLB{a,b}(L-2) a≤bab=bab=a(L-3) aa=a， aa=a （等幂律）(L-4) ab=ba， ab=ba （交换律）(L-5) (ab)c=a(bc)， (ab)c=a(bc) （结合律）(L-6) a(ab)=a，a(ab)=a （吸收律）② 是分配格，满足(D-1) a(bc)=(ab)(ac)， a(bc)=(ab)(ac) （分配律）(D-2) (ab=ac)∧(ab=ac)b=c (可约律)(D-3) (ab)(bc)(ca)=(ab)(bc)(ca)③ 是有界格，满足(B-1) 0≤a≤1(B-2) a0=a，aa=a （幺律）(B-3) a1=1，a0=0 （零律）④ 是有补格，满足(C-1) aa'=1，aa'=0 （互补律）(C-2) 1'=0，0'=1⑤ 是有补分配格，满足(CD-1) (ab)'=a'a'，(ab)'=a'b' （德·摩根律）(CD-2) a≤ba'b=1ab'=0b'≤a'注意，上述公式并非都是独立的，可从中选出一些公式作为基本公式，用它们推出其余的公式，而且可以用基本公式定义布尔代数。

定义15.2.1 设是一代数结构，其中和是B上的二元运算，'是B上的一元运算0,1B若对任意a,bB，有① ab=ba，ab=ba （交换律）② a(bc)=(ab)(ac)， a(bc)=(ab)(ac) （分配律）③ a0=a，a1=a （幺律）④ aa'=1，aa'=0 （互补律）则称是布尔代数，称、和'分别是B上的并、交和补运算，0和1分别称为和的幺元和幺元常记为事实上，可以由其它定律还可以推出结合律： 若x，y，z∈S，则(xy)z = x(yz)和(xy)z = x(yz)布尔代数的性质：1.零元是唯一的2.幺元是唯一的3.若x∈B，则x的补x'是唯一的4.(对合律)若x∈B，则(x')'=x5.零元“0”与幺元“1”是互补的，即0'=1,1'=06.(等幂律)若x∈B，则x  x =x且x  x =x7.(零律)若x∈B，则x  1 = 1 且x  0 =08.(吸收律)若x，y∈B，则x  (x  y) = x 且x  (x  y) = x9.(结合律)若x，y，z∈B，则(xy)z=x(yz)， (xy)z=x(yz)10.(德摩根律) 若x，y∈B，则(xy)'=x'y'且(xy)'=x'y'11.(可约律)若x，y，z∈B，则(xy=xz)∧(xy=xz)y=z12.若x，y，z∈B，则(xy)(yz)(zx)= (xy)(yz)(zx)13.若x，y∈B，则xy=x  xy=y习习 题题图所示的偏序集，哪些不是格？并说明理由。

图所示的偏序集，哪些不是格？并说明理由。