第09章格与布尔代数优秀课件.ppt
《第09章格与布尔代数优秀课件.ppt》由会员分享,可在线阅读,更多相关《第09章格与布尔代数优秀课件.ppt(70页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第09章格与布尔代数章格与布尔代数第1页,本讲稿共70页9.1 格格1格作为偏序集定定定定义义义义9.1.19.1.1 设设设设是是是是一一一一个个个个偏偏偏偏序序序序集集集集,若若若若对对对对任任任任意意意意a,b,a,b,L L,存存存存在在在在glba,bglba,b和和和和luba,bluba,b,则则则则称称称称为为为为格格格格,并并并并记记记记为为为为a*b=glba,ba*b=glba,b,a a b=luba,bb=luba,b,称称称称 和和和和 分分分分别别别别为为为为L L上上上上的的的的交交交交(或或或或积积积积)和和和和并并并并(或或或或和和和和)运运运运算算算算。
2、称称称称L,*为为为为所所所所诱诱诱诱导导导导的的的的代代代代数数数数结结结结构构构构的的的的格格格格。若若若若L L是有限集合,称是有限集合,称是有限集合,称是有限集合,称为有限格。为有限格。为有限格。为有限格。第2页,本讲稿共70页格的对偶性原理是成立的:格的对偶性原理是成立的:格的对偶性原理是成立的:格的对偶性原理是成立的:令令令令是偏序集,且是偏序集,且是偏序集,且是偏序集,且是其对偶的偏是其对偶的偏是其对偶的偏是其对偶的偏序集。若序集。若序集。若序集。若是格,则是格,则是格,则是格,则也是格,反之亦也是格,反之亦也是格,反之亦也是格,反之亦然。这是因为,对于然。这是因为,对于然。这是
3、因为,对于然。这是因为,对于L L中任意中任意中任意中任意a a和和和和b b,中中中中luba,bluba,b等同于等同于等同于等同于中中中中glb a,bglb a,b,中中中中glba,bglba,b等同于等同于等同于等同于中的中的中的中的luba,bluba,b。若。若。若。若L L是有限是有限是有限是有限集,这些性质易从偏序集及其对偶的哈斯图得集,这些性质易从偏序集及其对偶的哈斯图得集,这些性质易从偏序集及其对偶的哈斯图得集,这些性质易从偏序集及其对偶的哈斯图得到验证。到验证。到验证。到验证。第3页,本讲稿共70页从上讨论中,可知两格互为对偶。互为对从上讨论中,可知两格互为对偶。互为
4、对从上讨论中,可知两格互为对偶。互为对从上讨论中,可知两格互为对偶。互为对偶的两个偶的两个偶的两个偶的两个和和和和有着密切关系,即格有着密切关系,即格有着密切关系,即格有着密切关系,即格中交运算中交运算中交运算中交运算 正是格正是格正是格正是格中的并运算中的并运算中的并运算中的并运算 ,而,而,而,而格格格格中的并运算中的并运算中的并运算中的并运算 正是格正是格正是格正是格中的交运算中的交运算中的交运算中的交运算 。因此,给出关于格一般性质的任何有效命题,因此,给出关于格一般性质的任何有效命题,因此,给出关于格一般性质的任何有效命题,因此,给出关于格一般性质的任何有效命题,把关系把关系把关系把
5、关系 换成换成换成换成(或者(或者(或者(或者 换成换成换成换成),交换成并,并),交换成并,并),交换成并,并),交换成并,并换成交,可得到另一个有效命题,这就是关于换成交,可得到另一个有效命题,这就是关于换成交,可得到另一个有效命题,这就是关于换成交,可得到另一个有效命题,这就是关于格的对偶性原理。格的对偶性原理。格的对偶性原理。格的对偶性原理。定义定义定义定义9.1.29.1.2 设设设设是格,且是格,且是格,且是格,且S S L L。若对任。若对任。若对任。若对任意意意意a,ba,b S S,有,有,有,有a*ba*b S S和和和和a a b b S S,则称,则称,则称,则称是是是
6、是格格格格的子格。的子格。的子格。的子格。第4页,本讲稿共70页2格的基本性质在在在在证证证证明明明明格格格格的的的的性性性性质质质质前前前前,回回回回忆忆忆忆一一一一下下下下a*ba*b和和和和a a b b的的的的真正含义是有好处的。真正含义是有好处的。真正含义是有好处的。真正含义是有好处的。a*baa*ba和和和和a a bbbb,则则则则表表表表明明明明a*ba*b是是是是a a和和和和b b的的的的下下下下界。界。界。界。若若若若caca和和和和cbcb,则则则则ca*bca*b,这这这这表表表表明明明明a*ba*b是是是是a a和和和和b b的最大下界。的最大下界。的最大下界。的最
7、大下界。aaaa b b和和和和baba b b,则则则则表表表表明明明明a a b b是是是是a a和和和和b b的的的的上界。上界。上界。上界。若若若若acac,且且且且bcbc,则则则则a a bcbc,这这这这表表表表明明明明a a b b是是是是a a和和和和b b的最小上界。的最小上界。的最小上界。的最小上界。第5页,本讲稿共70页定理定理定理定理9.1.19.1.1 设设设设是格,对任意是格,对任意是格,对任意是格,对任意a,ba,b L L,有有有有 a a b=bb=babab a*b=a a*b=aabab a*b=a a*b=aa a b=bb=b亦即亦即亦即亦即 aba
8、ba a b=bb=ba*b=aa*b=a第6页,本讲稿共70页定定定定理理理理9.1.29.1.2 设设设设是是是是格格格格,对对对对任任任任意意意意a,ba,b L L,有有有有 a*b=a,aa*b=a,a a=aa=a。(幂等律)(幂等律)(幂等律)(幂等律)a*b=b*a,aa*b=b*a,a b=bb=b a a。(交换律)(交换律)(交换律)(交换律)a*(b*c)=(a*b)*ca*(b*c)=(a*b)*ca a (b(b c)=(ac)=(a b)b)c c (结合律)(结合律)(结合律)(结合律)a*(aa*(a b)=ab)=aa a (a*b)=a (a*b)=a (
9、吸收律)(吸收律)(吸收律)(吸收律)第7页,本讲稿共70页定定定定理理理理9.1.39.1.3 设设设设是是是是格格格格,对对对对任任任任意意意意a,b,ca,b,c L L,有,有,有,有若若若若abab和和和和cdcd,则,则,则,则a*cb*da*cb*d,a a cbcb d d。若若若若abab,则,则,则,则a*cb*ca*cb*c,a a cbcb c c。caca和和和和cb ca*bcb ca*bacac和和和和bc abc a bcbc第8页,本讲稿共70页定定定定 理理理理 9.1.49.1.4 设设设设 是是是是 格格格格,对对对对 任任任任 意意意意 的的的的a,b
10、,ca,b,c L L,有,有,有,有a a (b*c)(a(b*c)(a b)*(ab)*(a c)c)(a*b)(a*b)(a*c)a*(b(a*c)a*(b c)c)通常称上二式为格中分配不等式。通常称上二式为格中分配不等式。通常称上二式为格中分配不等式。通常称上二式为格中分配不等式。第9页,本讲稿共70页定定定定 理理理理 9.1.59.1.5 设设设设 是是是是 格格格格,对对对对 任任任任 意意意意 的的的的a,b,ca,b,c L L,有,有,有,有acaca a (b*c)(a(b*c)(a b)*cb)*c推推推推论论论论:在在在在格格格格中中中中,对对对对任任任任意意意意的
11、的的的a,b,ca,b,c L L,有有有有(a*b)(a*b)(a*c)a*(b(a*c)a*(b (a*c)(a*c)a a (b*(a(b*(a c)(ac)(a b)*(ab)*(a c)c)第10页,本讲稿共70页3特殊的格定定定定义义义义9.1.39.1.3 设设设设是是是是格格格格,若若若若L L中中中中有有有有最最最最大大大大元元元元和和和和最最最最小小小小元元元元,则则则则称称称称为为为为有有有有界界界界格格格格。一一一一般般般般把把把把格格格格中中中中最最最最大元记为大元记为大元记为大元记为1 1,最小元记为,最小元记为,最小元记为,最小元记为0 0。由定义可知,对任意由定
12、义可知,对任意由定义可知,对任意由定义可知,对任意a a L L,有,有,有,有0a10a1a*0=0,aa*0=0,a 0=a0=aa*1=a,aa*1=a,a 1=11=1第11页,本讲稿共70页定理定理9.1.6 设设设设是有限格,其中是有限格,其中是有限格,其中是有限格,其中L=a1 1,a,a2,an ,则,则是有界格。是有界格。第12页,本讲稿共70页定义定义定义定义9.1.49.1.4 设设设设是有界格,对于是有界格,对于是有界格,对于是有界格,对于a a L L,存在存在存在存在b b L L,使得,使得,使得,使得a*b=0a*b=0,a a b=1b=1称称称称b b为为为
13、为a a的补元,记为的补元,记为的补元,记为的补元,记为aa。由定义可知,若由定义可知,若由定义可知,若由定义可知,若b b是是是是a a的补元,则的补元,则的补元,则的补元,则a a也是也是也是也是b b的的的的补元,即补元,即补元,即补元,即a a与与与与b b互为补元。互为补元。互为补元。互为补元。显然,显然,显然,显然,0=10=1和和和和1=01=0,且易证补元是唯一的。,且易证补元是唯一的。,且易证补元是唯一的。,且易证补元是唯一的。一般说来,一个元素可以有其补元,未必一般说来,一个元素可以有其补元,未必一般说来,一个元素可以有其补元,未必一般说来,一个元素可以有其补元,未必唯一,
14、也可能无补元。唯一,也可能无补元。唯一,也可能无补元。唯一,也可能无补元。第13页,本讲稿共70页定定定定 义义义义 9.1.59.1.5 设设设设 是是是是 格格格格,对对对对 任任任任 意意意意 的的的的a,b,ca,b,c L L,有,有,有,有 a*(ba*(b c)=(a*b)c)=(a*b)(a*c)(a*c)a a (b*c)=(a(b*c)=(a b)*(ab)*(a c)c)则则则则称称称称为为为为分分分分配配配配格格格格,称称称称和和和和为为为为格格格格中中中中分分分分配配配配律。律。律。律。第14页,本讲稿共70页定义定义定义定义9.1.69.1.6 设设设设是格,对任意
15、的是格,对任意的是格,对任意的是格,对任意的a,b,ca,b,c L L,有,有,有,有acaca a (b*c)=(a(b*c)=(a b)*cb)*c称称称称为模格。为模格。为模格。为模格。定理定理定理定理9.1.79.1.7 分配格是模格分配格是模格分配格是模格分配格是模格定理定理定理定理9.1.89.1.8 每个链都是分配格。每个链都是分配格。每个链都是分配格。每个链都是分配格。第15页,本讲稿共70页定定定定理理理理9.1.99.1.9 一一一一个个个个格格格格为为为为分分分分配配配配格格格格,当当当当且且且且仅仅仅仅当当当当它它它它不不不不含有任何子格与这两个五元素格中任一个同构。
16、含有任何子格与这两个五元素格中任一个同构。含有任何子格与这两个五元素格中任一个同构。含有任何子格与这两个五元素格中任一个同构。定定定定理理理理9.1.109.1.10 设设设设是是是是分分分分配配配配格格格格,对对对对任任任任意意意意a,b,ca,b,c L L,有,有,有,有(a*b=a*c)(a*b=a*c)且且且且(a(a b=ab=a c)c)b=cb=c定定定定理理理理9.1.119.1.11 设设设设是是是是有有有有界界界界分分分分配配配配格格格格,若若若若a a L L,且补元存在,则其补元是唯一的。,且补元存在,则其补元是唯一的。,且补元存在,则其补元是唯一的。,且补元存在,则
17、其补元是唯一的。第16页,本讲稿共70页定定定定义义义义9.1.79.1.7 设设设设是是是是格格格格,若若若若L L中中中中每每每每个个个个元元元元素素素素至少有一补元,则称至少有一补元,则称至少有一补元,则称至少有一补元,则称为有补格。为有补格。为有补格。为有补格。由由由由于于于于补补补补元元元元的的的的定定定定义义义义是是是是在在在在有有有有界界界界格格格格中中中中给给给给出出出出的的的的,可可可可知,有补格一定是有界格。知,有补格一定是有界格。知,有补格一定是有界格。知,有补格一定是有界格。定定定定义义义义9.1.89.1.8 若若若若一一一一格格格格既既既既是是是是有有有有补补补补又
18、又又又是是是是分分分分配配配配的的的的,则则则则称该格为有补分配格,或布尔格,或布尔代数。称该格为有补分配格,或布尔格,或布尔代数。称该格为有补分配格,或布尔格,或布尔代数。称该格为有补分配格,或布尔格,或布尔代数。第17页,本讲稿共70页定定定定理理理理9.1.129.1.12 设设设设是是是是有有有有补补补补分分分分配配配配格格格格,若若若若任任任任意意意意元素元素元素元素a a L L,则,则,则,则a a的补元的补元的补元的补元aa是唯一的。是唯一的。是唯一的。是唯一的。该该该该定定定定理理理理9.1.119.1.11的的的的直直直直接接接接推推推推论论论论,因因因因为为为为有有有有补
19、补补补分分分分配配配配格格格格当然是有界分配格。当然是有界分配格。当然是有界分配格。当然是有界分配格。由由由由于于于于有有有有补补补补分分分分配配配配格格格格中中中中,每每每每个个个个元元元元素素素素a a都都都都有有有有唯唯唯唯一一一一的的的的补补补补元元元元aa,因因因因此此此此可可可可在在在在L L上上上上定定定定义义义义一一一一个个个个一一一一元元元元运运运运算算算算补补补补运运运运算算算算“”“”。这这这这样样样样,有有有有补补补补分分分分配配配配格格格格可可可可看看看看作作作作具具具具有有有有两两两两个个个个二二二二元元元元运运运运算算算算和和和和一一一一个个个个一一一一元元元元运
20、运运运算算算算的的的的代代代代数数数数结结结结构构构构,习习习习惯惯惯惯上上上上称它为布尔代数,记为称它为布尔代数,记为称它为布尔代数,记为称它为布尔代数,记为B,*,0,1,其中,其中,其中,其中B=LB=L。第18页,本讲稿共70页定理定理定理定理9.1.139.1.13 设设设设是有补分配格,对任意是有补分配格,对任意是有补分配格,对任意是有补分配格,对任意a,ba,b L L,则,则,则,则 (a)=a(a)=a(a*b)=a(a*b)=a bb(a(a b)=a*bb)=a*b后两式称为格中德后两式称为格中德后两式称为格中德后两式称为格中德 摩根律。摩根律。摩根律。摩根律。第19页,
21、本讲稿共70页定定定定理理理理9.1.149.1.14 设设设设是是是是有有有有补补补补分分分分配配配配格格格格,对对对对任任任任意意意意a,ba,b L L,有,有,有,有ababa*b=0a*b=0aa b=1b=1格格格格同同同同态态态态,格格格格直直直直积积积积等等等等概概概概念念念念可可可可以以以以接接接接下下下下来来来来定定定定义义义义和和和和研研研研究究究究,但但但但这这这这里里里里不不不不打打打打算算算算这这这这样样样样做做做做,因因因因为为为为如如如如此此此此进进进进行行行行会会会会相相相相对对对对较较较较繁繁繁繁,而而而而是是是是将将将将格格格格作作作作为为为为一一一一个个
22、个个代代代代数数数数结结结结构构构构而而而而引引引引入入入入它们。它们。它们。它们。第20页,本讲稿共70页4格是代数结构能能能能自自自自然然然然地地地地把把把把代代代代数数数数结结结结构构构构中中中中有有有有关关关关子子子子代代代代数数数数、同同同同态态态态、积代数等概念,引入到格中。积代数等概念,引入到格中。积代数等概念,引入到格中。积代数等概念,引入到格中。定定定定义义义义9.1.99.1.9 设设设设L,*是是是是一一一一代代代代数数数数结结结结构构构构,其其其其中中中中 和和和和*是是是是L L上上上上满满满满足足足足交交交交换换换换律律律律、结结结结合合合合律律律律和和和和吸吸吸吸
23、收收收收律律律律的的的的二二二二元运算,且对任意元运算,且对任意元运算,且对任意元运算,且对任意a,ba,b L L,定义关系,定义关系,定义关系,定义关系 如下:如下:如下:如下:ababa*b=aa*b=a则则则则 是是是是 格格格格,称称称称 为为为为 代代代代 数数数数 系系系系 统统统统L,*所诱导的偏序集确立的格。所诱导的偏序集确立的格。所诱导的偏序集确立的格。所诱导的偏序集确立的格。第21页,本讲稿共70页定定定定 义义义义 9.1.109.1.10 设设设设 L,*和和和和 S,是是是是 格格格格。存在函数存在函数存在函数存在函数f:Lf:LS S,若对任意,若对任意,若对任意
24、,若对任意a,ba,b L L,有,有,有,有f(af(a b)=f(a)b)=f(a)f(b)f(b),f(a*b)=f(a)f(a*b)=f(a)f(b)f(b)则称则称则称则称f f是从是从是从是从L,*到到到到S,的格同态。的格同态。的格同态。的格同态。下述定理说明格同态是保序的。下述定理说明格同态是保序的。下述定理说明格同态是保序的。下述定理说明格同态是保序的。定定定定理理理理9.1.159.1.15 设设设设L,*和和和和S,是是是是格格格格,而而而而L,和和和和分分分分别别别别是是是是给给给给定定定定两两两两个个个个格格格格所所所所诱诱诱诱导导导导的的的的偏偏偏偏序序序序集集集集
25、确确确确立立立立的的的的格格格格。若若若若f:Lf:LS S是是是是格格格格同同同同态态态态,则则则则对对对对任任任任意意意意a,ba,b L L,且,且,且,且abab,必有,必有,必有,必有f(a)f(b)f(a)f(b)。第22页,本讲稿共70页在在在在定定定定义义义义9.1.109.1.10中中中中,若若若若f f是是是是双双双双射射射射函函函函数数数数,则则则则称称称称f f是是是是格格格格同同同同构构构构。或或或或称称称称L,*和和和和S,两两两两个个个个格格格格同同同同构构构构。由由由由于于于于同同同同构构构构是是是是相相相相互互互互的的的的,又又又又是是是是保保保保序序序序的的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 09 布尔 代数 优秀 课件
限制150内