十章节格与布尔代数

《十章节格与布尔代数》由会员分享，可在线阅读，更多相关《十章节格与布尔代数（42页珍藏版）》请在金锄头文库上搜索。

1、1/73第十章第十章 格与布尔代数格与布尔代数10.1 10.1 格的定义与性质格的定义与性质1.1.定义定义与群，环，域，不同，格与布尔代数的基集都是一与群，环，域，不同，格与布尔代数的基集都是一个偏序集，格是具有两个二元运算的代数系统，个偏序集，格是具有两个二元运算的代数系统，是一个特殊的偏序集，布尔代数是一个特殊的格。是一个特殊的偏序集，布尔代数是一个特殊的格。定义定义10.110.1：设设是偏序集，若是偏序集，若都有上下确界，则称都有上下确界，则称为格为格(Lattice)(Lattice)(1)(1)偏序集的任一子集并非都有上下确界，偏序集的任一子集并非都有上下确界，(2)(2)偏序

2、集的某一子集的上下确界若存在，则唯一，偏序集的某一子集的上下确界若存在，则唯一，格的定义确定了上下确界的存在性，格的定义确定了上下确界的存在性，(3)x, y(3)x, y的上确界记为的上确界记为xyxy，下确界记为，下确界记为xyxy2/7310.1 格的定义与性质格的定义与性质定义定义10.210.2：设设f f是含有格中元素及符号是含有格中元素及符号=, , =, , , , 的命题，令的命题，令 是将是将f f中中, , , , 分别分别替换为替换为, , ,所得到的命题，则称所得到的命题，则称 是是f f的对偶命题或称对偶式。的对偶命题或称对偶式。格的对偶原理：若格的对偶原理：若f

3、f对一切格为真，则对一切格为真，则 也对一切也对一切格为真。格为真。例：例：定理定理10.110.1：设设是格，则运算是格，则运算, , 满足交满足交换律，结合律，幂等律，吸收律，即换律，结合律，幂等律，吸收律，即3/7310.1 格的定义与性质格的定义与性质4/7310.1 格的定义与性质格的定义与性质由定理由定理10.110.1知，格的两个运算满足交换律，结合知，格的两个运算满足交换律，结合律，幂等律，因此可以考虑用带有这律，幂等律，因此可以考虑用带有这4 4条性质的条性质的2 2个二元运算个二元运算, , ，来像群，环，域，一样定义，来像群，环，域，一样定义格，即用格，即用来定义格，可以

4、证明这是来定义格，可以证明这是可行的。可行的。定理定理10.210.2：设设S,*, 是具有二个二元运算的代数是具有二个二元运算的代数系统，且系统，且*,*,运算满足交换律，结合律，吸收律，运算满足交换律，结合律，吸收律，则可以适当定义则可以适当定义S S中的偏序中的偏序，使得，使得构成一构成一个格，个格，5/7310.1 格的定义与性质格的定义与性质6/7310.1 格的定义与性质格的定义与性质7/7310.1 格的定义与性质格的定义与性质由定理由定理10.1,10.210.1,10.2可知：可知：8/7310.1 格的定义与性质格的定义与性质因此，根据定理因此，根据定理10.110.1，1

5、0.210.2，可以用代数系统的方，可以用代数系统的方式来定义格。式来定义格。定义定义10.310.3：设设S,*, 是代数系统，是代数系统， *, *,是二元是二元运算且满足交换律，结合律，吸收律运算且满足交换律，结合律，吸收律( (幂等律幂等律) )，则则S,*, 构成一个格。构成一个格。2.2.性质性质定理定理10.310.3：设设是格，则是格，则 ，有，有9/7310.1 格的定义与性质格的定义与性质10/7310.1 格的定义与性质格的定义与性质11/7310.2 子格与格同态子格与格同态1.1.子格子格定义定义10.410.4：设代数系统设代数系统L,*, 是一个格，是一个格， ，

