第六章 格代数

第六章 格和布尔代数
格是一种特殊的代数系统，特殊在:在代数系统中 引入了次序关系,让一个代数系统的载体具有序结构。 1847年由英国数学家G.Boole创立的布尔代数， 最初的设想是利用代数学的方法研究人类的思维规 律。经过后继者的研究，使得它与许多数学分支发 生了联系，如集合论、数理逻辑、代数系统、图论 与组合学。而到上世纪30年代突然发现它与工程技 术又有着意想不到的联系，1950年苏联的 M.A.aBрИЛoB发表了“继电器接点网络原理”，把 基于布尔代数的演算系统发展成为接点网络实用中 的通用理论。目前布尔代数已成为计算机科学的最 重要基础理论之一。
再证a≤b a∨b=b 设a≤b，而b≤b从而a∨b≤b∨b(=b) 而b≤a∨b,故a∨b=b(由≤的反对称性) 反之，设a∨b=b，而a≤a∨b 从而a≤b.
#
15
(11)定理6-1.7 a≤c a∨(b∧c) ≤(a∨b) ∧c Proof:设a≤c 则 a∨c=c Def6-2.2 而 a∨(b∧c)≤ (a∨b)∧(a∨c) 故 a∨(b∧c)≤ (a∨b)∧c 反之，设 a∨(b∧c)≤ (a∨b)∧c， 而 a≤ a∨(b∧c)， (a∨b)∧c ≤c 故 a ≤c（由≤的传递性） # (12)推论 (a∧b)∨(a∧c) ≤a∧(b∨(a∧c)) a∨(b∧(a∨c)) ≤(a∨b) ∧(a∨c) Proof:在(11)中因a∧c≤a可得第一式(以a∧c代替a,a 代c);因a≤a∨c可得第二式(以a代a，以a∨c代c). #
13
(9) 定理6-1.5 a∨(b∧c) ≤(a∨b) ∧(a∨c) (a∧b)∨(a∧c) ≤ a∧(b∨c)(分配不等式) Proof:a≤a∨b a≤a∨c 故a∧a≤(a∨b) ∧(a∨c) 而a= a∧a 故a ≤(a∨b) ∧(a∨c) 另外 b∧c≤b, b≤a∨b故b∧c≤a∨b(传递性) b∧c≤c, c≤a∨c故b∧c≤a∨c(传递性) 故b∧c =(b∧c) ∧(b∧c)≤(a∨b)∧(a∨c) 从而 a∨(b∧c)≤ (a∨b)∧(a∨c)
8
(2)定理6-1.1 对格<A, ≤>中任意a和b有a≤a∨b , a∧b≤a , b≤a∨b , a∧b ≤b Proof:因为a∨b是a的一个上界，当然有 <a, a∨b>∈≤ 同样地 <b, a∨b>∈≤即b ≤ a∨b 而a∧b是a的一个下界，当然有 < a∧b,a> ∈≤ 同样地 < a∧b,b> ∈≤即a∧b ≤b #
7
2.格的性质 (1)格的对偶原理(Duality Priciple) 设<A, ≤>是格,则<A,≥>也是一个格(使用格的定义即 可证得)。前者的∧恰好是后者的∨，前者的∨恰好 是后者的∧，若有关于<A, ≤> 的有效命题(真命题)， 则在该命题中将≤换成≥,将∧换成∨，将∨换成∧便 得到一个关于<A, 一个非空集合，则<2S, >是一个格； 设B={T , F}，则<B，>也是一个格。 因集合{a,b}的上确界和下确界均唯一，我们可定义 两个运算： 定义6-1.2 设<A, ≤>是一个格，在A上定义并运算∨ 与交运算∧如下，对任意的 a , b A，a∨b等于a与 b的最小上界，a∧b等于a与b的最大下界，并称<A, ∨, ∧>为由格<A, ≤>所诱导的代数系统。 例3：设A={1,2,3,4,6,12}，则<A , | >是一个格，且 4∨6=12 , 4∧6=2。
19
所以a∧b是a、b的最大下界。 下面证A中任意两个元素a , b均有最小上界a∨b。 因 a∧(a∨b) = a (吸收律) b∧(a∨b )= b(吸收律) 所以a∨b是a与b的一个上界。 现在我们证明a∨b 是a与b的最小上界。 设d是a与b的任一个上界，则 (a∨b)∨d = a∨(b∨d) (结合律) = a∨((b∧d)∨d) (因为b = b∧d) =a∨d (吸收律) = (a∧d)∨d = d 故(a∨b)∧d = (a∨b)∧((a∨b)∨d ) = a∨b
10
(4)推论 对格<A, ≤>中任意a,b,c,若b≤c则 a∧b≤ a∧c , a∨b≤a∨c (格的保序性) Proof:由(iii) 即得 #
下面的(5)至(8)为定理6-1.3 (5) 交运算和并运算是可交换的(交换律) Proof:由定义 即得
#
11
(6) 交运算和并运算是可结合的(结合律) Proof:证∨可结合： 设g=a∨(b∨c),h=(a∨b) ∨c 则a≤a ∨(b∨c)(=g), b∨c ≤ a∨(b∨c)(=g) 而b≤b∨c,c≤b∨c 故b≤a∨(b∨c)(=g) c≤a∨(b∨c)(=g)(均由传递性) 从而a ∨b ≤g(因a ∨b是a和b的最小上界) 从而(a∨b)∨c≤g(因(a∨b)∨c是a和b的最小上界) 即 h ≤g（<h,g>∈≤ ） 同理 g≤h(<g,h>∈≤) 从而g=h(由≤的反对称性) 由对偶原理可证保交运算是可结合的。 #
20
从而 a∨b ≤ d 即a∨b 是a与b的最小上界。 #
格的另一种定义是：设<A,∨,∧>是一个代数系统,其
中的∨、∧都是二元运算且满足交换律、结合律、 原定义 吸收律，则称<A,∨,∧>是格。 本定理说明了两种定义间的等价性及运算与偏序的 对应关系。
21
4.格同态 定义6-1.4 设<A1, ≤1>,<A2, ≤2>是两个格，它们分别 诱导的代数系统为<A1, ∨1, ∧1>,<A2, ∨2, ∧2>,若存 在f:A1A2,使得：a,bA1 f(a∨1b)=f(a) ∨2 f(b) f(a ∧1 b)=f(a) ∧2 f(b) 则称f为从<A1, ∨1, ∧1>到<A2, ∨2, ∧2>的格同态， 称<f(A1), ≤2>是<A1, ≤1>的格同态像； 若这个f为双射，则称之为<A1, ∨1, ∧1>到<A2, ∨2, ∧2>的格同构,或说格<A1,≤1>和<A2,≤2>是同构的
4
定义6-1.3 设<A, ≤>是一个格，由它所诱导的代数 系统为<A, ∨, ∧>， B是A的非空子集，若A上的 二元运算 ∨, ∧在B上均是封闭的，则称<B, ≤>是 <A, ≤>的子格。 可以证明，若<B, ≤>是<A, ≤>的子格，则<B, ≤>是 一个格。(满足格的定义) 注意:设 <A, ≤>是格,B为A的子集，则<B, ≤>不一 定是格；即使是格也不一定是<A, ≤>的子格。
18
再证A中任意两个元素a、b均有最大下界和最小上 界。 以下要说明a∧b是a和b的下界： 由∧运算的交换性、结合性、吸收性有 (a∧b)∧a=(b∧a)∧a=b∧(a∧a)=b∧a=a∧b (a∧b)∧b=a∧(b∧b)=a∧b 从而由≤的定义有a∧b ≤a, a∧b ≤b 即a∧b 是a和b的下界,再说明它是最大下界： 另设c是a和b的任一下界，即c≤a , c≤b 从而 c∧a=c , c∧b=c 而 c∧(a∧b) = (c∧a)∧b = c∧b = c 即 c≤a∧b
由对偶原理可知a∧(b∨c) ≥(a∧b)∨(a∧c) #
14
(10) 定理6-1.6 a≤b a∧b =a b∨a=b Proof:先证a≤b a∧b=a 设a≤b，而a≤a从而(a=)a∧a≤a∧b 而a∧b ≤a,故a ∧b=a(由≤的反对称性) 反之，设a ∧b=a，而a∧b ≤b从而a ≤b.
3
例4：下面的HASEE图定义了一个格 。a A={a,b,c,d,e,f,g}, <A, ≤>是格 。b 。d <A,∨,∧>是<A,≤>诱导的代数系统 。c a b c d e f g 。e 。f a a b a d a a g a c a e f a 。g b b b a g b g b a e a e a g c a a c a c c g c e f e f c d d g a d g d d a a f a f g e a b c g e g g e e e a c e f a g c d g f g f a f f c f g g b g d g g g a g c g e f
9
(3)定理6-1.2 对格<A, ≤>中任意a,b,c,d,若a≤b,c≤d则 a∧c≤b ∧d , a∨c ≤ b∨d Proof:由(ii) 有b≤b∨d，而a≤b 即 <b,b∨d>∈≤,<a,b>∈≤ 由传递性知 <a,b ∨d>∈≤,即a ≤ b ∨d 同样地 因d≤b∨d，而c≤d 即 <d,b∨d>∈≤,<c,d>∈≤ 由传递性知 <c,b∨d>∈≤,即c≤ b ∨d a和c有一个上界 b ∨d，而a和c的最小上界为a∨c 故 a ∨c ≤ b ∨d 同理可有 a∧c≤b ∧d #
16
3.格的存在性 引理6-1.1 设<A,∨,∧>是一个代数系统,其中的∨、 ∧都是二元运算且满足吸收性，则∨、∧都满足幂 等性。 Proof:a,bA,有a ∨(a∧b)=a a ∧(a ∨b)=a 故 a ∨(a∧(a∨b))=a(第一式中以a∨b代b) 从而 a ∨a=a(由第二式即得)
1
6-1 格(Lattice)的概念 1.格的定义 定义6-1.1 设<A, ≤>是一个偏序集(即≤是A上的具有 自反、反对称、可传递的关系),若A中任两个元素 a,b构成的集合都有最大下界(下确界)和最小上界(上 确界)则称<A, ≤>为一个格。 另一定义 例1：设I+是所有正整数的集合，| 为I + 上的整除关 系，即<a,b>| 当且仅当b是a的倍数，则< I + , | > 是一个格。