第三部分 代数系统 ——格 西安工程大学 计算机科学学院 王爱丽.

Presentation on theme: "第三部分 代数系统 ——格 西安工程大学 计算机科学学院 王爱丽."— Presentation transcript:

1 第三部分 代数系统 ——格 西安工程大学 计算机科学学院 王爱丽

2 一、主要内容 格的定义 格的性质 子格 特殊格：分配格、有界格、有补格、布尔代数

3 二、基本要求 能够判别给定偏序集或者代数系统是否构成格 能够证明格中的等式和不等式 能判别格L的子集S是否构成子格
能够判别给定的格是否为分配格、有补格 能够判别布尔代数并证明布尔代数中的等式

4 格的定义 求{x,y} 最小上界和最大下界看成 x 与 y 的二元运算∨和∧。 通常，将∧称为保交运算，将∨称为保联运算。
定义11.1 设<S, ≼>是偏序集，如果x,yS，{x,y}都有最小上 界和最大下界，则称S关于偏序≼作成一个格（lattice）。 求{x,y} 最小上界和最大下界看成 x 与 y 的二元运算∨和∧。 通常，将∧称为保交运算，将∨称为保联运算。

5 例1 设n是正整数，Sn是n的正因子的集合. D为整除关系，则偏序集<Sn,D>构成格
例1 设n是正整数，Sn是n的正因子的集合. D为整除关系，则偏序集<Sn,D>构成格. x,y∈Sn，x∨y是lcm(x,y)，即x与y的最小公倍数. x∧y是gcd(x,y)，即x与y的最大公约数.

6 例2 判断下列偏序集是否构成格， 偏序集的哈斯图分别在下图给出.

7 子格 定义11.2 设<L,∧,∨>是格, S是L的非空子集, 若S关于L中的运算∧和∨仍构成格, 则称S是L的子格.
S1={a, e, f, g}, S2={a, b, e, g} S1不是L的子格, 因为e, fS1 但 e∧f = cS1. S2是L的子格.

8 分配格 定义11.3 设<L,∧,∨>是格, 若a,b,c∈L,有  a∧(b∨c) = (a∧b)∨(a∧c)
则称L为分配格（distributive lattice）. 注意：可以证明以上两个条件互为充分必要条件

9 例4 判断下面哪些是分配格 L3中， b∧(c∨d) ≠ (b∧c)∨(b∧d), L4中， c∨(b∧d) = (c∨b)∧(c∨d) L1 和 L2 是分配格, L3 和 L4不是分配格. 称 L3为钻石格, L4为五角格.

10 分配格的判别 定理11.4 设L是格, 则L是分配格当且仅当L不含有与钻石格或五角格同构的子格. 推论 (1) 小于五元的格都是分配格.
(2) 任何一条链都是分配格. 

11 例5 说明图中的格是否为分配格, 为什么？ 解 都不是分配格. { a,b,c,d,e }是L1的子格, 同构于钻石格 { a,b,c,e,f }是L2的子格, 同构于五角格； { a,c,b,e,f } 是L3的子格 ，同构于钻石格.

12 有界格 定义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>.

13 有界格的性质 定理11.5 设<L,∧,∨,0,1>是有界格, 则a∈L有 a∧0 = 0, a∨0 = a, a∧1 = a, a∨1 = 1

14 有界格中的补元 定义11.6 设<L,∧,∨,0,1>是有界格, a∈L, 若存在b∈L 使得  a∧b = 0 和 a∨b = 成立, 则称b是a的补元. 注意： 若b是a的补元, 那么a也是b的补元. a和b互为补元. 一个元素可以有几个补元。但0是1的唯一补，1也是0的唯一补。

15 例6 考虑下图中的格. 针对不同的元素，求出所有的补元.

16 有界分配格的补元惟一性 定理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.

17 注意： 在任何有界格中, 全下界0与全上界1互补. 对于一般元素, 可能存在补元, 也可能不存在补元. 如果存在补元, 可能是惟一的, 也可能是多个补元. 对于有界分配格, 如果元素存在补元, 一定是惟一的.

18 有补格 定义11.7 设<L,∧,∨,0,1>是有界格, 若L中所有元素都有补元存在, 则称L为有补格（complemented lattice）. 例7 图中的L2, L3和L4是有补格, L1不是有补格.

19 布尔格 定义11.8 布尔格（Boolean algebra）： 如果一个格既是有补格，又 是分配格, 则称它为布尔格.
定义11.9 布尔代数（Boolean lattice）：由布尔格<L,≤ >定义的包括 保交运算、保联运算和补运算的代数系统<L,∧,∨,, 0, 1>, 为求补运算， 称为布尔代数。

