格与布尔代数

图 7.2―6
图 7.2―7
7.3 特殊的格
7.3.1 分配格
任何格的元素都能满足分配不等式,但某些特殊格, 其所有元素都能满足分配律。
序关系≤可定义为细分,πi≤πj当且仅当πi中的每一块都在
πj的某一块中。
+分别是保交和
保联。所以〈π(S),≤〉是格。
例如S=｛a,b,c｝,则 π(S)=｛π1,π2,π3,π4,π5｝ π1=｛｛a,b,c｝｝,π2=｛｛a,b｝,｛c｝｝, π3=｛｛a,c｝,｛b｝｝, π4=｛｛a｝,｛b,c｝｝ π5=｛｛a｝,｛b｝,｛c｝｝ 〈π(S),≤〉的哈斯图如图7.1―1(d)所示。 (e)图7.1―1(e)所示的哈斯图也是一个格。
(9) 吸收律的证明。
由公式(1′)有a≥a,由公式(4)有a≥a*b,因此,根据公式
(5′)得a≥a (a*b),但由公式(4′)有a (a*b)≥a,这样,根据 公式(2′)得a Fra biblioteka*b)=a。
(10)a≤b a*b=a a b=b的证明。
先证a≤b a*b=a,由公式1知a≤a,由假设a≤b,所以,由
由对偶原理得a*b=b*a。(下边都仅证两对偶恒等式 中的一个。)
(7) 结合律的证明。
设R=a (b c)和R′=(a b) c,由公式(4′)(加撇表示 右侧的公式,下同)得R≥a,R≥b c,根据公式(4′)和(3′)得 R≥b和R≥c。这样,根据公式(5′)得R≥a b;由R≥a b和R≥c 得R≥(a b) c=R′。类似地可证R′≥a (b c)=R。因此, 根据公式(2′)
(12) 保序性的证明。
公式(11)中d取为a即得。
(13)分配不等式的证明。

二、有界格和有补格
有补格定义: 如果在一个有界格中，每个元素都至少有一个补元,则称这个格为有补格. 上图中(2)和(3)是有补格,而(1)不是有补格.
定理7 在有界格<L,∧,∨,0,1>中, 0 和 1互为补元, 且是唯一的.
证明: ∵0∧1=0，0∨1=1，∴0、1互为补元。设c也是0的补元， ∵0∨c =1， ∴必有c=1，故0的补元唯一。 同理可证1的补元也唯一。 定理8 在分配格中，如果元素a∈L有一个补元a' ，则此补元a'是唯一的. 证明: 设 b,c都是a的补元, 则a∧b=0=a∧c, a∨b=1=a∨c,分配格 满足消去律,可知b=c. 消去律: (即对于任意a,b,c∈L有(a∧b=a∧c)∧ (a∨b=a∨c)⇒b=c)
一、分配格
定理4 设<L,*,⊕>是一个分配格，那么对于任意a,b,c∈L,若有a*b= a*c和a⊕b=a⊕c，则必有b=c。 证明: c = (a*c)⊕c = (a*b)⊕c = (a⊕c) *(b⊕c) = (a⊕b)*(b⊕c) = ((a⊕b)*b)⊕((a⊕b) * c) = b⊕((a*c) ⊕(b*c))
二、有界格和有补格
例2 (1) S={a,b,c}, 偏序格是 <ρ(S), ⊆>， 全上界 S ∀A∈ρ(S),有A⊆S 全下界 Ø ∀A∈ρ(S), 有Ø⊆A (2) X={A|A是由变元p1,p2,…,pn, ﹁,∧,∨,→, 构成的合式公 式集}。< X, ∧,∨ >诱导的偏序格是 <X, >. 全上界 T ∀P∈X,有PT 全下界 F ∀P∈X, 有FP.
三、布尔格(布尔代数)
布尔格的定义 如果格<L,∧,∨,0,1>,既是有补格,又是分配格,则称此格为布尔格(或有 补分配格),也叫做布尔代数. 例3 设S是非空有限集合, <ρ(S),∩,∪>为代数格 ∀A,B∈ρ(S)，A≤BA∩B=AA⊆B 由<ρ(S),∩,∪>诱导的偏序格是<ρ(S),⊆>. 说明<ρ(S),⊆>是布尔格. 证明 (1)<ρ(S),⊆>是格; (2)<ρ(S),⊆>是有界格, 因为

