离散数学：有余格与分配格

本节主要介绍两种特殊的格。作为准备工作，先介绍格的几个重要运算性质。

定理1 设（L，≤）是一个格，a，b是L中任意元素，则下列诸条件等价：

a≤b⇔a×b=a⇔a⊕b=b

证明 若a≤b，因为a≤a，所以a是{a，b}的下界，而a×b是{a，b}的最大下界，故a≤a×b。因为a×b是{a，b}的下界，所以a×b≤a，故a×b=a。

若a×b=a，由吸收律知

(a⊕b)=(a×b)⊕b=b

若a⊕b=b，由a⊕b的定义知，b是{a，b}的最小上界，当然有a≤b。证毕。

定理2 设（L，≤）是一个格，a，b，c是L中任意元素。如果b≤c，则有

a×b≤a×c,a⊕b≤a⊕c

证明 因为b≤c，所以由定理1知b×c=b，又因为

(a×b)×(a×c)=(a×a)×(b×c)

=a×(b×c)

=(a×b)

再由定理1知，a×b≤a×c。

同理可证得第二个不等式。证毕。

定理3 设（L，≤）是一个格，a，b，c是L中任意元素，则如下分配不等式成立：

a⊕(b×c)≤(a⊕b)×(a⊕c)

a×(b⊕c)≥(a×b)⊕(a×c)

其中关系“≥”是关系“≤”的对偶关系。

证明 因为a≤a⊕b，a≤a⊕c，所以，由×的定义知

又因为

b×c≤b≤a⊕b

b×c≤c≤a⊕c

所以，再由×运算的定义知

由⊕的定义及（1），（2）式知

a⊕(b×c)≤(a⊕b)×(a⊕c)

利用对偶性可证得另一个不等式。证毕。

定理4 设（L，≤）是一个格，a，b，c是L中的任意元素，则有

a≤b⇔a⊕(b×c)≤b×(a⊕c)

证明 若a≤b，则由定理1知，a⊕b=b。由定理3知

a⊕(b×c)≤(a⊕b)×(a⊕c)=b×(a⊕c)

若a⊕（b×c）≤b×（a⊕c），则由⊕的定义知

a⊕(b×c)≥a

由×的定义知

b×(a⊕c)≤b

根据半序关系≤的传递性知a≤b。证毕。

定义1 设（L，≤）是格，如果L有最大元素（记为1）和最小元素（记为0），则称（L，≤）为有界格。

例1 参考本章第一节中例2、例3，设D是整除关系，则（S6，D），（S8，D），（S30，D）等是有界格，而（Z+，D）不是有界格。

容易证明：若（L，×，⊕，0，1）是有界格，则对任意a∈L，恒有

a⊕0=a,a×1=a

a⊕1=a,a×0=0

定义2 设（L，×，⊕，0，1）是有界格，a是L中的一个元素，如果L中存在元素b，使得

a×b=0,a⊕b=1

则b称为元素a的余元素（或称为补元素）。

在有界格（L，×，⊕，0，1）中任意元素a可以有余元素，也可以没有余元素；如果有余元素，也可以有一个或一个以上的余元素。

例2 下面哈斯图（图1）所表示的有界格，说明了余元素的几种情况。

定理5 在有界格（L，×，⊕，0，1）中，1是0的唯一一个余元素，反之亦然。

证明 因为

0×1=0,0⊕1=1

所以，0，1互为余元素。

若c∈L，且c≠1，c是0的余元素，则

0×c=0,0⊕c=1

但因0⊕c=c，所以有c=1，推出矛盾。证毕。

定义3 设（L，×，⊕，0，1）是一个有界格，如果L中的每一个元素都至少有一个余元素，则（L，×，⊕，0，1）称为有余格（或称为有补格）。

例3 设S是n个元素的集合，ρ（S）是S的幂集合，则（ρ（S），⊆）是有余分配格。和S是此格的界。对ρ（S）中任意元素A，ρ（S）中的元素S-A是A的余元素。

例4 设L={0，1}规定0≤1。于是不难看出（L，≤）是一个格。并且令（L，∧，∨）是与之等价的代数格，则∧，∨分别是集合L中两个元素的最大下界和最小上界运算。

