电子工业出版社：计算机类本科规划教材《离散数学》课程教学资源（PPT课件讲稿）第8章 格与布尔代数

第障格与布尔代数 第8章格与布尔代数 8.,1格 8,2布尔代数 返回总目录

第8章 格与布尔代数 第8章 格与布尔代数 8.1 格 8.2 布尔代数 返回总目录

第障格与布尔代数 第8章格与布尔代数 8.1格 8.1.1格的概念和性质 定义81.1设<>是偏序集,如果∨xy∈Y,集合1xy 都有最小上界和最大下界,则称是格。 【例81】设S12=1,2,346,12}是12的因子构成的集合 其上的整除关系R=1,, }, 哈斯图如图8.1所示。从哈斯图中可看出,集合S12的任意两 个元素都有最小上界和最大下界,故偏序集是格

第8章 格与布尔代数 第8章 格与布尔代数 8.1格 8.1.1格的概念和性质 定义8.1.1 设X,≼是偏序集，如果x,yX，集合x,y 都有最小上界和最大下界，则称X,≼是格。 【例8.1】设S12 ＝1,2,3,4,6,12是12的因子构成的集合。 其上的整除关系R=x,y| xS12∧yS12∧x整除y，R是S12 上的偏序关系，S12,R是偏序集。写出S12上的盖住关系 COV S12，画出哈斯图，验证偏序集S12,R是格。 解：S12上的盖住关系 COV S12 ＝1,2,1,3,2,4,2,6,3,6, 4,12,6,12， 哈斯图如图8.1所示。从哈斯图中可看出，集合S12的任意两 个元素都有最小上界和最大下界，故偏序集S12,R是格

第障格与布尔代数 图8.1

第8章 格与布尔代数

第降格与布尔代数 【例82】图82中给出了一些偏序集的哈斯图,判断它 们是否构成格。 解:它们都不是格。在(a)中,1,2}没有下界,因而没 有最大下界。在(b)中,12,4}虽有两个上界,但没有最小上 界。在(C)中,1,3}没有下界,因而没有最大下界。在(d)中, 12,3}虽有三个上界,但没有最小上界 O 4 64 5 4 32 图8.2

第8章 格与布尔代数 【例8.2】图8.2中给出了一些偏序集的哈斯图，判断它 们是否构成格。 解：它们都不是格。在(a)中，1,2没有下界，因而没 有最大下界。在(b)中，2,4虽有两个上界，但没有最小上 界。在(c)中，1,3没有下界，因而没有最大下界。在(d)中， 2,3虽有三个上界，但没有最小上界

第障格与布尔代数 设是格,xy∈X,今后用x∨y表示集合xy的最 小上界,二元运算∨称为并运算;用xy表示集合xy}的最 大下界,二元运算∧称为交运算。 定义8.1.2设是格,∨是Ⅺ上的并运算,∧是X上 的交运算。则称是格导出的代数系统 在例428中,根据图414,集合a},b}的最小上界为 1ab},即a∨bab}=a%Ub};它的最大下界为E, 即{a}∧b}=E=a}∩b}。这个结果可以推广到一般情况 xy∈P(4),xy=xUy,x^=xny。这样,格导 出的代数系统实际就是代数系统 所以,二元运算∨和∧的运算表如表81和表82所示 在例81中,根据图81,集合{46}的最小上界为12,即 4∨6=12=4和6的最小公倍数;它的最大下界为2,即 4∧6=2=4和6的最大公约数。同样,这个结果也可以推广到 般情况。即在格中,二 元运算∨是求最小公倍数;二元运算∧是求最大公约数

