-引-言-8-格的定义(离散数学)课件.ppt

1、8.1 引引 言言对对 A,B,C(S)，运算运算，满足：满足：l等幂律等幂律 A AA=AA=A，A AA=AA=A，l交换律交换律 A AB=BB=BA A，A AB=BB=BA A，l结合律结合律 A A（B BC C）=（A AB B）C C，A A（B BC C）=（A AB B）C C，l分配律分配律 A A（B BC C）=（A AB B）（A AC C），），A A（B BC C）=（A AB B）（A AC C），），l吸收律吸收律 A A（A AB B）=A=A，A A（A AB B）=A=A，若引进余集若引进余集的概念，的概念，有有De Morgan定律定律:BABABA

2、BA对对 A,B,CS，运算运算，满足：满足：l等幂律等幂律 AA=A，AA=A，l交换律交换律 AB=BAAB=BA，AB=BA AB=BA l结合律结合律 AA（BCBC）=（ABAB）CC，A A（BCBC）=（ABAB）C C l分配律分配律 A(BC)=(AB)(AC)A(BC)=(AB)(AC)，A A（BCBC）=（ABAB）（ACAC）l吸收律吸收律 A(AB)=A，A（AB）=A，若引进否定若引进否定 的概念，的概念，有有De Morgan定律定律:(AB AB)=A A B,B,(A AB B)=AA B,B,半序格半序格 定义定义A 给出一个部分序集（给出一个部分序集（L

3、，）,如果对于任意如果对于任意a，bL，L的子集的子集a，b在在L中都有一个最大下界中都有一个最大下界(记为记为infa，b)和一个最小上界（记为和一个最小上界（记为supa，b），），则则称（称（L，）为一个格。为一个格。例例.S S是任意一个集合，是任意一个集合，(S S)是是S S的幂集合，的幂集合，则，部分序集则，部分序集(S S)，)是一个格。是一个格。因为对因为对 A,B(S)，supA,B=ABsupA,B=AB(S),),infinfA,B=ABA,B=AB(S)例例.设设I I+是所有正整数集合，是所有正整数集合，D D是是I I+中的中的“整除关整除关系系”，对任意，对任意

4、a a，b bI I+，aDbaDb当且仅当当且仅当a a整除整除b b，于是，（于是，（I I+，D D）是一个格。是一个格。supasupa，b=ab=a，b b的最小公倍的最小公倍I I+，infinfa,b=aa,b=a，b b的最高公因的最高公因I I+。例例.设设n n是一个正整数，是一个正整数，S Sn n是是n n的所有正因数的集的所有正因数的集合，于是，（合，于是，（S Sn n，D D）是格。因为是格。因为supasupa，b=ab=a，b b的最小公倍的最小公倍 S Sn n，infinfa,b=aa,b=a，b b的最高公因的最高公因 S Sn n。例例.设设S S是所

5、有的命题集合，定义是所有的命题集合，定义“”如下：如下：A B A B 当且仅当当且仅当 B B蕴涵蕴涵A A。则（则（S S，）是一个格。因为是一个格。因为supAsupA，B=ABB=ABS S，infinfAA，B=ABB=ABS S。定义定义A 设（设（L，）是格，是格，S L，如果（如果（S，）是格，是格，则称（则称（S，）是格（是格（L，）的子格。的子格。例例.（S6，D）是（是（S24，D）的子格。的子格。定义定义B 设设L是一个集合，是一个集合，是是L上两个上两个二元代数运算，如果这两种运算对于二元代数运算，如果这两种运算对于L中元中元素满足：素满足：（1）交换律交换律：ab=

6、ba，ab=ba。（2）结合律结合律：a（bc）=（ab）c，a（bc）=（ab）c。（3）吸收律吸收律：a（ab）=a，a（ab）=a。则称此代数系统（则称此代数系统（L，），）为一个格。为一个格。note:定义定义B中由，中由，满足吸收律可推出它们满足吸收律可推出它们一定满足等幂律。一定满足等幂律。证明：证明：任取任取L中元素中元素a，由，由，满足吸收律知，满足吸收律知，a（aa）=a，a（aa）=a。故故aa=a（a（aa），），aa=a（a（a a）。）。又由，又由，满足吸收律知，上面两式的等式右满足吸收律知，上面两式的等式右端都等于端都等于a。因此，因此，aa=a，a a=a。即，即

7、，定义定义B中的，中的，运算亦满足等幂律。运算亦满足等幂律。例例.设设S是一个集合是一个集合,(S)是是S的幂集合，于是，的幂集合，于是，(S),)是一个代数格。而是一个代数格。而(S S)，)是半序是半序格。易见对格。易见对 A,B(S)，A B AB=A AB=B。例例.设设I+是所有正整数集合是所有正整数集合,两个正整数的最高公两个正整数的最高公因因,最小公倍最小公倍是是I+上两个代数运算，于上两个代数运算，于是是,(I+,)是一个代数格。而（是一个代数格。而（I+,D）是半序是半序格格,D是整除关系。易见，对任意是整除关系。易见，对任意a，bI+,a D b ab=a ab=b。例例.

