离散数学1第14与代数

1、离 散 数 学电子科技大学计算机科学与工程学院示 范 性 软 件 学 院16 九月 20222022/9/16第15章 格与布尔代数集合的表示方法2子格与格同态3特殊格4偏序格与代数格1格的性质2布尔代数52022/9/1615.1 本章学习要求重点掌握一般掌握了解11 格的定义及性质2 子格与格同态3 特殊格4 布尔代数31 斯通定理2 布尔函数 21 格与布尔代数的证明2022/9/16偏序格 efabdcabcd(a)(b)比较右边两个哈斯图的不同？2022/9/16定义15.2.1设是一个偏序集，如果对任意a, bL，a, b都有最大下界和最小上界存在，则称是格，简称L是格。若L为有限

2、集，则称格为有限格。暂且把由偏序关系定义的格称为偏序格2022/9/16保交与保联在格中，任取a, bG，则a, b的最大下界和最小上界都是惟一存在的，且均属于L。用a*b表示a, b的最大下界，称为a与b的保交，用ab表示a, b的最小上界，称为a与b的保联，即a*b = GLBa, b，ab = LUBa, b也可用和、和、和分别表示保交和保联 2022/9/16例15.2.1（1）考虑偏序集，其中Z+是正整数，D是一个整除关系，问此偏序集是否是一个格？（2）设A是一个集合，P(A)是A的幂集，*是集合上的包含关系，问此偏序集是否是一个格？（3）考虑偏序集，其中D是一个整除关系，Sn是n的

3、所有因子的集合，问此偏序集是否是一个格？（4）所有的全序集都是格？分析 判断一个偏序集是否是格，要对L的所有2元子集看它是否都有最大下界和最小上界2022/9/16例15.2.1（续）分析 判断一个偏序集是否是格，要对L的所有2元子集看它是否都有最大下界和最小上界解 （1）对a, bZ，有a*b = GLBa, b = GCDa, bZGCD表示a, b的最大公因子。ab = LUBa, b = LCMa, bZLCM表示a, b的最小公倍数。所以，是一个格。2022/9/16例15.2.1 解（续）（2）对S1，S2P(S)，有S1*S2 = GLBS1, S2 = S1S2P(S)S1S2

4、 = LUBS1, S2 = S1S2P(S)所以，是一个格。（3）由(1)可知：一定是一个格。举例如下： 当n = 6和n = 24时，有和是格。此时S6 = 1, 2, 3, 6，S24 = 1, 2, 3, 4, 6, 8, 12, 24，2022/9/16例15.2.1 解（续） 对a, bS6(或S24)，有a*b = GLBa, b= GCDa, bS6(或S24)ab = LUBa, b = LCMa, bS6(或S24)对应的Hasse图如图 (a)和图 (b)所示。61232412123684(a)(b)2022/9/16例15.2.1 解（续）（4）因为在全序集中，对任意a

5、, bL，都有a b或b a成立。若a b成立，则a, b有最大下界为a，最小上界为b；若b a成立，则a, b有最大下界为b，最小上界为a；故是一个格。2022/9/16例15.2.2判断哈斯图如下图所示的几个偏序集是否是格。(a)abcdefg(a)(b)abcde(c)abcdea(e)bcdea(d)bcdeba(f)cefd2022/9/16例15.2.2（续）a(g)bdfhceghadbcf(h)ge(i)abcdeffb(j)baceca(k)bdea(l)bcde2022/9/16例15.2.2（续）分析 图 (h)中2元素子集g, h不存在最小上界，图 (i)中2元素子集e

6、, f不存在最小上界，图 (j)中2元素子集e, f不存在最小上界，图 (k)中2元素子集a, b不存在最大下界，图 (l)中2元素子集d, e不存在最大下界，因此它们都不是格。解 图 (a)至(g)中的偏序集都是格，图 (h)至(l)中的偏序集都不是格。2022/9/16定义15.2.2 设是具有两个二元运算的代数系统，如果运算和满足交换律、结合律和吸收律，则称为格。 把由代数系统定义的格称为代数格。2022/9/16例15.2.3 设A是一个集合，P(A)是A的幂集，和分别是集合的交和并运算，试证明代数系统是一个格。证明 由集合的运算性质知，交和并运算都满足交换律、结合律和吸收律，因此由定

