离散数学-格与布尔代数课件.ppt

《离散数学-格与布尔代数课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章格与布尔代数布尔代数是计算机逻辑设计的基础，它是由格引出的，格又是从偏序集引出的。所以我们先回顾一下偏序集。是偏序集:≤是A上自反,反对称和传递关系(偏序).偏序集中的元素间的次序可以通过它的Hasse图反映出来.例如A={1,2,3,6,12,24,36},≤是A上的整除关系其Hasse图如图所示，BAB≠Φ1.B的极小元与极大元y是B的极小元y∈B∧x(x∈B∧x≤y)y是B的极大元y∈B∧x(x∈B∧y≤x)例如{2,3,6}的极小元:2,3极大元:6６。１。３。12。２。24。36。2.B的最小元与最大元y是B的最小元y∈B∧x(x∈B

2、y≤x)y是B的最大元y∈B∧x(x∈Bx≤y){2,3,6}的最小元:无最大元:6B如果有最小元(最大元),则是唯一的。3.B的下界与上界y是B的下界y∈A∧x(x∈By≤x)y是B的上界y∈A∧x(x∈Bx≤y){2,3,6}的下界:1上界:6,12,24,364.B的最大下界(下确界)与最小上界(上确界)y是B的最大下界(下确界)：B的所有下界x,有x≤y。y是B的最小上界(上确界)：B的所有上界x,有y≤x。{2,3,6}下确界:1上确界:6(B若有下(上)确界，则唯一)６。１。３。12。２。24。36。7-1格(Lattice)一.基本概念1.格的

3、定义是偏序集，如果任何a,b∈A,使得{a,b}都有最大下界和最小上界，则称是格。右图的三个偏序集，不是格，因为{24,36}无最小上界。是格。６。１。３。12。２。24。36。30。3。１。2。5。10。１5。6。3。4。1。2。这三个偏序集，也都不是格，第一个与第三个是同构的。因为d和e无下界，也无最小上界；b,c虽有下界，但无最大下界。2,3无最大下界，4,5无最小上界。2.平凡格：所有全序都是格，称之为平凡格。因为全序中任何两个元素x,y，要么x≤y,要么y≤x。如果x≤y，则{x,y}的最大下界

4、为x，最小上界为y。如果y≤x，则{x,y}的最大下界为y，最小上界为x。即这{x,y}的最大下界为较小元素，最小上界为较大元素.dabce123456dabce3.由格诱导的代数系统设是格,在A上定义二元运算∨和∧为:a,b∈Aa∨b=LUB{a,b}{a,b}的最小上界.LeastUpperBounda∧b=GLB{a,b}{a,b}的最大下界.GreatestLowerBound称是由格诱导的代数系统.(∨-并,∧-交)例如右边的格中a∧b=ba∨b=ab∧c=e4.子格：设是格,是由<

5、A,≤>诱导的代数系统。B是A的非空子集，如果∧和∨在B上封闭，则称是的子格。是的子格。而不是.b∧c=dB,(运算规则要从格中找)eabdcbacfegbacfegdacbd二.格的对偶原理设是格，≤的逆关系记作≥，≥也是偏序关系。也是格，的Hasse图是将的Hasse图颠倒180º即可。格的对偶原理：设P是对任何格都为真的命题，如果将P中的≤换成≥，∧换成∨，∨换成∧，就得到命题P’,称P’为P的对偶命题，

6、则P’对任何格也是为真的命题。例如：P:a∧b≤aP’:a∨b≥a{a,b}的最大下界≤a{a,b}的最小上界≥a三.格的性质是由格诱导的代数系统。a,b,c,d∈A1.a≤a∨bb≤a∨ba∧b≤aa∧b≤b此性质由运算∨和∧的定义直接得证。2.如果a≤b，c≤d，则a∨c≤b∨d，a∧c≤b∧d。证明：如果a≤b，又b≤b∨d，由传递性得a≤b∨d,类似由c≤d，d≤b∨d，由传递性得c≤b∨d,这说明b∨d是{a,c}的一个上界，而a∨c是{a,c}的最小上界，所以a∨c≤b∨d。类似可证a∧c≤b∧d。推论：在一个格中，任意a,b,c∈A，如果b≤c

7、，则a∨b≤a∨c，a∧b≤a∧c。此性质称为格的保序性。3.∨和∧都满足交换律。即a∨b=b∨a，a∧b=b∧a此性质由运算∨和∧的定义直接得证。4.∨和∧都满足幂等律。即a∨a=aa∧a=a证明：由性质1,a≤a∨a(再证a∨a≤a)又由≤自反有a≤a，这说明a是a的上界，而a∨a是a的最小上界，所以a∨a≤a。最后由≤反对称得a∨a=a。由对偶原理得a∧a=a5.∨和∧都满足结合律。即(a∨b)∨c=a∨(b∨c)，(a∧b)∧c=a∧(b∧c)证明