《离散数学课件格与布尔代数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 一个格如果有全上界，则
