《离散数学》课件 第19章 格与布尔代数.ppt

*****************************************分配格*定义设L为格，若?a,b,c?L有a?(b?c)=(a?b)?(a?c)或a?(b?c)=(a?b)?(a?c)则L为分配格.注：在任何格中两个分配等式是等价的.例如a?(b?c)=(a?b)?(a?c)?a?(b?c)=(a?b)?(a?c)证(a?b)?(a?c)=((a?b)?a)?((a?b)?c)(?对?的分配律)=a?((a?c)?(b?c))(吸收律,?对?的分配律)=(a?(a?c))?(b?c)=a?(b?c)(结合律,吸收律)反之，同理可证.分配格判别定理*定理1设L为模格，L为分配格当且仅当若?a,b,c?L有(a?b)?(b?c)?(c?a)=(a?b)?(b?c)?(c?a)注：一般格成立不等式(a?b)?(b?c)?(c?a)?(a?b)?(b?c)?(c?a)定理2设L为模格，L为分配格当且仅当L不含有与钻石格同构的子格.判别定理一的证明证：“?”?a,b,c?La?(b?c)=a?(a?b)?(b?c)?(c?a)（吸收律）=((a?b)?((b?c)?(c?a)))?a（等式替代）=(a?b)?(((b?c)?(c?a))?a)（模律a?b?a）=(a?b)?(((c?a)?(b?c))?a)（交换律）=(a?b)?(c?a)?(b?c?a)（模律c?a?a）=(a?b)?(a?c)（交换律,上界）*条件：(a?b)?(b?c)?(c?a)=(a?b)?(b?c)?(c?a)判别定理一的证明（续）*判别定理二的证明*uvxyza?c=b?ca?c=b?ca?b,?a=b模格、分配格之间关系*(a?b)?(b?c)?(c?a)=(a?b)?(b?c)?(c?a)格模格分配格不含与五角格同构子格不含与钻石格同构子格a?b,(a?c)?b=a?(c?b)a?c=b?ca?c=b?c?a=b分配律有界格与有补格*补元与有补格*0cba101abc01abca?b=0,a?b=1,则a与b互为补元.0与1互补a,b,c没补元0与1互补a,b,c中任两个元素都互补0与1互补a与b,c互补有补格补元性质：有界分配格中元素x如果存在补元，则是唯一的有补格定义：每个元素都有补元的有界格思考：求补是否为有补格上的一元运算？求补是否为分配格上的一元运算？*19.4布尔代数布尔代数定义布尔代数性质布尔代数的同态有限布尔代数的结构*布尔代数的定义定义有补分配格称为布尔格（布尔代数）实例：幂集格定理设B,?,°,?,a,b是代数系统，其中?,°为二元运算,?为一元运算，a,b为0元运算.如果满足以下算律：交换律x*y=y*x,x°y=y°x分配律x*(y°z)=(x*y)°(x*z)x°(y*z)=(x°y)*(x°z)同一律x?b=x,x°a=x补元律x??x=a,x°?x=b则B,?,°,?,a,b构成布尔格.*定理证明证明思路：由b,a分别为?和°运算的单位元，证b和a恰为°和?运算的零元；再证吸收律、结合律证:(1)x°b=(x°b)?b=(x°b)?(x°?x)=x°(?x?b)=x°?x=bx?a=(x?a)°a=