《离散数学格与布尔代数资料》由会员分享，可在线阅读，更多相关《离散数学格与布尔代数资料（88页珍藏版）》请在金锄头文库上搜索。
1、2019/9/27,Discrete Mathematics,回头看,R， 是一个代数系统， （）R，是一个Abel群 （）R， 是一个半群 （） 对 满足分配律，即 a（bc）（ab）（ ac） （bc）a （ba）（ac） 整数环 、高斯环 、模m剩余环 、零环,回头看,有单位元、无零因子的交换环称为整环 设R是一个有的环， 如果， 是一个群，则称R为除环，可交换的除环称为域 有限整环必为域 若p为素数，则Zp，p，p 为域,域F的特征,设F， 是一个域，则： （）在加法群F，中，每个非零元都具有同样的周期（阶） （）如果F，中非零元素的周期为有限数p，则p必为素数,2019/9/27,C
2、hapter 7,格与布尔代数 Lattices &Boolean Algebra,半加器 half adder,全加器 Full adder,全加器 Full adder,n位加法器 n-adder,布尔表达式,布尔代数 Boolean Algebra,偏序集 Posets,（布尔）代数系统L，* ,格L ,P，,格与布尔代数 Lattice&Boolean Algebra,7.1 格 (1),偏序集 Posets,例 1:S30 = 1,2,3,5,6,10,15,30,| = | x,yS30 且 x|y,S6=1,2,3,6 S30,S15=1,3,5,15 S30,偏序集: , ,2
3、019/9/27,7.1 格,定义 设L ,是一个偏序集， 如果 x , yL ,x , y必有最小上界和最大下界，则称L ,为格,2019/9/27,例 集合S的幂集P(S)和定义在其上的包含关系构成 偏序集. 对于任意子集A,Bp(S)，因为A AB,B AB， 而且若A C,B C,则AB C。 因此， A,B的最小上界A B=AB。 同理A,B的最大下界A * B=AB。 于是，是格 ; ()。 由集合S=a,b,c得到的格的Hass图，如下图所示。,7.1 格,2019/9/27,7.1 格,2019/9/27,Example :, , ,7.1 格,2019/9/27,例 判断图中
4、的哈斯图表示的偏序集是否构成格,说明为什么。,7.1 格,例 设Z+为正整数集合，对于a,b Z+，关系“”定义为： ab当且仅当a整除b。则偏序集构成格， 其中: a b是a,b的最小公倍数(记作LCM,Least Common Multiple) a * b是a,b的最大公因数(记作GCD, Greatest Common Divisor) 即 a b= LCM(a,b)， a * b=GCD(a,b),7.1 格,x,yL ,x , y 必有最小上界和最大下界,并运算与交运算,在格L，中，a, b的最小上界用 ab 表示，a, b的最大下界用 a*b表示. a, bL，由最小上界、最大下
5、界的唯一性，ab，a*b都在L上唯一确定 将 , * 视为L上的两个运算，通常称为L，上的并(Join,)运算与交(Meet,)运算,并、交 运算的性质,定理 设L，是一个格，并运算与交运算 * 满足如下性质： L1 a a a a * a a （幂等律） L2 a b b a a * b b * a （交换律） L3 （a b） c a （b c） (a * b) * c a *（b * c） （结合律） L4 a ( a * b ) a a*（a b） a （吸收集）,L1：a * a a a a a,证明 由于aa，故a是a，a的下界，又设c是a，a的任一下界，则ca，故a是a，a的最大
6、下界，即a * a a，同理可证 a a a，即L1成立,L2：a * b b * a， a b b a,证明 由于a，bb，a，故a * b b * a，同理a b b a即L2成立,L3： (a * b) * c a *（b * c）,( a * b ) * c a * b a ( a * b ) * c a * b b ( a * b ) * c c 因此，(a*b) *c是b，c的下界，从而小于等于其最大下界，即 ( a * b ) * c b * c (xa且xb,则x bc ) 因此又知 ( a * b ) * c 是a，b * c 的下界，从而 ( a * b ) * c a *
7、 ( b * c ) 同理 a * ( b * c ) ( a * b ) * c 所以 a * ( b * c ) ( a * b ) * c,L4： a*（a b） a,由于a是a，ab的下界， 故aa*(ab)， 再由*的定义， a*(ab) a，从而a*(ab)a,设是一个代数系统, 和*是L上的两个二元运算,如果这两个运算满足幂等律（L1）、交换律(L2)、结合律（L3）和吸收律(L4),则称是一个格(Lattice)。,7.1 格,格与代数系统的关系, ,例 是格 表示为 又可表示为,7.1 格,例 ,或 ,7.2 格代数系统,格L，中自然存在两个运算 和 * ，从而派生出一个代数
8、系统L，* 与 *满足LL。 反之，若给定一个代数系统L，* ，其中，运算 与 * 满足LL，是否一定能找到一个与该代数系统对应的格？ 是，一定能。,定理 设L，是一个格， 则对任意a，bL ab a*ba abb 证明： ab a*ba 设ab，则a是a，b的下界，故aa*b， 又a*ba，从而a*ba； 反之，设a*ba，则由a*bb 即知 ab 同理可证 ab，abb,7.2 格代数系统,如何定义偏序？,偏序 必须满足 ab a * ba a bb 用ab a * ba a bb 定义偏序 首先要求给定的运算 与 *满足 a * ba a bb,7.2 格代数系统,引理 设L，* 是一个
9、代数系统，* 满足LL，则 a * ba a bb 证明 设a * ba，则 a b（a * b） bb（b * a）b 反之，设 a bb 则 a * ba *（a b）a。,7.2 格代数系统,引理告诉我们在偏序关系上寻找* 是可行的。 用 ab a * ba（ a bb ） 规定关系 是可行的 但这样规定的关系 是否一定是要求的偏序关系呢？,7.2 格代数系统,定理 设L，* 是一个代数系统，运算 与 * 满足LL 令 L上的关系 定义如下： a b a * ba 则 是一个偏序关系，且 a，bL，a*b，ab分别为a, b在L，中的最大下界与最小上界，即 a * binfa，b； a
10、bsupa，b 从而L，是一个格，其中的并、交运算恰为给定的 与 *,7.2 格代数系统,证明 为偏序关系,(1)自反性;aL，因为a * aa，故aa，即满足自反性； (2)反对称性;a，bL，设ab，ba，则a * ba，b * ab，因为a * bb * a，故ab，即 满足反对称性； (3)传递性a，b，cL，设ab，bc，则a * ba，b * cb，故a * c（a * b）* ca *（b * c）a * ba，即ac，故满足传递性,7.2 格代数系统,证L，为要求的格,a，bL，（a * b）* a a*（a * b）（a * a）*ba*b，故a*ba， 同理a*bb，因此a
11、*b是a，b的下界， 又设c是a，b的任一下界，即ca，cb，则a * cc，b * cc，于是（a * b）* ca *（b * c）a * cc，即ca * b，所以a * b是a，b的最大下界，即a * binfa，b， 同理可证a bsupa，b， 这就证明了L，是格且其中的并、交运算分别为 ，*.,L3,L1,7.2 格代数系统,代数格,定义 设L，* 是一个代数系统，如果 ，*满足LL，则称L，* 为格,7.2 格代数系统,例 设N是自然数集合，对任意a，bN，规定a ba，b（即a，b的最小公倍数）， a*b（a，b）（即a，b的最大公因数）， 由于任意两自然数a，b都有唯一确定
12、的最大公因数与最小公倍数，故 *， 是N上的两个运算 L1、L2、L3、L4 是不是成立？,7.2 格代数系统,例 设S是一个集合，为集合的并、交运算，则P（S），是格，且其中的偏序为集合的包含关系,7.2 格代数系统,定理 设L，是格，a ，bL，则 （）a*ba a*bb （）aab bab,7.2 格代数系统,定理 设L，是格，a，b，cL 若 ca，cb则ca*b 若 ac，bc则abc 以上两定理由并、交运算的定义可得到,7.2 格代数系统,定理 设L，是一个格，a，a ，b ，b L，如果 ab，ab， 则 a* ab* b，a a b b 证明： a * a ab，a* a a
13、b 故 (a* a) b* b 又 a b b b，a b b b 故 a a(bb),7.2 格代数系统,推论 设L，是一个格，a，b，cL， 若ab， 则 a*cb*c，acbc,7.2 格代数系统,定理 设L是一个格，a，b，cL，则 a *（b c）（a * b）（a * c） a （b * c）（a b）*（a c）,b *（cd）b * ab （b * c）（b * d） b e,c *（bd）c * ac （c * b）（c * d）e dd c d,7.2 格代数系统,证明：因为 b b c 故 a * b a *（b c）-(1) 又 c b c 故 a * c a *（b c）-(2) 所以（a * b）（a * c） a *（b c）（依据定理5） 即 a *（b c）（a * b）（a * c）,同理 a （b * c）（a b）*（a c）,7.2 格代数系统,2019/9/27,定义子格(Sublattice):设是一个格,如果是的子代数,则称是的子格Sublattice)。 子格也是一个格,因为当运算和*限制在S上时,交换律、结合律和吸收律也是成立的。,7.3 子格与格同态,2019/9/27,不是的子格，这是因为,
