第障格与布尔代数 第8章格与布尔代数 8.,1格 8,2布尔代数 返回总目录
第8章 格与布尔代数 第8章 格与布尔代数 8.1 格 8.2 布尔代数 返回总目录
第障格与布尔代数 第8章格与布尔代数 8.1格 8.1.1格的概念和性质 定义81.1设<>是偏序集,如果∨xy∈Y,集合1xy 都有最小上界和最大下界,则称<X,≤>是格。 【例81】设S12=1,2,346,12}是12的因子构成的集合 其上的整除关系R=1<x|x∈S2个y∈S2x整除y},R是S2 上的偏序关系,<S12R是偏序集。写出S12上的盖住关系 COVS12,画出哈斯图,验证偏序集<S12R是格 解:S12上的盖住关系 COVS12=1<1,2><1,3><24>,<2,6>,<36> <4,12><6,12>}, 哈斯图如图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是格
第障格与布尔代数 图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虽有三个上界，但没有最小上界
第障格与布尔代数 设<X>是格,xy∈X,今后用x∨y表示集合xy的最 小上界,二元运算∨称为并运算;用xy表示集合xy}的最 大下界,二元运算∧称为交运算。 定义8.1.2设<,≤>是格,∨是Ⅺ上的并运算,∧是X上 的交运算。则称<X,∨,∧>是格<X,令>导出的代数系统 在例428中,根据图414,集合a},b}的最小上界为 1ab},即a∨bab}=a%Ub};它的最大下界为E, 即{a}∧b}=E=a}∩b}。这个结果可以推广到一般情况 xy∈P(4),xy=xUy,x^=xny。这样,格<P(4)R>导 出的代数系统<P(4,∧>实际就是代数系统<P(A,∪,∩> 所以,二元运算∨和∧的运算表如表81和表82所示 在例81中,根据图81,集合{46}的最小上界为12,即 4∨6=12=4和6的最小公倍数;它的最大下界为2,即 4∧6=2=4和6的最大公约数。同样,这个结果也可以推广到 般情况。即在格<S12R导出的代数系统<S12V,∧>中,二 元运算∨是求最小公倍数;二元运算∧是求最大公约数
第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,∨,∧中，二 元运算∨是求最小公倍数；二元运算∧是求最大公约数