引言格的定义专业知识讲座.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,文档来源于网络，文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不当之处，请联系本人或网站删除。,集合代数：(S)，),对,A,B,C,(S)，运算，满足：,等幂律,AA=A,，,AA=A,，,交换律,AB=B,A,，,AB=B,A,，,结合律,A(BC)=(AB),C,，,A(BC)=(AB),C,，,分配律,A(BC)=(AB)(AC),，,A(BC)=(AB)(AC),，,吸收律,A(AB)=,A,，,A(AB)=,A,，,若引进余集的概念，有,De Morgan,定律,:,1,命题代数(S，),对,A,B,C,S，运算，满足,等幂律AA=A，AA=A，,交换律AB=BA，AB=BA,结合律A(BC)=(AB)C，,A(BC)=(AB)C,分配律A(BC)=(AB)(AC)，,A(BC)=(AB)(AC),吸收律A(AB)=A，A(AB)=A，,若引进否定,的概念，有De Morgan定律:,(,AB,)=,A,B,(,AB,)=,A,B,2,美国数学家George David Birkhoff(1884-1944年),1905年在哈佛大学毕业；,1907年在芝加哥大学获博士学位；,先后执教于威斯康星、普林斯顿和哈佛大学。,第二次世界大战期间美国数学界公认的领袖人物。,最重要的工作是在动力系统的研究方面；,在20世纪30年代提出格。,是一位十分善于激励他人的教师和研究生导师，指导的许多博士生成为20世纪中期最多产的数学家。其子Garrett Birkhoff也是著名数学家。,3,英国数学家、哲学家George,Boole(1815-1864),4,因家境窘迫，1831年(16岁)开始从教，利用业余时间钻研数学。,1847年著文 The Mathematical Analysis of Logic，后又著 An Investigation of the Laws of Thought，发展成为布尔代数。给19世纪数学带来新的转机，并成为后来计算机理论的基础。,为逻辑代数化作出了决定性的贡献，利用代数语言使逻辑推理更简洁清晰。,1857年当选为伦敦皇家学会会员(唯一没有上过大学的皇家学会会员)，不久荣获该会皇家奖章。,5,8.2,格的定义,半序格,定义A,给出一个部分序集(L,)，如果对于任意a,bL，L的子集a,b在L中都有一个最大下界(记为infa,b)和一个最小上界(记为supa,b)，则称(L,)为一个,格,。,6,半序格的例,例：,S是任意一个集合，(S)是S的幂集合，则部分序集(S),)是一个格。,因为对,A,B,(S)，,supA,B=AB,(S)，,infA,B=AB,(S),例：,设I,+,是所有正整数集合，D是I,+,中的“整除关系”，对任意a,bI,+,，aDb当且仅当a整除b，于是，(I,+,D)是一个格。,supa,b=a,b的最小公倍I,+,，,infa,b=a,b的最高公因I,+,。,7,半序格的例,例：,设n是一个正整数，S,n,是n的所有正因数的集合，于是，(S,n,D)是格。因为：,supa,b=a,b的最小公倍S,n,，,infa,b=a,b的最高公因S,n,。,例：,设S是所有的命题集合，定义“”如下：,A B 当且仅当 B蕴涵A。,则(S，)是一个格。因为：,supA,B=AB,S，,infA,B=AB,S。,8,半序子格,定义A,设(L,)是格，S,L，如果(S,)是格，则称(S,)是格(L,)的,子格,。,例：,(S,6,D)是(S,24,D)的子格。,9,代数格,定义,B,设,L,是一个集合，,、是,L,上两个二元代数运算，如果这两种运算对于,L,中元素满足：,1),交换律,：,ab=ba,，,ab=ba,。,2),结合律,：,a(bc)=(ab),c,，,a(bc)=(ab),c,。,3),吸收律,：,a(ab)=,a,，,a(ab)=,a,。,则称此代数系统,(L,),为一个,格,。,10,注：,定义B中由,满足,吸收律,可推出它们一定满足,等幂律,。,证明：,任取L中元素a，由,满足吸收律知，a(a,a)=a，a,(aa)=a。,故：aa=a(a,(aa)，,a,a=a,(a(a,a)。,又由,满足吸收律知，上面两式的等式右端都等于,a,。因此，,aa=a，a,a=a。,即，定义,B,中的,运算亦满足,等幂律,。,11,代数格的例,例：,设S是一个集合，(S)是S的幂集合，于是，(S),)是一个代数格。而(S),)是半序格。易见对,A,B,(S)，,A,B AB=A AB=B。,例：,设I,+,是所有正整数集合，两个正整数的最高公因，最小公倍是I,+,上两个代数运算，于是，(I,+,)是一个代数格。而(I,+,D)是半序格，D是整除关系。易见，对任意a,b,I,+,aDb ab=a ab=b。,例：,设n是一个正整数，S,n,是n的所有正因数的集合，两个正整数的最高公因，最小公倍可是S,n,上两个代数运算，于是，(S,n,)是一个代数格。,12,代数格与半序格的等价性,定理8.2.1,定义A所定义的格和定义B所定义的格是,等价,的，亦即，一个半序格必是一个代数格；反之亦然。,证明：,i)若(L,)是一个半序格，,则对,a,bL，记,infa,b为ab；supa,b为ab。,由于对任意a,b，其infa,b，supa,b是唯一的，所以，如上定义的,是集合L上的两种二元代数运算。,不难证明，对于,满足交换律，结合律，吸收律。则根据定义B，(L,)是一个代数格。,13,我们只证明,吸收律,：,a(ab)=a,其它算律的证明留给同学。,因为a(ab)是a与(ab)的最大下界，所以,a(ab)a。,另一方面，由于aa，aab，所以，a是a与ab的下界，故,aa(ab),所以，a=a(ab)。,证明：,14,证明：,ii)若代数系统(L,)是一个代数格,，在集合L上定义一个关系如下：,对任意a,bL，ab ab=a,往证：是一个半序关系。,反身性:,因为aa=a(a,(aa)=a，所以aa。,反对称性:,若有ab，ba，则应有ab=a，ba=b，而ab=ba，所以a=b。,传递性:,若ab，bc，则有ab=a，bc=b，故：,ac=(ab)c=a(bc)=ab=a，亦即，ac。,15,证明：,往证：ab=a ab=b。,若ab=a，则,ab=(ab)b=b。,若ab=b，则,ab=a(ab)=a。,往证:,对任意a,b,L，存在infa,b，supa,b。,由吸收律知a(ab)=a，b(ab)=b，,故有a(ab)，b(ab)。亦即，ab是a,b的上界。,16,证明：,若cL，且c是a,b的上界，亦即有ac，bc，则应有ac=c，bc=c，,于是，,(ab)c=(ab)(cc),=(ac)(bc),=cc=c,故有(ab)c。,因此，(ab)是a,b的最小上界，即,supa,b=(ab)。,同理可证，infa,b=(ab)。,综上，(L,)为半序格。证毕。,17,代数子格,定义B,设(L,)是一个代数格，S,L，(S,)称为(L,)的一个代数子格，当且仅当在运算,下，S是封闭的。,结论：,(S,)是格(L,)的子格的充要条件是：S,L且(S,)是一个格。,例：,(S,n,)是(I,+,)的代数子格，其中,分别是最高公因和最小公倍运算。,18,代数子格与半序子格的关系,设(L,)是一个半序格，与其等价的代数格为(L,)，S,L。,若(S,)是(L,)的代数子格，则(S,)是(L,)的半序子格；,若(S,)是(L,)的半序子格，则(S,),不一定,是(L,)的代数子格。,19,a,6,a,3,a,1,a,2,a,4,a,5,a,8,a,7,设,L=,a,1,a,2,a,3,a,4,a,5,a,6,a,7,a,8,，,(L,),是格,。,取,S,1,=,a,1,a,2,a,4,a,6,，则,(S,1,),是,(L,),的半序子格,，,也是,(L,),的代数子格,。,取,S,2,=,a,1,a,2,a,4,a,8,，则,(S,2,),是,(L,),的半序子格，但,(S,2,),不是,(L,),的代数子格,。,因为：,a,2,a,4,=a,6,，而,a,6,S,2,，即，,S,2,在,下不封闭。,20,作业10,1.设(L,)、(S,)是两个格，若g是L到S的同态映射，证明(g(L),)是(S,)的代数子格。,2.判断对错：,设(L，)是格，则(L，)和(L，)均为交换半群。,代数格中(L，)的两个代数运算和满足交换律、结合律、吸收律和等幂律。,设(L，)是一个格，a，b是L中任意元素，于是ab=a，ab=b。,3.P287-3,21,