[理学]格与布尔代数 课件.ppt

对于非分配格，定理5－23不成立。 c　 d = c b , c d = c b ， 但 b ≠ d 。 例如， e d b c a 二 有补格 1．最小元素0和最大元素1 例4 I；≤是一个格，但这个格既无最小元素，又无最大元素。 N；≤这个格有最小元素，但没有最大元素。 格2U； 中无论U是什么样的集合，均有最小元素φ和最大元素U。 具有最小元素和最大元素的格称为有界格。 在有界格L；≤中，对任意L，有0≤ ， ≤1. 于是由定理5-14，对任意 ，有 2．补元素 定义5-6 设L； ， 是一个有界格， L，若存在元素 L，使得 =1 = 0，则称 是 的补元素。 在任一有界格中0和1互为补元素。 例5 1 a b c d 0 1 a b c d e g 0 f * 第五章 格与布尔代数 ? 本章在了解了代数系统一般概念的基础上，着重介绍的包含有两个代数运算的代数系统:格和布尔代数。主要讨论这些代数系统的相关基本概念和性质 主要内容如下： 5.1 格； 5.2 分配格和有补格； 5.3 布尔代数 一、 格 1．格的定义 定义5-1 设L；≤是一个偏序集，如果L中任意两个元素都存在着最大下界和最小上界，则称L；≤是格。 =glb（ ， ）， =lub（ ， ）。 若L；≤是一个格，则意味着L；≤也是一个形为L； ， 的代数系统，其中 和 是L上的两个二元运算，对于任意 ， ， 表示在偏序“≤”意义下， 和 的最小上界， 表示 和 的最大下界。 例1 试判断下列次序图给出的偏序集哪些是格？ 解 （a）不是格， (b)不是格， (c)是一个格， （d）是一个格 e f d c a b (a) e d b c a (b) f h g d e b c a (c) 5 1 2 10 15 3 6 30 (d) 在格＜L；≤中有如下四个关系式成立: 2．格的性质 定理5-1 在格L；≤中，对于任意 以下三式中若任意一式成立，那么其它两式也成立. 证明 ① =＞ ② 设 ， ② = ③ 设 ③ = ① 设 定义5-2 设L；≤是格，P是包含格的元素和符号=、≤、≥，∧ ，∨的命题，将P中的≤、≥，∧和∨分别替换成≥、 ≤、 ∨和∧所得的命题PD称为P的对偶。 例如 的对偶是 对偶原理 ： 对于格L，≤上的任一真命题P，其对偶 PD 亦为格L，≤上的真命题。 定理5-2（交换律） 设L；≤是格，则对任意的 有: 定理5-3 （结合律） 设L；≤是格，则对任意的 ，有 证明 定理5-4 （吸收律） 设＜L；≤＞是格，则对任意 ，有 证明 (b) 由（5-4） 另一方面，由（5-1） 于是，由（5-5） （2） 由（1)、(2）和反对称性 定理5-5 （等幂律） 设＜L；≤＞是格，则对任意 ，有 证明 （a）由定理5-17 , 定理5-6 （格的保序性） 设＜L；≤＞是格，则对于任意 ，有 证明 （1） ① 又已知 ② 由①,②和 因为 所以由(1)有 例2 设 L = ，L上的整除关系 与L构成一个格，记作L；≤， 3∨( 6 ∧ 4 ) = 3 ∨ 1= 3 (3∨6)∧(3∨4) = 6 ∧ 12 = 6 于是 3∨(6∧4)≠(3∨6)∧(3∨4) 6∧(3∨4) = 6∧12 = 6 (6∧3)∨(6∧4)= 3∨1= 3 于是 6∧(3∨4)≠(6∧3)∨(6∧4) 12 6 4 3 1 定理5-7 设L；≤是格，则对任意