离散数学课件第十三章格与布尔代数

第13章格与布尔代数第13章格与布尔代数本章内容13.1 格的定义与性质13.2 子格与格同态13.3 分配格与有补格13.4 布尔代数

本章总结

作业本章内容13.1 格的定义与性质13.1格的定义与性质定义13.1设<S,≤>是偏序集，如果x,y∈S，{x,y}都有最小上界和最大下界，则称S关于偏序≤作成一个格(lattice)。说明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧。

x∨y：表示x与y的最小上界

x∧y：表示x和y的最大下界。

本章出现的∨和∧符号只代表格中的运算，而不再有其它的含义。13.1格的定义与性质定义13.1设<S,≤>是偏序格的实例例13.1设n是正整数，Sn是n的正因子的集合。D为整除关系，则偏序集<Sn,D>构成格。x,y∈Sn， x∨y是lcm(x,y)，即x与y的最小公倍数。 x∧y是gcd(x,y)，即x与y的最大公约数。 下图给出了格<S8,D>，<S6,D>和<S30,D>。格的实例例13.1设n是正整数，Sn是n的正因子的集合。D例13.2例13.2判断下列偏序集是否构成格,并说明理由。 (1)<P(B),>，其中P(B)是集合B的幂集。 (2)<Z,≤>，其中Z是整数集,≤为小于或等于关系。 (3)偏序集的哈斯图分别在下图给出。例13.2例13.2判断下列偏序集是否构成格,并说明理由。例13.2解答(1)是格。 x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y。 由于∪和∩运算在P(B)上是封闭的，所以x∪y，x∩y∈P(B)。 称<P(B),>,为B的幂集格。(2)是格。 x,y∈Z,x∨y＝max(x,y)，x∧y＝min(x,y)，它们都是整数。(3)都不是格。 (a)中的{a,b}没有最大下界。 (b)中的{b,d}有两个上界c和e,但没有最小上界。 (c)中的{b,c}有三个上界d,e,f,但没有最小上界。 (d)中的{a,g}没有最大下界。例13.2解答(1)是格。例13.3例13.3设G是群，L(G)是G的所有子群的集合。即 L(G)＝{H|H≤G} 对任意的H1,H2∈L(G)，H1∩H2也是G的子群，而<H1∪H2>是由H1∪H2生成的子群（即包含着H1∪H2的最小的子群）。 在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格。 易见在L(G)中，H1∧H2就是H1∩H2，H1∨H2就是<H1∪H2>。例13.3例13.3设G是群，L(G)是G的所有子群的集合对偶原理定义13.2设f是含有格中元素以及符号＝、≤、≥、∨和∧的命题。令f*是将f中的≤替换成≥，≥替换成≤，∨替换成∧，∧替换成∨所得到的命题。称f*为f的对偶命题。例如 在格中令f是(a∨b)∧c≤c，则f*是(a∧b)∨c≥c。格的对偶原理设f是含有格中元素以及符号＝、≤、≥、∨和∧的命题。若f对一切格为真，则f的对偶命题f*也对一切格为真。例如

对一切格L都有 a,b∈L，a∧b≤a (因为a和b的交是a的一个下界) 那么对一切格L都有 a,b∈L，a∨b≥a说明 许多格的性质都是互为对偶命题的。 有了格的对偶原理，在证明格的性质时，

只须证明其中的一个命题即可。对偶原理定义13.2设f是含有格中元素以及符号＝、≤、≥、格的运算性质定理13.1设<L,≤>是格，则运算∨和∧适合交换律、结合律、幂等律和吸收律，即 (1)交换律a,b∈L有 a∨b＝b∨a a∧b＝b∧a (2)结合律a,b,c∈L有 (a∨b)∨c＝a∨(b∨c) (a∧b)∧c＝a∧(b∧c) (3)幂等律a∈L有 a∨a＝a a∧a＝a (4)吸收律a,b∈L有 a∨(a∧b)＝a a∧(a∨b)＝a格的运算性质定理13.1设<L,≤>是格，则运算∨和∧适合定理13.1(1)a∨b和b∨a分别是{a,b}和{b,a}的最小上界。 由于{a,b}＝{b,a}，所以a∨b＝b∨a。 由对偶原理，a∧b＝b∧a得证。(2)由最小上界的定义有 (a∨b)∨c≥a∨b≥a (13.1) (a∨b)∨c≥a∨b≥b (13.2) (a∨b)∨c≥c (13.3) 由式13.2和13.3有 (a∨b)∨c≥b∨c (13.4) 再由式13.1和13.4有 (a∨b)∨c≥a∨(b∨c) 同理可证 (a∨b)∨c≤a∨(b∨c) 根据偏序关系的反对称性有 (a∨b)∨c＝a∨(b∨c) 由对偶原理，(a∧b)∧c＝a∧(b∧c)得证。定理13.1(1)a∨b和b∨a分别是{a,b}和{b,a}定理13.1(3)显然a≤a∨a, 又由a≤a可得 a∨a≤a。 根据反对称性有 a∨a＝a， 由对偶原理，a∧a＝a得证。(4)显然 a∨(a∧b)≥a (13.5) 又由a≤a，a∧b≤a可得 a∨(a∧b)≤a (13.6) 由式13.5和13.6可得

a∨(a∧b)＝a， 根据对偶原理，a∧(a∨b)＝a得证。定理13.1(3)显然a≤a∨a,定理13.2定理13.2设<S,*,>是具有两个二元运算的代数系统，若对于*和运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序≤，使得<S,≤>构成一个格，且a,b∈S有a∧b＝a*b，a∨b＝ab。思路

(1)证明在S中*和运算都适合幂等律。 (2)在S上定义二元关系R，并证明R为偏序关系。 (3)证明<S,≤>构成格。说明 通过规定运算及其基本性质可以给出格的定义。定理13.2定理13.2设<S,*,>是具有两个二元运算定理13.2a∈S，由吸收律得(1)证明在S中*和运算都适合幂等律。a*a＝a*(a(a*a))＝a同理有aa＝a。(2)在S上定义二元关系R，a,b∈S有<a,b>∈Rab＝b下面证明R在S上的偏序。根据幂等律，a∈S都有aa＝a，即<a,a>∈R，所以R在S上是自反的。a,b∈S有aRb且bRaab＝b且ba＝aa＝ba＝ab＝b(由于ab=ba)所以R在S上是反对称的。定理13.2a∈S，由吸收律得(1)证明在S中*和运算都定理13.2a,b,c∈S有 aRb且bRc ab＝b且bc＝c ac＝a(bc) ac＝(ab)c ac＝bc＝c aRc 这就证明了R在S上是传递的。 综上所述，R为S上的偏序。 以下把R记作≤。定理13.2a,b,c∈S有定理13.2(3)证明<S，≤>构成格。即证明a∨b＝ab，a∧b＝a*b。a,b∈S有a(ab)＝(aa)b＝abb(ab)＝a(bb)＝ab根据≤的定义有a≤ab和b≤ab，所以ab是{a,b}的上界。假设c为{a,b}的上界，则有ac＝c和bc＝c，从而有(ab)c＝a(bc)＝ac＝c这就证明了ab≤c，所以ab是{a,b}的最小上界，即a∨b＝ab为证a*b是{a,b}的最大下界，先证首先由ab＝b可知a*b＝a*(ab)＝a反之由a*b＝a可知ab＝(a*b)b＝b(b*a)＝b再由式(13.7)和≤的定义有a≤ba*b＝a，依照前边的证明,类似地可证a*b是{a,b}的最大下界，即a∧b＝a*b。ab＝ba*b＝a (13.7)定理13.2(3)证明<S，≤>构成格。即证明a∨b＝a格的等价定义根据定理13.2，可以给出格的另一个等价定义。定义13.3设<S,*,>是代数系统，*和是二元运算，如果*和满足交换律，结合律和吸收律，则<S,*,>构成一个格(lattice)。说明 格中的幂等律可以由吸收律推出。 以后我们不再区别是偏序集定义的格，

