下载文档原格式
第十三章格与布尔代数13.1 格的定义与性质一、格作为偏序集的定义1．格的定义定义13.1设<S,>是偏序集,如果x,y S,{x,y}都有最小上界和最大下界,则称S 关于偏序作成一个格。
由于最小上界和最大下界的唯一性,可以把求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧,即求x∨y和x∧y分别表示x与y的最小上界和最大下界。
这里要说明一点，本章中出现的∨和∧符号只代表格中的运算，而不再有其它的含义。
2．格的实例例13.1设n是正整数,S n是n的正因子的集合。
D为整除关系,则偏序集<S n,D>构成格。
x,y∈S n,x∨y是lcm(x,y),即x与y的最小公倍数。
x∧y是gcd(x,y),即x与y的最大公约数。
图13.1给出了格<S8,D>，<S6,D>和<S30,D>.图13.1例13.2 判断下列偏序集是否构成格,并说明理由。
(1) <P(B),>,其中P(B)是集合B的幂集。
(2) <Z,≤>,其中Z是整数集,≤为小于或等于关系。
(3) 偏序集的哈斯图分别在图13.2中给出。
二．格的性质1．对偶原理定义13.2设f是含有格中元素以及符号=,,,∨和∧的命题。
令f*是将f中的替换成,替换成,∨替换成∧,∧替换成∨所得到的命题。
称f*为f的对偶命题。
例如,在格中令f是(a∨b)∧c c, 则f*是(a∧b)∨c c .格的对偶原理设f是含有格中元素以及符号=,,,∨和∧等的命题。
若f对一切格为真,则f的对偶命题f*也对一切格为真。
例如,对一切格L都有a,b∈L,a∧b a那么对一切格L都有a,b∈L,a∨b a许多格的性质都是互为对偶命题的。
有了格的对偶原理,在证明格的性质时,只须证明其中的一个命题就可以了。
2. 运算性质定理13.1设<L,>是格,则运算∨和∧适合交换律、结合律、幂等律和吸收律,即(1) a,b ∈L 有a∨b=b∨a, a∧b=b∧a(2) a,b,c∈L 有(a∨b)∨c=a∨(b∨c), (a∧b)∧c=a∧(b∧c)(3) a∈L 有a∨a=a, a∧a=a(4) a,b∈L 有a∨(a∧b)=a, a∧(a∨b)=a证(1)a∨b和b∨a分别是{a,b}和{b,a}的最小上界。
一、格的引入在上一章中讨论过偏序集与偏序关系时,已经把格定义为一种特殊的偏序集。
下面, 先回顾一下几个有关概念。
设<A；≤>是偏序集合, B 是A 的子集, 若任意 b∈B,b≤a,则a 是子集B 的上界。
若a′也是B 的上界, 有a≤a′,也即a是B的上界集合的最小元，这时称a 是子集B 的最小上界, 记为lub(B)；类似地，若任意b∈B,a≤b,则a是B 的下界。
若a′也是B 的下界, 有a′≤a, 称a 是子集B 的最大下界, 记为glb(B)。
由最大元、最小元的唯一性可知，最大下界、最小上界若存在, 则唯一。
此外, 若b≤a 且b≠a, 则可用b<a 表示。
例子:1) 设有集合U={a, b, c}, U 的幂集P(U)上的包含关系⊆是一个偏序关系, 根据它的哈斯图(图9.5(a))可见, {a, b, c}是{a, b}和{b, c}的上界, 它也是{a, b}和{b, c} 的最小上界, {b}和∅均是{a, b}和{b, c}的下界, 其中{b}是它们的最大下界。
{a, b, c} 和{a, b}是{a, b}和{b}的上界, 其中{a, b}是最小上界。
2) 集合A={2, 3, 4, 6, 8, 12, 36, 60}上的整除关系“｜”是一个偏序, 由它的哈斯图可以看出, 2 和3 没有下界, 因而没有最大下界；8 和12 没有上界, 因而也没有最小上界。
▊由上述例子可以看出：对任意一个偏序集来说, 其中每一对元素不一定都有最大下界或最小上界。
对于其中每一对元素有最大下界和最小上界的一类偏序集, 就是这里所要讨论的格。
二、格的定义和例子定义1：设<A；≤>是一个偏序集, 如果A 中任意两个元素均有最小上界和最大下界, 那么就说A 关于偏序“≤”作成一个格(Lattice), 有时直接称A 为格。
当一个格A 中的元素是有限时, 称格A 是个有限格。
对于一个有限格<A；≤>来说, A中的偏序关系可以通过偏序集A 的哈斯图表示, 这个图也称为格A 的次序图。
例子1) 偏序集<P(U)；⊆>, 对于任意 S1, S2∈P(U), S1, S2⊆U, 有S1⊆S1∪S2,S2⊆S1∪S2, 并且若有子集S⊆U, 使得S1⊆S, S2⊆S, 必有S1∪S2⊆S。
因此, 对于任意 S1, S2∈P(U),lub(S1, S2)=S1∪S2；同理可得, 对于任意 S1, S2∈P(U), glb(S1, S2)=S1∩S2, 于是<P(U)；⊆>是一个格。
2) 设n 是一个正整数, S n 是n 的所有因子的集合。
例如, 当n=30 时, S30={1, 2, 3, 5, 6, 10, 15, 30}。
设“|”是整除关系, 则由偏序集<S30；|>的哈斯图易知它是格。
类似地, 也容易判断<S6；|>, <S8；|>, <S24；|>也是格。
其实, 对于偏序关系“|”, S n 中子集{i,j}的最小上界就是i, j 的最小公倍数, 最大下界就是i,j 的最大公因数。
3) 设P 是所有的命题集合, “→”为蕴涵关系, 则对任意P1, P2∈P, glb(P1, P2)=P1∧P2,lub(P1, P2)=P1∨P2, 因此<P; →>是一个格。
注意, 如果偏序集<S；≤>是格, 则任意两个元素a、b 在格内存在唯一的最小上界和最大下界。
于是, 求最小上界和最大下界是格<S；≤>中的两个二元运算。
这两个运算可分别用符号“∨”、“∧”表示。
即在格<S；≤>中, 任意a, b ∈ S, lub(a,b)=a∨b,glb(a,b)=a∧b。
三、格的对偶原理及基本性质。
格的对偶原理是格的一个主要性质, 它与数理逻辑部分介绍的对偶定理是类似的, 这将有利于处理“对一切格都成立”的这一类成对出现的命题。
这里不对格的对偶原理作具体证明。
集合S 的偏序关系≤的逆关系≥也是偏序关系, 若A⊆S,其中≤的glb(A)对应于≥的lub(A),≤的lub(A)对应于≥的glb(A),所以, 若<S；≤>是格, 则<S；≥>也是格, 称这两个格互为对偶。
定理一（格的对偶原理）因为<S；≤>的∧是<S；≥>的∨, <S；≤>的∨是<S；≥> 的∧, 所以, 关于格的一般性质的任意命题P, 如用≥替换≤, 用∨替换∧, 用∧替换∨, 所得到的命题P′仍成立, 这称为格的对偶原理。
下面定理给出了格的基本性质。
定理二（格的基本性质）：设<L；≤>是一个格, ∨, ∧为求任意二元素最小上界和最大下界的二元运算,则对于任意a, b, c, d∈L, 满足1) 自反性 a≤a, 对偶命题 a≥a。
2) 反对称性 a≤b 且a≥b⇒a=b 对偶命题 a≥b 且a≤b⇒a=b。
3) 传递性 a≤b 且b≤c⇒a≤c 对偶命题 a≥b 且 b≥c ⇒a≥c4) 幂等律 a∧a=a 对偶命题 a∨a=a5) 交换律 a∧b=b∧a 对偶命题 a∨b=b∨a6) 最大下界描述a∧b≤a,a∧b≤b 对偶命题 a∨b≥a,a∨b≥bc≤a,c≤b⇒c≤a∧b 对偶命题 c≥a,c≥b⇒c≥a∨b7) 结合律 a∧(b∧c)=(a∧b)∧c 对偶命题 a∨(b∨c)=(a∨b)∨c8) 吸收律 a∧(a∨b)=a 对偶命题 a∨(a∧b)=a9) a≤b⇔a∧b=a⇔a∨b=b 对偶命题 a≥b⇔a∨b=a⇔a∧b=b10) a≤c,b≤d⇒a∧b≤c∧d 且a∨b≤c∨d11) 保序性 b≤c⇒a∧b≤a∧c 且a∨b≤a∨c12) 分配不等式 a∨(b∧c)≤(a∨b)∧(a∨c) 对偶命题 a∧(b∨c)≥(a∧b)∨(a∧c)四、格的第二定义：定义2 设有代数结构<L；∧,∨>，其中是集合, ∧,∨是L 上两个二元运算, 若∧,∨均满足结合律、交换律、∧和∨吸收律, 则称<L；∧,∨>是格, 称该代数结构为格代数。
例如，幂集格<P(U)；⊆>也可以认为是<P(U)；∩，∪>要证明这两个定义等价，只须证明由这两个二元运算可以唯一的确定一个偏序关系即可，这里从略。
五、分配格定义3 称格< L; ∨,∧>为分配格(Distributive lattice)。
如果它满足分配律, 即对任意a,b,c ∈L,a∧(b∨c)=(a∧b)∨(a∧c) (1)a∨(b∧c)=(a∨b)∧(a∨c) (2)需要说明的是, 上述定义中的两个等式事实上是等价的, 因此可以去掉其中一个。
因为根据等式(1) 有, a∨(b∧c)=(a∨(a∧c))∨(b∧c)=a∨((a∧c)∨(b∧c))=a∨((a∨b)∧c)=((a∨b)∧a)∨((a∨b)∧c)＝(a∨b)∧(a∨c), 即等式(2)。
反之, 也可以由(2)得到等式(1)。
例1设A 是任意的集合, 则幂集格<P(A)；∪, ∩>为分配格。
由集合的并∪和集合的交∩的性质容易得到此结论。
例2 设<S；∨, ∧>是一个分配格, 对于任意的a, b, c∈S, 如果a∧b=a∧c, a∨b=a ∨c,则有b=c。
证明b=b∨(b∧a)=b∨(c∧a)=(b∨c)∧(b∨a)=(c∨b)∧(c∨a)=c∨(b∧a)=c∨(c ∧a)=c。
证毕。
六、格的最大元和最小元----有界格类似于偏序集, 格中也可能存在最大元、最小元, 且如果存在则惟一。
定义4设<S；∨, ∧>是一个格, 如果存在一个元素a∈S, 对于任意的x∈S, 均有x≤a(或a≤x), 则称a 是格S 的一个最大(或最小)元。
当一个格中最大元、最小元均存在时, 则称S 是个有界格。
格的最大元、最小元如果存在, 其惟一性是容易证明的。
设a, b 是格S 的两个最大元素, 则有a≤b 和b≤a。
而<S；≤>是个偏序集, 所以由反对称性知a=b。
于是格L 中最大元是惟一的。
同理, 可证最小元素也必定是惟一的。
如果格的最大元、最小元如果存在, 通常用1 来表示这个惟一的最大元, 用0 来表示这个最小元。
例在幂集格<P(A)；∪, ∩>中, 1=A, 0=∅。
七、有补格定义5 设< L；∨,∧>为有界格, a 为L 中一元素, 如果a∨b=1, a∧b=0，则称b 为a 的补元或补( Complements ). 有界格< L, ∨,∧>称为有补格(Complemented lattice) 如果L 中每个元素都有补元。
显然, 补元是相互的, 即b 是a 的补元, 那么a 也是b 的补元。
此外, 0 和1 互为补元。
有补格中, 元素0, 1 的补元是惟一的。
假设a 也是1 的补元, 那么a∧1=0,即a=0. 因此1 的补元仅为0. 同样0 的补元仅为1 。
例幂集格<P(A)；∪, ∩>是一个有补格。
P(A)含有最大元素1(=A), 最小元素0(=∅), 于是<P(A)；∪, ∩>是一个有界格, 对于任意A1∈P(A), 则有A-A1=B∈P(A)满足A1∪B=A, A1∩B=∅, 于是A1 有补元A-A1∈P(A), 故<P(A)；∪, ∩>是有补格。
八、布尔代数定义6 如果格<L；∨, ∧>既是分配格, 又是有补格, 则称为布尔代数(也称为有补分配格或布尔格), 如果一个布尔代数的元素是有限的, 则称它是一个有限布尔代数。
例如，幂集格< P(A)；∪, ∩>就是一个有补分配格。
容易证明有补分配格中每个元素的补都是唯一的。
于是, 求补运算“′”是一个布尔代数S 中的一个一元运算。
这样, 布尔代数L 是一具有两个二元运算∨, ∧, 一个一元运算′(求补)的代数结构。
以后用<L；∨, ∧, ′>或<L；+, •, ->来表示布尔代数。
也常常用<L；∨, ∧, ′,0,1>或<L；+, •, -, 0, 1>来表示布尔代数, 其中0, 1 分别为最小元、最大元。
代数是个有补分配格, 从而关于格、分配格和有补格中成立的一切性质或运算定律在一个布尔代数中也都成立, 包括交换律、结合律、等幂律、吸收律、分配律、同一律、零一律、互补律、对合律以及德·摩根律等。
下面的定理3 指出了有补分配格中补运算的部分性质。
定理3 设<S；∨, ∧>是一个有补分配格, 则有：1) 对合律成立, 即对于S 中任意元素a 有(a′)′=a；2) 德·摩根律成立, 即对于任意a, b∈S, 有：(a∨b)′=a′∧b′, (a∧b)′=a′∨b′3) 对于任意a, b∈S, 有：(a≤b)⇔(a∧b′=0)⇔(a′∨b=1)。