20 例8 设 S110 = {1, 2, 5, 10, 11, 22, 55, 110}是110的正因子集合，gcd表示求最大公约数的运算，lcm表示求最小公倍数的运算，问<S110, gcd, lcm>是否构成布尔代数？为什么？ 解 (1) 不难验证S110关于gcd 和 lcm 运算构成格. (略) (2) 验证分配律 x, y, z∈S110 有  gcd(x, lcm(y, z)) = lcm(gcd(x, y), gcd(x, z)) (3) 验证它是有补格, 1作为S110中的全下界, 110为全上界,1和110互 为补元, 2和55互为补元, 5和22互为补元, 10和 11互为补元, 从而证明 了<S110, gcd, lcm>为布尔代数.

21 例 9 设B为任意集合, 证明B的幂集格<P(B), ∩,∪, ~,  , B>
构成布尔代数, 称为集合代数. 证 (1) P(B)关于∩和∪构成格, 因为∩和∪运算满足交换律, 结合律和吸收律. (2) 由于∩和∪互相可分配, 因此P(B)是分配格. (3) 全下界是空集, 全上界是B. (4) 根据绝对补的定义, 取全集为B,  x∈P(B), ~x是x的补元. 从而证明P(B)是有补分配格, 即布尔代数.

22 布尔代数的性质 定理11.7 设<B,∧,∨, , 0, 1>是布尔代数, 则 (1) a∈B, (a) = a .
(2) a,b∈B, (a∧b) = a∨b, (a∨b) = a∧b （德摩根律）

23 证 (1) (a)是a的补元, a也是a的补元. 由补元惟一性得(a)=a. (2) 对任意a, b∈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. 注意：德摩根律对有限个元素也是正确的.

24 布尔代数的另一种定义 定义11.10 设<B, ∗,◦>是代数系统, ∗和◦是二元运算. 若∗和◦运 算满足：
(1) 交换律, 即a,b∈B有a∗b = b∗a, a◦b = b◦a (2) 分配律, 即a,b,c∈B有 a∗(b◦c) = (a∗b)◦(a∗c),  a◦(b∗c) = (a◦b) ∗ (a◦c)  (3) 同一律, 即存在0,1∈B, 使得a∈B有a ∗1 = a, a◦0 = a (4) 补元律, 即a∈B, 存在 a∈B 使得 a ∗a = 0, a◦a = 1 则称 <B,∗,◦>是一个布尔代数. 可以证明，布尔代数的两种定义是等价的.

25 下图给出了 1 元, 2 元, 4 元和 8 元的布尔代数.

26 第十一章 习题课 基本要求 能够判别给定偏序集或者代数系统是否构成格 能够证明格中的等式和不等式 能判别格L的子集S是否构成子格
第十一章 习题课 基本要求 能够判别给定偏序集或者代数系统是否构成格 能够证明格中的等式和不等式 能判别格L的子集S是否构成子格 能够判别给定的格是否为分配格、有补格 能够判别布尔代数并证明布尔代数中的等式

27 e a b c d 1．求图中格的所有子格. 1元子格：{ a },{ b },{ c },{ d },{ e }；
2元子格：{ a, b },{ a, c },{ a, d }, { a, e },{ b, c },{ b, d }, { b, e },{ c, e },{ d, e }； 3元子格：{ a, b, c },{ a, b, d }, { a, b, e },{ a, c, e }, { a, d, e },{ b, c, e }, { b, d, e }； 4元子格：{ a, b, c, e },{ a, b, d, e }, { b, c, d, e }； 5元子格： { a, b, c, d, e } e a b c d

28 2.判别下述格L是否为分配格. L L L3 L1不是分配格, 因为它含有与钻石格同构的子格. L2和L3不是分配格, 因为它们含有与五角格同构的子格.

29 L3中, a与h互为补元, b的补元为d；c的补元为d；d的补元为b, c, g；g的补元为d. L2与L3是有补格.
L L L3 3.针对下图，求出每个格的补元并说明它们是否为有补格 L1中, a与h互为补元, 其他元素没补元. L2中, a与g互为补元. b的补元为c, d, f；c的补元为b, d, e, f；d的补元为b, c, e；e的补元为c, d, f；f的补元为b, c, e. L3中, a与h互为补元, b的补元为d；c的补元为d；d的补元为b, c, g；g的补元为d. L2与L3是有补格.

30 代数系统部分 习题课 ——第九、十、十一章习题课