离散数学第六章第一节

第六章格与布尔代数

格是另一类代数系统。格的理论形成于1935年前后，是代数学的一个分支。本章介绍格的基本知识，特殊的格：分配格、有补格，最后介绍布尔代数。1第六章目录第6-1讲格的概念第6-2讲分配格和有补格第6-3讲布尔代数第6-4讲布尔表达式2第6-1讲格的概念1.格的定义2.格的对偶原理3.格的基本性质4.格与代数系统间的关系5.格同态6.

课堂练习7.第6-1讲作业31、格的定义(1)

如果集合A上的关系具有自反性、反对称性和传递性，称之为偏序。<A，>称之为偏序集。设X={1,2,3,4,6,12},Y={2,3,6,12,24,36}。集合X和Y上的整除关系“|”就构成两个偏序集：<X,|>，<Y,|>。它们的哈斯图如下：虽然都是哈斯图,但是它们有一个重要的差别：

<X,|>中每两个元素构成的集合都有最大下界和最小上界。但<Y,|>无此特点。41、格的定义(2)定义2设<A,>是格，在A上定义两个二元运算和，对任意a,bA，ab等于a和b的最小上界，ab等于a和b的最大下界，则称<A,,>是格<A,>诱导的代数系统。和分别称为并运算和交运算。定义1如果偏序集<A,>中任意两个元素都有最小上界和最大下界，则称<A,>是格。注：定义2中定义的两个运算是本节证明过程中反复要用的基本依据。两个元素的集合{a,b}的上界可以属于该集合，也可以不属于该集合。但是，

如果ab，则ab=b，ab=a。如果a、b不可比，也应有a,bab，aba,b。51、格的定义(3)可以证明，子格也是格。注意：若<A,>是格,BA且B，则<B,>任然是偏序集，但<B,>不一定是格。即使是格，也不一定是<A,>的子格。定义3设<A,>是格,<A,,>是<A,>诱导的代数系统。如果BA且B，若运算和在B中封闭，则称<B,>是<A,>的子格。例如，设S={a,b,c},<(S),

>是格，其哈斯图如右，取A={,{a},{c},{a,c}}B={,{a},{c},{a,b},{a,c},{b,c},{a,b,c}}则<A,>是<(S),

>的子格，而<B,>虽是格，但非子格。62、格的对偶原理对偶原理设P是格<A,>的真命题，将P中的、、分别换成、、得命题P’，则P’在格<A,>中亦真。设<A,>是偏序集,用表示偏序关系的逆关系，则<A,>也是偏序集。将<A,>的哈斯图旋转180度，就是<A,>的哈斯图。称<A,>为<A,>彼此对偶的偏序集。如果<A,>是格，则<A,>也是格。由格<A,>诱导的代数系统的并(交)运算，正好是由格<A,>诱导的代数系统的交(并)运算。73、格的基本性质(1)设<A,>是格,a,b,c,dA，则如下性质成立：(1)并、交定义aab,bab

aab,bab

aba,abbaba,abb(2)保序性若ab,cd，则acbd，acbd若bc,则abac，abac(3)交换律

ab=ba，ab=ba(4)结合律a(bc)=(ab)c，a(bc)=(ab)c(5)等幂律aa=a，aa=a83、格的基本性质(2)(6)吸收律

a(ab)=a，a(ab)=a(7)分配不等式a(bc)(ab)(ac)，a(bc)(ab)(ac)(8)abab=aab=b(9)aca(bc)(ab)c作为例子下面证明部分式子：若ab,cd，则acbd。证：已知ab,cd，由(1)，bbd，dbd，再由传递性可得abd，cbd。这说明bd是a和c的一个上界，但ac是a和c的最小上界，所以acbd。93、格的基本性质(3)证(4)式：a(bc)=(ab)c。证：由(1)，aa(bc)，bbc

a(bc)，这说明a(bc)是a和b的一个上界。但ab是a和b的最小上界，所以ab

a(bc)。

同样，cbca(bc)，与上述理由相同，应有(ab)ca(bc)。类似的可证a(bc)(ab)cbd。因而原式得证。分析：由偏序的反对称性，要证原式，须证下列二式：(ab)ca(bc)，

a(bc)(ab)c

证明线索如右图所示。104、格与代数系统间的关系（1）证：对任意a,bA，因,满足吸收律，所以a(ab)=a，a(ab)=a由b的任意性，在前一式中用ab取代b仍然成立，可得a(a(ab))=a再由后一式得：aa=a同理可证aa=a。引理1设<A,,>是一个代数系统，其中,都是二元运算且满足吸收律，那么,必满足等幂律。114、格与代数系统间的关系（2）证：在A上定义二元关系：

