离散数学左孝凌6.ppt

第六章 格与布尔代数 6-1 格的概念 (Lattices) 6-2 分配格（distributive lattices） 6-3 有补格(complemented Lattices) 6-4 布尔代数(Boolean algebra ) 6-5 布尔表达式(Boolean representative ) 6-1 格的概念（Lattices ） 6-1 格的概念 本章将讨论另外两种代数系统——格与布尔代数，它们与群、环、域的基本不同之处是：格与布尔代数的基集都是一个偏序集。这一序关系的建立及其与代数运算之间的关系是介绍的要点。格是具有两个二元运算的代数系统，它是一个特殊的偏序集，而布尔代数则是一个特殊的格。 在第三章，对偏序集的任一子集可引入上确界（最小上界）和下确界（最大下界）的概念，但并非每个子集都有上确界或下确界，例如在图6.1.1中哈斯图所示的偏序集里，{24，36}没有上确界，{2，3}没有下确界。然而有一些偏序集却有这样一个共同特征,即任意两个元素都有上、下确界(不妨把{a，b}的上(下)确界称为元素a，b的上(下)确界)。例如图6-1.2中哈斯图所示的偏序集。 定义6-1.1 如果偏序集〈L，≤〉中的任何两个元素都 有上确界和下确界,则称偏序集〈 L，≤〉为格（lattice）。 【例6-1.1】设n是一正整数,Sn是n的所有正因子的集合。例 如S6=｛1,2,3,6｝,S8=｛1,2,4,8｝, “|”是整除关系,则〈Sn, |〉是 格,因为 x,y∈ Sn, LUB{x,y}= x与y的最小公倍数=LCM{x,y}, GLB{x,y}= x与y的最大公约数=GCD{x,y}。 例如〈S8, |〉,〈S6, |〉,〈S30, |〉的哈斯图如图6.1.2(a),(b),(c)所 示。 虽然偏序集合的任何子集的上确界、下确界并不一定都存在，但存在，则必唯一，而格的定义保证了任意两个元素的上确界、下确界的存在性。因此我们通常用a∨b表示{a，b}的上确界，用a∧b表示{a，b}的下确界，即 a∨b=LUB{a,b}（Least upper bound）, a∧b=GLB{a,b}(Greatest lower bound), ∨和∧分别称为并（join）和交（meet）运算。 由于对任何a，b，a∨b及a∧b都是L中确定的成员，因此∨,∧均为L上的二元运算。这样我们便有如下定义: 定义6-1.2 设〈L，≤〉是一个格, ∨和∧分别为L上的并和交运算,则称代数系统〈L,∨, ∧〉为由格〈L，≤〉 所诱导的代数系统。 【例6-1.3】 （1）对任意集合S，偏序集〈 ，〉为格， 其中并、交运算即为集合的并、交运算，即 B∨C＝B∪C B∧C＝B∩C ∨和∧在 上封闭,这里B,C∈ , 〈 ，〉所诱导的代数系统为〈 ， ∪ , ∩ 〉 。 【例6-1.3】 （2）设L为命题公式集合，逻辑蕴涵关系“”为L上的偏序关系（指定逻辑等价关系“ ”为相等关系），那么，〈L,〉为格，对任何命题公式A，B，A∨B=A∨B，A∧B=A∧B（等式右边的∨，∧为析取与合取逻辑运算符）,因此由 〈L,〉所诱导的代数系统为〈 L ， ∨，∧ 〉 。 （3）设Z+表示正整数集，“|”表示Z+上整除关系，那么〈 Z+ ，|〉为格，其中并、交运算即为求两正整数最小公倍数和最大公约数的运算，即 m∨n＝LCM（m,n） m∧n＝GCD(m,n）, 由〈 Z+ ，|〉所诱导的代数系统为〈 Z+ ， ∨，∧ 〉。 （4）任一全序集〈A， 〉是一个格。因为 a,b ∈A， 由〈A,〉所诱导的代数系统为〈 A ，∨，∧ 〉。 2.子格 若偏序集〈L，≤〉是格,非空集合B L,显然〈B, ≤〉也是一个偏序集,我们自然会问, 〈B, ≤〉是否是格