还是代数系统定义的格，而统称为格L。格的等价定义根据定理13.2，可以给出格的另一个等价定义。格的性质定理13.3

设L是格，则a,b∈L有 a≤ba∧b＝aa∨b＝b证明

先证a≤ba∧b＝a 由a≤a和a≤b可知，a是{a,b}的下界， 故a≤a∧b。显然又有a∧b≤a。 由反对称性得a∧b＝a。

再证a∧b＝aa∨b＝b。 根据吸收律有b＝b∨(b∧a) 由a∧b＝a得b＝b∨a,即a∨b＝b。

最后证a∨b＝ba≤b。 由a≤a∨b得a≤a∨b＝b。格的性质定理13.3设L是格，则a,b∈L有格的性质定理11.4设L是格，a,b,c,d∈L，若a≤b且c≤d，则 a∧c≤b∧d， a∨c≤b∨d证明 a∧c≤a≤b a∧c≤c≤d 因此，a∧c≤b∧d。 同理可证a∨c≤b∨d。格的性质定理11.4设L是格，a,b,c,d∈L，若a≤例13.4

例13.4设L是格，证明a,b,c∈L有 a∨(b∧c)≤(a∨b)∧(a∨c)证明 由a≤a，b∧c≤b得 a∨(b∧c)≤a∨b 由a≤a，b∧c≤c得 a∨(b∧c)≤a∨c 从而得到a∨(b∧c)≤(a∨b)∧(a∨c)说明 在格中分配不等式成立。 一般说来，格中的∨和∧运算并不是满足分配律的。例13.4

例13.4设L是格，证明a,b,c∈L有本节小结偏序集构成格的条件：任意二元子集都有最大下界和最小上界。

格的实例：正整数的因子格，幂集格，子群格。格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。

格作为代数系统的定义。格的证明方法本节小结偏序集构成格的条件：任意二元子集都有最大下界和最小上13.2子格与格同态定义13.4设<L,∧,∨>是格，S是L的非空子集，若S关于L中的运算∧和∨仍构成格，则称S是L的子格。例13.5设格L如右图所示。令S1＝{a,e,f,g}S2＝{a,b,e,g}则S1不是L的子格，S2是L的子格。因为对于e和f,有e∧f＝c，但cS1。13.2子格与格同态定义13.4设<L,∧,∨>是格，S格同态定义13.5设L1和L2是格，:L1→L2，若a,b∈L1有 (a∧b)＝(a)∧(b),

(a∨b)＝(a)∨f(b) 成立，则称为格L1到L2的同态映射，简称格同态。例13.6(1)设L1＝{2n|n∈Z+}，L2＝{2n+1|n∈N} 则L1和L2关于通常数的小于或等于关系构成格。 令:L1→L2，(x)＝x-1 不难验证是L1到L2的同态映射，因为对任意的x,y∈L1有(x∨y)＝(max(x,y))＝max(x,y)-1(x)∨(y)＝(x-1)∨(y-1)＝max(x-1,y-1)＝max(x,y)-1(x∧y)＝(min(x,y))＝min(x,y)-1(x)∧(y)＝(x-1)∧(y-1)＝min(x-1,y-1)＝min(x,y)-1即(x∧y)＝(x)∧(y),

(x∨y)＝(x)∨(y)格同态定义13.5设L1和L2是格，:L1→L2，若例13.6(2)如图中的格L1，L2和L3，若定义1:L1→L21(a)＝1(b)＝1(c)＝a1，1(d)＝d12:L1→L3

2(a)＝a2，2(b)＝b2,2(c)＝c2，2(d)＝d2则1和2都不是格同态，因为 1(b∨c)＝1(d)＝d1 1(b)∨1(c)＝a1∨a1＝a1 2(b∨c)＝2(d)＝d2 2(b)∨2(c)＝b2∨c2＝c2从而

1(b∨c)≠1(b)∨1(c) 2(b∨c)≠2(b)∨2(c)例13.6(2)如图中的格L1，L2和L3，若定义1:L1格同态的性质定理13.5设是格L1到L2的映射， (1)若是格同态映射，则是保序映射，即x,y∈L1，有 x≤y

(x)≤(y) (2)若是双射，则是格同构映射当且仅当x,y∈L1，有 x≤y

(x)≤(y)证明(1)任取x,y∈L1，x≤y， 由格的性质知x∨y＝y。 又由于是格同态映射，必有

(y)＝(x∨y)＝(x)∨(y) 从而得到(x)≤(y)。格同态的性质定理13.5设是格L1到L2的映射，定理13.5(2)的证明充分性。(2)若是双射，则是格同构映射当且仅当x,y∈L1，有 x≤y(x)≤(y)只须证明是L1到L2的同态映射即可。任取x,y∈L1，令x∨y＝z，由x≤z和y≤z知(x)≤(z)，(y)≤(z)从而有(x)∨(y)≤(z)＝(x∨y)另一方面，由(x)∨(y)∈L2和的满射性可知，必存在u∈L1使得 (u)＝(x)∨(y)因此有 (x)≤(u)，(y)≤(u)。由已知条件可得x≤u，y≤u。从而推出x∨y≤u。再次使用已知条件得

(x∨y)≤(u)＝(x)∨(y)。综合上述有 (x∨y)＝(x)∨(y)。同理可证 (x∧y)＝(x)∧(y)。定理13.5(2)的证明充分性。(2)若是双射，则是格同定理13.5(2)的证明必要性。由(1)的结论必有 x≤y(x)≤(y)反之，若(x)≤(y)，由于是同构映射，则

(x∨y)＝(x)∨(y)＝(y)又由于是双射，必有x∨y＝y。从而证明了x≤y。(2)若是双射，则是格同构映射当且仅当x,y∈L1，有 x≤y(x)≤(y)定理13.5(2)的证明必要性。由(1)的结论必有(2)若例13.7例13.7设L1＝<S12,D>,L2＝<S12,≤>是格，其中S12是12的所有正因子构成的集合，D为整除关系，≤为通常数的小于或等于关系。令

