《（本科）第14章 格与布尔代数ppt课件.ppt》由会员分享，可在线阅读，更多相关《（本科）第14章 格与布尔代数ppt课件.ppt（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、课程主讲人：（本科）第（本科）第1414章章 格与布尔代数格与布尔代数pptppt课件课件电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程离离 散散 数数 学学2022年5月16日星期一电子科技大学离散数学课程组电子科技大学离散数学课程组3电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16第第1515章章 格与布尔代数格与布尔代数集合的表示方法集合的表示方法2子格与格同态子格与格同态3特殊格特殊格4偏序格与代数格偏序格与代数格1格的性质格的性质2布尔代数布尔代数54电子科
2、技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-1615.1 15.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 格的定义及格的定义及性质性质2 2 子格与格同子格与格同态态3 3 特殊格特殊格4 4 布尔代数布尔代数31 1 斯通定理斯通定理2 2 布尔函数布尔函数 21 1 格与布尔代格与布尔代数的证明数的证明5电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16偏序格偏序格 efabdcabcd(a)(b)比较右边两个哈比较右边
3、两个哈斯图的不同？斯图的不同？6电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定义定义设设是一个偏序集，如果对任意是一个偏序集，如果对任意a, bLa, bL，a, ba, b都有最大下界和最小上界存在，则称都有最大下界和最小上界存在，则称L, 是是格格，简称，简称L L是是格格。若。若L L为有限集，则称格为有限集，则称格L, 为为有限格有限格。暂且把由偏序关系定义的格称为暂且把由偏序关系定义的格称为偏序格偏序格7电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程20
4、22-5-16保交与保联保交与保联在格在格中，任取中，任取a, bGa, bG，则，则a, ba, b的最大的最大下界和最小上界都是惟一存在的，且均属于下界和最小上界都是惟一存在的，且均属于L L。用用a a* *b b表示表示a, ba, b的最大下界，称为的最大下界，称为a a与与b b的的保交保交，用用a a b b表示表示a, ba, b的最小上界，称为的最小上界，称为a a与与b b的的保联保联，即即a a* *b = GLBa, bb = GLBa, b，a a b = LUBa, bb = LUBa, b也可用也可用和和、和、和、和和分别表示保交和保分别表示保交和保联联 8电子科
5、技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例（1 1）考虑偏序集）考虑偏序集Z, D，其中，其中Z Z+ +是正整数，是正整数，D D是是一个整除关系，问此偏序集一个整除关系，问此偏序集Z, D是否是一个格？是否是一个格？（2 2）设）设A A是一个集合，是一个集合，P(A)P(A)是是A A的幂集，是集合上的幂集，是集合上的包含关系，问此偏序集的包含关系，问此偏序集是否是一个格？是否是一个格？（3 3）考虑偏序集）考虑偏序集S, D，其中，其中D D是一个整除关系，是一个整除关系，S Sn n是是n n的所有因子的集合
6、，问此偏序集的所有因子的集合，问此偏序集S, D是否是否是一个格？是一个格？（4 4）所有的全序集）所有的全序集都是格？都是格？9电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例（续）例（续）分析分析 判断一个偏序集判断一个偏序集是否是格，要对是否是格，要对L L的的所有所有2 2元素子集看它是否都有最大下界和最小上界元素子集看它是否都有最大下界和最小上界解解 （1 1）对）对a, ba, bZ Z，有，有a a* *b = GLBa, b = GCDa, bb = GLBa, b = GCDa, bZ ZGCDGCD表
7、示表示a, ba, b的最大公因子。的最大公因子。a a b = LUBa, b = LCMa, bb = LUBa, b = LCMa, bZ ZLCMLCM表示表示a, ba, b的最小公倍数。的最小公倍数。所以，所以，Z, D是一个格。是一个格。10电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例15.2.1 15.2.1 解（续）解（续）（2 2）对）对S S1 1，S S2 2P(S)P(S)，有，有S S1 1* *S S2 2 = GLBS = GLBS1 1, S, S2 2 = S = S1 1SS2
8、 2P(S)P(S)S S1 1 S S2 2 = LUBS = LUBS1 1, S, S2 2 = S = S1 1S S2 2P(S)P(S)所以，所以，P(S), 是一个格。是一个格。（3 3）由）由(1)(1)可知：可知：S, D一定是一个格。一定是一个格。举例如下：举例如下：当当n = 6n = 6和和n = 24n = 24时，有时，有S, D和和S, D是格。是格。此时此时S S6 6 = 1, 2, 3, 6 = 1, 2, 3, 6，S S2424 = 1, 2, 3, 4, 6, 8, 12, 24 = 1, 2, 3, 4, 6, 8, 12, 24，11电子科技大学离
9、散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例15.2.1 15.2.1 解（续）解（续）对对a, ba, bS S6 6( (或或S S2424) )，有，有a a* *b = GLBa, bb = GLBa, b= GCDa, b= GCDa, bS S6 6( (或或S S2424) )a a b = LUBa, b b = LUBa, b = LCMa, b= LCMa, bS S6 6( (或或S S2424) )对应的对应的HasseHasse图如图图如图 (a) (a)和图和图 (b) (b)所示。所示。612324
10、12123684(a)(b)12电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例15.2.1 15.2.1 解（续）解（续）（4 4）因为在全序集）因为在全序集中，对任意中，对任意a, ba, bL L，都有都有a ba b或或b ab a成立。成立。若若a ba b成立，则成立，则a, ba, b有最大下界为有最大下界为a a，最小上，最小上界为界为b b；若若b ab a成立，则成立，则a, ba, b有最大下界为有最大下界为b b，最小上，最小上界为界为a a；故故是一个格。是一个格。13电子科技大学离散数学课程
11、组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例判断哈斯图如下图所示的几个偏序集是否是格。判断哈斯图如下图所示的几个偏序集是否是格。(a)abcdefg(a)(b)abcde(c)abcdea(e)bcdea(d)bc deba(f)cefd14电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例（续）例（续）a(g)bdfhceghadbcf(h)ge(i)abcdeffb(j)baceca(k)bdea(l)bcde15电子科技大学离散数学课程组电子科技大学离散数学课程
12、组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例（续）例（续）分析分析 图图 (h) (h)中中2 2元素子集元素子集g, hg, h不存在最小上界，不存在最小上界，图图 (i) (i)中中2 2元素子集元素子集e, fe, f不存在最小上界，图不存在最小上界，图 (j) (j)中中2 2元素子集元素子集e, fe, f不存在最小上界，图不存在最小上界，图 (k) (k)中中2 2元元素子集素子集a, ba, b不存在最大下界，图不存在最大下界，图 (l) (l)中中2 2元素子元素子集集d, ed, e不存在最大下界，因此它们都不是格。不存在最大下界，因此它们都不是格
13、。解解 图图 (a) (a)至至(g)(g)中的偏序集都是格，图中的偏序集都是格，图 (h) (h)至至(l)(l)中的偏序集都不是格。中的偏序集都不是格。16电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16代数格代数格定义定义设设是具有两个二元运算的代数系统，是具有两个二元运算的代数系统，如果运算如果运算和和满足交换律、结合律和吸收律，则满足交换律、结合律和吸收律，则称称为为格格。把由代数系统定义的格称为把由代数系统定义的格称为代数格代数格。17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程
14、 双语示范课程双语示范课程2022-5-16例例设设A A是一个集合，是一个集合，P(A)P(A)是是A A的幂集，的幂集，和和分别是集分别是集合的交和并运算，试证明代数系统合的交和并运算，试证明代数系统是一个格。是一个格。证明证明 由集合的运算性质知，交和并运算都满足交由集合的运算性质知，交和并运算都满足交换律、结合律和吸收律，因此由定义知，换律、结合律和吸收律，因此由定义知，P(A), , 是一个格。是一个格。18电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理定理偏序格与代数格是等价的。偏序格与代数格是等价的。证
15、明证明 先证偏序格是代数格。先证偏序格是代数格。设设L 是一个格，是一个格，* *和和 分别是分别是L L上的保交和上的保交和保联。对任意保联。对任意a, bLa, bL，由最小上界和最大下界的，由最小上界和最大下界的惟一性知，惟一性知，a a* *b = bb = b* *a a，a a b = bb = b a a即即* *和和 都满足交换律。都满足交换律。19电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理定理15.2.1 15.2.1 证明（续）证明（续）对任意对任意a, b, cLa, b, cL，因为，因为
16、(a(a* *b)b)* *c ac a* *b bb b，(a(a* *b)b)* *c cc c，所以，所以(a(a* *b)b)* *c bc b* *c c又因为又因为(a(a* *b)b)* *c ac a* *b ab a，于是有，于是有(a(a* *b)b)* *c ac a* *(b(b* *c)c)同样有，同样有，a a* *(b(b* *c) (ac) (a* *b)b)* *c c。故。故(a(a* *b)b)* *c = ac = a* *(b(b* *c)c)即即* *满足结合律。满足结合律。同理可证，同理可证， 满足结合律。满足结合律。20电子科技大学离散数学课程组
17、电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理定理15.2.1 15.2.1 证明（续）证明（续）对任意对任意a, bLa, bL，因为，因为a aa a，a aa a b b，所以，所以a aa a* *(a(a b)b)显然显然a a* *(a(a b) ab) a，故，故a a* *(a(a b) = ab) = a同理可证，同理可证，a a (a (a* *b) = ab) = a。故故* *与与 满足吸收律。满足吸收律。综上，综上，L, 是一个格。是一个格。21电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品
18、课程 双语示范课程双语示范课程2022-5-16定理证明（续）定理证明（续）再证一个代数格是一个偏序格。再证一个代数格是一个偏序格。设代数系统设代数系统一个格，在一个格，在L L上定义一种关上定义一种关系系“ ”如下：如下： 对任意对任意a, bLa, bL，有，有a b a b ab = a ab = a(1)(1)分下面分下面3 3步证明。步证明。（1 1）证明证明 是偏序关系是偏序关系。对任意对任意aLaL，由吸收律有，由吸收律有aa = a(a(aa) = aaa = a(a(aa) = a故故a aa a，即关系，即关系 是是自反的自反的。 22电子科技大学离散数学课程组电子科技大学
19、离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理证明（续）定理证明（续）对任意对任意a, bLa, bL，若，若a ba b，b ab a，有：，有：ab = aab = a，ab = bab = b所以所以a = ba = b，即关系，即关系 是是反对称的反对称的。对任意对任意a, b, cLa, b, cL，若，若a ba b，b cb c，有，有ab = a, bc = bab = a, bc = b由结合律知由结合律知ac = (ab)c = a(bc) = ab = aac = (ab)c = a(bc) = ab = a所以所以a ca c，即
20、关系，即关系 是是传递的传递的。故故 是偏序关系，即是偏序关系，即是偏序集。是偏序集。23电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理定理15.2.1 15.2.1 证明（续）证明（续）（2 2）证明：对任意）证明：对任意a, bLa, bL，有，有ab = a ab = a ab = b ab = b事实上，若有事实上，若有ab = aab = a，则由吸收律，则由吸收律ab = (ab)b = bab = (ab)b = b反之，若反之，若ab = bab = b，再由吸收律，再由吸收律ab = a(ab) =
21、 aab = a(ab) = a因此，因此，a b a b ab = a ab = a ab = b ab = b。24电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理证明（续）定理证明（续）（3 3）证明：对任意）证明：对任意a, bLa, bL，a, ba, b存在最大下界存在最大下界和最小上界。和最小上界。由吸收律由吸收律a(ab) = a a(ab) = a a ab a abb(ab) = b b(ab) = b b ab b ab因此，因此，abab是是a, ba, b的一个上界。的一个上界。设设cLcL是
22、是a, ba, b的任意一个上界，即的任意一个上界，即a ca c，b b c c，于是有，于是有ac = cac = c，bc = cbc = c25电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理证明（续）定理证明（续）由结合律知由结合律知(ab)c = a(bc) = ac = c(ab)c = a(bc) = ac = c故有故有ab cab c，即，即abab是是a, ba, b的最小上界。的最小上界。同理，同理，abab是是a, ba, b的最大下界。的最大下界。故故是一个格。且有是一个格。且有a a* *
23、b = abb = ab， a a b = abb = ab注意注意：偏序格与代数格等价，今后就不再区分偏：偏序格与代数格等价，今后就不再区分偏序格与代数格了，而把它们统称为格。序格与代数格了，而把它们统称为格。26电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16自然运算与自然偏序自然运算与自然偏序任何偏序格任何偏序格都存在两个二元运算都存在两个二元运算保交保交( (* *) )和保联和保联( ( ) )，称之为格，称之为格的的自然运算自然运算；代数格代数格都可以得到一个偏序关系都可以得到一个偏序关系 ，称之为格称之为格的
24、的自然偏序自然偏序。27电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16格的性质格的性质对偶格对偶格: :对于集合对于集合L L的任何偏序关系的任何偏序关系“ ”，其逆关系，其逆关系“”也是集合也是集合L L上的偏序关系；上的偏序关系；对对L L的任意子集的任意子集T T，T T在偏序集在偏序集中的最大下中的最大下界和最小上界分别是界和最小上界分别是中的最小上界和最大中的最小上界和最大下界。下界。因此偏序集因此偏序集是格当且仅当是格当且仅当是格，是格，我们称此两个格为我们称此两个格为对偶格对偶格；格格的保联运算与保交运算分
25、别是对偶格的保联运算与保交运算分别是对偶格L, 的保交运算和保联运算。的保交运算和保联运算。28电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16对偶原理对偶原理对于格对于格的任何命题，将保联运算与保交运的任何命题，将保联运算与保交运算分别换成对偶格算分别换成对偶格的保交运算和保联运算，的保交运算和保联运算，将命题中的将命题中的“ ”换成对偶格换成对偶格中的中的“”，得到的一个关于对偶格，得到的一个关于对偶格中的命题，中的命题，称这个命题为称这个命题为对偶命题对偶命题。容易证明，关于格容易证明，关于格的任何真命题，其对应的任
26、何真命题，其对应的对偶命题在对偶格的对偶命题在对偶格中也是真命题，把这中也是真命题，把这个原理称为个原理称为对偶原理对偶原理。29电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16性质性质设设是格，是格，“”是是“ ”的逆关系。则对的逆关系。则对任意任意a, b, c, dLa, b, c, dL，有，有（1 1）自反性：自反性：a aa a；aaaa（2 2）反对称性：反对称性：a ba b且且b ab aa = b a = b ab ab且且ba ba a = b a = b （3 3）传递性：传递性：a ba b且且b
27、 c b c a c a c； abab且且bcacbcac（4 4）a a* *b ab a；a a baba（5 5）c ac a且且c b c b c a c a* *b b； ca ca且且cbcacbca b b30电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16性质（续）性质（续）（6 6）交换律交换律：a a* *b = bb = b* *a a； a a b = bb = b a a。（7 7）结合律结合律：(a(a* *b)b)* *c = ac = a* * (b (b* *c)c)； (a(a b)
28、b) c = ac = a (b (b c)c) （8 8）吸收律：吸收律：a a* * (a (a b) = ab) = a； a a (a (a* *b) = ab) = a（9 9）幂等律：幂等律：a a* *a = aa = a；a a a = aa = a（1010）a b a b a a* *b = a b = a a a b = bb = b31电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16性质（续）性质（续）（1111）a ba b且且c dc da a* *c bc b* *d d； a b a b且且
29、c dac da c bc b d d（1212）保序性：保序性：a b a b a a* *c bc b* *c c； a b a b a a c bc b c c（1313）分配不等式分配不等式： a a (b (b* *c) (ac) (a b) b) * * (a (a c)c)； a a* * (b (b c)(ac)(a* *b) b) (a (a* *c)c) （1414）模不等式模不等式： a c a c a a (b (b* *c) (ac) (a b) b) * *c c32电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课
30、程2022-5-16性质性质15.2.1 15.2.1 证明证明性质性质(1)(1)、(2)(2)、(3)(3) (4)(4)、(5)(5)直接可得。直接可得。性质性质(6)(6)、(7)(7)、(8)(8)由定理的直接得到。由定理的直接得到。性质性质(9)(9)由性质由性质(8)(8)得到：得到：a a* *a = aa = a* *(a(a (a(a* *a) = aa) = a，a a a = aa = a (a (a* *(a(a a) = aa) = a。性质性质(10)(10)由最大下界和最小上界的定义直接得到。由最大下界和最小上界的定义直接得到。性质性质(11)(11)：因：因a
31、 a* *c ac a，a a* *c cc c，由假设，由假设a a b b，c dc d，利用传递性得，利用传递性得a a* *c bc b，a a* *c dc d，由性质由性质(5)(5)得得a a* *c bc b* *d d；同理可证，；同理可证，a a c c b b d d。性质性质(12)(12)是性质是性质(11)(11)中中c = dc = d的特殊情况。的特殊情况。33电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16性质性质15.2.1 15.2.1 证明（续）证明（续）性质性质(13)(13)：因
32、：因a a* *b ab a，a a c ac a，所以，所以(a(a b) b) (a (a c) ac) a由于由于a a b bb b，a a c cc c，由性质，由性质1111得得(a(a b) b) (a (a c) bc) b c c故故(a(a b) b) (a (a c) ac) a (b (b c)c)，即，即a a (b(b c)(ac)(a b)b) (a(a c)c)34电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16性质性质15.2.1 15.2.1 证明（续）证明（续）性质性质(14)(14)
33、：必要性必要性：若：若a ca c，则，则a a c = cc = c，由性质，由性质1313得得a a (b (b c) (ac) (a b)b) c c充分性充分性：若：若a a (b (b c) (ac) (a b) b) c c，因，因a aa a (b(b c)c)，(a(a b)b) c cc c由传递性得由传递性得a ca c。35电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16子格与格同态子格与格同态定义定义15.2.3:15.2.3:设代数系统设代数系统L, 是一个格，是一个格，S S L L，若，若S
34、S满足：满足：（1 1）SS；（2 2）运算）运算 和和 对子集对子集S S都是封闭的；都是封闭的；则称则称S, 是是L, 的的子格子格，简称，简称S S是是L L的的子格。子格。36电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例在正整数集合在正整数集合Z Z+ +中规定中规定 、 为：对任意为：对任意a, bPa, bP，a a b = a, bb = a, b，其中，其中a, ba, b表示表示a, ba, b的最小公倍数的最小公倍数a a b = (a, b)b = (a, b)，其中，其中(a, b)(a,
35、b)表示表示a, ba, b的最大公因数的最大公因数则则 , , 是是Z Z+ +上的二元运算，且满足交换律、结合律、上的二元运算，且满足交换律、结合律、吸收律和等幂律，于是吸收律和等幂律，于是Z+, 是一个格。是一个格。S = S = 3k | kZ3k | kZ+ +ZZ+ +，试证明，试证明S, 是是Z 的的子格。子格。37电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例15.2.4 15.2.4 证明证明显然显然SS。因为对任意。因为对任意3m, 3nS3m, 3nS，都有，都有3m3m 3n = 3m, 3n
36、 = 3m, nS3n = 3m, 3n = 3m, nS，3m3m 3n = (3m, 3n) = 3(m, n)S3n = (3m, 3n) = 3(m, n)S所以，所以，S, 是是Z+, 的子格。的子格。38电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16子格子格定义定义15.2.4 15.2.4 设设是一个格，是一个格，S S L L，若，若S S满足：满足：（1 1）SS；（2 2）对任意）对任意a, bSa, bS， 的保交和保联运的保交和保联运算都有算都有a a b = GLBa, bSb = GLBa,
37、bS，a a b = LUBa, bSb = LUBa, bS，则称则称是是的一个的一个子格子格，简称，简称S S是是L L的的子格。子格。39电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例在如下图在如下图 (a) (a)所示的偏序格所示的偏序格中，考虑如下中，考虑如下子集：子集：B B1 1 = a, b, g, h = a, b, g, h，B B2 2 = a, b, c, d = a, b, c, d，B B3 3 = a, b, d, h = a, b, d, h ，问，问B B1 1，B B2 2，B B
38、3 3中那些是中那些是L, 的子格？的子格？habca(a)bdfhceg(b)40电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例（续）例（续）分析分析 显然显然B B1 1，B B2 2，B B3 3都是都是L L的非空子集，的非空子集，B B1 1是是L L的的子格；子格；B B2 2的的2 2元素子集元素子集b, cb, c的最小上界的最小上界e e不在不在B B2 2中，中，因此因此B B2 2不是不是L L的子格；的子格；B B3 3的的2 2元素子集元素子集b, cb, c的最小的最小上界上界e e不在不在
39、B B3 3中，因此中，因此B B3 3不是不是L L的子格。的子格。注意注意，偏序集，偏序集B, 的哈斯图如上图的哈斯图如上图 (b) (b)所示，所示，因此因此B, 是格。即存在子集关于偏序能构成是格。即存在子集关于偏序能构成格，但不是子格，主要原因是它们的保交或保联运格，但不是子格，主要原因是它们的保交或保联运算不一样。算不一样。解解 B B1 1是是L L的子格，的子格，B B2 2, B, B3 3, B, B4 4都不是都不是L L的子格。的子格。41电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例设设是一
40、个格，是一个格，aLaL，令，令S = x|xL, x S = x|xL, x a a，则，则S S是是L L的子格。的子格。证明证明 因为因为a aa a，所以，所以aSaS，即，即S S是非空子集。是非空子集。对任意对任意x, ySx, yS，由，由x ax a，y ay a，可知，可知x x y = GLBx, y ay = GLBx, y a，即，即x x y = GLBx, ySy = GLBx, ySx x y = LUBx, y ay = LUBx, y a，即，即x x y = LUBx, ySy = LUBx, yS故故S S是是L L的子格。的子格。 42电子科技大学离散数
41、学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定义定义设设和和S, 是两个格，是两个格，f f是是L L到到S S的的映射。如果对任意映射。如果对任意x, yLx, yL，都有，都有f(xy) = f(x)f(xy) = f(x)* * f(y) f(y)，f(xy) = f(x) f(xy) = f(x) f(y) f(y)则称则称f f为从格为从格到格到格S, 的的格同态格同态映射映射，简称，简称格同态格同态。如果如果f f是格同态，当是格同态，当f f分别是单射、满射和双射时，分别是单射、满射和双射时，f f分别称为分别称为单一格同
42、态、满格同态和格同构单一格同态、满格同态和格同构。43电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理定理15.2.3 (15.2.3 (保序定理保序定理) )设设L 和和L 是两个格，对应的偏是两个格，对应的偏序关系为序关系为 1 1、 2 2，则有：，则有：（1 1）如）如f f：L L1 1L L2 2是格同态，则对任意是格同态，则对任意a, ba, bL L1 1，a a 1 1b bf(a) f(a) 2 2f(b)f(b)；（2 2）如）如f f：L L1 1L L2 2是格同构，则对任意是格同构，则对任意
43、a, ba, bL L1 1，a a 1 1b b f(a) f(a) 2 2f(b)f(b)。证明证明 （1 1）对任意）对任意a, ba, bL L1 1，若，若a a 1 1b b，则有，则有a a* *1 1b = ab = a，由同态式知：，由同态式知：f(a)f(a)* *2 2f(b) = f(af(b) = f(a* *1 1b) = f(a)b) = f(a)所以所以f(a) f(a) 2 2f(b)f(b)。44电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理（续）定理（续）（2 2）“”：若：若f
44、 f是格同构，则是格同构，则f f是格同态。由是格同态。由(1)(1)知：对任意知：对任意a, ba, bL L1 1，a a 1 1b b f(a) f(a) 2 2f(b)f(b)。“”：对任意：对任意a, ba, bL L1 1，有，有f(a) f(a) 2 2 f(b) f(b) f(a) f(a)* *2 2f(b) = f(a)f(b) = f(a)于是，由同态式知于是，由同态式知f(af(a* *1 1b) = f(a)b) = f(a)* *2 2f(b) = f(a)f(b) = f(a)因因f f是单射，故有是单射，故有a a* *1 1b = ab = a所以，所以，a
45、a 1 1b b。45电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例设设是格，其中是格，其中L = a, b, L = a, b, c, d, ec, d, e，它的，它的HasseHasse图如右图所图如右图所示。示。P(L), 也是一个格。作映也是一个格。作映射射f f：LP(L)LP(L)，使得对任意，使得对任意xLxL，有有f(x) = yf(x) = yyLyL，y xy x试证明：试证明：f f是保序映射，但不是格是保序映射，但不是格同态。同态。ebcda46电子科技大学离散数学课程组电子科技大学离散数学
46、课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例（续）例（续）分析分析 要证明要证明f f是保序映射，必须验证：对任意是保序映射，必须验证：对任意x, x, yLyL，xy f(x) xy f(x) f(y)f(y)。而证明。而证明f f不是格同态，不是格同态，只需要找到一对只需要找到一对x, yLx, yL，使得，使得f(xf(x y)f(x)f(y)y)f(x)f(y) 。证明证明 容易验证容易验证f f是保序映射。是保序映射。对于对于b, dLb, dL，有，有b b d = ad = a，f(bf(b d) = f(a) = Ld) = f(a) = L，而
47、而f(b)f(d) = b, ed, e = b, d, ef(b)f(d) = b, ed, e = b, d, e所以，所以，f(bf(b d)f(b)f(d)d)f(b)f(d)，即，即f f不是格同态。不是格同态。47电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定义定义设设L, 是一个格，如果对任意是一个格，如果对任意a, b, cLa, b, cL，都，都有有a a (b(b c) = (ac) = (a b) b) (a (a c)c) ， a a (b(b c) = (ac) = (a b) b) (a
48、(a c)c)，即运算满足分配律，则称即运算满足分配律，则称L, 是一个是一个分配格分配格。48电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16例例（1 1）设）设A A为任意一个集合，格为任意一个集合，格是是否是分配格？否是分配格？（2 2）设）设P P为命题公式集合，为命题公式集合，与与分别是命题公式分别是命题公式的合取与析取运算，格的合取与析取运算，格是否是分配格？是否是分配格？解解 （1 1）因集合的交、并运算满足分配律，所以，）因集合的交、并运算满足分配律，所以，格格是一个分配格。是一个分配格。（2 2）因命题公
49、式的析取、合取运算满足分配律，）因命题公式的析取、合取运算满足分配律，所以，格所以，格是分配格。是分配格。49电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理定理所有链都是分配格。所有链都是分配格。证明证明 设设是链，因此是链，因此是格，任取是格，任取a, b, cLa, b, cL，只有以下两种情况：，只有以下两种情况：（1 1）a a是三者中最大的，即是三者中最大的，即b ab a，c ac a；（2 2）a a不是三者中最大的，即不是三者中最大的，即a ba b或或a ca c。在情况在情况(1)(1)中，中，b
50、 b c ac a，故，故a a (b (b c) = bc) = b c c。显然，显然，a a b = bb = b，a a c = cc = c。所以。所以a a (b (b c) = bc) = b c = (ac = (a b) b) (a (a c)c)。50电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程2022-5-16定理（续）定理（续）在情况在情况(2)(2)中，中，a ba b c c，而，而a a b = ab = a或或a a c = ac = a，从而从而(a(a b) b) (a (a c) = ac) = a