离散数学格与布尔代数.ppt

《离散数学格与布尔代数.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11章格与布尔代数离散数学中国地质大学本科生课程本章内容11.1格的定义与性质11.2分配格、有补格与布尔代数本章总结作业11.1格的定义与性质定义11.1设是偏序集，如果x,y∈S，{x,y}都有最小上界和最大下界，则称S关于偏序≤作成一个格(lattice)。说明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧。x∨y：表示x与y的最小上界x∧y：表示x和y的最大下界。本章出现的∨和∧符号只代表格中的运算，而不再有其它的含义。格的实例例1

2、1.1设n是正整数，Sn是n的正因子的集合。D为整除关系，则偏序集构成格。x,y∈Sn，x∨y是lcm(x,y)，即x与y的最小公倍数。x∧y是gcd(x,y)，即x与y的最大公约数。下图给出了格，和。例11.2例11.2判断下列偏序集是否构成格,并说明理由。(1)，其中P(B)是集合B的幂集。(2)，其中Z是整数集,≤为小于或等于关系。(3)偏序集的哈斯图分别在下图给出。例11.2解答(1)是格。x,y∈P(B)，x∨y就是

3、x∪y，x∧y就是x∩y。由于∪和∩运算在P(B)上是封闭的，所以x∪y，x∩y∈P(B)。称,为B的幂集格。(2)是格。x,y∈Z,x∨y＝max(x,y)，x∧y＝min(x,y)，它们都是整数。(3)都不是格。(a)中的{a,b}没有最大下界。(b)中的{b,d}有两个上界c和e,但没有最小上界。(c)中的{b,c}有三个上界d,e,f,但没有最小上界。(d)中的{a,g}没有最大下界。例11.3例11.3设G是群，L(G)是G的所有子群的集合。即L(G)＝{H

4、H≤G}对任意的H

5、1,H2∈L(G)，H1∩H2也是G的子群，而是由H1∪H2生成的子群（即包含着H1∪H2的最小的子群）。在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格。易见在L(G)中，H1∧H2就是H1∩H2，H1∨H2就是。对偶原理定义11.2设f是含有格中元素以及符号＝、≤、≥、∨和∧的命题。令f*是将f中的≤替换成≥，≥替换成≤，∨替换成∧，∧替换成∨所得到的命题。称f*为f的对偶命题。例如在格中令f是(a∨b)∧c≤c，则f*是(a∧b)∨c≥c。格的

6、对偶原理设f是含有格中元素以及符号＝、≤、≥、∨和∧的命题。若f对一切格为真，则f的对偶命题f*也对一切格为真。例如对一切格L都有a,b∈L，a∧b≤a(因为a和b的交是a的一个下界)那么对一切格L都有a,b∈L，a∨b≥a说明许多格的性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，只须证明其中的一个命题即可。格的运算性质定理11.1设是格，则运算∨和∧适合交换律、结合律、幂等律和吸收律，即(1)交换律a,b∈L有a∨b＝b∨aa∧b＝b∧a(2)结合律a,b,c∈L有(a

7、∨b)∨c＝a∨(b∨c)(a∧b)∧c＝a∧(b∧c)(3)幂等律a∈L有a∨a＝aa∧a＝a(4)吸收律a,b∈L有a∨(a∧b)＝aa∧(a∨b)＝a定理11.1(1)a∨b和b∨a分别是{a,b}和{b,a}的最小上界。由于{a,b}＝{b,a}，所以a∨b＝b∨a。由对偶原理，a∧b＝b∧a得证。(2)由最小上界的定义有(a∨b)∨c≥a∨b≥a(13.1)(a∨b)∨c≥a∨b≥b(13.2)(a∨b)∨c≥c(13.3)由式13.2和13.3有(a∨b)∨c

8、≥b∨c(13.4)再由式13.1和13.4有(a∨b)∨c≥a∨(b∨c)同理可证(a∨b)∨c≤a∨(b∨c)根据偏序关系的反对称性有(a∨b)∨c＝a∨(b∨c)由对偶原理，(a∧b)∧c＝a∧(b∧c)得证。定理11.1(3)显然a≤a∨a,又由a≤a可得a∨a≤a。根据反对称性有a∨a＝a，由对偶原理，a∧a＝a得证。(4)显然a∨(a∧b)≥a(13.5)又由a≤a，a∧b≤a可得a∨(a∧b)≤a(13.6)由式13.5和13.6可得a∨(a∧b)＝a，根据对偶原理，a∧(a∨b)＝a得证

9、。定理11.2定理11.2设是具有两个二元运算的代数系统，若对于*和运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序≤，使得构成一个格，且a,b∈S有a∧b＝a*b，a∨b＝ab。思路(1)证明在S中*和运算都适合幂等律。(2)在S上定义二元关系R，并证明R为偏序关系。(3)证明构成格。说明通过规定运算及其基本性质可以给出格的定义。定理11.2a∈S，由吸收律得(1)证明在S中