:S12→S12，(x)＝x 则是双射，但不是格L1到L2的同构映射。 因为(2)≤(3)，但2不整除3。 根据定理13.5可知，不是同构映射。例13.7例13.7设L1＝<S12,D>,L2＝<S1格的直积类似于半群,群和环,也可以定义格的直积。定义13.6设L1和L2是格，定义L1×L2上的运算∩,∪： 即<a1,b1>,<a2,b2>∈L1×L2有 <a1,b1>∩<a2,b2>＝<a1∧a2,b1∧b2> <a1,b1>∪<a2,b2>＝<a1∨a2,b1∨b2> 称<L1×L2,∩,∪>为格L1和L2的直积。 可以证明<L1×L2,∩,∪>仍是格。格的直积类似于半群,群和环,也可以定义格的直积。格的直积<a1,b1>，<a2,b2>，<a3,b3>∈L1×L2，有交换律<a1,b1>∩<a2,b2>＝<a1∧a2,b1∧b2>＝<a2∧a1,b2∧b1>＝<a2,b2>∩<a1,b1>结合律(<a1,b1>∩<a2,b2>)∩<a3,b3>＝<a1∧a2,b1∧b2>∩<a3,b3>＝<(a1∧a2)∧a3,(b1∧b2)∧b3>＝<a1∧a2∧a3,b1∧b2∧b3>同样

<a1,b1>∩(<a2,b2>∩<a3,b3>)＝<a1∧a2∧a3,b1∧b2∧b3>同理可证∪运算也满足交换律和结合律。格的直积<a1,b1>，<a2,b2>，<a3,b3>∈L格的直积吸收律 <a1,b1>∩(<a1,b1>∪<a2,b2>) ＝<a1,b1>∩<a1∨a2,b1∨b2> ＝<a1∧(a1∨a2),b1∧(b1∨b2)> ＝<a1,b1>同理有

