格和布尔代数.ppt

格和布尔代数
格与子格
本章将讨论另外两种代数系统——格与布尔代数，它们与群、环、域的基本不同之处是：格与布尔代数的基集都是一个有序集。这一序关系的建立及其与代数运算之间的关系是介绍的要点。格是具有两个二元运算的代数系统，它是一个特殊的偏序集，而布尔代数则是一个特殊的格。
图
在第四章，对偏序集的任一子集可引入上确界（最小上界）和下确界（最大下界）的概念，但并非每个子集都有上确界或下确界，，{a，b}没有上确界，{e，f}没有下确界。不过，当某子集的上、下确界存在时，这个上、下确界是唯一确定的。
如果偏序集〈L，〉中的任何两个元素的子集都有上确界和下确界,则称偏序集〈L，〉为格（lattice）。
虽然偏序集合的任何子集的上确界、下确界并不一定都存在，但存在，则必唯一，而格定义保证了上确界、下确界的存在性。因此我们通常用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上的二元运算。由定义知道，并非所有的偏序集都能构成格，我们用Hasse图表示偏序集，？
（a）、（b）、（c）所规定的偏序集是格，图（d）、（e),因为图中{a,b}无上确界。
【】
（1）对任意集合S，偏序集〈P（S），〉为格，其中并、交运算即为集合的并、交运算，即
B∨C＝B∪C B∧C＝B∩C
封闭于P(S),这里B,C∈P(S)。
（2）设L为命题公式集合，逻辑蕴涵关系“”为L上的偏序关系（指定逻辑等价关系“ ”为相等关系），那么，〈L,〉为格，对任何命题公式A，B，A∨B=A∨B，A∧B=A∧B（等式右边的∨，∧为析取与合取逻辑运算符）。
（3）设Z+表示正整数集，|表示Z+上整除关系，那么〈Z+，|〉为格，其中并、交运算即为求两正整数最小公倍数和最大公约数的运算，即
m∨n＝LCM（m,n） m∧n＝gcd（m,n）
另外，若将〈L,〉中的小于等于关系换成大于等于关系，即对于L中任何两个元素a,b定义ab的充分必要条件是ba,则〈L,〉也是偏序集。我们把偏序集〈L,〉和〈L,〉称为是相互对偶的。并且它们所对应的哈斯图是互为颠倒的。关于格我们有同样的性质。
若〈L,〉是一个格，则〈L,〉也是一个格,且它的并、交运算∨r,∧r对任意a,b∈L满足
a∨rb=a∧b a∧rb=a∨b
于是，我们有下列对偶原理。