1、第七章 格与布尔代数布尔代数是计算机逻辑设计的基础，它是由格引出的，格又是从偏序集引出的。所以我们先 回顾 一下 偏序集 。是偏序集 :是 A上自反 ,反对称和传递关系 (偏序 ).偏序集中的元素间的次序可以通过它的 Hasse图反映出来 .例如 A=1,2,3,6,12,24,36, 是 A上 的 整除 关系其 Hasse图如图所示另设有集合 BA,且 B1.B的极小元与极大元y是 B的极小元 y B x(x B xy)y是 B的极大元 y B x(x B yx)例如 2,3,6的极小元 :2,3 极大元 :6 。 。 。12。 。24。 36。2.B的最小元与最大元y是 B的最小元 y B
2、 x(x Byx)y是 B的最大元 y B x(x Bxy)2,3,6的最小元 :无 最大元 : 6B如果有最小元 (最大元 ), 则是 唯一 的。3.B的下界与上界y是 B的下界 y A x(x Byx)y是 B的上界 y A x(x Bxy)2,3,6的下界 :1 上界 : 6,12,24,364.B的最大下界 (下确界 )与最小上界 (上确界 )y是 B的最大下界 (下确界 )： B的所有下界 x,有 xy。y是 B的最小上界 (上确界 )： B的所有上界 x,有 yx。2,3,6下确界 :1 上确界 :6 (B若有下 (上 )确界，则 唯一 ) 。 。 。12。 。24。 36。7-1
3、 格 (Lattice)一 . 基本概念1. 格的定义是偏序集，如果任何 a,b A,使得 a,b都有最大下界和最小上界，则称 是格。 右图的三个偏序集，不是格，因为 24,36无 最小上界。是格。 。 。 。12。 。24。 36。 30。3。 。2。 5。10。 15。6。3。4。1。2。这三个偏序集，也都不是格，第一个与第三个是同构的。因为 d和 e无下界，也无最小上界； b,c虽有下界，但无最大下界。 2,3无最大下界， 4,5无最小上界。2. 平凡格 ：所有全序都是格，称之为平凡格。因为全序中任何两个元素 x,y， 要么 xy, 要么 yx。如果 xy， 则 x,y的最大下界为 x，
4、 最小上界为 y。如果 yx， 则 x,y的最大下界为 y， 最小上界为 x 。即这 x,y的最大下界为较小元素，最小上界为较大元素 . dab ce12 34 5 6 dab c e3. 由格诱导的代数系统设 是格 ,在 A上定义二元运算 和 为 :a,b Aa b=LUB a,b, a,b的最小上界 . Least Upper Bounda b=GLB a,b, a,b的最大下界 . Greatest Lower Bound称 是由格 诱导的代数系统 . ( -并 , -交 )例如右边的格中a b=b, a b=a, b c=e4. 子格 ：设 是格 , 是由 诱导的代数系统。 B是 A的
5、非空子集 ，如果 和 在 B上 封闭 ，则称 是 的子格。是 的子格。而 不是 . b c=dB (运算规则要从格 中找 )e ab d cb a c fe gb a c fe g d a cb d二 . 格的对偶原理设 是格， 的逆关系记作 ， 也是偏序关系。也是格， 的 Hasse图是将 的 Hasse图颠倒 180即可。格的对偶原理 ：设 P是对 任 意 格 都为真的命题，如果将P中的 换成 ， 换成 ， 换成 ， 就得到命题 P , 称 P为 P的对偶命题，则 P对 任 意 格 也是为真的命题。例如： P: a ba a,b的最大下界 a 由对偶原理 P: a ba a,b的最小上界
6、a三 . 格的性质是由格 诱导的代数系统。 a,b,c,d A1. aa b, ba b, a ba, a bb此性质由运算 和 的定义直接得证。2.如果 ab， cd， 则 a cb d， a cb d。证明 ：如果 ab， 又 bb d, 由传递性得 ab d, 类似由 cd， db d， 由传递性得 cb d,这说明 b d是 a,c的 一个 上界而 a c是 a,c的最小上界所以 a cb d。类似可证 a cb d。推论 ：在一个格中，任何 a,b,c A， 如果 bc， 则a ba c， a ba c。此性质称为 格的保序性 。3. 和 都满足 交换律 。即a b=b a， a b
7、=b a。此性质由运算 和 的定义直接得证。4. 和 都满足 幂等律 。即 a a=a, a a=a 证明 ：由性质 1 得 aa a (再证 a aa)又 自反得 aa, 这说明 a是 a的上界 ,而 a a是 a的最小上界 ,所以 a a a。最后由 反对称 性 得 a a=a 。由对偶原理得 a a=a 5. 和 都满足 结合律 。即(a b) c =a (b c) ， (a b) c =a (b c) 。证明 ： 先证明 (a b) c a (b c) a a (b c) ,且 bb c a (b c) (a b) a (b c) cb c a (b c) (a b) c a (b c
8、) 同理可证 a (b c)(a b) c 最后由 反对称 性 得 (a b) c = a (b c)类似可证 (a b) c =a (b c) 。6. 和 都满足 吸收律 。即a ( a b) =a， a (a b) =a。证明 ： 显然有 aa ( a b) 再证 a ( a b) a a a a b a a ( a b) a最后由反对称得 a ( a b) =a， 类似可证 a (a b) =a。7. 和 不 满足 分配律 。但有分配 不等式 ：a (b c) (a b) (a c) ， (a b) (a c) a (b c) 。我们 先看 右图的 例子 ：d (b e)=d c=d(d b) (d e) =a e=e 而 de 即d (b e) (d b) (d e) 证明 ： aa b aa c a (a b) (a c) b cb a b, b cc a c b c (a b) (a c) 于是有 a (b c) (a b) (a c) 由对偶原理得 a (b c) (a b) (a c) 。即 (a b) (a c) a (b c) 。 c ab e d