<a1,b1>∪(<a1,b1>∩<a2,b2>)＝<a1,b1>这就证明了∩和∪运算满足吸收律。从而证明L1×L2仍是格格的直积吸收律 <a1,b1>∩(<a1,b1>∪<a2格的直积举例格L＝<{0,1},≤>，≤为通常的小于或等于关系。则 L×L＝{<0,0>，<0,1>，<1,0>，<1,1>}，其中<0,0>是最小元，<1,1>是最大元，且 <0,0>≤<0,1>≤<1,1>， <0,0>≤<1,0>≤<1,1>，而<0,1>与<1,0>是不可比的。易见L×L与图13.4的L1同构。格的直积举例格L＝<{0,1},≤>，≤为通常的小于或等于关本节小结格L的非空子集S构成L的子格的条件： S对L的两个运算封闭。

函数构成格同态的条件：

(a∧b)＝(a)∧(b)

(a∨b)＝(a)∨(b)格同态的保序性。本节小结格L的非空子集S构成L的子格的条件：13.3分配格与有补格一般说来，格中运算∨对∧满足分配不等式， 即a,b,c∈L，有 a∨(b∧c)≤(a∨b)∧(a∨c) 但是不一定满足分配律。满足分配律的格称为分配格。定义13.7设<L,∧,∨>是格，若a,b,c∈L，有 a∧(b∨c)＝(a∧b)∨(a∧c) a∨(b∧c)＝(a∨b)∧(a∨c) 则称L为分配格。说明 上面两个等式互为对偶式。 在证明L为分配格时，只须证明其中的一个等式即可。13.3分配格与有补格一般说来，格中运算∨对∧满足分配不等例13.8L1和L2是分配格，L3和L4不是分配格。在L3中， b∧(c∨d)＝b∧e＝b(b∧c)∨(b∧d)＝a∨a＝a在L4中, c∨(b∧d)＝c∨a＝c(c∨b)∧(c∨d)＝e∧d＝d钻石格五角格例13.8L1和L2是分配格，L3和L4不是分配格。在L3中分配格的判别定理13.6设L是格，则L是分配格当且仅当L中不含有与钻石格或五角格同构的子格。证明 略。推论 (1)小于五元的格都是分配格。 (2)任何一条链都是分配格。分配格的判别定理13.6设L是格，则L是分配格当且仅当L中例13.9说明下图中的格是否为分配格，为什么？L1,L2和L3都不是分配格。{a,b,c,d,e}是L1的子格，并且同构于钻石格。{a,b,c,e,f}是L2的子格，并且同构于五角格。{a,c,b,e,f}是L3的子格，也同构于钻石格。

例13.9说明下图中的格是否为分配格，为什么？L1,L2和定理13.7定理13.7格L是分配格当且仅当 a,b,c∈L，a∧b＝a∧c且a∨b＝a∨cb＝c。证明

必要性。a,b,c∈L，有 b＝b∨(a∧b) (吸收律,交换律) ＝b∨(a∧c) (已知条件代入) ＝(b∨a)∧(b∨c) (分配律) ＝(a∨c)∧(b∨c) (已知条件代入,交换律) ＝(a∧b)∨c (分配律) ＝(a∧c)∨c (已知条件代入) ＝c (交换律,吸收律)定理13.7定理13.7格L是分配格当且仅当定理13.7充分性。假若a,b,c∈L，有 a∧b＝a∧c且a∨b＝a∨cb＝c 成立，而L不是分配格。 根据定理13.6，L中必含有与钻石格或五角格同构的子格。 假设L中含有与钻石格同构的子格，且该子格为{u,v,x,y,z}，其中u为它的最小元，v为它的最大元。从而推出 x∧y＝x∧z＝u，x∨y＝x∨z＝v但y≠z，与已知矛盾。对五角格的情况同理可证。vuxzy定理13.7充分性。假若a,b,c∈L，有从而推出vuxz定理13.7的应用使用定理13.7也可以判别一个格是否为分配格。例如下图中的三个格都不是分配格。在L1中有b∨c＝b∨d，b∧c＝b∧d，但c≠d。在L2中有b∧c＝b∧e，b∨c＝b∨e，但c≠e。在L3中有c∧b＝c∧d，c∨b＝c∨d，但b≠d。定理13.7的应用使用定理13.7也可以判别一个格是否为分配格的全下界和全上界定义13.8设L是格， 若存在a∈L使得x∈L有a≤x，则称a为L的全下界； 若存在b∈L使得x∈L有x≤b，则称b为L的全上界。命题 格L若存在全下界或全上界，一定是唯一的。证明 以全下界为例，假若a1和a2都是格L的全下界, 则有a1≤a2和a2≤a1。 根据偏序关系的反对称性必有a1＝a2。记法 将格L的全下界记为0，全上界记为1。格的全下界和全上界定义13.8设L是格，有界格定义13.9设L是格，若L存在全下界和全上界，则称L为有界格，并将L记为<L,∧,∨,0,1>。说明 有限格L一定是有界格。举例设L是n元格，且L＝{a1,a2,…,an}，那么a1∧a2∧…∧an是L的全下界，而a1∨a2∨…∨an是L的全上界。因此L是有界格。对于无限格L来说，有的是有界格，有的不是有界格。如集合B的幂集格<P(B),∩,∪>，不管B是有穷集还是无穷集，它都是有界格。它的全下界是空集，全上界是B。整数集Z关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。有界格定义13.9设L是格，若L存在全下界和全上界，则称L有界格的性质定理13.8设<L,∧,∨,0,1>是有界格，则a∈L有 a∧0＝0 a∨0＝a a∧1＝a a∨1＝1证明 由a∧0≤0和0≤a∧0可知a∧0＝0。说明 在有界格中， 全下界0是关于∧运算的零元，∨运算的单位元。 全上界1是关于∨运算的零元，∧运算的单位元。对偶原理对于涉及到有界格的命题，如果其中含有全下界0或全上界1，在求该命题的对偶命题时，必须将0替换成1，而将1替换成0。例如 a∧0＝0和a∨1＝1互为对偶命题， a∨0＝a和a∧1＝a互为对偶命题。有界格的性质定理13.8设<L,∧,∨,0,1>是有界格，有界格中的补元定义13.10设<L,∧,∨,0,1>是有界格，a∈L， 若存在b∈L使得

a∧b＝0和a∨b＝1 成立，则称b是a的补元。说明 若b是a的补元，那么a也是b的补元。 换句话说，a和b互为补元。有界格中的补元定义13.10设<L,∧,∨,0,1>是有界例13.10考虑下图中的四个格。L1中的a与c互为补元，其中a为全下界，c为全上界，b没有补元。L2中的a与d互为补元，其中a为全下界，d为全上界，b与c也互为补元。L3中的a与e互为补元，其中a为全下界，e为全上界，b的补元是c和d，c的补元是b和d，d的补元是b和c。b,c,d每个元素都有两个补元。L4中的a与e互为补元。其中a为全下界。e为全上界。b的补元是c和d，c的补元是b，d的补元是b。例13.10考虑下图中的四个格。L1中的a与c互为补元，其中有界格中补元的说明在任何有界格中，全下界0与全上界1互补。对于其他元素，可能存在补元，也可能不存在补元。如果存在，可能是唯一的，也可能是多个补元。对于有界分配格，如果它的元素存在补元，一定是唯一的。有界格中补元的说明在任何有界格中，有界分配格中补元的唯一性定理13.9设<L,∧,∨,0,1>是有界分配格。 若a∈L，且对于a存在补元b，则b是a的唯一补元。证明 假设c∈L也是a的补元，则有 a∨c＝1，a∧c＝0 又知b是a的补元，故 a∨b＝1，a∧b＝0 从而得到 a∨c＝a∨b，a∧c＝a∧b 由于L是分配格，根据定理13.7，b＝c。有界分配格中补元的唯一性定理13.9设<L,∧,∨,0,有补格的定义定义13.11设<L,∧,∨,0,1>是有界格，若L中所有元素都有补元存在，则称L为有补格。L2,L3和L4是有补格，L1不是有补格。L2和L3是有补格，L1不是有补格。有补格的定义定义13.11设<L,∧,∨,0,1>是有界格本节小结如果格中一个运算对另一个运算是可分配的，称这个格是分配格。

分配格的两种判别法： 不存在与钻石格或五角格同构的子格； 对于任意元素a,b,c,有a∧b＝a∧c且a∨b＝a∨cb＝c。

有界格的定义及其实例。

格中元素的补元及其性质（分配格中补元的唯一性）。

有补格的定义。本节小结如果格中一个运算对另一个运算是可分配的，称这个格是分13.4布尔代数定义13.12如果一个格是有补分配格，则称它为布尔格或布尔代数。说明 在布尔代数中，每个元素都存在着唯一的补元。 可以把求补元的运算看作是布尔代数中的一元运算。 可以把一个布尔代数标记为<B,∧,∨,＇,0,1>，

＇为求补运算,a∈B，a＇是a的补元。13.4布尔代数定义13.12如果一个格是有补分配格，则例13.11例13.11

设S110＝{1,2,5,10,11,22,55,110}是110的正因子集合。令gcd,lcm分别表示求最大公约数和最小公倍数的运算。问<S110,gcd,lcm>是否构成布尔代数？为什么？解答

证明<S110,gcd,lcm>构成格。容易验证x,y,z∈S110，有gcd(x,y)∈S110 lcm(x,y)∈S110gcd(x,y)＝gcd(y,x)lcm(x,y)＝lcm(y,x)gcd(gcd(x,y),z)＝gcd(x,gcd(y,z))lcm(lcm(x,y),z)＝lcm(x,lcm(y,z))gcd(x,lcm(x,y))＝xlcm(x,gcd(x,y))＝x二元运算交换律结合律吸收律例13.11例13.11

设S110＝{1,2,5,10,例13.11证明<S110,gcd,lcm>是分配格。 易验证x,y,z∈S110有 gcd(x,lcm(y,z))＝lcm(gcd(x,y),gcd(x,z))证明<S110,gcd,lcm>是有补格。 1为S110中的全下界 110为S110中的全上界 1和110互为补元，2和55互为补元， 5和22互为补元，10和11互为补元。综上所述，<S110,gcd,lcm>为布尔代数。例13.11证明<S110,gcd,lcm>是分配格。例13.12例13.12设B为任意集合,证明B的幂集格<P(B),∩,∪,～,,B>构成布尔代数，称为集合代数。证明 P(B)关于∩和∪构成格，因为 ∩和∪运算满足交换律、结合律和吸收律。 由于∩和∪互相可分配，因此P(B)是分配格， 且全下界是空集,全上界是B。 根据绝对补的定义，取全集为B， x∈P(B)，～x是x的补元。 从而证明P(B)是有补分配格，即布尔代数。例13.12例13.12设B为任意集合,证明B的幂集格<P布尔代数的性质定理13.10设<B,∧,∨,′,0,1>是布尔代数，则(1)a∈B，(a＇)＇＝a(2)a,b∈B，(a∧b)＇＝a＇∨b＇,(a∨b)＇＝a＇∧b＇说明 (1)称为双重否定律。 (2)称为德摩根律。 命题代数与集合代数的双重否定律与德摩根律实际上

是这个定理的特例。 可以证明德摩根律对有限个元素也是正确的。证明 (1)(a′)′是a′的补元，a也是a′的补元。 由补元的唯一性得(a′)′＝a。布尔代数的性质定理13.10设<B,∧,∨,′,0,1>是定理13.10(2)的证明(2)a,b∈B，(a∧b)＇＝a＇∨b＇,(a∨b)＇＝a＇∧b＇ (a∧b)∨(a＇∨b＇) ＝(a∨a＇∨b＇)∧(b∨a＇∨b＇) ＝(1∨b＇)∧(a＇∨1) ＝1∧1 ＝1

(a∧b)∧(a＇∨b＇) ＝(a∧b∧a＇)∨(a∧b∧b＇) ＝(0∧b)∨(a∧0) ＝0∨0＝0 所以a＇∨b＇是a∧b的补元，根据补元的唯一性有 (a∧b)＇＝a＇∨b＇ 同理可证(a∨b)＇=a＇∧b＇。定理13.10(2)的证明(2)a,b∈B，(a∧b)＇布尔代数作为代数系统的定义定义13.13设<B,*,>是代数系统，*和是二元运算。 若*和°运算满足： (1) 交换律，即a,b∈B有 a*b＝b*a， ab＝ba (2) 分配律，即a,b,c∈B有 a*(bc)＝(a*b)(a*c) a(b*c)＝(ab)*(ac)

(3) 同一律，即存在0,1∈B，使得a∈B有 a*1＝a， a0＝a (4) 补元律，即a∈B,存在a′∈B，使得 a*a′＝0， aa′＝1则称<B,*,>是一个布尔代数。

布尔代数作为代数系统的定义定义13.13设<B,*,>是关于布尔代数定义的说明所谓同一律就是指运算含有单位元的性质，这里的1是*运算的单位元，0是运算的单位元。可以证明1和0分别也是和*运算的零元。a∈B有 a1 ＝(a1)*1 （同一律） ＝1*(a1) （交换律） ＝(aa′)*(a1) （补元律） ＝a(a′*1) （分配律） ＝aa′ （同一律） ＝1（补元律）同理可证a*0＝0。关于布尔代数定义的说明所谓同一律就是指运算含有单位元的性质，关于布尔代数定义的说明为证明以上定义的<B,*,°>是布尔代数，只需证明它是一个格，即证明*和°运算满足结合律和吸收律。证明吸收律，a,b∈B有

a(a*b) ＝(a*1)(a*b) （同一律） ＝a*(1b) （分配律） ＝a*1 （1是运算的零元) ＝a （同一律）同理有a*(ab)＝a。关于布尔代数定义的说明为证明以上定义的<B,*,°>是布尔代关于布尔代数定义的说明为证结合律，先证以下命题：

a,b,c∈B，ab＝ac且ab＝acb＝c由ab＝ac且ab＝ac可得 (ab)*(ab)＝(ac)*(ac)由分配律和交换律得 (a*a)b＝(a*a)c由补元律得 0b＝0c由同一律和交换律得 b＝c关于布尔代数定义的说明为证结合律，先证以下命题：关于布尔代数定义的说明使用这个命题，为证明(a*b)*c＝a*(b*c)，只需证明以下两个等式：(1)a((a*b)*c)＝a(a*(b*c))(2)a((a*b)*c)＝a(a*(b*c))先证明第一个等式，由吸收律有 a(a*(b*c))＝a a((a*b)*c) ＝(a(a*b))*(ac) (分配律) ＝a*(ac) (吸收律) ＝a所以(1)式成立。关于布尔代数定义的说明使用这个命题，为证明(a*b)*c＝关于布尔代数定义的说明下面证明(2)式：a((a*b)*c)＝a(a*(b*c))

a(a*(b*c)) ＝(aa)*(a(b*c)) (分配律) ＝1*(a(b*c)) (交换律,补元律) ＝a(b*c) (交换律,同一律)

a((a*b)*c) ＝(a(a*b))*(ac)(分配律) ＝((aa)*(ab))*(ac) (分配律) ＝(1*(ab))*(ac) (交换律,补元律) ＝(ab)*(ac)(交换律,同一律) ＝a(b*c) (分配律)所以（2）式成立。关于布尔代数定义的说明下面证明(2)式：a((a*b)布尔代数的子代数定义13.14设<B,∧,∨,,0,1>是布尔代数，S是B的非空子集，若0,1∈S，且S对∧,∨和运算都是封闭的，则称S是B的子布尔代数。

布尔代数的子代数定义13.14设<B,∧,∨,,0,1>例13.13例13.13设<B,∧,∨,,0,1>是布尔代数，a,b∈B，且a＜b。令 S＝{x|x∈B，且a≤x≤b} 称S为B中的区间，可简记为[a,b]。 可以证明[a,b]是一个布尔代数。 显然S是B的非空子集，且a和b分别为S的全下界和全上界。 对任意的x,y∈S都有 a≤x≤b， a≤y≤b 从而有 a≤x∧y≤b,a≤x∨y≤b S关于∧和∨运算是封闭的。 易见∧和∨运算在S上适合交换律和分配律。例13.13例13.13设<B,∧,∨,,0,1>是布尔例13.13对任意的x∈S，令y＝(a∨x)∧b(下面证明y为x得补元。)由于a≤a∨x，a≤b，故a≤(a∨x)∧b。同时(a∨x)∧b≤b，因此y∈S。又x∨y ＝x∨((a∨x)∧b) ＝x∨((a∧b)∨(x∧b)) (分配律) ＝x∨a∨(x∧b) (a＜b) ＝x∨(x∧b) (a≤x) ＝(x∨x)∧(x∨b) (分配律) ＝1∧(x∨b) (补元律) ＝x∨b (交换律，同一律) ＝b (x≤b)例13.13对任意的x∈S，令y＝(a∨x)∧b(例13.13 x∧y ＝x∧((a∨x)∧b) ＝x∧(a∨x) (x≤b,交换律) ＝(x∧a)∨(x∧x) (分配律) ＝(x∧a)∨0 (补元律) ＝x∧a (同一律) ＝a (a≤x)根据定义13.13，<S,∧,∨>构成布尔代数。其全上界是a，全下界是b。x∈[a,b]，x关于这个全上界和全下界的补元是(a∨x)∧b。当a＝0且b＝1时，[a,b]是B的子布尔代数。但当a≠0或b≠1时，[a,b]不是B的子布尔代数。例13.13 x∧y ＝x∧((a∨x)∧b)例13.14考虑110的正因子集合S110关于gcd,lcm运算构成的布尔代数。它有以下的子布尔代数： {1,110} {1,2,55,110} {1,5,22,110} {1,10,11,110} {1,2,5,10,11,22,55,110}例13.14考虑110的正因子集合S110关于gcd,lcm布尔代数的同态映射定义13.15设<B1,∧,∨,,0,1>和<B2,∩,∪,-,θ,E>是两个布尔代数。这里的∩,∪,-泛指布尔代数B2中的求最大下界、最小上界和补元的运算。θ和E分别是B2的全下界和全上界。

:B1→B2。如果对于任意的a,b∈B1有

(a∨b)＝(a)∪(b)

(a∧b)＝(a)∩(b)

(a)＝-(a) 则称是布尔代数B1到B2的同态映射，简称布尔代数的同态。说明

类似于其它代数系统，也可以定义布尔代数的单同态、

满同态和同构。布尔代数的同态映射定义13.15设<B1,∧,∨,,0,例13.15例13.15设<B1,∧,∨,,0,1>和<B2,∩,∪,-,θ,E>是布尔代数。:B1→B2。若a,b∈B1有

(a∧b)＝(a)∩(b) (a)＝-(a) 证明是B1到B2的同态。证明 只须证明a,b∈B1有(a∨b)＝(a)∪(b)成立即可。

(a∨b) ＝(((a∨b))) (双重否定律) ＝-((a∨b)) (已知) ＝-(a∧b) (德摩根律) ＝-((a)∩(b)) (已知) ＝-(-(a)∩-(b)) (已知) ＝-(-(a))∪-(-(b)) (德摩根律) ＝(a)∪(b) (双重否定律)例13.15例13.15设<B1,∧,∨,,0,1>和<有限布尔代数的结构定义13.16设L是格，0∈L，a∈L，若b∈L有 0＜b≤ab＝a 则称a是L中的原子。考虑右图中的几个格。L1的原子是a。L2的原子是a,b,c。L3的原子是a和b。若L是正整数n的全体正因子关于整除关系构成的格，则L的原子恰为n的全体质因子。若L是集合B的幂集合，则L的原子就是由B中元素构成的单元集。有限布尔代数的结构定义13.16设L是格，0∈L，a∈L，引理１引理1 设Ｌ是格，a,b是Ｌ中的原子，若a≠b，则a∧b＝0。证明 假设a∧b≠0，则有 0＜a∧b≤a和0＜a∧b≤b 由于a,b是原子，则有a∧b＝a和a∧b＝b， 从而有a＝b，与已知矛盾。引理１引理1 设Ｌ是格，a,b是Ｌ中的原子，若a≠b，则a∧引理２引理２设B是有限的布尔代数，x∈B，x≠0，令 T(x)＝{a1,a2,…,an} 是B中所有小于或等于x的原子构成的集合，则 x＝a1∨a2∨…∨an 称这个表示式为x的原子表示，且是唯一的表示。 这里的唯一性是指：若 x＝a1∨a2∨…∨an，x＝b1∨b2∨…∨bn 都是x的原子表示，则有 {a1,a2,…an}＝{b1,b2,…bn}引理２引理２设B是有限的布尔代数，x∈B，x≠0，令引理2的证明令y＝a1∨a2∨…∨an。由于ai≤x，i＝1,2,…n，所以必有y≤x。由此可知t1是原子，且t1≤x和t1≤y。假如x∧y≠0，则存在B中元素t1,t2,…,ts，现证明x∧y＝0。使得t1覆盖0，t2覆盖t1，…，ts覆盖ts-1，且ts＝x∧y。由t1≤x可知t1∈T(x)。即存在ai∈T(x)，使得t1＝ai。又由t1≤y可知t1∧y＝t1，从而有t1＝t1∧y＝ai∧y＝ai∧(a1∨a2∨…∨an)＝ai∧(a1∧a2∧…∧ai∧…∧an)＝(ai∧ai)∧(a1∧…∧ai-1∧ai+1∧…∧an)＝0∧a1∧…∧ai-1∧ai+1∧…∧an＝0这与t1覆盖0矛盾。从而证明了x∧y＝0。引理2的证明令y＝a1∨a2∨…∨an。由于ai≤x，i＝1引理２由 y＝y∨0＝(y∨x)∧(y∨y)＝y∨(x∧y)＝(y∨x)∧1＝y∨x可知x≤y。综合上述得x＝y，即x＝a1∨a2∨…∨an。设x＝b1∨b2∨…∨bm是x的另一个原子表示，任取ai∈{a1,a2,…,an}，假若ai{b1,b2,…,bm}。由引理1必有ai∧bj＝0，j＝1,2,…m。又由于ai≤x，于是ai＝ai∧x＝ai∧(b1∨b2∨…∨bn)＝(ai∧b1)∨(ai∧b2)∨…∨(ai∧bm)＝0∨0∨…∨0＝0这与ai是原子矛盾。从而证明了ai∈{b1,b2,…,bm}。同理可证，bj∈{b1,b2,…,bm}，必有bj∈{a1,a2,…,an}，于是{a1,a2,…,an}＝{b1,b2,…,bm}。引理２由 y＝y∨0＝(y∨x)∧(y∨y)＝y∨(x∧有限布尔代数的表示定理定理13.11(有限布尔代数的表示定理)设B是有限布尔代数，A是B的全体原子构成的集合，则B同构于A的幂集代数P(A)。证明 任取x∈B，令T(x)＝{a|a∈B,a是原子且a≤x} 则T(x)A，定义函数 ：B→P(A)，(x)＝T(x)，x∈B 下面证明是B到P(A)的同构映射。 任取x,y∈B，b有 b∈T(x∧y)b∈A且b≤x∧y (b∈A且b≤x)且(b∈A且b≤y) b∈T(x)且b∈T(y) b∈T(x)∩T(y) 从而有T(x∧y)＝T(x)∩T(y)， 即x,yB有(x∧y)＝(x)∩(y)。有限布尔代数的表示定理定理13.11(有限布尔代数的表示定定理13.11证明任取x,y∈B，设 x＝a1∨a2∨…∨an， y＝b1∨b2∨…∨bm是x,y的原子表示，则 x∨y＝a1∨a2∨…∨an∨b1∨b2∨…∨bm由引理2可知 T(x∨y)＝{a1,a2,…,an,b1,b2,…,bm}又由于 T(x)＝{a1,a2,…,an}， T(y)＝{b1,b2,…,bm}所以 T(x∨y)＝T(x)∪T(y)即 (x∨y)＝(x)∪(y)定理13.11证明任取x,y∈B，设定理13.11证明任取x∈B，存在x∈B使得 x∨x＝1，x∧x＝0因此有 (x)∪(x)＝(x∨x)＝(1)＝A (x)∩(x)＝(x∧x)＝(0)＝而和A分别为P(A)的全下界和全上界，因此(x)是(x)在P(A)中的补元，即 (x)＝〜(x)综上所述，是B到P(A)的同态映射。定理13.11证明任取x∈B，存在x∈B使得定理13.11证明下面证明为双射。假设(x)＝(y)，则有 T(x)＝T(y)＝{a1,a2,…,an}由引理2可知x＝a1∨a2∨…∨an＝y于是为单射。任取{b1,b2,…,bm}∈P(A)，令x＝b1∨b2∨…∨bm，则 (x)＝T(x)＝{b1,b2,…,bm}于是为满射。定理得证。定理13.11证明下面证明为双射。例子考虑110的正因子的集合S110关于gcd,lcm运算构成的布尔代数。它的原子是2、5和11，因此原子的集合A＝{2,5,11}。幂集P(A)＝{,{2},{5},{11},{2,5},{2,11},{5,11},{2,5,11}}。幂集代数是<P(A),∩,∪,∽,,A>。只要令

:S110→P(A)，

(1)＝， (2)＝{2}， (5)＝{5}，

(11)＝{11}， (10)＝{2,5}， (22)＝{2,11}，

(55)＝{5,11},

(110)＝A，那么f就是定理13.11中从S110到幂集P(A)的同构映射。例子考虑110的正因子的集合S110关于gcd,lcm运算推论1推论1 任何有限布尔代数的基数为2n，n∈N。证明 设B是有限布尔代数，A是B的所有原子构成的集合， 且|A|＝n，n∈N。 由定理13.11得 B≌P(A)，而|P(A)|＝2n，所以|B|＝2n。推论1推论1 任何有限布尔代数的基数为2n，n∈N。推论2推论2

任何等势的有限布尔代数都是同构的。证明设B1和B2是有限布尔代数，且|B1|=|B2|。 则B1≌P(A1)，B2≌P(A2)，其中A1和A2分别为B1和B2的原子集合。 易见|A1|＝|A2|，存在双射f：A1→A2。令

：P(A1)→P(A2)，(x)＝f(x)，xA1 下面证明是P(A1)到P(A2)的同构映射。 任取x,y∈P(A1)，由定理7.5有 f(x∪y)＝f(x)∪f(y) f(x∩y)f(x)∩f(y) 又由于f的单射性，必有f(x∩y)＝f(x)∩f(y)

由于 f(x)∩f(～x)＝f(x∩～x)＝f()＝ f(x)∪f(～x)＝f(x∪～x)＝f(A1)＝A2 得f(～x)＝～f(x)，这就证明了是P(A1)到P(A2)的同态映射。 综上所述,有P(A1)≌P(A2),根据习题十三章第19题，B1≌B2得证。推论2推论2任何等势的有限布尔代数都是同构的。有限布尔代数的说明有限布尔代数的基数都是2的幂。在同构意义上，对于任何2n，n为自然数，仅存在一个2n元的布尔代数。下图给出了1元,2元,4元和8元的布尔代数。有限布尔代数的说明有限布尔代数的基数都是2的幂。主要内容布尔代数的两个等价定义：有补分配格；有两个二元运算并满足交换律、分配律、同一律和补元律的代数系统。

布尔代数的特殊性质：双重否定律和德摩根律。子布尔代数的定义及其判别。

布尔代数同态的判定：f(a∧b)＝f(a)∩f(b)(或f(a∨b)＝f(a)∪f(b)),f(a)＝-f(a)

对于任意自然数n，只有一个2n元的有限布尔代数，就是幂集代数。

主要内容布尔代数的两个等价定义：学习要求能够判断给定偏序集或者代数系统是否构成格。

能够确定一个命题的对偶命题。

能够证明格中的等式和不等式。

能够判别格L的子集S是否构成格。了解格的同态及其性质。能够判别给定的格是否为分配格。能够判别布尔代数并证明布尔代数的等式。学习要求能够判断给定偏序集或者代数系统是否构成格。

作业习题十三1，2，3，6，8，12，16，17，19作业习题十三格的证明方法格中等式的证明方法 证明等式的左边“小于等于”右边，右边“小于等于”左边。 根据偏序关系的反对称性，得到需要的等式。格中不等式的证明方法 a≤a (偏序关系的自反性) a≤b且b≤ca≤c (偏序关系的传递性) a∧b≤a，a∧b≤b，a≤a∨b，a≤a∨b (下界定义与上界的定义) a≤b且a≤ca≤b∧c，b≤a且c≤ab∨c≤a (最大下界定义与最小上界的定义) a≤b且c≤da∧c≤b∧d，a∨c≤b∨d (保序性)格的证明方法格中等式的证明方法第13章格与布尔代数第13章格与布尔代数本章内容13.1 格的定义与性质13.2 子格与格同态13.3 分配格与有补格13.4 布尔代数

本章总结

作业本章内容13.1 格的定义与性质13.1格的定义与性质定义13.1设<S,≤>是偏序集，如果x,y∈S，{x,y}都有最小上界和最大下界，则称S关于偏序≤作成一个格(lattice)。说明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧。

x∨y：表示x与y的最小上界

x∧y：表示x和y的最大下界。

本章出现的∨和∧符号只代表格中的运算，而不再有其它的含义。13.1格的定义与性质定义13.1设<S,≤>是偏序格的实例例13.1设n是正整数，Sn是n的正因子的集合。D为整除关系，则偏序集<Sn,D>构成格。x,y∈Sn， x∨y是lcm(x,y)，即x与y的最小公倍数。 x∧y是gcd(x,y)，即x与y的最大公约数。 下图给出了格<S8,D>，<S6,D>和<S30,D>。格的实例例13.1设n是正整数，Sn是n的正因子的集合。D例13.2例13.2判断下列偏序集是否构成格,并说明理由。 (1)<P(B),>，其中P(B)是集合B的幂集。 (2)<Z,≤>，其中Z是整数集,≤为小于或等于关系。 (3)偏序集的哈斯图分别在下图给出。例13.2例13.2判断下列偏序集是否构成格,并说明理由。例13.2解答(1)是格。 x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y。 由于∪和∩运算在P(B)上是封闭的，所以x∪y，x∩y∈P(B)。 称<P(B),>,为B的幂集格。(2)是格。 x,y∈Z,x∨y＝max(x,y)，x∧y＝min(x,y)，它们都是整数。(3)都不是格。 (a)中的{a,b}没有最大下界。 (b)中的{b,d}有两个上界c和e,但没有最小上界。 (c)中的{b,c}有三个上界d,e,f,但没有最小上界。 (d)中的{a,g}没有最大下界。例13.2解答(1)是格。例13.3例13.3设G是群，L(G)是G的所有子群的集合。即 L(G)＝{H|H≤G} 对任意的H1,H2∈L(G)，H1∩H2也是G的子群，而<H1∪H2>是由H1∪H2生成的子群（即包含着H1∪H2的最小的子群）。 在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格。 易见在L(G)中，H1∧H2就是H1∩H2，H1∨H2就是<H1∪H2>。例13.3例13.3设G是群，L(G)是G的所有子群的集合对偶原理定义13.2设f是含有格中元素以及符号＝、≤、≥、∨和∧的命题。令f*是将f中的≤替换成≥，≥替换成≤，∨替换成∧，∧替换成∨所得到的命题。称f*为f的对偶命题。例如 在格中令f是(a∨b)∧c≤c，则f*是(a∧b)∨c≥c。格的对偶原理设f是含有格中元素以及符号＝、≤、≥、∨和∧的命题。若f对一切格为真，则f的对偶命题f*也对一切格为真。例如

对一切格L都有 a,b∈L，a∧b≤a (因为a和b的交是a的一个下界) 那么对一切格L都有 a,b∈L，a∨b≥a说明 许多格的性质都是互为对偶命题的。 有了格的对偶原理，在证明格的性质时，

只须证明其中的一个命题即可。对偶原理定义13.2设f是含有格中元素以及符号＝、≤、≥、格的运算性质定理13.1设<L,≤>是格，则运算∨和∧适合交换律、结合律、幂等律和吸收律，即 (1)交换律a,b∈L有 a∨b＝b∨a a∧b＝b∧a (2)结合律a,b,c∈L有 (a∨b)∨c＝a∨(b∨c) (a∧b)∧c＝a∧(b∧c) (3)幂等律a∈L有 a∨a＝a a∧a＝a (4)吸收律a,b∈L有 a∨(a∧b)＝a a∧(a∨b)＝a格的运算性质定理13.1设<L,≤>是格，则运算∨和∧适合定理13.1(1)a∨b和b∨a分别是{a,b}和{b,a}的最小上界。 由于{a,b}＝{b,a}，所以a∨b＝b∨a。 由对偶原理，a∧b＝b∧a得证。(2)由最小上界的定义有 (a∨b)∨c≥a∨b≥a (13.1) (a∨b)∨c≥a∨b≥b (13.2) (a∨b)∨c≥c (13.3) 由式13.2和13.3有 (a∨b)∨c≥b∨c (13.4) 再由式13.1和13.4有 (a∨b)∨c≥a∨(b∨c) 同理可证 (a∨b)∨c≤a∨(b∨c) 根据偏序关系的反对称性有 (a∨b)∨c＝a∨(b∨c) 由对偶原理，(a∧b)∧c＝a∧(b∧c)得证。定理13.1(1)a∨b和b∨a分别是{a,b}和{b,a}定理13.1(3)显然a≤a∨a, 又由a≤a可得 a∨a≤a。 根据反对称性有 a∨a＝a， 由对偶原理，a∧a＝a得证。(4)显然 a∨(a∧b)≥a (13.5) 又由a≤a，a∧b≤a可得 a∨(a∧b)≤a (13.6) 由式13.5和13.6可得

a∨(a∧b)＝a， 根据对偶原理，a∧(a∨b)＝a得证。定理13.1(3)显然a≤a∨a,定理13.2定理13.2设<S,*,>是具有两个二元运算的代数系统，若对于*和运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序≤，使得<S,≤>构成一个格，且a,b∈S有a∧b＝a*b，a∨b＝ab。思路

(1)证明在S中*和运算都适合幂等律。 (2)在S上定义二元关系R，并证明R为偏序关系。 (3)证明<S,≤>构成格。说明 通过规定运算及其基本性质可以给出格的定义。定理13.2定理13.2设<S,*,>是具有两个二元运算定理13.2a∈S，由吸收律得(1)证明在S中*和运算都适合幂等律。a*a＝a*(a(a*a))＝a同理有aa＝a。(2)在S上定义二元关系R，a,b∈S有<a,b>∈Rab＝b下面证明R在S上的偏序。根据幂等律，a∈S都有aa＝a，即<a,a>∈R，所以R在S上是自反的。a,b∈S有aRb且bRaab＝b且ba＝aa＝ba＝ab＝b(由于ab=ba)所以R在S上是反对称的。定理13.2a∈S，由吸收律得(1)证明在S中*和运算都定理13.2a,b,c∈S有 aRb且bRc ab＝b且bc＝c ac＝a(bc) ac＝(ab)c ac＝bc＝c aRc 这就证明了R在S上是传递的。 综上所述，R为S上的偏序。 以下把R记作≤。定理13.2a,b,c∈S有定理13.2(3)证明<S，≤>构成格。即证明a∨b＝ab，a∧b＝a*b。a,b∈S有a(ab)＝(aa)b＝abb(ab)＝a(bb)＝ab根据≤的定义有a≤ab和b≤ab，所以ab是{a,b}的上界。假设c为{a,b}的上界，则有ac＝c和bc＝c，从而有(ab)c＝a(bc)＝ac＝c这就证明了ab≤c，所以ab是{a,b}的最小上界，即a∨b＝ab为证a*b是{a,b}的最大下界，先证首先由ab＝b可知a*b＝a*(ab)＝a反之由a*b＝a可知ab＝(a*b)b＝b(b*a)＝b再由式(13.7)和≤的定义有a≤ba*b＝a，依照前边的证明,类似地可证a*b是{a,b}的最大下界，即a∧b＝a*b。ab＝ba*b＝a (13.7)定理13.2(3)证明<S，≤>构成格。即证明a∨b＝a格的等价定义根据定理13.2，可以给出格的另一个等价定义。定义13.3设<S,*,>是代数系统，*和是二元运算，如果*和满足交换律，结合律和吸收律，则<S,*,>构成一个格(lattice)。说明 格中的幂等律可以由吸收律推出。 以后我们不再区别是偏序集定义的格，

还是代数系统定义的格，而统称为格L。格的等价定义根据定理13.2，可以给出格的另一个等价定义。格的性质定理13.3

设L是格，则a,b∈L有 a≤ba∧b＝aa∨b＝b证明

先证a≤ba∧b＝a 由a≤a和a≤b可知，a是{a,b}的下界， 故a≤a∧b。显然又有a∧b≤a。 由反对称性得a∧b＝a。

再证a∧b＝aa∨b＝b。 根据吸收律有b＝b∨(b∧a) 由a∧b＝a得b＝b∨a,即a∨b＝b。

最后证a∨b＝ba≤b。 由a≤a∨b得a≤a∨b＝b。格的性质定理13.3设L是格，则a,b∈L有格的性质定理11.4设L是格，a,b,c,d∈L，若a≤b且c≤d，则 a∧c≤b∧d， a∨c≤b∨d证明 a∧c≤a≤b a∧c≤c≤d 因此，a∧c≤b∧d。 同理可证a∨c≤b∨d。格的性质定理11.4设L是格，a,b,c,d∈L，若a≤例13.4

例13.4设L是格，证明a,b,c∈L有 a∨(b∧c)≤(a∨b)∧(a∨c)证明 由a≤a，b∧c≤b得 a∨(b∧c)≤a∨b 由a≤a，b∧c≤c得 a∨(b∧c)≤a∨c 从而得到a∨(b∧c)≤(a∨b)∧(a∨c)说明 在格中分配不等式成立。 一般说来，格中的∨和∧运算并不是满足分配律的。例13.4

例13.4设L是格，证明a,b,c∈L有本节小结偏序集构成格的条件：任意二元子集都有最大下界和最小上界。

格的实例：正整数的因子格，幂集格，子群格。格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。

格作为代数系统的定义。格的证明方法本节小结偏序集构成格的条件：任意二元子集都有最大下界和最小上13.2子格与格同态定义13.4设<L,∧,∨>是格，S是L的非空子集，若S关于L中的运算∧和∨仍构成格，则称S是L的子格。例13.5设格L如右图所示。令S1＝{a,e,f,g}S2＝{a,b,e,g}则S1不是L的子格，S2是L的子格。因为对于e和f,有e∧f＝c，但cS1。13.2子格与格同态定义13.4设<L,∧,∨>是格，S格同态定义13.5设L1和L2是格，:L1→L2，若