复旦大学：《离散数学 Discrete Mathematics（下）》英文课件（赵一鸣）18/32

冷考试时间:5月6日(周五)950 地点:Z2108教室

❖ 考试时间：5月6日(周五)9:50 ❖ 地点： Z2108教室

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

❖ 定理17.6:是格L到格S的一一对应, 则是 同构映射,当且仅当:对任何a,bL,a≤b当且 仅当(a)≤(b)。 ❖ 证明:(1)是格L到格S的同构映射,对任何 a,bL,a≤b当且仅当(a)≤(b) ❖ 由定理17.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)

§2有补格及分配格 一、有补格 定义178:一个具有最大元1和最小元0的格 Lv,称为有界格。 冷定理178:[Lv~]为有界格,则任a∈L 有:av1=1;a0=0;a1a;av0=a

§2 有补格及分配格 ❖ 一、有补格 ❖ 定义17.8:一个具有最大元1和最小元0的格 [L;,]称为有界格。 ❖ 定 理 1 7 . 8 : [ L;,] 为 有 界 格 , 则 任 aL 有:a1=1; a0=0;a1=a;a0=a

冷定义178:[Lv,小为有界格对a∈L如果 存在b∈L,使avb=1ab=0,则称b为a的补 元,记b为a。若L中的每个元有补元,则 称L为有补格。 冷例:S=1,2,34,5},其偏序关系由下图所示, 则S是有界格,且为有补格

❖ 定义17.8:[L;,]为有界格,对aL,如果 存在bL,使ab=1,ab=0,则称b为a的补 元,记b为a'。若L中的每个元有补元, 则 称L为有补格。 ❖ 例:S={1,2,3,4,5},其偏序关系由下图所示, 则S是有界格,且为有补格

由此可知补元不唯一 今二、分配格 冷定理(习题179):对任意格成立分配不等 式,即格[LV~中任a,bc∈L,有: (1)a(b∧c)≤(avb)∧avC) 冷(2)(aAby(a∧c≤a~(bvc)。 但等式不一定成立

❖ 由此可知补元不唯一. ❖ 二、分配格 ❖ 定理(习题17.9)：对任意格成立分配不等 式, 即格[L;,]中任a,b,cL,有: ❖ (1)a(bc)≤(ab)(ac); ❖ (2)(ab)(ac)≤a(bc)。 ❖ 但等式不一定成立

例:如下图所示的格分配等式不成立 Ma

❖ 例:如下图所示的格分配等式不成立

例:S,[P(S);U,∩]满足分配等式。 分配格 冷定义179:[L;v~]为格,当对其任意元 ab,c∈L成立分配律,即 (1)av(bAc=avb)aavc) 冷(2)(a∧b)v(a/c)=a∧(bvc)。 则称该格为分配格

❖ 例：S,[P(S);∪,∩]满足分配等式。 ❖ 分配格 ❖ 定义17.9:[L;,]为格,当对其任意元 a,b,cL成立分配律,即 ❖ (1)a(bc)=(ab)(ac); ❖ (2)(ab)(ac)=a(bc)。 ❖ 则称该格为分配格

冷定理:设S是分配格,ax,y∈S,若 a∧x=ay,且aNx=awy,则x=y

❖ 定理：设S是分配格，a,x,yS,若 ax=ay,且ax=ay，则x=y。 ❖ L1 ～L4

a 0 N5 上述两个图所代表的格都不是分配格 冷可以证明对于任意的格,若|≤4则一定 是分配格。而所有非分配格,一定含有 子格是与M或N同构的

❖ 上述两个图所代表的格都不是分配格 ❖ 可以证明对于任意的格，若|L|4,则一定 是分配格。而所有非分配格，一定含有 子格是与M5或N5同构的