ch 19 1定義性質(zhì)同態(tài)直積

第三編代數(shù)結(jié)構(gòu)1第十九章格與布爾代數(shù)19.1格的定義與性質(zhì)19.2子格、格同態(tài)與格的直積19.3特殊的格19.4布爾代數(shù)第三編代數(shù)結(jié)構(gòu)219.1格的定義和性質(zhì)格的定義格的基本性質(zhì)對偶原理格中的基本等式與不等式格中的基本等價條件格中的算律格的代數(shù)定義格中的不等式第三編代數(shù)結(jié)構(gòu)3格的定義格的偏序集定義：

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

求最大下界、最小上界構(gòu)成格中的運算∧,∨格<L,?>與導(dǎo)出的代數(shù)系統(tǒng)<L,∧,∨>的對應(yīng)關(guān)系格的實例：

n的正因子格Sn

冪集格P(B)

子群格L(G)第三編代數(shù)結(jié)構(gòu)4格的實例例1

設(shè)n是正整數(shù)，Sn是n的正因子的集合.D為整除關(guān)系，則偏序集<Sn,D>構(gòu)成格.?x,y∈Sn，x∨y

是lcm(x,y)，即x

與y

的最小公倍數(shù).x∧y

是gcd(x,y)，即x

與y

的最大公約數(shù).下圖給出了格<S8,D>，<S6,D>和<S30,D>.第三編代數(shù)結(jié)構(gòu)5格的實例（續(xù)）(b)abcdfe(a)acbdedacbefgfeabcd(c)(d)例2

判斷下列偏序集是否構(gòu)成格，并說明理由.(1)<Z,≤>，其中Z是整數(shù)集，≤為小于或等于關(guān)系.(2)偏序集的哈斯圖分別在下圖給出.(1)是格.(2)都不是格.第三編代數(shù)結(jié)構(gòu)6格的性質(zhì)——對偶原理對偶命題：設(shè)P是由格中元素,?,?,=,∧,∨等表示的命題，若將P中的?,?,∧,∨分別替換成?,?,∨,∧得到的命題稱為P的對偶命題，記作P*.實例：

P:a∧b=b∧a P*：a∨b=b∨a性質(zhì)：(P*)*=P.對偶原理：如果P對于一切格為真，則P*也對一切格為真.第三編代數(shù)結(jié)構(gòu)7格的性質(zhì)（續(xù)）格中的基本不等式和等式

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第三編代數(shù)結(jié)構(gòu)8格的性質(zhì)（續(xù)）格中的基本等價條件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第三編代數(shù)結(jié)構(gòu)9格的性質(zhì)（續(xù)）格中交換律、結(jié)合律、冪等律、吸收律證(1)a∧b是{a,b}的下界，

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

結(jié)合律

(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第三編代數(shù)結(jié)構(gòu)10格的代數(shù)定義引理

<S,*,?>是具有兩個二元運算的代數(shù)系統(tǒng).

如果*,?運算滿足交換、結(jié)合、吸收律，則(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第三編代數(shù)結(jié)構(gòu)11格的代數(shù)定義（續(xù)）定理設(shè)<S,*,?>是具有兩個二元運算的代數(shù)系統(tǒng)，若*和?運算滿足交換、結(jié)合、吸收律，則可以適當(dāng)定義S上偏序?，使得<S,?>構(gòu)成格，且<S,?>導(dǎo)出的代數(shù)系統(tǒng)就是<S,*,?>.證明思路

(1)利用運算?或*定義S上的二元關(guān)系R(2)證明R為S上的偏序

(3)證明對于S中任意兩個元素x,yx∨y=x?y,x∧y=x*y<S,∧,∨>構(gòu)成格第三編代數(shù)結(jié)構(gòu)12定理的證明證

(1)定義二元關(guān)系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記作?第三編代數(shù)結(jié)構(gòu)13定理的證明（續(xù)）(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最小上界：假設(shè)c為上界，則(a?b)?c=a?(b?c)=a?c=c

a?b?c同理，a*b是{a,b}的最大下界.第三編代數(shù)結(jié)構(gòu)14格的代數(shù)定義等價定義設(shè)<L,∧,∨>是具有兩個二元運算的代數(shù)系統(tǒng)，如果∧,∨滿足交換、結(jié)合、吸收律，則稱<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>是同一個格第三編代數(shù)結(jié)構(gòu)15格的性質(zhì)（續(xù)）格的不等式（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思考：如何證明以上不等式？第三編代數(shù)結(jié)構(gòu)16不滿足分配律的格鉆石格：b∨(c∧d)=b∨a=b(b∨c)∧(b∨d)=e∧e=e思考：指出五角格不滿足分配律的元素abcde鉆石格五角格abcde第三編代數(shù)結(jié)構(gòu)1719.2子格、格同態(tài)、格的直積子格子格定義子格判別格的同態(tài)與同構(gòu)格同態(tài)定義格同態(tài)的性質(zhì)完備格格的直積第三編代數(shù)結(jié)構(gòu)18格的子格L的子格：L的非空子集S，且S關(guān)于L中∧和∨運算封閉.注意：子格元素在原來格中求最大下界和最小上界.實例：子群格L(G)是格，但一定不是P(G)的子格.

例如Klein四元群G={e,a,b,c},L(G)={<e>,<a>,<b>,<c>,G}P(G)={?,<e>,{a},,{c},<a>,<b>,<c>,{a,b},{a,c},{b,c},{a,b,c},{a,b,e},{a,c,e},{b,c,e},G}第三編代數(shù)結(jié)構(gòu)19格的同態(tài)定義設(shè)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的同態(tài).實例：L1=<{1,2,3,6},|>,L2=<{0,1},≤>f(1)=f(2)=0,f(3)=f(6)=1f為L1到L2的同態(tài).123601第三編代數(shù)結(jié)構(gòu)20格同態(tài)的性質(zhì)格同態(tài)具有保序性定理1

f是格L1

到L2

的同態(tài)，則?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.思考反例.第三編代數(shù)結(jié)構(gòu)21格同態(tài)的性質(zhì)（續(xù)）定理2

f為雙射，f為L1

到L2

的同構(gòu)當(dāng)且僅當(dāng)?a,b∈L1,a?b?f(a)?f(b)證明同構(gòu)的思路（充分性）：(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)第三編代數(shù)結(jié)構(gòu)22完備格定義設(shè)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)存在.實例：有限格、冪集格、格的理想格完備第三編代數(shù)結(jié)構(gòu)23格的理想I