《离散数学 第2版 教学课件 ppt 作者 尤枫 第09章 格与布尔代数》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 尤枫 第09章 格与布尔代数（75页珍藏版）》请在金锄头文库上搜索。
1、9章 格与布尔代数,第9章 格与布尔代数,9.1.1 偏序集定义的格,第9章 格与布尔代数,定义9-1 设是一个偏序集，如果中任意两个 元素a和b都有最小上界和最大下界在L中 存在，则称为格。 也称这样定义的格为偏序格。 一般用ab或LUBa,b表示a和b的最小上界， 用ab或GLBa,b表示a和b的最大下界，和 分别称为保联运算和保交运算。,9.1.1 偏序集定义的格,第9章 格与布尔代数,【例9-1】 设I+是所有正整数的集合，在I+上定义 整除关系|：对于任意的a,bI+，a|b 当且仅当a整除b，则是格。这是 因为|是I+上的一个偏序关系（自反的、 反对称的、可传递的），且对于任意两
2、个元素a,bI+，它们的最小上界和最大 下界为两元素的最小公倍数和最大公约数， 即ab=lcma,b，ab=gcda,b,9.1.1 偏序集定义的格,第9章 格与布尔代数,【例9-2】对任意集合S，(S)是S的幂集，则 是格。因为是(S)上的偏序关 系，且对于任意两个元素A,BS，它们 的最小上界和最大下界分别为两集合的 并集和交集，即 AB=AB, AB=AB 格称为集合的幂集格。,9.1.1 偏序集定义的格,第9章 格与布尔代数,【例9-3】设n是一个正整数，Sn是n的所有正因数 的集合，例如， S8=1,2,4,8， S24=1,2,3,4,6,8,12,24。 又设|是整除关系，则是格
3、。,9.1.1 偏序集定义的格,第9章 格与布尔代数,下面的图分别给出了, , 的哈斯图，由图可以看出，它们都是格。,9.1.1 偏序集定义的格,第9章 格与布尔代数,【例9-4】设P为所有命题公式的集合，定义关 系“”如下： AB当且仅当A蕴涵B 则逻辑蕴涵关系为P上的偏序关系，是一个格。对任意的命题公式A,BP，AB=AB，AB=AB（等式右边的和是逻辑运算符）。 并不是每一个偏序集都是格，下图所示的两哈斯图对应的偏序集就不是格。,9.1.1 偏序集定义的格,第9章 格与布尔代数,定理9-1 若是一个格，则也是一个格， 且格中的保联运算和保交运算（用 和表示）与格中的保联运算和 保交运算（
4、用和表示）满足如下的关 系：对任意的a,bL，有 ab=ab，ab=ab 格和格称为互为对偶的格，关 系和关系称为互为对偶的关系。,9.1.1 偏序集定义的格,第9章 格与布尔代数,定义9-2 一个由格中的元素以及符号 ,=和所组成的命题P的对偶命题是 指命题P*，它是将P中的换为，换 为，换为所得到的命题。 例如，命题(ab)cc的对偶式为命题 (ab)cc。实际上，(ab)cc是格 中的命题，而(ab)cc是格中 的命题。,9.1.1 偏序集定义的格,第9章 格与布尔代数,定理9-2 （对偶原理）对于格中的任一真命 题P，其对偶命题P*也是真命题。 【例9-5】格中的真命题ABA的对偶 命
5、题ABA也是真命题。,9.1.1 偏序集定义的格,第9章 格与布尔代数,定理9-3 设为格，则对L中任何元素a,b和c有 (1) aab，bab aba, abb (2) 若ab，ac，则abc 若ac，bc，则abc (3) 若ab，cd，则acbd， acbd (4) 若bc，则abac， abac,9.1.1 偏序集定义的格,第9章 格与布尔代数,证明 (1) 因为ab是a的一个上界，也是b的一个 上界，所以有aab，bab。 同理，因为ab是a的一个下界，也是b 的一个下界，所以有aba, abb。 (2) 设ab，ac。因为bc是b和c的最 大下界，又由已知条件可知a是b和c的 一个
6、下界，因此有abc。 同理可证若ac，bc，则abc,9.1.1 偏序集定义的格,第9章 格与布尔代数,证明(3) 设ab，cd。由(1)式知bbd， dbd，于是由传递性可得 abd，cbd 这表明bd是a和c的一个上界，而 ac是a和c的最小上界，所以必有 acbd。 同理可证若ab，cd，则acbd。 (4) 因为bc，又因为aa，故由(3)式可得 abac，abac。 这个性质称为格的保序性。,9.1.1 偏序集定义的格,第9章 格与布尔代数,定理9-4 设为格，那么对L中任何元素a,b和c， 有如下算律成立。 (1) 幂等律 aa=a，aa=a (2) 交换律 ab=ba，ab=ba
7、 (3) 结合律 (ab)c=a(bc)， (ab)c=a(bc) (4) 吸收律 a(ab)=a，a(ab)=a,9.1.1 偏序集定义的格,第9章 格与布尔代数,证明 (1) 因为aa，故有aaa。又因为 aaa， 因此由的反对称性得aa=a。 同理可证aa=a。 (2) 在格中，由于任意两元素a和b的最小上 界与b和a的最小上界是相同的，因此 ab=ba。同样，由于任意两元素a 和b的最大下界与b和a的最大下界也是 相同的，因此ab=ba。,9.1.1 偏序集定义的格,第9章 格与布尔代数,证明(3) 因为 aab(ab)c bab(ab)c 又因为 c(ab)c 于是 bc(ab)c
8、从而有 a(bc)(ab)c 同理 (ab)ca(bc) 由的反对称性得 (ab)c=a(bc) 同理可证(ab)c=a(bc)。,9.1.1 偏序集定义的格,第9章 格与布尔代数,证明(4) 因为aa，aba，所以 a(ab)a 显然aa(ab)， 于是由的反对称性得： a(ab)=a 同理可证a(ab)=a。,9.1.1 偏序集定义的格,第9章 格与布尔代数,定理9-5 设为格，则对L中任何元素a和b，有 abab=aab=b 证明 若ab，则由aa和ab可得aab。 又aba，从而ab=a。 若ab=a， 则由吸收律得ab=(ab)b=b。 若ab=b，则aab=b。 至此可得abab=
9、aab=b。,9.1.1 偏序集定义的格,第9章 格与布尔代数,定理9-6 设为格，则对L中任何元素a,b和c， 有 (1) a(bc)(ab)(ac) (2) a(bc)(ab)(ac) 其中关系是关系的对偶关系。 证明 (1) 因为 aab，aac， 所以 a(ab)(ac) 又因为 bcbab， bccac，,9.1.1 偏序集定义的格,第9章 格与布尔代数,因此有 bc(ab)(ac) 故 a(bc)(ab)(ac)。 证明(2) 由格的对偶原理 可直接由(1)式得出 a(bc)(ab)(ac)。,9.1.1 偏序集定义的格,第9章 格与布尔代数,定理9-7 设为格，那么对L中任何元素
10、a,b和 c，有 aca(bc)(ab)c 证明 必要性。若ac，ac=c，于是由定理9-6得 a(bc)(ab)(ac)=(ab)c 充分性。若a(bc)(ab)c， 则显然有 aa(bc)(ab)cc 即有 ac。 这一不等式称为格的模不等式。,9.1.2 代数系统定义的格,第9章 格与布尔代数,定义9-3 设是代数系统，其中和是L 中上的两个二元运算，如果这两个运算对L 中的元素满足： (1) 交换律 ab=ba，ab=ba (2) 结合律 (ab)c=a(bc)， (ab)c=a(bc) (3) 吸收律 a(ab)=a，a(ab)=a 则称代数系统是格。 也称这样定义的格为代数格。,9
11、.1.2 代数系统定义的格,第9章 格与布尔代数,定理9-8 由代数系统定义的格和由偏序集定义的格 是等价的。亦即，一个代数格必是一个偏 序格；一个偏序格必是一个代数格。 证明 (1) 设是一个格，在集合L上定义二 元关系如下： 对任意a,bL， abab=a 首先证明是一个偏序关系。即要证明 满足自反性、反对称性和传递性。,9.1.2 代数系统定义的格,第9章 格与布尔代数,对L的任意元素a，因aa=a，故aa。 自反性得证。 对L的任意元素a和b，若ab，ba， 则有a=ab，ba=b，而ab=ba， 故a=b。对称性得证。 对L的任意元素a,b和c，若ab，bc， 则有a=ab，bc=b
12、，于是 ac=(ab)c=a(bc)= ab=a 故ac。传递性得证。,9.1.2 代数系统定义的格,第9章 格与布尔代数,其次证明对于L的任意两元素a和b，a和b的最大下界和最小上界存在。 由吸收律a(ab)=a，b(ab)=b，知 aab，bab 因而ab为a,b的上界。 设c为a,b的任一个上界，即ac，bc，那么有ac=c，bc=c，于是 (ab)c=a(bc)=ac=c 故有abc。这表明ab是a,b的最小上界。 同理可证ab是a,b的最大下界。,9.1.2 代数系统定义的格,第9章 格与布尔代数,证明(2) 若是格，则对L的任意两元素a和b， 记a,b的最大下界为ab，最小上界为
13、ab。 首先证明是一个代数系统。 由偏序集的性质可知，a,b的最小上界和 最大下界是唯一的，所以，如上定义的和 是L上的两个二元运算，因此是 一个代数系统。 其次证明二元运算和满足交换律、结合 律和吸收律。,9.1.2 代数系统定义的格,第9章 格与布尔代数,下面给出吸收律的证明， 因为a(ab)是a和ab的最小上界，所以aa(ab)。而由于aa，aba，所以，a是a和ab的上界，因此a(ab)a，故a(ab)=a。 又因为a(ab)是a和ab的最大下界，所以a(ab)a。而由于aa，aab，所以，a是a和ab的下界，因此aa(ab)，故a(ab)=a。吸收律得证。 今后，若提到格则即可以理解
14、为偏序格也可以理解为代数格。,9.1.2 代数系统定义的格,第9章 格与布尔代数,【例9-6】对任意集合S，(S)是S的幂集，集合的 并集（）和交集（）是(S)上的两 个二元运算，满足交换律、结合律和吸 收律，因此是格。它与前 面曾提到的格是一致的，且对 于任意的A,BS，有 ABAB=AAB=B,9.1.3 子格与格的同态,第9章 格与布尔代数,定义9-4 设是格，S是L的非空子集，若对S 中的任意元素a和b，有 (1) abS (2) abS 则称是的子格。 子格必是格。因为当运算限制在S上时，交换律、结合律和吸收律也是成立的。,9.1.3 子格与格的同态,第9章 格与布尔代数,【例9-7】在整数集合I中定义两个二元运算和 为：对任意a,bI， ab=maxa,b，ab=mina,b 容易看出，这两个二元运算和适合交换 律、结合律和吸收律，因此是格。又设I+ 是所有正整数的集合，显然I+I，且对于任意 a,bI+，有 ab=maxa,bI+，ab=mina,bI+ 因此，是的子格。,9.1.3 子格与格的同态,第9章 格与布尔代数,子格的另一种定义: 定义9-5 设是格，S是L的子集，若对S中的 任意元素a和b，a,b在L中求得的最小 上界a
