《格与布尔代数》PPT课件.ppt

1、离 散 数 学,中北大学,电子与计算机科学技术学院,2021年3月3日星期三,2021/3/3,第6章 格与布尔代数,2021/3/3,偏序格,比较右边两个哈斯图的不同,2021/3/3,定义6.2.1,设是一个偏序集，如果对任意a, bL，a, b都有最大下界和最小上界存在，则称是格，简称L是格。若L为有限集，则称格为有限格。 暂且把由偏序关系定义的格称为偏序格,2021/3/3,保交与保联,在格中，任取a, bG，则a, b的最大下界和最小上界都是惟一存在的，且均属于L。 用a*b表示a, b的最大下界，称为a与b的保交，用ab表示a, b的最小上界，称为a与b的保联，即 a*b = GL

2、Ba, b，ab = LUBa, b 也可用和、和、和分别表示保交和保联,2021/3/3,例6.2.1,1）考虑偏序集，其中Z+是正整数，D是一个整除关系，问此偏序集是否是一个格？ （2）设A是一个集合，P(A)是A的幂集，是集合上的包含关系，问此偏序集是否是一个格？ （3）所有的全序集都是格,2021/3/3,例6.2.1（续,分析 判断一个偏序集是否是格，要对L的所有2元素子集看它是否都有最大下界和最小上界 解 （1）对a, bZ，有 a*b = GLBa, b = GCDa, bZ GCD表示a, b的最大公因子。 ab = LUBa, b = LCMa, bZ LCM表示a, b的最

3、小公倍数。 所以，是一个格,2021/3/3,例6.2.1 解（续,2）对S1，S2P(S)，有 S1*S2 = GLBS1, S2 = S1S2P(S) S1S2 = LUBS1, S2 = S1S2P(S) 所以，是一个格,2021/3/3,例6.2.1 解（续,4）因为在全序集中，对任意a, bL，都有a b或b a成立。 若a b成立，则a, b有最大下界为a，最小上界为b； 若b a成立，则a, b有最大下界为b，最小上界为a； 故是一个格,2021/3/3,定义6.2.2,设是具有两个二元运算的代数系统，如果运算和满足交换律、结合律和吸收律，则称为格。 把由代数系统定义的格称为代数

4、格,2021/3/3,例6.2.3,设A是一个集合，P(A)是A的幂集，和分别是集合的交和并运算，试证明代数系统是一个格。 证明 由集合的运算性质知，交和并运算都满足交换律、结合律和吸收律，因此由定义知，是一个格,2021/3/3,定义6.2.3,设代数系统是一个格，S L，若S满足： （1）S； （2）运算和对子集S都是封闭的； 则称是的子格，简称S是L的子格,2021/3/3,例6.2.4,在正整数集合Z+中规定、为：对任意a, bP， ab = a, b，其中a, b表示a, b的最小公倍数 ab = (a, b)，其中(a, b)表示a, b的最大公因数 则, 是Z+上的二元运算，且满

5、足交换律、结合律、吸收律和等幂律，于是是一个格。S = 3k | kZ+ ，试证明是的子格,2021/3/3,例6.2.4 证明,显然S。因为对任意3m, 3nS，都有 3m3n = 3m, 3n = 3m, nS， 3m3n = (3m, 3n) = 3(m, n)S 所以，是的子格,2021/3/3,子格,定义6.2.4 设是一个格，S L，若S满足： （1）S； （2）对任意a, bS， 的保交和保联运算都有 ab = GLBa, bS， ab = LUBa, bS， 则称是的一个子格，简称S是L的子格,2021/3/3,例6.2.5,设是一个格，aL，令S = x|xL, x a，则S

6、是L的子格。 证明 因为a a，所以aS，即S是非空子集。 对任意x, yS，由x a，y a，可知 xy = GLBx, y a，即xy = GLBx, yS xy = LUBx, y a，即xy = LUBx, yS 故S是L的子格,2021/3/3,定义6.2.5,设和是两个格，f是L到S的映射。如果对任意x, yL，都有 f(xy) = f(x)* f(y)，f(xy) = f(x) f(y) 则称f为从格到格的格同态映射，简称格同态。 如果f是格同态，当f分别是单射、满射和双射时，f分别称为单一格同态、满格同态和格同构,2021/3/3,定义6.2.6,设是一个格，如果对任意a, b

