《格与布尔代数课件》由会员分享，可在线阅读，更多相关《格与布尔代数课件（50页珍藏版）》请在金锄头文库上搜索。
1、第五章 格与布尔代数 本章在了解了代数系统一般概念的基础上，着重介绍的包含有两个代数运算的代数系统:格和布尔代数。主要讨论这些代数系统的相关基本概念和性质 主要内容如下： 5.1 格； 5.2 分配格和有补格； 5.3 布尔代数,一、 格 1格的定义 定义5-1 设是一个偏序集，如果L中任意两个元素都存在着最大下界和最小上界，则称是格。,=glb（ ， ）， =lub（ ， ）。,若是一个格，则意味着也是一个形为的代数系统，其中 和 是L上的两个二元运算，对于任意 ， ， 表示在偏序“”意义下， 和 的最小上界， 表示 和 的最大下界。,例1 试判断下列次序图给出的偏序集哪些是格？,解 （a）
2、不是格， (b)不是格，,(c)是一个格， （d）是一个格,在格L；中有如下四个关系式成立:,2格的性质 定理5-1 在格中，对于任意 以下三式中若任意一式成立，那么其它两式也成立.,证明 = 设 ，, = 设, = 设,定义5-2 设是格，P是包含格的元素和符号=、， ，的命题，将P中的、，和分别替换成、 、 和所得的命题PD称为P的对偶。,例如 的对偶是,对偶原理 ： 对于格上的任一真命题P，其对偶 PD 亦为格上的真命题。,定理5-2（交换律） 设是格，则对任意的 有:,定理5-3 （结合律） 设是格，则对任意的 ，有,证明,定理5-4 （吸收律） 设L；是格，则对任意 ，有,证明 (b
3、) 由（5-4）,另一方面，由（5-1）,于是，由（5-5） （2）,由（1)、(2）和反对称性,定理5-5 （等幂律） 设L；是格，则对任意 ，有,证明 （a）由定理5-17 ,定理5-6 （格的保序性） 设L；是格，则对于任意 ，有,由,和,因为 所以由(1)有,例2 设 L = ，L上的整除关系 与L构成一个格，记作，,3( 6 4 ) = 3 1= 3,(36)(34) = 6 12 = 6,于是 3(64)(36)(34),6(34) = 612 = 6,(63)(64)= 31= 3,于是 6(34)(63)(64),定理5-7 设是格，则对任意 ,有,证明 （a）由(5-4)有,
4、于是，根据定理5-6有,又由（5-4）有,3格的另一种定义方式 定理5-8 设是一个代数系统，其中和都是二元运算，满足交换律，结合律和吸收律，则在L上必存在一偏序关系，使得是一个格。,可以证明关系是L上的自反，反对称和可传递的关系，因此是L上的偏序关系。,进一步还可以证明，对任意 ， 是在偏序关系意义下 1和 2的最小上界， 1 2 是 1和 2的最大下界。 故是一个格。,格既可以看作是一个偏序集，也可以看作是一个代数系统。,定义5-3 设是一个代数系统， 和 是 L 上的两个二元运算，如果这两个运算满足交换律，结合律和吸收律，则称是格。,例3 在全集合 U 的幂集 2U = 上的包含关系“
5、”是 2U 上的一偏序关系。,因为对任意Si 2U，总有Si Si，所以 是自反的。,对任意Si , Sj 2U , 若Si Sj ，且Sj Si ， 则必有Si = Sj ，所以 是反对称的。,对任意Si , Sj ，Sk 2U，若Si Sj ，Sj Sk ，则必有Si Sk，所以 是可传递的。 因此是一偏序集。,因此SiSj是Si和Sj的上界。,对于任意Si , Sj 2U，有Si SiSj，Sj, SiSj，,类似地可以证明，对任意 ，glb(si,sj)=sisj 因此是一个格 另一方面，集合的并运算和交运算和2U构成代数系统 ，因为运算和都满足交换律，结合律 和吸收律，因此是一个格。
6、,则必有SiSj S。因此SiSj是Si和Sj的最小 上界。即lub(Si，Sj)= SiSj。,若有S 2U，使得 Si S ，Sj S，,例4 设U=a,b,c 则2U=,a,b,c,a,b,a,c,b,c,a,b,c,三 子格 定义5-4 设是格，如果是的子代数，则称是的子格。,格对应的代数系统形式的格是.,子格也是一个格。,令 S1=b,a,bb,c,a,b,c S2=,a, c,a, c S3=,a,c,a,b,a,c,b,c,a,b,c,是的子格。,也是的子格。,S3不能与这两个运算构成的子格。,2 6,1 12,3 4,1 10,（1） glb(6,9) = ; glb(8,12
7、) = .； （2） glb(9,7) = ; lub(5,10) = .。,12,Y Y,N N,定义5-5 设是一个格，若对于任意的 1, 2， 3 L，有 则称是分配格。,52 分配格和有补格 一、分配格 1分配格的定义,例1 对任意的集合A，是一个分配格，,= aa =a 因此 b(cd)（bc）bd）,而（bc)(bd）,2 分配格的判别,定理5-11 在格中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的；如果并运算对交运算是可分配的，则交运算对并运算也是可分配的。,证明 设在格中，对任意 1， 2， 3L，有 1 （ 2 3）=（ 1 2） （ 1 3 ）,例如 设
8、L =1，2，4，16，32，64, 定义在L上的整除关系与L构成一个链。,设是一个偏序集，若对于任意的 ， L，或者 ，或者 ，则称是一个链。,例3 每一个链都是一个分配格。,证明 （1）先证明是一个格。,由链的定义，对于任意 1， 2L或者 1 2 ， 或者 2 1。,若 1 2，则glb( 1, 2)= 1 ,lub( 1, 2)= 2,若 2 1，则glb( 1, 2)= 2 , lub( 1, 2)= 1,所以是一个格，可将其表示为。对任意 1, 2 L， 1 2=lub( 1, 2), 1 2=glb( 1, 2),(2) 证明 是一个分配格,对任意 1, 2, 3L必有 2 3或
9、者 3 2， 不妨设 2 3，,于是有 1 （ 2 3）= 1 3。,又因为 1 2 1 3，,所以（ 1 2） （ 1 3）= 1 3,因此 1 （ 2 3）=（ 1 2） （ 1 3）,若 3 2，其证明方法类似，因此链是一个 分配格。,3分配格的性质 定理5-14 设 1， 2， 3是分配格中的任意三个元素， 那么 当且仅当,证明 若 ，则显然,反之，设,则,对于非分配格，定理523不成立。,c d = c b , c d = c b ， 但 b d 。,二 有补格 1最小元素0和最大元素1,例4 是一个格，但这个格既无最小元素，又无最大元素。,这个格有最小元素，但没有最大元素。,格中无
10、论U是什么样的集合，均有最小元素和最大元素U。,具有最小元素和最大元素的格称为有界格。,在有界格中，对任意L，有0 ， 1.,于是由定理5-14，对任意 ，有,2补元素 定义5-6 设是一个有界格， L，若存在元素 L，使得 =1 = 0，则称 是 的补元素。,因为对任意S2U， 所以S的补集 是S的补元素。,例6 格 是一个有补格，,3有补格 定义5-7 设是一个有界格，如果L中每一个元素都有补元素，则称是有补格。,(a)是分配格，但不是有补格，,(c)既是有补格，又是分配格；,例7 是有补分配格。,三、有补分配格 若格既是分配格，又是有补格，则称为有补分配格,(d)是有补格，但不是分配格。
11、,(b)既不是分配格，又不是有补格；,有补分配格有如下一些性质： 定理5-15 在有补分配格中，任一元素的补元素是唯一的。,使得 , ， ,于是 ， ， 由定理 5-23 .,我们记 的补元素为 。,证明 假设 有两个补元素 和 ，,定理5-16 （对合律） 在有补分配格中，对每一个 ， 有 。,证明 因为 ，由交换律有 .,所以 是 的补元素，由补元素的唯一性,故有 。,定理5-17 （德摩根定律） 在有补分配格中，对于任意的 (a) (b),证明 （a）,由补元素的唯一性有,练习5-2 1、填空 （1）下图所表示的格中 d 有 个补元素，它们分别是_. a 有 个补元素，它们是 . b 的
12、补元素是 。,3 a、b、c,1 d,d,B,B,A,5.7 布尔代数 一 布尔代数的定义 定义5-8 如果一个格是有补分配格，则称其为布尔代数，一般记作。,（1）交换律：,（3) 等幂律：,（4）吸收律：,（2）结合律：,布尔代数具有如下性质，对于B中任意元素x，y，z，有,（5）分配律：,（8）互补律：,（9）对合律：,（10）德摩根定律：,例1 全集合 U 的幂集 2U 上定义的集合的并，交和补运算与 2U 构成的代数系统称作集合代数，它是一个布尔代数，,定义5-9 设是一个代数系统， 和 是B上的二元运算，- 是一元运算，若这些运算满足交换律，分配律，同一律和互补律，则称是布尔代数。,
13、二、布尔代数的性质 定理5-18 布尔代数的每一子代数都是布尔代数。,定理5-20 每一有限布尔代数都有2n（nZ）个元素，元素个数相同的布尔代数必同构。,定理5-19 布尔代数的每一满同态象也是布尔代数。,例9 设,则 和,等都是例8中 的子代数.,练习5-3 1 在下列各题后面的括号中键入“Y”或“N”来回答 各题中相应的问题。 （1） 设是一个五元素的分配格，问该格 是有补格吗？ （ ） （2） 设是一个九元素的有补格，问该格 是分配格吗？ （ ） （3） U=a,b,c，2U ； 是布尔代数吗？( ) (4) 上题的2U； 的子代数是布尔代数吗？ ( ),N,N,Y,Y,1 设和是偏序集，按下面方式定义 L1 L2上的关系：对于所有的（ 1 ， 2）， （ 1 ， 2）L1 L2，有 (（ 1 ， 2）（ 1 ， 2）) ( 1 1， 2 2 ) 试证明是偏序集。,证明 对于任意的（ 1 ， 2） L1 L2 ， 因为 1 1 ， 2 2 所以（ 1 ， 2）（ 1 ， 2）,例 题,对于任意的（ 1 ， 2）,（ 1， 2）L1L2 ， 如果（ 1， 2）( 1， 2）且（ 1 ， 2）（ 1 ， 2），则有 1 1， 2 2 且 1 1， 2 2 ， 由反对称性得 1= 1 ， 2= 2， 因此有（ 1 ， 2）=（ 1 ， 2）。
