离散数学第六章格与布尔代数

1、离散数学第六章格与布尔代数1第1页，共47页，2022年，5月20日，11点13分，星期五6.1格的概念本章将介绍其他的代数系统格和布尔代数，格论是数学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在19世纪，就已经有了相当的发展，布尔代数是研究和逻辑、集合等运算有关的知识。2第2页，共47页，2022年，5月20日，11点13分，星期五定义 设为偏序集, BA, yA. (1) 若x(xBxy)成立, 则称y为B的上界; (2) 若x(xByx)成立, 则称y为B的下界; (3) 令C = y | y为B的上界 ,若 C 有最小元素，则称该最

2、小元素为 B 的最小上界或上确界,记为LUB(上确界) (4) 令D = y | y为B的下界 ,若 D 有最大元素，则称该最大元素为为B的最大下界或下确界,记为GLB(下确界) 复习偏序关系中的上界，下界，上确界与下确界3第3页，共47页，2022年，5月20日，11点13分，星期五6.1格的概念例：偏序集(2,3,5,7,14,15,21,/)，“/”为整除关系。 其hasze图如下：2,7的最小上界、最大下界各为什么？2,3呢？5,14呢？ 2,7的最小上界为14。最大下界无。2,3的最小上界无，最大下界无。5,14的最小上界无，最大下界无。4第4页，共47页，2022年，5月20日，1

3、1点13分，星期五然而也存在这样一类偏序集，它的每一对元素都有最小上界和最大下界，如：偏序集(1,2,3,4,6,8,12,24,/)：其Hasze图如下： 6.1格的概念5第5页，共47页，2022年，5月20日，11点13分，星期五一、格1定义：设是一个偏序集，若对A中的任两个元素a、b，都有最小上界和最大下界，则称为格。其中上确界 lub a,b，记为ab,称为a和b的并。 下确界 glb a,b，记为ab,称为a和b的交。将、，看作集合上的两个二元运算，故格所诱导的代数系统记作。 6第6页，共47页，2022年，5月20日，11点13分，星期五一、格下述偏序集能构成格的是（ ？）(a)

4、(b)(c)(d)bbcdefacdfabcdefghabcdefac7第7页，共47页，2022年，5月20日，11点13分，星期五一、格2、对偶格：若是一个偏序集，则也是一个偏序集，其中“”是“”的逆关系。若是一个格，则也是一个格，称这两个格互为对偶。 若将关于格的命题中符号，、，分别用，、，代替，则得到一个新的命题，称这个新命题为原命题的对偶命题。定理：对于格中的一个真命题，其对偶命题亦真。 8第8页，共47页，2022年，5月20日，11点13分，星期五二、格的性质定理1：若是一个格，则对任意a、b 、cA，有（1）aab， bab （2）aba ，abb（3）若ac且bc，则abc（

5、4）若ca且cb，则cab9第9页，共47页，2022年，5月20日，11点13分，星期五二、格的性质（1）aab， bab 证明：因ab= luba，b，它显然是 a 的一个上界， aab ，同理：bab。 （2） aba ，abb证明：因ab= glba，b，它显然是 a 的一个下界， aba ，同理：abb。10第10页，共47页，2022年，5月20日，11点13分，星期五二、格的性质（3）若ac且bc，则abc 证明：ac且bc，由上界的定义知，c是a，b的一个上界，而ab是a，b的最小上界，abc。（4） 若ca且cb，则cab证明：ca且cb，由下界的定义知，c是a，b的一个下界

6、，而ab是a，b的最大下界，cab。 11第11页，共47页，2022年，5月20日，11点13分，星期五二、格的性质推论：在中，对于任意a，b ，cA，如果bc，则 abac，abac。定理2：若是一个格，则对于任意a，bA，以下三个公式等价；（1）ab （2）ab =b （3）ab =a12第12页，共47页，2022年，5月20日，11点13分，星期五二、格的性质（1）ab （2）ab =b （3）ab =a证明：（1）（2） ab 且偏序关系是自反的。 bb ， abb 又 bab成立 ab =b（偏序关系是反对称的） 设ab=b aab成立，将ab =b代入aab得：ab 类似可证（

7、1）（3） 13第13页，共47页，2022年，5月20日，11点13分，星期五二、格的性质定理3：是一个格，则对于任意a，b，cA，满足以下四个定律：（1）交换律： ab =ba ab =ba（2）吸收律： a（ab）=a a （ab ）=a（3）结合律：a（bc）=（ab ）c， a（bc）=（ab ）c（4）等幂律：aa = a aa = a14第14页，共47页，2022年，5月20日，11点13分，星期五二、格的性质定理4：设有格，对于任意a，b，c，dA，如果ab和cd，则（1） acbd， （2）acbd证： bbd，dbd ，而ab，cd， 由传递性可得：abd ，cbd，这就

