离散数学第十五章格与布尔代数简课件

第十五章格与布尔代数15.1格15.2布尔代数在介绍格之前，对于我们在前面学过的偏序，我们要补充两个内容：1.哈斯图2.最小上界与最大下界1.哈斯图为了更清楚地描述偏序集合中元素间的层次关系,也为了更快、更有效地画出偏序关系的简化图,下面介绍“盖住”的概念。定义在偏序集<A,≤>中,对x,yA,x≤y且xy,且A中无任何其它元素z,满足x≤z且z≤y,称y盖住x,或称x是y的直接前趋,y是x的直接后继。盖住关系记作cov(A)={(x,y)|x,yA且y盖住x}。例A={1,2,3,4,5,6,8,10,12,16,24},偏序关系是A上的整除关系“≤”,画出偏序集<A,≤>的哈斯图。我们先画出关系图。注意图中，并没有画出所有关系，否则画面更显凌乱。按照哈斯图的画法，去掉一部分，结果如左图。例以下是偏序集<P(X)，>的哈斯图。利用哈斯图，可以很方便的解决我们在学习偏序集中的一些问题：例偏序集<S,≤>，其中S={2,4,5,10,12,20,25}，≤是整除关系，求此偏序集的极大元和极小元。解：作出哈斯图，从图中看出，12,20和25是极大元，2和5是极小元。2.最小上界与最大下界定义设集合X上有一个偏序关系“≤”且设Y是X的一个子集。（1）如果存在一个元素x∈X，对每个y'∈Y都有y'≤x，则称x是Y的上界(upperbound)；如果均有x≤y'，则称x是Y的下界(lowerbound)。（2）如果x∈X是Y的上界且对每一个Y的上界x'均有x≤x'，则称x是Y的最小上界（或上确界LUB，leastupperbound）；如果x∈X是Y的下界且对每一个Y的下界x'均有x'≤x，则称x是Y的最大下界（或下确界GLB，greatestlowerbound）例：找出下图所示哈斯图的偏序集的子集{a,b,c},{j,h}和{a,c,df}的下界和上界。解：{a,b,c}的上界是e,f,j,h，它唯一的下界是a。{j,h}没有上界，它的下界是a,b,c,d,e,f。{a,c,df}的上界是f,h,j，它的下界是a。例在上图所示偏序集中，如果{b,d,g}的最大下界和最小上界存在，求出这个最大下界和最小上界。解：{b,d,g}的上界是g,h，故它的最小上界是g。{b,d,g}的下界是a,b，故它的最大下界是b。显然，对于ab，有：①ab≤a和ab≤b，则表明ab是a和b的下界。②若c≤a和c≤b，则c≤ab，这表明ab是a和b的最大下界。对于ab，有：①a≤ab和b≤ab，则表明ab是a和b的上界。②若a≤c，且b≤c，则ab≤c，这表明ab是a和b的最小上界。例

设n为正整数，Sn为n的正因子的集合，≤为整除关系，则<Sn，≤>构成格。因为x，y∈Sn，xy就是x，y的最小公倍数，xy是x，y的最大公约数。例

