第8章格与布尔代数 第8章格与布尔代数 8.1格 8.2布尔代数 返回总目录
第8章 格与布尔代数 第8章 格与布尔代数 8.1 格 8.2 布尔代数 返回总目录
第章格与布尔代数 第8章格与布尔代数 8.1格 8.1.1格的概念和性质 定义8.1.1设<X,≤>是偏序集，如果x,yeX,集合x,y 都有最小上界和最大下界，则称<X,≤>是格 【例8.1】设S12=1,2,3,4,6,12是12的因子构成的集合。 其上的整除关系R<x>lx∈S12∧yeS12∧x整除y,R是S2 上的偏序关系，<S12,R心是偏序集。写出S12上的盖住关系 COVS12,画出哈斯图，验证偏序集<S12,R心是格 解：S12上的盖住关系 C0VS12=<1,2>,<1,3>,<2,4>,<2,6>,<3,6> <4,12>,<6,12>7, 哈斯图如图8.1所示。从哈斯图中可看出，集合S12的任意两 个元素都有最小上界和最大下界，故偏序集<S12,R>是格
第8章 格与布尔代数 第8章 格与布尔代数 8.1格 8.1.1格的概念和性质 定义8.1.1 设X,≼是偏序集，如果x,yX，集合x,y 都有最小上界和最大下界，则称X,≼是格。 【例8.1】设S12 ＝1,2,3,4,6,12是12的因子构成的集合。 其上的整除关系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， 哈斯图如图8.1所示。从哈斯图中可看出，集合S12的任意两 个元素都有最小上界和最大下界，故偏序集S12,R是格
第章格与布尔代数 12 4 6 2 3 1 图8.1
第8章 格与布尔代数
第8章 格与布尔代数 【例8.2】图8.2中给出了一些偏序集的哈斯图，判断它 们是否构成格。 解：它们都不是格。在(a)中，子1,2没有下界，因而没 有最大下界。在(b)中，了2,4虽有两个上界，但没有最小上 界。在(c)中，了1,3没有下界，因而没有最大下界。在(d)中， 2,3}虽有三个上界，但没有最小上界。 (a) (b) (c) (d) 图8.2
第8章 格与布尔代数 【例8.2】图8.2中给出了一些偏序集的哈斯图，判断它 们是否构成格。 解：它们都不是格。在(a)中，1,2没有下界，因而没 有最大下界。在(b)中，2,4虽有两个上界，但没有最小上 界。在(c)中，1,3没有下界，因而没有最大下界。在(d)中， 2,3虽有三个上界，但没有最小上界
第8章 格与布尔代数 设<X,>是格，x,yEX,今后用xVy表示集合x,y的最 小上界，二元运算V称为并运算；用x个y表示集合x,y的最 大下界，二元运算∧称为交运算。 定义81.2设<X,≤>是格，V是X上的并运算，∧是X上 的交运算。则称<X,V,个>是格<X,>导出的代数系统。 在例4.28中，根据图4.14，集合a},b的最小上界为 a,b,即aVba,b=a}Ub；它的最大下界为E, 即a}∧b=E=anb}。这个结果可以推广到一般情况。 x,yeP(A),xVy=xUy,x∧y=xny。这样，格<P(A),R>导 出的代数系统<P(A),V,∧>实际就是代数系统<P(A),U,∩>， 所以，二元运算V和个的运算表如表8.1和表8.2所示。 在例8.1中，根据图8.1，集合4,6}的最小上界为12，即 4V6=12=4和6的最小公倍数；它的最大下界为2，即 4∧6=2=4和6的最大公约数。同样，这个结果也可以推广到 一 般情况。即在格<S12,R导出的代数系统<S12V,A>中，二 元运算V是求最小公倍数；二元运算个是求最大公约数
第8章 格与布尔代数 设X,≼是格，x,yX，今后用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,yP (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,∨,∧中，二 元运算∨是求最小公倍数；二元运算∧是求最大公约数