哈尔滨理工大学呻斛生課程 离影数 第13章格与布尔代数 O计算机系
第13章 格与布尔代数 离 散 数 学 哈尔滨理工大学本科生课程 计算机系
本章内空 13.1格的定义与性质 13.2子格与格同态 13.3分配格与有补格 13.4布尔代数 本章总结 作业
本章内容 13.1 格的定义与性质 13.2 子格与格同态 13.3 分配格与有补格 13.4 布尔代数 本章总结 作业
13,1格的定义与性质 定义13.1设<S,≤>是偏序集,如果∨x,y∈s,tx,y都有最小 上界和最大下界,则称S关于偏序≤作成一个格(atte) 说明:由于最小上界和最大下界的唯一性,可以把求{x,y的最 小上界和最大下界看成x与y的二元运算∨和∧ xVy:表示x与y的最小上界 x∧y:表示x和y的最大下界 本章出现的∨和∧符号只代表格中的运算,而不再有其它的 含义
13.1 格的定义与性质 定义13.1 设<S,≤>是偏序集，如果x,y∈S，{x,y}都有最小 上界和最大下界，则称S关于偏序≤作成一个格(lattice)。 说明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最 小上界和最大下界看成x与y的二元运算∨和∧。 x∨y：表示x与y的最小上界 x∧y：表示x和y的最大下界。 本章出现的∨和∧符号只代表格中的运算，而不再有其它的 含义
格的奥例 例13.1设n是正整数,S是n的正因子的集合。D为整除关系, 则偏序集<,D构成格。Vx,y∈Sn, x∨y是|cm(x,y),即x与y的最小公倍数。 x∧y是gcd(x,y),即x与y的最大公约数。 下图给出了格<S3D),<S,D>和<S30,D>。 30 8 6 10 15 3 2 <S,D> Se,D> <S30,D>
格的实例 例13.1 设n是正整数，Sn是n的正因子的集合。D为整除关系， 则偏序集<Sn ,D>构成格。x,y∈Sn， x∨y是lcm(x,y)，即x与y的最小公倍数。 x∧y是gcd(x,y)，即x与y的最大公约数。 下图给出了格<S8 ,D>，<S6 ,D>和<S30,D>
例13,2 例13.2判断下列偏序集是否构成格,并说明理由。 (1)P(B),>,其中P(B)是集合B的幂集 (2)<Z,≤>,其中Z是整数集,≤为小于或等于关系。 (3)偏序集的哈斯图分别在下图给出
例13.2 例13.2 判断下列偏序集是否构成格,并说明理由。 (1) <P(B),>，其中P(B)是集合B的幂集。 (2) <Z,≤>，其中Z是整数集,≤为小于或等于关系。 (3) 偏序集的哈斯图分别在下图给出