《电子科大离散数学内部教学课件第14章格与布尔代数》由会员分享，可在线阅读，更多相关《电子科大离散数学内部教学课件第14章格与布尔代数（85页珍藏版）》请在金锄头文库上搜索。
1、离 散 数 学,电子科技大学,计算机科学与工程学院 示 范 性 软 件 学 院,2019年8月6日星期二,2019/8/6,第15章 格与布尔代数,2019/8/6,15.1 本章学习要求,2019/8/6,偏序格,比较右边两个哈斯图的不同？,2019/8/6,定义15.2.1,设是一个偏序集，如果对任意a, bL，a, b都有最大下界和最小上界存在，则称是格，简称L是格。若L为有限集，则称格为有限格。 暂且把由偏序关系定义的格称为偏序格,2019/8/6,保交与保联,在格中，任取a, bG，则a, b的最大下界和最小上界都是惟一存在的，且均属于L。 用a*b表示a, b的最大下界，称为a与b
2、的保交，用ab表示a, b的最小上界，称为a与b的保联，即 a*b = GLBa, b，ab = LUBa, b 也可用和、和、和分别表示保交和保联,2019/8/6,例15.2.1,（1）考虑偏序集，其中Z+是正整数，D是一个整除关系，问此偏序集是否是一个格？ （2）设A是一个集合，P(A)是A的幂集，是集合上的包含关系，问此偏序集是否是一个格？ （3）考虑偏序集，其中D是一个整除关系，Sn是n的所有因子的集合，问此偏序集是否是一个格？ （4）所有的全序集都是格？,2019/8/6,例15.2.1（续）,分析 判断一个偏序集是否是格，要对L的所有2元素子集看它是否都有最大下界和最小上界 解
3、（1）对a, bZ，有 a*b = GLBa, b = GCDa, bZ GCD表示a, b的最大公因子。 ab = LUBa, b = LCMa, bZ LCM表示a, b的最小公倍数。 所以，是一个格。,2019/8/6,例15.2.1 解（续）,（2）对S1，S2P(S)，有 S1*S2 = GLBS1, S2 = S1S2P(S) S1S2 = LUBS1, S2 = S1S2P(S) 所以，是一个格。 （3）由(1)可知：一定是一个格。 举例如下： 当n = 6和n = 24时，有和是格。 此时S6 = 1, 2, 3, 6， S24 = 1, 2, 3, 4, 6, 8, 12,
4、24，,2019/8/6,例15.2.1 解（续）,对a, bS6(或S24)，有 a*b = GLBa, b = GCDa, bS6(或S24) ab = LUBa, b = LCMa, bS6(或S24) 对应的Hasse图如图 (a)和图 (b)所示。,2019/8/6,例15.2.1 解（续）,（4）因为在全序集中，对任意a, bL，都有a b或b a成立。 若a b成立，则a, b有最大下界为a，最小上界为b； 若b a成立，则a, b有最大下界为b，最小上界为a； 故是一个格。,2019/8/6,例15.2.2,判断哈斯图如下图所示的几个偏序集是否是格。,2019/8/6,例15.
5、2.2（续）,2019/8/6,例15.2.2（续）,分析 图 (h)中2元素子集g, h不存在最小上界，图 (i)中2元素子集e, f不存在最小上界，图 (j)中2元素子集e, f不存在最小上界，图 (k)中2元素子集a, b不存在最大下界，图 (l)中2元素子集d, e不存在最大下界，因此它们都不是格。 解 图 (a)至(g)中的偏序集都是格，图 (h)至(l)中的偏序集都不是格。,2019/8/6,定义15.2.2,设是具有两个二元运算的代数系统，如果运算和满足交换律、结合律和吸收律，则称为格。 把由代数系统定义的格称为代数格。,2019/8/6,例15.2.3,设A是一个集合，P(A)
6、是A的幂集，和分别是集合的交和并运算，试证明代数系统是一个格。 证明 由集合的运算性质知，交和并运算都满足交换律、结合律和吸收律，因此由定义15.2.2知，是一个格。,2019/8/6,定理15.2.1,偏序格与代数格是等价的。 证明 先证偏序格是代数格。 设是一个格，*和分别是L上的保交和保联。对任意a, bL，由最小上界和最大下界的惟一性知， a*b = b*a，ab = ba 即*和都满足交换律。,2019/8/6,定理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，于是
7、有 (a*b)*c a*(b*c) 同样有，a*(b*c) (a*b)*c。故 (a*b)*c = a*(b*c) 即*满足结合律。 同理可证，满足结合律。,2019/8/6,定理15.2.1 证明（续）,对任意a, bL，因为a a，a ab，所以 a a*(ab) 显然a*(ab) a，故 a*(ab) = a 同理可证，a (a*b) = a。 故*与满足吸收律。 综上，是一个格。,2019/8/6,定理15.2.1证明（续）,再证一个代数格是一个偏序格。 设代数系统一个格，在L上定义一种关系“ ”如下： 对任意a, bL，有 a b ab = a (1) 分下面3步证明。 （1）证明
8、是偏序关系。 对任意aL，由吸收律有 aa = a(a(aa) = a 故a a，即关系 是自反的。,2019/8/6,定理15.2.1证明（续）,对任意a, bL，若a b，b a，有： ab = a，ab = b 所以a = b，即关系 是反对称的。 对任意a, b, cL，若a b，b c，有 ab = a, bc = b 由结合律知 ac = (ab)c = a(bc) = ab = a 所以a c，即关系 是传递的。 故 是偏序关系，即是偏序集。,2019/8/6,定理15.2.1 证明（续）,（2）证明：对任意a, bL，有 ab = a ab = b 事实上，若有ab = a，则
9、由吸收律 ab = (ab)b = b 反之，若ab = b，再由吸收律 ab = a(ab) = a 因此，a b ab = a ab = b。,2019/8/6,定理15.2.1证明（续）,（3）证明：对任意a, bL，a, b存在最大下界和最小上界。 由吸收律 a(ab) = a a ab b(ab) = b b ab 因此，ab是a, b的一个上界。 设cL是a, b的任意一个上界，即a c，b c，于是有 ac = c，bc = c,2019/8/6,定理15.2.1证明（续）,由结合律知 (ab)c = a(bc) = ac = c 故有ab c，即ab是a, b的最小上界。 同理
10、，ab是a, b的最大下界。 故是一个格。且有 a*b = ab， ab = ab,注意：偏序格与代数格等价，今后就不再区分偏序格与代数格了，而把它们统称为格。,2019/8/6,自然运算与自然偏序,任何偏序格都存在两个二元运算保交(*)和保联()，称之为格的自然运算； 代数格都可以得到一个偏序关系 ，称之为格的自然偏序。,2019/8/6,对偶格,对于集合L的任何偏序关系“ ”，其逆关系“”也是集合L上的偏序关系； 对L的任意子集T，T在偏序集中的最大下界和最小上界分别是中的最小上界和最大下界。 因此偏序集是格当且仅当是格，我们称此两个格为对偶格； 格的保联运算与保交运算分别是对偶格的保交运
11、算和保联运算。,2019/8/6,对偶原理,对于格的任何命题，将保联运算与保交运算分别换成对偶格的保交运算和保联运算，将命题中的“ ”换成对偶格中的“”，得到的一个关于对偶格中的命题，称这个命题为对偶命题。 容易证明，关于格的任何真命题，其对应的对偶命题在对偶格中也是真命题，把这个原理称为对偶原理。,2019/8/6,性质15.2.1,设是格，“”是“ ”的逆关系。则对任意a, b, c, dL，有 （1）自反性：a a； aa （2）反对称性：a b且b aa = b ab且ba a = b （3）传递性：ab且bc a c； ab且bc ac （4）a*b a； aba a*b b； ab
12、b,2019/8/6,性质15.2.1（续）,（5）c a且c b c a*b； c a且c b c ab （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 = a；aa = a （10）a b a*b = a ab = b,2019/8/6,性质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 (
13、b*c) (ab) * (ac)； a* (bc)(a*b) (a*c) （14）模不等式： a c a (b*c) (ab) *c,2019/8/6,性质15.2.1 证明,性质(1)、(2)、(3) (4)、(5)直接可得。 性质(6)、(7)、(8)由定理15.2.1的直接得到。 性质(9)由性质(8)得到：a*a = a*(a(a*a) = a，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。 性
14、质(12)是性质(11)中c = d的特殊情况。,2019/8/6,性质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),2019/8/6,性质15.2.1 证明（续）,性质(14)： 必要性：若a c，则ac = c，由性质13得 a (bc) (ab)c 充分性：若a (bc) (ab) c，因 a a(bc)，(ab)c c 由传递性得a c。,2019/8/6,定义15.2.3,设代数系统是一个格，S L，若S满足： （1）S； （2）运算和对子集S都是封闭的； 则称是的子格，简称S是L的子格。,2019/8/6,例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+，试证明是的子格。,2019/8/6,例15.2.4 证明,显然S。因为对任意3m, 3nS，都有 3m3n = 3m, 3n = 3m, nS， 3m3n = (3m, 3n) = 3(m, n)S
