格与布尔代数

第九章格与布尔代数9.1格的定义及性质定义设(L,≼)是一个偏序集，若对于任意

{a,b}⊆L都有最小上界lub(a,b)和最大下界glb(a,b),则称(L,≼)是格,记lub(a,b)为a∨b,glb(a,b)为a∧b.例设S是集合，P(S)是S的幂集合，则偏序集(P(S),⊆)是格。

若A,B

⊆S,则lub(A,B)=A∪B,glb(A,B)=A∩B即A∨B=A∪B,A∧B=A∩B例设Z+是正整数集合，偏序“≼”定义为：a

≼

b⇔a|b(a整除b)。则(Z+,≼)是格。

设a,b∈Z+,则lub(a,b)=lcm(a,b),即a∨b=lcm(a,b),同理,glb(a,b)=gcd(a,b),即a∧b=gcd(a,b),其中,lcm(a,b)为a和b的最小公倍数;

gcd(a,b)为a和b的最大公约数。例试问图所示的偏序集中哪些是格。图全序集都是格。群G的全体子群S(G)对于偏序⊆构成格。G;H∩K群G的全体正规子群H(G)对于偏序⊆构成格。H,K的最小上界HK={hk|h∈H,k∈K},最大下界H∩K环R的全体理想I(R)对于偏序⊆构成格。I,J的最小上界I+J={i+j|i∈I,j∈J},最大下界I∩J线性空间V的全体子空间S(V)对于偏序⊆构成格。定理若(L,≼)是格，则其对偶偏序集(L,≽)也是格。例如，由于(P(S),⊆)是格，所以(P(S),⊇)也是格，并且在格(P(S),⊇)中，A∨B=A∩B,A∧B=A∪B。设(L,≼)是格，由于L的任意两个元素a和b均有唯一的最小上界和最大下界，因此“∨”和“∧”是格中的两个二元运算，所以格可以看作具有两个二元运算“∨”和“∧”的代数系统。

定理设(L,≼)是格，则1．(1)a∨a=a，(2)

a∧a=a幂等律2．(1)a∨b=b∨a，(2)

a∧b=b∧a交换律3．(1)(a∨b)∨c=a∨(b∨c),(2)

(a∧b)∧c=a∧(b∧c)结合律4．(1)

a∨(a∧b)=a，(2)

a∧(a∨b)=a吸收律由a∨(b∨c)是{a,(b∨c)}的最小上界知a≼a∨(b∨c),

b∨c≼a∨(b∨c)而b∨c是{b,c}的最小上界，故b≼b∨c,c≼b∨c,再由传递性知:b,c≼a∨(b∨c)。所以a∨(b∨c)是{a,b}的上界，而a∨b是{a,b}的最小上界，因此a∨b≼a∨(b∨c),故a∨(b∨c)是{a∨b,c}的上界，而(a∨b)∨c是{a∨b,c}的最小上界，于是(a∨b)∨c≼a∨(b∨c)；同理，a∨(b∨c)≼

(a∨b)∨c

故由反对称性知:

(a∨b)∨c=a∨(b∨c)定理设(L,∘,∗)是有两个运算的代数系统，并且运算“∘”和“∗”满足幂等律，交换律，结合律，吸收律，则可以在L上定义一个偏序关系“≼”使得(L,≼)是格，并对任意x,y∈

L,有x∘

y=x∨

y，x∗

y=x∧

y证.在L上定义关系“≼”如下：a

≼

b⇔a=a∗b

。首先说明“≼”是偏序关系

对任意a,b∈L，由于*是幂等的，因此a=a*a，于是a≼a，故≼是自反的。如果a≼b且b≼a，则a=a*b且b=b*a，由于*是交换的，因此a=a*b=b*a=b，故≼是反对称的。如果a≼b,b≼c,则a=a*b，b=b*c，由于*是结合的，因此a=a*b=a*(b*c)=(a*b)*c=a*c，即a≼c，故≼是传递的。

所以(L,≼)是偏序集。

然后说明(L,≼)是格。对任意a,b∈L，由(a*b)*a=a*(b*a)=a*(a*b)=(a*a)*b=a*b得a*b≼a由(a*b)*b=a*(b*b)=a*b得a*b≼b，所以a*b是{a,b}的下界；设c是{a,b}的下界，则c≼a,c≼b,即c=c*a,c=c*b,故c=c*c=(c*a)*(c*b)=(c*c)*(a*b)=c*(a*b),即c≼a*b所以a*b是{a,b}的最大下界,即a∧b=glb(a,b)=a*b类似地说明，a∨b=lub(a,b)=a∘b设a,b∈L,a≼b,则a=a∗b,由吸收律知a∘b=(a∗b)∘b=b反之，设a∘b=b，则a∗b=a∗(a∘b)=a,

所以a≼b。综合得：a≼b⇔

a∘b=b。由(a∘b)∘a=(a∘a)∘b=a∘b得a≼a∘b,由(a∘b)∘b=a∘(b∘b)=a∘b得b≼a∘b,所以a∘b是{a,b}的上界；设c是{a,b}的上界，则a≼c,b≼c,即a∘c=c,

b∘c=c故c=c∘c=(a∘c)∘(b∘c)=(a∘b)∘(c∘c)=(a∘b)∘c,即(a∘b)≼c所以a∘b是{a,b}的最小上界，即a∨b=

lub(a,b)=a∘b

定义设(L,∨,∧)是一个代数系统，二元运算“∨”和“∧”满足幂等律，交换律，结合律，吸收律，则称代