复旦大学：《离散数学——代数结构与数理逻辑》PPT课件_18/29

冷考试时间:5月8日(周三)950 地点:Z2107教室 答疑时间:5月7日13:30-16:00 地点:软件楼4楼密码与信息安全实验室

❖ 考试时间：5月8日(周三)9:50 ❖ 地点： Z2107教室 ❖ 答疑时间： 5月7日13:30-16:00 ❖ 地点：软件楼4楼密码与信息安全实验室

冷定理163如引理16.2所得之偏序集(L;s 为格。 冷定义164:[L∨2小]为一代数系统,为定 义在L上的二元运算当其满足L~L时, 称L为格。并称为积(或交),v为和(或并

❖ 定理16.3:如引理16.2所得之偏序集(L;≤) 为格。 ❖ 定义16.4: [L;,]为一代数系统,,为定 义在L上的二元运算,当其满足L1 ～L4时， 称L为格。并称为积(或交),为和(或并)

冷定义:[L∨,为格,若L中存在元素0, 使得对任意的x∈L有X0=x,则称0为v的 单位元,并称0是格的零元;若L中存在 元素1,使得对任意的x∈L有x1x则称 1为入的单位元,并称1是格的单位元 冷例:A的幂集格[P(A∨小] 冷群G的子群格[L(G)2~] C,,AI (z:s)是格,但既无单位元,又无零元

❖ 定义：[L;,]为格，若L中存在元素0， 使得对任意的xL有x0=x,则称0为的 单位元，并称0是格的零元；若L中存在 元素1，使得对任意的xL有x1=x,则称 1为的单位元，并称1是格的单位元。 ❖ 例：A的幂集格[P(A);,] ❖ 群G的子群格[L(G);,] ❖ [Z+ ;,] ❖ (Z;)是格，但既无单位元，又无零元

冷零元(单位元存在则必唯 冷定理:若格[;,]存在零元0和单位元1, 则0和1分别是L的最小元和最大元。 由于具有零元和单位元的格一定有最小 元和最大元,称为有界格

❖ 零元(单位元)存在则必唯一 ❖ 定理：若格[L;,]存在零元0和单位元1， 则0和1分别是L的最小元和最大元。 ❖ 由于具有零元和单位元的格一定有最小 元和最大元，称为有界格

冷定理16.4保序性):格[L:v,小任ab,c∈L, 当b≤c时有avb≤ac及ab≤a∧C。 冷定义16.5:LV小为格,T≠②,TL,T关于 封闭即a,b∈T则ab∈T,ab∈T时, 则称T为L的子格

❖ 定理16.4(保序性):格[L;,],任a,b,cL, 当b≤c时有ab≤ac及ab≤ac。 ❖ 定义16.5:[L;,]为格,T, TL,T关于 ,封闭(即a,bT则abT, abT)时, 则称T为L的子格

必须注意的是:当T为L的子格时,T一定 是格;但当TL,T关于L中的偏序关系≤为 格时,T不一定是L的子格。 冷例:S={1,2,3}S3={e,σ1σ2,可3,σ4,05} 为三次对称群,则(P(S3)c)是格,并且 是完全格。取T={e},H1H2H3H4,S3}其 中H={e,σ1};H2={e,c2};H3={e,o3} H4={e,o4,o5}都是S的子群,则T;g是 格但它不是P(S))的子格

❖ 必须注意的是：当T为L的子格时,T一定 是格; 但当TL,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 );)的子格

、格的同态与同构 定义166:设[L;V~与[s;+,]为两个格,如 果存在映射φ:LS使对任a,b∈L有: q(avb)=q(a)+o(b),o(a∧b=p(a)p(b,则 称q为L到S的同态欧射当p(L=S即q为 满射时又说与整S同态当q是一一对 应时说L与S同构若S=L时又分别称它 是自同态与自同构

三、格的同态与同构 ❖ 定义16.6:设[L;,]与[S;+,·]为两个格,如 果存在映射:L→S使对任a, bL有: (ab)=(a)+(b), (ab)=(a)·(b),则 称为L到S的同态映射,当(L)=S即为 满射时又说格L与格S同态;当是一一对 应时说格L与S同构;若S=L时又分别称它 是自同态与自同构

定理16.5:格[L;v,与格S;v,A同态,为 其同态映射,则q是保序映射,即对任a, b∈L当a≤b时,p(a)≤o(b) 保序映射不一定是同态映射

❖ 定理16.5:格[L;,]与格[S;,]同态,为 其同态映射,则是保序映射, 即对任a, bL,当a≤b时,(a)≤(b)。 ❖ 保序映射不一定是同态映射

冷定理166:q是格L到格S的一一对应,则p 是同构映射,当且仅当:对任何a,b∈L,a≤b 当且仅当q(a)≤p(b) 冷证明:(1)p是格L到格S的同构映射则由定 理16.5知q是保序映射因此对任何ab∈L, 当a≤b必有q(a)≤o(b) 冷若对任何a,b∈L,有q(a)≤o(b,则由≤定义 知qayp(b)=o(b 冷因为同构故有q(avb)=o(b) 且avb=b 因此由≤定义得asb

❖ 定理16.6:是格L到格S的一一对应, 则 是同构映射,当且仅当:对任何a,bL,a≤b 当且仅当(a)≤(b)。 ❖ 证明:(1)是格L到格S的同构映射,则由定 理16.5知是保序映射,因此对任何a,bL, 当a≤b,必有(a)≤(b). ❖ 若对任何a,bL,有(a)≤(b),则由≤定义 知(a)(b)=(b), ❖ 因为同构,故有(ab)=(b) ❖ 且ab=b, ❖ 因此由≤定义得a≤b

冷(2)φ是格L到格S的一一对应,且对任何 ab∈L2asb当且仅当q(a)≤p(b) 主要证明q是同态映射,即 冷q(avb=p(ap(b),q(ab)=(a)∧p(b) 分别证明p(ab)≤p(a)p(b) 令φ(a)∧p(b)≤paAb)

❖ (2) 是格L到格S的一一对应, 且对任何 a,bL,a≤b当且仅当(a)≤(b) ❖ 主要证明是同态映射,即 ❖ (ab)=(a)(b), (ab)=(a)(b) ❖ 分别证明(ab)≤(a)(b) ❖ (a)(b)≤(ab)