《离散数学-格与布尔代数课件》由会员分享，可在线阅读，更多相关《离散数学-格与布尔代数课件（87页珍藏版）》请在金锄头文库上搜索。
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,2.B的最小元与最大元 y是B的最小元yBx(xByx) y是B的最大元yBx(xBxy) 2,3,6的最小元:无 最大元: 6 B如果有
2、最小元(最大元), 则是唯一的。 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若有下(上)确界，则唯一),7-1 格 (Lattice),一 . 基本概念 1. 格的定义 是偏序集，如果任何a,bA,使得a,b都有最大 下界和最小上界，则称是格。 右图的三个偏 序集， 不是格， 因为24,36 无最小上界。 是格
3、。,这三个偏序集，也都不是格，第一个与第三个是同构的。 因为 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的最大下界为较小元素，最小上界为较大元素.,3. 由格诱导的代数系统 设是格,在A上定义二元运算和为:a,bA ab=LUB a,b a,b的最小上界.Least Upper Bound ab=GLB a,b a,b的最大下
4、界.Greatest Lower Bound 称是由格诱导的代数系统. (-并,-交) 例如右边的格中ab=b ab=a bc=e 4. 子格：设是格, 是 由诱导的代数系统。B是A的 非空子集，如果 和在B上封闭，则 称是 的子格。 是的子格。 而不是. bc=dB, (运算规则要从格中找),二. 格的对偶原理 设是格，的逆关系记作，也是偏序关系。 也是格，的Hasse图是将的Hasse图 颠倒180即可。 格的对偶原理：设P是对任何格都为真的命题，如果将 P中的换成，换成，换成，就得到命题P , 称P为P的对偶命题，则P对任何格也是为真的命题。 例如：P: aba P: aba a,b的最
5、大下界a 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。 类似可证 acbd。 推论：在一个格中，任意 a,b,cA，如果bc，则 abac，abac。 此性质称为格的保序性。,3. 和都满足交换律。即 ab=ba，ab=ba 此性质由运算和的定义直接得证。 4. 和都满足幂等律。
6、即 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) 所以 aba(bc) 又 cbc a(bc) 于是有 (ab)c a(bc) 再证 a(bc)(ab)c 因aab (ab)c； 再由bab(ab)c， c (ab)c 所以 bc (ab)c 于是有 a(bc)(ab)c 最后由反对称得 (ab
7、)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) 证明： 因 aab，aac 所以 a (ab)(ac) 又因 bcb a
8、b，bcc ac 所以 bc (ab)(ac) 于是有 a(bc) (ab)(ac) 。 由对偶原理得 a(bc) (ab)(ac) 。 即 (ab)(ac) a(bc) 。,8. ab ab=b ab=a 证明：先证明ab ab=a 先证ab ab=a 由 ab，又aa 所以aab 又由ab的定义有aba 由反对称得 ab=a 再证 ab=a ab 由 ab=a 则 a=ab b。 综上得 ab ab=b 下面证明ab ab=b 先证ab ab=b 由 ab，又bb 所以 ab b 又因为 bab 由反对称得 ab=b 再证 ab=b ab 由 ab=b 因 a ab 所以 ab。 综上得
9、ab ab=b,引理： 是代数系统，如果和是满足吸收律的二元运算，则和必满足幂等律。 证明：任取a,bA 因为 和满足吸收律。 于是有 a( ab) =a - a(ab) =a -。 由于上式中的b是任意的，可以令b=ab 并代入式得 a(a(ab) =a 由式得 aa=a 同理可证aa=a,定理： 设是代数系统，如果和是满足交换律，结合律，和吸收律的二元运算，则A上存在偏序关系 ，使是一个格，并且该格所诱导的代数系统恰好是。（由代数系统得到格） 证明：设在A上定义二元关系 为：对任意a,bA, a b 当且仅当 ab=a （1）先证二元关系 是一个偏序关系 （2）再证ab 是 a,b 的下确
10、界 （3）然后证a b是 a,b 的上确界 见书上238页,四.格的同态与同构,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,b f(23)=f(1)= f
11、(2)f(3)=ab= f(26)=f(6)=a,b f(2)f(6)=aa,b=a,b f(26)=f(2)=a f(2)f(6)=aa,b=a 可见它们同构。 格同构，它们的哈斯图的形状一定相同。,具有1、2、3个元素的格分别同构于含有一、二、三 个元素的链。 具有4个元素的格分别同构于下面两种格形式之一： 具有5个素的格分别同构于下面五种格形式之一：,2. 格同态的保序性 定理：设f是格 到 的同态映射，则对任 何a,bA1，如果a1b，则 f(a)2f(b)。 证明：令和 是格 和 诱导的代数系统，任取a,bA1，设a1b， 则 a1b=a f(a1b)=f(a) 即 f(a)2f(b
12、)=f(a) 而 f(a)2f(b) 2f(b) 所以 f(a)2f(b). 3. 格同构的保序性 定理：设两个格为和 ，f是A1到A2的双射，则f是 到的格同构，当且仅当 对任意a,bA1，a1b f (a)2f(b) 证明：令和 是格 和 诱导的代数系统，,1) 必要性：已知 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)
13、因f 是双射，所以 a=a1b 所以 a1b 最后得 a1b f (a)2f(b) 。,2) 充分性：已知，对任意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
14、(d) 所以 f(d)2f(a)，f(d)2f(b) 由已知得： d1a，d1b ，于是 d1a1b=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是它们的同构映射。,7-2 几个特殊格,一. 分配格 前面我们介绍一般的格，和只满足分配不等式。 a(bc) (ab)(ac) ， (ab)(ac) a(bc) 。 下面介绍的是满足分配律的格-分配格。 1. 定义： 是由格诱导的代数系统。如果 对a,b,cA，有 a(bc)
15、=(ab)(ac) ， a(bc)= (ab)(ac) 则称是分配格。 例： 所诱导的代数系统为 所以是分配格。,2. 二个重要的五元素非分配格： 2(35)=230=2 (23)(25)=11=1 c(bd)=ca=c (cb)(cd)=ed=d 可见它们都不是分配格。 3.分配格的判定： 一个格是分配格的充分且必要条件是在该格中没有任何 子格与上述两个五元素非分配格之一同构。 用此方法可以判定下面两个格不是分配格：,4. 分配格的性质 1. 在一个格中，如果对可分配，则对也可 分配。反之亦然。 证明：设是由格诱导的代数系统，且 对可分配。则任取 a,b,cA， (ab)(ac) = (ab
16、)a)(ab)c) 分配 =a(ab)c)=a(ac)(bc) 吸收、分配 = (a(ac)(bc) 结合 = a(bc) 即对也可分配 同理可证: 如果对可分配，则对也可分配. 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).全上界:设是格，