7、, cL，都有 a(bc) = (ab) (ac)， a(bc) = (ab) (ac)， 即运算满足分配律，则称是一个分配格,2021/3/3,例6.2.7,1）设A为任意一个集合，格是否是分配格？ （2）设P为命题公式集合，与分别是命题公式的合取与析取运算，格是否是分配格？ 解 （1）因集合的交、并运算满足分配律，所以，格是一个分配格。 （2）因命题公式的析取、合取运算满足分配律，所以，格是分配格,2021/3/3,定理6.2.4,所有链都是分配格。 证明 设是链，因此是格，任取a, b, cL，只有以下两种情况： （1）a是三者中最大的，即b a，c a； （2）a不是三者中最大的，即a

8、 b或a c。 在情况(1)中，bc a，故a(bc) = bc。显然，ab = b，ac = c。所以 a(bc) = bc =(ab)(ac)。,2021/3/3,定理6.2.4（续,在情况(2)中，abc，而ab=a或ac=a，从而(ab)(ac) = a，所以 (ab)(ac)= a = a(bc) 所以是分配格,2021/3/3,例6.2.8,右图所示的两个格都不是分配格。 分析 由于链是分配格，因此在同一条链上的元素都满足分配等式，最有可能不满足分配等式的元素不在同一条链上。选取b, c, d来验证即可,2021/3/3,例6.2.8（续,解 取图中b, c, d三个元素验证。在图

9、 (a)中， b(cd)=be=b，而 (bc)(bd)=aa = a。 在图 (b)中， b(cd)=be= b，而 (bc)(bd)=aa=a。 因此，在图 (a)和(b)中都有， b(cd)(bc)(bd) 故它们都不是分配格,2021/3/3,定理6.2.5,一个格是分配格的充分必要条件是该格中没有任何子格与6例15.2.86中的两个五元素格中的任何一个同构,2021/3/3,性质6.2.2,1）四个元素以下的格都是分配格； （2）五个元素的格仅有两个格是非分配格(图6.2.8(a)和(b)，其余三个格(右图 (a), (b)和(c)都是分配格,2021/3/3,定理6.2.6,设是分

10、配格，对于任何a, x, yL，如果ax = ay且ax = ay，则x = y。 证明 x = x (ax)(吸收律) = x (ay)(已知ax = ay) = (xa) (xy)(分配律) = (ay) (xy)(已知ax = ay) = y (ax)(交换律，分配律) = y (ay)(已知ax = ay) = y(吸收律,2021/3/3,定义6.2.7,设是格，如果对任意a, b, cL，有 ab a(bc)=b(ac)或(模律) ab a(bc)=b(ac) 则称为模格，也称为戴德金格,2021/3/3,定理6.2.7,分配格是模格。 证明 设是分配格，对任意a, b, cL，如

11、果a b，那么ab = b，由分配律得 a (bc) = (ab)(ac) = b(ac) 故是模格,2021/3/3,性质6.2.3,1)每一个链格都是模格； （2）四个元素以下的格都是模格,2021/3/3,定义6.2.8,设是一个格，若存在元素aL，使得对任意xL，都有： a x(或x a)， 则称a为格的全下界(或全上界)，分别记为0(或1)，具有全上界和全下界的格称为有界格。 显然，对任意xL，有 1x = x1 = x，1x = x1 = 1 0 x = x0 = 0，0 x = x0 = x,2021/3/3,有限格与有界格,若是有限格，设L = a1, a2, , an，由于运

12、算“”和“”满足结合律，所以有 (a1a2)an) = a1a2an (a1a2)an) = a1a2an 此时， a1a2an和a1a2an分别是格L的全下界和全上界，即有 a1a2an = 0 a1a2an = 1 所以，有限格一定是有界格,2021/3/3,定理6.2.8,在格中，全下界和全上界分别是集合L的最小元和最大元，由于最大元和最小元的惟一性，有下面的定理： 定理6.2.8 设是一个格，若格的全上界和全下界存在，则必惟一,2021/3/3,定义6.2.9,设为有界格，1和0分别为它的全上界和全下界，aL。如果存在bL，使得 ab = 0，ab = 1， 则称b为a的补元，记为a。

