格 - Discrete Mathematics

Transcription

1 格 Discrete Mathematics 黄正华 数学与统计学院 武汉大学 December 3, 2012 黄正华 ( 武汉大学 ) 格 December 3, / 103

2 主要内容 格 (Lattice): 一个偏序集, 其任意两个元素都有最 小 上 界 和最 大 下 界 特殊的格 : 分配格, 有补格 布尔代数 : 有补分配格 黄正华 ( 武汉大学 ) 格 December 3, / 103

3 本章概念关系图 全序集 布尔格 分配格 有补格 模格 有界格 格 偏序集 黄正华 ( 武汉大学 ) 格 December 3, / 103

4 1 格的定义 2 子格与格同态 3 几种特殊的格 4 布尔代数 5 有限布尔代数的表示定理 黄正华 ( 武汉大学 ) 格 December 3, / 103

5 1 格的定义 2 子格与格同态 3 几种特殊的格 4 布尔代数 5 有限布尔代数的表示定理 黄正华 ( 武汉大学 ) 格 December 3, / 103

6 本节主要内容 : 1 格的两种定义 ; 2 格的基本性质 ; 3 格与代数系统间的关系 黄正华 ( 武汉大学 ) 格 December 3, / 103

7 回顾 : Definition 11 ( 偏序 ) 如果集合 A 上的关系 具有 1 自反性, 2 反对称性, 3 传递性 则称关系 为 A 上偏序关系 A, 称为偏序集 黄正华 ( 武汉大学 ) 格 December 3, / 103

8 Example 12 设 X = {1, 2, 3, 4, 6, 12}, Y = {2, 3, 6, 12, 24, 36} 集合 X 和 Y 关于整除关 系 构成两个偏序集 : X,, Y, (a) X, (b) Y, 黄正华 ( 武汉大学 ) 格 December 3, / 103

9 Example 12 设 X = {1, 2, 3, 4, 6, 12}, Y = {2, 3, 6, 12, 24, 36} 集合 X 和 Y 关于整除关 系 构成两个偏序集 : X,, Y, (a) X, (b) Y, X, 中 每两个元素构成的集合 都有最大下界和最小上界 Y, 无此特点 黄正华 ( 武汉大学 ) 格 December 3, / 103

10 格的定义 Definition 13 ( 格 ) 如果偏序集 A, 中任意两个元素都有最 小 上 界 和最 大 下 界, 则称 A, 是格 (lattice) 黄正华 ( 武汉大学 ) 格 December 3, / 103

11 格的定义 Definition 13 ( 格 ) 如果偏序集 A, 中任意两个元素都有最 小 上 界 和最 大 下 界, 则称 A, 是格 (lattice) lattice: 木格, 窗格 黄正华 ( 武汉大学 ) 格 December 3, / 103

12 格的定义 Definition 13 ( 格 ) 如果偏序集 A, 中任意两个元素都有最 小 上 界 和最 大 下 界, 则称 A, 是格 (lattice) a 和 b 的最小上界 : lub{a, b} (least upper bound) a 和 b 的最大下界 : glb{a, b} (greatest lower bound) 黄正华 ( 武汉大学 ) 格 December 3, / 103

13 格的典型例子 Example 14 偏序集 P(S), 是格 : 任意 S 1, S 2 P(S), 它们的最大下界为 S 1 S 2 ; 最小上界为 S 1 S 2 黄正华 ( 武汉大学 ) 格 December 3, / 103

14 格的典型例子 Example 14 偏序集 P(S), 是格 : 任意 S 1, S 2 P(S), 它们的最大下界为 S 1 S 2 ; 最小上界为 S 1 S 2 这是格的一个典型例子 关于格的很多性质, 都可以借助这个例子理解 黄正华 ( 武汉大学 ) 格 December 3, / 103

15 格的典型例子 Example 14 偏序集 P(S), 是格 : 任意 S 1, S 2 P(S), 它们的最大下界为 S 1 S 2 ; 最小上界为 S 1 S 2 这是格的一个典型例子 关于格的很多性质, 都可以借助这个例子理解 Example 15 偏序集 Z +, 是格 : Z + 中任意两个元素的最小公倍数 最大公约数就是这两个元素的最小上界和 最大下界 黄正华 ( 武汉大学 ) 格 December 3, / 103

16 格的等价定义 任意两个元素有最小上界 最大下界 任意有 限 个 元素有最小上界 最大下界 黄正华 ( 武汉大学 ) 格 December 3, / 103

17 格的等价定义 任意两个元素有最小上界 最大下界 任意有 限 个 元素有最小上界 最大下界 Definition 16 偏序集 A, 是一个格, 当且仅当 A 中任意非空有 限 子集 S 有最小上界 最大下界 黄正华 ( 武汉大学 ) 格 December 3, / 103

18 格的等价定义 任意两个元素有最小上界 最大下界 任意有 限 个 元素有最小上界 最大下界 Definition 16 偏序集 A, 是一个格, 当且仅当 A 中任意非空有 限 子集 S 有最小上界 最大下界 其中要求子集元素个数 有限 是重要的, 不能是 任意的非空子集 黄正华 ( 武汉大学 ) 格 December 3, / 103

19 格的等价定义 任意两个元素有最小上界 最大下界 任意有 限 个 元素有最小上界 最大下界 Definition 16 偏序集 A, 是一个格, 当且仅当 A 中任意非空有 限 子集 S 有最小上界 最大下界 其中要求子集元素个数 有限 是重要的, 不能是 任意的非空子集 比如 N, 是一个格, 但不是任意的非空子集都有最小上界 最大下 界 N 就是它自己的一个子集, 它没有最小上界 黄正华 ( 武汉大学 ) 格 December 3, / 103

20 Definition 17 设 A, 是格, 在 A 上定义两个二元运算 和 : 对任意 a, b A, 诱 导 的 代 数 系 统 a b lub{a, b}, (1) a b glb{a, b} (2) 则二元运算 和 分别称为并运算和交运算 ; 称 A,, 是格 A, 所 黄正华 ( 武汉大学 ) 格 December 3, / 103

21 Definition 17 设 A, 是格, 在 A 上定义两个二元运算 和 : 对任意 a, b A, 诱 导 的 代 数 系 统 a b lub{a, b}, (1) a b glb{a, b} (2) 则二元运算 和 分别称为并运算和交运算 ; 称 A,, 是格 A, 所 Example 18 在格 P(S), 诱导的代数系统中, 运算 和 就是普通的并 交运算 : 任 意 S 1, S 2 P(S), 有 S 1 S 2 = S 1 S 2, S 1 S 2 = S 1 S 2 黄正华 ( 武汉大学 ) 格 December 3, / 103

22 Definition 17 设 A, 是格, 在 A 上定义两个二元运算 和 : 对任意 a, b A, 诱 导 的 代 数 系 统 a b lub{a, b}, (1) a b glb{a, b} (2) 则二元运算 和 分别称为并运算和交运算 ; 称 A,, 是格 A, 所 Example 18 在格 Z, 或 N, 诱导的代数系统中, 运算 和 就是普通的取大 取小 运算 比如, 任意的 a, b N, 有 a b = max{a, b}, a b = min{a, b} 黄正华 ( 武汉大学 ) 格 December 3, / 103