❖ 因为同构,故有(ab)=(b) ❖ 且ab=b, ❖ 因此由≤定义得a≤b
❖ (2) 是格L到格S的一一对应, 且对任何 a,bL,a≤b当且仅当(a)≤(b)
❖ 主要证明是同态映射,即
❖ (ab)=(a)(b), (ab)=(a)(b) ❖ 分别证明(ab)≤(a)(b)
❖ (a)(b)≤(ab)
❖ 由(B;≤)定义了,运算，而a的补元a'也 是B中的元素，且分配格补元唯一
❖ '看作为B上的一元运算。
❖ [B;,,']为代数系统，又称为布尔代数。
❖ 布尔代数[B;,,']是有补分配格,具有性
质L1~L4,
❖ 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。 ❖ 分配格,满足分配等式D1~D2,
❖ D1:a(bc)=(ab)(ac);(ab)(ac)=a(b c)
❖ D2:(ab)(ac)(bc)=(ab)(ac)(bc)
❖ 有补格:一定是有界格,每个元素有补元, 满足B1、B2和C1~C3,
❖ 例:如下图所示的格分配等式不成立.
❖ 例：S,[P(S);∪,∩]满足分配等式。 ❖ 分配格 ❖ 定 义 16.9 : [ L;,] 为 格 , 当 对 其 任 意 元
a,b,cL成立分配律,即
❖ (1)a(bc)=(ab)(ac); ❖ (2)(ab)(ac)=a(bc)。 ❖ 则称该格为分配格。
❖ 例:S={1,2,3,4,5},其偏序关系由下图所示, 则S是有界格,且为有补格.
❖ 由此可知补元不唯一.

证明思路： 因为a和b的并是a的一个上界，所以 a ≤ a∨b 同理 b ≤ a∨b 由对偶原理，即得 a∧b ≤ a a∧b ≤ b
定理6-1.2 在一个格<A, ≤>中，对于任意元素a,b,c,dA, 如果 则 a≤b 和 c≤d a∨c ≤ b∨d a∧c ≤ b∧d
证明 因为b ≤ b∨d，d ≤ b∨d，所以，由传递性可得 a ≤ b∨d和 c ≤ b∨d 这就表明b∨d是a和c的一个上界，而a∨c是a和c的最小上界， 所以，必有a∨c ≤ b∨d 类似地可以证明 a∧c ≤ b∧d
例3 给定S={a，b}，(S)={,{a},{b},{a,b}}，那么，格
<(S)，>如图6-1.3所示。
二、由格<A, ≤>所诱导的代数系统
定义6-1.2 设<A, ≤>是一个格,如果在上定义两个二元运 算∨和∧ ,使得对于任意的a,b A ， a∨b等于 a和b的最小 上界, a∧b等于a和b的最大下界,那么,就称<A,∨,∧>为由格 <A, ≤>所诱导的代数系统。二元运算∨和∧分别称为并运算和 交运算。 通常用a∨b 表示{a,b}的上确界,用a∧b 表示{a，b}的下 确界,∨和∧分别称为保联(join)和保交(meet)运算。由于对任 何a，b，因为在格中，a∨b及a∧b都是A 中确定的成员，因 此 ∨,∧均为A上的运算。 设S={a,b} ， (S) ={, {a},{b},{a,b}}由格<(S), > 诱导的代数系统为<(S),∨,∧> 。其中∨为集合的并运算和 ∧为集合的交运算。如表6-1.1所示。
定理6-1.4 设<A,∨,∧>是一个代数系统,其中 ∨,∧都是二元运算且满足交换律、结合律和吸收律，