1、 离散数学 教案计算机科学与技术学院课程学时： 64主 讲：宋 成河南理工大学 电子教案第六章：格和布尔代数6.1 格的概念6.2 分配格6.3 有补格6.4* 布尔代数第六章：格和布尔代数教学目的及要求：深刻理解和掌握格与布尔代数的基本概念和基本运算教学类容：格的概念、有补格，分配格、布尔代数和布尔表达式。教学重点：格、布尔代数和布尔表达式。教学难点：布尔代数和布尔表达式。6.1 格的概念【 定义 6.1.1】 设 X,是偏序集，如果 x,yX， 集合 x,y都有最小上界和最大下界，则称 X,是格。【 例 6.1】 设 S12 1,2,3,4,6,12是 12的因子构成的集合。其上的整除关系
2、 R=x,y| xS12 yS12 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，哈斯图如图 6.1所示。从哈斯图中可看出，集合 S12的任意两个元素都有最小上界和最大下界，故偏序集 S12,R是格。 第六章：格和布尔代数第六章：格和布尔代数【 例 6.2】 图 8.2中给出了一些偏序集的哈斯图，判断它们是否构成格。解： 它们都不是格。在 (a)中， 1,2没有下界，因而没有最大下界。在 (b)中
3、， 2,4虽有两个上界，但没有最小上界。在 (c)中， 1,3没有下界，因而没有最大下界。在 (d)中， 2,3虽有三个上界，但没有最小上界。第六章：格和布尔代数设 X,是格， x,yX， 今后用 x y表示集合 x,y的最小上界，二元运算 称为并运算；用 x y表示集合 x,y的最大下界，二元运算 称为交运算。 【 定义 6.1.2】 设 X,是格， 是 X上的并运算， 是 X上的交运算。则称 X, , 是格 X,导出的代数系统。x,yP (A)， x y=x y， x y=xy。 这样，格 P (A),R导出的代数系统 P (A), , 实际就是代数系统 P (A), ,， 所以，二元运算
4、 和 的运算表如表 6.1和表 6.2所示。在例 6.1中，根据图 6.1，集合 4,6的最小上界为 12，即4 6=12=4和 6的最小公倍数；它的最大下界为 2，即 4 6=2=4和 6的最大公约数。同样，这个结果也可以推广到一般情况。即在格 S12,R导出的代数系统 S12, , 中，二元运算 是求最小公倍数；二元运算 是求最大公约数。 第六章：格和布尔代数表 6. 1表 6. 2 a abba,ba a a a,ba,ba,bb b a,b a,ba,b a,b a,bba,b a,b a b a,b a a ab b ba,b a b a,b第六章：格和布尔代数定义 6.1.3 设
5、f是含有格中元素以及符号 =, 和 的命题。将 f中的 替换成 ， 替换成 ， 替换成 ， 替换成 ，得到一个新命题，所得的命题叫做 f的对偶命题，记为 f *。 例如，在格中， f为 a (b c)a，则 f的对偶命题 f *为a (b c)a命题 f和它的对偶命题 f *遵循下列的规则，这规则叫做格的对偶原理。设 f是含有格中元素以及符号 =, 和 的命题。 若 f对一切格为真，则 f的对偶命题 f *也对一切格为真。格的许多性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，只需证明其中的一个就可以了。 第六章：格和布尔代数【 定理 6.1.1】 设 X,是格， X, , 是格 X,导出的代数系统。则 a,b,cX有 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,bX， a,b=b,a， 所以它们的最小上界相等。即 a b=b a， 同理可证 a b=b a a和 b的最大下界一定是 a、 b的下界，即 a ba， 同理， (a b) ca b， 所以， (a b) ca ba同理有 (a b) ca bb 和 (a b) cc第六章：格和布尔代数