13、若有界格中的所有元素都存在补元，则称为有补格,2021/3/3,例6.2.9,如下图有界格，求其所有元素的补元(如果有的话,2021/3/3,例6.2.9（续,解 对于图a中,d与c互补,a,d都是e的补元,c和e都是d的补元, b无补元。 对于图b: 0 = 1，1 = 0， a = b，a = d， b = a，b = c， c = d，c = b， d = a，d = c 则图a不是有补格，图b是有补格,2021/3/3,定理6.2.9,在有界分配格(既是有界格又是分配格，简称为有界分配格)中，如元素aL有补元存在，则此元素的补元必惟一。 证明 设a有两个补元b和c，由补元的定义知 ab

14、 = 0 = ac，ab = 1 = ac 由定理知，b = c。 推论6.2.1 在有补分配格(既是有补格又是分配格，简称为有补分配格)中，每个元素都存在惟一的补元,2021/3/3,定理6.2.10,设是有补分配格，“ ”是该格的偏序，则对任意a, bL，都有 （1）(a) = a；(对合律) （2）(ab ) = a b ， (ab) = ab； (De Morgan律) （3）a b b a； （4）a b ab = 0 ab = 1,2021/3/3,定理6.2.10（续,证明 （1）因a是a的补元，反过来，a也是a的补元，由推论15.2.1得，(a) = a。 （2）因为 (ab)

15、 (ab) = (ab) a) (ab) b)(分配律) = (aa)b) (a (bb)(交换律，结合律) = (0b) (a0) = 00 = 0,2021/3/3,定理6.2.10（续,ab) (ab) = (a (ab) * (b (ab)(分配律) = (aa) b) * (a (bb)(交换律，结合律) = (1b) (a1) = 11 = 1 所以， ab是ab的补元，由补元的惟一性得，(ab) = ab。 同理可证，(ab) = ab,2021/3/3,定理6.2.10（续,3）“”，由a b，可得ab = a，则有 (ab) = a 由De Morgan律(即(2)，有 ab

16、 = a ，即是 b a “”，上述过程可逆，故成立。 （4）“”由a b，根据(3)，有 b a则 ab aa = 0，即是,2021/3/3,定理6.2.10（续,ab 0， 又0是全下界，有 0 ab 则根据偏序关系“ ”的反对称性，有 ab = 0， 对上式使用De Morgan律，自然有 ab = 1,2021/3/3,定理6.2.10（续,如果ab = 1，由De Morgan律，有 ab = 0，则有 a(ab) = a0 = a 对上式的左边使用分配律，可得 a(ab) = (aa) (ab) = 1 (ab) = ab 即是 ab = a，所以有 b a，由(3)可得 a b

17、,2021/3/3,定义6.3.1,称有补分配格为布尔格。 定义6.3.2 由一个布尔格所诱导的一个代数系统称为布尔代数。若一个布尔代数的元素个数是有限的，则称此布尔代数为有限布尔代数，否则称为无限布尔代数,2021/3/3,布尔代数,布尔代数是有补分配格，有补分配格必须满足它是格、有全上界和全下界、分配律成立、每个元素都有补元存在。显然，全上界1和全下界0可以用下面的同一律来描述： 同一律： 在L中存在两个元素0和1，使得对任意aL，有 a1 = a，a0 = a,2021/3/3,布尔代数,补元的存在可以用下面的互补律来描述。 互补律：对任意aL，存在aL，使得 aa = 0，aa = 1

18、。 格可以用交换律、结合律、吸收律来描述。 因此，一个有补分配格就必须满足交换律、结合律、吸收律、分配律、同一律、互补律。 另外，可以证明，由交换律、分配律、同一律、互补律可以得到结合律、吸收律。所以布尔代数有下面的等价定义,2021/3/3,定义6.2.3,设是代数系统，其中、是B中的二元运算，如果对任意a, b, cB，满足 （1）交换律：ab = ba，ab = ba； （2）分配律：a (bc) = (ab) (ac)， a (bc) = (ab) (ac)； （3）同一律：在B中存在两个元素0和1，使得对任意aB，有 a1 = a，a0 = a； （4）互补律：对任意aB，存在aB，使得 aa = 0，aa = 1。 则称为布尔代数,2021/3/3,定义6.2.3（续,通常将布尔代数记为。为方便起见，也简称B是布尔代数,