第6章-格与布尔代数.ppt

第六章格与布尔代数6.1格的概念及性质(LatticesTheirsProperties)6.2分配格（distributivelattices）6.3有补格(complementedLattices)6.4布尔代数(Booleanalgebra)6.5布尔表达式(Booleanrepresentative)6.1格的概念及性质（Latticestheirsproperties）6.1格的概念及性质(Latticestheirsproperties)

本章将讨论另外两种代数系统——格与布尔代数，它们与群、环、域的基本不同之处是：格与布尔代数的基集都是一个偏序集。这一序关系的建立及其与代数运算之间的关系是介绍的要点。格是具有两个二元运算的代数系统，它是一个特殊的偏序集，而布尔代数则是一个特殊的格。在第三章，对偏序集的任一子集可引入上确界（最小上界）和下确界（最大下界）的概念，但并非每个子集都有上确界或下确界，例如在图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}（Leastupperbound）,a∧b=GLB{a,b}(Greatestlowerbound),∨和∧分别称为并（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∪CB∧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，∨，∧〉。