当前位置:
文档之家› 最新离散数学第十五章格与布尔代数简
最新离散数学第十五章格与布尔代数简
解: 在a)和c)中的哈斯图表示的偏序集是格。因为每个偏序
集中每对元素都有最小上界和最大下界。 b)所示的哈斯图的偏序集不是格,例如元素b和c没有最
小上界。只要注意到d,e,f中每一个都是上界,但这3个元素 的任何一个关于这个偏序集中的序都不小于其它两个。
格的对偶性原理是成立的:
令<L,≤>是偏序集,且<L,≥>是其对偶的偏序 集。若<L,≤>是格,则<L,≥>也是格,反之亦然。 这是因为,对于L中任意a和b,<L,≤>中LUB{a,b} 等同于<L,≥>中GLB {a,b},<L,≤>中GLB{a,b}等 同于<L,≥>中的LUB{a,b}。若L是有限集,这些性 质易从偏序集及其对偶的哈斯图得到验证。
(结合律)
④ a(ab)=a, a(ab)=a (吸收律)
定理15.1.3 设<L,≤>是格,对任意a,b,cL, 有
①若a≤b和c≤d,则ac≤bd,ac≤bd。 ②若a≤b,则ac≤bc,ac≤bc。 ③c≤a和c≤b c≤ab ④a≤c和b≤c ab≤c
定理15.1.4 设<L,≤>是格,对任意的a,b,cL, 有
注意:并非每个偏序集都是格。如, 设A={2,3,6,8}, “整除”关系R={‹2,2›, ‹2,6›, ‹2,8›, ‹3,3›, ‹3,6›, ‹6,6›, ‹8,8›}是A上的一 个偏序关系,则<A,R>是一个偏序集,但不 是格。因为23不存在,68也不存在。
例 确定下图中每个哈斯图表示的偏序集是 不是格。
(2)如果x∈X是Y的上界且对每一个Y的上 界x'均有x≤x',则称x是Y的最小上界(或上确界 LUB,least upper bound);如果x∈X是Y的下 界且对每一个Y的下界x'均有x'≤x,则称x是Y的最 大下界(或下确界GLB,greatest lower bound )
例:找出下图所示哈斯图的偏序集的子集 {a,b,c},{j,h}和{a,c,d f}的下界和上界。
a(bc)≤(ab)(ac) (ab)(ac)≤a(bc) 通常称上二式为格中分配不等式。
– 3.特殊的格
定义15.1.2 设<L,≤>是格,若L中有最大元和 最小元,则称<L,≤>为有界格。由于最大元存在必 唯一,故一般把格中最大元记为1,最小元记为0。
由定义可知,对任意aL,有 ① 0≤a≤1 ② a0=0, a0=a ③ a1=a, a1=1 由此可知,0是<L,≤>关于的零元,关于的 幺元;1是<L,≤>关于的幺元,关于的零元
15.1 格(lattice)
– 1.格作为偏序集
定义15.1.1 设<L,≤>是一个偏序集,若对任 意a,bL,存在 最大下界(GLB)和最小上界(LUB), 则称<L,≤>为格。
用 ab 表 示 GLB{a,b} , ab 表 示 LUB{a,b} , 并称和分别为L上的交(或积)和并(或和) 运算。这样我们由偏序关系定义了两种二元运算。
例 设n为正整数,Sn为n的正因子的集合, ≤为整除关系,则<Sn,≤>构成格。
因为x,y∈Sn, xy就是x,y的最小公 倍数,xy是x,y的最大公约数。
例 幂集P(A)上的包含关系定义了一个 偏序关系,P(A)中任意两个元素x,y,有
xy =x∪y xy =x∩y 因此,<P(A), >是一个格。
若L是有限集合,称<L,≤>为有限格。
显然,对于ab,有: ①ab≤a和ab≤b,则表明ab是a和b的下界。 ②若c≤a和c≤b,则c≤ab,这表明ab是a和b 的最大下界。
对于ab,有: ①a≤ab和b≤ab,则表明ab是a和b的上界。 ②若a≤c,且b≤c,则ab≤c,这表明ab是a 和b的最小上界。
离散数学第十五章格与布 尔代数简
在介绍格之前,对于我们在前面学过的偏序, 我们要补充两个内容:
1. 哈斯图 2. 最小上界与最大下界
2.最小上界与最大下界
定义 设集合X上有一个偏序关系“≤”且设Y 是X的一个子集。
(1)如果存在一个元素x∈X,对每个y'∈Y 都有y'≤x,则称x是Y的上界(upper bound);如果 均有x≤y',则称x是Y的下界(lower bound)。
ab=0,ab=1 称b为a的补元,记为a'。 由定义可知,若b是a的补元,则a也是b的补 元,即a与b互为补元。 显然,0'=1和1'=0。 一般说来,一个元素可以有其补元,未必唯 一,也可能无补元。
– 2.格的基本性质
定理15.1.1 设<L,≤>是格,对任意a,bL,有 ① ab=ba≤b ② ab=aa≤b ③ ab=aab=b
亦即 a≤bab=bab=a
定理15.1.2 设<L,≤>是格,对任意a,bL,有
① aa=a, bb=b
(等幂律)
பைடு நூலகம்
② ab=ba, ab=ba
(交换律)
③ a(bc)=(ab)c, a(bc)=(ab)c
定理15.1.5 设<L,≤>是有限格,其中 L={a1,a2,···,an},则<L,≤>是有界格。
定义15.1.3 设<L,≤>是格,对任意的a,b,cL, 有
① a(bc)=(ab)(ac) ② a(bc)=(ab)(ac) 则称<L,≤>为分配格,称①和②为格中分配 律。
定义15.1.4 设<L,≤>是有界格,对于aL,存 在bL,使得
从上讨论中,可知两格互为对偶。互为对偶 的两个<L,≤>和<L,≥>有着密切关系,即格<L,≤> 中交运算正是格<L,≥>中的并运算,而格 <L,≤>中的并运算正是格<L,≥>中的交运算。 因此,给出关于格一般性质的任何有效命题,把 关系≤换成≥(或者≥换成≤),交换成并,并换成 交,可得到另一个有效命题,这就是关于格的对 偶性原理。
解: {a,b,c}的上界是e,f,j,h,它唯 一的下界是a。 {j,h}没有上界,它的下界是 a,b,c,d,e,f。 {a,c,d f}的上界是f,h,j,它的 下界是a。
例 在上图所示偏序集中,如果{b,d,g}的最 大下界和最小上界存在,求出这个最大下界和最 小上界。
解: {b,d,g}的上界是g,h,故它的 最小上界是g。 {b,d,g}的下界是a,b,故它的 最大下界是b。