哈尔滨理工大学呻斛生課程 离影数 第13章格与布尔代数 O计算机系
第13章 格与布尔代数 离 散 数 学 哈尔滨理工大学本科生课程 计算机系
本章内空 13.1格的定义与性质 13.2子格与格同态 13.3分配格与有补格 13.4布尔代数 本章总结 作业
本章内容 13.1 格的定义与性质 13.2 子格与格同态 13.3 分配格与有补格 13.4 布尔代数 本章总结 作业
13,1格的定义与性质 定义13.1设是偏序集,如果∨x,y∈s,tx,y都有最小 上界和最大下界,则称S关于偏序≤作成一个格(atte) 说明:由于最小上界和最大下界的唯一性,可以把求{x,y的最 小上界和最大下界看成x与y的二元运算∨和∧ xVy:表示x与y的最小上界 x∧y:表示x和y的最大下界 本章出现的∨和∧符号只代表格中的运算,而不再有其它的 含义
13.1 格的定义与性质 定义13.1 设是偏序集，如果x,y∈S，{x,y}都有最小 上界和最大下界，则称S关于偏序≤作成一个格(lattice)。 说明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最 小上界和最大下界看成x与y的二元运算∨和∧。 x∨y：表示x与y的最小上界 x∧y：表示x和y的最大下界。 本章出现的∨和∧符号只代表格中的运算，而不再有其它的 含义
格的奥例 例13.1设n是正整数,S是n的正因子的集合。D为整除关系, 则偏序集和。 30 8 6 10 15 3 2 Se,D>
格的实例 例13.1 设n是正整数，Sn是n的正因子的集合。D为整除关系， 则偏序集构成格。x,y∈Sn， x∨y是lcm(x,y)，即x与y的最小公倍数。 x∧y是gcd(x,y)，即x与y的最大公约数。 下图给出了格，和
例13,2 例13.2判断下列偏序集是否构成格,并说明理由。 (1)P(B),>,其中P(B)是集合B的幂集 (2),其中Z是整数集,≤为小于或等于关系。 (3)偏序集的哈斯图分别在下图给出
例13.2 例13.2 判断下列偏序集是否构成格,并说明理由。 (1) ，其中P(B)是集合B的幂集。 (2) ，其中Z是整数集,≤为小于或等于关系。 (3) 偏序集的哈斯图分别在下图给出
例13,2 解答(1)是格。 x,y∈P(B),x∨y就是xUy,x∧y就是x∩y。 由于U和∩运算在P(B)上是封闭的,所以xUy,x∩y∈P(B)。 称P(B),c>,为B的幂集格。 (2)是格。 Vx,y∈Z,xVy=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}没有最大下界
例13.2 解答 (1)是格。 x,y∈P(B)，x∨y就是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}没有最大下界
13,3 例13.3设G是群,L(G是G的所有子群的集合。即 L(G)={HH≤G 对任意的H1,H2∈L(G),H1∩H2也是G的子群,而是由 H1UH2生成的子群(即包含着HUH2的最小的子群)。 在L(G)上定义包含关系c,则L(G关于包含关系构成一个格, 称为G的子群格。 易见在L(G)中,H1∧H2就是H1∩H2,H1VH2就是
例13.3 例13.3 设G是群，L(G)是G的所有子群的集合。即 L(G)＝{ H|H≤G } 对任意的H1 ,H2∈L(G)，H1∩H2也是G的子群，而是由 H1∪H2生成的子群（即包含着H1∪H2的最小的子群）。 在L(G)上定义包含关系，则L(G)关于包含关系构成一个格， 称为G的子群格。 易见在L(G)中，H1∧H2就是H1∩H2，H1∨H2就是
对偶原理 定义13.2设f是含有格中元素以及符号=、≤、≥、V和∧的 命题。令是将f中的≤替换成≥,≥替换成≤,V替换成 ∧,∧替换成∨所得到的命题。称f为f的对偶命题。 例如在格中令f是(aVb)∧c≤c,则f是(a∧b)∨c≥c。 格的对偶原理设f是含有格中元素以及符号 ≥、∨和 ∧的命题。若f对一切格为真,则f的对偶命题也对一切格 为真。 例如对一切格L都有 va,b∈L,a∧b≤a (因为a和b的交是a的一个下界) 那么对一切格L都有Va,b∈L,ab≥a 说明许多格的性质都是互为对偶命题的。 有了格的对偶原理,在证明格的性质时, 只须证明其中的一个命题即可
对偶原理 定义13.2 设f是含有格中元素以及符号＝、≤、≥、∨和∧的 命题。令f *是将f中的≤替换成≥，≥替换成≤，∨替换成 ∧，∧替换成∨所得到的命题。称f *为f的对偶命题。 例如 在格中令f是(a∨b)∧c≤c，则f *是(a∧b)∨c≥c。 格的对偶原理 设f是含有格中元素以及符号＝、≤、≥、∨和 ∧的命题。若f对一切格为真，则f的对偶命题f *也对一切格 为真。 例如 对一切格L都有 a,b∈L，a∧b≤a (因为a和b的交是a的一个下界) 那么对一切格L都有 a,b∈L，a∨b≥a 说明 许多格的性质都是互为对偶命题的。 有了格的对偶原理，在证明格的性质时， 只须证明其中的一个命题即可
格的运算性质 定理13.1设是格,则运算∨和∧适合交换律、结合 律、幂等律和吸收律,即 (1)交换律∨a,b∈L有 a b=bVa a∧b=b∧a (2)结合律Va,b,c∈L有 (a∨b)∨c=a∨(b∨o)(a∧b)∧c=a∧(b∧c) (3)幂等律∨a∈L有 a=a ala=a (4)吸收律∨a,b∈L有 aV(a∧b)=a a∧(a∨b)=a
格的运算性质 定理13.1 设是格，则运算∨和∧适合交换律、结合 律、幂等律和吸收律，即 (1)交换律 a,b∈L 有 a∨b＝b∨a a∧b＝b∧a (2)结合律 a,b,c∈L 有 (a∨b)∨c＝a∨(b∨c) (a∧b)∧c＝a∧(b∧c) (3)幂等律 a∈L 有 a∨a＝a a∧a＝a (4)吸收律 a,b∈L 有 a∨(a∧b)＝a a∧(a∨b)＝a
定理13,1 (1)aVb和b∨a分别是{a,b}和{b,a}的最小上界。 由于{a,b}={b,a},所以a∨b=b∨a 由对偶原理,a∧b=b∧a得证。 (2)由最小上界的定义有 (a∨b)∨c≥aVb≥a (13.1) (aVb)∨c≥a∨b≥b (13.2) (a∨b)∨c≥c (13.3) 由式13.2和13.3有 (a∨b)Vc≥bVc(13.4) 再由式13.1和13.4有 (aVb)∨c≥aV(bVc) 同理可证 (aVb)Vc≤a∨(b∨c) 根据偏序关系的反对称性有(aVb)Vc=a(b∨c) 由对偶原理,(a∧b)∧c=a∧(b∧c)得证
定理13.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≥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)得证