第十三章格与布尔代数.ppt

1、第十三届章格和布尔代数，13.1格的定义和性质，1。格作为偏序集的定义，定义13.1让它成为偏序集。如果x，y，s，x和y都有一个最小上界和一个最大下界，那么s就称为偏序格。由于最小上界和最大下界的唯一性，我们可以把求x和y的最小上界和最大下界看作是x和y的二元运算和，即求xy和xy分别代表x和y的最小上界和最大下界。本章中出现的和符号仅代表格中的运算，没有其他含义。设n为正整数，Sn为n的一组正因子，D为可分关系，则偏序集构成格。x，ysn和xy是lcm(x，Y)，是x和Y的最小公倍数.Xy是gcd(x，Y)，是x和Y的最大公约数.图13.1给出了网格。例13.2判断下列偏序集是否构成格，并

2、解释原因。(1)，其中P(B)是集合B的幂集.解：是一个点阵。x，yP(B)，xy是xy，xy是xy。因为求和运算在P(B)、xy、xyP(B)上是闭合的。叫做B的幂集格.(2)，其中z是整数集，并且小于或等于关系。解：是一个点阵。x，yZ，xy=max(x，y)，xy=min(x，y)，所有这些都是整数。(3)图13.2给出了部分有序集的哈斯图。a，b没有最大下界，不是格，b，d有两个上界C和E，但没有最小上界，不是格，b，C有三个上界d，E，f，但没有最小上界。不是格，不是格，a，g没有最大下界。设G为一个群，L(G)为G的所有子群的集合，即L(G)=H|HG，且包含关系定义在L(G)上，

3、则L(G)形成一个关于包含关系的格，称为G的子群格.对于任何H1，H2L(G)，H1H2也是G的子群，但是由H1H2生成的子群(即，包含H1H2的最小子群)。很容易看出，H1H2，H1H2在L(G)中，H1H2是两个晶格的性质。定义13.2假设F是一个包含格中元素和符号=、和的命题。设f*是用，用，用，用替换得到的命题。格的对偶原理让F是一个包含格中元素和符号=、等的命题。如果f对于所有格都是真的，那么f的对偶命题f*对于所有格也是真的。例如，如果f是格中的(ab) c c，那么f*是(ab)c c，例如，如果所有格l都有a，bL，ab a，那么所有格l都有a，bL，ab a，并且许多格的性质

4、是对偶命题。利用格的对偶原理，证明格的性质时，只需证明其中一个命题。2。运算性质，定理13.1是格，那么运算和适用于交换律、结合律、幂等律和吸收律，即(1) a，b L有ab=ba，ab=ba，A，b，cL有(ab) C=A (BC)，(AB) C=A (BC)因为A，b=b，A，ab=ba。由对偶原理证明，ab=ba。(2)证明：(ab)c ab a，(ab)c ab b，(ab)c c由最小上界定义，(ab)c bc由和定义，(ab)c a(bc)由和定义，(ab)c a(bc)可以用同样的方法证明，(AB) C A (BC)是根据偏序关系的反对称发现的。(3)证书：很明显，a，a和a可以

