离散数学格与布尔代数

第11章格与布尔代数离散数学中国地质大学本科生课程本章内容11.1格的定义与性质11.2分配格、有补格与布尔代数本章总结作业11.1格的定义与性质定义11.1设S,≤是偏序集，如果x,y∈S，{x,y}都有最小上界和最大下界，则称S关于偏序≤作成一个格(lattice)。说明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧。x∨y：表示x与y的最小上界x∧y：表示x和y的最大下界。本章出现的∨和∧符号只代表格中的运算，而不再有其它的含义。格的实例例11.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。例11.2例11.2判断下列偏序集是否构成格,并说明理由。(1)P(B),，其中P(B)是集合B的幂集。(2)Z,≤，其中Z是整数集,≤为小于或等于关系。(3)偏序集的哈斯图分别在下图给出。例11.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}没有最大下界。例11.3例11.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。对偶原理定义11.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说明许多格的性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，只须证明其中的一个命题即可。格的运算性质定理11.1设L,≤是格，则运算∨和∧适合交换律、结合律、幂等律和吸收律，即(1)交换律a,b∈L有a∨b＝b∨aa∧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＝aa∧a＝a(4)吸收律a,b∈L有a∨(a∧b)＝aa∧(a∨b)＝a定理11.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)得证。定理11.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得证。定理11.2定理11.2设S,*,是具有两个二元运算的代数系统，若对于*和运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序≤，使得S,≤构成一个格，且a,b∈S有a∧b＝a*b，a∨b＝ab。思路(1)证明在S中*和运算都适合幂等律。(2)在S上定义二元关系R，并证明R为偏序关系。(3)证明S,≤构成格。说明通过规定运算及其基本性质可以给出格的定义。定理11.2a∈S，由吸收律得(1)证明在S中*和运算都适合幂等律。a*a＝a*(a(a*a))＝a同理有aa＝a。(2)在S上定义二元关系R，a,b∈S有a,b∈Rab＝b下面证明R在S上的偏序。根据幂等律，a∈S都有aa＝a，即a,a∈R，所以R在S上是自反的。a,b∈S有aRb且bRaab＝b且ba＝aa＝ba＝ab＝b(由于ab=ba)所以R在S上是反对称的。定理11.2a,b,c∈S有aRb且bRcab＝b且bc＝cac＝a(bc)ac＝(ab)cac＝bc＝caRc这就证明了R在S上是传递的。综上所述，R为S上的偏序。以下把R记作≤。定理11.2(3)证明S，≤构成格。即证明a∨b＝ab，a∧b＝a*b。a,b∈S有a(ab)＝(aa)b＝abb(ab)＝a(bb)＝ab根据≤的定义有a≤ab和b≤ab，所以ab是{a,b}的上界。假设c为{a,b}的上界，则有ac＝c和bc＝c，从而有(ab)c＝a(bc)＝ac＝c这就证明了ab≤c，所以ab是{a,b}的最小上界，即a∨b＝ab为证a*b是{a,b}的最大下界，先证首先由ab＝b可知a*b＝a*(ab)＝a反之由a*b＝a可知ab＝(a*b)b＝b(b*a)＝b再由式(13.7)和≤的定义有a≤ba*b＝a，依照前边的证明,类似地可证a*b是{a,b}的最大下界，即a∧b＝a*b。ab＝ba*b＝a(13.7)格的等价定义根据定理11.2，可以给出格的另一个等价定义。定义11.3设S,*,是代数系统，*和是二元运算，如果*和满足交换律，结合律和吸收律，则S,*,构成一个格(lattice)。说明格中的幂等律可以由吸收律推出。以后我们不再区别是偏序集定义的格，还是代数系统定义的格，而统称为格L。格的性质定理11.3设L是格，则a,b∈L有a≤ba∧b＝aa∨b＝b证明先证a≤ba∧b＝a由a≤a和a≤b可知，a是{a,b}的下界，故a≤a∧b。显然又有a∧b≤a。由反对称性得a∧b＝a。再证a∧b＝aa∨b＝b。根据吸收律有b＝b∨(b∧a)由a∧b＝a得b＝b∨a,即a∨b＝b。最后证a∨b＝ba≤b。由a≤a∨b得a≤a∨b＝b。格的性质定理11.4设L是格，a,b,c,d∈L，若a≤b且c≤d，则a∧c≤b∧d，a∨c≤b∨d证明a∧c≤a≤ba∧c≤c≤d因此，a∧c≤b∧d。同理可证a∨c≤b∨d。例11.5例11.5设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)说明在格中分配不等式成立。一般说来，格中的∨和∧运算并不是满足分配律的。本节小结偏序集构成格的条件：任意二元子集都有最大下界和最小上界。格的实例：正整数的因子格，幂集格，子群格。格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。格作为代数系统的定义。格的证明方法子格定义11.4设L,∧,∨是格，S是L的非空子集，若S关于L中的运算∧和∨仍构成格，则称S是L的子格。例11.6设格L如右图所示。令S1＝{a,e,f,g}S2＝{a,b,e,g}则S1不是L的子格，S2是L的子格。因为对于e和f,有e∧f＝c，但cS1。11.2分配格、有补格与布尔代数一般说来，格中运算∨对∧满足分配不等式，即a,b,c∈L，有a∨(b∧c)≤(a∨b)∧(a∨c)但是不一定满足分配律。满足分配律的格称为分配格。定义11.5设L,∧,∨是格，若a,b,c∈L，有a∧(b∨c)＝(a∧b)∨(a∧c)a∨(b∧c)＝(a∨b)∧(a∨c)则称L为分配格。说明上面两个等式互为对偶式。在证明L为分配格时，只须证明其中的一个等式即可。例11.7L1和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钻石格五角格分配格的判别定理11.5设L是格，则L是分配格当且仅当L中不含有与钻石格或五角格同构的子格。证明略。推论(1)小于五元的格都是分配格。(2)任何一条链都是分配格。例11.8说明下图中的格是否为分配格，为什么？L1,L2和L3都不是分配格。{a,b,c,d,e}是L1的子格，并且同构于钻石格。{a,b,c,e,f}是L2的子格，并且同构于五角格。{a,c,b,e,f}是L3的子格，也同构于钻石格。格的全下界和全上界定义11.6设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。有界格定义11.7设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关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。有界格的性质定理（补充）设L,∧,∨,0,1是有界格，则a∈L有a∧0＝0a∨0＝aa∧1＝aa∨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互为对偶命题。有界格中的补元定义11.8设L,∧,∨,0,1是有界格，a∈L，若存在b∈L使得a∧b＝0和a∨b＝1成立，则称b是a的补元。说明若b是a的补元，那么a也是b的补元。换句话说，a和b互为补元。例11.9考虑下图中的四个格。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。有界格中补元的说明在任何有界格中，全下界0与全上界1互补。对于其他元素，可能存在补元，也可能不存在补元。如果存在，可能是唯一的，也可能是多个补元。对于有界分配格，如果它的元素存在补元，