7、义15.2.2知，是一个格。2022/9/16定理15.2.1偏序格与代数格是等价的。证明 先证偏序格是代数格。设是一个格，*和分别是L上的保交和保联。对任意a, bL，由最小上界和最大下界的惟一性知，a*b = b*a，ab = ba即*和都满足交换律。2022/9/16定理15.2.1 证明（续）对任意a, b, cL，因为(a*b)*c a*b b，(a*b)*c c，所以(a*b)*c b*c又因为(a*b)*c a*b a，于是有(a*b)*c a*(b*c)同样有，a*(b*c) (a*b)*c。故(a*b)*c = a*(b*c)即*满足结合律。同理可证，满足结合律。2022/9

8、/16定理15.2.1 证明（续）对任意a, bL，因为a a，a ab，所以a a*(ab)显然a*(ab) a，故a*(ab) = a同理可证，a (a*b) = a。故*与满足吸收律。综上，是一个格。2022/9/16定理15.2.1证明（续）再证一个代数格是一个偏序格。设代数系统一个格，在L上定义一种关系“ ”如下： 对任意a, bL，有a b ab = a(1)分下面3步证明。（1）证明 是偏序关系。对任意aL，由吸收律有aa = a(a(aa) = a故a a，即关系 是自反的。 2022/9/16定理15.2.1证明（续）对任意a, bL，若a b，b a，有：ab = a，ab

9、 = b所以a = b，即关系 是反对称的。对任意a, b, cL，若a b，b c，有ab = a, bc = b由结合律知ac = (ab)c = a(bc) = ab = a所以a c，即关系 是传递的。故 是偏序关系，即是偏序集。2022/9/16定理15.2.1 证明（续）（2）证明：对任意a, bL，有ab = a ab = b事实上，若有ab = a，则由吸收律ab = (ab)b = b反之，若ab = b，再由吸收律ab = a(ab) = a因此，a b ab = a ab = b。2022/9/16定理15.2.1证明（续）（3）证明：对任意a, bL，a, b存在最大下

10、界和最小上界。由吸收律a(ab) = a a abb(ab) = b b ab因此，ab是a, b的一个上界。设cL是a, b的任意一个上界，即a c，b c，于是有ac = c，bc = c2022/9/16定理15.2.1证明（续）由结合律知(ab)c = a(bc) = ac = c故有ab c，即ab是a, b的最小上界。同理，ab是a, b的最大下界。故是一个格。且有a*b = ab， ab = ab注意：偏序格与代数格等价，今后就不再区分偏序格与代数格了，而把它们统称为格。2022/9/16自然运算与自然偏序任何偏序格都存在两个二元运算保交(*)和保联()，称之为格的自然运算；代数

11、格都可以得到一个偏序关系 ，称之为格的自然偏序。2022/9/16对偶格对于集合L的任何偏序关系“ ”，其逆关系“”也是集合L上的偏序关系；对L的任意子集T，T在偏序集中的最大下界和最小上界分别是中的最小上界和最大下界。因此偏序集是格当且仅当是格，我们称此两个格为对偶格；格的保联运算与保交运算分别是对偶格的保交运算和保联运算。2022/9/16对偶原理 对于格的任何命题，将保联运算与保交运算分别换成对偶格的保交运算和保联运算，将命题中的“ ”换成对偶格中的“”，得到的一个关于对偶格中的命题，称这个命题为对偶命题。 容易证明，关于格的任何真命题，其对应的对偶命题在对偶格中也是真命题，把这个原理称

12、为对偶原理。2022/9/16性质15.2.1设是格，“ ”是“ ”的逆关系。则对任意a, b, c, dL，有（1）自反性：a a；aa（2）反对称性：a b且b aa = b ab且ba a = b （3）传递性：a b且b c a c； ab且bcac（4）a*b a；ab a（5）c a且c b c a*b； ca且cbcab2022/9/16性质15.2.1（续）（6）交换律：a*b = b*a；ab = ba。（7）结合律：(a*b)*c = a* (b*c)； (ab) c = a (bc) （8）吸收律：a* (ab) = a； a (a*b) = a（9）幂等律：a*a =

13、a；aa = a（10）a b a*b = a ab = b2022/9/16性质15.2.1（续）（11）a b且c da*c b*d； a b且c dac bd（12）保序性：a b a*c b*c； a b ac bc（13）分配不等式： a (b*c) (ab) * (ac)； a* (bc)(a*b) (a*c) （14）模不等式： a c a (b*c) (ab) *c2022/9/16性质15.2.1 证明性质(1)、(2)、(3) (4)、(5)直接可得。性质(6)、(7)、(8)由定理15.2.1的直接得到。性质(9)由性质(8)得到：a*a = a*(a(a*a) = a，

14、aa = a (a*(aa) = a。性质(10)由最大下界和最小上界的定义直接得到。性质(11)：因a*c a，a*c c，由假设a b，c d，利用传递性得a*c b，a*c d，由性质(5)得a*c b*d；同理可证，ac bd。性质(12)是性质(11)中c = d的特殊情况。2022/9/16性质15.2.1 证明（续）性质(13)：因a*b a，ac a，所以(ab) (ac) a由于ab b，ac c，由性质11得(ab) (ac) bc故(ab) (ac) a (bc)，即a(bc)(ab)(ac)2022/9/16性质15.2.1 证明（续）性质(14)：必要性：若a c，则

15、ac = c，由性质13得a (bc) (ab)c充分性：若a (bc) (ab) c，因a a(bc)，(ab)c c由传递性得a c。2022/9/16定义15.2.3设代数系统是一个格，S L，若S满足：（1）S；（2）运算和对子集S都是封闭的；则称是的子格，简称S是L的子格。2022/9/16例15.2.4在正整数集合Z+中规定、为：对任意a, bP，ab = a, b，其中a, b表示a, b的最小公倍数ab = (a, b)，其中(a, b)表示a, b的最大公因数则, 是Z+上的二元运算，且满足交换律、结合律、吸收律和等幂律，于是是一个格。S = 3k | kZ+Z+，试证明是的

16、子格。2022/9/16例15.2.4 证明显然S。因为对任意3m, 3nS，都有3m3n = 3m, 3n = 3m, nS，3m3n = (3m, 3n) = 3(m, n)S所以，是的子格。2022/9/16子格定义15.2.4 设是一个格，S L，若S满足：（1）S；（2）对任意a, bS， 的保交和保联运算都有ab = GLBa, bS，ab = LUBa, bS，则称是的一个子格，简称S是L的子格。2022/9/16例15.2.5在如下图 (a)所示的偏序格中，考虑如下子集：B1 = a, b, g, h，B2 = a, b, c, d，B3 = a, b, d, h ，问B1，B

17、2，B3中那些是的子格？habca(a)bdfhceg(b)2022/9/16例15.2.5（续）分析 显然B1，B2，B3都是L的非空子集，B1是L的子格；B2的2元素子集b, c的最小上界e不在B2中，因此B2不是L的子格；B3的2元素子集b, c的最小上界e不在B3中，因此B3不是L的子格。注意，偏序集的哈斯图如上图 (b)所示，因此是格。即存在子集关于偏序能构成格，但不是子格，主要原因是它们的保交或保联运算不一样。解 B1是L的子格，B2, B3, B4都不是L的子格。2022/9/16例15.2.5设是一个格，aL，令S = x|xL, x a，则S是L的子格。证明 因为a a，所以

18、aS，即S是非空子集。对任意x, yS，由x a，y a，可知xy = GLBx, y a，即xy = GLBx, ySxy = LUBx, y a，即xy = LUBx, yS故S是L的子格。 2022/9/16定义15.2.5设和是两个格，f是L到S的映射。如果对任意x, yL，都有f(xy) = f(x)* f(y)，f(xy) = f(x) f(y)则称f为从格到格的格同态映射，简称格同态。如果f是格同态，当f分别是单射、满射和双射时，f分别称为单一格同态、满格同态和格同构。2022/9/16定理15.2.3 (保序定理)设和是两个格，对应的偏序关系为 1、 2，则有：（1）如f：L1

19、L2是格同态，则对任意a, bL1，a 1 b f(a) 2 f(b)；（2）如f：L1L2是格同构，则对任意a, bL1，a 1 b f(a) 2 f(b)。证明 （1）对任意a, bL1，若a 1b，则有a*1b = a，由同态式知：f(a)*2f(b) = f(a*1b) = f(a)所以f(a) 2f(b)。2022/9/16定理15.2.3（续）（2）“”：若f是格同构，则f是格同态。由(1)知：对任意a, bL1，a 1b f(a) 2f(b)。“”：对任意a, bL1，有f(a) 2 f(b) f(a)*2f(b) = f(a)于是，由同态式知f(a*1b) = f(a)*2f(

20、b) = f(a)因f是单射，故有a*1b = a所以，a 1b。2022/9/16例15.2.6设是格，其中L = a, b, c, d, e，它的Hasse图如右图所示。也是一个格。作映射f：LP(L)，使得对任意xL，有f(x) = yyL，y x试证明：f是保序映射，但不是格同态。ebcda2022/9/16例15.2.6（续）分析 要证明f是保序映射，必须验证：对任意x, yL，xy f(x) f(y)。而证明f不是格同态，只需要找到一对x, yL，使得f(xy)f(x)f(y) 。证明 容易验证f是保序映射。对于b, dL，有bd = a，f(bd) = f(a) = L，而f(b

21、)f(d) = b, ed, e = b, d, e所以，f(bd)f(b)f(d)，即f不是格同态。2022/9/16定义15.2.6设是一个格，如果对任意a, b, cL，都有a (bc) = (ab) (ac) ， a (bc) = (ab) (ac)，即运算满足分配律，则称是一个分配格。2022/9/16例15.2.7（1）设A为任意一个集合，格是否是分配格？（2）设P为命题公式集合，与分别是命题公式的合取与析取运算，格是否是分配格？解 （1）因集合的交、并运算满足分配律，所以，格是一个分配格。（2）因命题公式的析取、合取运算满足分配律，所以，格是分配格。2022/9/16定理15.2

22、.4所有链都是分配格。证明 设是链，因此是格，任取a, b, cL，只有以下两种情况：（1）a是三者中最大的，即b a，c a；（2）a不是三者中最大的，即a b或a c。在情况(1)中，bc a，故a (bc) = bc。显然，ab = b，ac = c。所以a (bc) = bc = (ab) (ac)。2022/9/16定理15.2.4（续）在情况(2)中，a bc，而ab = a或ac = a，从而(ab) (ac) = a，所以(ab) (ac) = a = a (bc) 所以是分配格。 2022/9/16例15.2.8右图所示的两个格都不是分配格。分析 由于链是分配格，因此在同一条

23、链上的元素都满足分配等式，最有可能不满足分配等式的元素不在同一条链上。选取b, c, d来验证即可。a(b)bcdea(a)bcde2022/9/16例15.2.8（续）解 取图中b, c, d三个元素验证。在图 (a)中，b (cd) = ba = b，而(bc) (bd) = ee = e。在图 (b)中，b (cd) = ba = b，而(bc) (bd) = ed = d。因此，在图 (a)和(b)中都有，b (cd)(bc) (bd)故它们都不是分配格。2022/9/16定理15.2.5一个格是分配格的充分必要条件是该格中没有任何子格与图15.2.7（例15.2.8）中的两个五元素格

24、中的任何一个同构。2022/9/16性质15.2.2（1）四个元素以下的格都是分配格；（2）五个元素的格仅有两个格是非分配格(图15.2.7(a)和(b)，其余三个格(右图 (a), (b)和(c)都是分配格。(a)(a)abcde(b)abcde(c)abcde2022/9/16定理15.2.6设是分配格，对于任何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 =

25、 ay)= y(吸收律)2022/9/16定义15.2.7设是格，如果对任意a, b, cL，有a b a (bc) = b (ac) 或(模律) a b a (bc) = b (ac)则称为模格，也称为戴德金格 2022/9/16定理15.2.7分配格是模格。证明 设是分配格，对任意a, b, cL，如果a b，那么ab = b，由分配律得 a (bc) = (ab)(ac) = b(ac)故是模格。2022/9/16性质13.2.3（1)每一个链格都是模格；（2）四个元素以下的格都是模格；（3）五个元素的格仅有一个格不是模格(图15.2.7(b)，其余四个格(图15.2.7(a), 图15

26、.2.8(a), (b)和(c)都是模格。 2022/9/16定义15.2.8设是一个格，若存在元素aL，使得对任意xL，都有：a x(或x a)，则称a为格的全下界(或全上界)，分别记为0(或1)，具有全上界和全下界的格称为有界格。显然，对任意xL，有1x = x1 = x，1x = x1 = 10 x = x0 = 0，0 x = x0 = x2022/9/16有限格与有界格若是有限格，设L = a1, a2, , an，由于运算“”和“”满足结合律，所以有(a1a2)an) = a1a2an(a1a2)an) = a1a2an此时， a1a2an和a1a2an分别是格L的全下界和全上界，

27、即有a1a2an = 0a1a2an = 1所以，有限格一定是有界格。2022/9/16定理15.2.8 在格中，全下界和全上界分别是集合L的最小元和最大元，由于最大元和最小元的惟一性，有下面的定理： 定理15.2.8 设是一个格，若格的全上界和全下界存在，则必惟一。2022/9/16定义15.2.9 设为有界格，1和0分别为它的全上界和全下界，aL。如果存在bL，使得ab = 0，ab = 1，则称b为a的补元，记为a。 若有界格中的所有元素都存在补元，则称为有补格。2022/9/16例15.2.9如下图有界格，求其所有元素的补元(如果有的话)。a0(b)bd1c0(a)abd1ce2022

28、/9/16例15.2.9（续）解 对于图a 0 = 1，1 = 0， a = e，c = e， c = d，e = a， d无补元。 对于图b 0 = 1，1 = 0， a = d，a = c， b = d，b = c， c = a，c = b， d = a，d = b则图a不是有补格，图b是有补格。2022/9/16定理15.2.9 在有界分配格(既是有界格又是分配格，简称为有界分配格)中，如元素aL有补元存在，则此元素的补元必惟一。证明 设a有两个补元b和c，由补元的定义知ab = 0 = ac，ab = 1 = ac由定理15.2.6知，b = c。推论15.2.1 在有补分配格(既是有

29、补格又是分配格，简称为有补分配格)中，每个元素都存在惟一的补元。2022/9/16定理15.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。2022/9/16定理15.2.10（续）证明 （1）因a是a的补元，反过来，a也是a的补元，由推论15.2.1得，(a) = a。（2）因为(ab) (ab)= (ab) a) (ab) b)(分配律)= (aa)b) (a (bb)(交换律，结合律)= (

30、0b) (a0)= 00 = 02022/9/16定理15.2.10（续）(ab) (ab)= (a (ab) * (b (ab)(分配律)= (aa) b) * (a (bb)(交换律，结合律)= (1b) (a1)= 11 = 1所以， ab是ab的补元，由补元的惟一性得，(ab) = ab。同理可证，(ab) = ab。2022/9/16定理15.2.10（续）（3）“”，由a b，可得ab = a，则有(ab) = a由De Morgan律(即(2)，有ab = a ，即是b a“”，上述过程可逆，故成立。 （4）“”由a b，根据(3)，有b a则ab aa = 0，即是2022/9

31、/16定理15.2.10（续）ab 0，又0是全下界，有0 ab则根据偏序关系“ ”的反对称性，有ab = 0，对上式使用De Morgan律，自然有ab = 12022/9/16定理15.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。2022/9/16定义15.3.1称有补分配格为布尔格。在有补分配格中每个元都有补元而且补元惟一，可以将求元素的补元作为一种一元运算，则此布尔格可记为，此时

32、，称为布尔代数。因此有：定义15.3.2 一个布尔格称为布尔代数。若一个布尔代数的元素个数是有限的，则称此布尔代数为有限布尔代数，否则称为无限布尔代数。2022/9/16布尔代数 布尔代数是有补分配格，有补分配格必须满足它是格、有全上界和全下界、分配律成立、每个元素都有补元存在。显然，全上界1和全下界0可以用下面的同一律来描述：同一律：在L中存在两个元素0和1，使得对任意aL，有a1 = a，a0 = a。2022/9/16布尔代数补元的存在可以用下面的互补律来描述。互补律：对任意aL，存在aL，使得aa = 0，aa = 1。 格可以用交换律、结合律、吸收律来描述。因此，一个有补分配格就必须满足交换律、结合律、吸收律、分配律、同一律、互补律。另外，可以证明，由交换律、分配律、同一律、互补律可以得到结合律、吸收律。所以布尔代数有下面的等价定义： 2022/9/16定义15.2.3设是代数系统，其中、是B中的二元运算，如果对任意a, b, cB，满足（1）交换律：ab = ba，ab = ba；