23 Definition 17 设 A, 是格, 在 A 上定义两个二元运算 和 : 对任意 a, b A, 诱 导 的 代 数 系 统 a b lub{a, b}, (1) a b glb{a, b} (2) 则二元运算 和 分别称为并运算和交运算 ; 称 A,, 是格 A, 所 Example 18 对于格 Z +, 来说, 其诱导的代数系统 Z +,, 中的二元运算 和 分别 为 : 对任意的 a, b Z + 有 a b = LCM(a, b), (least common mutiple, 最小公倍数 ) a b = GCD(a, b) (greatest common divisor, 最大公约数 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

24 Definition 17 设 A, 是格, 在 A 上定义两个二元运算 和 : 对任意 a, b A, 诱 导 的 代 数 系 统 a b lub{a, b}, (1) a b glb{a, b} (2) 则二元运算 和 分别称为并运算和交运算 ; 称 A,, 是格 A, 所 这个定义表明, 从格出发, 可以构造一个代数系统 这也说明了格这类特殊 偏序集的重要性 黄正华 ( 武汉大学 ) 格 December 3, / 103

25 格的对偶原理 设 A, 是偏序集, 用 表示偏序关系 的逆关系, 则 A, 也是偏序集 黄正华 ( 武汉大学 ) 格 December 3, / 103

26 格的对偶原理 设 A, 是偏序集, 用 表示偏序关系 的逆关系, 则 A, 也是偏序集 A, 与 A, 的哈斯图是互为颠倒的 黄正华 ( 武汉大学 ) 格 December 3, / 103

27 格的对偶原理 设 A, 是偏序集, 用 表示偏序关系 的逆关系, 则 A, 也是偏序集 A, 与 A, 的哈斯图是互为颠倒的 称 A,, A, 为彼 此 对 偶 的偏序集 黄正华 ( 武汉大学 ) 格 December 3, / 103

28 格的对偶原理 设 A, 是偏序集, 用 表示偏序关系 的逆关系, 则 A, 也是偏序集 A, 与 A, 的哈斯图是互为颠倒的 称 A,, A, 为彼 此 对 偶 的偏序集 如果其中一个是格, 则另一个也是格 黄正华 ( 武汉大学 ) 格 December 3, / 103

29 格的对偶原理 设 A, 是偏序集, 用 表示偏序关系 的逆关系, 则 A, 也是偏序集 A, 与 A, 的哈斯图是互为颠倒的 称 A,, A, 为彼 此 对 偶 的偏序集 如果其中一个是格, 则另一个也是格 由格 A, 诱导的代数系统的并 ( 交 ) 运算, 正好是由格 A, 诱导的代数系统的交 ( 并 ) 运算 黄正华 ( 武汉大学 ) 格 December 3, / 103

30 格的对偶原理 设 A, 是偏序集, 用 表示偏序关系 的逆关系, 则 A, 也是偏序集 A, 与 A, 的哈斯图是互为颠倒的 称 A,, A, 为彼 此 对 偶 的偏序集 如果其中一个是格, 则另一个也是格 由格 A, 诱导的代数系统的并 ( 交 ) 运算, 正好是由格 A, 诱导的代 数系统的交 ( 并 ) 运算 Theorem 18 ( 对偶原理 ) 设 P 是对任意格都为真的命题, 将 P 中的,, 分别换成,, 得命题 Q, 则 Q 对任意格也是真的命题 (Q 称为 P 的对偶命题 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

31 格的基本性质 Theorem 19 设 A, 是格, 对任意 a, b A, 有 a a b, b a b, a b a, a b b 黄正华 ( 武汉大学 ) 格 December 3, / 103

32 格的基本性质 Theorem 19 设 A, 是格, 对任意 a, b A, 有 a a b, b a b, a b a, a b b 分析由, 的定义即得上述结论 如图 : a b a b a b 黄正华 ( 武汉大学 ) 格 December 3, / 103

33 格的基本性质 Theorem 19 设 A, 是格, 对任意 a, b A, 有 a a b, b a b, 证 a b a, a b b 因为 a b 是 a 和 b 的 ( 最小 ) 上界, 所以 a a b, b a b 黄正华 ( 武汉大学 ) 格 December 3, / 103

34 格的基本性质 Theorem 19 设 A, 是格, 对任意 a, b A, 有 a a b, b a b, 证 a b a, a b b 因为 a b 是 a 和 b 的 ( 最小 ) 上界, 所以 a a b, b a b 由对偶原理, 即得 a b a, a b b 黄正华 ( 武汉大学 ) 格 December 3, / 103

35 Theorem 110 设 A, 是格, a, b, c, d A, 若 a b, c d, 则 a c b d, (3) a c b d (4) 黄正华 ( 武汉大学 ) 格 December 3, / 103

36 Theorem 110 设 A, 是格, a, b, c, d A, 若 a b, c d, 则 a c b d, (3) a c b d (4) 证 已知 a b, c d, 又 b b d, d b d, 黄正华 ( 武汉大学 ) 格 December 3, / 103

37 Theorem 110 设 A, 是格, a, b, c, d A, 若 a b, c d, 则 a c b d, (3) a c b d (4) 证 已知 a b, c d, 又 b b d, d b d, 由传递性可得 a b d, c b d 黄正华 ( 武汉大学 ) 格 December 3, / 103

38 Theorem 110 设 A, 是格, a, b, c, d A, 若 a b, c d, 则 a c b d, (3) a c b d (4) 证 已知 a b, c d, 又 b b d, d b d, 由传递性可得 a b d, c b d 这说明 b d 是 a 和 c 的一个上界, 黄正华 ( 武汉大学 ) 格 December 3, / 103

39 Theorem 110 设 A, 是格, a, b, c, d A, 若 a b, c d, 则 a c b d, (3) a c b d (4) 证 已知 a b, c d, 又 b b d, d b d, 由传递性可得 a b d, c b d 这说明 b d 是 a 和 c 的一个上界, 但 a c 是 a 和 c 的最小上界, 黄正华 ( 武汉大学 ) 格 December 3, / 103

40 Theorem 110 设 A, 是格, a, b, c, d A, 若 a b, c d, 则 a c b d, (3) a c b d (4) 证 已知 a b, c d, 又 b b d, d b d, 由传递性可得 a b d, c b d 这说明 b d 是 a 和 c 的一个上界, 但 a c 是 a 和 c 的最小上界, 所以 a c b d 黄正华 ( 武汉大学 ) 格 December 3, / 103

41 Theorem 110 设 A, 是格, a, b, c, d A, 若 a b, c d, 则 a c b d, (3) a c b d (4) 证 已知 a b, c d, 又 b b d, d b d, 由传递性可得 a b d, c b d 这说明 b d 是 a 和 c 的一个上界, 但 a c 是 a 和 c 的最小上界, 所以 a c b d 类似地可以证明 a c b d 黄正华 ( 武汉大学 ) 格 December 3, / 103

42 推论 设 A, 是格, a, b, c A, 若 b c, 则 这个性质称为格的保序性 a b a c, a b a c 黄正华 ( 武汉大学 ) 格 December 3, / 103

43 推论 设 A, 是格, a, b, c A, 若 b c, 则 这个性质称为格的保序性 证已知 b c, a b a c, a b a c 黄正华 ( 武汉大学 ) 格 December 3, / 103

44 推论 设 A, 是格, a, b, c A, 若 b c, 则 这个性质称为格的保序性 证已知 b c, 又 a a, a b a c, a b a c 黄正华 ( 武汉大学 ) 格 December 3, / 103

45 推论 设 A, 是格, a, b, c A, 若 b c, 则 这个性质称为格的保序性 a b a c, a b a c 证 已知 b c, 又 a a, 所以 a b a c 黄正华 ( 武汉大学 ) 格 December 3, / 103

46 推论 设 A, 是格, a, b, c A, 若 b c, 则 这个性质称为格的保序性 a b a c, a b a c 证 已知 b c, 又 a a, 所以 a b a c 同理有 a b a c 黄正华 ( 武汉大学 ) 格 December 3, / 103

47 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 黄正华 ( 武汉大学 ) 格 December 3, / 103

48 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 证先证明 a b a b = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

49 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 证先证明 a b a b = a 设 a b 黄正华 ( 武汉大学 ) 格 December 3, / 103

50 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 证先证明 a b a b = a 设 a b 又 a a, 则 a 是 a 和 b 的下界, 而 a b 是最大下界, 得 黄正华 ( 武汉大学 ) 格 December 3, / 103

51 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 证先证明 a b a b = a 设 a b 又 a a, 则 a 是 a 和 b 的下界, 而 a b 是最大下界, 得 a a b 黄正华 ( 武汉大学 ) 格 December 3, / 103

52 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 证先证明 a b a b = a 设 a b 又 a a, 则 a 是 a 和 b 的下界, 而 a b 是最大下界, 得 a a b 又 a b a, 黄正华 ( 武汉大学 ) 格 December 3, / 103

53 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 证先证明 a b a b = a 设 a b 又 a a, 则 a 是 a 和 b 的下界, 而 a b 是最大下界, 得 a a b 又 所以 a b a, a b = a ( 反对称性 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

54 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 证先证明 a b a b = a 设 a b 又 a a, 则 a 是 a 和 b 的下界, 而 a b 是最大下界, 得 a a b 又 a b a, 所以 a b = a ( 反对称性 ) 反之, 假定 a b = a, 又 a b b, 所以 黄正华 ( 武汉大学 ) 格 December 3, / 103

55 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 证先证明 a b a b = a 设 a b 又 a a, 则 a 是 a 和 b 的下界, 而 a b 是最大下界, 得 a a b 又 a b a, 所以 a b = a ( 反对称性 ) 反之, 假定 a b = a, 又 a b b, 所以 a b 黄正华 ( 武汉大学 ) 格 December 3, / 103

56 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 证先证明 a b a b = a 设 a b 又 a a, 则 a 是 a 和 b 的下界, 而 a b 是最大下界, 得 a a b 又 a b a, 所以 a b = a ( 反对称性 ) 反之, 假定 a b = a, 又 a b b, 所以 a b 因此, a b a b 黄正华 ( 武汉大学 ) 格 December 3, / 103

57 Theorem 111 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 a b a b = a a b = b 证先证明 a b a b = a 设 a b 又 a a, 则 a 是 a 和 b 的下界, 而 a b 是最大下界, 得 a a b 又 a b a, 所以 a b = a ( 反对称性 ) 反之, 假定 a b = a, 又 a b b, 所以 a b 因此, a b a b 其他的证明类似 黄正华 ( 武汉大学 ) 格 December 3, / 103

58 Theorem 112 设 A, 是一个格, 那么, 对于任意的 a, b A, 有 此时的哈斯图为 : a b a b = a a b = b b a 小 大 = 小, 小 大 = 大 黄正华 ( 武汉大学 ) 格 December 3, / 103

59 格的基本性质 Theorem 113 设 A, 是格, 由格 A, 所诱导的代数系统为 A,,, 则对任意 的 a, b, c, d A, 有 1 a b = b a, } ( 交换律 ) a b = b a 黄正华 ( 武汉大学 ) 格 December 3, / 103

60 格的基本性质 Theorem 113 设 A, 是格, 由格 A, 所诱导的代数系统为 A,,, 则对任意 的 a, b, c, d A, 有 1 a b = b a, } ( 交换律 ) a b = b a } a (b c) = (a b) c, 2 ( 结合律 ) a (b c) = (a b) c 黄正华 ( 武汉大学 ) 格 December 3, / 103

61 格的基本性质 Theorem 113 设 A, 是格, 由格 A, 所诱导的代数系统为 A,,, 则对任意 的 a, b, c, d A, 有 1 a b = b a, } ( 交换律 ) a b = b a } a (b c) = (a b) c, 2 ( 结合律 ) a (b c) = (a b) c 3 a a = a, } ( 幂等律 ) a a = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

62 格的基本性质 Theorem 113 设 A, 是格, 由格 A, 所诱导的代数系统为 A,,, 则对任意 的 a, b, c, d A, 有 1 a b = b a, } ( 交换律 ) a b = b a } a (b c) = (a b) c, 2 ( 结合律 ) a (b c) = (a b) c 3 a a = a, } ( 幂等律 ) a a = a } a (a b) = a, 4 ( 吸收律 ) a (a b) = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

63 下证结合律 : a (b c) = (a b) c 黄正华 ( 武汉大学 ) 格 December 3, / 103

64 下证结合律 : a (b c) = (a b) c 分析由偏序的反对称性, 可证下列两式同时成立 : (a b) c a (b c), (5) a (b c) (a b) c (6) 黄正华 ( 武汉大学 ) 格 December 3, / 103

65 下证结合律 : a (b c) = (a b) c 证 因为 b b c, 由保序性得 a b a (b c) 反复使用结论 x x y, y x y, 有 c b c a (b c) 这说明 a (b c) 是 a b 和 c 的一个上界 黄正华 ( 武汉大学 ) 格 December 3, / 103

66 下证结合律 : a (b c) = (a b) c 证 因为 b b c, 由保序性得 a b a (b c) 反复使用结论 x x y, y x y, 有 c b c a (b c) 这说明 a (b c) 是 a b 和 c 的一个上界 但 (a b) c 是 a b 和 c 的最小上界, 黄正华 ( 武汉大学 ) 格 December 3, / 103