8、表明bd是a和c的一个上界，而ac是a和c的最小上界，必有acbd。类似地可以证明：acbd 15第15页，共47页，2022年，5月20日，11点13分，星期五二、格的性质定理5：在一个格中，对于任意a，b，c A，有下列分配不等式成立：（1）a（bc）（ab）（ac）（2）a（bc）（ab）（ac）证：由定理1，（1）（2）知： aab和aac，可得： a （ab）（ac）， 又 bc bab和 bccac bc（ab）（ac） 对于和，有：a（bc）（ab）（ac）利用对偶原理，即得：（ab）（ac）a（bc） 16第16页，共47页，2022年，5月20日，11点13分，星期五定义 设

9、是一个格，设非空集合S且S A,若对任意的a,bS,有abS,abS,则称S, 是的子格。显然，子格必是格。而格的某个子集构成格，却不一定是子格。三、子格17第17页，共47页，2022年，5月20日，11点13分，星期五【例】 设A, 是一个格，其中A=a,b,c,d,e,其哈斯图如图所示。S1=a,b,c,d，S2=a,b,c,e,则S1, 是A, 是一个子格，S2, 不是A, 是一个子格，因为bc=dS2，S2, 不是子格。三、子格18第18页，共47页，2022年，5月20日，11点13分，星期五 定义：设 A1, , A2, 是两个格,由它们所诱导的代数系统为A1, 1,1 ,A2,

10、 2,2 ，如果存在映射f: A1 A2,任意a,b A1，满足：f(a 1 b)=f(a) 2 f(b), f(a 1 b)=f(a) 2 f(b)称f为A1, 1,1 到A2, 2,2 的格同态。若f是双射，则称f为格同构， 亦称 A1, , A2, 这两个格是同构。 四、格同态与格同构类似群的同态，也可以定义格的同态。19第19页，共47页，2022年，5月20日，11点13分，星期五定理：设f是格 A1, 1 到 A2, 2的格同态，则对任意的x,y A1 ，如果x 1 y，必有f(x) 2 f(y)。这说明格的同态是保序的。定理：设两个格为 A1, 1 ， A2, 2，f是从 A1到

