第三部分代数系统.ppt

第三部分 代数系统 ——格 西安工程大学 计算机科学学院 王爱丽 一、主要内容 格的定义 格的性质 子格 特殊格：分配格、有界格、有补格、布尔代数 二、基本要求 能够判别给定偏序集或者代数系统是否构成格 能够证明格中的等式和不等式 能判别格L的子集S是否构成子格 能够判别给定的格是否为分配格、有补格 能够判别布尔代数并证明布尔代数中的等式 格的定义 定义11.1 设S, ?是偏序集，如果?x,y?S，{x,y}都有最小上界和最大下界，则称S关于偏序?作成一个格（lattice）。 求{x,y} 最小上界和最大下界看成 x 与 y 的二元运算∨和∧。通常，将∧称为保交运算，将∨称为保联运算。 例1 设n是正整数，Sn是n的正因子的集合. D为整除关系，则偏序集Sn,D构成格. ?x,y∈Sn，x∨y是lcm(x,y)，即x与y的最小公倍数. x∧y是gcd(x,y)，即x与y的最大公约数. 例2 判断下列偏序集是否构成格， 偏序集的哈斯图分别在下图给出. 子格 定义11.2 设L,∧,∨是格, S是L的非空子集, 若S关于L中的运算∧和∨仍构成格, 则称S是L的子格. 例3 设格L如图所示. 令 S1={a, e, f, g}, S2={a, b, e, g} S1不是L的子格, 因为e, f?S1 但 e∧f = c?S1. S2是L的子格. 分配格 定义11.3 设L,∧,∨是格, 若?a,b,c∈L,有 a∧(b∨c) = (a∧b)∨(a∧c)   a∨(b∧c) = (a∨b)∧(a∨c) 则称L为分配格（distributive lattice）. 注意：可以证明以上两个条件互为充分必要条件 L1 和 L2 是分配格, L3 和 L4不是分配格. 称 L3为钻石格, L4为五角格. 例4 判断下面哪些是分配格 L3中， b∧(c∨d) ≠ (b∧c)∨(b∧d), L4中， c∨(b∧d) = (c∨b)∧(c∨d) 分配格的判别 定理11.4 设L是格, 则L是分配格当且仅当L不含有与钻石格或五角格同构的子格. 推论 (1) 小于五元的格都是分配格. (2) 任何一条链都是分配格.? 例5 说明图中的格是否为分配格, 为什么？ 解 都不是分配格. { a,b,c,d,e }是L1的子格, 同构于钻石格 { a,b,c,e,f }是L2的子格, 同构于五角格； { a,c,b,e,f } 是L3的子格 ，同构于钻石格. 有界格 定义11.4 设L是格, (1) 若存在a∈L使得?x∈L有 a ? x, 则称a为L的全下界 (2) 若存在b∈L使得?x∈L有 x ? b, 则称b为L的全上界? 说明： 格L若存在全下界或全上界, 一定是惟一的. 一般将格L的全下界记为0, 全上界记为1. 定义11.5 设L是格,若L存在全下界和全上界, 则称L 为有界 格（bounded lattice）, 一般将有界格L记为L,∧,∨,0,1. 有界格的性质 定理11.5 设L,∧,∨,0,1是有界格, 则?a∈L有a∧0 = 0, a∨0 = a, a∧1 = a, a∨1 = 1 有界格中的补元 定义11.6 设L,∧,∨,0,1是有界格, a∈L, 若存在b∈L 使得 a∧b = 0 和 a∨b = 1 成立, 则称b是a的补元. 注意： 若b是a的补元, 那么a也是b的补元. a和b互为补元. 一个元素可以有几个补元。但0是1的唯一补，1也是0的唯一补。 例6 考虑下图中的格. 针对不同的元素，求出所有的补元. 有界分配格的补元惟一性 定理11.6 设L,∧,∨,0,1是有界分配格. 若L中元素 a 存在补元, 则这个补元是唯一的. 证明：假设 c 是 a 的补元, 则有  a∨c = 1, a∧c = 0, 又知 b 是 a 的补元, 故   a∨b = 1, a∧b = 0  从而得到 a∨c = a∨b, a∧c = a∧b, 由于L是分配格, b = c. 注意： 在任何有界格中, 全下界0与全上界1互补. 对于一般元素, 可能存在补元, 也可能不存在补元. 如果存在补元, 可能是惟一的, 也可能是多个补元. 对于有界分配格, 如果元素存在补元, 一定是惟一的. 有补格 定义11.7 设L,∧,∨,0,1是有界格, 若L中所有元素都有补元存在, 则称L为有补格（complemented lattice）