[高等教育]离散数学 第5章 格和布尔代数st.ppt

Chapter 5 Lattices Boolean algebra(格与布尔代数) 5.1 Lattices(格的概念) 5.2 Distributive lattices （分配格） 5.3 Complemented Lattices(有补格) 5.4 Boolean algebra (布尔代数) 例题选解 习 题 五 5.1 Lattices(格的概念) 5.1 Lattices(格的概念) 本章将讨论另外两种代数系统——格与布尔代数，它们与群基本不同之处是：格与布尔代数的基集都是一个偏序集。这一序关系的建立及其与代数运算之间的关系是介绍的要点。格是具有两个二元运算的代数系统，它是一个特殊的偏序集，而布尔代数则是一个特殊的格。 在第三章，对偏序集的任一子集可引入上确界（最小上界）和下确界（最大下界）的概念，但并非每个子集都有上确界或下确界，例如在图5.1.1中哈斯图所示的偏序集里，{24，36}没有上确界，{2，3}没有下确界。然而有一些偏序集却有这样一个共同特征,即任意两个元素都有上、下确界(不妨把{a，b}的上(下)确界称为元素a，b的上(下)确界)。例如图5.1.2中哈斯图所示的偏序集。 Definition5.1.1 We call a poset 〈L，〉a lattice provided every subset {x, y} of L has both the least upper bound and the greatest lower bound. 【Example5.1.1】 Let n be a positive integer and , then〈Sn, |〉is a lattice. Because for any x,y ∈ Sn, LUB{x,y}=LCM{x,y}=Least common multiple of {x,y}. GLB{x,y}=GCD{x,y}=Greatest common divisor of {x,y}. The Hasse Diagrams for 〈S8, |〉,〈S6, |〉, and 〈S30, |〉are (a),(b),(c) of graph5.1.2. Here S6=｛1,2,3,6｝, S8=｛1,2,4,8｝, S30=｛1,2,3,5,6,10,15,30｝. If〈L, 〉is a lattice, we can introduce two binary operations ∨ and ∧ on L where a∨b=LUB{a,b}（Least upper bound）, a∧b=GLB{a,b}(Greatest lower bound), ∨ and ∧ are called join（并）and meet （交）. ∨,∧are binary operations on L. Definition5.1.2 Let 〈L，〉be a lattice, ∨ and ∧ are binary operations of join and meet on L, then the algebraic system 〈L,∨, ∧〉is called an algebraic system induced by 〈L，〉 (由格〈L，〉 所诱导的代数系统). 【Example5.1.3】 （1）Let S be a nonempty set, then〈 〉is a lattice. Since for any B,C ∈ , LUB{B, C}=B∪C, GLB{B, C}= B∩C. i.e., B∨C＝B∪C B∧C＝B∩C is closed under ∨and ∧, the algebraic system induced by 〈 ，〉is〈 ， ∪ , ∩ 〉. （2）Let L be the set of all propositional formulas. Then “”is a partial order on L，and 〈L,〉is a lattice, for