8、设设n是一个正整数是一个正整数,Sn是是n的所有正因数的的所有正因数的集合集合,两个正整数的最高公因两个正整数的最高公因,最小公倍最小公倍可可是是Sn上两个代数运算上两个代数运算,于是于是,(,(Sn,),)是一个是一个代数格。代数格。定理定理8.2.1 定义定义A A所定义的格和定义所定义的格和定义B B所定义的所定义的格是格是等价等价的，亦即，一个半序格必是一个代的，亦即，一个半序格必是一个代数格；反之亦然。数格；反之亦然。证明：证明：i i）若若(L,L,)是一个半序格是一个半序格,则对则对 a,ba,bL L，记记infinfaa，bb为为a ab b；supasupa，bb为为aba

9、b。由于对任意由于对任意a a，b b，其其infinfaa，bb，supasupa，bb是是唯一的，所以，如上定义的，唯一的，所以，如上定义的，是集合是集合L L上上的两种二元代数运算。的两种二元代数运算。不难证明不难证明,对于对于,满足交换律满足交换律,结合律结合律,吸收律。吸收律。则根据定义则根据定义B,(L,B,(L,),)是一个代数格。是一个代数格。我们只证明我们只证明吸收律吸收律：a a（a ab b）=a=a为例，其它算律的证明留给读者。为例，其它算律的证明留给读者。因为因为a a(a ab b)是是a a与与(a ab b)的最大下界，所以的最大下界，所以a a(a ab b)

10、a a另一方面，由于另一方面，由于a aa a，a aa ab b，所以，所以，a a是是a a与与a ab b的下界，故的下界，故a aa a(a ab b)所以，所以，a=aa=a(a ab b)。ii）若代数系统（若代数系统（L，）是一个代数格是一个代数格，在集合在集合L上定义一个关系上定义一个关系如下：如下：对任意对任意a，bL，ab ab=a往证：往证：是一个半序关系。是一个半序关系。l反身性反身性:因为因为aa=a(a(aa)=a,所以所以aa。l反对称性反对称性:若有若有ab,ba,则应有则应有ab=a，ba=b，而而ab=ba，所以所以a=b。l传递性传递性:若若ab，bc，则

11、有则有ab=a，bc=b，故故ac=(ab)c=a(bc)=ab=a,亦即亦即,ac。往证：往证：ab=a a b=b。若若ab=a，则则 ab=（ab）b=b。若若ab=b，则则 ab=a（ab）=a。往证往证:对任意对任意a,b L,存在存在infa,b,supa,b.由吸收律知由吸收律知 a a（abab）=a=a，b b（abab）=b=b，故有故有a a（abab），），b b（abab）。）。亦即，亦即，abab是是 a a，bb的上界。的上界。若若c cL L，且且c c是是 a a，bb的上界，亦即有的上界，亦即有a ac c，b bc c，则应有则应有 ac=cac=c，bc

12、=cbc=c，于是，于是，（abab）c=c=（abab）（cccc）=（acac）（bcbc）=cc=c =cc=c故有（故有（abab）c c。因此，（因此，（abab）是是 a a，bb的最小上界，即的最小上界，即supasupa，b=b=（abab）。）。同理可证，同理可证，infinfaa，b=b=（a ab b）。）。综上，（综上，（L L，）为半序格。为半序格。定义定义B 设设(L,)是一个代数格，是一个代数格，S L，(S,)称为称为(L,)的一个代数子格，当的一个代数子格，当且仅当在运算且仅当在运算,下，下，S是封闭的。是封闭的。结论：结论：(S,),)是格是格(L,),)的

13、子格的充的子格的充要条件是：要条件是：S L且（且（S,）是一个格。是一个格。例例.(Sn,)是是(I+,)的代数子格，其中的代数子格，其中,分别是最高公因和最小公倍运算。分别是最高公因和最小公倍运算。设（设（L，）是一个半序格，与其等价的代数是一个半序格，与其等价的代数格为（格为（L，），），S L。l若（若（S，）是（是（L，）的代数子的代数子格，则（格，则（S，）是（是（L，）的半序子格；的半序子格；l若（若（S，）是（是（L，）的半序子格，的半序子格，则（则（S，）不一定是（不一定是（L，）的代的代数子格。数子格。a6a3a1a2a4a5a8a7设设L=aL=a1 1,a,a2 2,a

14、,a3 3,a,a4 4,a,a5 5,a,a6 6,a,a7 7,a,a8 8,（L,L,）是格是格。取取S S1 1=a=a1 1,a,a2 2,a,a4 4,a,a6 6,则（则（S S1 1,）是（是（L,L,）的半的半序子格序子格，也是（也是（L,L,）的代数子格的代数子格。取取S S2 2=a=a1 1,a,a2 2,a,a4 4,a,a8 8,则则(S S2 2,),)是是(L,)L,)的的半序半序子格子格,但但(S S2 2,),)不是不是(L,L,),)的代数子格的代数子格。因为因为:a a2 2a a4 4=a=a6 6,而而a a6 6 S S2 2,即即,S S2 2在下不封闭。在下不封闭。