幂集P(A)上的包含关系定义了一个偏序关系，P(A)中任意两个元素x，y，有xy=x∪yxy=x∩y因此，<P(A),>是一个格。例确定下图中每个哈斯图表示的偏序集是不是格。解：在a)和c)中的哈斯图表示的偏序集是格。因为每个偏序集中每对元素都有最小上界和最大下界。b)所示的哈斯图的偏序集不是格，例如元素b和c没有最小上界。只要注意到d,e,f中每一个都是上界，但这3个元素的任何一个关于这个偏序集中的序都不小于其它两个。格的对偶性原理是成立的：令<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,≥>中的交运算。因此，给出关于格一般性质的任何有效命题，把关系≤换成≥（或者≥换成≤），交换成并，并换成交，可得到另一个有效命题，这就是关于格的对偶性原理。定理15.1.2设<L,≤>是格，对任意a,bL，有①aa=a,bb=b （等幂律）②ab=ba,ab=ba （交换律）③a(bc)=(ab)c, a(bc)=(ab)c（结合律）④a(ab)=a, a(ab)=a （吸收律）定理15.1.3设<L,≤>是格，对任意a,b,cL，有①若a≤b和c≤d，则ac≤bd，ac≤bd。②若a≤b，则ac≤bc，ac≤bc。③c≤a和c≤bc≤ab④a≤c和b≤cab≤c定理15.1.4设<L,≤>是格，对任意的a,b,cL，有a(bc)≤(ab)(ac)(ab)(ac)≤a(bc)通常称上二式为格中分配不等式。定理15.1.5设<L,≤>是有限格，其中L={a1,a2,···,an}，则<L,≤>是有界格。定义15.1.3设<L,≤>是格，对任意的a,b,cL，有①a(bc)=(ab)(ac)②a(bc)=(ab)(ac)则称<L,≤>为分配格，称①和②为格中分配律。定义15.1.5设<L,≤>是格，若L中每个元素至少有一补元，则称<L,≤>为有补格。由于补元的定义是在有界格中给出的，可知，有补格一定是有界格。定义15.1.6若一格既是有补又是分配的，则称该格为有补分配格，或布尔格，或布尔代数。定理15.1.7设<L,≤>是有补分配格，若任意元素aL，则a的补元a'是唯一的。该定理15.1.6的直接推论，因为有补分配格当然是有界分配格。由于有补分配格中，每个元素a都有唯一的补元a'，因此可在L上定义一个一元运算—补运算“'”。这样，有补分配格可看作具有两个二元运算和一个一元运算的代数结构，习惯上称它为布尔代数，记为<B,,,',0,1>，其中B=L。定理15.1.8设<L,≤>是有补分配格，对任意a,bL，则①(a')'=a②(ab)'=a'b'③(ab)'=a'b'后两式称为格中德·摩根律。定理15.1.9设<L,≤>是有补分配格，对任意a,bL，有 a≤bab'=0 a'b=1格同态，格直积等概念可以接下来定义和研究，但这里不打算这样做，因为如此进行会相对较繁，而是将格作为一个代数结构而引入它们。4．格是代数结构前面我们已知，有补分配格是一个代数结构，叫做布尔代数；反之，由代数结构也可以导出格。定义15.1.7设<L,,>是一代数结构，其中和是L上满足交换律、结合律和吸收律的二元运算，且对任意a,bL，定义偏序关系≤如下：a≤bab=a则<L,≤>是格，称<L,≤>为代数结构<L,,>所诱导的偏序集确立的格。15.2布尔代数前已指出，布尔代数是有补分配格，常记为<B,,,',0,1>。对任意a,b,cB，有①<B,,>是格，且≤为B上由或所定义的偏序关系，满足(L-1)ab=LUB{a,b}，ab=GLB{a,b}(L-2)a≤bab=bab=a(L-3)aa=a，aa=a（等幂律）(L-4)ab=ba，ab=ba（交换律）(L-5)(ab)c=a(bc)，(ab)c=a(bc)（结合律）(L-6)a(ab)=a，a(ab)=a（吸收律）②<B,,>是分配格，满足(D-1)a(bc)=(ab)(ac)，a(bc)=(ab)(ac)（分配律）(D-2)(ab=ac)∧(ab=ac)b=c(可约律)(D-3)(ab)(bc)(ca)=(ab)(bc)(ca)③<B,,,',0,1>是有界格，满足(B-1)0≤a≤1(B-2)a0=a，aa=a（幺律）(B-3)a1=1，a0=0（零律）④<B,,,',0,1>是有补格，满足(C-1)aa'=1，aa'=0（互补律）(C-2)1'=0，0'=1⑤<B,,,',0,1>是有补分配格，满足(CD-1)(ab)'=a'a'，(ab)'=a'b'（德·摩根律）(CD-2)a≤ba'b=1ab'=0b'≤a'注意，上述公式并非都是独立的，可从中选出一些公式作为基本公式，用它们推出其余的公式，而且可以用基本公式定义布尔代数。定义15.2.1设<B,,,'>是一代数结构，其中和是B上的二元运算，'是B上的一元运算。0,1B。若对任意a,bB，有①ab=ba，ab=ba（交换律）②a(bc)=(ab)(ac)，a(bc)=(ab)(ac)（分配律）③a0=a，a1=a（幺律）④aa'=1，aa'=0（互补律）则称<B,,,'>是布尔代数，称、和'分别是B上的并、交和补运算，0和1分别称为和的幺元和幺元。常记为<B,,,',0,1>。事实上，可以由其它定律还可以推出结合律：若x，y，z∈S，则(xy)z=x(yz)和(xy)z=x(yz)。布尔代数的性质：1.零元是唯一的2.幺元是唯一的3.若x∈B，则x的补x'是唯一的4.(对合律)若x∈B，则(x')'=x5.零元“0”与幺元“1”是互补的，即0'=1,1'=06.(等幂律)若x∈B，则xx=x且xx=x7.(零律)若x∈B，则x

1

=1且x

0

=08.(吸收律)若x，y∈B，则x(xy)

=x且x

(xy)

=x9.(结合律)若x，y，z∈B，则(xy)z=x(yz)，(xy)z=x(yz)10.(德摩根律)若x，y