第7章格和布尔代数 b (d 图7.12
第7章 格和布尔代数 图 7.1.2 b a a b (a) (b) (c) (d) (e)
第7章格和布尔代数 并记作aVb=LUB{a,b} (Leastupperbound), a b=GLBa, b(Greatestlowerbou nd),∨和∧分别称为并(join)和交(met)运算。由 于对任何a,b,a∨b及a∧b都是L中确定的成员,因此 V,∧均为L上的二元运算。由定义知道,并非所有的 偏序集都能构成格,我们用Hasε图表示偏序集,图 7.1.2中哪个能构成格? 图712中哈斯图(a)、(b)、(c)所规定的偏 序集是格,图(d)、(e)及图71.1所规定的偏序集不 是格,因为图中{a,b}无上确界
第7章 格和布尔代数 并记作a∨b=LUB{a,b} （Leastupperbound）,a∧b=GLB{a,b}(Greatestlowerbou nd),∨和∧分别称为并（join）和交（meet）运算。由 于对任何a，b，a∨b及a∧b都是L中确定的成员，因此 ∨,∧均为L上的二元运算。由定义知道，并非所有的 偏序集都能构成格，我们用Hasse图表示偏序集，图 7.1.2中哪个能构成格？ 图7.1.2中哈斯图（a）、（b）、（c）所规定的偏 序集是格，图（d）、（e)及图7.1.1所规定的偏序集不 是格,因为图中{a,b}无上确界
第7章格和布尔代数 【例71.1】 (1)对任意集合S,偏序集〈P(S),≤〉为格, 其中并、交运算即为集合的并、交运算,即 BVC=B∪CB∧C=B∩C 封闭于P(S)这里BC∈P(S)。 (2)设L为命题公式集合,逻辑蕴涵关系“→”为 L上的偏序关系(指定逻辑等价关系“令”为相等关 系),那么,《L,→〉为格,对任何命题公式A,B, A∨B=A∨B,A∧B=A∧B(等式右边的√,∧为析取 与合取逻辑运算符)
第7章 格和布尔代数 【例7.1.1】 （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（等式右边的∨，∧为析取 与合取逻辑运算符）。
第7章格和布尔代数 (3)设z表示正整数集,表示Z上整除关系,那 么〈Z,〉为格,其中并、交运算即为求两正整数最 小公倍数和最大公约数的运算,即 m∨n=LCM(m,n)m∧n=gcd(m,n) 另外,若将〈L,≤〉中的小于等于关系换成大于等 于关系,即对于L中任何两个元素ab定义a≥=b的充 分必要条件是ba则〈L,≥〉也是偏序集。我们把偏 序集(L≤〉和〈L,≥〉称为是相互对偶的。并且它们 所对应的哈斯图是互为颠倒的。关于格我们有同样的 性质
第7章 格和布尔代数 （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, 〉称为是相互对偶的。并且它们 所对应的哈斯图是互为颠倒的。关于格我们有同样的 性质
第7章格和布尔代数 定理71.1若〈L,≤)是一个格,则《L,≥=〉也是 个格,且它的并、交运算∨r,∧r对任意ab∈L满足 aV1b=a∧ba∧b=aVb 于是,我们有下列对偶原理
第7章 格和布尔代数 定理7.1.1 若〈L, 〉是一个格，则〈L, 〉也是一 个格,且它的并、交运算∨r,∧r对任意a,b∈L满足 a∨rb=a∧b a∧rb=a∨b 于是，我们有下列对偶原理