67 下证结合律 : a (b c) = (a b) c 证 因为 b b c, 由保序性得 a b a (b c) 反复使用结论 x x y, y x y, 有 c b c a (b c) 这说明 a (b c) 是 a b 和 c 的一个上界 但 (a b) c 是 a b 和 c 的最小上界, 所以 (a b) c a (b c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

68 下证结合律 : a (b c) = (a b) c 证 因为 b b c, 由保序性得 a b a (b c) 反复使用结论 x x y, y x y, 有 c b c a (b c) 这说明 a (b c) 是 a b 和 c 的一个上界 但 (a b) c 是 a b 和 c 的最小上界, 所以 (a b) c a (b c) 类似可证 a (b c) (a b) c 黄正华 ( 武汉大学 ) 格 December 3, / 103

69 下证结合律 : a (b c) = (a b) c 证 因为 b b c, 由保序性得 a b a (b c) 反复使用结论 x x y, y x y, 有 c b c a (b c) 这说明 a (b c) 是 a b 和 c 的一个上界 但 (a b) c 是 a b 和 c 的最小上界, 所以 (a b) c a (b c) 类似可证 a (b c) (a b) c 因而 a (b c) = (a b) c 黄正华 ( 武汉大学 ) 格 December 3, / 103

70 证明吸收律 : a (a b) = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

71 证明吸收律 : a (a b) = a 证 因为 a b a, 黄正华 ( 武汉大学 ) 格 December 3, / 103

72 证明吸收律 : a (a b) = a 证 所以 因为 a b a, a (a b) = a (5) 黄正华 ( 武汉大学 ) 格 December 3, / 103

73 证明吸收律 : a (a b) = a 证 所以 因为 a b a, a (a b) = a (5) 这里 (5) 式成立的理由是 大 小 = 大 黄正华 ( 武汉大学 ) 格 December 3, / 103

74 引理 设 A,, 是一个代 数 系 统, 其中, 都是二元运算且满足吸收律, 那么, 必满足幂等律 黄正华 ( 武汉大学 ) 格 December 3, / 103

75 引理 设 A,, 是一个代 数 系 统, 其中, 都是二元运算且满足吸收律, 那么, 必满足幂等律 证 对任意 a, b A, 因, 满足吸收律, 所以 a (a b) = a, (6) a (a b) = a (7) 黄正华 ( 武汉大学 ) 格 December 3, / 103

76 引理 设 A,, 是一个代 数 系 统, 其中, 都是二元运算且满足吸收律, 那么, 必满足幂等律 证 对任意 a, b A, 因, 满足吸收律, 所以 a (a b) = a, (6) a (a b) = a (7) 由 b 的任意性, 在 (6) 式中用 a b 取代 b 仍然成立, 可得 a ( a b ) = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

77 引理 设 A,, 是一个代 数 系 统, 其中, 都是二元运算且满足吸收律, 那么, 必满足幂等律 证 对任意 a, b A, 因, 满足吸收律, 所以 a (a b) = a, (6) a (a b) = a (7) 由 b 的任意性, 在 (6) 式中用 a b 取代 b 仍然成立, 可得 a ( a ( a b ) ) = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

78 引理 设 A,, 是一个代 数 系 统, 其中, 都是二元运算且满足吸收律, 那么, 必满足幂等律 证 对任意 a, b A, 因, 满足吸收律, 所以 a (a b) = a, (6) a (a b) = a (7) 由 b 的任意性, 在 (6) 式中用 a b 取代 b 仍然成立, 可得 a ( ) a ( a b ) = a }{{} a 黄正华 ( 武汉大学 ) 格 December 3, / 103

79 引理 设 A,, 是一个代 数 系 统, 其中, 都是二元运算且满足吸收律, 那么, 必满足幂等律 证 对任意 a, b A, 因, 满足吸收律, 所以 a (a b) = a, (6) a (a b) = a (7) 由 b 的任意性, 在 (6) 式中用 a b 取代 b 仍然成立, 可得 a ( ) a ( a b ) = a }{{} a 再由 (7) 式得 : a a = a 同理可证 a a = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

80 格与代数系统之间的关系 Theorem 114 设 A,, 是一个代数系统, 其中, 都是二元运算, 且满足交换律 结合 律和吸收律, 则 A 上存在偏序关系, 使 A, 是一个格 黄正华 ( 武汉大学 ) 格 December 3, / 103

81 格与代数系统之间的关系 Theorem 114 设 A,, 是一个代数系统, 其中, 都是二元运算, 且满足交换律 结合 律和吸收律, 则 A 上存在偏序关系, 使 A, 是一个格 分析证明思路 : 1 在 A 上构造偏序关系 ; 2 证明 A, 中任意两个元素有最小上界和最大下界 黄正华 ( 武汉大学 ) 格 December 3, / 103

82 格与代数系统之间的关系 Theorem 114 设 A,, 是一个代数系统, 其中, 都是二元运算, 且满足交换律 结合 律和吸收律, 则 A 上存在偏序关系, 使 A, 是一个格 分析证明思路 : 1 在 A 上构造偏序关系 ; 2 证明 A, 中任意两个元素有最小上界和最大下界 证在 A 上定义二元关系 : 对任意 a, b A, a b a b = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

83 格与代数系统之间的关系 Theorem 114 设 A,, 是一个代数系统, 其中, 都是二元运算, 且满足交换律 结合 律和吸收律, 则 A 上存在偏序关系, 使 A, 是一个格 分析证明思路 : 1 在 A 上构造偏序关系 ; 2 证明 A, 中任意两个元素有最小上界和最大下界 证在 A 上定义二元关系 : 对任意 a, b A, 先证 是偏序 ( 下一页 ) a b a b = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

84 续证 : 注意到 a b a b = a, 运算 满足吸收律, 由引理知满足幂等律 : 对任意 a A, a a = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

85 续证 : 注意到 a b a b = a, 运算 满足吸收律, 由引理知满足幂等律 : 对任意 a A, a a = a 所以 a a 从而 是自反的 黄正华 ( 武汉大学 ) 格 December 3, / 103

86 续证 : 注意到 a b a b = a, 运算 满足吸收律, 由引理知满足幂等律 : 对任意 a A, a a = a 所以 a a 从而 是自反的 设 a b, 则 a b = a 如果同时有 b a, 则 b a = b 黄正华 ( 武汉大学 ) 格 December 3, / 103

87 续证 : 注意到 a b a b = a, 运算 满足吸收律, 由引理知满足幂等律 : 对任意 a A, a a = a 所以 a a 从而 是自反的 设 a b, 则 a b = a 如果同时有 b a, 则 b a = b 而运算 满足交 换律, 所以 a b = b a 黄正华 ( 武汉大学 ) 格 December 3, / 103

88 续证 : 注意到 a b a b = a, 运算 满足吸收律, 由引理知满足幂等律 : 对任意 a A, a a = a 所以 a a 从而 是自反的 设 a b, 则 a b = a 如果同时有 b a, 则 b a = b 而运算 满足交 换律, 所以 a b = b a 故 a = b 从而 是反对称的 黄正华 ( 武汉大学 ) 格 December 3, / 103

89 续证 : 注意到 a b a b = a, 运算 满足吸收律, 由引理知满足幂等律 : 对任意 a A, a a = a 所以 a a 从而 是自反的 设 a b, 则 a b = a 如果同时有 b a, 则 b a = b 而运算 满足交 换律, 所以 a b = b a 故 a = b 从而 是反对称的 设 a b, b c, 则 a b = a, b c = b 黄正华 ( 武汉大学 ) 格 December 3, / 103

90 续证 : 注意到 a b a b = a, 运算 满足吸收律, 由引理知满足幂等律 : 对任意 a A, a a = a 所以 a a 从而 是自反的 设 a b, 则 a b = a 如果同时有 b a, 则 b a = b 而运算 满足交 换律, 所以 a b = b a 故 a = b 从而 是反对称的 设 a b, b c, 则 a b = a, b c = b 那么 a c = (a b) c (a b = a) = a (b c) ( 结合律 ) = a b (b c = b) = a (a b = a) 黄正华 ( 武汉大学 ) 格 December 3, / 103

91 续证 : 注意到 a b a b = a, 运算 满足吸收律, 由引理知满足幂等律 : 对任意 a A, a a = a 所以 a a 从而 是自反的 设 a b, 则 a b = a 如果同时有 b a, 则 b a = b 而运算 满足交 换律, 所以 a b = b a 故 a = b 从而 是反对称的 设 a b, b c, 则 a b = a, b c = b 那么 所以 a c, 说明 是传递的 a c = (a b) c (a b = a) = a (b c) ( 结合律 ) = a b (b c = b) = a (a b = a) 黄正华 ( 武汉大学 ) 格 December 3, / 103

92 续证 : 其次, 证明 a b 是 a, b 的最大下界 黄正华 ( 武汉大学 ) 格 December 3, / 103

93 续证 : 其次, 证明 a b 是 a, b 的最大下界 因 (a b) a = a (b a) ( 结合律 ) = a (a b) ( 交换律 ) = (a a) b ( 结合律 ) = a b ( 幂等律 ) (a b) b = a (b b) = a b 黄正华 ( 武汉大学 ) 格 December 3, / 103

94 续证 : 其次, 证明 a b 是 a, b 的最大下界 因 (a b) a = a (b a) ( 结合律 ) = a (a b) ( 交换律 ) = (a a) b ( 结合律 ) = a b ( 幂等律 ) (a b) b = a (b b) = a b 又由 的定义, 可得 a b a, a b b 黄正华 ( 武汉大学 ) 格 December 3, / 103

95 续证 : 其次, 证明 a b 是 a, b 的最大下界 因 (a b) a = a (b a) ( 结合律 ) = a (a b) ( 交换律 ) = (a a) b ( 结合律 ) = a b ( 幂等律 ) (a b) b = a (b b) = a b 又由 的定义, 可得 a b a, a b b 说明 a b 是 a, b 的下界 黄正华 ( 武汉大学 ) 格 December 3, / 103

96 续证 : 其次, 证明 a b 是 a, b 的最大下界 因 (a b) a = a (b a) ( 结合律 ) = a (a b) ( 交换律 ) = (a a) b ( 结合律 ) = a b ( 幂等律 ) (a b) b = a (b b) = a b 又由 的定义, 可得 a b a, a b b 说明 a b 是 a, b 的下界 设 c 是 a, b 的任一下界, 则 c a, c b 黄正华 ( 武汉大学 ) 格 December 3, / 103

97 续证 : 其次, 证明 a b 是 a, b 的最大下界 因 (a b) a = a (b a) ( 结合律 ) = a (a b) ( 交换律 ) = (a a) b ( 结合律 ) = a b ( 幂等律 ) (a b) b = a (b b) = a b 又由 的定义, 可得 a b a, a b b 说明 a b 是 a, b 的下界 设 c 是 a, b 的任一下界, 则 c a, c b 按 的定义有 c a = c, c b = c 黄正华 ( 武汉大学 ) 格 December 3, / 103

98 续证 : 其次, 证明 a b 是 a, b 的最大下界 因 (a b) a = a (b a) ( 结合律 ) = a (a b) ( 交换律 ) = (a a) b ( 结合律 ) = a b ( 幂等律 ) (a b) b = a (b b) = a b 又由 的定义, 可得 a b a, a b b 说明 a b 是 a, b 的下界 设 c 是 a, b 的任一下界, 则 c a, c b 按 的定义有 c a = c, c b = c 进而有 c (a b) = (c a) b = c b = c 黄正华 ( 武汉大学 ) 格 December 3, / 103

99 续证 : 其次, 证明 a b 是 a, b 的最大下界 因 (a b) a = a (b a) ( 结合律 ) = a (a b) ( 交换律 ) = (a a) b ( 结合律 ) = a b ( 幂等律 ) (a b) b = a (b b) = a b 又由 的定义, 可得 a b a, a b b 说明 a b 是 a, b 的下界 设 c 是 a, b 的任一下界, 则 c a, c b 按 的定义有 c a = c, c b = c 进而有 c (a b) = (c a) b = c b = c 按 的定义有 c a b 故 a b 是 a, b 的最大下界 黄正华 ( 武汉大学 ) 格 December 3, / 103

100 续证 : 第三, 证明 a b 是 a, b 的最小上界 黄正华 ( 武汉大学 ) 格 December 3, / 103

101 续证 : 第三, 证明 a b 是 a, b 的最小上界 先证 a b = a 与 a b = b 等价 黄正华 ( 武汉大学 ) 格 December 3, / 103

102 续证 : 第三, 证明 a b 是 a, b 的最小上界 先证 a b = a 与 a b = b 等价 若 a b = a, 则 a b = (a b) b (a b = a) = b (a b) ( 交换律 ) = b (b a) ( 交换律 ) = b ( 吸收律 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

103 续证 : 第三, 证明 a b 是 a, b 的最小上界 先证 a b = a 与 a b = b 等价 若 a b = a, 则 a b = (a b) b (a b = a) = b (a b) ( 交换律 ) = b (b a) ( 交换律 ) = b ( 吸收律 ) 于是 a b = b 黄正华 ( 武汉大学 ) 格 December 3, / 103

104 续证 : 第三, 证明 a b 是 a, b 的最小上界 先证 a b = a 与 a b = b 等价 若 a b = a, 则 a b = (a b) b (a b = a) = b (a b) ( 交换律 ) = b (b a) ( 交换律 ) = b ( 吸收律 ) 于是 a b = b 反之, 若 a b = b, 则 a b = a (a b) (a b = b) = a ( 吸收律 ) 亦即 a b = a 黄正华 ( 武汉大学 ) 格 December 3, / 103

105 续证 : 第三, 证明 a b 是 a, b 的最小上界 先证 a b = a 与 a b = b 等价 若 a b = a, 则 a b = (a b) b (a b = a) = b (a b) ( 交换律 ) = b (b a) ( 交换律 ) = b ( 吸收律 ) 于是 a b = b 反之, 若 a b = b, 则 a b = a (a b) (a b = b) = a ( 吸收律 ) 亦即 a b = a 由此可见, 偏序关系 的等价定义为 : a b a b = b 黄正华 ( 武汉大学 ) 格 December 3, / 103

106 续证 : 可以用证明 a b 是 a, b 的最大下界 类似的方法证明 a b 是 a, b 的 最小上界 黄正华 ( 武汉大学 ) 格 December 3, / 103

107 续证 : 可以用证明 a b 是 a, b 的最大下界 类似的方法证明 a b 是 a, b 的最小上界 综上所述, A, 是格 黄正华 ( 武汉大学 ) 格 December 3, / 103

108 续证 : 可以用证明 a b 是 a, b 的最大下界 类似的方法证明 a b 是 a, b 的 最小上界 综上所述, A, 是格 事实上, 这个定理给出的是格的另一个定义方式 Definition 115 设 A,, 是一个代数系统, 其中, 都是二元运算, 且满足交换律 结合律 和吸收律, 定义 A 上的偏序关系 : 对任意 a, b A, a b a b = a ( 或 a b a b = b) 则 A, 是一个格 黄正华 ( 武汉大学 ) 格 December 3, / 103

109 续证 : 可以用证明 a b 是 a, b 的最大下界 类似的方法证明 a b 是 a, b 的 最小上界 综上所述, A, 是格 事实上, 这个定理给出的是格的另一个定义方式 Definition 115 设 A,, 是一个代数系统, 其中, 都是二元运算, 且满足交换律 结合律 和吸收律, 定义 A 上的偏序关系 : 对任意 a, b A, a b a b = a ( 或 a b a b = b) 则 A, 是一个格 由格 A, 可以构造代数系统 A,,, 反过来, 由代数系统 A,, 出发也可以返回到格 A, 黄正华 ( 武汉大学 ) 格 December 3, / 103

110 Theorem 116 ( 弱分配律 ) 在一个格 A, 中, 对任意的 a, b, c A, 都有 a (b c) (a b) (a c), (8) (a b) (a c) a (b c) (9) 黄正华 ( 武汉大学 ) 格 December 3, / 103

111 Theorem 116 ( 弱分配律 ) 在一个格 A, 中, 对任意的 a, b, c A, 都有 a (b c) (a b) (a c), (8) (a b) (a c) a (b c) (9) 分析 比较 : 集合的并 交运算的分配律 A (B C) = (A B) (A C), (10) (A B) (A C) = A (B C) (11) 黄正华 ( 武汉大学 ) 格 December 3, / 103

112 Theorem 116 ( 弱分配律 ) 在一个格 A, 中, 对任意的 a, b, c A, 都有 a (b c) (a b) (a c), (8) (a b) (a c) a (b c) (9) 分析 比较 : 集合的并 交运算的分配律 A (B C) = (A B) (A C), (10) (A B) (A C) = A (B C) (11) 谓之 分配不等式, 或弱分配律, 次分配律 ; 黄正华 ( 武汉大学 ) 格 December 3, / 103

113 Theorem 116 ( 弱分配律 ) 在一个格 A, 中, 对任意的 a, b, c A, 都有 a (b c) (a b) (a c), (8) (a b) (a c) a (b c) (9) 分析 比较 : 集合的并 交运算的分配律 A (B C) = (A B) (A C), (10) (A B) (A C) = A (B C) (11) 谓之 分配不等式, 或弱分配律, 次分配律 ; 这里, (8) 式与 (9) 式是互为对偶的 黄正华 ( 武汉大学 ) 格 December 3, / 103

114 Theorem 116 ( 弱分配律 ) 在一个格 A, 中, 对任意的 a, b, c A, 都有 a (b c) (a b) (a c), (8) (a b) (a c) a (b c) (9) 分析 比较 : 集合的并 交运算的分配律 A (B C) = (A B) (A C), (10) (A B) (A C) = A (B C) (11) 谓之 分配不等式, 或弱分配律, 次分配律 ; 这里, (8) 式与 (9) 式是互为对偶的 下证 (8) 式成立, (9) 式由对偶原理可得 黄正华 ( 武汉大学 ) 格 December 3, / 103

115 证 要证 a (b c) (a b) (a c), 可以先分别证明 a (a b) (a c), (12) b c (a b) (a c) (13) 黄正华 ( 武汉大学 ) 格 December 3, / 103

116 证 要证 a (b c) (a b) (a c), 可以先分别证明 a (a b) (a c), (12) b c (a b) (a c) (13) (12) 式成立, 因为 a = a a (a b) (a c) ( 幂等性 ) ( ) a (a b), a (a c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

117 证 要证 a (b c) (a b) (a c), 可以先分别证明 a (a b) (a c), (12) b c (a b) (a c) (13) (12) 式成立, 因为 a = a a (a b) (a c) ( 幂等性 ) ( ) a (a b), a (a c) (13) 式成立, 因为 b c b a b, b c c a c, 黄正华 ( 武汉大学 ) 格 December 3, / 103

118 证 要证 a (b c) (a b) (a c), 可以先分别证明 a (a b) (a c), (12) b c (a b) (a c) (13) (12) 式成立, 因为 a = a a (a b) (a c) ( 幂等性 ) ( ) a (a b), a (a c) (13) 式成立, 因为 b c b a b, b c c a c, 所以 b c = (b c) (b c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

119 证 要证 a (b c) (a b) (a c), 可以先分别证明 a (a b) (a c), (12) b c (a b) (a c) (13) (12) 式成立, 因为 a = a a (a b) (a c) ( 幂等性 ) ( ) a (a b), a (a c) (13) 式成立, 因为 b c b a b, b c c a c, 所以 b c = (b c) (b c) (a b) (a c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

120 分配不等式 a (b c) (a b) (a c), Example 117 分配不等式实例 : (a b) (a c) a (b c) e b c d a b (c d) = b e = b, (b c) (b d) = a a = a 称为钻石格 (diamond lattice) 黄正华 ( 武汉大学 ) 格 December 3, / 103

121 分配不等式 a (b c) (a b) (a c), Example 118 分配不等式实例 : (a b) (a c) a (b c) e b d c a d (b c) = d e = d, (d b) (d c) = a c = c 称为五角格 (pentagon lattice) 黄正华 ( 武汉大学 ) 格 December 3, / 103

122 练习 设 L = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, L, 是偏序集, 定义为 : 对 于 n 1, n 2 L, n 1 n 2 当且仅当 n 1 是 n 2 的因子 问 L, 是否为格? 黄正华 ( 武汉大学 ) 格 December 3, / 103

123 练习 设 L = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, L, 是偏序集, 定义为 : 对 于 n 1, n 2 L, n 1 n 2 当且仅当 n 1 是 n 2 的因子 问 L, 是否为格? 解不是格 黄正华 ( 武汉大学 ) 格 December 3, / 103

124 练习 设 L = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, L, 是偏序集, 定义为 : 对 于 n 1, n 2 L, n 1 n 2 当且仅当 n 1 是 n 2 的因子 问 L, 是否为格? 解不是格 哈斯图为 : 黄正华 ( 武汉大学 ) 格 December 3, / 103

125 练习 设 L = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, L, 是偏序集, 定义为 : 对 于 n 1, n 2 L, n 1 n 2 当且仅当 n 1 是 n 2 的因子 问 L, 是否为格? 解不是格 哈斯图为 : 例如, 9 和 10 没有最小上界 黄正华 ( 武汉大学 ) 格 December 3, / 103

126 1 格的定义 2 子格与格同态 3 几种特殊的格 4 布尔代数 5 有限布尔代数的表示定理 黄正华 ( 武汉大学 ) 格 December 3, / 103

127 Definition 21 ( 子格 ) 设 A, 是格, A,, 是 A, 诱导的代数系统 设 B 是 A 的非空子集 如果运算 和 在 B 中封闭, 则称 B, 是 A, 的子格 黄正华 ( 武汉大学 ) 格 December 3, / 103

128 Definition 21 ( 子格 ) 设 A, 是格, A,, 是 A, 诱导的代数系统 设 B 是 A 的非空子集 如果运算 和 在 B 中封闭, 则称 B, 是 A, 的子格 可以证明, 子格也是格 黄正华 ( 武汉大学 ) 格 December 3, / 103

129 Definition 21 ( 子格 ) 设 A, 是格, A,, 是 A, 诱导的代数系统 设 B 是 A 的非空子集 如果运算 和 在 B 中封闭, 则称 B, 是 A, 的子格 可以证明, 子格也是格 Example 22 设 E + 是正偶数的全体, 易知 E +, 是 Z +, 的子格 : 黄正华 ( 武汉大学 ) 格 December 3, / 103

130 Definition 21 ( 子格 ) 设 A, 是格, A,, 是 A, 诱导的代数系统 设 B 是 A 的非空子集 如果运算 和 在 B 中封闭, 则称 B, 是 A, 的子格 可以证明, 子格也是格 Example 22 设 E + 是正偶数的全体, 易知 E +, 是 Z +, 的子格 : 任何两个偶数的最大公约数和最小公倍数都是偶数, 运算 和 关于 E + 是封 闭的 黄正华 ( 武汉大学 ) 格 December 3, / 103

131 Example 23 设 S, 是一个格, 任取 a S, 构造 S 的子集为 : 则 T, 是 S, 的一个子格 T = { x x S 且 x a }, 黄正华 ( 武汉大学 ) 格 December 3, / 103

132 Example 23 设 S, 是一个格, 任取 a S, 构造 S 的子集为 : 则 T, 是 S, 的一个子格 T = { x x S 且 x a }, 证对任意的 x, y T, 必有 x a 和 y a, 黄正华 ( 武汉大学 ) 格 December 3, / 103

133 Example 23 设 S, 是一个格, 任取 a S, 构造 S 的子集为 : 则 T, 是 S, 的一个子格 T = { x x S 且 x a }, 证 对任意的 x, y T, 必有 x a 和 y a, 所以 x y a, (a 是 x, y 的上界 ) x y a, (x y x y) 黄正华 ( 武汉大学 ) 格 December 3, / 103

134 Example 23 设 S, 是一个格, 任取 a S, 构造 S 的子集为 : 则 T, 是 S, 的一个子格 T = { x x S 且 x a }, 证 对任意的 x, y T, 必有 x a 和 y a, 所以 x y a, (a 是 x, y 的上界 ) x y a, (x y x y) 故 x y T, x y T 黄正华 ( 武汉大学 ) 格 December 3, / 103

135 Example 23 设 S, 是一个格, 任取 a S, 构造 S 的子集为 : 则 T, 是 S, 的一个子格 T = { x x S 且 x a }, 证 对任意的 x, y T, 必有 x a 和 y a, 所以 x y a, (a 是 x, y 的上界 ) x y a, (x y x y) 故 x y T, x y T 运算 和 关于 T 是封闭的, 因此, T, 是 S, 的一个子格 黄正华 ( 武汉大学 ) 格 December 3, / 103

136 注意 若 A, 是格, B A 且 B, 则 B, 仍然是偏序集, 但 B, 不一定是格 黄正华 ( 武汉大学 ) 格 December 3, / 103

137 注意 若 A, 是格, B A 且 B, 则 B, 仍然是偏序集, 但 B, 不一定是格 即使是格, 也不一定是 A, 的子格 黄正华 ( 武汉大学 ) 格 December 3, / 103

138 Example 24 设 S = {a, b, c}, 则 P(S), 是格, 其哈斯图如下 {a, b} {a, b, c} {a, c} {b, c} 取 A = {, {a}, {c}, {a, c} }, B = {, {a}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} } {a} {b} {c} 黄正华 ( 武汉大学 ) 格 December 3, / 103

139 Example 24 设 S = {a, b, c}, 则 P(S), 是格, 其哈斯图如下 {a, b} {a, b, c} {a, c} {b, c} 取 A = {, {a}, {c}, {a, c} }, B = {, {a}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} } 则 A, 是 P(S), 的子格 ; {a} {b} {c} 黄正华 ( 武汉大学 ) 格 December 3, / 103

140 Example 24 设 S = {a, b, c}, 则 P(S), 是格, 其哈斯图如下 {a, b} {a, b, c} {a, c} {b, c} 取 A = {, {a}, {c}, {a, c} }, B = {, {a}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} } 则 A, 是 P(S), 的子格 ; {a} {b} {c} B, 是格, 但不是 P(S), 的子格 黄正华 ( 武汉大学 ) 格 December 3, / 103

141 Example 24 设 S = {a, b, c}, 则 P(S), 是格, 其哈斯图如下 {a, b} {a, b, c} {a, c} {b, c} 取 A = {, {a}, {c}, {a, c} }, B = {, {a}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} } 则 A, 是 P(S), 的子格 ; {a} {b} {c} B, 是格, 但不是 P(S), 的子格 这是因为 {a, b} {b, c} = {b} / B 黄正华 ( 武汉大学 ) 格 December 3, / 103

142 格同态 格 A, 可视为具有两个二元运算的代数系统 A,,, 其中运算满足交 换律 结合律 吸收律和幂等律 因此, 对格可引入代数系统中同态的概念 黄正华 ( 武汉大学 ) 格 December 3, / 103

143 格同态 Definition 25 设 A 1, 1, A 2, 2 是格, 它们所诱导的代数系统分别是 A 1, 1, 1, A 2, 2, 2 如果存在映射 f : A 1 A 2, 使对任意 a, b A 1, 有 f(a 1 b) = f(a) 2 f(b), f(a 1 b) = f(a) 2 f(b) 黄正华 ( 武汉大学 ) 格 December 3, / 103

144 格同态 Definition 25 设 A 1, 1, A 2, 2 是格, 它们所诱导的代数系统分别是 A 1, 1, 1, A 2, 2, 2 如果存在映射 f : A 1 A 2, 使对任意 a, b A 1, 有 f(a 1 b) = f(a) 2 f(b), f(a 1 b) = f(a) 2 f(b) 则称 f 是从 A 1, 1, 1 到 A 2, 2, 2 的格同态 黄正华 ( 武汉大学 ) 格 December 3, / 103

145 格同态 Definition 25 设 A 1, 1, A 2, 2 是格, 它们所诱导的代数系统分别是 A 1, 1, 1, A 2, 2, 2 如果存在映射 f : A 1 A 2, 使对任意 a, b A 1, 有 f(a 1 b) = f(a) 2 f(b), f(a 1 b) = f(a) 2 f(b) 则称 f 是从 A 1, 1, 1 到 A 2, 2, 2 的格同态 称 f(a 1 ), 2 是 A 1, 1 的格同态象 黄正华 ( 武汉大学 ) 格 December 3, / 103

146 格同态 Definition 25 设 A 1, 1, A 2, 2 是格, 它们所诱导的代数系统分别是 A 1, 1, 1, A 2, 2, 2 如果存在映射 f : A 1 A 2, 使对任意 a, b A 1, 有 f(a 1 b) = f(a) 2 f(b), f(a 1 b) = f(a) 2 f(b) 则称 f 是从 A 1, 1, 1 到 A 2, 2, 2 的格同态 称 f(a 1 ), 2 是 A 1, 1 的格同态象 如果 f 是双射, 则称 f 是从 A 1, 1, 1 到 A 2, 2, 2 的格同构 也称 格 A 1, 1, A 2, 2 同构 黄正华 ( 武汉大学 ) 格 December 3, / 103

147 Theorem 26 设 f 是格 A 1, 1 到 A 2, 2 的格同态 对任意 x, y A 1, 如果 x 1 y, 则 f(x) 2 f(y) 黄正华 ( 武汉大学 ) 格 December 3, / 103

148 Theorem 26 设 f 是格 A 1, 1 到 A 2, 2 的格同态 对任意 x, y A 1, 如果 x 1 y, 则 f(x) 2 f(y) 证 已知 x 1 y, 因 x 1 y x 1 y = x, 则 x 1 y = x 黄正华 ( 武汉大学 ) 格 December 3, / 103

149 Theorem 26 设 f 是格 A 1, 1 到 A 2, 2 的格同态 对任意 x, y A 1, 如果 x 1 y, 则 f(x) 2 f(y) 证 已知 x 1 y, 因 x 1 y x 1 y = x, 则 x 1 y = x 所以 f(x) = f(x 1 y) (x 1 y = x) = f(x) 2 f(y) (f 是格同态 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

150 Theorem 26 设 f 是格 A 1, 1 到 A 2, 2 的格同态 对任意 x, y A 1, 如果 x 1 y, 则 f(x) 2 f(y) 证 已知 x 1 y, 因 x 1 y x 1 y = x, 则 x 1 y = x 所以 f(x) = f(x 1 y) (x 1 y = x) = f(x) 2 f(y) (f 是格同态 ) 而 f(x) 2 f(y) = f(x) f(x) 2 f(y), 所以 f(x) 2 f(y) 黄正华 ( 武汉大学 ) 格 December 3, / 103

151 Theorem 26 设 f 是格 A 1, 1 到 A 2, 2 的格同态 对任意 x, y A 1, 如果 x 1 y, 则 f(x) 2 f(y) 证 已知 x 1 y, 因 x 1 y x 1 y = x, 则 x 1 y = x 所以 f(x) = f(x 1 y) (x 1 y = x) = f(x) 2 f(y) (f 是格同态 ) 而 f(x) 2 f(y) = f(x) f(x) 2 f(y), 所以 f(x) 2 f(y) 注 : 此定理说明, 格同态是保序的 黄正华 ( 武汉大学 ) 格 December 3, / 103

152 Theorem 26 设 f 是格 A 1, 1 到 A 2, 2 的格同态 对任意 x, y A 1, 如果 x 1 y, 则 f(x) 2 f(y) 证 已知 x 1 y, 因 x 1 y x 1 y = x, 则 x 1 y = x 所以 f(x) = f(x 1 y) (x 1 y = x) = f(x) 2 f(y) (f 是格同态 ) 而 f(x) 2 f(y) = f(x) f(x) 2 f(y), 所以 f(x) 2 f(y) 注 : 此定理说明, 格同态是保序的 但, 其逆不真 黄正华 ( 武汉大学 ) 格 December 3, / 103

153 Example 27 设 A = {1, 2, 3, 4, 6, 12}, A, 和 A, 都是格, 其中 表示整除关系, 表示数的 小 于 等 于 关系 黄正华 ( 武汉大学 ) 格 December 3, / 103

154 Example 27 设 A = {1, 2, 3, 4, 6, 12}, A, 和 A, 都是格, 其中 表示整除关系, 表示数的 小 于 等 于 关系 作映射 f : A A, f(x) = x 黄正华 ( 武汉大学 ) 格 December 3, / 103

155 Example 27 设 A = {1, 2, 3, 4, 6, 12}, A, 和 A, 都是格, 其中 表示整除关系, 表示数的 小 于 等 于 关系 作映射 f : A A, f(x) = x 显然, 若 x y, 则 f(x) f(y), 因而 f 是保序的 黄正华 ( 武汉大学 ) 格 December 3, / 103

156 Example 27 设 A = {1, 2, 3, 4, 6, 12}, A, 和 A, 都是格, 其中 表示整除关系, 表示数的 小 于 等 于 关系 作映射 f : A A, f(x) = x 显然, 若 x y, 则 f(x) f(y), 因而 f 是保序的 但 f 不是格同态 黄正华 ( 武汉大学 ) 格 December 3, / 103

157 Example 27 设 A = {1, 2, 3, 4, 6, 12}, A, 和 A, 都是格, 其中 表示整除关系, 表示数的 小 于 等 于 关系 作映射 f : A A, f(x) = x 显然, 若 x y, 则 f(x) f(y), 因而 f 是保序的 但 f 不是格同态 例如 : f(4 1 6) f(4) 2 f(6) }{{}}{{} =2 =4 黄正华 ( 武汉大学 ) 格 December 3, / 103

158 Theorem 28 设两个格为 A 1, 1 和 A 2, 2, f 是 A 1 到 A 2 的双射 则 f 是格 A 1, 1 到 A 2, 2 的格同构, 当且仅当 a, b A 1, a 1 b f(a) 2 f(b) (14) 黄正华 ( 武汉大学 ) 格 December 3, / 103

159 Theorem 28 设两个格为 A 1, 1 和 A 2, 2, f 是 A 1 到 A 2 的双射 则 f 是格 A 1, 1 到 A 2, 2 的格同构, 当且仅当 a, b A 1, a 1 b f(a) 2 f(b) (14) 证 (1) 设 f 是格 A 1, 1 到 A 2, 2 的格同构 下证 (14) 式成立 黄正华 ( 武汉大学 ) 格 December 3, / 103

160 Theorem 28 设两个格为 A 1, 1 和 A 2, 2, f 是 A 1 到 A 2 的双射 则 f 是格 A 1, 1 到 A 2, 2 的格同构, 当且仅当 a, b A 1, a 1 b f(a) 2 f(b) (14) 证 (1) 设 f 是格 A 1, 1 到 A 2, 2 的格同构 下证 (14) 式成立 i) 对任意 a, b A 1, 如果 a 1 b, 由保序性, 则 f(a) 2 f(b) 黄正华 ( 武汉大学 ) 格 December 3, / 103

161 Theorem 28 设两个格为 A 1, 1 和 A 2, 2, f 是 A 1 到 A 2 的双射 则 f 是格 A 1, 1 到 A 2, 2 的格同构, 当且仅当 a, b A 1, a 1 b f(a) 2 f(b) (14) 证 (1) 设 f 是格 A 1, 1 到 A 2, 2 的格同构 下证 (14) 式成立 i) 对任意 a, b A 1, 如果 a 1 b, 由保序性, 则 f(a) 2 f(b) ii) 若 f(a) 2 f(b), 则 黄正华 ( 武汉大学 ) 格 December 3, / 103

