第十五章 格与布尔代数(简).pptVIP

第十五章 格与布尔代数 15.1 格 15.2 布尔代数 在介绍格之前，对于我们在前面学过的偏序，我们要补充两个内容： 1. 哈斯图 2. 最小上界与最大下界 1.哈斯图 为了更清楚地描述偏序集合中元素间的层次关系, 也为了更快、更有效地画出偏序关系的简化图, 下面介绍“盖住”的概念。 定义 在偏序集A, ≤中, 对x, y?A, x≤y且x ? y, 且 A中无任何其它元素z, 满足x≤z且z≤y, 称y盖住x, 或称x是y的直接前趋, y是x的直接后继。盖住关系记作cov(A) = {(x, y) | x, y?A且y盖住x}。 显然盖住关系是唯一确定的, 盖住关系是“≤”的子集。盖住关系的关系图称哈斯(Hasse)图, 它实际上偏序关系是经过如下简化的关系图: 1. 省略关系图中的每个结点处的自环, 这是因为偏序关系“≤”是自反的。 2. 若xy且y盖住x, 将代表y的结点放在代表x的结点之上, 并在x与y之间连线, 省去有向边的箭头, 使其成为无向边。 若xy 但y不盖住x, 则省去x与y之间的连线。 例 A = {1, 2, 3, 4, 5, 6, 8, 10, 12, 16, 24}, 偏序关系是A上的整除关系“≤”, 画出偏序集A, ≤的哈斯图。 例 以下是偏序集P(X)，? 的哈斯图。 利用哈斯图，可以很方便的解决我们在学习偏序集中的一些问题： 例 确定下图中每个哈斯图表示的偏序集是否有最大元和最小元。 2.最小上界与最大下界 定义 设集合X上有一个偏序关系“≤”且设Y是X的一个子集。 （1）如果存在一个元素x∈X，对每个y∈Y都有y≤x，则称x是Y的上界(upper bound)；如果均有x≤y，则称x是Y的下界(lower bound)。 （2）如果x∈X是Y的上界且对每一个Y的上界x均有x≤x，则称x是Y的最小上界（或上确界LUB，least upper bound）；如果x∈X是Y的下界且对每一个Y的下界x均有x≤x，则称x是Y的最大下界（或下确界GLB，greatest lower bound ） 例：找出下图所示哈斯图的偏序集的子集{a,b,c},{j,h}和{a,c,d f}的下界和上界。 例 在上图所示偏序集中，如果{b,d,g}的最大下界和最小上界存在，求出这个最大下界和最小上界。 15.1 格(lattice) 1．格作为偏序集 定义15.1.1 设L,≤是一个偏序集，若对任意a,b?L，存在 最大下界(GLB)和最小上界(LUB)，则称L,≤为格。 用a?b表示GLB{a,b}，a?b表示LUB{a,b}，并称?和?分别为L上的交（或积）和并（或和）运算。这样我们由偏序关系定义了两种二元运算。 若L是有限集合，称L,≤为有限格。 显然，对于a?b，有： ①a?b≤a和a?b≤b，则表明a?b是a和b的下界。 ②若c≤a和c≤b，则c≤a?b，这表明a?b是a和b的最大下界。 对于a?b，有： ①a≤a?b和b≤a?b，则表明a?b是a和b的上界。 ②若a≤c，且b≤c，则a?b≤c，这表明a?b是a和b的最小上界。 例 确定下图中每个哈斯图表示的偏序集是不是格。 格的对偶性原理是成立的： 令L,≤是偏序集，且L,≥是其对偶的偏序集。若L,≤是格，则L,≥也是格，反之亦然。这是因为，对于L中任意a和b，L,≤中LUB{a,b}等同于L,≥中GLB {a,b}，L,≤中GLB{a,b}等同于L,≥中的LUB{a,b}。若L是有限集，这些性质易从偏序集及其对偶的哈斯图得到验证。 从上讨论中，可知两格互为对偶。互为对偶的两个L,≤和L,≥有着密切关系，即格L,≤中交运算?正是格L,≥中的并运算?，而格L,≤中的并运算?正是格L,≥中的交运算?。因此，给出关于格一般性质的任何有效命题，把关系≤换成≥（或者≥换成≤），交换成并，并换成交，可得到另一个有效命题，这就是关于格的对偶性原理。 2．格的基本性质 定理15.1.1 设L,≤是格，对任意a,b?L，有 ① a?b=b?a≤b ② a?b=a?a≤b ③ a?b=a?a?b=b 亦即 a≤b?a?b=b?a?b=a 定理15.1.2 设L,≤是格，对任意a,b?L，有 ① a?a=a, b?b=b （等幂律） ② a?b=b?a, a?b=b?a （交换律） ③ a?(b?c)=(a?b)?c, a?(b?c)=(a?b)?c （结合律） ④ a?(a?b)=a, a?(a?b)=a （吸收律） 定理15.1.3 设L,≤是格，对任意a,b,c?L，有 ①若a≤b和c≤d，则a?c≤b?d，a?c≤b?d。 ②若a≤b，则a?c≤b?c，