西安电子科技大学出版社：面向21世纪高等学校计算机类专业系列教材《离散数学》课程教学资源（PPT课件讲稿）第7章 格和布尔代数

第7章格和布尔代数 第7章格和布尔代数 7,1格与子格 7,2特殊格 73布尔代数 74例题选解 习题七 dBac

第7章 格和布尔代数 第7章 格和布尔代数 7.1 格与子格 7.2 特殊格 7.3 布尔代数 7.4 例题选解 习 题 七

第7章格和布尔代数 71格与子格 本章将讨论另外两种代数系统—一格与布尔代数, 它们与群、环、域的基本不同之处是:格与布尔代数 的基集都是一个有序集。这一序关系的建立及其与代 数运算之间的关系是介绍的要点。格是具有两个二元 运算的代数系统,它是一个特殊的偏序集,而布尔代 数则是一个特殊的格

第7章 格和布尔代数 7.1 格与子格 本章将讨论另外两种代数系统——格与布尔代数， 它们与群、环、域的基本不同之处是：格与布尔代数 的基集都是一个有序集。这一序关系的建立及其与代 数运算之间的关系是介绍的要点。格是具有两个二元 运算的代数系统，它是一个特殊的偏序集，而布尔代 数则是一个特殊的格

第7章格和布尔代数 b of 图7.11

第7章 格和布尔代数 图 7.1.1 a b c d e f

第7章格和布尔代数 在第四章,对偏序集的仼一子集可引入上确界(最 小上界)和下确界(最大下界)的概念,但并非每个 子集都有上确界或下确界,例如在图7.1.1中哈斯图所 示的有序集里,{a,b}没有上确界,{e,∫没有下确界 不过,当某子集的上、下确界存在时,这个上、下确 界是唯一确定的

第7章 格和布尔代数 在第四章，对偏序集的任一子集可引入上确界（最 小上界）和下确界（最大下界）的概念，但并非每个 子集都有上确界或下确界，例如在图7.1.1中哈斯图所 示的有序集里，{a，b}没有上确界，{e，f}没有下确界。 不过，当某子集的上、下确界存在时，这个上、下确 界是唯一确定的

第7章格和布尔代数 定义71.1如果偏序集(,≤〉中的任何两个元素 的子集都有上确界和下确界,则称偏序集〈L,≤〉为 格( lattice)。 虽然偏序集合的任何子集的上确界、下确界并不 定都存在,但存在,则必唯一,而格定义保证了上 确界、下确界的存在性。因此我们通常用a∨b表示{a, b}的上确界,用a∧b表示{a,b}的下确界

第7章 格和布尔代数 定义7.1.1 如果偏序集〈L 〉中的任何两个元素 的子集都有上确界和下确界,则称偏序集〈L 〉为 格（lattice）。 虽然偏序集合的任何子集的上确界、下确界并不 一定都存在，但存在，则必唯一，而格定义保证了上 确界、下确界的存在性。因此我们通常用a∨b表示{a， b}的上确界，用a∧b表示{a，b}的下确界

第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 于是，我们有下列对偶原理