第九章格与布尔代数.ppt

《第九章格与布尔代数.ppt》由会员分享，可在线阅读，更多相关《第九章格与布尔代数.ppt（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第九章 格与布尔代数,9.1 格的定义及性质,定义 9.1.1 设 ( L, ) 是一个偏序集，若对于任意 a,bL都有最小上界lub(a,b)和最大下界glb(a,b),则称( L, )是格, 记lub(a,b)为ab, glb(a,b)为ab.例9.1.1 设S是集合，P(S)是S的幂集合，则偏序集(P(S), )是格。 若A, B S, 则lub(A, B)=AB, glb(A,B)=AB 即AB = AB, AB= AB,例9.1.2 设Z+是正整数集合，偏序“”定义为：a b a|b (a整除b)。则(Z+, )是格。 设a, b Z+, 则lub(a,b)=lcm(a,b), 即a

2、b=lcm(a,b), 同理, glb(a,b)=gcd(a,b), 即ab=gcd(a,b), 其中, lcm(a,b)为a和b的最小公倍数; gcd(a,b)为a和b的最大公约数。,例9.1.3 试问图9.1.1所示的偏序集中哪些是格。,图9.1.1,全序集都是格。群G的全体子群S(G)对于偏序 构成格。G; HK群G的全体正规子群H(G)对于偏序 构成格。H, K 的最小上界HK= hk|hH, kK , 最大下界HK环R的全体理想I(R)对于偏序 构成格。I, J 的最小上界I+J= i+j|iI, jJ , 最大下界IJ线性空间V的全体子空间S(V)对于偏序 构成格。,定理9.1.1

3、 若( L, )是格，则其对偶偏序集( L, )也是格。例如，由于(P(S), )是格，所以(P(S), )也是格，并且在格(P(S), )中，AB = AB, AB= AB。设( L, )是格，由于L的任意两个元素 a和 b均有唯一的最小上界和最大下界，因此“”和“”是格中的两个二元运算，所以格可以看作具有两个二元运算“”和“”的代数系统。,定理 9.1.2 设( L, )是格，则1(1) aa = a， (2) aa = a 幂等律2(1) ab=ba， (2) ab=ba 交换律3(1) (ab)c=a(bc), (2) (ab)c=a(bc)结合律4(1) a(ab)=a， (2) a

4、(ab)=a 吸收律 由a(bc)是a, (bc)的最小上界知 aa(bc), bca(bc)而bc是b, c的最小上界，故bbc, c bc, 再由传递性知: b, c a(bc)。所以a(bc)是a, b的上界，而ab是a, b的最小上界，因此 aba(bc), 故a(bc)是ab, c的上界，而(ab)c是ab, c的最小上界，于是(ab)ca(bc)；同理，a(bc) (ab)c 故由反对称性知: (ab)c=a(bc),定理 9.1.3 设(L, , )是有两个运算的代数系统，并且运算“”和“”满足幂等律，交换律，结合律，吸收律，则可以在L上定义一个偏序关系“”使得( L, )是格，

5、并对任意 x, y L, 有x y= x y，x y= x y证. 在L上定义关系“”如下：a b a = a b 。 首先说明“”是偏序关系,对任意a, bL，由于*是幂等的，因此a =a*a，于是a a，故是自反的。 如果a b 且 b a，则a = a*b 且 b = b*a，由于*是交换的，因此a=a*b=b*a=b，故是反对称的。 如果a b, b c,则a=a*b，b=b*c，由于*是结合的，因此a=a*b=a*(b*c)=(a*b)*c=a*c，即a c，故是传递的。 所以(L, )是偏序集。,然后说明(L, )是格。对任意a, b L， 由(a*b)*a=a*(b*a)=a*(

6、a*b)=(a*a)*b=a*b得 a*ba由(a*b)*b=a*(b*b)=a*b得 a*bb， 所以a*b是a, b的下界； 设c是a, b的下界，则c a, c b, 即c =c*a, c =c*b, 故c=c*c=(c*a)*(c*b)=(c*c)*(a*b)=c*(a*b), 即c a*b所以a*b是a, b的最大下界, 即ab = glb(a,b) = a*b 类似地说明，ab=lub(a, b)=ab 设a, bL, ab, 则a =ab, 由吸收律知 ab=(ab)b=b,反之，设ab=b，则 ab=a(ab)=a, 所以ab。 综合得：a b a b=b。 由(ab)a =

7、(aa)b = a b 得 a a b, 由(ab)b = a(bb) = a b 得 b a b, 所以ab是a, b的上界； 设c是a, b的上界，则 ac, bc, 即 ac =c, bc =c 故c=cc=(ac)(bc)=(ab)(cc)=(ab)c, 即(ab)c所以ab是a, b的最小上界，即ab = lub(a, b) = ab,定义9.1.2 设 (L, , )是一个代数系统，二元运算“”和“” 满足幂等律，交换律，结合律，吸收律，则称代数系统(L, , )为格。例9.1.4 设Z是整数集合，在Z上定义二元运算“”和“”如下：对任意 x, y Z，xy =maxx,y, xy = minx, y, 则(Z, , )是格。 只需验证“”和“”满足幂等律，交换律，结合律和吸收律,