162 Theorem 28 设两个格为 A 1, 1 和 A 2, 2, f 是 A 1 到 A 2 的双射 则 f 是格 A 1, 1 到 A 2, 2 的格同构, 当且仅当 a, b A 1, a 1 b f(a) 2 f(b) (14) 证 (1) 设 f 是格 A 1, 1 到 A 2, 2 的格同构 下证 (14) 式成立 i) 对任意 a, b A 1, 如果 a 1 b, 由保序性, 则 f(a) 2 f(b) ii) 若 f(a) 2 f(b), 则 f(a) = f(a) 2 f(b) 黄正华 ( 武汉大学 ) 格 December 3, / 103

163 Theorem 28 设两个格为 A 1, 1 和 A 2, 2, f 是 A 1 到 A 2 的双射 则 f 是格 A 1, 1 到 A 2, 2 的格同构, 当且仅当 a, b A 1, a 1 b f(a) 2 f(b) (14) 证 (1) 设 f 是格 A 1, 1 到 A 2, 2 的格同构 下证 (14) 式成立 i) 对任意 a, b A 1, 如果 a 1 b, 由保序性, 则 f(a) 2 f(b) ii) 若 f(a) 2 f(b), 则 f(a) = f(a) 2 f(b) = f(a 1 b) (f 是同构 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

164 Theorem 28 设两个格为 A 1, 1 和 A 2, 2, f 是 A 1 到 A 2 的双射 则 f 是格 A 1, 1 到 A 2, 2 的格同构, 当且仅当 a, b A 1, a 1 b f(a) 2 f(b) (14) 证 (1) 设 f 是格 A 1, 1 到 A 2, 2 的格同构 下证 (14) 式成立 i) 对任意 a, b A 1, 如果 a 1 b, 由保序性, 则 f(a) 2 f(b) ii) 若 f(a) 2 f(b), 则 f(a) = f(a) 2 f(b) = f(a 1 b) (f 是同构 ) 而 f 是双射, 则 f(a 1 b) = f(a) a 1 b = a a 1 b 黄正华 ( 武汉大学 ) 格 December 3, / 103

