电子工业出版社：计算机类本科规划教材《离散数学》课程教学资源（PPT课件讲稿）第8章 格与布尔代数

第障格与布尔代数 定理8.1.7设<X121>和<2,≤2>是格,<X1V1,1和 <X2,V2,^2>是它们导出的代数系统。是格<X1,V1∧1>到格 <X2V2∧2>的格同态,则a,b∈X1,如果a≤b,必有 fa)≤f(b 证明:设a≤1b,根据定理84,a∧1b=a,由于f是格 <X1,V1^1>到格<X2,∨2^2>的格同态,所以fa)aA1b)= f(a)∧2/(b),再由定理814,f(a)≤f(b) 定理8.1.7说明格同态是保序的。一般地说,定理8.1.7 的逆并不成立。 【例83】设A=ab,c,de},<A,令是格,其哈斯图如图 8.3所示,R4)是A的幂集合,R=<xy>k∈R4)Ny∈P(4)∧ xgy是RA)上的偏序关系。<RA),R>也是格。作映射 A:A→P(4),定义为:Vx∈A,(x)=y∈A且y≤x},即: faa,b, c, de=A,bb, er, fc)cer, n Rd er fe)=e}。证明是保序的,但不是格同态

第8章 格与布尔代数 定理8.1.7 设X1 ,≼1 和X2 ,≼2 是格，X1 ,∨1 ,∧1 和 X2 ,∨2 ,∧2 是它们导出的代数系统。f是格X1 ,∨1 ,∧1 到格  X2 ,∨2 ,∧2  的格同态 ， 则 a,bX1 ， 如 果 a≼1 b ， 必 有 f(a)≼2 f(b) 证明：设a≼1 b，根据定理8.1.4，a∧1 b=a，由于 f 是格 X1 ,∨1 ,∧1 到格X2 ,∨2 ,∧2 的格同态，所以f(a)=f(a∧1 b)= f (a)∧2 f (b)，再由定理8.1.4，f (a)≼2 f (b)。 定理8.1.7说明格同态是保序的。一般地说，定理8.1.7 的逆并不成立。 【例8.3】设A=a,b,c,d,e，A,≼是格，其哈斯图如图 8.3所示，P(A)是A的幂集合，R =x,y|xP(A)∧yP (A)∧ xy是P(A)上的偏序关系。P(A), R 也是格。作映射 f：A→P (A)，定义为：xA，f(x)= y|yA且y≼x，即： f(a)=a,b,c,d,e=A ， f(b)=b,e ， f(c)=c,e ， f(d)=d,e ， f(e)=e。证明f是保序的，但不是格同态

第障格与布尔代数 证明:Va,b∈A,设a≤b, Vc∈fa),c≤a,由偏序关系 的传递性得c≤b,所以c∈fb), 即fa)c(b),于是f(a)Rfb) 故是保序的 对于bd∈A,b∨d=a b fb∨a)=(a)=A Ab)Uf(d b,suid er Rbdel f(bVd(b)Uf(d f不是格同态。 但是,当′是格同构时, 定理8.1.7的逆成立 图8.3

第 8 章 格与布尔代数 证明 ：  a , b  A ， 设 a ≼ b ，  c f( a ) ， c ≼ a ，由偏序关系 的传递性得 c ≼ b ，所以 c f( b ) ， 即f( a ) f( b ) ，于是f( a ) R f( b ) 。 故f是保序的 。 对于 b , d  A ， b ∨ d= a f( b ∨ d)=f( a)=A f( b ) ∪ f ( d)=  b , e  ∪  d , e  =  b , d , e  f( b ∨ d)≠f( b ) ∪ f ( d) f不是格同态 。 但是 ， 当f是格同构时 ， 定理 8 . 1 . 7的逆成立

第障格与布尔代数 定理8.1.8设<不≤1>和<X2,≤2是格,<1V1,∧1>和<2 22>是它们导出的代数系统。∫是x1到X2的双射,则∫是 <X12V1^1>到<X2,V2∧2>的格同构的充分必要条件是 va,b∈X1,a≤1b÷f(a)≤(b) 证明:设是<X1,V12∧1>到<X2,∨2∧2>的格同构,下证 va,b∈X1,a≤1b<)f(a)≤2f(b) 由定理817可知,vab∈X1,如果a≤b,必有f(a)≤人b) 设fa)≤(b),由定理8.1.4有a)≠a)∧3fb)a∧1b), 由于是双射,故a∧1b=a,所以a≤b 这就证明a≤1ba)≤2fb) 设va,b∈X1,a≤b<(a)≤2fb),下证∫是<12V1,1>到 <X2V22>的格同构 设a∧1b=C,则c≤a,C≤1b,fc)≠f(a∧1b),fc)≤3f(a) f(c)≤八b),故fc)≤f(a)∧2f(b)。 设(a)∧3fb)d),则有)≤a)∧(b)=d),即 f(c)≤f(d;还有f(d)≤3a)和(d)≤b)。所以有d≤a和≤b

第8章 格与布尔代数 定理8.1.8 设X1 ,≼1 和X2 ,≼2 是格，X1 ,∨1 ,∧1 和X2 , ∨2 ,∧2 是它们导出的代数系统。f 是X1到X2的双射，则 f 是 X1 ,∨1 ,∧1  到 X2 ,∨2 ,∧2  的格同构的充分必要条件是 a,bX1，a≼1 bf(a)≼2 f(b) 证明：设f是X1 ,∨1 ,∧1 到X2 ,∨2 ,∧2 的格同构，下证 a,bX1，a≼1 bf(a)≼2 f(b) 由定理8.1.7可知，a,bX1，如果a≼1 b，必有f(a)≼2 f(b) 设f(a)≼2 f(b)，由定理8.1.4有f(a)=f(a)∧2 f(b)=f(a∧1 b)， 由于f是双射，故a∧1 b=a，所以a≼1 b 这就证明a≼1 bf(a)≼2 f(b) 设a,bX1，a≼1 bf(a)≼2 f(b)，下证 f 是X1 ,∨1 ,∧1 到 X2 ,∨2 ,∧2 的格同构。 设a∧1 b=c，则c≼1 a，c≼1 b，f(c)=f(a∧1 b)，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(a)∧2 f(b)=f(d)，即 f(c)≼2 f(d)；还有f(d)≼2 f(a)和f(d)≼2 f(b)。所以有d≼1 a和d≼1 b