对任意a,bA，ab当且仅当ab=a。

先证是偏序。由所设,运算满足吸收律，根据引理1，对任意aA，aa=a。所以aa，从而是自反的。设ab，则ab=a。如果同时有ba,则ba=b。而运算满足交换律，所以ab=ba，故a=b。从而是反对称的。设ab，bc,则ab=a,bc=b。那么ac=(ab)c=a(bc)=ab=a所以ac，说明是传递的。定理1设<A,,>是一个代数系统，其中,都是二元运算且满足交换律、结合律和吸收律，则A上存在偏序，使<A,>是格。分析：需要做的工作是：(1)在A上构造偏序关系；(2)证明<A,>中任意两个元素有最小上界和最大下界。124、格与代数系统间的关系（3）证(续)：其次证明ab是a、b的最大下界。因(ab)a=a(ab)=(aa)b=ab(ab)b=a(bb)=ab由上二式，并按的定义，可得aba，abb。说明ab是a、b的下界。设c是a、b的任一下界，则ca,cb。按的定义有ca=c,cb=c。进而有c(ab)=(ca)b=cb=c。按的定义有cab。故ab是a、b的最大下界。定理1

设<A,,>是一个代数系统，其中,都是二元运算且满足交换律、结合律和吸收律，则A上存在偏序，使<A,>是格。134、格与代数系统间的关系（4）证(续)：第三，证明ab是a、b的最小上界。

先证ab=a与ab=b等价：若ab=a，则(ab)b=ab；另一方面，由交换律和吸收律，上式左边(ab)b=b(ba)=b。于是ab=b。反之，若ab=b，则a(ab)=ab。

根据吸收律得a=ab,亦即ab=a。由此可见，证明开始定义的偏序关系等价于：“对任意a、bA，ab当且仅当ab=b。”

可以用证明“ab是a、b的最大下界”类似的方法证明“ab是a、b的最小上界”。

综上所述，<A,>是格。定理1

设<A,,>是一个代数系统，其中,都是二元运算且满足交换律、结合律和吸收律，则A上存在偏序，使<A,>是格。145、格同态(1)定义4设<A1,1>、<A2,2>是格。它们所诱导的代数系统分别是<A1,1,1>、<A2,2,2>。如果存在映射f：A1A2，使对任意a,bA1,有f(a1b)=f(a)2f(b),f(a1b)=f(a)2f(b)则称f是从<A1,1,1>到<A2,2,2>的格同态。称<f(A1),2>是<A1,1>的格同态象。如果f是双射，则称f是从<A1,1,1>到<A2,2,2>的格同构。也称格<A1,1>、<A2,2>同构。

定理1中说明，格<A,>可视为具有两个二元运算的代数系统<A,,>，其中运算满足交换律、结合律、吸收律和等幂律。因此，对格可引入代数系统中同态的概念。155、格同态(2)定理2设f是格<A1,1>到<A2,2>格同态。对任意a,bA1,如果a1b,则f(a)2f(b)。证明：因a1ba1b=a。又因f是格同态，所以f(a)=f(a1b)=f(a)2f(b)故f(a)2f(b)。

注：定理2说明，格同态是保序的。其逆不真。例如，设A={1,2,3,4,6,12}，<A,|>和<A,>都是格，其中“|”表示整除关系，“”表示数的大于小于关系。作映射f:AA,f(x)=x。显然，如果x|y,则f(x)f(y),因而f是保序的。但f不是格同态。例如:f(416)f(4)2f(6)165、格同态(3)定理3f是格<A1,1>到<A2,2>的格同构，当且仅当对任意a,bA1,a1bf(a)2f(b)。证明：设f是格<A1,1>到<A2,2>的格同构，由定理2，对任意a,bA1,如果a1b，则f(a)2f(b)；反之，若f(a)2f(b)，则f(a)2f(b)=f(a)，因f是同构，所以f(a)2f(b)=f(a1b)，从而f(a1b)=f(a)，注意到f是双射，可知a1b=a，故a1b。

反之，若对任意a,bA1,a1bf(a)2f(b)，要证f是<A1,1>到<A2,2>的格同构，即证f(a1b)=f(a)2f(b)。（转下页）175、格同态(3)定理3f是格<A1,1>到<A2,2>的格同构，当且仅当对任意a,bA1,a1bf(a)2f(b)。

证明(续)：令a1b=c,则c1a，c1b。已知a1bf(a)2f(b)，所以，f(c)2f(a),f(c)2f(b)。故f(c)2f(a)2f(b)。又令f(a)2f(b)=f(d)，则上式化为f(c)2f(d)；