《离散数学课件格与布尔代数2》由会员分享,可在线阅读,更多相关《离散数学课件格与布尔代数2(33页珍藏版)》请在金锄头文库上搜索。
1、第十一章 格与布尔代数布尔代数是计算机逻辑设计的基础,它是由格引出的,格又是 从偏序集引出的。所以我们先回顾一下偏序集。 是偏序集:是A上自反,反对称和传递关系(偏序). 偏序集中的元素间的次序可以通过它的Hasse图反映出来.例如A=1,2,3,6,12,24,36, 是A上的整除关系 其Hasse图如图所示 另设有集合BA,且 B 1.B的极小元与极大元y是B的极小元yBx(xBxy)y是B的极大元yBx(xByx) 例如2,3,6的极小元:2,3 极大元:6。12。24。36。2.B的最小元与最大元y是B的最小元yBx(xByx)y是B的最大元yBx(xBxy)2,3,6的最小元:无 最
2、大元: 6 B如果有最小元(最大元), 则是唯一的。 3.B的下界与上界 y是B的下界yAx(xByx) y是B的上界yAx(xBxy)2,3,6的下界:1 上界: 6,12,24,36 4.B的最大下界(下确界)与最小上界(上确界) y是B的最大下界(下确界):B的所有下界x,有xy。 y是B的最小上界(上确界):B的所有上界x,有yx。 2,3,6下确界:1 上确界:6 (B若有下(上)确界,则唯一)。12。24。36。11-1 格 (Lattice)一 . 基本概念 1. 格的定义 是偏序集,如果任何a,bA,使得a,b都有最大下 界和最小上界,则称是格。 右图的三个偏 序集, 不是格,
3、 因为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,最小上界为y。 如果yx,则x,y的最大下界为y,最小上界为 x 。 即这x,y的最大下界为较小元素,最小上界为较大元素. dab ce1 2 3 4 5 6dab c e3. 由格诱导的代数系统 设是格,
4、在A上定义二元运算和为:a,bAab=LUB a,b, a,b的最小上界. Least Upper Boundab=GLB a,b, a,b的最大下界. Greatest Lower Bound 称是由格诱导的代数系统. (-并,-交) 例如右边的格中 ab=b, ab=a, bc=e 4. 子格:设是格, 是 由诱导的代数系统。B是A的 非空子集,如果 和在B上封闭,则 称是 的子格。 是的子格。 而不是. bc=dB (运算规则要从格中找)e ab d cb a c fe gb a c fe g d a cb d二. 格的对偶原理设是格,的逆关系记作,也是偏序关系。 也是格,的Hasse图
5、是将的Hasse图 颠倒180即可。格的对偶原理:设P是对任意格都为真的命题,如果将 P中的换成,换成,换成,就得到命题P , 称P为P的对偶命题,则P对任意格也是为真的命题。例如: P: aba a,b的最大下界a 由对偶原理 P: aba a,b的最小上界a 三. 格的性质是由格诱导的代数系统。a,b,c,dA 1. aab, bab, aba, abb此性质由运算和的定义直接得证。2.如果ab,cd,则 acbd,acbd。 证明:如果ab,又bbd, 由传递性得abd, 类似由cd, dbd,由传递性得cbd, 这说明bd是a,c的一个上界 而ac是a,c的最小上界 所以 acbd。
6、类似可证 acbd。 推论:在一个格中,任何 a,b,cA,如果bc,则abac,abac。此性质称为格的保序性。 3. 和都满足交换律。即ab=ba,ab=ba。此性质由运算和的定义直接得证。4. 和都满足结合律。即(ab)c =a(bc) , (ab)c =a(bc) 。证明:先证明(ab)c a(bc) a a(bc) ,且 bbc a(bc) (ab) a(bc) cbc a(bc) (ab)c a(bc) 同理可证 a(bc)(ab)c 最后由反对称性得 (ab)c = a(bc)类似可证 (ab)c =a(bc) 。 5. 和都满足幂等律。即 aa=a, aa=a 证明:由性质1
7、得 aaa (再证aaa)又自反得aa, 这说明a是a的上界,而aa是a的最小上界,所以 aa a。最后由反对称性得 aa=a 。由对偶原理得 aa=a 6. 和都满足吸收律。即a( ab) =a, a(ab) =a。 证明:显然有 aa( ab) 再证 a( ab) a a a ab a a( ab) a 最后由反对称得 a( ab) =a, 类似可证 a(ab) =a。7. 和不满足分配律。但有分配不等式:a(bc) (ab)(ac) , (ab)(ac) a(bc) 。 我们先看右图的例子:d(be)=dc=d(db)(de) =ae=e 而 de 即d(be) (db)(de) 证明:
8、 aab aac a (ab)(ac) bcb ab, bcc ac bc (ab)(ac) 于是有 a(bc) (ab)(ac) 由对偶原理得 a(bc) (ab)(ac) 。即 (ab)(ac) a(bc) 。 c ab e d8. ab ab=a ab=b 证明:先证明ab ab=a 先证ab ab=a 由 ab,又aa 所以aab 又由ab的定义有aba 由反对称得 ab=a 再证 ab=a ab由 ab=a 则 a=abb。综上得 ab ab=b 下面证明ab ab=b 先证ab ab=b 由 ab,又bb 所以 ab b 又因为 bab 由反对称得 ab=b 再证 ab=b ab由
9、 ab=b 因 a ab 所以 ab。综上得 ab ab=b 四.格的同态与同构1.定义:设 和是两个格,由它们诱导 的代数系统分别是和 如果存在映射f:A1A2 使得对任何a,bA1, 有f(a1b)=f(a)2f(b)f(a1b)=f(a)2f(b) 则称f是从到 的格同态。 也称是 的格同态像。 如果 f 是双射的,就称f是到 的格同构,也称格 和同构。例如, A=1,2,3,6, 是A上整除关系。, E=a,b 它们诱导的代数系统分别是和 其中和分别是求两个数的最小公倍数和最大公约数.f(23)=f(6)=a,b f(2)f(3)=ab=a,bf(23)=f(1)= f(2)f(3)=
10、ab=f(26)=f(6)=a,b f(2)f(6)=aa,b=a,bf(26)=f(2)=a f(2)f(6)=aa,b=a 可见它们同构。 格同构,它们的哈斯图的形状一定相同。 ba a,b 1 32 6f6 3 2 1 aba,bA P(E)具有四个素的格分别同构于下面两种格形式之一 :具有五个素的格分别同构于下面五种格形式之一 : d a b c d ab c e c d d ab c e ab c e ab d a e bc d d a b c e11-2 几个特殊格一. 分配格 前面我们介绍一般的格,和只满足分配不等式。a(bc) (ab)(ac) , (ab)(ac) a(bc)
11、 。 下面介绍的是满足分配律的格-分配格。 1. 定义: 是由格诱导的代数系统。如果 对a,b,cA,有a(bc) =(ab)(ac) , a(bc)= (ab)(ac) 则称是分配格。2. 二个重要的五元素非分配格2(35)=230=2 (23)(25)=11=1c(bd)=ca=c (cb)(cd)=ed=d 可见它们都不是分配格。 3.分配格的判定:一个格是分配格的充分且必要条件是在该格中没有任何 子格与上述两个五元素非分配格之一同构。 用此方法判定下面两个格是不是分配格? 3 1 302 5 d e ab c 4 1 63 5 2 f g ad ceb4. 分配格的性质 1. 定理7-
12、2.1. 在格中,如果对可分配,则对也可 分配.反之亦然。 证明:设是由格诱导的代数系统。且 对可分配。任取a,b,cA, a(bc)= (ab)(ac) 而 (ab)(ac) = (ab)a)(ab)c) 分配 =a(ab)c)=a(ac)(bc) 吸收、分配 = (a(ac)(bc) 结合 = a(bc) 吸收 同理可证: 如果对可分配,则对也可分配. 2. 定理11-2.2. 所有链均为分配格。 证明:显然任何链都不会含有与五元素非分配格之一同 构的子格,所以链必是分配格。3. 定理11-2.3 . 设是分配格,对任何a,b,cA, 如果 有 ab=ac 及 ab=ac 则必有 b=c . 证明:任取a,b,cA, 设有 ab=ac 及 ab=ac b=b(ab) (吸收律)=b(ac) (代换)=(ba)(bc) (分配)=(ab)(bc) (交换)=(ac)(bc) (代换)=(ab)c (分配)=(ac)c (代换)=c (吸收律)二. 有界格1. 格的全上界与全下界 1).全上界:设是格,如果存在元素aA 对任何xA, xa, 则称 a是格的全上界,记作1。 (即是A的最大元) 定理7-2.4 一个格如果有全上界,则