1、1离散数学（二）格和布尔代数格与布尔代数 ：它们都是具有两个二元运算的代数系统，这两个代数系统与前面讨论的代数系统之间存在着一个重要区别： 在格与布尔代数中， 偏序关系 具有重要意义 。为了强调偏序关系的作用，我们将分别从 偏序集 和 代数系统 两个方面引入格的概念，给格附加一定的限制之后，格就转化为布尔代数，即 布尔代数是特殊的格 。格和布尔代数起源与发展 :布尔代数最初是作为对逻辑思维法则的研究出现的。 英国哲学家布尔 (George Boole)于 1847年利用数学方法研究了类与类 (集合与集合 )之间的关系法则 。他的研究后来发展成为一个数学分支 布尔代数 。自布尔之后，许多数学家对
2、布尔代数一般化作了努力。在奠基工作方面， 丰廷顿 (E. V. Huntington)、雪弗尔 (H. M. Sheffer)和斯通 (M. H. Stone)都作出了贡献。 毕克霍夫(Garrett Birkhoff)和 麦克朗 (Saunders Maclane)的研究进一步使布尔代数得到严谨的处理。格和布尔代数格是一种兼 有序 和 代数 的重要结构，它和模糊数学等现代数学有十分紧密的联系；格与布尔代数具体应用：格与布尔代数在计算机科学中具有非常重要的应用。如在 保密学 、 计算机语义学 、 开关理论 、 计算机理论 和逻辑设计 以及其他一些科学和工程领域中都直接应用了格与布尔代数。格和布
3、尔代数格 (lattice)在 闪 存 (flash memory)编码 中的 应 用:格的定义与基本性质格的两种定义11子格和格同态2主要内容 :格的定义和性质重点 : 重点和难点:格的两种定义难点 : 一、格的两种定义预备知识：1. 若集合 A上的二元关系 R是自反的、反对称的、传递的，则称 R为 A上的 偏序 ，记为 。2 设 是一偏序集合 ,B A(i) 若 a A，对于每一 x B, 均有 xa, 称 a A为 B的上界；(ii) 若 b A，对于每一 x B, 均有 bx, 称 b A为 B的下界；(iii) c为 B的上界 , 若对 B的任一上界 c, 均有 c c, 称 c为
4、B的 上确界 (最小上界 )；(iv) d为 B的下界，若对 B的任一下界 d, 均有 d d,称 d为B的下确界 (最大下界 )。一、格的两种定义偏序格的定义：设 是一偏序集合 ,若对于任意 a,b L, a,b均有上确界(最小上界 )和下确界 (最大下界 ),则称此 偏序集合 为格。一、格的两种定义代数格的引入：设 是一偏序集合，在 L上定义两运算 *与 如下 , 即对任意 a,b L：a * b=a,b 的下确界 =glba,b 保交ab=a,b 的上确界 =luba,b 保联 那么 是代数吗？例 1： 对任意 a,b I+,有a*b=a,b的下确界 =GCDa,b (a,b的最大公约数
5、 ) ab=a,b的上确界 =LCMa,b (a,b的最小公倍数 )一、格的两种定义代数格的定义：设 是代数系统 ,*和 是载体 L上的二元运算 ,若满足(1)交换律 a * b=b * a ab=ba(2)结合律 a *(b * c)=(a * b) * c a(bc)=(ab)c(3)吸收律 a(a * b)=a a * (ab)=a则称 是代数格 。事实上代数格也满足 等幂律 ， aa=a, a*a=a, 由吸收律可推出 等幂律 , 因为 a*a=a*(a(a*a)=a。类似地可证 aa=a。例 3 (1) S=a,b,c, 为代数格；(2) 定义 X:由命题变元 p1,p2, pn, , , , , 构成的合式公式集。则 为代数格。
