9/25/2017 2:13 PM,Discrete Math. , Chen Chen,1,,离散数学Discrete Mathematics,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,2,第十一章 格与布尔代数,主要内容格的定义及性质 子格分配格、有补格布尔代数,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,3,11.1 格的定义与性质,定义11.1 设是偏序集，如果x,yS，{x,y}都有最小上界和最大下界，则称S关于偏序≼作成一个格. 求{x,y} 最小上界和最大下界看成 x 与 y 的二元运算∨和∧，,例1 设n是正整数，Sn是n的正因子的集合. D为整除关系，则偏序集构成格. x,y∈Sn，x∨y是lcm(x,y)，即x与y的最小公倍数. x∧y是gcd(x,y)，即x与y的最大公约数.,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,4,图2,例2 判断下列偏序集是否构成格，并说明理由. (1) ，其中P(B)是集合B的幂集. (2) ，其中Z是整数集，≤为小于或等于关系. (3) 偏序集的哈斯图分别在下图给出.,实例,(1) 幂集格. x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y. (2) 是格. x,y∈Z，x∨y = max(x,y)，x∧y = min(x,y)，(3) 都不是格. 可以找到两个结点缺少最大下界或最小上界,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,5,实例：子群格,例3 设G是群，L(G)是G 的所有子群的集合. 即 L(G) = { H | H≤G }，对任意的H1, H2∈L(G)，H1∩H2是G 的子群，是由H1∪H2生成的子群（即包含着H1∪H2的最小子群）.在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格. 在 L(G)中， H1∧H2 就是 H1∩H2 H1∨H2 就是 ,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,6,格的性质：对偶原理,定义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，那么对一切格L都有 a,b∈L, a∨b≽a 注意：对偶是相互的，即 ( f*)*= f,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,7,格的性质：算律,定理11.1 设是格, 则运算∨和∧适合交换律、结合律、幂等律和吸收律, 即(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,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,8,证明,(1) a∨b是{ a, b }的最小上界, b∨a是{ b, a }的最小上界. 由于{ a, b } = { b, a }, 所以 a∨b = b∨a. 由对偶原理, a∧b = b∧a.,(2) 由最小上界的定义有 (a∨b)∨c≽a∨b≽a (1) (a∨b)∨c≽a∨b≽b (2) (a∨b)∨c≽c (3)由式(2)和(3)有 (a∨b)∨c≽b∨c (4)由式(1)和(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),9/25/2017 2:13 PM,Discrete Math. , Chen Chen,9,证明,(3) 显然 a ≼ a∨a, 又由 a ≼ a 可得 a∨a ≼a. 根据反对称性有a∨a = a . 由对偶原理, a∧a = a 得证. (4) 显然 a∨(a∧b)≽ a (5) 由 a ≼a, a∧b ≼ a 可得 a∨(a∧b) ≼a (6) 由式(5)和(6) 可得 a∨(a∧b) = a, 根据对偶原理, a∧(a∨b) = a,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,10,格的性质：序与运算的关系,定理11.2 设L是格, 则a,b∈L有 a ≼ b a∧b = a a∨b = b,证 (1) 先证 a ≼ b a∧b = a 由 a ≼ a 和 a ≼ b 可知 a 是{ a,b }的下界, 故 a ≼ a∧b.显然有a∧b ≼ a. 由反对称性得 a∧b = a.(2) 再证 a∧b = a a∨b = b根据吸收律有 b = b∨(b∧a) 由 a∧b = a 和上面的等式得 b = b∨a, 即 a∨b = b.(3) 最后证 a∨b = b a≼b由 a ≼ a∨b 得 a ≼ a∨b = b,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,11,格的性质：保序,定理11.3 设L是格, a,b,c,d∈L，若a ≼ b 且 c ≼ d, 则 a∧c ≼ b∧d, a∨c ≼ b∨d,例4 设L是格, 证明a,b,c∈L有 a∨(b∧c) ≼ (a∨b)∧(a∨c).,证 a∧c ≼ a ≼ b, a∧c ≼ c ≼ d 因此 a∧c ≼ b∧d. 同理可证 a∨c ≼ b∨d,证 由 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)注意：一般说来, 格中的∨和∧运算不满足分配律.,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,12,格作为代数系统的定义,定理11.4 设是具有两个二元运算的代数系统, 若对于∗和◦运算适合交换律、结合律、吸收律, 则可以适当定义S中的偏序 ≼,使得 构成格, 且a,b∈S 有 a∧b = a∗b, a∨b = a◦b.证明省略. 根据定理11.4, 可以给出格的另一个等价定义.,定义11.3 设是代数系统, ∗和◦是二元运算, 如果∗和◦满足交换律、结合律和吸收律, 则构成格.,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,13,子格及其判别法,定义11.4 设是格, S是L的非空子集, 若S关于L中的运算∧和∨仍构成格, 则称S是L的子格.,例5 设格L如图所示. 令 S1={a, e, f, g}, S2={a, b, e, g}S1不是L的子格, 因为e, fS1 但 e∧f = cS1.S2是L的子格.,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,14,11.2 分配格、有补格与布尔代数,定义11.5 设是格, 若a,b,c∈L,有 a∧(b∨c) = (a∧b)∨(a∧c) a∨(b∧c) = (a∨b)∧(a∨c) 则称L为分配格.注意：可以证明以上两个条件互为充分必要条件,L1 和 L2 是分配格, L3 和 L4不是分配格. 称 L3为钻石格, L4为五角格.,实例,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,15,分配格的判别及性质,定理11.5 设L是格, 则L是分配格当且仅当L不含有与钻石格或五角格同构的子格.证明省略.推论 (1) 小于五元的格都是分配格.(2) 任何一条链都是分配格. 例6 说明图中的格是否为分配格, 为什么？,解 都不是分配格. { a,b,c,d,e }是L1的子格, 同构于钻石格{ a,b,c,e,f }是L2的子格, 同构于五角格；{ a,c,b,e,f } 是L3的子格 同构于钻石格.,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,16,有界格的定义,定义11.6 设L是格,(1) 若存在a∈L使得x∈L有 a ≼ x, 则称a为L的全下界(2) 若存在b∈L使得x∈L有 x ≼ b, 则称b为L的全上界 说明：格L若存在全下界或全上界, 一定是惟一的. 一般将格L的全下界记为0, 全上界记为1.定义11.7 设L是格,若L存在全下界和全上界, 则称L 为有界格, 一般将有界格L记为.,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,17,,定理11.6 设是有界格, 则a∈L有 a∧0 = 0, a∨0 = a, a∧1 = a, a∨1 = 1,注意：有限格L={a1,a2,…,an}是有界格, a1∧a2∧…∧an是L的全下界, a1∨a2∨…∨an是L的全上界. 0是关于∧运算的零元,∨运算的单位元；1是关于∨运算的零元,∧运算的单位元. 对于涉及到有界格的命题, 如果其中含有全下界0或全上界1, 在求该命题的对偶命题时, 必须将0替换成1, 而将1替换成0.,有界格的性质,9/25/2017 2:13 PM,Discrete Math. , Chen Chen,18,有界格中的补元及实例,定义11.8 设是有界格, a∈L, 若存在b∈L 使得 a∧b = 0 和 a∨b = 1 成立, 则称b是a的补元.注意：若b是a的补元, 那么a也是b的补元. a和b互为补元.,。