165 续证 : (2) 假设对任意 a, b A 1, a 1 b f(a) 2 f(b) 即映射 f 是保序的 黄正华 ( 武汉大学 ) 格 December 3, / 103

166 续证 : (2) 假设对任意 a, b A 1, a 1 b f(a) 2 f(b) 即映射 f 是保序的 要证 f 是 A 1, 1 到 A 2, 2 的格同构, 即要证 f(a 1 b) = f(a) 2 f(b), (15) f(a 1 b) = f(a) 2 f(b) (16) 黄正华 ( 武汉大学 ) 格 December 3, / 103

167 续证 : (2) 假设对任意 a, b A 1, a 1 b f(a) 2 f(b) 即映射 f 是保序的 要证 f 是 A 1, 1 到 A 2, 2 的格同构, 即要证 f(a 1 b) = f(a) 2 f(b), (15) f(a 1 b) = f(a) 2 f(b) (16) 要证 (15) 式成立, 即要证 f(a 1 b) 2 f(a) 2 f(b), f(a) 2 f(b) 2 f(a 1 b) 同时成立 黄正华 ( 武汉大学 ) 格 December 3, / 103

168 续证 : (2) 假设对任意 a, b A 1, a 1 b f(a) 2 f(b) 即映射 f 是保序的 要证 f 是 A 1, 1 到 A 2, 2 的格同构, 即要证 f(a 1 b) = f(a) 2 f(b), (15) f(a 1 b) = f(a) 2 f(b) (16) 要证 (15) 式成立, 即要证 f(a 1 b) 2 f(a) 2 f(b), f(a) 2 f(b) 2 f(a 1 b) 同时成立 因为 a 1 b 1 a, a 1 b 1 b, 由 f 的保序性, 得 f(a 1 b) 2 f(a), f(a 1 b) 2 f(b) 黄正华 ( 武汉大学 ) 格 December 3, / 103