令

Ln={(a1,a2,…,an)|ai∈L,i=1,2,…,n}

规定

(a1,…,an)≤n(b1,…,bn)⇔ai≤bi(i=1,2,…,n)(www.xing528.com)

于是，不难证明（Ln，≤n）是一个格，通常称为n维格。令与（Ln，≤n）等价的代数格为（Ln，×，⊕），对Ln中任意两个元素（a1，…，an），（b1，…，bn）显然有

(a1,…,an)×(b1,…,bn)=(a1∧b1,…,an∧bn)

(a1,…,an)⊕(b1,…,bn)=(a1∨b1,…,an∨bn)

n维格（Ln，≤n）是一个有余格，其中（1，1，…，1），（0，0，…，0）分别是上、下界。对Ln中任意元素（a1，…，an），元素（b1，…，bn）是其余元素，其中

由定理3知，对于任意格，其格中元素都满足分配不等式，下面我们引进一种满足分配恒等式的特殊格。

定义4 设（L，×，⊕）是格，如果对于任意a，b，c∈L，恒有

a×(b⊕c)=(a×b)⊕(a×c)

a⊕(b×c)=(a⊕b)×(a⊕c)

则（L，×，⊕）称为分配格。

应该指出的是，分配格定义中两个等式是等价的。亦即，在格中，只要一个分配恒等式成立，则由格的对偶性可以推出另一个分配恒等式。

例5 设S={a，b，c}，则（ρ（s），∪，∩）是由格（ρ（S），⊆）所诱导的代数系统。这个格所对应的是哈斯图如图2所示。

容易验证，对于任意的P、Q、R∈ρ（S），有

P∩(Q∪R)=(P∩Q)∪(P∩R)

P∪(Q∩R)=(P∪Q)∩(P∪R)

成立。所以，（ρ（S），⊆）是一个有界分配格。

定理6 任意一个链都是一个分配格。

证明 设格（L，≤）是一个链，任取L中三个元素a，b，c，无非是下面两种情况：

（1）a≥b，a≥c，于是a≥b⊕c，故

a×(b⊕c)=b⊕c

而a×b=b，a×c=c，所以

(a×b)⊕(a×c)=b⊕c

故

a×(b⊕c)=(a×b)⊕(a×c)

（2）a≤b或者a≤c，于是a≤（b⊕c），故a×（b⊕c）=a，而

(a×b)⊕(a×c)=a

所以a×（b⊕c）=（a×b）⊕（a×c）。

定理7 设格（L，×，⊕）是分配格，对任意a，b，c∈L，如果

a×c=b×c,a⊕c=b⊕c

则有a=b。

证明 若（L，×，⊕）是分配格，且a×c=b×c，a⊕c=b⊕c，则

a=a×(a⊕c)=a×(b⊕c)

=(a×b)⊕(a×c)

=(a×b)⊕(b×c)=b×(a⊕c)

=b×(b⊕c)=b

证毕。

我们从前面的例子已经知道，若（L，×，⊕）是有余分配格，则任意元素a的余元素未必唯一。但若这个有余格还是分配格，则余元素就唯一了。定理7的推论说明了这一事实。

推论 设格（L，×，⊕）是一个有余分配格，则对任意a∈L，a的余元素a′是唯一的。

证明 因（L，×，⊕）是有余格，设a′和a″都是a的余元素，即

a×a′=0,a⊕a′=1

a×a″=0,a⊕a″=1

则a×a′=a×a″，a⊕a′=a⊕a″，由定理7知a′=a″。证毕。

定理8（德·摩根律）设（L，×，⊕）是一个有界分配格，对任意元素a，b，若a，b有余元素a′，b′，则

(a×b)′=a′⊕b′

(a⊕b)′=a′×b′

证明 因为

(a′⊕b′)⊕(a×b)

=(a′⊕b′⊕a)×(a′⊕b′⊕b)

=(1⊕b′)×(a′⊕1)

=1×1

=1

而

(a′⊕b′)×(a×b)

=(a′×a×b)⊕(b′×a×b)

=(0×b)⊕(0×a)

=0⊕0

=0

故由余元素定义知

(a×b)′=a′⊕b′

同理可证另一等式。证毕。