第8章 格与布尔代数 设X,≼是格，x,yX，今后用x∨y表示集合x,y的最 小上界，二元运算∨称为并运算；用x∧y表示集合x,y的最 大下界，二元运算∧称为交运算。 定义8.1.2 设X,≼是格，∨是X上的并运算，∧是X上 的交运算。则称X,∨,∧是格X,≼导出的代数系统。 在例4.28中，根据图4.14，集合a,b的最小上界为 a,b，即a∨b=a,b=a∪b；它的最大下界为Æ， 即a∧b=Æ=a∩b。这个结果可以推广到一般情况。 x,yP (A)，x∨y=x∪y，x∧y=x∩y。这样，格P (A),R 导 出的代数系统P (A),∨,∧实际就是代数系统P (A),∪,∩， 所以，二元运算∨和∧的运算表如表8.1和表8.2所示。 在例8.1中，根据图8.1，集合4,6的最小上界为12，即 4∨6=12=4 和 6 的最小公倍数；它的最大下界为 2 ， 即 4∧6=2=4和6的最大公约数。同样，这个结果也可以推广到 一般情况。即在格S12,R导出的代数系统S12,∨,∧中，二 元运算∨是求最小公倍数；二元运算∧是求最大公约数

第障格与布尔代数 表 8aaa l( b C 369 3a.bl 3a.b5 3a.bs 1b} 36 Ba.bs b abl Ra,brfabrabia,bi ia,b7 表8.2 ∧ 365 3a.bl Oa a ba 69 b b bsa, bt

第 8 章 格与布尔代数 表8. 1 表8. 2 ∨   a     a   b   b   a , b   a   a   a   a , b   a , b   a , b   b   b   a , b   a , b   a , b   a , b   a , b   b   a , b   a , b  ∧   a   b   a , b        a    a    a   b     b   b   a , b    a   b   a , b 