169 续证 : (2) 假设对任意 a, b A 1, a 1 b f(a) 2 f(b) 即映射 f 是保序的 要证 f 是 A 1, 1 到 A 2, 2 的格同构, 即要证 f(a 1 b) = f(a) 2 f(b), (15) f(a 1 b) = f(a) 2 f(b) (16) 要证 (15) 式成立, 即要证 f(a 1 b) 2 f(a) 2 f(b), f(a) 2 f(b) 2 f(a 1 b) 同时成立 因为 a 1 b 1 a, a 1 b 1 b, 由 f 的保序性, 得 f(a 1 b) 2 f(a), f(a 1 b) 2 f(b) 所以 f(a 1 b) 2 f(a) 2 f(b) 黄正华 ( 武汉大学 ) 格 December 3, / 103

170 续证 : 记 f(a) 2 f(b) f(d), 则 f(d) 2 f(a), f(d) 2 f(b) 黄正华 ( 武汉大学 ) 格 December 3, / 103

171 续证 : 记 f(a) 2 f(b) f(d), 则 f(d) 2 f(a), f(d) 2 f(b) 由 f 的保序性, 得 d 1 a, d 1 b 所以, d 1 a 1 b 黄正华 ( 武汉大学 ) 格 December 3, / 103

172 续证 : 记 f(a) 2 f(b) f(d), 则 f(d) 2 f(a), f(d) 2 f(b) 由 f 的保序性, 得 d 1 a, d 1 b 所以, d 1 a 1 b 再由保序性, 得 f(d) 2 f(a 1 b), 即 f(a) 2 f(b) 2 f(a 1 b) 黄正华 ( 武汉大学 ) 格 December 3, / 103

173 续证 : 记 f(a) 2 f(b) f(d), 则 f(d) 2 f(a), f(d) 2 f(b) 由 f 的保序性, 得 d 1 a, d 1 b 所以, d 1 a 1 b 再由保序性, 得 f(d) 2 f(a 1 b), 即 f(a) 2 f(b) 2 f(a 1 b) 类似可证 f(a 1 b) = f(a) 2 f(b) 成立 故 f 是 A 1, 1 到 A 2, 2 的格同构 黄正华 ( 武汉大学 ) 格 December 3, / 103

174 练习 设 A, 是一个格, 任取 a, b 且 a b ( 意指 a b 且 a b) 构造集合 则 B, 也是一个格, B = { x x A 且 a x b } 黄正华 ( 武汉大学 ) 格 December 3, / 103

175 练习 设 A, 是一个格, 任取 a, b 且 a b ( 意指 a b 且 a b) 构造集合 则 B, 也是一个格, 证可证 B, 是 A, 的子格 B = { x x A 且 a x b } 黄正华 ( 武汉大学 ) 格 December 3, / 103

176 练习 设 A, 是一个格, 任取 a, b 且 a b ( 意指 a b 且 a b) 构造集合 则 B, 也是一个格, B = { x x A 且 a x b } 证可证 B, 是 A, 的子格 下证 集合 B 关于运算是封闭的 即可 黄正华 ( 武汉大学 ) 格 December 3, / 103

177 练习 设 A, 是一个格, 任取 a, b 且 a b ( 意指 a b 且 a b) 构造集合 则 B, 也是一个格, B = { x x A 且 a x b } 证可证 B, 是 A, 的子格 下证 集合 B 关于运算是封闭的 即可 任意 x, y B A, 有 a x b, a y b 黄正华 ( 武汉大学 ) 格 December 3, / 103

178 练习 设 A, 是一个格, 任取 a, b 且 a b ( 意指 a b 且 a b) 构造集合 则 B, 也是一个格, B = { x x A 且 a x b } 证可证 B, 是 A, 的子格 下证 集合 B 关于运算是封闭的 即可 任意 x, y B A, 有 所以由 a x, 和 a y, a x b, a y b 黄正华 ( 武汉大学 ) 格 December 3, / 103

179 练习 设 A, 是一个格, 任取 a, b 且 a b ( 意指 a b 且 a b) 构造集合 则 B, 也是一个格, B = { x x A 且 a x b } 证可证 B, 是 A, 的子格 下证 集合 B 关于运算是封闭的 即可 任意 x, y B A, 有 a x b, a y b 所以由 a x, 和 a y, 可得 a x y 黄正华 ( 武汉大学 ) 格 December 3, / 103

180 练习 设 A, 是一个格, 任取 a, b 且 a b ( 意指 a b 且 a b) 构造集合 则 B, 也是一个格, B = { x x A 且 a x b } 证可证 B, 是 A, 的子格 下证 集合 B 关于运算是封闭的 即可 任意 x, y B A, 有 a x b, a y b 所以由 a x, 和 a y, 可得 a x y 由 x b, 和 y b, 黄正华 ( 武汉大学 ) 格 December 3, / 103

181 练习 设 A, 是一个格, 任取 a, b 且 a b ( 意指 a b 且 a b) 构造集合 则 B, 也是一个格, B = { x x A 且 a x b } 证可证 B, 是 A, 的子格 下证 集合 B 关于运算是封闭的 即可 任意 x, y B A, 有 a x b, a y b 所以由 a x, 和 a y, 可得 由 x b, 和 y b, 可得 a x y x y b 黄正华 ( 武汉大学 ) 格 December 3, / 103

182 练习 设 A, 是一个格, 任取 a, b 且 a b ( 意指 a b 且 a b) 构造集合 则 B, 也是一个格, B = { x x A 且 a x b } 证可证 B, 是 A, 的子格 下证 集合 B 关于运算是封闭的 即可 任意 x, y B A, 有 a x b, a y b 所以由 a x, 和 a y, 可得 由 x b, 和 y b, 可得 a x y x y b 所以 a x y b, 即 x y B 黄正华 ( 武汉大学 ) 格 December 3, / 103

183 练习 设 A, 是一个格, 任取 a, b 且 a b ( 意指 a b 且 a b) 构造集合 则 B, 也是一个格, B = { x x A 且 a x b } 证可证 B, 是 A, 的子格 下证 集合 B 关于运算是封闭的 即可 任意 x, y B A, 有 a x b, a y b 所以由 a x, 和 a y, 可得 由 x b, 和 y b, 可得 a x y x y b 所以 a x y b, 即 x y B 同理可证 x y B 黄正华 ( 武汉大学 ) 格 December 3, / 103

184 1 格的定义 2 子格与格同态 3 几种特殊的格 4 布尔代数 5 有限布尔代数的表示定理 黄正华 ( 武汉大学 ) 格 December 3, / 103

185 本节介绍几种特殊的格 : 分配格 ; 有补格 ; 模格 黄正华 ( 武汉大学 ) 格 December 3, / 103

186 分配格 格中任意三个元素 a, b, c 满足分配不等式 : a (b c) (a b) (a c) (17) a (b c) (a b) (a c) (18) 黄正华 ( 武汉大学 ) 格 December 3, / 103

187 分配格 格中任意三个元素 a, b, c 满足分配不等式 : a (b c) (a b) (a c) (17) a (b c) (a b) (a c) (18) 是否存在格使上述两式等号成立呢? 黄正华 ( 武汉大学 ) 格 December 3, / 103

188 分配格 格中任意三个元素 a, b, c 满足分配不等式 : a (b c) (a b) (a c) (17) a (b c) (a b) (a c) (18) 是否存在格使上述两式等号成立呢? 回答是肯定的 比如格的典型例子 P(S),, 其分配律是成立的 黄正华 ( 武汉大学 ) 格 December 3, / 103