5、从a获得。摘要：根据偏序关系的反对称，用对偶原理证明aa=a，aa=a. (4)证明：显然，a(ab) a可以由A和ab a得到，a(ab)=a可以由和得到，这是用对偶原理和A (AB)=A证明的，三格是代数系统的定义。定理13.2假设一个代数系统有两个二元运算。如果*和运算适用于交换律、结合律和吸收律，则S中的偏序可以适当地定义为格，A和BS具有ab=a*b，ab=a b。根据定理13.2，可以给出格的另一个等价定义。定义13.3让它成为一个代数系统，并且*和是二进制运算。如果*和满足交换定律、关联定律和吸收定律，它们将形成一个格。格中的运算满足四个算术定律，并且还有一个幂等定律(见定理13

6、.1)，但是幂等定律可以从吸收定律导出，因此在定义13.3中只需要满足三个算术定律。证明：(1)证明S中的*和运算适用于幂等律。aS，源自吸收定律，a*a=a*(a(a*a)=a，aa=a，方式相同。(2)定义s上的二元关系r，a，bs，Rab=b，并证明，a，b，cS有，aRb和bRcab=b和BC=c，AC=a (b c)，AC=(ab) c，AC=b c=c弧，证明了r在S上是可传递的.总而言之，r是s的偏序，写成。证明构成一个案件。a，bS有，a(a b)=a(a)B=a B，B(a B)=a B，所以a B是a和B的上界.如果c是a和b的上界，那么c=c，bc=c，因此，(a b)

7、c=a (bc)=a c=c，这证明了a b c，所以a b是a和b的最小上界，即ab=ab。为了证明a*b是a和b的最大下界，首先证明Ab=(a*b) b=b (b*a)=b，从ab=b a*b=a，可以证明a*b是a和b的最大下界，即ab=a*b，无论它是由偏序集定义的格还是由代数系统定义的格，都统称为格l， 定理11因为a a和a b知道A是A和B的下界，a ab，很明显是ab a，根据反对称关系得到ab=a，因为ab=a，ab=(ab) b=b，因为ab，也就是ab，定理13.4把L设定为格，那么A，B，C，DL，如果ab和c d，那么，Ac c d，因此，ac bd可以用同样的方法证

8、明。 在例13.4中，假设l是一个格，并证明a、b和cl有一个(bc) (ab) (ac)。证明了a a，bc b得到a (bc) ab，而a a，bc c得到a (bc) ac，所以a(BC)ab如果你不给出理由。不能形成晶格，可以形成晶格，可以形成晶格，2。找出下列命题的对偶命题。(1) (ab) b=b，(ab) b=b，(2) b (ca) (BC) a，b (ca) (BC) a，3。证明：(ab)(cd) (ac)(bd)，证明：ab a ac，ab b bd从而获得(ab)(cd) (ac)(bd)，方法2: so (cd) (ac)(bd)，so (ab) (ac)(bd)从定

9、理4中获得，并且c ac和d bd是相同的原因，从而获得(ab) (CD) (AC) (BD)。解决方案：S1不是L的子网格，对于E和F，ef=c，而是c S1。S2是L的一个子格，两格同态的定义及其性质，一格同态的定义，定义13.5设L1和L2是格，f: L1L2，如果a，bL1有f (ab)=f (a) f (b)例13.6 (1)设L1=2n|nZ，L2=2n1|nN，那么L1和L2之间的关系小于或等于通常的数形成一个格。为了证明对于任何x，yL1具有xy max (x，Y)，f (xy)=f (max (x，y)=max (x，y)-1，f(x)f(Y)=(x-1)(Y-1)=max(

10、x-1)Y)-1 f(x)f(Y)=(x-1)(y-1)=min (x-1，Y-1)=min(x，Y)-1，即f(xy)=f(x)f(y)，所以f是同态映射询问F1和F2是否同态。解：f1和f2不是格同态，f1(BC)=f1(d)=D1 f1(b)f1(c)=a1 a1=a1 f1(BC)f1(b)f1(c)，F2 (BC)=F2 (d)=d2f2 (b) F2 (c) Xyy从定理13.3可知，因为f是格同态映射，所以必须有f(y)f(xy)=f(x)f(y)，所以有f(x)f(y)。(2)证明：充分性：只需证明它是从L1到L2的同态映射。让x，y L1，让xy=z，已知x z和y z，(x

11、) (z)，(y) (z)，所以有，(x)(y) (z)=(xy)。另一方面，它可以从(x)(y)L2和的满射性中得知。因此，推导出xy u，然后，从已知的条件，(x)(y) (u)=(xy)，这可以用同样的理由来证明，(x)(y)=(xy)，必然性：(1)的结论必须是，xy (x) Xy=y，从而证明x y，例13.7，让L1和L2是格，其中S12是由12的所有正因子组成的集合，而d是一个可分的关系，它小于或等于正常数，所以f:s12，f (x)=x解：不是。因为f(2)=2 f(3)=3 f(2) f(3)，但是2不能精确地划分3或3格的直积，这类似于半群、群和环，并且还可以定义格的直积。

12、定义13.6假设L1和L2是格，定义L1L2，上的运算，L1L2=称为格L1和L2的直积。，可以证明仍然是这样。L1L2，有=，交换律，()=，结合律，()=，()=，也是一样。求和运算满足吸收定律，可证运算也满足交换性、联系性和吸收定律，从而证明L1L2仍然是一个格。例如，如果格L=是小于或等于的通常关系，那么它是L和L的直积，是格L1的最小元素和最大元素，是不可比拟的。13.3分配格和互补格的定义和例子1一般来说，格中的运算满足分配不等式，即a，b，cL，并且有a，定义13.7让它是格。如果a，b，cL有一个(bc)=(ab)(ac) a(bc)=(ab)(ac)，那么L叫做分配格。以上两

13、个方程是相互对偶的。当l被证明是分配格时，只需要证明其中一个方程。例13.8，分配格，分配格，b(cd)=be=b(bc)(bd)=aa=a，不是分配格，c(bd)=ca=c(cb)(cd)=ed=d，不是分配格，DIA格，五边形格，判别式和分配格的性质推论(1)所有小于5元的格都是分配格。(2)任何链都是分配格。示例13.9显示了图13.6中的格是否是分配格，为什么？不是分配格，因为A、B、C、D和E是L1的子格，并且同构于DIA格，但不是分配格；a、B、C、E和F是L2的子晶格，与五边形晶格同构；a、C、B、E和F是L3的子晶格，与DIA晶格同构。不是分配格，定理13.7格l是分配格当且仅

14、当a，b，cL，ab=ac且ab=AC b=C，有必要证明：a，b，cL有b=b(ab)(吸收定律，交换定律)，b=b(AC)(已知条件的替代)，ba=BC(分配定律)，BC=AC(已知条件的替代，交换定律)，c=(ab)。(证明相反)，如果A，B和C1有ab=ac和AB=AC和B=C成立，并且L不是分配格，根据定理13.6，L必须包含与DIA格或五边形格同构的子图。从而推出xy=xz=u，xy=xz=v，但yz，与已知的相矛盾。对于五边形情况也可以证明这一点。利用定理13.7，我们还可以判断一个格是否是分配格。在L1，有bc=bd，bc=bd，但CD；在L2，有bc=be，bc=be，但是ce；在L3中，有cb=cd，cb=cd，但有bd，还有互补晶格。定义13.8让我是一个格子。如果aL的存在使得xL有一个x，那么A就叫做L的完全下界；如果bL存在，那么xL有x b，那么b被称为l的全上界。如果一个格l有一个全下界或全上界，它必须是唯一的。如果a1和a2都是格L的完全下界，那么就有a1 a2和a2 a1。根据偏序关系的反对称，必须有a1=a2。由于完全下界和完全上界的唯一性，格L的完全下界和完全上界一般被记录为0和1。全上界和全下界是格中最大和最小的元素。定义13.9让L是一个格。如果L有一个完全下界和一个完全上界，那么L被称为有界格，并且不难看出有限格L必须