Download presentation
Presentation is loading. Please wait.
1
考试时间：5月8日(周三)9:50 地点： Z2107教室 答疑时间： 5月7日13:30-16:00 地点：软件楼4楼密码与信息安全实验室
2
定理16.3:如引理16.2所得之偏序集(L;≤)为格。
定义16.4: [L;,]为一代数系统,,为定义在L上的二元运算,当其满足L1～L4时，称L为格。并称为积(或交),为和(或并)
3
定义：[L;,]为格，若L中存在元素0，使得对任意的xL有x0=x,则称0为的单位元，并称0是格的零元；若L中存在元素1，使得对任意的xL有x1=x,则称1为的单位元，并称1是格的单位元。 例：A的幂集格[P(A);,] 群G的子群格[L(G);,] [Z+;,] (Z;)是格，但既无单位元，又无零元。
![定义：[L;,]为格，若L中存在元素0，使得对任意的xL有x0=x,则称0为的单位元，并称0是格的零元；若L中存在元素1，使得对任意的xL有x1=x,则称1为的单位元，并称1是格的单位元。](http://slidesplayer.com/slide/16758634/97/images/3/%E5%AE%9A%E4%B9%89%EF%BC%9A%5BL%3B%EF%83%9A%2C%EF%83%99%5D%E4%B8%BA%E6%A0%BC%EF%BC%8C%E8%8B%A5L%E4%B8%AD%E5%AD%98%E5%9C%A8%E5%85%83%E7%B4%A00%EF%BC%8C%E4%BD%BF%E5%BE%97%E5%AF%B9%E4%BB%BB%E6%84%8F%E7%9A%84x%EF%83%8EL%E6%9C%89x%EF%83%9A0%3Dx%2C%E5%88%99%E7%A7%B00%E4%B8%BA%EF%83%9A%E7%9A%84%E5%8D%95%E4%BD%8D%E5%85%83%EF%BC%8C%E5%B9%B6%E7%A7%B00%E6%98%AF%E6%A0%BC%E7%9A%84%E9%9B%B6%E5%85%83%EF%BC%9B%E8%8B%A5L%E4%B8%AD%E5%AD%98%E5%9C%A8%E5%85%83%E7%B4%A01%EF%BC%8C%E4%BD%BF%E5%BE%97%E5%AF%B9%E4%BB%BB%E6%84%8F%E7%9A%84x%EF%83%8EL%E6%9C%89x%EF%83%991%3Dx%2C%E5%88%99%E7%A7%B01%E4%B8%BA%EF%83%99%E7%9A%84%E5%8D%95%E4%BD%8D%E5%85%83%EF%BC%8C%E5%B9%B6%E7%A7%B01%E6%98%AF%E6%A0%BC%E7%9A%84%E5%8D%95%E4%BD%8D%E5%85%83%E3%80%82.jpg "例：A的幂集格[P(A);,] 群G的子群格[L(G);,] [Z+;,] (Z;)是格，但既无单位元，又无零元。")
4
零元(单位元)存在则必唯一 定理：若格[L;,]存在零元0和单位元1，则0和1分别是L的最小元和最大元。 由于具有零元和单位元的格一定有最小元和最大元，称为有界格。
![零元(单位元)存在则必唯一 定理：若格[L;,]存在零元0和单位元1，则0和1分别是L的最小元和最大元。 由于具有零元和单位元的格一定有最小元和最大元，称为有界格。](http://slidesplayer.com/slide/16758634/97/images/4/%E9%9B%B6%E5%85%83%28%E5%8D%95%E4%BD%8D%E5%85%83%29%E5%AD%98%E5%9C%A8%E5%88%99%E5%BF%85%E5%94%AF%E4%B8%80+%E5%AE%9A%E7%90%86%EF%BC%9A%E8%8B%A5%E6%A0%BC%5BL%3B%EF%83%9A%2C%EF%83%99%5D%E5%AD%98%E5%9C%A8%E9%9B%B6%E5%85%830%E5%92%8C%E5%8D%95%E4%BD%8D%E5%85%831%EF%BC%8C%E5%88%990%E5%92%8C1%E5%88%86%E5%88%AB%E6%98%AFL%E7%9A%84%E6%9C%80%E5%B0%8F%E5%85%83%E5%92%8C%E6%9C%80%E5%A4%A7%E5%85%83%E3%80%82+%E7%94%B1%E4%BA%8E%E5%85%B7%E6%9C%89%E9%9B%B6%E5%85%83%E5%92%8C%E5%8D%95%E4%BD%8D%E5%85%83%E7%9A%84%E6%A0%BC%E4%B8%80%E5%AE%9A%E6%9C%89%E6%9C%80%E5%B0%8F%E5%85%83%E5%92%8C%E6%9C%80%E5%A4%A7%E5%85%83%EF%BC%8C%E7%A7%B0%E4%B8%BA%E6%9C%89%E7%95%8C%E6%A0%BC%E3%80%82.jpg "零元(单位元)存在则必唯一 定理：若格[L;,]存在零元0和单位元1，则0和1分别是L的最小元和最大元。 由于具有零元和单位元的格一定有最小元和最大元，称为有界格。")
5
定理16.4(保序性):格[L;,],任a,b,cL,当b≤c时有ab≤ac及ab≤ac。
定义16.5:[L;,]为格,T, TL,T关于,封闭(即a,bT则abT, abT)时,则称T为L的子格。
![定理16.4(保序性):格[L;,],任a,b,cL,当b≤c时有ab≤ac及ab≤ac。](http://slidesplayer.com/slide/16758634/97/images/5/%E5%AE%9A%E7%90%8616.4%28%E4%BF%9D%E5%BA%8F%E6%80%A7%29%3A%E6%A0%BC%5BL%3B%EF%83%9A%2C%EF%83%99%5D%2C%E4%BB%BBa%2Cb%2Cc%EF%83%8EL%2C%E5%BD%93b%E2%89%A4c%E6%97%B6%E6%9C%89a%EF%83%9Ab%E2%89%A4a%EF%83%9Ac%E5%8F%8Aa%EF%83%99b%E2%89%A4a%EF%83%99c%E3%80%82.jpg "定义16.5:[L;,]为格,T, TL,T关于,封闭(即a,bT则abT, abT)时,则称T为L的子格。")
6
必须注意的是：当T为L的子格时,T一定是格; 但当TL,T关于L中的偏序关系≤为格时,T不一定是L的子格。
例：S={1,2,3},S3={e,1, 2, 3, 4, 5}为三次对称群，则(P(S3);)是格，并且是完全格。取T={{e}, H1,H2,H3,H4,S3},其中H1={e, 1}; H2={e, 2}; H3={e, 3}; H4={e, 4, 5}都是S3的子群，则(T; )是格,但它不是(P(S3);)的子格。
7
三、格的同态与同构 定义16.6:设[L;,]与[S;+,·]为两个格,如果存在映射:L→S使对任a, bL有: (ab)=(a)+(b), (ab)=(a)·(b),则称为L到S的同态映射,当(L)=S即为满射时又说格L与格S同态;当是一一对应时说格L与S同构;若S=L时又分别称它是自同态与自同构。
8
定理16.5:格[L;,]与格[S;,]同态,为其同态映射,则是保序映射, 即对任a, bL,当a≤b时,(a)≤(b)。
保序映射不一定是同态映射
![定理16.5:格[L;,]与格[S;,]同态,为其同态映射,则是保序映射, 即对任a, bL,当a≤b时,(a)≤(b)。](http://slidesplayer.com/slide/16758634/97/images/8/%E5%AE%9A%E7%90%8616.5%3A%E6%A0%BC%5BL%3B%EF%83%9A%2C%EF%83%99%5D%E4%B8%8E%E6%A0%BC%5BS%3B%EF%83%9A%2C%EF%83%99%5D%E5%90%8C%E6%80%81%2C%EF%81%AA%E4%B8%BA%E5%85%B6%E5%90%8C%E6%80%81%E6%98%A0%E5%B0%84%2C%E5%88%99%EF%81%AA%E6%98%AF%E4%BF%9D%E5%BA%8F%E6%98%A0%E5%B0%84%2C+%E5%8D%B3%E5%AF%B9%E4%BB%BBa%2C+b%EF%83%8EL%2C%E5%BD%93a%E2%89%A4b%E6%97%B6%2C%EF%81%AA%28a%29%E2%89%A4%EF%81%AA%28b%29%E3%80%82.jpg "保序映射不一定是同态映射.")
9
定理16.6:是格L到格S的一一对应, 则是同构映射,当且仅当:对任何a,bL,a≤b当且仅当(a)≤(b)。
若对任何a,bL,有(a)≤(b),则由≤定义知(a)(b)=(b), 因为同构,故有(ab)=(b) 且ab=b, 因此由≤定义得a≤b
10
(2) 是格L到格S的一一对应, 且对任何a,bL,a≤b当且仅当(a)≤(b)
主要证明是同态映射,即 (ab)=(a)(b), (ab)=(a)(b) 分别证明(ab)≤(a)(b) (a)(b)≤(ab)
11
§2 有补格及分配格 一、有补格 定义16.7:一个具有最大元1和最小元0的格[L;,]称为有界格。
定理16.8:[L;,]为有界格, 则任aL有:a1=1; a0=0;a1=a;a0=a。
![§2 有补格及分配格 一、有补格 定义16.7:一个具有最大元1和最小元0的格[L;,]称为有界格。](http://slidesplayer.com/slide/16758634/97/images/11/%C2%A72+%E6%9C%89%E8%A1%A5%E6%A0%BC%E5%8F%8A%E5%88%86%E9%85%8D%E6%A0%BC+%E4%B8%80%E3%80%81%E6%9C%89%E8%A1%A5%E6%A0%BC+%E5%AE%9A%E4%B9%8916.7%3A%E4%B8%80%E4%B8%AA%E5%85%B7%E6%9C%89%E6%9C%80%E5%A4%A7%E5%85%831%E5%92%8C%E6%9C%80%E5%B0%8F%E5%85%830%E7%9A%84%E6%A0%BC%5BL%3B%EF%83%9A%2C%EF%83%99%5D%E7%A7%B0%E4%B8%BA%E6%9C%89%E7%95%8C%E6%A0%BC%E3%80%82.jpg "定理16.8:[L;,]为有界格, 则任aL有:a1=1; a0=0;a1=a;a0=a。")
12
定义16.8:[L;,]为有界格,对aL,如果存在bL,使ab=1,ab=0,则称b为a的补元,记b为a'。若L中的每个元有补元, 则称L为有补格。
例:S={1,2,3,4,5},其偏序关系由下图所示,则S是有界格,且为有补格.
![定义16.8:[L;,]为有界格,对aL,如果存在bL,使ab=1,ab=0,则称b为a的补元,记b为a 。若L中的每个元有补元, 则称L为有补格。](http://slidesplayer.com/slide/16758634/97/images/12/%E5%AE%9A%E4%B9%8916.8%3A%5BL%3B%EF%83%9A%2C%EF%83%99%5D%E4%B8%BA%E6%9C%89%E7%95%8C%E6%A0%BC%2C%E5%AF%B9a%EF%83%8EL%2C%E5%A6%82%E6%9E%9C%E5%AD%98%E5%9C%A8b%EF%83%8EL%2C%E4%BD%BFa%EF%83%9Ab%3D1%2Ca%EF%83%99b%3D0%2C%E5%88%99%E7%A7%B0b%E4%B8%BAa%E7%9A%84%E8%A1%A5%E5%85%83%2C%E8%AE%B0b%E4%B8%BAa+%E3%80%82%E8%8B%A5L%E4%B8%AD%E7%9A%84%E6%AF%8F%E4%B8%AA%E5%85%83%E6%9C%89%E8%A1%A5%E5%85%83%2C+%E5%88%99%E7%A7%B0L%E4%B8%BA%E6%9C%89%E8%A1%A5%E6%A0%BC%E3%80%82.jpg "例:S={1,2,3,4,5},其偏序关系由下图所示,则S是有界格,且为有补格.")
13
由此可知补元不唯一. 二、分配格 定理(习题16.9)：对任意格成立分配不等式, 即格[L;,]中任a,b,cL,有: (1)a(bc)≤(ab)(ac); (2)(ab)(ac)≤a(bc)。 但等式不一定成立。
![由此可知补元不唯一. 二、分配格. 定理(习题16.9)：对任意格成立分配不等式, 即格[L;,]中任a,b,cL,有: (1)a(bc)≤(ab)(ac); (2)(ab)(ac)≤a(bc)。](http://slidesplayer.com/slide/16758634/97/images/13/%E7%94%B1%E6%AD%A4%E5%8F%AF%E7%9F%A5%E8%A1%A5%E5%85%83%E4%B8%8D%E5%94%AF%E4%B8%80.+%E4%BA%8C%E3%80%81%E5%88%86%E9%85%8D%E6%A0%BC.+%E5%AE%9A%E7%90%86%28%E4%B9%A0%E9%A2%9816.9%29%EF%BC%9A%E5%AF%B9%E4%BB%BB%E6%84%8F%E6%A0%BC%E6%88%90%E7%AB%8B%E5%88%86%E9%85%8D%E4%B8%8D%E7%AD%89%E5%BC%8F%2C+%E5%8D%B3%E6%A0%BC%5BL%3B%EF%83%9A%2C%EF%83%99%5D%E4%B8%AD%E4%BB%BBa%2Cb%2Cc%EF%83%8EL%2C%E6%9C%89%3A+%281%29a%EF%83%9A%28b%EF%83%99c%29%E2%89%A4%28a%EF%83%9Ab%29%EF%83%99%28a%EF%83%9Ac%29%3B+%282%29%28a%EF%83%99b%29%EF%83%9A%28a%EF%83%99c%29%E2%89%A4a%EF%83%99%28b%EF%83%9Ac%29%E3%80%82.jpg "但等式不一定成立。")
14
例:如下图所示的格分配等式不成立.
15
例：S,[P(S);∪,∩]满足分配等式。
分配格 定义16.9:[L;,]为格,当对其任意元a,b,cL成立分配律,即 (1)a(bc)=(ab)(ac); (2)(ab)(ac)=a(bc)。 则称该格为分配格。
![例：S,[P(S);∪,∩]满足分配等式。](http://slidesplayer.com/slide/16758634/97/images/15/%E4%BE%8B%EF%BC%9AS%EF%82%B9%EF%83%86%2C%5BP%28S%29%3B%E2%88%AA%2C%E2%88%A9%5D%E6%BB%A1%E8%B6%B3%E5%88%86%E9%85%8D%E7%AD%89%E5%BC%8F%E3%80%82.jpg "分配格. 定义16.9:[L;,]为格,当对其任意元a,b,cL成立分配律,即. (1)a(bc)=(ab)(ac); (2)(ab)(ac)=a(bc)。 则称该格为分配格。")
16
定理：设S是分配格，a,x,yS,若ax=ay,且ax=ay，则x=y。
L1～L4
17
上述两个图所代表的格都不是分配格 可以证明对于任意的格，若|L|4,则一定是分配格。而所有非分配格，一定含有子格是与M5或N5同构的。
18
定理16.9:[L;,]为任意格, 则下述条件等价:
(1)对任意a,b,cL,有 a(bc)=(ab)(ac) (2)对任意a,b,cL,有 a(bc)=(ab)(ac) (3)对任意a,b,cL,有 (ab)(ac)(bc)=(ab)(ac)(bc) (4)不含与M5或N5同构的子格。
![定理16.9:[L;,]为任意格, 则下述条件等价:](http://slidesplayer.com/slide/16758634/97/images/18/%E5%AE%9A%E7%90%8616.9%3A%5BL%3B%EF%83%9A%2C%EF%83%99%5D%E4%B8%BA%E4%BB%BB%E6%84%8F%E6%A0%BC%2C+%E5%88%99%E4%B8%8B%E8%BF%B0%E6%9D%A1%E4%BB%B6%E7%AD%89%E4%BB%B7%3A.jpg "(1)对任意a,b,cL,有. a(bc)=(ab)(ac) (2)对任意a,b,cL,有. a(bc)=(ab)(ac) (3)对任意a,b,cL,有. (ab)(ac)(bc)=(ab)(ac)(bc) (4)不含与M5或N5同构的子格。")
19
(1) (2) (1),(2)(3) 左=((ab)(bc))(ac) =((a(bc))(b(bc)))(ca) =((a(bc))b)(ca) =((ab)(ac))b)(ca) =((b(ab))(ac)))(ca) =(b(ac))(ca)
20
(3)(1) 1.c≤a时,必有 a(bc)=?(ab)(ac)=(ab)c 2.一般情况 利用c≤a时的结论 (1),(2)(4) (4)(1) 反证,若L不是分配格,推出存在与M5或N5同构的子格 约定:a≤b,且ab,记为a<b 基本设想是在L中构造5个元素的子格,使其与M5或N5同构
21
{a,e,d,b,0}是M5
22
分两种情况 1.存在a,b,cL,当c≤a时,有 (ab)c=(ab)(ac)<a(bc) u=a(bc),v=(ab)c,v<u vb=ub vb=ub u,v,b,vb,ub, 2.对任意a,b,cL,当c≤a时,有 (ab)c=(ab)(ac)=a(bc) 关键是构造M5,N5 由此定理可以判定一个格是否为分配格.
23
作业P220:10, 14,15,16,17, 18(2)(3),27,28? 考试时间：5月8日(周三)9:50 地点： Z2107教室
答疑时间： 5月7日13:30-16:00 地点：软件楼4楼密码与信息安全实验室
24
L1幂等律:aa=a,aa=a; L2交换律:ab=ba,ab=ba; L3结合律:a(bc)=(ab)c, a(bc)=(ab)c; L4吸收律:a(ab)=a, a(ab)=a。
25
定理17.5:格[L;,]与格[S;,]同态,为其同态映射,则是保序映射, 即对任a, bL,当a≤b时,(a)≤(b)。
![定理17.5:格[L;,]与格[S;,]同态,为其同态映射,则是保序映射, 即对任a, bL,当a≤b时,(a)≤(b)。](http://slidesplayer.com/slide/16758634/97/images/25/%E5%AE%9A%E7%90%8617.5%3A%E6%A0%BC%5BL%3B%EF%83%9A%2C%EF%83%99%5D%E4%B8%8E%E6%A0%BC%5BS%3B%EF%83%9A%2C%EF%83%99%5D%E5%90%8C%E6%80%81%2C%EF%81%AA%E4%B8%BA%E5%85%B6%E5%90%8C%E6%80%81%E6%98%A0%E5%B0%84%2C%E5%88%99%EF%81%AA%E6%98%AF%E4%BF%9D%E5%BA%8F%E6%98%A0%E5%B0%84%2C+%E5%8D%B3%E5%AF%B9%E4%BB%BBa%2C+b%EF%83%8EL%2C%E5%BD%93a%E2%89%A4b%E6%97%B6%2C%EF%81%AA%28a%29%E2%89%A4%EF%81%AA%28b%29%E3%80%82.jpg "定理17.5:格[L;,]与格[S;,]同态,为其同态映射,则是保序映射, 即对任a, bL,当a≤b时,(a)≤(b)。")
Similar presentations
![[S;*]是一个代数系统,*为定义在S上的二元运算,若满足:](/62/11553398/big_thumb.jpg "[S;*]是一个代数系统,*为定义在S上的二元运算,若满足:>")
