第5篇ch15格与布尔代数.ppt

* 第15章 格 与 布 尔 代 数 15-1 格的概念 定义15-1.1 设A,?是一个偏序集，如果A中任意两个元素都有最小上界和最大下界，则称A,?为格（lattice）。 图6-1.2所示的偏序集都是格。 例1 正整数集，整除关系是格。 例2 集合的幂集，包含于关系是格。 定义15-1.2 设A,?是一个格,如果在上定义两个二元运算∨和∧ ,使得对于任意的a,b ? A ， a∨b等于 a和b的最小上界, a∧b等于a和b的最大下界,那么,就称A,∨,∧为由格A,?所诱导的代数系统。二元运算∨和∧分别称为并运算和交运算。 通常用a∨b 表示{a,b}的上确界,用a∧b 表示{a，b}的下确界,∨和∧分别称为保联(join)和保交(meet)运算。由于对任何a，b，a∨b及a∧b都是A 中确定的成员，因此 ∨,∧均为A上的运算。 定义15-1.3 设A,?是一个格, 由格A,?所诱导的代数系统为A,∨,∧ 。设B?A 且B≠? ，如果A中的两个运算∨和∧ 关于B是封闭的，则称 B,?是A,?的子格。 例3 设S={a,b} ， ?(S) ={?, {a},{b},{a,b}}由格 ?(S), ? 诱导的代数系统为 ?(S),∨,∧ 。其中∨为集合的并运算和∧为集合的交运算。 格对偶原理：设A,?是一个偏序集,在A上定义一 个二元关系?R,使得对于A中任意两个元素a,b都有关系a?Rb当且仅当b?a,于是A,?R也是一个偏序集。把A,?和A,?R称为相互对偶的(哈斯图相互颠倒)。 可以证明，若A,?是格，则A,?R也是格。 称?R是?的逆关系。记为?。 格对偶原理可以叙述为：设P是对任意格都真的命题，如果在命题P中把?换成? ，∨换成∧，∧换成∨，就得到另一个命题P’，我们把P’称为P的对偶命题，则P’对任意格也是真的命题。 定理15-1.1 在一个格A,?中，对任意两个元素a,b?A都有 a? a∨b b?a∨b a∧b?a a∧b? b ? 证明思路： 因为a和b的并是a的一个上界，所以 a? a∨b 同理 b?a∨b 有对偶原理，即得 a∧b?a a∧b? b ? 定理15-1.2 在一个格A,?中，对于任意元素a,b,c,d?A,如果 a?b 和 c?d 则 a∨c ? b∨d a∧c ? b∧d 推论 在一个格A,?中，对于任意元素a,b,c?A,如果b?c,则 a∨b ? a∨c, a∧b?a∧c(保序性)。 ? 证明思路：因为b?b∨d和d?b∨d，所以由传递性 a?b∨d和 c?b∨d 即 b∨d是a和c的一个上界，而a∨c是a和c的最小上界，所以，必有 a∨c ? b∨d 类似地证明 a∧c ? b∧d ? 定理15-1.3 在一个格A,?中,由格A,?所诱导的代数系统为A,∨,∧,则对于任意元素a,b,c,d?A,有 (1) a∨b= b∨a a∧b= b∧a (2) a∨(b∨c)=(a∨b)∨c a∧(b∧c)=(a∧b)∧c (3) a∨a=a a∧a=a (4) a∨(a∧b)=a a∧(a∨b)=a （交换律） （结合律） （幂等律） （吸收律） ? 证明思路：因（1）根据格的定义， a，b 。 （2）第一式：先证[(a∨b)∨c]?[a∨(b∨c)] 根据定理1（x?x∨y,y?x∨y） b ?b∨c ? a∨(b∨c ) , a ? a∨(b∨c ) 根据定理2（x1?x2且y1?y2 ?x1∨y1?x2∨y2） a∨b ? a∨(b∨c ) 又因为 c ?(b∨c ) ? a∨(b∨c ) 再根据定理2 (