离散数学-第6章格与布尔代数课件.ppt

1,代数系统,第六章格和布尔代数 1格的概念 2分配格 3有补格,2,6-1 格的概念,偏序集,a,b 最小上界 最大下界 e,f 最大下界 最小上界,注意：今后把a，b的最小上界（最大下界）称为元素a，b的最小上界（最大下界）。,a,b 最小上界 c 最大下界 无e,f 最大下界 d 最小上界 无,3,6-1 格的概念,共同的特性：在这些偏序集中，任何两个元素都有最小上界和最大下界。,4,一、格定义1 设是一个偏序集，如果A中任意两个元素都有最小上界和最大下界，则称为格。,复习,6-1 格的概念,5,6-1 格的概念,6,6-1 格的概念,7,6-1 格的概念,8,6-1 格的概念,例：a|b当且仅当a整除b,任意两元素a,b的最小上界：最小公倍数 最大下界：最大公约数,任意两元素S1,S2的最小上界：S1S2 最大下界：S1 S2,称为正整数格,9,6-1 格的概念,例：给定S=a，b，(S)=,a,b,a,b，那么，格如图所示。,10,6-1 格的概念,定义2 设是一个格，如果在A上定义两个二元运算和，使得对于a,bA，ab等于a和b的最小上界(LUB)，ab等于a和b的最大下界(GLB)，则称为由格所诱导的代数系统。二元运算和分别称为并运算和交运算。,复习,11,6-1 格的概念,例：1.2.3.,：最小公倍数（lcm）：最大公约数（gcd）,：集合的并：集合的交,，A:1,2,3,4,5 ab=max(a,b)ab=min(a,b),12,6-1 格的概念,4.设nI+，In=x|xI+，(x|n),为格，当n=20时，I20=1,2,4,5,10,20，如图：,xy=lcm(x,y),xy=gcd(x,y)则是由格所诱导的代数系统,13,6-1 格的概念,二、子格定义3 设是一个格，由格所诱导的代数系统为，设BA且B，如果A中的这两个运算和关于B是封闭的，则称是的子格。注意：与子群概念的异同,复习,14,6-1 格的概念,例：A=a,b,c,(A)=,a,b,c,a,b,b,c,c,a,a,b,c S1=a,b,c,a,b,b,c,b S2=a,c,a,c,S3=,a,c,a,b,b,c,c,a,a,b,c,是格，但不是 的子格因为a,b b,c=b S3,15,6-1 格的概念,注意：对于格，设B是A的非空子集，尽管必定是一个偏序集，然而不一定是格，即使是格，也不一定是的子格。,16,格的主要性质格的对偶原理:设是格，“”的逆关系“R”与 A组成的偏序集也是格。两者互为对偶。前者的GLB(最大下界），LUB（最小上界）恰好是后者的LUB，GLB。如有关于的有效命题P，(1)将“”换成“”，(2)“”换成“”，(3)“”换成“”，便能得到的有效命题P。反之亦然。,6-1 格的概念,17,6-1 格的概念,定理1 在一个格中，对于任意的a,b A，都有 a ab，b ab ab a，ab b,证明：因为ab 是a的一个上界 所以 a ab 同理 b ab 由对偶原理得 ab a，ab b,复习,18,6-1 格的概念,定理2 在一个格中，对于a,b,c,dA，如果有a b，c d，则：ac bdac b d,证明：因为ac a acc 而a b，cd 所以 acb acd 所以 ac b d,复习,19,6-1 格的概念,推论：(格的保序性）在一个格中，对于a,b,cA，如果有bc，则 ab acab ac证明：因为a a，bc 依据定理2可得。,复习,20,定理3 设是一个格，由格所诱导的代数系统为，则对于a,b,c,dA，有：（）交换律ab=baab=ba（）结合律（ab）c=a（bc）（a b）c=a（bc）（）幂等律aa=aaa=a（）吸收律a（ab）=a a（ab）=a,复习,6-1 格的概念,21,6-1 格的概念,结合律（ab）c=a（bc）证明：由定理1知 b bc a(bc)a a(bc)ab a(bc)又 c bc a(bc)（ab）c a（bc）类似地 a（bc）（ab）c（ab）c=a（bc）,22,6-1 格的概念,幂等律aa=a aa=a 证明：a aa 由自反性可知 a a aa a（aa是最小上界）aa=a 由对偶原理：aa=a,23,6-1 格的概念,吸收律 a（ab）=a,a（ab）=a 证明：由定理1知 a a（ab）又 a a，ab a a（ab）a a（ab）=a,24,6-1 格的概念,例：设是一个偏序集，N是自然数集，是“小于等于”关系，定义 ab=maxa,b（取大运算）ab=min a,b（取小运算）则是一个格。由此格诱导的代数系统为。则该代数系统的两个运算满足,交换律结合律等幂律吸收律,25,6-1 格的概念,1.交换性：任意两个数a和b的最大值（最小值）与b和a的最大值（最小值）是相等的。2.结合性：max(max(a,b),c)=max(a,max(b,c)都是三个数a,b,c中的最大值，所以是可结合的，min(min(a,b),c)=min(a,min(b,c)，说明是可结合的。3.幂等性：max(a,a)=min(a,a)=a4.吸收性：max(a,min(a,b)=a min(a,max(a,b)=a,26,6-1 格的概念,引理：设是一个代数系统，其中,都是二元运算且满足吸收性，则和都满足幂等性。,即要证，已知对于 a,bA 有a(ab)=a和a(ab)=a则:aa=a aa=a,复习,证明:a（ab）=a（吸收律）用（ab）代替b，得：a（a（ab）=a 又 a（ab）=a aa=a,27,6-1 格的概念,定理4 设是一个代数系统，其中,都是二元运算且满足交换性，结合性和吸收性，则A上存在偏序关系，使是一个格。,复习,证明思路：分四部分内容来证明：(1)定义二元关系：a b当且仅当(ab)=a(2)证明是偏序关系（证自反、反对称和传递）；(3)证明ab是a和b的最大下界（下确界）；(4)根据、满足交换律和吸收律，证明ab是a和b的最小上界（上确界）。,首先证明 是偏序关系（1）满足吸收律 满足幂等性(根据引理)即 a a=a a a 自反性,（2）设ab，则ab=a 再设ba，则ba=b 满足交换律 a=b 反对称性,（3）设ab，bc，则ab=a，bc=b ac=（ab）c=a（b c）=ab=a a c 传递性 即是偏序关系,证明:在A上定义二元关系为：对于a,bA，ab当且仅当(ab)=a,29,其次证明ab是a和b的最大下界 ab当且仅当ab=a,由于（ab）a=ab（ab）b=ab 所以 aba,abb 即 ab是a和b的下界,设cA，是a和b的任一下界，即：ca，cb ca=c cb=c c(ab)=(ca)b=cb=c c ab ab是a和b的最大下界,6-1 格的概念,30,即为：对于a,bA，ab当且仅当 ab=b,最后，根据交换性和吸收性，由ab=a 得（ab）b=a b 即 b=a b 反之由 a b=b 得 a（a b）=a b a=a b a=a b b=a b,在A上定义二元关系为：对于a,bA，ab当且仅当ab=a,类似的可证明 ab是 a和 b的最小上界 因此，是一个格,6-1 格的概念,31,6-1 格的概念,定理5 设是一个格，则对于a,b,cA，有：a（bc）（ab）（ac）（ab）（ac）a（bc）（分配不等式）,复习,32,a（bc）（ab）（ac）证明：a a b a ac a=aa（ab）（ac）（1）,又 bc b ab bc c ac bc=(bc)(bc)(ab)（ac）（2）a（bc）（ab）（ac）,利用对偶原理（ab）（ac）a（bc）,6-1 格的概念,33,6-1 格的概念,定理6 设是一个格，则对于a,bA，有 a b ab=a ab=b,证明：先证a b ab=a（1）a b，a a，a a b 又 ab a，则 ab=a（2）反之，假定 ab=a 则 a=ab b a b a b ab=a,同理：a b ab=b,复习,34,6-1 格的概念,定理7 设是一个格，对于a,b,cA，有 a c a(bc)(ab)c（模不等式）,证明：由定理6 a c ac=c 由定理5 a(bc)(ab)(ac)用c代替ac a(bc)(ab)c a c a(bc)(ab)c,复习,若 a(bc)(ab)c则 a a(bc)(ab)c c 即 a c a(bc)(ab)c ac ac a(bc)(ab)c,35,6-1 格的概念,推论：在格中，则对于 a,b,cA，必有：（ab）（ac）a（b（ac）a（b（ac）（ab）（ac）,复习,证明：(ab)(ac)(a(ac)(b(ac)（ab）（ac）a（b（ac）,a(b(ac)(ab)(a(ac)a(b(ac)(ab)(ac),36,定义:设和是两个格，由它们分别诱导的代数系统为和，若存在着一个从A1到A2的映射f，使得对于a,bA1，有 f(a 1 b)=f(a)2 f(b)f(a 1 b)=f(a)2 f(b)则称f为从到 的格同态。称是的格同态象。当f是双射时，称f为从到的格同构。,复习,6-1 格的概念,37,6-1 格的概念,定理8：(格同态的保序性）设f是和的格同态，则对x,yA1，如果x1y，必有f(x)2 f(y),证明：x 1 y x1y=x f(x1y)=f(x)=f(x)2 f(y)（同态公式）f(x)2 f(y),注意：定理8的逆命题是不一定成立的 格同态是保序的，但是保序的不一定是格同态,复习,38,但是，对于b,dS，有bd=a f(bd)=f(a)=S f(b)f(d)=b,d,e f(bd)f(b)f(d),例：设是一个格，其中S=a,b,c,d,e，如图 则也是一个格。作f：S(S)，对xS，使得 f(x)=y|yS，yx 有f(a)=S,f(b)=b,e,f(c)=c,e,fd=d,e,f(e)=e,当x,yS 且 xy 时，有f(x)f(y)f是保序的,6-1 格的概念,39,6-1 格的概念,定理9：设两个格和，f是从A1到A2的双射，则f是到的格同构，当且仅当对a,bA1，a1 b f(a)2 f(b)。,复习,证明：设f是到的格同构。由定理8知对a,bA1，若a1b，必有f(a)2f(b)反之，设f(a)2f(b)，则f(a)2f(b)=f(a1b)=f(a)f是双射 a1b=a 故a1 b,40,6-1 格的概念,设对a,bA1，a1b f(a)2 f(b)设a1b=c，则c1a，c1b，有 f(a1b)=f(c)，f(c)2 f(a)，f(c)2 f(b)f(c)2 f(a)2 f(b)设f(a)2 f(b)=f(d)，则 f(c)2 f(d)，f(d)2 f(a)，f(d)2 f(b)d1 a，d1 b d1 a1 b 即d1 c，f(d)2 f(c)f(c)=f(d)即f(a1b)=f(a)2f(b)类似地可证 f(a1b)=f(a)2f(b)因此，f是到的格同构,41,代数系统,第六章格和布尔代数 1 格的概念 2 分配格 3 有补格,42,6-2 分配格,定义1：设是由格所诱导的代数系统。如果对于任意的a,b,cA，满足：a（bc）=（ab）（ac）a（bc）=（ab）（ac）则称是分配格。,复习,43,讨论定义：(1)定义中的两式互为对偶式。(2)如为非分配格，则有下面的分配不等式：a(b c)(a b)(a c)(a b)(a c)a(b c)(定理6-1.5)以及模不等式：a ca(b c)(a b)c(定理6-1.7),6-2 分配格,44,例：S=a,b,c(S)=,a,b,c,a,b,b,c,c,a,a,b,c,对于P,Q,R(S),有P(QR)=(PQ)(PR)P(QR)=(PQ)(PR),则是一个分配格,6-2 分配格,45,b（cd）=b a=b（bc）（bd）=ee=e,c（bd）=ca=c（cb）（cd）=ed=d,注意：一个格是分配格的充要条件是该格中没有任何子格与这两个五元素格中的任一个同构。,复习,6-2 分配格,46,是格 的子格，但不是分配格,6-2 分配格,47,定理1：如果格中交对并是分配的，那么并对交也 是分配的，反之亦然。,证明：已知 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)即：并对交也是分配的。,复习,6-2 分配格,48,6-2 分配格,定理2：每个链均是分配格。,证明：设是链。则一定是格 对 a，b，cA若ab 或 ac，则 a(b c)=a(a b)(a c)=a 即：a(b c)=(a b)(a c)(2)若 ba 且 ca，则 a(b c)=b c，(a b)(a c)=b c 即：a(b c)=(a b)(a c)。,复习,49,定理3 设是一个分配格，对于a,b,cA，如果有ab=ac 和 ab=ac 成立，则必有b=c。,证明：（a b）c=（a c）c=c 而（a b）c=(a c)(b c)=(a b)(b c)=b（a c）=b（a b）=b 所以 b=c,复习,6-2 分配格,50,定义2 设是由格所诱导的代数系统。如果对于a,b,cA，当ba时，有 a(b c)=b(a c)则称为模格。也称戴德金格。,定理6-1.7：设是一个格，则对于a,b,cA，有 ac a（bc）（ab）c（模不等式）,(b c)a=b(c a),模律（模等式）,复习,6-2 分配格,51,定理4：格是模格，当且仅当A中不含有适合下述条件的元素u，v，w vu 且 uwvw,uw=vw,证明：(反证法)(1)存在这样三个元素u,v,w满足上式 u（wv）=u（wu）=u（uw）v=（vw）v=v 又 v不是模格。,6-2 分配格,52,（2）若不是模格，则存在 a,b,c，当ba时，有b（c a）（bc）a,令 v=b（c a），u=（bc）a，w=c uw=（bc）a）c=a（bc）c）=ac=（ac）c 又（ac）b（c a）（ac）c b（c a）c 即 uw vw,6-2 分配格,53,因此，若不是模格，就一定存在u，v，wA，使得vu 且 uwvw,uw=vw。所以，定理成立。,又v u vw uw 故 uw=vw 同理：uwvw,6-2 分配格,54,定理5 对于模格，若有三个元素a,b,c，使得上面三个式子的任何一个式子中把“”换成“=”成立，则另外两个式子中把“”换成“=”也必成立。,一般的格中，下式成立：（1）a(bc)(ab)(ac)（2）(ab)(ac)a(bc)（3）(ab)(bc)(ca)(ab)(bc)(ca),6-2 分配格,55,证明：若（1）中=成立，则由对偶性（2）的=也成立(ab)(b c)(ca)=(ac)b)(ca)=(ca)b)(ac)=(ab)(bc)(ca),若（3）中=成立，则有 a(bc)=a(ab)(ca)(bc)=a(ab)(bc)(ca)=a(bc)(ab)(ca)=(abc)(ab)(ca)=(ab)(ac),（1）a（b c）=（a b）（a c）（2）（a b）（a c）=a（b c）,6-2 分配格,56,定理6：分配格必定是模格。,证明：设是一个分配格，对于a,b,cA 若b a，则a b=b a(b c)=(a b)(a c)=b(a c)分配格是模格,6-2 分配格,57,注意：分配格一定是模格，但模格不一定是分配格。,对于 x，y，z0，1，a，b，c 若有yx,则只有y=0或x=1,若y=0，则x(y z)=x z y(x z)=x z,若x=1，则x(y z)=y z y(x z)=y z,所以，x(y z)=y(x z)即该格是模格，但不是分配格。,6-2 分配格,当ba时，有 a(bc)=b(ac),58,补充性质：（1）四个元素以下的格都是分配格。,6-2 分配格,59,（2）五个元素的格仅有两个格是非分配格。,6-2 分配格,60,代数系统,第六章格和布尔代数 1 格的概念 2 分配格 3 有补格,61,6-3 有补格,定义1 设是一个格，如果存在元素aA，对于xA，都有：ax，则称a为格的全下界，记格的全下界为0。,定义2 设是一个格，如果存在元素bA，对于xA，都有：xb，则称b为格的全上界，记格的全上界为1。,62,6-3 有补格,定理1、2 如果格有全上界（全下界），那么它是唯一的。,证明：（反证法）设有两个全上界a和b,a,bA 且 ab 则由定义ab，且ba，由“”的反对称性，a=b。,63,全下界：h全上界：a,定义3 如果一个格中存在全上界和全下界，则称该格为有界格。,例1：中,全下界：全上界：S,6-3 有补格,64,定理3 如果是有界格，全上界和全下界分别是1和0，则对任意元素aA，有：a1=1a=1，a1=1a=a a0=0a=a，a0=0a=0,证明:(1)(a1)A且1是全上界，a1 1 又 1 a1 a1=1 由交换律：1aa1=1(2)a a，a 1，a a a 1，即 a a 1 又 a1 a a1=a 由交换律：a1=1a=a,的幺元：0的零元：1,的幺元：1的零元：0,6-3 有补格,65,定义4 设是一个有界格，对于A中的一个元素a，如果存在bA，使得ab=1和ab=0，则称元素b是元素a的补元。,讨论定义：（1）和是可交换的，补元是相互的。（2）在有界格中，1和0互为补元；（3）A中一个元素的补元不一定是唯一的；,6-3 有补格,66,dc=1 dc=0 d和c互补 d的补元：c和ea的补元：e b的补元：无 c的补元：de的补元：a和d,6-3 有补格,dc=1 dc=0 d和c互补 d的补元：a的补元：b的补元：c的补元：e的补元：,67,定义5 在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。,注意：（1）在有补格中，每一个元素一定存在补元（不一定只有一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。（3）有补格不一定是分配格，分配格不一定是有补格。,6-3 有补格,68,(a),(b),(c),(d),下类有界格中哪个是有补格？,6-3 有补格,69,（a）,（b）,(a)是分配格，不是有补格。(b)是有补格，不是分配格。,6-3 有补格,70,定理4 在有界分配格中，若有一个元素有补元，则必是唯一的。,证明：设a有两个补元素b和c且bc，即有 ab=1 ab=0 ac=1 ac=0 ab=ac ab=ac 由定理6-2.3得 b=c 即 a的补元是唯一的。,6-3 有补格,71,定义6 一个格如果它既是有补格，又是分配格，则称它为有补分配格。我们把有补分配格中任意元素a的唯一补元记为a。,定义:一个有补分配格称为布尔格。,性质：有补分配格中，每个元素都存在唯一的补元。（定理4的推论）,6-3 有补格,72,定义：由布尔格，可以诱导一个包括交，并 和补运算的代数系统，称此代数 系统为布尔代数。,例：设S是一个非空有限集，是一个格，且是一个布尔格。由所诱导的代数系统为 是一个布尔代数。其中“,-”分别是集合的交、并、补运算。若S有n个元素，该布尔代数的哈斯图为n为立方体图。,6-4 布尔代数,73,6-4 布尔代数,74,定义：一个格如果它既是有补格，又是分配格，则它为有补分配格。我们把有补分配格中任一元素a的唯一补元记为a。讨论定义：(1)布尔格中，每个元素有唯一的补元。(2)我们可以定义L上的一个一元运算，称为补运算，记为“-”。,-,6-4 布尔代数,75,6-4 布尔代数,定义：由布尔格，可以诱导一个包括交，并和补运算的代数系统，称此代数系统为布尔代数。,例：设S是一个非空有限集，是一个格，且是一个布尔格。由所诱导的代数系统为 是一个布尔代数。其中“,-”分别是集合的交、并、补运算。,76,6-4 布尔代数,定理：对于布尔代数中任意两个元素a,b，必定有,77,6-4 布尔代数,定理：设是由有限布尔格所诱导的一个有限布尔代数，S是布尔格中的所有原子的集合，则和同构。,讨论：(1)当布尔代数的载体A的基数|A|是有限数时,则称之为有限布尔代数。(2)设是一个布尔代数，aA,如果a盖住0，则称元素a是该布尔代数的一个原子。(3)A中除0外的每个元素，都可唯一地表示成原子的并。,78,6-4 布尔代数,例：，其中S=a,b,c，在这个布尔代数中的元素分三种情况：（）界：全上界S，全下界；（）a,b,c单个元素集合的元素；（）二，三个元素作为集合的元素，但它们均可用单个元素的集合的元素来表述：a,b=ab,a,c=ac,b,c=bc,a,b,c=abc。,a,c,a,b,c,a,b,b,c,a,c,b,79,6-4 布尔代数,该定理可得以下两个推论：a)与同构，|p(S)|=2|s|所以，|B|=2|s|，故任一有限布尔代数载体的基数是2的幂。b)任一有限布尔代数和它的原子集合S构成的幂集集合代数同构，但后者又与任一基数相同的幂集集合代数同构，故具有相同载体基数的有限布尔代数都同构。,80,6-4 布尔代数,81,6-4 布尔代数,例：设A是一非空集合，(A)是A的幂集，可以验证，是个布尔代数,称此为集合代数，其中运算为,最小元,最大元A。S是命题公式的全体，则是一个布尔代数，称之为命题代数。其中运算为,，最小元是恒假公式0，最大元是恒真公式1。,82,6-4 布尔代数,因此，从逻辑观点看，布尔代数是命题演算系统。从集合论观点看，布尔代数是集合代数。从抽象代数的观点看，布尔代数是一个代数系统。,83,第三篇小结,通过本篇的学习应该达到以下基本要求：(1)给定集合与运算的解析表达式，写出该运算的运算表。(2)给定集合和运算，判别该集合对运算是否封闭。(3)给定二元运算，说明运算是否满足交换律、结合律、幂等律、分配律和吸收律。(4)给定集合S上的二元运算，求出该运算的幺元、零元、幂等元和所有可逆元素的逆元。(5)给定集合S和二元运算，能判定是否构成半群、独异点和群。,84,第三篇小结,(6)给定半群S和子集B，判定B是否为S的子半群；给定独异点V和子集B，判定B是否为V的子独异点，给定群G和子集H，判定H是否为G的子群。(7)求循环群的所有生成元。(8)给定代数系统V1=，V2=，其中“”和“”为二元运算，判定：S1 S2是否为V1到V2的同态映射。如果是，说明是否为单同态、满同态和同构，并求出同态象(V1)。(9)判别格、分配格、有界格、有补格和布尔格。求有界格的全上界、全下界和给定元素的补元。,85,