6、若若S S满足：满足： ，则称，则称S,*, 是是L,*, 的子格。的子格。定义定义10.510.5：设设是一个格，是一个格， ，若，若S S满足：满足： ，则称，则称是是的子格。的子格。例例10-110-1：(1)(1)设设是一个格，其中是一个格，其中L=a,b,c,d,eL=a,b,c,d,e，其哈斯图如右图。，其哈斯图如右图。b b b ba a a ae e e ec c c cd d d d12/7310.2 子格与格同态子格与格同态2.2.格同态格同态定义定义10.610.6：设设 和和 是格，是格， ，若，若 有有 ，则称，则称 为格为格 到到 的同态映射，简称格同态，的同态映射

7、，简称格同态，若若 是双射，则称是双射，则称 为格同构。为格同构。定义定义10.710.7：设设 和和 是格，其中是格，其中 分别为格分别为格 上上的偏序关系，存在映射的偏序关系，存在映射 ，若，若 ，称，称f f是序同态，若是序同态，若f f是双射，则称是双射，则称f f是序同构。是序同构。( (格同态定理格同态定理) )定理定理10.410.4：(1)(1)设设 是格是格 到格到格 的同态，则的同态，则 是序同态，即同态是偏序的，即是序同态，即同态是偏序的，即13/7310.2 子格与格同态子格与格同态(2) (2) 是双射，则是双射，则 是是 到到 的同构的充的同构的充要条件是要条件是1

8、4/7310.2 子格与格同态子格与格同态例例10-210-2：在同构意义下：具有在同构意义下：具有1 1，2 2，3 3个元素的格个元素的格分别同构于元素个数相同的链，分别同构于元素个数相同的链，4 4个元素的格必同个元素的格必同构于下图构于下图4 4元素格之一，元素格之一，5 5个元素的格必同构于下个元素的格必同构于下图图5 5元素格之一元素格之一(2)(2)(2)(2)(3)(3)(3)(3)(4)(4)(4)(4)(5)(5)(5)(5)(6)(6)(6)(6)(7)(7)(7)(7)五角格五角格五角格五角格(9)(9)(9)(9)(8)(8)(8)(8)钻石格钻石格钻石格钻石格(10

9、)(10)(10)(10)(1)(1)(1)(1)15/7310.2 子格与格同态子格与格同态定义定义10.810.8：设设 和和 是格，定义是格，定义 上的二元运上的二元运算算 ：对：对 ，有：，有： 则称则称 为为 和和 的直积。的直积。直积仍是格直积仍是格( (证明满足交换，结合，吸收律即可证明满足交换，结合，吸收律即可) )16/7310.3 特殊格特殊格1.1.分配格分配格一般来说，对格一般来说，对格 ，有，有 ，则，则定义定义10.910.9：设设 是格，若是格，若 ，有，有 则称则称L L为分配格。为分配格。例：例：(1)(1)(2)(2)是是是是是是是是非非非非是是是是17/7

10、310.3 特殊格特殊格定理定理10.510.5：L L是格，则是格，则L L是分配格是分配格LL中不含有与钻中不含有与钻石格或五角格同构的子格。石格或五角格同构的子格。推论：推论：(1)(1)小于五元的格都是分配格；小于五元的格都是分配格；(2)(2)任何一条任何一条链都是分配格。链都是分配格。( (分配格的性质分配格的性质) )定理定理10.610.6：若若L L是格，则是格，则L L是分配格是分配格当且仅当当且仅当18/7310.3 特殊格特殊格命题条件命题条件 同时成立，否则同时成立，否则不正确。不正确。反例：分配格反例：分配格 中：中：19/7310.3 特殊格特殊格2.2.模格模格