11、 A2的的双射，则 f是 A1, 1 到 A2, 2是格同构，当且仅当对任意的x,y A1 ，如果x 1 y f(x) 2 f(y)。四、格同态与格同构20第20页，共47页，2022年，5月20日，11点13分，星期五6.2分配格对格中的任意元素a,b,cA，必有a (b c) (a b) (a c)(a b) (a c) a (b c）当上述两式中等号成立的时候，就得到一类特殊的格。定义设是由格所诱导的代数系统。如果对任意的a,b,cA，满足： a (b c)=(a b) (a c) a (b c)=(a b) (a c)则称是分配格。21第21页，共47页，2022年，5月20日，11点

12、13分，星期五例：判断图示的格是否是分配格 a3（a4a5）=a3a1=a3 （a3a4）（a3a5）=a4a6=a4 所示的格不是分配格。 6.2分配格22第22页，共47页，2022年，5月20日，11点13分，星期五6.2分配格定理如果格中交对并是分配的，那么并对交也是分配的，反之亦然。证明：已知a (b c) (a b) (a c)(a b) (a c)=(a b) a) (a b) c)=a (a b) c)=a (a c) (b c)=(a (a c) (b c)=a (b c)即：并对交也是分配的。23第23页，共47页，2022年，5月20日，11点13分，星期五6.2分配格定

13、理每个链均是分配格。证明：设是链。对任意a，b，cA(1)若ab或ac，则 a (b c) a， (a b) (a c)a即： a (b c) (a b) (a c)(2)若ab且ac，则 a (b c) b c， (a b) (a c) b c即：a (b c) (a b) (a c)。得证。24第24页，共47页，2022年，5月20日，11点13分，星期五定理：设是一个分配格，则对于任意a，b，c A，如果有ab =ac和ab =ac成立，则必有b =c。6.2分配格证： （ab）c =（ac）c = c（ab）c=（ac）（bc）=（ab）（bc）=（ba）（bc）=b（ac）=b (

14、ab)=b b =c 25第25页，共47页，2022年，5月20日，11点13分，星期五6.2分配格定义设是由格所诱导的代数系统。如对A中任意a，b，c有：baa (b c) b (a c) 则称为模格。26第26页，共47页，2022年，5月20日，11点13分，星期五6.2分配格定理分配格是模格。证明：由于a (b c) (a b) (a c)若ba，则a b=b，代入上式得 a (b c) b (a c)分配格是模格27第27页，共47页，2022年，5月20日，11点13分，星期五6.3有补格定义设是一个格，如果存在元素aA，对于任意的x A，都有：ax 则称a为格的全下界，记格的全

15、下界为0。定义设是一个格，如果存在元素bA，对于任意的x A，都有：xb 则称b为格的全上界，记格的全上界为1。28第28页，共47页，2022年，5月20日，11点13分，星期五6.3有补格定理如果格有全上界（全下界），那么它是唯一的。证明：（反证法）设有两个全上界a和b，则由定义 ab，且ba，由“”的反对称性， ab。定义设是一个格，如果格中存在全上界和全下界，则称该格为有界格。29第29页，共47页，2022年，5月20日，11点13分，星期五6.3有补格定理如果是有界格，全上界和全下界分别是1和0，则对任意元素aA，有： a1=1a=1 ，a1= 1a=a， a0=0a=a ，a0=

16、 0a=0。证明：因为1a1，又因 (a1) A且1是全上界， a11， a1=1。由交换律：1aa1=1。因为aa，a1，a aa 1，即： aa 1，又 a1a， a1= a。仿此可得另两式。30第30页，共47页，2022年，5月20日，11点13分，星期五6.3有补格定义设是一个有界格，对于A中的一个元素a，如果存在bA，使得ab=1和ab= 0，则称元素b是元素a的补元。讨论定义：（1） 和是可交换的，补元是相互的。 （2） ，即在有界格中，1和0互为补元； （3）由定义可知A中一个元素的补元不一定是唯一的；可能存在多个补元，也可能不存在补元。31第31页，共47页，2022年，5月

17、20日，11点13分，星期五6.3有补格定义在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。讨论定义：（1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。32第32页，共47页，2022年，5月20日，11点13分，星期五如图所示的格，是有补格吗？该格是有界格，却不是有补格。 6.3有补格33第33页，共47页，2022年，5月20日，11点13分，星期五6.3有补格定理在有界分配格中，若有一个元素有补元，则必是唯一的。证明：设a有两个补元素b和c,则有： ab=1,ab= 0 ac=1,ac= 0所以ab= ac，

18、ab= ac由定理知：b=c34第34页，共47页，2022年，5月20日，11点13分，星期五有补分配格定义：一个格如果既是有补格，又是分配格，则称该格为有补分配格，可以证明：在有补分配格中，任一元素的补元都是唯一的。将有补分配格中任一元素a的唯一补元记为a6.3有补格35第35页，共47页，2022年，5月20日，11点13分，星期五6.4 布尔代数定义一个格如果它既是有补格，又是分配格，则它为有补分配格。我们把有补分配格中任一元素a的唯一补元记为a。定义一个有补分配格称为布尔格。讨论定义：(1)布尔格中，每个元素有唯一的补元。(2)我们可以定义A上的一个一元运算，称为补运算，记为“-”。

19、-36第36页，共47页，2022年，5月20日，11点13分，星期五6.4 布尔代数定义由布尔格，可以诱导一个 包括交，并和补运算的代数系统，称此代数系统为布尔代数。例：设S是一个非空有限集，是一个格，且是一个布尔格。由所诱导的代数系统为 是一个布尔代数。其中“,-”分别是集合的交、并、补运算。37第37页，共47页，2022年，5月20日，11点13分，星期五6.4 布尔代数例：设A是一非空集合,(A)是A的幂集,可以验证,是个布尔代数,称此为集合代数,其中运算为, , ,全下界,全上界A。S是命题公式的全体,则是一个布尔代数,称之为命题代数。其中运算为, , ,全下界是恒假公式0,全上界

20、是恒真公式1。38第38页，共47页，2022年，5月20日，11点13分，星期五6.4 布尔代数定理对于布尔代数中任意两个元素a,b，必定有39第39页，共47页，2022年，5月20日，11点13分，星期五定义：当布尔代数的载体A的基数|A|是有限数时,则称之为有限布尔代数。定义：设是一个布尔代数，aA,如果a盖住0，则称元素a是该布尔代数的一个原子。6.4 布尔代数定义：布尔代数中除0外的每个元素，都可以唯一地表示成原子的并。例如：40第40页，共47页，2022年，5月20日，11点13分，星期五6.4 布尔代数例：，其中S=a,b,c，在这个布尔代数中的元素分三种情况：（）界：全上界

21、S，全下界 ；（）a,b,c单个元素集合的元素；（）二，三个元素作为集合的元素，但它们均可用单个元素的集合的元素来表述：a,b=ab ,a,c=ac, b,c=bc, a,b,c=abc 。 a,ca,b,ca,bb,cacb41第41页，共47页，2022年，5月20日，11点13分，星期五6.4 布尔代数定理设是由有限布尔格所诱导的一个有限布尔代数，S是布尔格中的所有原子的集合，则和同构。42第42页，共47页，2022年，5月20日，11点13分，星期五6.4 布尔代数该定理可得以下两个推论：a)与同构，|p(S)|=2|s|所以，|B|=2|s| ，故任一有限布尔代数载体的基数是2的幂。b)任一有限布尔代数和它的原子集合S构成的幂集集合代数同构，但后者又与任一基数相同的幂集集合代数同构，故具有相同载体基数的有限布尔代数都同构。 43第43页，共47页，2022年，5月20日，11点13分，星期五第三篇小结通过本篇的学习应该达到以