十章节格与布尔代数讲课资料.ppt

,*,/73,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,/73,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第十章 格与布尔代数,10.1,格的定义与性质,1.,定义,与群，环，域，不同，格与布尔代数的基集都是一个偏序集，格是具有两个二元运算的代数系统，是一个特殊的偏序集，布尔代数是一个特殊的格。,定义,10.1,：,设,是偏序集，若,都有上下确界，则称,为格,(Lattice),(1),偏序集的任一子集并非都有上下确界，,(2),偏序集的某一子集的上下确界若存在，则唯一，格的定义确定了上下确界的存在性，,(3)x,y,的上确界记为,xy,，下确界记为,xy,10.1,格的定义与性质,定义,10.2,：,设,f,是含有格中元素及符号,=,的命题，令 是将,f,中,分别替换为,所得到的命题，则称 是,f,的对偶命题或称对偶式。,格的对偶原理：若,f,对一切格为真，则 也对一切格为真。,例：,定理,10.1,：,设,是格，则运算,满足交换律，结合律，幂等律，吸收律，即,10.1,格的定义与性质,10.1,格的定义与性质,由定理,10.1,知，格的两个运算满足交换律，结合律，幂等律，因此可以考虑用带有这,4,条性质的,2,个二元运算,，来像群，环，域，一样定义格，即用,来定义格，可以证明这是可行的。,定理,10.2,：,设,是具有二个二元运算的代数系统，且,*,运算满足交换律，结合律，吸收律，则可以适当定义,S,中的偏序，使得,构成一个格，,10.1,格的定义与性质,10.1,格的定义与性质,由定理,10.1,10.2,可知：,10.1,格的定义与性质,因此，根据定理,10.1,，,10.2,，可以用代数系统的方式来定义格。,定义,10.3,：,设,是代数系统，,*,是二元运算且满足交换律，结合律，吸收律,(,幂等律,),，则,构成一个格。,2.,性质,定理,10.3,：,设,是格，则 ，有,10.1,格的定义与性质,10.1,格的定义与性质,10.2,子格与格同态,1.,子格,定义,10.4,：,设代数系统,是一个格，若,S,满足：，则称,是,的子格。,定义,10.5,：,设,是一个格，若,S,满足：，则称,是,的子格。,例,10-1,：,(1),设,是一个格，其中,L=a,b,c,d,e,，其哈斯图如右图。,b,a,e,c,d,10.2,子格与格同态,2.,格同态,定义,10.6,：,设 和 是格，若 有 ，则称 为格 到 的同态映射，简称格同态，若 是双射，则称 为格同构。,定义,10.7,：,设 和 是格，其中 分别为格 上的偏序关系，存在映射 ，若 ，称,f,是序同态，若,f,是双射，则称,f,是序同构。,(,格同态定理,),定理,10.4,：,(1),设 是格 到格 的同态，则 是序同态，即同态是偏序的，即,10.2,子格与格同态,(2),是双射，则 是 到 的同构的充要条件是,10.2,子格与格同态,例,10-2,：,在同构意义下：具有,1,，,2,，,3,个元素的格分别同构于元素个数相同的链，,4,个元素的格必同构于下图,4,元素格之一，,5,个元素的格必同构于下图,5,元素格之一,(2),(3),(4),(5),(6),(7),五角格,(9),(8),钻石格,(10),(1),10.2,子格与格同态,定义,10.8,：,设 和 是格，定义 上的二元运算 ：对 ，有：,则称 为 和 的直积。,直积仍是格,(,证明满足交换，结合，吸收律即可,),10.3,特殊格,1.,分配格,一般来说，对格 ，有 ，则,定义,10.9,：,设 是格，若 ，有,则称,L,为分配格。,例：,(1),(2),是,是,非,是,10.3,特殊格,定理,10.5,：,L,是格，则,L,是分配格,L,中不含有与钻石格或五角格同构的子格。,推论：,(1),小于五元的格都是分配格；,(2),任何一条链都是分配格。,(,分配格的性质,),定理,10.6,：,若,L,是格，则,L,是分配格当且仅当,10.3,特殊格,命题条件 同时成立，否则不正确。,反例：分配格 中：,10.3,特殊格,2.,模格,定义,10.10,：,设 是格，若 ，有：,(,模律,),，则称 为模格，也称为戴德全格。,定理,10.7,：,格,L,是模格的充要条件是它不含有同构于五角格的子格。,定理,10.8,：,设 为分配格，则 是模格,10.3,特殊格,3.,有界格,定义,10.11,：,设,L,是格，若存在 ，使得 ，有 ，则称,a,为,L,的全下界，若存在 ，使得 ，有 ，则称,b,为,L,的全上界。,(1):,有限格 一定是有界格，全下界,，全上界 ；,(2):,无限格可以为有界格，如 全下界,，全上界,B,；,(3):,全上界，全下界唯一，分别记为,1,和,0,定义,10.12,：,设,L,是格，若,L,存在全上界和全下界，则称,L,为有界格，记为,10.3,特殊格,定理,10.9,：,设 为有界格，则 ，有,4.,有补格,定义,10.13,：,设 是有界格，若存在 ，使得 且 ，则称,b,是,a,的补元。,补元的性质：,(1):,补元素相互的；,(2):,并非有界格的每个元素都有补元，而有补元也不一定唯一；,(3):0,，,1,互为补元，且唯一。,10.3,特殊格,定理,10.10,：,设 是有界分配格，若,且对于,a,存在补元,b,，则,b,是,a,的唯一补元。,定义,10.14,：,设 是有界格，若,在,L,中都有,a,的补元存在，则称,L,是有补格。,10.4,布尔代数,1.,概念,定义,10.15,：,如果一个格是有补分配格，则称它为布尔代数。,有补格保证每个元素有补元，分配格保证每个元素的补元的唯一性，因此，可将求补元看作是布尔代数的一元运算，即,例：,定理,10.11,：,设 是布尔代数，则,10.4,布尔代数,布尔代数：交换律，结合律，吸收律，分配律，存在补元，可用交换律，分配律，同一律，补元律代替。另一等价定义：,定义,10.16,：,是代数系统，是二元运算，且 满足：,(1),交换律，,(2),分配律，,(3),同一律：存在,(4),补元律：,则称 是布尔代数。,10.4,布尔代数,(1):,幺元为,1,；,：幺元为,0(,同一律,),。可证：,:,零元为,0,；,：零元为,1,。,(2):,吸收律成立。,结合律成立。,10.4,布尔代数,2.,子布尔代数,定义,10.17,：,设 是布尔代数，若 ，且,S,对,，,，,封闭，则称,S,是,B,的子布尔代数。,例：,(1),对任何布尔代数 恒有子布尔代数 和 均为,B,的平凡布尔代数。,10.4,布尔代数,(2),定理,10.12(,判定定理,),：,设 是布尔代数，若 ，则,S,是,B,的子布尔代数，记作,1,f,d,e,c,b,a,0,10.4,布尔代数,3.,布尔代数的同态,定义,10.18,：,设 和 是两个布尔代数，若 ，有：,则称 为 到 的布尔同态，若 为双射，则为布尔同构。,4.,有限布尔代数的结构,定义,10.19,：,设,L,是格，若,a,是,0,的覆盖，则称,a,是,L,中的原子，即：,定理,10.13,：,设 是布尔代数，,B,中元素,a,是原子的充要条件是,a0,，且对 ，有：,10.4,布尔代数,定理,10.14,：,设,L,是格，,a,，,b,是,L,中的原子，若,ab,，则,ab=0,。,定理,10.15,：,设,B,是有限布尔代数，令 是,B,中所有,x,的原子构成的集合,(),，则：,10.4,布尔代数,10.4,布尔代数,10.4,布尔代数,定理,10.16(,有限布尔代数的表示定理,),：,设,是有限布尔代数，,A=a|aB,且,a,是原子,，则,10.4,布尔代数,10.4,布尔代数,推论,1,：,任何有限布尔代数的基数为,推论,2,：,任何具有 个元素的布尔代数互相同构,(,对无限布尔代数不成立,),10.4,布尔代数,5.,布尔表达式,定义,10.20,：,设 是一个布尔代数，,B,中的元素称为布尔常元，取值于,B,中元素的变元称为布尔变元。,定义,10.21,：,设 是一个布尔代数，在,B,上的布尔表达式定义如下：,(1).B,中任何一个常元是布尔表达式；,(2).B,中任何一个布尔变元是布尔表达式；,(3).,如果 是布尔表达式，则 也是布尔表达式；,(4).,有限次使用,(1),，,(2),，,(3),所构造的符号串是布尔表达式。,10.4,布尔代数,定义,10.22,：,设 是一个布尔代数，,B,的一个含有,n,个相异布尔变元的布尔表达式称为,n,元布尔表达式，记为 ，其中,是布尔变元。,定义,10.23,：,设 和 是布尔代数 上的两个布尔表达式，如果对,n,个布尔变元的任意指派，和 的值均相等，则称 与 是等价的或相等的，记作：,(1).,如果能有限次应用布尔代数的公式，将一个布尔表达式化成另一个布尔表达式，就可判定两式是等价的；,10.4,布尔代数,(2).,等价关系将,n,元布尔表达式集合划分成等价类，同一等价类中的布尔表达式等价，等价类数目有限。,定义,10.24,：,设 是布尔代数，给定,n,个布尔变元 ，表达式：,(),，称为极小项。,(1).n,个布尔变元就有 个不同的极小项，分别记为 ，下标识二进制数，的十进制表示，其中,10.4,布尔代数,(2).,(3).,定义,10.25,：,设 是布尔代数，如,的布尔表达式称为主析取范式，其中 是布尔常元，是极小项,().,(1).,每个 有,|B|,种取法，故有,n,个布尔变元的不同的主析取范式有 个，当,B=0,1,时有 个,;,(2).,个极小项，最多能构造出 个主析取范式，所以一个,n,元布尔表达式必等价于这 个主析取范式之一；,(3).,可用数理逻辑中的方法，用德摩根律等将一,10.4,布尔代数,个,n,元布尔表达式转化为等价的主析取范式；,(4).,相应的：极大项：,主合取范式为：,是布尔常元，是极大项，同样有 个不同的主合取范式，个极大项最多能构造 个不同的主合取范式。,例：将布尔代数 上的布尔表达式,10.4,布尔代数,10.4,布尔代数,定义,10.26,：,设 是一个格，一个从 到,B,的函数，如果能够用该布尔代数上的布尔表达式，则称这个函数为布尔代数。,(1).,每一个,n,元布尔表达式可以看作是一个,n,个布尔变元的函数；,(2).n,个变元的主析取范式最多有 个，,不能代表 个不同的函数，到,|B|,的函数共有,个；,当,B=0,1,时，函数有 个，主析取范式 个，每个函数均可用布尔表达式表示，当,B0,1,时，如,B=0,1,a,b,时，函数有 个，主析取范式有 个，即当,|B|2,时，有些 到,B,的函数不能用布尔表达式表示。,10.4,布尔代数,(3).,命题逻辑可以用布尔代数 来描述，开关代数可以用布尔代数,来描述。,