11、定义定义10.1010.10：设设 是格，若是格，若 ，有：，有： ( (模律模律) )，则称，则称 为为模格，也称为戴德全格。模格，也称为戴德全格。定理定理10.710.7：格格L L是模格的充要条件是它不含有同构是模格的充要条件是它不含有同构于五角格的子格。于五角格的子格。定理定理10.810.8：设设 为分配格，则为分配格，则 是模格是模格20/7310.3 特殊格特殊格3.3.有界格有界格定义定义10.1110.11：设设L L是格，若存在是格，若存在 ，使得，使得 ，有有 ，则称，则称a a为为L L的全下界，若存在的全下界，若存在 ，使得，使得 ，有，有 ，则称，则称b b为为L

12、L的全上界。的全上界。(1):(1):有限格有限格 一定是有界格，全下界一定是有界格，全下界 ，全上界，全上界 ；(2):(2):无限格可以为有界格，如无限格可以为有界格，如 全下界全下界 ，全上界，全上界B B；(3):(3):全上界，全下界唯一，分别记为全上界，全下界唯一，分别记为1 1和和0 0定义定义10.1210.12：设设L L是格，若是格，若L L存在全上界和全下界，存在全上界和全下界，则称则称L L为有界格，记为为有界格，记为21/7310.3 特殊格特殊格定理定理10.910.9：设设 为有界格，则为有界格，则 ，有有4.4.有补格有补格定义定义10.1310.13：设设 是

13、有界格，是有界格， ，若存，若存在在 ，使得，使得 且且 ，则称，则称b b是是a a的补的补元。元。补元的性质：补元的性质：(1):(1):补元素相互的；补元素相互的；(2):(2):并非有界并非有界格的每个元素都有补元，而有补元也不一定唯一；格的每个元素都有补元，而有补元也不一定唯一；(3):0(3):0，1 1互为补元，且唯一。互为补元，且唯一。22/7310.3 特殊格特殊格定理定理10.1010.10：设设 是有界分配格，若是有界分配格，若 且对于且对于a a存在补元存在补元b b，则，则b b是是a a的唯一补元。的唯一补元。定义定义10.1410.14：设设 是有界格，若是有界格

14、，若 在在L L中都有中都有a a的补元存在，则称的补元存在，则称L L是有补格。是有补格。23/7310.4 布尔代数布尔代数1.1.概念概念定义定义10.1510.15：如果一个格是有补分配格，则称它为如果一个格是有补分配格，则称它为布尔代数。布尔代数。有补格保证每个元素有补元，分配格保证每个元有补格保证每个元素有补元，分配格保证每个元素的补元的唯一性，因此，可将求补元看作是布素的补元的唯一性，因此，可将求补元看作是布尔代数的一元运算，即尔代数的一元运算，即例：例：定理定理10.1110.11：设设 是布尔代数，则是布尔代数，则24/7310.4 布尔代数布尔代数 布尔代数：交换律，结合律

15、，吸收律，分配律，布尔代数：交换律，结合律，吸收律，分配律，存在补元，可用交换律，分配律，同一律，补元存在补元，可用交换律，分配律，同一律，补元律代替。另一等价定义：律代替。另一等价定义：定义定义10.1610.16： 是代数系统，是代数系统， 是二元运算，是二元运算，且且 满足：满足：(1)(1)交换律，交换律，(2)(2)分配律，分配律，(3)(3)同一律：同一律：存在存在 (4) (4)补元律：补元律： 则称则称 是布尔代数。是布尔代数。25/7310.4 布尔代数布尔代数(1):(1):幺元为幺元为1 1；：幺元为：幺元为0(0(同一律同一律) )。可证：。可证： :零元为零元为0 0

16、；：零元为：零元为1 1。(2):(2):吸收律成立。吸收律成立。结合律成立。结合律成立。26/7310.4 布尔代数布尔代数2.2.子布尔代数子布尔代数定义定义10.1710.17：设设 是布尔代数，是布尔代数， ，若若 ，且，且S S对对，封闭，则称封闭，则称S S是是B B的子的子布尔代数。布尔代数。例：例：(1)(1)对任何布尔代数对任何布尔代数 恒有子布尔代恒有子布尔代数数 和和 均为均为B B的平凡布的平凡布尔代数。尔代数。27/7310.4 布尔代数布尔代数(2)(2)定理定理10.12(10.12(判定定理判定定理) )：设设 是布尔代是布尔代数，数， ，若，若 ，则则S S是

