ch 19 1定义性质同态直积

第三编代数结构1第十九章格与布尔代数19.1格的定义与性质19.2子格、格同态与格的直积19.3特殊的格19.4布尔代数第三编代数结构219.1格的定义和性质格的定义格的基本性质对偶原理格中的基本等式与不等式格中的基本等价条件格中的算律格的代数定义格中的不等式第三编代数结构3格的定义格的偏序集定义：

<S,≼>,S的任何二元子集都有最大下界、最小上界.

求最大下界、最小上界构成格中的运算∧,∨格<L,≼>与导出的代数系统<L,∧,∨>的对应关系格的实例：

n的正因子格Sn

幂集格P(B)

子群格L(G)第三编代数结构4格的实例例1

设n是正整数，Sn是n的正因子的集合.D为整除关系，则偏序集<Sn,D>构成格.∀x,y∈Sn，x∨y

是lcm(x,y)，即x

与y

的最小公倍数.x∧y

是gcd(x,y)，即x

与y

的最大公约数.下图给出了格<S8,D>，<S6,D>和<S30,D>.第三编代数结构5格的实例（续）(b)abcdfe(a)acbdedacbefgfeabcd(c)(d)例2

判断下列偏序集是否构成格，并说明理由.(1)<Z,≤>，其中Z是整数集，≤为小于或等于关系.(2)偏序集的哈斯图分别在下图给出.(1)是格.(2)都不是格.第三编代数结构6格的性质——对偶原理对偶命题：设P是由格中元素,≼,≽,=,∧,∨等表示的命题，若将P中的≼,≽,∧,∨分别替换成≽,≼,∨,∧得到的命题称为P的对偶命题，记作P*.实例：

P:a∧b=b∧a P*：a∨b=b∨a性质：(P*)*=P.对偶原理：如果P对于一切格为真，则P*也对一切格为真.第三编代数结构7格的性质（续）格中的基本不等式和等式

a≼a a≼b,b≼c⇒a≼c a∧b≼a,a∧b≼b a≼a∨b,b≼a∨b a≼b,a≼c⇒a≼b∧c a≽b,a≽c⇒a≽b∨c a≼b,b≼a⇒a=b第三编代数结构8格的性质（续）格中的基本等价条件a≼b⇔a∧b=a⇔a∨b=b①②③证：①⇒②

a≼a,a≼b⇒a≼a∧ba∧b≼a②⇒③b≼a∨ba=a∧b≼b,b≼b⇒a∨b≼b③⇒①a≼a∨b=b⇒a∨b=b⇒a∧b=a第三编代数结构9格的性质（续）格中交换律、结合律、幂等律、吸收律证(1)a∧b是{a,b}的下界，

b∧a是{b,a}的下界,{a,b}={b,a}⇒a∧b=b∧a

结合律

(2)(a∧b)∧c≼a∧b≼a(a∧b)∧c≼a∧b≼b(a∧b)∧c≼c(a∧b)∧c≼b∧c(a∧b)∧c≼a∧(b∧c)同理，a∧(b∧c)≼(a∧b)∧c所以，a∧(b∧c)=(a∧b)∧c第三编代数结构10格的代数定义引理

<S,*,◦>是具有两个二元运算的代数系统.

如果*,◦运算满足交换、结合、吸收律，则(1)*,◦满足幂等律

(2)a*b=a⇔a◦b=b证(1)a*a=a*(a◦(a*a))=a

同理，a◦a=a(2)“⇐”a*b=a*(a◦b)=a“⇒”a◦b=(a*b)◦b=b第三编代数结构11格的代数定义（续）定理设<S,*,◦>是具有两个二元运算的代数系统，若*和◦运算满足交换、结合、吸收律，则可以适当定义S上偏序≼，使得<S,≼>构成格，且<S,≼>导出的代数系统就是<S,*,◦>.证明思路

(1)利用运算◦或*定义S上的二元关系R(2)证明R为S上的偏序

(3)证明对于S中任意两个元素x,yx∨y=x◦y,x∧y=x*y<S,∧,∨>构成格第三编代数结构12定理的证明证

(1)定义二元关系R,aRb⇔a◦b=b,(2)R为偏序：

a◦a=a

aRaaRb,bRa

a◦b=b,

b◦a=a

a=baRb,bRc

a◦b=b,

b◦c=c

a◦c=a◦(b◦c)=(a◦b)◦c=b◦c=c

