第九章 格和代数.pptVIP

第十三章 格与布尔代数 第一节 格的定义与性质 第9章 格与代数 第9章 格与代数 第9章 格与代数 第9章 格与代数 第9章 格与代数 第9章 格与代数 第9章 格与代数 第9章 格与代数 第9章 格与代数 第9章 格与代数 第9章 格与代数 第9章 格与代数 * * 一、偏序格的定义 定义 设A，≤是一个偏序集，如果A中任意两个元素x,y∈A，都有上确界和下确界，则称A，≤为格。 [注]：对任意的x,y∈A,记 x∨y=sup{x,y} x∧y=inf{x,y} 二、 偏序格的基本性质 1、对偶命题 设f是含有格中元素以及符号=，≤，≥，∧和∨的命题，令f*是将f中的≤替换成≥，≥替换成≤，∧替换成∨，∨替换成∧所得到的命题，称f*为f的对偶命题。 2、对偶原理 设f是含有格中元素以及符号=，≤，≥，∧和∨的命题，若f对一切格为真，则f的对偶命题f*也对一切格为真。 3、定理 设A，≤是格，则对任意的x,y∈A，有 (1)交换律 x∨y=y∨x x∧y=y∧x (2)结合律 (x∨y)∨z=x∨(y∨z) (x∧y)∧z=x∧(y∧z) (3)等幂律 x∨x=x x∧x=x (4)吸收律 x∨(x∧y)=x x∧(x∨y)=x 三、代数格及与偏序格的等价性 定义 设集合S关于其上的二元运算*，+封闭，若*，+满足交换律、结合律和吸收律，则称(S,*,+)是一个格，称为代数格。 定理 一个偏序格当且仅当为代数格。 【注】：将偏序格S,≤和代数格(S,*,+)统称为格，这样可以从两个不同的角度描述格。 ≤与运算*，+间的关系为： a*b=inf{a,b}，a+b=sup{a,b} 四、格的其他性质 1、设L是格，则对任意的a,b∈L，有 a≤b?a*b=a?a+b=b 2、设L是格，对任意的a,b,c,d∈L,若a≤b且c≤d，则 a*c≤b*d,a+c≤b+d 定义 设〈L，*，+〉是一个格，S是L的非空子集。 若〈S，*，+〉是格，则称之为L的子格。 第二节 子格 一、子格 [注] 〈S，*，+〉是〈L，*，+〉的子格当且仅当运算*和+在S上是封闭的。 1、定义 设〈L，*，+〉是格，若*，+满足分配律，即对任意的a，b，c∈L，有 a*（b+c）=（a*b）+（a*c） a+（b*c）=（a+b）*（a+c） 则称〈L，*，+〉是分配格. 第三节 分配格与有补格 一、分配格 [注]：格L是分配格 L中不含有与钻石格或五角格同构的子格。 2、性质 格L是分配格 若对任意的a，b，c∈L， 有a*b=a*c且a+b=a+c,则b=c。 二、有界格和有补格 1. 定义 设〈L，*，+〉是格，若L有最大元和最小元，则称〈L，*，+〉为有界格，记作〈L，*，+，0，1〉 。 2.定理 设〈L，*，+，0，1〉为有界格，则对任意a∈L，有 a*0=0,a+0=a a*1=a,a+1=1 3.定义 设有界格L,*,+,0,1，a∈L,若存在b∈L，使得a*b=0，a+b=1 则称b为a的补元(余元)。 [注]：1）补元是相互的。 2）在一般的有界格中，元素的补元可能不存在或存在不唯一。 5.定理 设(B,﹡,+)即是一个有界格，同时还是一个分配格，那么若某一个元素有补元素，则其补元素必是唯一的。 4.定义 在一个有界格中，如果每个元素均存在补元，则称此格为有补格。 第四节 布尔代数 一、概念 定义：有补的分配格称为布尔格或布尔代数。 二、布尔代数的公理化定义 定义 设(B,﹡,+)是代数系统，若满足：对任意的a,b,c∈B,有 1)交换律成立：a﹡b=b﹡a，a+b=b+a； 2)分配律成立：a﹡(b+c)=(a﹡b)+(a﹡c) a+(b﹡c)=(a+b)﹡(a+c) 3)同一律成立：存在0,1∈B，使a+0=a，a﹡1=a 4)互补律成立：对任意a∈B，存在b∈B使得 a+b=1，a﹡b=0 则称(B,﹡,+)为布尔代数。 【注】布尔代数可归纳为： 一个代数系统具有两种代数运算，若满足： a)交换律成立； b)分配律成立； c)存在0，1元素 d)存在补元 则此代数系统是一个布尔代数。 定理 设有布尔代数(B,﹡,+) ，对于任意两个元素a，b∈B，必定有 三、布尔代数的性质 9.3 布尔代数 9.3.2 布尔代数的性质 定义9.12 设A，∧，∨，￣和B，∧，∨，￣是两个布尔 代数，如果存在着A到B的双射f，对于任意的a，b∈A，都有 f（a∨b）=f（a）