17、是B B的子布尔代数，记作的子布尔代数，记作1 1 1 1f f f fd d d de e e ec c c cb b b ba a a a0 0 0 028/7310.4 布尔代数布尔代数3.3.布尔代数的同态布尔代数的同态定义定义10.1810.18：设设 和和 是是两个布尔代数，两个布尔代数， ，若，若 ，有：，有： 则称则称 为为 到到 的布尔同态，若的布尔同态，若 为双射，则为布为双射，则为布尔同构。尔同构。4.4.有限布尔代数的结构有限布尔代数的结构定义定义10.1910.19：设设L L是格，若是格，若a a是是0 0的覆盖，则称的覆盖，则称a a是是L L中中的原子，即：的原

18、子，即：定理定理10.1310.13：设设 是布尔代数，是布尔代数，B B中元素中元素a a是原子的充要条件是是原子的充要条件是a0a0，且对，且对 ，有：，有： 29/7310.4 布尔代数布尔代数定理定理10.1410.14：设设L L是格，是格，a a，b b是是L L中的原子，若中的原子，若abab，则，则ab=0ab=0。定理定理10.1510.15：设设B B是有限布尔代数，是有限布尔代数， ，令，令 是是B B中所有中所有xx的原子构成的集合的原子构成的集合( ( ) )，则：，则：30/7310.4 布尔代数布尔代数31/7310.4 布尔代数布尔代数32/7310.4 布尔代

19、数布尔代数定理定理10.16(10.16(有限布尔代数的表示定理有限布尔代数的表示定理) )：设设 是有限布尔代数，是有限布尔代数，A=a|aBA=a|aB且且a a是原是原子子 ，则，则33/7310.4 布尔代数布尔代数34/7310.4 布尔代数布尔代数推论推论1 1：任何有限布尔代数的基数为任何有限布尔代数的基数为推论推论2 2：任何具有任何具有 个元素的布尔代数互相同构个元素的布尔代数互相同构( (对对无限布尔代数不成立无限布尔代数不成立) )35/7310.4 布尔代数布尔代数5.5.布尔表达式布尔表达式定义定义10.2010.20：设设 是一个布尔代数，是一个布尔代数，B B中中

20、的元素称为布尔常元，取值于的元素称为布尔常元，取值于B B中元素的变元称为中元素的变元称为布尔变元。布尔变元。定义定义10.2110.21：设设 是一个布尔代数，在是一个布尔代数，在B B上的布尔表达式定义如下：上的布尔表达式定义如下：(1).B(1).B中任何一个常元是布尔表达式；中任何一个常元是布尔表达式；(2).B(2).B中任何一个布尔变元是布尔表达式；中任何一个布尔变元是布尔表达式；(3).(3).如果如果 是布尔表达式，则是布尔表达式，则 也是也是布尔表达式；布尔表达式；(4).(4).有限次使用有限次使用(1)(1)，(2)(2)，(3)(3)所构造的符号串是布所构造的符号串是布

21、尔表达式。尔表达式。36/7310.4 布尔代数布尔代数定义定义10.2210.22：设设 是一个布尔代数，是一个布尔代数，B B的的一个含有一个含有n n个相异布尔变元的布尔表达式称为个相异布尔变元的布尔表达式称为n n元元布尔表达式，记为布尔表达式，记为 ，其中，其中 是布尔变元。是布尔变元。定义定义10.2310.23：设设 和和 是是布尔代数布尔代数 上的两个布尔表达式，如上的两个布尔表达式，如果对果对n n个布尔变元的任意指派，个布尔变元的任意指派， 和和 的值均相等，的值均相等，则称则称 与与 是等价的或相等的，记作：是等价的或相等的，记作：(1).(1).如果能有限次应用布尔代数

