《格与布尔代数》ppt课件

《《格与布尔代数》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章格与布尔代数10.1格的定义与性质1.定义与群，环，域，不同，格与布尔代数的基集都是一个偏序集，格是具有两个二元运算的代数系统，是一个特殊的偏序集，布尔代数是一个特殊的格。定义10.1：设是偏序集，若都有上下确界，则称为格(Lattice)(1)偏序集的任一子集并非都有上下确界，(2)偏序集的某一子集的上下确界若存在，则唯一，格的定义确定了上下确界的存在性，(3){x,y}的上确界记为x∨y，下确界记为x∧y10.1格的定义与性质定义10.2：设f是含有格中元素及符号=,≤,≥,∨,∧的命题，令是将

2、f中≤,≥,∨,∧分别替换为≥,≤,∧,∨所得到的命题，则称是f的对偶命题或称对偶式。格的对偶原理：若f对一切格为真，则也对一切格为真。例：定理10.1：设是格，则运算∨,∧满足交换律，结合律，幂等律，吸收律，即10.1格的定义与性质10.1格的定义与性质由定理10.1知，格的两个运算满足交换律，结合律，幂等律，因此可以考虑用带有这4条性质的2个二元运算∨,∧，来像群，环，域，一样定义格，即用来定义格，可以证明这是可行的。定理10.2：设是具有二个二元运算的代数系统，且*,ο运算满足交换

3、律，结合律，吸收律，则可以适当定义S中的偏序≤，使得构成一个格，10.1格的定义与性质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：设代数系统

4、*,ο>是一个格，，若S满足：，则称是的子格。定义10.5：设是一个格，，若S满足：，则称是的子格。例10-1：(1)设是一个格，其中L={a,b,c,d,e}，其哈斯图如右图。baecd10.2子格与格同态2.格同态定义10.6：设和是格，，若有，则称为格到的同态映射，简称格同态，若是双射，则称为格同构。定义10.7：设和是格，其中分别为格上的偏序关系，存在映射，若，称f是序同态，若f是双射，则称f是序同构。(格同态定理)定理10.4：(1)设是格到格的同

5、态，则是序同态，即同态是保序的，即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：设

6、是格，若，有则称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特殊

7、格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):并非有界格的每个元素都有补元，而有补元也不一定唯一

8、；(3):0，1互为补元，且唯一。10.3特殊格定理10.10：设是有界分配格，若且对于a存在补元b，则b是a的唯一补元。定义10.14：设是有界格，若在L中都有a的补元存在，则称L是有补格。10.4布尔代数1.概念定义10.15：如果一个格是有补分配格，则称它为布尔代数。有补格保证每个元