《离散数学2013第六章格与布尔代数》由会员分享，可在线阅读，更多相关《离散数学2013第六章格与布尔代数（133页珍藏版）》请在金锄头文库上搜索。
1、1,第六章 格和布尔代数,2,在第一章我们介绍了命题逻辑。当时被侧重的只是形式系统。如果视P为全体命题的集合，于是逻辑联词，就可以被看作P上的两个二元代数运算。因而，(P,)是一个代数,即通常所说的命题代数。 在命题代数中，运算,满足幂等律，交换律，结合律，分配律和吸收律。,格与布尔代数,3,在第三章我们介绍了集合的最为一般的一些理论，被关心的只是集合的基本概念，集合的运算和基数等方面的事实。如果我们令S2A，对于X,YS,则都有XY，XYS。在这两种二元运算下，(S,)是代数,即所谓幂集代数。,4,在幂集代数中, 运算, 满足幂等律, 交换律, 结合律, 分配律和吸收律. 在幂集代数中引进了
2、补集的概念和在命题代数中引进了否定的概念之后, 则在这两种代数中, 都具有了De Morgan律.,5,从代数的观点出发，我们是否能对一种更为抽象的代数系统进行研究, 使得幂集代数, 命题代数仅仅是它的特例? 回答是肯定的. 这种抽象的代数系统就是格和布尔代数. 研究布尔代数首先要研究格, 因为布尔代数是一种特殊的格.,6,格作为数学中一个很有特色的分支, 大体上说形成于二十世纪的三十到四十年代. 格作为一种理论, 它不只是代数学的一个部分, 而且在近代解析几何, 半序空间等方面也都有重要的作用. 布尔代数的问世比格要早,在十九世纪中叶,由英国数学家乔治布尔研究并提出。,7,格和布尔代数在计算
3、机科学中有广泛的应用，象有限自动机理论,开关网络理论，逻辑设计等领域都直接地应用了格和布尔代数的结论。,8,一个布尔代数是一个有补分配格. 一个格是这样的一个偏序集, 在这个偏序集中, 每两个元素都有唯一一个最小上界和唯一一个最大下界. 可见, 我们首要的任务是讨论偏序和确界的一些有关的性质, 以作为我们本章要讲述内容的基础.,9,6-1 格的概念,定义6-1.1 设是一个偏序集，如果A中任意两个元素都有最小上界(上确界)和最大下界(下确界)，则称为格。,1 格的定义,10,说明：,由于确界唯一，所以在格 中，对A中任意元素a,b ，求其上确界或下确界的结果是 中唯一的元素. 从代数的意义上说
4、，求上确界和下确界都是格中的二元运算。,由定义6-1.1及全序定义, 有: 任何一个全序集都是格. 但是任何一个偏序集并非总是格.这其实也是明显的。从逻缉的角度讲，格定义在偏序集上，其内涵的增加必然导致外延的缩小。,11,例：,考查下面Hasse图（哈斯图）:是偏序集但非格的Hasse图中,总有元素a,b,使得a,b没有上确界或下确界。,12,( a )链是格; ( b )偏序,格; ( c )偏序,格; ( d )偏序,格; ( e )偏序,非格; ( f )偏序,非格.,13,例1,设S是任意集合, 则是格。|S|=1时和|S|=2时,此格的Hasse图为:,14,例2,设I+为正整数集,
5、 偏序关系为整除,则是格, 此时对a,bI+, a、b的上确界是a,b(最小公倍数)，a、b的下确界是(a,b)(最大公因数)。,15,例,设n为正整数,Sn是n的全部正因数的集合,则是格.和 的Hasse图如下:,16,2 格诱导的代数系统,定义6-1.2 设是一个格，如果在A上定义两个二元运算和，使得对于任意的a，bA，ab等于a和b的最小上界，ab等于a和b的最大下界，那么，就称为由格所诱导的代数系统。二元运算和分别称为并运算和交运算。,17,例3,给定Sa，b，P(S)，a，b，a，b，那么，格如图6-1.3所示。,18,由格所诱导的代数系统为，其中运算是集合的并，运算是集合的交。故和
6、的运算表可分别由表6-1.1的(a)和(b)所示。,19,3 子格,定义6-1.3 设是一个格，由诱导的代数系统为，设B A且B，如果A中的这两个运算和关于B是封闭的，则称是的子格。,可以证明子格必成为格。,20,注意：,对于格，设B是A的非空子集，尽管必定是一个偏序集，然而不一定是格，而且即使是格，也不一定是的子格。,21,例5,设是一个格，其中 S=a, b, c, d, e, f, g, h，如图所示。,取 S1=a, b, d, f, S2=c, e, g, h S3=a, b, c, d, e, g, h,从图6-1.4上容易看出，和都是的子格，而虽然是格，但它不是的子格，这是因为
7、bdfS3,22,例题1,设是一个格，任取aS，构造S的子集T为：Tx | xS 且 x a 则是的一个子格。,对于任意的x，yT,必有x a和y a,解：,所以 xy a， xy a,故 xyT， xyT,因此，是的一个子格。,23,4 对偶,在命题代数、集合代数中,我们应用了对偶原理。在比命题代数和集合代数更为一般的格与布尔代数中,我们也将应用对偶原理。对偶原理是很重要的概念，它出现在许多不同的场合和领域。下面是两个生活中的例： 人体镜面成像中,如果人体(或镜中的像)X能将左手覆于右臂之上,那么X的像(或原像)X*就能将右手覆于左臂之上。,24,国内汽车交通规则,司机座在驾驶室左侧,并规定
8、汽车前行要沿马路右侧,超车须从左边道,红灯禁行时汽车可以右转弯; 英国汽车,司机座在驾驶室右侧,英国交通规则规定汽车前行要沿马路左侧,超车要从右边道,红灯禁行时汽车可以左转弯.在这里,左和右的概念都作互相交换;交换的结果形成了各自的交通规则。,左和右就是一种对偶概念,25,格上偏序关系作为二元关系, 自然可逆，我们称这一个逆关系为 的对偶关系,记为 。偏序关系的逆 , 把的Hasse图作了上下的翻转. 于是, 对集合A的任意子集B, B在偏序中的上确界, 便成了B在偏序中的下确界; B在 中的下确界,就是B在中的上确界. 之所以可称之为偏序集, 是因为二元关系的逆关系，保持原关系的自反、反对称
9、和传递性不变, 即偏序关系之逆关系仍为偏序关系.从以上分析,我们可以断言:若是格,则也是格,当然反之亦真.并称格与格为对偶的格.,26,设P是对任意格都为真的命题，如果在命题P中把 换成 ，换成，换成，就得到另一个命题P，把P称为P的对偶命题，则P对任意格也是真的命题。,27,5 格的基本性质,格是偏序集,具有偏序集的性质. 是格，对a,b,cA, 则: (1) a a ; (自反性) (2) 若a b且b a则a=b; (反对称性) (3) 若a b且b c则a c; (传递性),28,证明 ：,29,证明 ：,30,格的保序性,31,定理6-1.3 设是一个格，由格所诱导的代数系统为，则对
10、任意的a，b，c，d A，有,(1) ab=ba ab=ba,（交换律）,(2) a(bc) = (ab ) c a(bc) = (ab)c,（结合律）,(3) aa=a aa=a,(4) a(ab)=a a(ab)=a,（幂等律）,（吸收律）,32,证明：,(1) 格中任何两个元素a，b的最小上界（最大下界）当然等于b，a的最小上界（最大下界），故ab=ba （ab=ba）,33,其它结论 利用对偶原理可证,34,例6 设是一个偏序集合，这里N是自然数集，是普通的数与数之间的“小于等于”关系因为对于任意的a，bN，有 abmax(a，b)，abmin(a，b)，所以，是一个格，由这个格所诱导
11、的代数系统是。,分析：在此代数系统中，任意两个数a和b的最大值(最小值)与b和a的最大值(最小值)是相等的，因此，并运算和交运算都是可交换的；又因为max(max(a，b)，c)和max (a， max(b，c)都是三个数a，b，c中的最大值，所以在中并运算是可结合的，同理min (min(a，b)，c)min(a，min(b，c)，说明交运算的可结合性；由于max (a，a)min (a，a)a，所以幂等性成立；又由于max(a，max(a，b)a和min (a，max(a，b)a，因此，吸收性也成立。,35,6 从代数系统到格,引理6-1.1 设是一个代数系统，其中，都是二元运算且满足吸收
12、律，则和都满足幂等律。,证明：因为运算和满足吸收律，即对任意a，bA，有 a(ab)=a (1) a(ab)=a (2) 将(1)式中的b取为ab，便得 a(a(ab)=a 再由(2)，即得 aa=a 同理可证 aa=a,36,证明：,37,38,39,证明ab是a和b的最小上界。,40,7 格的性质,证明：,41,证明 ：,42,证明 ：,43,44,45,8 格同态,46,证明：,定理6-1.8说明格同态是保序的,47,定理6-1.8的逆命题不一定成立。,例7 设是一个格，其中S=a，b，c，d，e，如图所示。,我们知道，也是一个格,作映射f：SP(S),48,49,证明 ：,50,51,
13、作业：,P243 (5) (8),52,6-2 分配格,1 分配格的定义,53,54,图(a)中： b(cd) = ba = b 而 (bc)(bd) = ee = e 所以 b(cd) (bc)(bd),55,56,注意：,在分配格的定义中，必须是对任意的a，b，cA都要满足分配等式，因此，决不能验证格中的某些元素满足分配等式就断定该格是分配格。,57,例2中给出的两个具有五个元素的格是很重要的，因为有一个定理证明了如下的结论：一个格是分配格的充要条件是该格中没有任何子格与这两个五元素格中的任一个同构。,58,2 分配格的性质,定理6-2.1 如果在一个格中交运算对于并运算可分配，则并运算对
14、于交运算也一定是可分配的。反之亦然。,证明 ：,59,定理6-2.2 每个链是分配格。,证明：,60,61,证明：,62,3 模格,63,证明 ：,64,65,66,证明 ：,67,定理6-2.6 分配格必定是模格。,证明 ：,因此,68,6-3 有 补 格,1 有界格,69,证明 :,70,71,72,定义6-3.3 如果一个格中存在全下界和全上界，则称该格为有界格。,证明：,73,注意：,由a0=0a=a和a1= 1a=a说明0和1分别是关于运算和的幺元。 另外，0和1分别是关于运算和的零元。,74,2 有补格,定义6-3.4设是一个有界格，对于A中的一个元素a，如果存在bA，使得ab=1
15、和 ab=0，则称元素b是元素a的补元。,说明： 在定义6-3.4中，a和b是对称的，即如果a是b的补元，则b也是a的补元，因此，a和b这两个元素是互补的。 对于元素aA，可以存在多个补元，也可以不存在补元。 在有界格中，0是1的唯一补元，1是0的唯一补元。,75,例3 在如图所示的有界格中，因为dc=1和dc=0，所以，d和c是互补的。但是b是没有补元的。此外，a和d都是e的补元；c和e都是d的补元。,76,定义6-3.5 在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。,例4 图6-3.3中给出了一些有补格。,77,定理6-3.4 在有界分配格中，若一个元素有补元素，则必是唯一的。,证明： 设a有两个补元素b和c，即有 ab=1 ab=0 ac=1 ac=0 由定理6-2.3即得b=c。 这就证明了a的补元素是唯一的。,78,3 有补分配格,定义6-3.6 一个格如果它既是补格，又是分配格，则称它为有补分配格。有补分配格中任一元素a的唯一补元记为 。,79,6-4 布尔代数,1 布尔格,定义6-4.1 一个有补分配格称为布尔格。,注明：,80,2 布尔代数,81,82,证明：,83,3 一些概念,84,4 原子,例2 如图所示的格中，d，e都是原子且de=0，说明原子不是唯一的。1盖住a，b，c；a盖住d；c盖住e；b盖
