《离散数学格与布尔代数_图文》由会员分享，可在线阅读，更多相关《离散数学格与布尔代数_图文（88页珍藏版）》请在金锄头文库上搜索。
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。7-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. 由格诱导的代数系统 设是格,在A
4、上定义二元运算和为: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. 和都满足幂等律。即 aa=a, aa=a 证明：由性质1 得 aaa (再证aaa)又自反得aa, 这说明a是a的上界,而aa是a的最小上界,所以 aa a。最后由反对称性得 aa=a 。由对偶原理得 aa=a 5. 和都满足结合律。即(ab)c =a(bc) ， (ab)c =a(bc) 。证明：先证明(ab)c a(bc) a a(bc) ,且 bbc a(bc) (ab) a(bc) cbc a
7、(bc) (ab)c a(bc) 同理可证 a(bc)(ab)c 最后由反对称性得 (ab)c = a(bc)类似可证 (ab)c =a(bc) 。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) 证明： aa
8、b 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由 ab
9、=b 因 a ab 所以 ab。综上得 ab ab=b 引理： 是代数系统，如果和是满足 吸收律的二元运算，则和必满足幂等律。 证明：任取a,bA 因为 和满足吸收律。 于是有a( ab) =a - a(ab) =a - 上式中的b是任意的 可以令b=ac 并代入式得a(a(ac) =a 由式得 aa=a 同理可证aa=a定理： 设是代数系统，如果和是满足 交换律，结合律，和吸收律的二元运算，则A上存在 偏序关系，使是一个格。 证明：见书上237页四.格的同态与同构1.定义：设 和是两个格，由它们诱导 的代数系统分别是和 如果存在映射f:A1A2 使得对任何a,bA1, 有f(a1b)=f(a
10、)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)=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 6f
11、6 3 2 1 aba,bA P(E)2. 格同态的保序性 定理：设f是格 到 的同态映射，则对任 何a,bA1,如果a1b, 则 f(a)2f(b). 证明：令和 是格 和诱导的代数系统，任取a,bA1,设a1b则必有a1b=a ,即f(a1b)=f(a) 而由同态关系式f(a1b)= f(a)2f(b), 所以有f(a)2f(b)=f(a) 而f(a)2f(b)2f(b) 所以 f(a)2f(b). 3. 格同构的保序性 定理：设两个格 到,f是从A1到A2的双射,则f 是 到的同构映射，当且仅当 对任何 a,bA1, 若 a1b f (a)2f(b). 证明：令和 是格 和诱导的代数系统
12、，1).充分性:已知f是双射,任取a,bA1,若a1b f (a)2f(b).( 应证出 f(a1b)=f(a)2f(b) 及 f(a1b)=f(a)2f(b) ) a) 证 f(a1b)=f(a)2f(b) 令a1b=c c1a c1b 由已知得 f(c)2f(a) 和 f(c)2f(b). 所以 f(c)2f(a)2f(b)-再证 f(a)2f(b)2 f(c) 由于f(a),f(b)A2 , 又2的封闭性得 f(a)2f(b)A2 , 又由f:A1A2是双射，必有dA1, 使得 f(a)2f(b)=f(d) 所以 f(d)2f(a)及f(d)2f(b) 由已知条件得： d1a及d1b d
13、1a1b=c,即 d1c f(d)2f(c) 即 f(a)2f(b)2 f(c) - 由得 f(a)2f(b)=f(c) 即 f(a1b)=f(a)2f(b) 。 b)类似可证 f(a1b)=f(a)2f(b) 所以 f是它们的同构映射2).必要性:已知 f是格 到 的同构映射, （ 应证出：任取a,bA1, 若a1b f (a)2f(b) ） a) 先证 a1b f (a)2f(b) 任取a,bA1,设a1b ，由格同态保序性得 f(a)2 f(b) b)再证f (a)2f(b) a1b 设 f (a)2f(b)， f(a)=f(a)2f(b)=f(a1b) f 是双射， a=a1b 所以 a1b 最后得 若a1b f (a)2f(b) 。 定理证毕。 由格的同构得： 具有一、二、三个素的格分别同构于含有一、二、三 个元素的链。 a a b a b c具有四个素的格分别同构于下面两种格形式之一 ：具有五个素的格分别同构于下面五种格形式之一 ：作业 P242 (1) (2) (4) (7) d a