189 分配格 Definition 31 设 A,, 是由格 A, 诱导的代数系统 如果对任意 a, b, c A, 满足 则称 A, 是分配格 a (b c) = (a b) (a c), ( 并对交可分配 ) a (b c) = (a b) (a c) ( 交对并可分配 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

190 分配格 Definition 31 设 A,, 是由格 A, 诱导的代数系统 如果对任意 a, b, c A, 满足 则称 A, 是分配格 a (b c) = (a b) (a c), ( 并对交可分配 ) a (b c) = (a b) (a c) ( 交对并可分配 ) 这和我们熟知的集合运算的分配律, 有完全相同的形式 : A (B C) = (A B) (A C), A (B C) = (A B) (A C) 黄正华 ( 武汉大学 ) 格 December 3, / 103

191 分配格 Definition 31 设 A,, 是由格 A, 诱导的代数系统 如果对任意 a, b, c A, 满足 则称 A, 是分配格 a (b c) = (a b) (a c), ( 并对交可分配 ) a (b c) = (a b) (a c) ( 交对并可分配 ) 这和我们熟知的集合运算的分配律, 有完全相同的形式 : A (B C) = (A B) (A C), A (B C) = (A B) (A C) 可见 P(S), 也是分配格的典型例子 黄正华 ( 武汉大学 ) 格 December 3, / 103

192 Example 32 判断下列各图是否为分配格? c e d e e d {a, b} {a, b, c} {a, c} {b, c} ḃ b c d b c {a} {b} {c} 1 a 2 ȧ 3 ȧ 4 解 (1), (4) 是分配格 (2), (3) 不是分配格 黄正华 ( 武汉大学 ) 格 December 3, / 103

193 Example 32 判断下列各图是否为分配格? c e d e e d {a, b} {a, b, c} {a, c} {b, c} ḃ b c d b c {a} {b} {c} 1 a 2 ȧ 3 ȧ 4 解 (1), (4) 是分配格 (2), (3) 不是分配格 在 (2) 中, b (c d) = b e = b, (b c) (b d) = a a = a, 黄正华 ( 武汉大学 ) 格 December 3, / 103

194 Example 32 判断下列各图是否为分配格? c e d e e d {a, b} {a, b, c} {a, c} {b, c} ḃ b c d b c {a} {b} {c} 1 a 2 ȧ 3 ȧ 4 解 (1), (4) 是分配格 (2), (3) 不是分配格 在 (2) 中, b (c d) = b e = b, (b c) (b d) = a a = a, 在 (3) 中, d (b c) = d e = d, (d b) (d c) = a c = c 黄正华 ( 武汉大学 ) 格 December 3, / 103

195 Example 32 判断下列各图是否为分配格? c e d e e d {a, b} {a, b, c} {a, c} {b, c} ḃ b c d b c {a} {b} {c} 1 a 2 ȧ 3 ȧ 4 (2), (3) 这两个具有五个元素的格是很重要的, 分别称为钻石格 (diamond lattice) 和五角格 (pentagon lattice), 分别记为 M 3 和 N 5 黄正华 ( 武汉大学 ) 格 December 3, / 103

196 有一个如下的重要结论 ( 证明略去 ) Theorem 33 一个格是分配格的充要条件是, 在该格中没有任何子格与 M 3 和 N 5 中的任一 个同构 (a) 钻石格 M 3 (b) 五角格 N 5 黄正华 ( 武汉大学 ) 格 December 3, / 103

197 Example 34 如图 (a) 所示的格中, {a, b, d, g, e}, 是格 {a, b, c, d, e, f, g}, 的子格, a b c ė d g f (a) (b) 黄正华 ( 武汉大学 ) 格 December 3, / 103

198 Example 34 如图 (a) 所示的格中, {a, b, d, g, e}, 是格 {a, b, c, d, e, f, g}, 的子格, a b c ė d g f (a) (b) 而这个子格与图 (b) 是同构的, 所以, 图 (a) 所示的格不是分配格 黄正华 ( 武汉大学 ) 格 December 3, / 103

199 Theorem 35 如果格中运算 对运算 可分配, 则运算 对运算 可分配 反之亦然 黄正华 ( 武汉大学 ) 格 December 3, / 103

200 Theorem 35 如果格中运算 对运算 可分配, 则运算 对运算 可分配 反之亦然 证 设 a, b, c 是格中任意元素, 如果 a (b c) = (a b) (a c) (19) 黄正华 ( 武汉大学 ) 格 December 3, / 103

201 Theorem 35 如果格中运算 对运算 可分配, 则运算 对运算 可分配 反之亦然 证设 a, b, c 是格中任意元素, 如果 a (b c) = (a b) (a c) (19) 则 (a b) (a c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

202 Theorem 35 如果格中运算 对运算 可分配, 则运算 对运算 可分配 反之亦然 证设 a, b, c 是格中任意元素, 如果 a (b c) = (a b) (a c) (19) 则 (a b) (a c) = ( (a b) a ) ( (a b) c ) ( 对 可分配 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

203 Theorem 35 如果格中运算 对运算 可分配, 则运算 对运算 可分配 反之亦然 证 则 设 a, b, c 是格中任意元素, 如果 a (b c) = (a b) (a c) (19) (a b) (a c) = ( (a b) a ) ( (a b) c ) ( 对 可分配 ) = a ( (a b) c ) ( (a b) a = a ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

204 Theorem 35 如果格中运算 对运算 可分配, 则运算 对运算 可分配 反之亦然 证 则 设 a, b, c 是格中任意元素, 如果 a (b c) = (a b) (a c) (19) (a b) (a c) = ( (a b) a ) ( (a b) c ) ( 对 可分配 ) = a ( (a b) c ) ( (a b) a = a ) = a ( (a c) (b c) ) ( 对 可分配 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

205 Theorem 35 如果格中运算 对运算 可分配, 则运算 对运算 可分配 反之亦然 证 则 设 a, b, c 是格中任意元素, 如果 a (b c) = (a b) (a c) (19) (a b) (a c) = ( (a b) a ) ( (a b) c ) ( 对 可分配 ) = a ( (a b) c ) ( (a b) a = a ) = a ( (a c) (b c) ) ( 对 可分配 ) = ( a (a c) ) (b c) ( 结合律 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

206 Theorem 35 如果格中运算 对运算 可分配, 则运算 对运算 可分配 反之亦然 证 则 设 a, b, c 是格中任意元素, 如果 a (b c) = (a b) (a c) (19) (a b) (a c) = ( (a b) a ) ( (a b) c ) ( 对 可分配 ) = a ( (a b) c ) ( (a b) a = a ) = a ( (a c) (b c) ) ( 对 可分配 ) = ( a (a c) ) (b c) ( 结合律 ) = a (b c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

207 Theorem 35 如果格中运算 对运算 可分配, 则运算 对运算 可分配 反之亦然 证 则 设 a, b, c 是格中任意元素, 如果 a (b c) = (a b) (a c) (19) (a b) (a c) = ( (a b) a ) ( (a b) c ) ( 对 可分配 ) = a ( (a b) c ) ( (a b) a = a ) = a ( (a c) (b c) ) ( 对 可分配 ) = ( a (a c) ) (b c) ( 结合律 ) = a (b c) 类似可证 a (b c) = (a b) (a c) a (b c) = (a b) (a c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

208 Theorem 36 链是分配格 黄正华 ( 武汉大学 ) 格 December 3, / 103

209 Theorem 36 链是分配格 证设 A, 是链, 则 A, 是格 黄正华 ( 武汉大学 ) 格 December 3, / 103

210 Theorem 36 链是分配格 证设 A, 是链, 则 A, 是格 ( 链中的任意两个元都是可比的 比如 a b, 则 a b = a, a b = b 任意两个元素都有最小上界和最大下界, 所以是格 ) 黄正华 ( 武汉大学 ) 格 December 3, / 103

211 Theorem 36 链是分配格 证设 A, 是链, 则 A, 是格 ( 链中的任意两个元都是可比的 比如 a b, 则 a b = a, a b = b 任意两个元素都有最小上界和最大下界, 所以是格 ) 对任意 a, b, c A, 可分两种情况讨论 : 1 a b 或 a c 2 b a 且 c a 黄正华 ( 武汉大学 ) 格 December 3, / 103

212 Theorem 36 链是分配格 证设 A, 是链, 则 A, 是格 ( 链中的任意两个元都是可比的 比如 a b, 则 a b = a, a b = b 任意两个元素都有最小上界和最大下界, 所以是格 ) 对任意 a, b, c A, 可分两种情况讨论 : 1 a b 或 a c 2 b a 且 c a 1 a b 或 a c a c = a, b c, a (b c) = a b = a, c b 黄正华 ( 武汉大学 ) 格 December 3, / 103

213 Theorem 36 链是分配格 证设 A, 是链, 则 A, 是格 ( 链中的任意两个元都是可比的 比如 a b, 则 a b = a, a b = b 任意两个元素都有最小上界和最大下界, 所以是格 ) 对任意 a, b, c A, 可分两种情况讨论 : 1 a b 或 a c 2 b a 且 c a 1 a b 或 a c a c = a, b c, a (b c) = a b = a, c b a (a c) = a, a b, (a b) (a c) = (a b) a = a, a c 黄正华 ( 武汉大学 ) 格 December 3, / 103

214 Theorem 36 链是分配格 证设 A, 是链, 则 A, 是格 ( 链中的任意两个元都是可比的 比如 a b, 则 a b = a, a b = b 任意两个元素都有最小上界和最大下界, 所以是格 ) 对任意 a, b, c A, 可分两种情况讨论 : 1 a b 或 a c 2 b a 且 c a 1 a b 或 a c a c = a, b c, a (b c) = a b = a, c b a (a c) = a, a b, (a b) (a c) = (a b) a = a, a c 所以, a (b c) = (a b) (a c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

215 续证 : 2 b a 且 c a 这时必有 b c a ( 上界 ) 进而有 a (b c) = b c 黄正华 ( 武汉大学 ) 格 December 3, / 103

216 续证 : 2 b a 且 c a 这时必有 b c a ( 上界 ) 进而有 a (b c) = b c 另一方面, 由 b a 且 c a 可得 : (a b) (a c) = b c 黄正华 ( 武汉大学 ) 格 December 3, / 103

217 续证 : 2 b a 且 c a 这时必有 b c a ( 上界 ) 进而有 a (b c) = b c 另一方面, 由 b a 且 c a 可得 : (a b) (a c) = b c 所以, a (b c) = (a b) (a c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

218 续证 : 2 b a 且 c a 这时必有 b c a ( 上界 ) 进而有 a (b c) = b c 另一方面, 由 b a 且 c a 可得 : (a b) (a c) = b c 所以, a (b c) = (a b) (a c) 得证 : 链是分配格 黄正华 ( 武汉大学 ) 格 December 3, / 103

219 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 a c a (b c) (a b) c 黄正华 ( 武汉大学 ) 格 December 3, / 103

220 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 a c a (b c) (a b) c 证 1 设 a c 黄正华 ( 武汉大学 ) 格 December 3, / 103

221 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 a c a (b c) (a b) c 证 1 设 a c 由 a c (a c) = c, 黄正华 ( 武汉大学 ) 格 December 3, / 103

222 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 证 a c a (b c) (a b) c 1 设 a c 由 a c (a c) = c, 得 a (b c) (a b) (a c) ( 分配不等式 ) = (a b) c ( ) (a c) = c 黄正华 ( 武汉大学 ) 格 December 3, / 103

223 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 证 a c a (b c) (a b) c 1 设 a c 由 a c (a c) = c, 得 a (b c) (a b) (a c) ( 分配不等式 ) = (a b) c ( ) (a c) = c 2 若 a (b c) (a b) c, 黄正华 ( 武汉大学 ) 格 December 3, / 103

224 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 证 a c a (b c) (a b) c 1 设 a c 由 a c (a c) = c, 得 a (b c) (a b) (a c) ( 分配不等式 ) = (a b) c ( ) (a c) = c 2 若 a (b c) (a b) c, 则由 黄正华 ( 武汉大学 ) 格 December 3, / 103

225 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 证 a c a (b c) (a b) c 1 设 a c 由 a c (a c) = c, 得 a (b c) (a b) (a c) ( 分配不等式 ) = (a b) c ( ) (a c) = c 2 若 a (b c) (a b) c, 则由 黄正华 ( 武汉大学 ) 格 December 3, / 103

226 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 证 a c a (b c) (a b) c 1 设 a c 由 a c (a c) = c, 得 a (b c) (a b) (a c) ( 分配不等式 ) ( ) = (a b) c (a c) = c 2 若 a (b c) (a b) c, 则由 a a (b c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

227 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 证 a c a (b c) (a b) c 1 设 a c 由 a c (a c) = c, 得 a (b c) (a b) (a c) ( 分配不等式 ) ( ) = (a b) c (a c) = c 2 若 a (b c) (a b) c, 则由 a a (b c) (a b) c c 黄正华 ( 武汉大学 ) 格 December 3, / 103

228 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 证 a c a (b c) (a b) c 1 设 a c 由 a c (a c) = c, 得 a (b c) (a b) (a c) ( 分配不等式 ) ( ) = (a b) c (a c) = c 2 若 a (b c) (a b) c, 则由 a a (b c) (a b) c c 黄正华 ( 武汉大学 ) 格 December 3, / 103

229 模格 Theorem 37 设 A, 是一个格, 则对于任意的 a, b, c A, 有 证 a c a (b c) (a b) c 1 设 a c 由 a c (a c) = c, 得 a (b c) (a b) (a c) ( 分配不等式 ) ( ) = (a b) c (a c) = c 2 若 a (b c) (a b) c, 则由 a a (b c) (a b) c c 所以, a c 黄正华 ( 武汉大学 ) 格 December 3, / 103

230 模格 Definition 38 设 A,, 是由格 A, 诱导的代数系统 如果对任意 a, b, c A, 只 要 a c, 就有 则称 A, 是模格 (modular lattice) a (b c) = (a b) c, (20) 黄正华 ( 武汉大学 ) 格 December 3, / 103

231 模格 Definition 38 设 A,, 是由格 A, 诱导的代数系统 如果对任意 a, b, c A, 只 要 a c, 就有 则称 A, 是模格 (modular lattice) 对照前述结论 : 设 A, 是一个格, 则对于任意的 a, b, c A, 有 a (b c) = (a b) c, (20) a c a (b c) (a b) c (21) 把 (20) 式与 分配等式 相比较 : a (b c) = (a b) (a c), (22) 黄正华 ( 武汉大学 ) 格 December 3, / 103

232 模格 Definition 38 设 A,, 是由格 A, 诱导的代数系统 如果对任意 a, b, c A, 只 要 a c, 就有 则称 A, 是模格 (modular lattice) 对照前述结论 : 设 A, 是一个格, 则对于任意的 a, b, c A, 有 a (b c) = (a b) c, (20) a c a (b c) (a b) c (21) 把 (20) 式与 分配等式 相比较 : a (b c) = (a b) (a c), (22) 知分配格必定是模格 黄正华 ( 武汉大学 ) 格 December 3, / 103

233 Theorem 39 分配格必定是模格 黄正华 ( 武汉大学 ) 格 December 3, / 103

234 Theorem 39 分配格必定是模格 证 设 A, 是分配格, 任意的 a, b, c A, 若 a c, 则 a c = c 黄正华 ( 武汉大学 ) 格 December 3, / 103

235 Theorem 39 分配格必定是模格 证 设 A, 是分配格, 任意的 a, b, c A, 若 a c, 则 a c = c 故 a (b c) = (a b) (a c) ( 分配律 ) = (a b) c 黄正华 ( 武汉大学 ) 格 December 3, / 103

236 Theorem 39 分配格必定是模格 证 设 A, 是分配格, 任意的 a, b, c A, 若 a c, 则 a c = c 故 a (b c) = (a b) (a c) ( 分配律 ) = (a b) c 即证 A, 是模格 黄正华 ( 武汉大学 ) 格 December 3, / 103

237 模格不一定是分配格 Example 310 钻石格 M 3 不是分配格, 但它是模格 1 x y z 0 黄正华 ( 武汉大学 ) 格 December 3, / 103

238 模格不一定是分配格 Example 310 钻石格 M 3 不是分配格, 但它是模格 对于任意的 a, b, c {0, 1, x, y, z}, 若有 a c, 则必 有 a = 0 或 者 c = 1 1 x y z 0 黄正华 ( 武汉大学 ) 格 December 3, / 103

239 模格不一定是分配格 Example x y z 钻石格 M 3 不是分配格, 但它是模格 对于任意的 a, b, c {0, 1, x, y, z}, 若有 a c, 则必有 a = 0 或 者 c = 1 若 a = 0, 则 a (b c) = b c, (a b) c = b c 0 黄正华 ( 武汉大学 ) 格 December 3, / 103

240 模格不一定是分配格 Example x y 0 z 钻石格 M 3 不是分配格, 但它是模格 对于任意的 a, b, c {0, 1, x, y, z}, 若有 a c, 则必有 a = 0 或 者 c = 1 若 a = 0, 则 a (b c) = b c, (a b) c = b c 若 c = 1, 则 a (b c) = a b, (a b) c = a b 黄正华 ( 武汉大学 ) 格 December 3, / 103

241 模格不一定是分配格 Example x y 0 z 钻石格 M 3 不是分配格, 但它是模格 对于任意的 a, b, c {0, 1, x, y, z}, 若有 a c, 则必有 a = 0 或 者 c = 1 若 a = 0, 则 a (b c) = b c, (a b) c = b c 若 c = 1, 则 a (b c) = a b, (a b) c = a b 所以它是模格 黄正华 ( 武汉大学 ) 格 December 3, / 103

242 练习 试举两个含有 6 个元素的格, 一个是分配格, 另一个不是分配格 黄正华 ( 武汉大学 ) 格 December 3, / 103

243 练习 试举两个含有 6 个元素的格, 一个是分配格, 另一个不是分配格 解分配格如图 (a) 所示, 不是分配格如图 (b) 所示 (a) (b) 黄正华 ( 武汉大学 ) 格 December 3, / 103

244 练习 试举两个含有 6 个元素的格, 一个是分配格, 另一个不是分配格 解分配格如图 (a) 所示, 不是分配格如图 (b) 所示 (a) (b) 图 (b) 中有子格与钻石格同构, 所以图 (b) 不是分配格 黄正华 ( 武汉大学 ) 格 December 3, / 103

245 练习 试举两个含有 6 个元素的格, 一个是分配格, 另一个不是分配格 解分配格如图 (a) 所示, 不是分配格如图 (b) 所示 (a) (b) 图 (b) 中有子格与钻石格同构, 所以图 (b) 不是分配格 当然, 分配格的最直接例子是链 黄正华 ( 武汉大学 ) 格 December 3, / 103

246 练习 试举两个含有 6 个元素的格, 一个是分配格, 另一个不是分配格 解分配格如图 (a) 所示, 不是分配格如图 (b) 所示 (a) (b) 图 (b) 中有子格与钻石格同构, 所以图 (b) 不是分配格 当然, 分配格的最直接例子是链 非分配格还有很多, 比如六个元素组成的 一个环形结构, 此时在其中任取 5 点都是和五角格 N 5 同构的 黄正华 ( 武汉大学 ) 格 December 3, / 103

247 练习 在下图中给出的几个格, 哪个是分配格? a c b e d f (a) (b) (c) 黄正华 ( 武汉大学 ) 格 December 3, / 103

248 练习 在下图中给出的几个格, 哪个是分配格? a c b e d f (a) (b) (c) 解图 (b) 是分配格 图 (a), (c) 中都有子格与 同构, 所以图 (a), (c) 不是分配格 黄正华 ( 武汉大学 ) 格 December 3, / 103

249 练习 在下图中给出的几个格, 哪个是分配格? a c b e d f (a) (b) (c) 解图 (b) 是分配格 图 (a), (c) 中都有子格与 同构, 所以图 (a), (c) 不是分配格 黄正华 ( 武汉大学 ) 格 December 3, / 103

250 格的全下界 全上界 Definition 311 设 A, 是格, 如果存在元素 a A, 对任意 x A, 都有 a x, 则称 a 为格 A, 的全下界 格的全下界记为 0 黄正华 ( 武汉大学 ) 格 December 3, / 103

251 格的全下界 全上界 Definition 311 设 A, 是格, 如果存在元素 a A, 对任意 x A, 都有 a x, 则称 a 为格 A, 的全下界 格的全下界记为 0 Definition 312 设 A, 是格, 如果存在元素 a A, 对任意 x A, 都有 x a, 则称 a 为格 A, 的全上界 格的全上界记为 1 黄正华 ( 武汉大学 ) 格 December 3, / 103

252 格的全下界 全上界 Theorem 313 格的全下界 ( 全上界 ) 如果存在, 则必惟一 黄正华 ( 武汉大学 ) 格 December 3, / 103

253 格的全下界 全上界 Theorem 313 格的全下界 ( 全上界 ) 如果存在, 则必惟一 证假设格 A, 有两个全下界 a 和 b 黄正华 ( 武汉大学 ) 格 December 3, / 103

254 格的全下界 全上界 Theorem 313 格的全下界 ( 全上界 ) 如果存在, 则必惟一 证 假设格 A, 有两个全下界 a 和 b 那么按全下界的定义, 应有 a b 和 b a 同时成立, 黄正华 ( 武汉大学 ) 格 December 3, / 103

255 格的全下界 全上界 Theorem 313 格的全下界 ( 全上界 ) 如果存在, 则必惟一 证 假设格 A, 有两个全下界 a 和 b 那么按全下界的定义, 应有 a b 和 b a 同时成立, 从而 a = b 黄正华 ( 武汉大学 ) 格 December 3, / 103

256 有界格 Definition 314 具有全下界和全上界的格称为有界格 黄正华 ( 武汉大学 ) 格 December 3, / 103

257 有界格 Definition 314 具有全下界和全上界的格称为有界格 Example 315 设 S 是有限集合, 那么格 P(S), 是有界格, 其全下界是, 全上界是 S 黄正华 ( 武汉大学 ) 格 December 3, / 103

258 有界格 Definition 314 具有全下界和全上界的格称为有界格 Example 315 设 S 是有限集合, 那么格 P(S), 是有界格, 其全下界是, 全上界是 S Example 316 如图所示的格中, h 是全下界, a 是全上界 该格是有界格 a b d c e f g h 黄正华 ( 武汉大学 ) 格 December 3, / 103

259 Theorem 317 设 A, 是有界格, 则对任意 a A, 必有 a 1 = 1, a 1 = a; (23) a 0 = a, a 0 = 0 (24) 黄正华 ( 武汉大学 ) 格 December 3, / 103

260 Theorem 317 设 A, 是有界格, 则对任意 a A, 必有 a 1 = 1, a 1 = a; (23) a 0 = a, a 0 = 0 (24) 证因 A, 是有界格, 对任意 a A, 应有 0 a 1 黄正华 ( 武汉大学 ) 格 December 3, / 103

261 Theorem 317 设 A, 是有界格, 则对任意 a A, 必有 a 1 = 1, a 1 = a; (23) a 0 = a, a 0 = 0 (24) 证因 A, 是有界格, 对任意 a A, 应有 0 a 1 再由格的性质, 即可得 : a 1 = 1, a 1 = a; a 0 = a, a 0 = 0 黄正华 ( 武汉大学 ) 格 December 3, / 103

262 Theorem 317 设 A, 是有界格, 则对任意 a A, 必有 a 1 = 1, a 1 = a; (23) 注 a 0 = a, a 0 = 0 (24) 运算 的零元和幺元分别为 1 和 0 黄正华 ( 武汉大学 ) 格 December 3, / 103

263 Theorem 317 设 A, 是有界格, 则对任意 a A, 必有 a 1 = 1, a 1 = a; (23) 注 a 0 = a, a 0 = 0 (24) 运算 的零元和幺元分别为 1 和 0 a 1 = 1 a = 1 1 是 的零元 ; 黄正华 ( 武汉大学 ) 格 December 3, / 103

264 Theorem 317 设 A, 是有界格, 则对任意 a A, 必有 a 1 = 1, a 1 = a; (23) 注 a 0 = a, a 0 = 0 (24) 运算 的零元和幺元分别为 1 和 0 a 1 = 1 a = 1 1 是 的零元 ; a 0 = 0 a = a 0 是 的幺元 黄正华 ( 武汉大学 ) 格 December 3, / 103

265 Theorem 317 设 A, 是有界格, 则对任意 a A, 必有 a 1 = 1, a 1 = a; (23) 注 a 0 = a, a 0 = 0 (24) 运算 的零元和幺元分别为 1 和 0 a 1 = 1 a = 1 1 是 的零元 ; a 0 = 0 a = a 0 是 的幺元 运算 的零元和幺元分别为 0 和 1 黄正华 ( 武汉大学 ) 格 December 3, / 103

266 Theorem 317 设 A, 是有界格, 则对任意 a A, 必有 a 1 = 1, a 1 = a; (23) 注 a 0 = a, a 0 = 0 (24) 运算 的零元和幺元分别为 1 和 0 a 1 = 1 a = 1 1 是 的零元 ; a 0 = 0 a = a 0 是 的幺元 运算 的零元和幺元分别为 0 和 1 a 0 = 0 a = 0 0 是 的零元 ; 黄正华 ( 武汉大学 ) 格 December 3, / 103

267 Theorem 317 设 A, 是有界格, 则对任意 a A, 必有 a 1 = 1, a 1 = a; (23) 注 a 0 = a, a 0 = 0 (24) 运算 的零元和幺元分别为 1 和 0 a 1 = 1 a = 1 1 是 的零元 ; a 0 = 0 a = a 0 是 的幺元 运算 的零元和幺元分别为 0 和 1 a 0 = 0 a = 0 0 是 的零元 ; a 1 = 1 a = a 1 是 的幺元 黄正华 ( 武汉大学 ) 格 December 3, / 103

268 补元 Definition 318 设 A, 是有界格, 对 a A, 若存在 b A, 使 则称 b 是 a 的补元 a b = 1, a b = 0, 黄正华 ( 武汉大学 ) 格 December 3, / 103

269 补元 Definition 318 设 A, 是有界格, 对 a A, 若存在 b A, 使 则称 b 是 a 的补元 a b = 1, a b = 0, Example 319 设 S 是有限集合, 对有界格 P(S),, 其全下界是, 全上界是 S 任 意 A P(S), A 的补元是 S A 黄正华 ( 武汉大学 ) 格 December 3, / 103

270 补元 Example 320 a 1 b c 如图所示有界格中, d 和 c, d 和 e, a 和 e, 0 和 1 互为 补元, 即 a, c, d, e, 0, 1 都有补元 d e 0 黄正华 ( 武汉大学 ) 格 December 3, / 103

271 补元 Example 320 a 1 b c 如图所示有界格中, d 和 c, d 和 e, a 和 e, 0 和 1 互为补元, 即 a, c, d, e, 0, 1 都有补元 但 b 没有补元 d e 0 黄正华 ( 武汉大学 ) 格 December 3, / 103

272 补元 Example 320 a 1 c 如图所示有界格中, d 和 c, d 和 e, a 和 e, 0 和 1 互为 补元, 即 a, c, d, e, 0, 1 都有补元 d b e 但 b 没有补元 一个元的补元可以有多个 : 例如, d, e 有两个补元 ; 0 黄正华 ( 武汉大学 ) 格 December 3, / 103

273 补元 Example 320 a 1 c 如图所示有界格中, d 和 c, d 和 e, a 和 e, 0 和 1 互为 补元, 即 a, c, d, e, 0, 1 都有补元 d b 0 e 但 b 没有补元 一个元的补元可以有多个 : 例如, d, e 有两个补元 ; 0 是 1 惟一的补元 ; 1 是 0 惟一的补元 黄正华 ( 武汉大学 ) 格 December 3, / 103