22、的公式，将一个如果能有限次应用布尔代数的公式，将一个布尔表达式化成另一个布尔表达式，就可判定两布尔表达式化成另一个布尔表达式，就可判定两式是等价的；式是等价的；37/7310.4 布尔代数布尔代数(2).(2).等价关系将等价关系将n n元布尔表达式集合划分成等价类，元布尔表达式集合划分成等价类，同一等价类中的布尔表达式等价，等价类数目有同一等价类中的布尔表达式等价，等价类数目有限。限。定义定义10.2410.24：设设 是布尔代数，给定是布尔代数，给定n n个个布尔变元布尔变元 ，表达式：，表达式： ( ) ( )，称为极小项。，称为极小项。(1).n(1).n个布尔变元就有个布尔变元就有

23、个不同的极小项，分别记个不同的极小项，分别记为为 ，下标识二进制数，下标识二进制数， 的十进制表示，其中的十进制表示，其中 38/7310.4 布尔代数布尔代数(2).(2).(3).(3).定义定义10.2510.25：设设 是布尔代数，如是布尔代数，如 的布尔表达式的布尔表达式称为主析取范式，其中称为主析取范式，其中 是布尔常元，是布尔常元， 是极小是极小项项( ).( ).(1).(1).每个每个 有有|B|B|种取法，故有种取法，故有n n个布尔变元的不个布尔变元的不同的主析取范式有同的主析取范式有 个，当个，当B=0,1B=0,1时有时有 个个; ;(2). (2). 个极小项，最多

24、能构造出个极小项，最多能构造出 个主析取范个主析取范式，所以一个式，所以一个n n元布尔表达式必等价于这元布尔表达式必等价于这 个主个主析取范式之一；析取范式之一；(3).(3).可用数理逻辑中的方法，用德摩根律等将一可用数理逻辑中的方法，用德摩根律等将一39/7310.4 布尔代数布尔代数个个n n元布尔表达式转化为等价的主析取范式；元布尔表达式转化为等价的主析取范式；(4).(4).相应的：极大项：相应的：极大项：主合取范式为：主合取范式为： 是布尔常元，是布尔常元， 是极大项，同样有是极大项，同样有 个不同的个不同的主合取范式，主合取范式， 个极大项最多能构造个极大项最多能构造 个不同个

25、不同的主合取范式。的主合取范式。例：将布尔代数例：将布尔代数 上的布尔表达上的布尔表达式式40/7310.4 布尔代数布尔代数41/7310.4 布尔代数布尔代数定义定义10.2610.26：设设 是一个格，一个从是一个格，一个从 到到B B的函数，如果能够用该布尔代数上的布尔表达式，的函数，如果能够用该布尔代数上的布尔表达式，则称这个函数为布尔代数。则称这个函数为布尔代数。(1).(1).每一个每一个n n元布尔表达式可以看作是一个元布尔表达式可以看作是一个n n个布个布尔变元的函数；尔变元的函数；(2).n(2).n个变元的主析取范式最多有个变元的主析取范式最多有 个，个，不能不能代表代表

26、 个不同的函数，个不同的函数， 到到|B|B|的函数共有的函数共有 个；个；当当B=0,1B=0,1时，函数有时，函数有 个，主析取范式个，主析取范式 个，每个，每个函数均可用布尔表达式表示，当个函数均可用布尔表达式表示，当B0,1B0,1时，时，如如B=0,1,a,bB=0,1,a,b时，函数有时，函数有 个，主析取范式有个，主析取范式有 个，即当个，即当|B|2|B|2时，有些时，有些 到到B B的函数不能用布尔的函数不能用布尔表达式表示。表达式表示。42/7310.4 布尔代数布尔代数(3).(3).命题逻辑可以用布尔代数命题逻辑可以用布尔代数 来描述，开关代数可以用布尔代数来描述，开关代数可以用布尔代数 来描述。来描述。