第十七章格与布尔代数 81偏序与格
第十七章 格与布尔代数 §1 偏序与格
一、格的一般概念 偏序集(P;是由一个非空的集合P及在 P上定义的偏序关系≤构成 在偏序集(P;s)中,若对任意ab∈P有asb 或b≤a时称P为全序。 冷定义171:设(L;为偏序集,如果对任意 的a,b∈L有最小上界与最大下界时称L为 橙。以ab=ub(a,b)表示ab的最小上 界,aAb=gb(a,b)表示a,b的最大下界
❖ 一、格的一般概念 ❖ 偏序集(P;≤)是由一个非空的集合P 及在 P上定义的偏序关系≤构成 ❖ 在偏序集(P;≤)中，若对任意a,bP有a≤b 或b≤a 时称P为全序。 ❖ 定义17.1:设(L;≤)为偏序集, 如果对任意 的a,bL有最小上界与最大下界时,称L为 格。以ab=lub(a,b)表示a,b的最小上 界,ab=glb(a,b)表示a,b的最大下界
冷定义172:(L;)为格如果a≤ba≠b(记为 a<b),且不存在u∈L{a,b}使asu≤b,则称b 盖a c(=d.ab的如果的 当a<b时,如有c1,ck∈L(k≥1)使c覆 k-1),且有a=c<c2<.<ck= 则称c1 何两个元素a<b,总有连接它们的链,则称 L是离散的。有限的离散全序集的哈斯图 由一条链组成
❖ 定义17.2:(L;≤)为格,如果a≤b,ab(记为 a<b),且不存在uL-{a,b}使a≤u≤b,则称b 覆盖a。 ❖ 当a<b时,如有c1 ,,ckL(k1),使ci+1覆 盖ci (i=1,2,,k-1),且有a=c1<c2<<ck=b, 则称c1 ,,ck为连接a,b的链。如果L的任 何两个元素a<b,总有连接它们的链, 则称 L是离散的。有限的离散全序集的哈斯图 由一条链组成
冷例:设G是一个群,L(G表示G的所有子群 构成的集合则L(G关于集合包含关系g 构成一个偏序集, 并且是格 称为G的子群格 冷例:设G是一个群,P(G表示G的所有正规 子群构成的集合,则P(G关于集合包含关 系c构成一个偏序集 并且是格 称为G的不变子群格
❖ 例:设G是一个群,L(G)表示G的所有子群 构成的集合,则L(G)关于集合包含关系 构成一个偏序集, 并且是格. 称为G的子群格 ❖ 例:设G是一个群,P(G)表示G的所有正规 子群构成的集合,则P(G)关于集合包含关 系构成一个偏序集 并且是格. 称为G的不变子群格
冷例:设B={0,4},≤为定义在B上的关系,对 任(a12,a(b1,bn)∈B,(a1,an)≤ (b12…b)当且仅当a≤b(1sn),显然这是 个偏序关系。并且(B,≤)是格
❖ 例:设B={0,1},≤n为定义在Bn上的关系, 对 任(a1 ,,an ),(b1 ,,bn )Bn , (a1 ,,an )≤n (b1 ,,bn )当且仅当ai≤nbi (1in),显然这是 一个偏序关系。并且(Bn ,≤n )是格
冷格的定义是设(L;为偏序集,如果对任意的 ab∈L有最小上界与最大下界时,称L为格。 冷定义173L;为偏序集,当任AcL有最大 下界,最小上界时,L显然是格称为完全格。 L自身的最小上界是整个格L的最大元,记 为1;L自身的最大下界为整个格L的最小 元,记为0。于是任x∈L,x≤1,0≤。 冷注意:此处的子集A可以是有限的,也可 以是无限的。 冷例如前面的子群格L(G)是完全格
❖ 格的定义是:设(L;≤)为偏序集, 如果对任意的 a,bL有最小上界与最大下界时,称L为格。 ❖ 定义17.3(L;≤)为偏序集, 当任AL有最大 下界,最小上界时,L显然是格,称为完全格。 L自身的最小上界是整个格L的最大元,记 为1;L自身的最大下界为整个格L的最小 元,记为0。于是任xL,x≤1,0≤x。 ❖ 注意: 此处的子集A可以是有限的, 也可 以是无限的。 ❖ 例如前面的子群格L(G)是完全格
冷例:取S={ab,cP(S);g)是一个格,其最 大元是S={ab,c,最小元是②。任取一个 子集合有最大下界和最小上界,如 {t2{a,c}2{c}的最大下界是②,最小上界 是{a,c};它是一个完全格。 要说明的是并不是所有的格都是完全格
❖ 例:取S={a,b,c},(P(S);)是一个格,其最 大元是S={a,b,c},最小元是。任取一个 子集合有最大下界和最小上界, 如 {{a},{a,c},{c}}的最大下界是,最小上界 是{a,c};它是一个完全格。 ❖ 要说明的是并不是所有的格都是完全格
二、作为代数系统的格 冷(L;为偏序集,如果对任意的a,b∈L有最 小上界与最大下界时,称L为格。以 ab=lub(a,b)表示a2b的最小上 界,aAb=glb(a,b)表示a,b的最大下界。而 最小上界和最大下界都是L中的元素。 在格(;中,对任意两个元素a,b∈L,可 唯一确定ab和ab,且它们都属于L, 和入看作为集合L上的2个二元运算
❖ 二、作为代数系统的格 ❖ (L;≤)为偏序集, 如果对任意的a,bL有最 小上界与最大下界时 ,称 L 为 格 。 以 ab=lub(a,b) 表 示 a,b 的最小上 界,ab=glb(a,b)表示a,b的最大下界。而 最小上界和最大下界都是L中的元素。 ❖ 在格(L;≤)中，对任意两个元素a,bL,可 唯一确定ab和ab,且它们都属于L， 和看作为集合L上的2个二元运算
冷定理171:(L;s为格则对任意a,b∈L有: 冷(1)a≤avb,b≤avb, aabsa aabb; 冷(2)a≤b当且仅当avb=b 冷(3a≤b当且仅当a∧b=a
❖ 定理17.1:(L;≤)为格,则对任意a,bL有: ❖ (1)a≤ab,b≤ab,ab≤a ab≤b; ❖ (2)a≤b当且仅当ab=b; ❖ (3)a≤b当且仅当ab=a
非空集合L上和∧这两个二元运算所具 有性质,[LV,为一个代数系统。 冷定理172L;为格任a,bc∈L有: 冷L幂等律ava=a,aAa=a; 冷L2交换律avb=bva,a∧b=bAa; 冷L3结合律av(bvc=(avb)yc, a∧(bAc)=(a∧b)入C; 冷L4吸收律:avab)=a,a∧(avb=a
❖ 非空集合L上和这两个二元运算所具 有性质，[L;,]为一个代数系统。 ❖ 定理17.2:(L;≤)为格,任a,b,cL有: ❖ L1幂等律:aa=a,aa=a; ❖ L2交换律:ab=ba,ab=ba; ❖ L3结合律:a(bc)=(ab)c, ❖ a(bc)=(ab)c; ❖ L4吸收律:a(ab)=a, a(ab)=a