chapter5 格与布尔代数

《chapter5 格与布尔代数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章格与布尔代数(Chapter5LatticeandBooleanAlgebra)第一节格的定义与性质(Section1Definition&PropertiesofLattice)内容：格，格的性质重点：格的有关概念、性质及例子2021/9/15偏序格efabdcabcd(a)(b)比较右边两个哈斯图的不同？图(b)中任意2个元素都有最小上界和最大下界图(a)中e,f两个元素没有最小上界;a,b没有最大下界一、格的概念定义：设是偏序集，如果对，都有最小上界(记)和最大下界(记)，则称关于构成一个格。格也记作。例1、设为正整数，表示的所有正因子的集合，

2、表示整除关系，则构成格。的最小公倍数的最大公约数如：，下图给出了格，，，下图给出了格，，，例2、判断下列偏序集是否构成格，并说明理由。（1），其中P(B)是集合B的幂集。（2），其中Z是整数集，≤是小于或等于关系。解：（1）是格。，，由于和运算在P(B)上是封闭的，所以称为B的幂集格。（2）是格。，它们都是整数。例3、判断下图中的偏序集是否构成格，并说明理由。(4)dabcefg例4、设G是群，L(G)是G的所有子群的集合，即L(G)={H

3、H≤G}二、格的性质1、对偶原理：设是含有格中的元素以及符号的命题，令

4、是将中的分别改写成所得到的命题，称为切格为真。也对一对一切格为真，则的对偶命题。若说明：的哈斯图只要将的哈斯图翻转，上变下，下变上即可．因此最小上界变为最大下界，最大下界变为最小上界．最大元变最小元，最小元变最大元．例：L={1,2,3,6},≤是整除关系，≥是因子关系在中23=6,在中23=6在中有(13)2≤2，所以(13)2≥2二、格的性质二、格的性质2、性质：设为格，则运算和适合交换律，结合律，幂等律和吸收律，即，有(1)交换律，(2)结合律，二、格的性质2、性质：设为格，则运算和适合交

5、换律，结合律，幂等律和吸收律，即，有(3)幂等律，(4)吸收律，1、格的代数定义的引理三、格的代数定义2、格的代数定义的定理三、格的代数定义定理的证明定理的证明（续）定理的证明（续）三、格的代数定义注意：偏序格与代数格等价，今后就不再区分偏序格与代数格了，而把它们统称为格。二、格的性质（续）格中不等式的证明不满足分配律的格第二节子格与格同态(Section2Sub-lattice&LatticeHomomorphism)内容：子格，格同态重点：子格的定义及判定，格的同态了解：格的直积2021/9/15一、子格(Sub-lattice)1、定义：设代数系统<

6、L,,>是一个格，SL，若S满足：（1）S≠；（2）S关于运算和仍然构成格；则称是的子格，简称S是L的子格。2021/9/15一、子格(Sub-lattice)2、实例：例1：在正整数集合Z+中规定、为：对任意a,b∈P，ab=(a,b)，其中(a,b)表示a,b的最大公因数ab=[a,b]，其中[a,b]表示a,b的最小公倍数则、是Z+上的二元运算，且满足交换律、结合律、吸收律和等幂律，于是是一个格。S={3k

7、k∈Z+}，试证明是的子格。2021/9/15

8、证明：显然S≠。因为对任意3m,3n∈S，都有3m3n=[3m,3n]=3[m,n]∈S，3m3n=(3m,3n)=3(m,n)∈S所以，是的子格。2021/9/15例2：在如下图(a)所示的偏序格中，考虑如下子集：B1={a,b,g,h}，B2={a,b,c,d}，B3={a,b,c,h}，问B1，B2，B3中那些是的子格？habca(a)bdfhceg(b)一、子格(Sub-lattice)2、实例：2021/9/15分析显然B1，B2，B3都是L的非空子集，B1是L的子格；B2的2元素子集{b,

9、c}的最小上界e不在B2中，因此B2不是L的子格；B3的2元素子集{b,c}的最小上界e不在B3中，因此B3不是L的子格。注意，偏序集的哈斯图如上图(b)所示，因此是格。即存在子集关于偏序能构成格，但不是子格。解B1是L的子格，B2,B3都不是L的子格。例2：（续）一、子格(Sub-lattice)2、实例：2021/9/15设是一个格，a∈L，令S={x

10、x∈L,x≤a}，则S是L的子格。证明因为a≤a，所以a∈S，即S是非空子集。对任意x,y∈S，由x≤a，y≤a，可知xy=inf{x,y}≤a，即xy=inf{x

11、,y}∈Sxy=sup{x,y}≤a，即xy=sup{x,y}