aRc将R记作≼第三编代数结构13定理的证明（续）(3)a◦b为{a,b}的上界a◦(a◦b)=(a◦a)◦b=a◦b

a

≼a◦bb◦(a◦b)=a◦(b◦b)=a◦b

b

≼a◦ba◦b最小上界：假设c为上界，则(a◦b)◦c=a◦(b◦c)=a◦c=c

a◦b≼c同理，a*b是{a,b}的最大下界.第三编代数结构14格的代数定义等价定义设<L,∧,∨>是具有两个二元运算的代数系统，如果∧,∨满足交换、结合、吸收律，则称<L,∧,∨>是格.实例：

<Sn,gcd,lcm>∀x,y∈Sn,gcd(x,y)=gcd(y,x),lcm(x,y)=lcm(y,x)gcd(x,gcd(y,z))=gcd(gcd(x,y),z)lcm(x,lcm(y,z))=lcm(lcm(x,y),z)gcd(x,lcm(x,y))=x,lcm(x,gcd(x,y))=xx|y⇔lcm(x,y)=y<Sn,|>与<Sn,gcd,lcm>是同一个格第三编代数结构15格的性质（续）格的不等式（1）保序不等式

a≼b,c≼d⇒a∧c≼b∧d,a∨c≼b∨d（2）分配不等式

a∨(b∧c)≼(a∨b)∧(a∨c),a∧(b∨c)≽(a∧b)∨(a∧c)（3）模不等式

a≼b⇔a∨(c∧b)≼(a∨c)∧b思考：如何证明以上不等式？第三编代数结构16不满足分配律的格钻石格：b∨(c∧d)=b∨a=b(b∨c)∧(b∨d)=e∧e=e思考：指出五角格不满足分配律的元素abcde钻石格五角格abcde第三编代数结构1719.2子格、格同态、格的直积子格子格定义子格判别格的同态与同构格同态定义格同态的性质完备格格的直积第三编代数结构18格的子格L的子格：L的非空子集S，且S关于L中∧和∨运算封闭.注意：子格元素在原来格中求最大下界和最小上界.实例：子群格L(G)是格，但一定不是P(G)的子格.

例如Klein四元群G={e,a,b,c},L(G)={<e>,<a>,<b>,<c>,G}P(G)={∅,<e>,{a},{b},{c},<a>,<b>,<c>,{a,b},{a,c},{b,c},{a,b,c},{a,b,e},{a,c,e},{b,c,e},G}第三编代数结构19格的同态定义设L1和L2是格,f:L1→L2,∀x,y∈L1，有

f(x∧y)=f(x)∧f(y),f(x∨y)=f(x)∨f(y)

则称f为L1到L2的同态.实例：L1=<{1,2,3,6},|>,L2=<{0,1},≤>f(1)=f(2)=0,f(3)=f(6)=1f为L1到L2的同态.123601第三编代数结构20格同态的性质格同态具有保序性定理1

f是格L1

到L2

的同态，则∀a,b∈L1,a≼b⇒f(a)≼f(b)证：a≼b⇒a∧b=a⇒f(a∧b)=f(a)⇒f(a)∧f(b)=f(a)⇒f(a)≼f(b)注意：f(a)≼f(b)不一定推出a≼b.思考反例.第三编代数结构21格同态的性质（续）定理2

f为双射，f为L1

到L2

的同构当且仅当∀a,b∈L1,a≼b⇔f(a)≼f(b)证明同构的思路（充分性）：(1)由保序性证明f(a)∨f(b)≼f(a∨b)(2)由满射性存在d使得f(a)∨f(b)=f(d)

由f(a)≼f(d)推出a≼d,同理b≼d(3)a∨b≼d推出f(a∨b)≼f(a)∨f(b)(4)由(1)和(3)得f(a)∨f(b)=f(a∨b)(5)同理f(a)∧f(b)=f(a∧b)第三编代数结构22完备格定义设L是格，若对L的任何子集S，

S的最大下界∧S,最小上界∨S存在，则L是完备格.注意：S可以是空集

x是∅的下界⇔∀a(a∈∅→x≼a)x是∅的上界⇔∀a(a∈∅→a≼x)

前件为假，L中任何元素都是∅的上界和下界，取L最大元为∧∅，最小元为∨∅条件：L为偏序，任意子集S⊆L,∨S(或∧S)存在.实例：有限格、幂集格、格的理想格完备第三编代数结构23格的理想I