第障格与布尔代数 下面介绍格的对偶原理 设是偏序集,在X上定义二元关系 ≥=1kba>∈≤ 可以证明也是偏序集 定义81.3设/是含有格中元素以及符号=≤>,V和∧的 命题。将户的≤替换成≥,≥替换成≤,∨替换成∧,∧替 换成∨,得到一个新命题,所得的命题叫做的对偶命题 记为厂* 例如,在格中,/为a∧(b∨c)≤a,则的对偶命题/*为 aV(b∧c)≥a 命题缃和它的对偶命题*遵循下列的规则,这规则叫做 格的对偶原理。 设是含有格中元素以及符号=,《,≥,∨和∧的命题 若/对一切格为真,则f的对偶命题f*也对一切格为真 格的许多性质都是互为对偶命题的。有了格的对偶原 理,在证明格的性质时,只需证明其中的一个就可以了

第8章 格与布尔代数 下面介绍格的对偶原理。 设X,≼是偏序集，在X上定义二元关系 ≽=a,b|b,a≼ 可以证明X,≽也是偏序集。 定义8.1.3 设f是含有格中元素以及符号=,≼,≽,∨和∧的 命题。将f中的≼替换成≽，≽替换成≼，∨替换成∧，∧替 换成∨，得到一个新命题，所得的命题叫做f的对偶命题， 记为f * 。 例如，在格中，f为a∧(b∨c)≼a，则f的对偶命题f *为 a∨(b∧c)≽a 命题f和它的对偶命题f *遵循下列的规则，这规则叫做 格的对偶原理。 设f是含有格中元素以及符号=,≼,≽,∨和∧的命题。 若f对一切格为真，则f的对偶命题f *也对一切格为真。 格的许多性质都是互为对偶命题的。有了格的对偶原 理，在证明格的性质时，只需证明其中的一个就可以了

第障格与布尔代数 定理81.1设是格,是格导出的 代数系统。则a,b,C∈X有 (1)a∨b=b∨a,a∧b=b∧a(交换律) (2)(a∨b)∨c=a∨(bc) (a∧b)∧c=a∧(b∧c) (结合律) (ava=a a/a= a (幂等律) (4)aV(a∧b)=a a∧(aVb)=a (吸收律) 证明:()ab∈X,{ab}=ba},所以它们的最小上界 相等。即a∨b=bVa,同理可证a∧b=b∧a (2)a和b的最大下界一定是a、b的下界,即a∧b≤a, 同理,(a∧b)∧c≤a∧b,所以,(a∧b)∧c≤a∧b≤a 同理有(a∧b)∧c≤a∧b≤b和(a∧b)∧c≤c

第8章 格与布尔代数 定理8.1.1 设X,≼是格，X,∨,∧是格X,≼导出的 代数系统。则a,b,cX有 ⑴ a∨b=b∨a， a∧b=b∧a (交换律) ⑵ (a∨b)∨c=a∨(b∨c) (a∧b)∧c=a∧(b∧c) (结合律) ⑶ a∨a= a， a∧a= a (幂等律) ⑷ a∨(a∧b)=a a∧(a∨b)=a (吸收律) 证明：⑴a,bX，a,b=b,a，所以它们的最小上界 相等。即a∨b=b∨a，同理可证a∧b=b∧a ⑵ a和b的最大下界一定是a、b的下界，即a∧b≼a， 同理，(a∧b)∧c≼a∧b，所以，(a∧b)∧c≼a∧b≼a 同理有 (a∧b)∧c≼a∧b≼b 和 (a∧b)∧c≼c

第障格与布尔代数 由以上3式得(a∧b)∧c≤b∧c和(a∧b)∧c≤aA(b∧c) 类似地可证a∧(b∧c)≤(a∧b)∧c 根据偏序关系的反对称性有(a∧b)∧c=a∧(b∧c) 由对偶原理得(aVb)∨ca∨(b∨c) (3)显然a≤a∨a,又由≤的自反性得a≤a,从而推出 a∨a≤a,根据偏序关系的反对称性有a√a=a 由对偶原理得a∧a=a (4)显然a≤a∨(a∧b), 又由a≤a,a∧b≤得a∨(a∧b)≤a,从而得 aV(a∧b)=a 由对偶原理得a∧(a∨b)=a

第8章 格与布尔代数 由以上3式得 (a∧b)∧c≼b∧c和(a∧b)∧c≼a∧(b∧c) 类似地可证 a∧(b∧c)≼(a∧b)∧c 根据偏序关系的反对称性有(a∧b)∧c= a∧(b∧c) 由对偶原理得 (a∨b)∨c= a∨(b∨c) ⑶ 显然a≼a∨a，又由≼的自反性得a≼a，从而推出 a∨a≼a，根据偏序关系的反对称性有a∨a=a 由对偶原理得a∧a=a ⑷显然 a≼a∨(a∧b)， 又由a≼a，a∧b≼a得a∨(a∧b)≼a，从而得 a∨(a∧b)=a。 由对偶原理得a∧(a∨b)=a

第障格与布尔代数 定理812设是代数系统,其中∨,∧都是二元 运算。如果∨和∧满足吸收律,则∨和∧满足幂等律。 证明:aVa=av(a∧(aVb)=a,同理可证a∧a=a 定理813设是代数系统,其中∨,∧都是二元 运算,满足交换律、结合律和吸收律,则可适当定义X的偏 序关系≤,使构成一个格。 证明:定义X上的 元关系 ≤a,b∈X且a∧b=a (1)证明≤是X上的偏序关系。 由定理81.2知∧满足幂等律,即a∧a=a,所以a≤a。故 ≤是自反的 设a≤b且b≤a,则a∧b=a且b∧a=b,于是a=a∧b=b∧a b。所以≤是反对称的 设a≤b且b≤c,则a∧b=a且b∧c=b,于是a∧c=(a∧b)∧c a(b∧c)=a∧b=a,即a≤c,故≤是传递的 这就证明了≤是X上的偏序关系

第8章 格与布尔代数 定理8.1.2 设X,∨,∧是代数系统，其中∨,∧都是二元 运算。如果∨和∧满足吸收律，则∨和∧满足幂等律。 证明：a∨a=a∨(a∧(a∨b))=a，同理可证a∧a=a 定理8.1.3 设X,∨,∧是代数系统，其中∨,∧都是二元 运算，满足交换律、结合律和吸收律，则可适当定义X的偏 序关系≼，使X,≼构成一个格。 证明：定义X上的一个二元关系 ≼=a,b|a,bX且a∧b=a ⑴ 证明≼是X上的偏序关系。 由定理8.1.2知∧满足幂等律，即a∧a=a，所以a≼a。故 ≼是自反的。 设a≼b且b≼a，则a∧b=a且b∧a=b，于是a=a∧b=b∧a =b。所以≼是反对称的。 设a≼b且b≼c，则a∧b=a且b∧c=b，于是a∧c=(a∧b)∧c =a∧(b∧c)=a∧b=a，即a≼c，故≼是传递的。 这就证明了≼是X上的偏序关系