離散數(shù)學(xué)(第16-17章)陳瑜

陳瑜Email：chenyu.inbox@2/4/2023離散數(shù)學(xué)計算機(jī)學(xué)院2/4/20231計算機(jī)科學(xué)與工程學(xué)院第16章：環(huán)和域16.1環(huán)的定義及其性質(zhì)2/4/20232計算機(jī)科學(xué)與工程學(xué)院環(huán)和域

前面討論了具有一個二元運(yùn)算的代數(shù)系統(tǒng)——半群、含幺半群、群、子群。下面討論具有兩個二元運(yùn)算的代數(shù)系統(tǒng)。給定兩個代數(shù)系統(tǒng)<A,+>，<A,*>可將它們組合成一個具有兩個二元運(yùn)算的代數(shù)系統(tǒng)<A,+,*>,而這兩個二元運(yùn)算符+和*之間是有聯(lián)系的。環(huán),域，特別是有限域是糾錯碼理論的基礎(chǔ)。2/4/20233計算機(jī)科學(xué)與工程學(xué)院環(huán)Ring定義16.1

一個代數(shù)系統(tǒng)<R,+,*>，如果滿足：

（1）<R，+>是阿貝爾群；

（2）<R,*>是半群；

（3）乘法*在加法+上可分配。即對任意a，b，cR有

a*(b+c)=（a*b）+（a*c）

(b+c)*a=（b*a）+（c*a)

則稱<R,+,*>是一個環(huán)。(聯(lián)系兩個二元運(yùn)算，否則就不是一個系統(tǒng)而是兩個系統(tǒng))2/4/20234計算機(jī)科學(xué)與工程學(xué)院例16.1在加法和乘法作用下，整數(shù)、實數(shù)、有理數(shù)、偶數(shù)和復(fù)數(shù)都能構(gòu)成環(huán)。

<Z,+,×><R,+,×><Q,+,×><E,+,×><C,+,×>+可以交換，0是+的幺元，

i的逆為-i；+,×可結(jié)合,×對+可分配2/4/20235計算機(jī)科學(xué)與工程學(xué)院例16.2設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即:Zk={[0]，[1]，[2]，…，[k-1]}<Zk

，>是群（剩余類加群），<Zk

，>是半群（剩余類乘半群），∵對[i]，[j]，[k]Zk有[i]（[j][k]）=[i(j+k)]=[ij+ik]=[ij][ik]=([i][j])([i][k]）∴<Zk

，，>是環(huán)，稱為（模k）剩余類環(huán)。特別，k=2時，稱為布爾環(huán)。2/4/20236計算機(jī)科學(xué)與工程學(xué)院例16.2設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即:Zk={[0]，[1]，[2]，…，[k-1]}<Zk

，>是群（剩余類加群），<Zk

，>是半群（剩余類乘半群），∵

對[i]，[j]，[k]Zk有[i]（[j][k]）=[i(j+k)]=[ij+ik]=[ij][ik]=([i][j])([i][k]）∴<Zk

，，>是環(huán)，稱為（模k）剩余類環(huán)。特別，k=2時，稱為布爾環(huán)。2/4/20237計算機(jī)科學(xué)與工程學(xué)院例16.2設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即:Zk={[0]，[1]，[2]，…，[k-1]}<Zk

，>是群（剩余類加群），<Zk

，>是半群（剩余類乘半群），∵對[i]，[j]，[k]Zk有[i]（[j][k]）=[i(j+k)]=[ij+ik]=[ij][ik]=([i][j])([i][k]）∴<Zk

，，>是環(huán)，稱為（模k）剩余類環(huán)。特別，k=2時，稱為布爾環(huán)。2/4/20238計算機(jī)科學(xué)與工程學(xué)院定理16.1(移項法則)設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:

a+b=ca+b-c=θ2/4/20239計算機(jī)科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)(-a)*b=a*(-b)=-(a*b)(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c2/4/202310計算機(jī)科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)(-a)*b=a*(-b)=-(a*b)(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c證明:

因為a*θ=a*（θ+θ）=(a*θ)+(a*θ)，由移項法則a*θ=θ。同樣，可得θ*a=θ。2/4/202311計算機(jī)科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c2/4/202312計算機(jī)科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c證明：因為(a*(-b))+(a*b)=a*(-b+b)=a*θ=θ,所以a*(-b)=-(a*b)。同理，(a*b)+((-a)*b)=(a-a)*b=θ,所以（-a)*b=-(a*b).2/4/202313計算機(jī)科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c2/4/202314計算機(jī)科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c證明：利用②式的結(jié)果，

((-a)*(-b))-(a*b)=((-a)*(-b)）+((-a)*b)）=(-a)*(-b+b)=(-a)*θ=θ,但是，-(a*b)又是a*b的逆，根據(jù)群<R,+>中逆的唯一性，a*b=(-a)*(-b).2/4/202315計算機(jī)科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*ba*(b-c)=(a*b)-(b*c)證明：a*(b-c)=a*(b+(-c))=(a*b)+(a*(-c))=(a*b)-(a*c).2/4/202316計算機(jī)科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*ba*(b-c)=(a*b)-(b*c)

（b-c）*a=(b*a)-(c*a)2/4/202317計算機(jī)科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*ba*(b-c)=(a*b)-(b*c)

（b-c）*a=(b*a)-(c*a)

這個定理表明，普通環(huán)的運(yùn)算性質(zhì)在很多方面類似于數(shù)的運(yùn)算性質(zhì)，但是在某些方面它們卻有不同。例如在模m剩余類環(huán)<Zm,，

>中，我們特別注意到一種情況：當(dāng)[i]≠[0],[j]≠[0]時，卻可能[i][j]=[0]。例如在<Z6,，

>中，[2][3]=[0],[4][3]=[0]。2/4/202318計算機(jī)科學(xué)與工程學(xué)院定義16.2設(shè)<R,+,*>是環(huán)，a,b∈R。如果a≠θ且b≠θ,而a*b=θ，則稱a和b是R中的零因子。例16-3模m剩余類環(huán)<Zm,，

>沒有零因子當(dāng)且僅當(dāng)m是素數(shù)。因為當(dāng)m是合數(shù)時，必有a≥2,b≥2使m=ab，從而[a][b]=[m]=[0],而且[a]和[b]都是零因子。當(dāng)m是素數(shù)時，不存在a≥2和b≥2使m=ab，因而無零因子。

2/4/202319計算機(jī)科學(xué)與工程學(xué)院定義16.2設(shè)<R,+,*>是環(huán)，a,b∈R。如果a≠θ且b≠θ,而a*b=θ，則稱a和b是R中的零因子。例16.3

模m剩余類環(huán)<Zm,，

>沒有零因子當(dāng)且僅當(dāng)m是素數(shù)。因為當(dāng)m是合數(shù)時，必有a≥2,b≥2使m=ab，從而[a][b]=[m]=[0],而且[a]和[b]都是零因子。當(dāng)m是素數(shù)時，不存在a≥2和b≥2使m=ab，因而無零因子。

合數(shù)是除了1和它本身還能被其他的正整數(shù)整除的正整數(shù).

除2之外的偶數(shù)都是合數(shù).(除0以外)2/4/202320計算機(jī)科學(xué)與工程學(xué)院16.2整環(huán)與域2/4/202321計算機(jī)科學(xué)與工程學(xué)院特殊環(huán)定義16.3設(shè)<R,+,*>是一個環(huán):如果<R,*>是可交換的，稱<R,+,*>是交換環(huán)；如果<R,*>是含幺半群，稱<R,+,*>是含幺環(huán)；如果對于R中某些非零元素a≠θ、b≠θ,能使a*b=θ,稱<R,+,*>是含零因子環(huán)；a、b稱為零因子；如果<R,+,*>是可交換的、含幺、而無零因子，則稱它是整環(huán)。2/4/202322計算機(jī)科學(xué)與工程學(xué)院例16.4（同前例16.3）

證明（模k）剩余類環(huán)<Zk，，>無零因子當(dāng)且僅當(dāng)k是素數(shù)。證明：∵當(dāng)k是合數(shù)時，必有a≥2、b≥2，使得k=ab，從而[a][b]=[k]=[0]，即[a]、[b]都是零因子。又∵當(dāng)k是素數(shù)時，不存在a≥2、b≥2，使得k=ab，從而無零因子。

∴結(jié)論成立。2/4/202323計算機(jī)科學(xué)與工程學(xué)院定理16.3

設(shè)<R,+,*>是一個環(huán)，則R中無零因子當(dāng)且僅當(dāng)對a,x,yR，當(dāng)a≠0時，

a*x=a*yx=y或x*a=y*ax=y

（即滿足可約律）證明如果R中無零因子，則當(dāng)a*x=a*y時，(a*x)-(a*y)=θ，即a*(x-y)=θ.由于a≠θ,因而x-y=θ，即x=y。同理，由x*a=y*a可以得出x=y。反過來，設(shè)由a*x=a*y必然得出x=y的結(jié)論，如果R中存在b和c使b*c=θ，那么由b*c=θ=b*θ就導(dǎo)出c=θ。這說明R中必?zé)o零因子。

2/4/202324計算機(jī)科學(xué)與工程學(xué)院定理16.3

設(shè)<R,+,*>是一個環(huán)，則R中無零因子當(dāng)且僅當(dāng)對a,x,yR，當(dāng)a≠0時，

a*x=a*yx=y或x*a=y*ax=y

（即滿足可約律）證明如果R中無零因子，則當(dāng)a*x=a*y時，(a*x)-(a*y)=θ，即a*(x-y)=θ.由于a≠θ,因而x-y=θ，即x=y。同理，由x*a=y*a可以得出x=y。反過來，設(shè)由a*x=a*y必然得出x=y的結(jié)論，如果R中存在b和c使b*c=θ，那么由b*c=θ=b*θ就導(dǎo)出c=θ。這說明R中必?zé)o零因子。

2/4/202325計算機(jī)科學(xué)與工程學(xué)院定理16.3

設(shè)<R,+,*>是一個環(huán)，則R中無零因子當(dāng)且僅當(dāng)對a,x,yR，當(dāng)a≠0時，

a*x=a*yx=y或x*a=y*ax=y

（即滿足可約律）證明如果R中無零因子，則當(dāng)a*x=a*y時，(a*x)-(a*y)=θ，即a*(x-y)=θ.由于a≠θ,因而x-y=θ，即x=y。同理，由x*a=y*a可以得出x=y。反過來，設(shè)由a*x=a*y必然得出x=y的結(jié)論，如果R中存在b和c使b*c=θ，那么由b*c=θ=b*θ就導(dǎo)出c=θ。這說明R中必?zé)o零因子。

2/4/202326計算機(jī)科學(xué)與工程學(xué)院定理16.3設(shè)<R,+,*>是一個環(huán)，則R中無零因子當(dāng)且僅當(dāng)對a,x,yR，當(dāng)a≠0時，

a*x=a*yx=y或x*a=y*ax=y

（即滿足可約律）定義16.4

設(shè)<R,+,*>是一個環(huán)，S是R的非空集合，如果<S,+,*>也是一個環(huán)，則稱S是R的子環(huán)。例如：<{[0],[2],[4]}，，>是模6剩余類環(huán)<Z6，，>的子環(huán)。2/4/202327計算機(jī)科學(xué)與工程學(xué)院環(huán)的同構(gòu)與同態(tài)定義16.5

設(shè)<S,+,*>和<T,,>是兩個環(huán)，如在集合S與T之間存在映射f：ST，使得對a，bS，有：

f(a+b)=f(a)f(b)

f(a*b)=f(a)f(b)

則稱f是從<S,+,*>到<T,,>的環(huán)同態(tài)映射，f(S)為S的一個同態(tài)象。當(dāng)f是一個滿射時，則稱f為滿同態(tài)；當(dāng)f是一個雙射時，則稱f是環(huán)同構(gòu)映射；2/4/202328計算機(jī)科學(xué)與工程學(xué)院例16.5存在整數(shù)環(huán)<Z,+,*>到模m剩余類環(huán)<Zm,,>的同態(tài)，因為我們可以定義映射f：Z→Zm如下：使對所有x∈Z，

f(x)=xmodm.

在此映射下，設(shè)a,b∈Z,由同余的性質(zhì)，

[a+b]=[a][b],[a*b]=[a][b]，所以<Z,+,*>～<Zm,,>

。2/4/202329計算機(jī)科學(xué)與工程學(xué)院定理16.4設(shè)f是環(huán)<S,+,*>到環(huán)<T,,>的同態(tài)映射，則:如果θ和e分別是S中的加法幺元和乘法幺元，則f(θ)和f(e)分別是f(S)中的幺元和幺元；對aS，如果-a（或a-1）是a的加法（或乘法）逆元，則f(-a)（或f(a-1)）是f(S)中的逆元（或逆元）；<f(S),,>也是環(huán)。2/4/202330計算機(jī)科學(xué)與工程學(xué)院域

給環(huán)施加進(jìn)一步的限制，從而得到另一個代數(shù)系統(tǒng)——域。問題歸結(jié)為<R-{θ},*>是否是一個群。定義16.6

設(shè)<R,+,*>是一個環(huán)，如果<R,+>和<R-{θ},*>都是交換群，則稱<R,+,*>是域。

一般情況下，整環(huán)不是域，但當(dāng)環(huán)的元素個數(shù)有限時，有以下結(jié)論：定理16.5有限整環(huán)<R,+,*>必是域。(教材p198)θ是加法幺元2/4/202331計算機(jī)科學(xué)與工程學(xué)院例16.6實數(shù)環(huán)<R,+,×>、有理數(shù)環(huán)<Q,+,×>、剩余類環(huán)<Zp，，>(p是素數(shù)）都是域。整數(shù)環(huán)<Z,+,×>、剩余類環(huán)<Zm，，>(m是合數(shù)）都不是域。因為<Z-{0}，×>、<Zm–{[0]}，>都不是群。2/4/202332計算機(jī)科學(xué)與工程學(xué)院習(xí)題熟記相關(guān)概念2/4/202333計算機(jī)科學(xué)與工程學(xué)院第17章格與布爾代數(shù)17.1格的定義與性質(zhì)2/4/202334計算機(jī)科學(xué)與工程學(xué)院格與布爾代數(shù)下面討論另外兩個重要的代數(shù)系統(tǒng)—格與布爾代數(shù)，這兩個代數(shù)系統(tǒng)與前面討論的代數(shù)系統(tǒng)之間存在著一個重要區(qū)別：在格與布爾代數(shù)中，偏序關(guān)系具有重要意義。2/4/202335計算機(jī)科學(xué)與工程學(xué)院本章主要介紹以下幾點(diǎn)：格的概念和基本性質(zhì)子格的定義特殊的格及性質(zhì)布爾代數(shù)的概念和基本性質(zhì)2/4/202336計算機(jī)科學(xué)與工程學(xué)院格的定義定義17.1（代數(shù)格）設(shè)<L，∨，∧>是一個代數(shù)系統(tǒng)，如果∨，∧滿足：交換律：a∨b=b∨a，a∧b=b∧a,結(jié)合律：a∨(b∨c)=(a∨b)∨c,

a∧(b∧c)=(a∧b)∧c吸收律：a∨(a∧b)=a，a∧(a∨b)=a

則稱<L，∨，∧>是一個代數(shù)格。2個典型的格:

集合代數(shù)系統(tǒng)<2A，∪，∩>

命題邏輯系統(tǒng)<，∨，∧>代數(shù)格2/4/202337計算機(jī)科學(xué)與工程學(xué)院定理17.1

(冪等律)設(shè)<L,∨，∧>是一個代數(shù)格，a∈L，則必有a∨a=a,a∧a=a。證明：

a∨a=a∨(a∧(a∨a))(吸收律)=a.(吸收律)

在上兩式中，把∨換成∧，把∧換成∨后，可以證明a∧a=a。2/4/202338計算機(jī)科學(xué)與工程學(xué)院復(fù)習(xí)：偏序關(guān)系是集合上的自反的、可傳遞、反對稱關(guān)系,它提供比較集合元素的工具。定義：設(shè)R是集合A上的自反的、反對稱的、傳遞的關(guān)系，則稱R是A上的偏序關(guān)系(記為“”,讀作“小于等于”)。序偶<A，R>稱為偏序集。定義17.2設(shè)<L，>是一個偏序集，對a，bL，集合{a，b}都有最大下界(glb)和最小上界(lub)，則稱<L，>是一個偏序格，簡稱L是一個格，若L是一個有限集，則稱<L，>為有限格。2/4/202339計算機(jī)科學(xué)與工程學(xué)院復(fù)習(xí)：偏序關(guān)系是集合上的自反的、可傳遞、反對稱關(guān)系,它提供比較集合元素的工具。定義：設(shè)R是集合A上的自反的、反對稱的、傳遞的關(guān)系，則稱R是A上的偏序關(guān)系(記為“”,讀作“小于等于”)。序偶<A，R>稱為偏序集。定義17.2

設(shè)<L，>是一個偏序集，對a，bL，集合{a，b}都有最大下界(glb)和最小上界(lub)，則稱<L，>是一個偏序格，簡稱L是一個格，若L是一個有限集，則稱<L，>為有限格。從定義知道：有限偏序集要成為格，必須有一個最大元和最小元。2/4/202340計算機(jī)科學(xué)與工程學(xué)院偏序集<2A，>中，任何兩個元素X、Y2A，都有l(wèi)ub（X，Y）=X∪Y，glb（X，Y）=X∩Y，則<2A，>是一個偏序格，稱為冪集格。2/4/202341計算機(jī)科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個偏序格；2/4/202342計算機(jī)科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個偏序格；

證明

（首先證明<L,≤>是偏序集。）由于a∧a=a(冪等律)，因此a≤a,即“≤”具有自反性。設(shè)a≤b且b≤a,則由“≤”的定義a=a∧b(a≤b)=b∧a(交換律)=b,(b≤a),即反對稱性成立。

2/4/202343計算機(jī)科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個偏序格；

證明

（首先證明<L,≤>是偏序集。）再設(shè)a≤b，b≤c,那么a∧c=(a∧b)∧c(由a≤b)=a∧(b∧c)(結(jié)合律)=a∧b(由b≤c)

=a,(由a≤b),即有a≤c，傳遞性成立。2/4/202344計算機(jī)科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個偏序格；

證明其次，證明對任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y是{x，y}的一個下界。現(xiàn)在設(shè)c是x和y的任一下界，即c≤x且c≤y,那么c∧(x∧y)=(c∧x)∧y(結(jié)合律)=c∧y=c.這說明c≤x∧y，從而知道，glb(x，y)=x∧y。類似地，可以證明lub(x，y)=x∨y，只需在上述證明中把∧換成∨，把∨換成∧即可。2/4/202345計算機(jī)科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個偏序格；

證明

其次，證明對任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y是{x，y}的一個下界。

現(xiàn)在設(shè)c是x和y的任一下界，即c≤x且c≤y,那么c∧(x∧y)=(c∧x)∧y(結(jié)合律)=c∧y=c.這說明c≤x∧y，從而知道，glb(x，y)=x∧y。類似地，可以證明lub(x，y)=x∨y，只需在上述證明中把∧換成∨，把∨換成∧即可。2/4/202346計算機(jī)科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個偏序格；

證明

其次，證明對任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y是{x，y}的一個下界。現(xiàn)在設(shè)c是x和y的任一下界，即c≤x且c≤y,那么c∧(x∧y)=(c∧x)∧y(結(jié)合律)=c∧y=c.這說明c≤x∧y，從而知道，glb(x，y)=x∧y。

類似地，可以證明lub(x，y)=x∨y，只需在上述證明中把∧換成∨，把∨換成∧即可。2/4/202347計算機(jī)科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個偏序格；

證明

其次，證明對任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y是{x，y}的一個下界。

現(xiàn)在設(shè)c是x和y的任一下界，即c≤x且c≤y,那么c∧(x∧y)=(c∧x)∧y(結(jié)合律)=c∧y=c.這說明c≤x∧y，從而知道，glb(x，y)=x∧y。類似地，可以證明lub(x，y)=x∨y，只需在上述證明中把∧換成∨，把∨換成∧即可。綜合以上結(jié)論，命題得證。2/4/202348計算機(jī)科學(xué)與工程學(xué)院定理17.3設(shè)<L，>是一個偏序格，在格上定義“∨”、“∧”：a∧b=glb（a，b），a∨b=lub（a，b），則<L，∨，∧>是一個代數(shù)格。

證明

從運(yùn)算和的定義可以看出，它們滿足交換律、結(jié)合律和冪等律?，F(xiàn)證明吸收律成立。事實上，由glb(a,b)≤a≤lub(a,b),可以看出

a∧(a∨b)=glb(a,lub(a,b))=a,

a∨(a∧b)=lub(a,glb(a,b))=a.

由此可知，<L,∨，∧>是代數(shù)格。

定理17.2和17.3表明：格的兩種定義是完全等價的。以后我們將不特別加以區(qū)分，而是根據(jù)需要采用相應(yīng)的定義來說明問題。2/4/202349計算機(jī)科學(xué)與工程學(xué)院定理17.3設(shè)<L，>是一個偏序格，在格上定義“∨”、“∧”：a∧b=glb（a，b），a∨b=lub（a，b），則<L，∨，∧>是一個代數(shù)格。

證明

從運(yùn)算和的定義可以看出，它們滿足交換律、結(jié)合律和冪等律?，F(xiàn)證明吸收律成立。事實上，由glb(a,b)≤a≤lub(a,b),可以看出

a∧(a∨b)=glb(a,lub(a,b))=a,

a∨(a∧b)=lub(a,glb(a,b))=a.

由此可知，<L,∨，∧>是代數(shù)格。

定理17.2和17.3表明：格的兩種定義是完全等價的。以后我們將不特別加以區(qū)分，而是根據(jù)需要采用相應(yīng)的定義來說明問題。2/4/202350計算機(jī)科學(xué)與工程學(xué)院定理17.3設(shè)<L，>是一個偏序格，在格上定義“∨”、“∧”：a∧b=glb（a，b），a∨b=lub（a，b），則<L，∨，∧>是一個代數(shù)格。

證明

從運(yùn)算和的定義可以看出，它們滿足交換律、結(jié)合律和冪等律?，F(xiàn)證明吸收律成立。事實上，由glb(a,b)≤a≤lub(a,b),可以看出

a∧(a∨b)=glb(a,lub(a,b))=a,

a∨(a∧b)=lub(a,glb(a,b))=a.

由此可知，<L,∨，∧>是代數(shù)格。

定理17.2和17.3表明：格的兩種定義是完全等價的。以后我們將不特別加以區(qū)分，而是根據(jù)需要采用相應(yīng)的定義來說明問題。2/4/202351計算機(jī)科學(xué)與工程學(xué)院例如圖所示的八個偏序集都是格；2/4/202352計算機(jī)科學(xué)與工程學(xué)院2/4/202353計算機(jī)科學(xué)與工程學(xué)院如圖所示的四個偏序集都不是格。2/4/202354計算機(jī)科學(xué)與工程學(xué)院作業(yè)熟練掌握相關(guān)概念、定理2/4/202355計算機(jī)科學(xué)與工程學(xué)院17.2子格與格同態(tài)2/4/202356計算機(jī)科學(xué)與工程學(xué)院定義17.3

設(shè)代數(shù)系統(tǒng)<L,∨,∧>是一個格，SL，若S滿足：S≠Φ；運(yùn)算∨和∧對子集S都是封閉的；則稱<S,∨,∧>是<L,∨,∧>的子格。2/4/202357計算機(jī)科學(xué)與工程學(xué)院格的性質(zhì)與同態(tài)定義17.4設(shè)<L，>和<L，′>是兩個偏序格，如果偏序關(guān)系′是的逆關(guān)系，則稱此兩個偏序格為對偶格。

設(shè)L是由18的正因子組成的集合，則L關(guān)于整除關(guān)系構(gòu)成的逆關(guān)系是倍數(shù)關(guān)系；設(shè)倍數(shù)關(guān)系用“‖”表示，那么<L，‖>是格，并和<L，∣>互為對偶。

在一個格中的最大（?。┰厥菍ε几裰械淖钚。ù螅┰?；即兩個對偶格的Hasse圖是相互顛倒的。2/4/202358計算機(jī)科學(xué)與工程學(xué)院格的性質(zhì)與同態(tài)定義17.4設(shè)<L，>和<L，′>是兩個偏序格，如果偏序關(guān)系′是的逆關(guān)系，則稱此兩個偏序格為對偶格。

設(shè)L是由18的正因子組成的集合，則L關(guān)于整除關(guān)系構(gòu)成的逆關(guān)系是倍數(shù)關(guān)系；設(shè)倍數(shù)關(guān)系用“‖”表示，那么<L，‖>是格，并和<L，∣>互為對偶。

在一個格中的最大（小）元必是對偶格中的最?。ù螅┰?；即兩個對偶格的Hasse圖是相互顛倒的。2/4/202359計算機(jī)科學(xué)與工程學(xué)院格的性質(zhì)與同態(tài)定義17.4設(shè)<L，>和<L，′>是兩個偏序格，如果偏序關(guān)系′是的逆關(guān)系，則稱此兩個偏序格為對偶格。

設(shè)L是由18的正因子組成的集合，則L關(guān)于整除關(guān)系構(gòu)成的逆關(guān)系是倍數(shù)關(guān)系；設(shè)倍數(shù)關(guān)系用“‖”表示，那么<L，‖>是格，并和<L，∣>互為對偶。

在一個格中的最大（?。┰厥菍ε几裰械淖钚。ù螅┰?；即兩個對偶格的Hasse圖是相互顛倒的。2/4/202360計算機(jī)科學(xué)與工程學(xué)院定義17.5設(shè)<L，∨，∧>是一個格，E是格中的公式。將E中的0（最小元）和1（最大元）互換、∨和∧互換后得到的新公式E*稱為E的對偶公式。對偶原理：設(shè)X和Y是格<L，∨，∧>上的兩個公式，X*和Y*是相對應(yīng)的對偶公式。如果X=Y，則X*=Y*。定理17.4設(shè)X和Y是格<L，∨，∧>上的兩個公式，是對應(yīng)的偏序。如果XY，則Y*X*。2/4/202361計算機(jī)科學(xué)與工程學(xué)院定義17.5設(shè)<L，∨，∧>是一個格，E是格中的公式。將E中的0（最小元）和1（最大元）互換、∨和∧互換后得到的新公式E*稱為E的對偶公式。對偶原理：設(shè)X和Y是格<L，∨，∧>上的兩個公式，X*和Y*是相對應(yīng)的對偶公式。如果X=Y，則X*=Y*。定理17.4設(shè)X和Y是格<L，∨，∧>上的兩個公式，是對應(yīng)的偏序。如果XY，則Y*X*。2/4/202362計算機(jī)科學(xué)與工程學(xué)院定義17.5設(shè)<L，∨，∧>是一個格，E是格中的公式。將E中的0（最小元）和1（最大元）互換、∨和∧互換后得到的新公式E*稱為E的對偶公式。對偶原理：設(shè)X和Y是格<L，∨，∧>上的兩個公式，X*和Y*是相對應(yīng)的對偶公式。如果X=Y，則X*=Y*。定理17.4設(shè)X和Y是格<L，∨，∧>上的兩個公式，是對應(yīng)的偏序。如果XY，則Y*X*。

證明：由偏序集的定義及對偶原理有：

XYX∧Y=X（偏序定義）

X*∨Y*=X*

（對偶原理）Y*X*

（偏序定義）2/4/202363計算機(jī)科學(xué)與工程學(xué)院定理17.5、17.6設(shè)<L，∨，∧>是一個格，是對應(yīng)的偏序，a,b,c,dL，則：(教材p202)a≤b

a∨c≤b∨c

a≤b

a∧c≤b∧c

a≤b且c≤d

a∧c≤b∧da≤b且c≤d

a∨c≤b∨d

a≤b且a≤c

a≤b∧ca≤c且b≤c

a∨b≤ca∨(b∧c)≤(a∨b)∧(a∨c) (a∧b)∨(a∧c)≤a∧(b∨c)

(保序性)(準(zhǔn)分配關(guān)系)2/4/202364計算機(jī)科學(xué)與工程學(xué)院定理17.5、17.6設(shè)<L，∨，∧>是一個格，是對應(yīng)的偏序，a,b,c,dL，則：(教材p202)a≤b

a∨c≤b∨c

a≤b

a∧c≤b∧c

(保序性)證明：①a≤b

a∨b=b(a∨c)∨(b∨c)=b∨c

a∨c≤b∨c。②a≤b

a∧b=a(a∧c)∧(b∧c)=a∧c

a∧c≤b∧c。2/4/202365計算機(jī)科學(xué)與工程學(xué)院格的同態(tài)與同構(gòu)

將代數(shù)系統(tǒng)的同態(tài)與同構(gòu)應(yīng)用于格，可以獲得格的同態(tài)與同構(gòu)定義：定義17.6設(shè)<L,∨，∧>和<S，，>是兩個格，ψ是L到S的映射。如果對任意x,y∈L，都有：ψ(x∨y)＝ψ(x)ψ(y)ψ(x∧y)＝ψ(x)ψ(y)，則稱ψ為從格<L,∨，∧>到格<S，，>的格同態(tài)映射，當(dāng)ψ分別是單射、滿射和雙射時，ψ分別稱為單一格同態(tài)、滿格同態(tài)和格同構(gòu)。2/4/202366計算機(jī)科學(xué)與工程學(xué)院格的同態(tài)與同構(gòu)將代數(shù)系統(tǒng)的同態(tài)與同構(gòu)應(yīng)用于格，可以獲得格的同態(tài)與同構(gòu)定義：定義17.6設(shè)<L,∨，∧>和<S，，>是兩個格，ψ是L到S的映射。如果對任意x,y∈L，都有：ψ(x∨y)＝ψ(x)ψ(y)ψ(x∧y)＝ψ(x)ψ(y)，則稱ψ為從格<L,∨，∧>到格<S，，>的格同態(tài)映射，當(dāng)ψ分別是單射、滿射和雙射時，ψ分別稱為單一格同態(tài)、滿格同態(tài)和格同構(gòu)。2/4/202367計算機(jī)科學(xué)與工程學(xué)院例設(shè)D6表示6的正因子集，證明因子格<D6

，|>和冪集格<2{a,b}，>是同構(gòu)的。證明：定義映射f：D6→2{a,b}，使得f(1)=,f(2)={a},f(3)=,f(6)={a,b}∵<D6

，|>對應(yīng)的代數(shù)格為<D6

，lcm，gcd><2{a,b}，>對應(yīng)的代數(shù)格為<2{a,b}，∪，∩>∴f(lcm(1,3))=f(3)==∪=f(1)∪f(3)f(gcd(2,6))=f(2)={a}={a}∩{a,b}=f(2)∩f(6)f(lcm(2,3))=f(6)={a,b}={a}∪=f(2)∪f(3)f(gcd(2,3))=f(1)=={a}∩=f(2)∩f(3)

其余情況也可一一驗證，又因為是雙射，所以，命題得證。2/4/202368計算機(jī)科學(xué)與工程學(xué)院例

設(shè)D6表示6的正因子集，證明因子格<D6

，|>和冪集格<2{a,b}，>是同構(gòu)的。證明：定義映射f：D6→2{a,b}，使得f(1)=,f(2)={a},f(3)=,f(6)={a,b}∵<D6

，|>對應(yīng)的代數(shù)格為<D6

，lcm，gcd><2{a,b}，>對應(yīng)的代數(shù)格為<2{a,b}，∪，∩>∴f(lcm(1,3))=f(3)==∪=f(1)∪f(3)f(gcd(2,6))=f(2)={a}={a}∩{a,b}=f(2)∩f(6)f(lcm(2,3))=f(6)={a,b}={a}∪=f(2)∪f(3)f(gcd(2,3))=f(1)=={a}∩=f(2)∩f(3)

其余情況也可一一驗證，又因為是雙射，所以，命題得證。2/4/202369計算機(jī)科學(xué)與工程學(xué)院例

設(shè)D6表示6的正因子集，證明因子格<D6

，|>和冪集格<2{a,b}，>是同構(gòu)的。證明：定義映射f：D6→2{a,b}，使得f(1)=,f(2)={a},f(3)=,f(6)={a,b}∵<D6

，|>對應(yīng)的代數(shù)格為<D6

，lcm，gcd><2{a,b}，>對應(yīng)的代數(shù)格為<2{a,b}，∪，∩>∴f(lcm(1,3))=f(3)==∪=f(1)∪f(3)f(gcd(2,6))=f(2)={a}={a}∩{a,b}=f(2)∩f(6)f(lcm(2,3))=f(6)={a,b}={a}∪=f(2)∪f(3)f(gcd(2,3))=f(1)=={a}∩=f(2)∩f(3)

其余情況也可一一驗證，又因為是雙射，所以，命題得證。lcm:最小公倍數(shù)gcd：最大公約數(shù)2/4/202370計算機(jī)科學(xué)與工程學(xué)院保序定理（教材p203）定理17.7設(shè)<L1，∨，∧>和<L2，，>是兩個格，對應(yīng)的偏序關(guān)系為、，則有：如果f：L1→L2是一個格同態(tài)，則對a，bL1，ab

f(a)

f(b)；

證明：對a，bL1，由f是函數(shù)，所以有f(a)、f(b)L2， 因為aba∧b＝a，于是，由同態(tài)等式知：f(a)＝f(a∧b)＝f(a)f(b)

所以：f(a)f(b)。 即：對a，bL1，ab

f(a)f(b)2/4/202371計算機(jī)科學(xué)與工程學(xué)院保序定理定理17.7設(shè)<L1，∨，∧>和<L2，，>是兩個格，對應(yīng)的偏序關(guān)系為、，則有：如果f：L1→L2是一個格同態(tài)，則對a，bL1，ab

f(a)

f(b)；

證明：對a，bL1，由f是函數(shù)，所以有f(a)、f(b)L2， 因為aba∧b＝a，于是，由同態(tài)等式知：f(a)＝f(a∧b)＝f(a)f(b)

所以：f(a)f(b)。 即：對a，bL1，ab

f(a)f(b)2/4/202372計算機(jī)科學(xué)與工程學(xué)院定理17.8

雙射f：L→P為格<L,∨，∧>到格<P,⊕,>的格同構(gòu)的充分必要條件是：對任意的a,b∈L，a≤bf(a)f(b),其中≤和分別是格L和P對應(yīng)的偏序。

證明：

2/4/202373計算機(jī)科學(xué)與工程學(xué)院定理17.8

雙射f：L→P為格<L,∨，∧>到格<P,⊕,>的格同構(gòu)的充分必要條件是：對任意的a,b∈L，a≤bf(a)f(b),其中≤和分別是格L和P對應(yīng)的偏序。

證明：當(dāng)f是L到P的格同構(gòu)時，它必須滿足保序定理，因此保序為必要條件是成立的。至于充分條件，只需證明由a≤bf(a)f(b)能導(dǎo)出f(a∨b)=f(a)⊕f(b)和f(a∧b)=f(a)f(b)就行了。

設(shè)a∨b=c，則a≤c且b≤c,從而f(a)f(c)，且

f(b)f(c).再由定理17-2.2第⑥條知道：

f(a)⊕f(b)

f(c)，這說明f(c)是f(a)和f(b)的一個上界。2/4/202374計算機(jī)科學(xué)與工程學(xué)院定理17.8

雙射f：L→P為格<L,∨，∧>到格<P,⊕,>的格同構(gòu)的充分必要條件是：對任意的a,b∈L，a≤bf(a)f(b),其中≤和分別是格L和P對應(yīng)的偏序。

證明：當(dāng)f是L到P的格同構(gòu)時，它必須滿足保序定理，因此保序為必要條件是成立的。至于充分條件，只需證明由a≤bf(a)f(b)能導(dǎo)出f(a∨b)=f(a)⊕f(b)和f(a∧b)=f(a)f(b)就行了。設(shè)a∨b=c，則a≤c且b≤c,從而f(a)f(c)，且

f(b)f(c).再由定理17.5第⑥條知道：

f(a)⊕f(b)

f(c)，這說明f(c)是f(a)和f(b)的一個上界。a≤c且b≤ca∨b≤c2/4/202375計算機(jī)科學(xué)與工程學(xué)院定理17.8

雙射f：L→P為格<L,∨，∧>到格<P,⊕,>的格同構(gòu)的充分必要條件是：對任意的a,b∈L，a≤bf(a)f(b),其中≤和分別是格L和P對應(yīng)的偏序。

證明：

剩下的任務(wù)要證明f(c)是f(a)和f(b)的最小上界。設(shè)f(d)是f(a)和f(b)的任意一個上界，即f(a)f(d)且f(b)f(d)。由題設(shè)條件可以得到a≤d且b≤d，從而a∨b≤d，即c≤d，于是f(c)f(d).

由此，就證明了f(c)=f(a∨b)=f(a)⊕f(b)。同理可證f(a∧b)=f(a)f(b)。因此，雙射f是格同構(gòu)。2/4/202376計算機(jī)科學(xué)與工程學(xué)院定理17.8

雙射f：L→P為格<L,∨，∧>到格<P,⊕,>的格同構(gòu)的充分必要條件是：對任意的a,b∈L，a≤bf(a)f(b),其中≤和分別是格L和P對應(yīng)的偏序。

證明：剩下的任務(wù)要證明f(c)是f(a)和f(b)的最小上界。設(shè)f(d)是f(a)和f(b)的任意一個上界，即f(a)f(d)且f(b)f(d)。由題設(shè)條件可以得到a≤d且b≤d，從而a∨b≤d，即c≤d，于是f(c)f(d).

由此，就證明了f(c)=f(a∨b)=f(a)⊕f(b)。同理可證f(a∧b)=f(a)f(b)。因此，雙射f是格同構(gòu)。2/4/202377計算機(jī)科學(xué)與工程學(xué)院例

設(shè)L={1，2，3，12}，在<L，|>和冪集格<2L，>之間構(gòu)造映射f：L→2L，使得對xL,f(x)={y|yL且y|x}。則：

f(1)=1，f(2)={1,2},f(3)={1,3},f(12)={1,2,3,12}，且x|y時,f(x)f(y)

所以，f是保序映射。

而f(lcm(2,3))=f(12)={1,2,3,12},f(2)∪f(3)={1,2,3}

即f(lcm(2,3))≠f(2)∪f(3)

所以f不是<L，|>到<2L，>的格同態(tài)。2/4/202378計算機(jī)科學(xué)與工程學(xué)院例

設(shè)L={1，2，3，12}，在<L，|>和冪集格<2L，>之間構(gòu)造映射f：L→2L，使得對xL,f(x)={y|yL且y|x}。則：

f(1)=1，f(2)={1,2},f(3)={1,3},f(12)={1,2,3,12}，且x|y時,f(x)f(y)

所以，f是保序映射。而f(lcm(2,3))=f(12)={1,2,3,12},f(2)∪f(3)={1,2,3}

即f(lcm(2,3))≠f(2)∪f(3)

所以f不是<L，|>到<2L，>的格同態(tài)。2/4/202379計算機(jī)科學(xué)與工程學(xué)院習(xí)題熟練掌握相關(guān)概念、定理2/4/202380計算機(jī)科學(xué)與工程學(xué)院17.3分配格與有補(bǔ)格2/4/202381計算機(jī)科學(xué)與工程學(xué)院分配格定義17.7設(shè)<L,∨，∧>是一個格，如果對任意a,b,c∈L，都有：

a∨(b∧c)＝(a∨b)∧(a∨c)(1)

a∧(b∨c)＝(a∧b)∨(a∧c)(2)

則稱<L,∨，∧>是一個分配格。注意：式(1)和式(2)的兩個分配律是對偶的，由對偶原理，定義17.7可簡化為只含式(1)和式(2)中一個的分配律。2/4/202382計算機(jī)科學(xué)與工程學(xué)院分配格定義17.7設(shè)<L,∨，∧>是一個格，如果對任意a,b,c∈L，都有：

a∨(b∧c)＝(a∨b)∧(a∨c)(1)

a∧(b∨c)＝(a∧b)∨(a∧c)(2)

則稱<L,∨，∧>是一個分配格。注意：式(1)和式(2)的兩個分配律是對偶的，由對偶原理，定義17.7可簡化為只含式(1)和式(2)中一個的分配律。2/4/202383計算機(jī)科學(xué)與工程學(xué)院例設(shè)A為任意一個集合，則冪集格<2A,∩,∪>是否是分配格？設(shè)P為命題公式集合，∧、∨分別是命題合取與析取運(yùn)算，則<P,∧,∨>是否是分配格？解：1)對任意P、Q、R∈2A

，有：P∩(Q∪R)＝(P∩Q)∪(P∩R)P∪(Q∩R)＝(P∪Q)∩(P∪R)

所以，格<2A，∩,∪>是一個分配格。

2)對任意R、S、T∈P，有R∧(S∨T)＝(R∧S)∨(R∧T)R∨(S∧T)＝(R∨S)∧(R∨T)

所以，格<P,∧,∨>是一個分配格。2/4/202384計算機(jī)科學(xué)與工程學(xué)院例設(shè)A為任意一個集合，則冪集格<2A,∩,∪>是否是分配格？設(shè)P為命題公式集合，∧、∨分別是命題合取與析取運(yùn)算，則<P,∧,∨>是否是分配格？解：1)

對任意P、Q、R∈2A

，有：P∩(Q∪R)＝(P∩Q)∪(P∩R)P∪(Q∩R)＝(P∪Q)∩(P∪R)

所以，格<2A，∩,∪>是一個分配格。

2)對任意R、S、T∈P，有R∧(S∨T)＝(R∧S)∨(R∧T)R∨(S∧T)＝(R∨S)∧(R∨T)

所以，格<P,∧,∨>是一個分配格。2/4/202385計算機(jī)科學(xué)與工程學(xué)院例設(shè)A為任意一個集合，則冪集格<2A,∩,∪>是否是分配格？設(shè)P為命題公式集合，∧、∨分別是命題合取與析取運(yùn)算，則<P,∧,∨>是否是分配格？解：1)對任意P、Q、R∈2A

，有：P∩(Q∪R)＝(P∩Q)∪(P∩R)P∪(Q∩R)＝(P∪Q)∩(P∪R)

所以，格<2A，∩,∪>是一個分配格。

2)

對任意R、S、T∈P，有R∧(S∨T)＝(R∧S)∨(R∧T)R∨(S∧T)＝(R∨S)∧(R∨T)

所以，格<P,∧,∨>是一個分配格。2/4/202386計算機(jī)科學(xué)與工程學(xué)院例證明圖中a）、b）所示的兩個格都不是分配格。2/4/202387計算機(jī)科學(xué)與工程學(xué)院證明在圖a）、b）中都取b,c,d三個元素來驗證。用“∧”和“∨”表示它們的交和并運(yùn)算。在圖a）中， b∧

(c∨d)＝b∧a＝b，而 (b∧c)∨(b∧d)＝e∨e＝e。在圖b）中，b∧(c∨d)＝b∧a＝b，而 (b∧c)∨(b∧d)＝e∨d＝d。因此，在圖a）和圖b）中都有：b∧(c∨d)≠(b∧c)∨(b∧d)。故它們都不是分配格。2/4/202388計算機(jī)科學(xué)與工程學(xué)院證明在圖a）、b）中都取b,c,d三個元素來驗證。用“∧”和“∨”表示它們的交和并運(yùn)算。在圖a）中， b∧

(c∨d)＝b∧a＝b，而 (b∧c)∨(b∧d)＝e∨e＝e。在圖b）中，b∧(c∨d)＝b∧a＝b，而 (b∧c)∨(b∧d)＝e∨d＝d。因此，在圖a）和圖b）中都有：b∧(c∨d)≠(b∧c)∨(b∧d)。故它們都不是分配格。2/4/202389計算機(jī)科學(xué)與工程學(xué)院結(jié)論一個格是分配格，當(dāng)且僅當(dāng)該格中沒有任何子格與圖中的兩個五元素格中的任何一個同構(gòu)。2/4/202390計算機(jī)科學(xué)與工程學(xué)院如圖a）～h）所示的八個圖都是分配格嗎？結(jié)論：1）四個元素以下的格都是分配格；

2）五個元素的格僅有兩個格是非分配格(前一個頁面中圖a）、b)），其余三個格(上圖中的圖f、圖g、圖h)都是分配格。2/4/202391計算機(jī)科學(xué)與工程學(xué)院定理17.9

設(shè)<L,∨,∧>是分配格，對于任何a,x,y∈L，如果a∨x＝a∨y且a∧x＝a∧y，則x＝y(tǒng)。

證明：x＝x∧

(a∨x) (吸收律)

＝x∧

(a∨y) (已知a∨x＝a∨y)

＝(x∧a)∨(x∧y) (分配律)

＝(a∧y)∨(x∧y) (已知a∧x＝a∧y)

＝y(tǒng)∧

(a∨x) (交換律，分配律)

＝y(tǒng)∧(a∨y) (已知a∨x＝a∨y)

＝y(tǒng) (吸收律)注意，在定理17.9中，<L,∨,∧>是分配格，a∨x＝a∨y和a∧x＝a∧y三者缺一不可。2/4/202392計算機(jī)科學(xué)與工程學(xué)院定理17.9

設(shè)<L,∨,∧>是分配格，對于任何a,x,y∈L，如果a∨x＝a∨y且a∧x＝a∧y，則x＝y(tǒng)。證明：x＝x∧

(a∨x) (吸收律)

＝x∧

(a∨y) (已知a∨x＝a∨y)

＝(x∧a)∨(x∧y) (分配律)

＝(a∧y)∨(x∧y) (已知a∧x＝a∧y)

＝y(tǒng)∧

(a∨x) (交換律，分配律)

＝y(tǒng)∧(a∨y) (已知a∨x＝a∨y)

＝y(tǒng) (吸收律)注意，在定理17.9中，<L,∨,∧>是分配格，a∨x＝a∨y和a∧x＝a∧y三者缺一不可。2/4/202393計算機(jī)科學(xué)與工程學(xué)院有界格定義17.8設(shè)<L,≤>（或<L,∨，∧>）是一個格，若存在元素a∈L，使得對任意x∈L，都有a≤x(或x≤a)，則稱a為格<L,≤>的最小元(或最大元)，分別記為0(或1)，而具有最大元和最小元的格稱為有界格。根據(jù)最大元“1”和最小元“0”的定義，對任意x∈L，1∧x＝x∧1＝x， 1∨x＝x∨1＝10∧x＝x∧0＝0， 0∨x＝x∨0＝x2/4/202394計算機(jī)科學(xué)與工程學(xué)院有界格定義17.8設(shè)<L,≤>（或<L,∨，∧>）是一個格，若存在元素a∈L，使得對任意x∈L，都有a≤x(或x≤a)，則稱a為格<L,≤>的最小元(或最大元)，分別記為0(或1)，而具有最大元和最小元的格稱為有界格。根據(jù)最大元“1”和最小元“0”的定義，對任意x∈L，1∧x＝x∧1＝x， 1∨x＝x∨1＝10∧x＝x∧0＝0， 0∨x＝x∨0＝x2/4/202395計算機(jī)科學(xué)與工程學(xué)院例如下圖a、b、c所示的格是有界格，其最大元和最小元都是1，0。有限格一定是有界格。但一個有界格則不一定是有限格，如<[0,1]，≤>。2/4/202396計算機(jī)科學(xué)與工程學(xué)院例如下圖a、b、c所示的格是有界格，其最大元和最小元都是1，0。圖12-3．2有限格一定是有界格。但一個有界格則不一定是有限格，如<[0,1]，≤>。2/4/202397計算機(jī)科學(xué)與工程學(xué)院有補(bǔ)格定義17.9、17.10設(shè)<L,∨,∧>為有界格，1和0分別為它的最大元和最小元，對于a∈L。如果存在b∈L，使得：a∧b＝0，a∨b＝1（同時成立），則稱a和b互為補(bǔ)元。若對任意a∈L，都有補(bǔ)元存在，則稱<L,∨,∧>為有補(bǔ)格。2/4/202398計算機(jī)科學(xué)與工程學(xué)院例

如下圖所示的圖，求其所有元素的補(bǔ)元(如果有的話)。2/4/202399計算機(jī)科學(xué)與工程學(xué)院對于圖a（這里設(shè)x的補(bǔ)元為x’） 0'＝1，1'＝0，a'＝e，d'＝c，d'＝e， c'＝d，e'＝a，e'＝d，b無補(bǔ)元。對于圖b 0'＝1，1'＝0，a'＝d，a'＝c， b'＝d，b'＝c，c'＝a，c'＝b， d'＝a，d'＝b因此圖a不是有補(bǔ)格，圖b是有補(bǔ)格。補(bǔ)元如果存在，不一定唯一，那么，在什么條件下可以保證補(bǔ)元是唯一的呢？2/4/2023100計算機(jī)科學(xué)與工程學(xué)院對于圖a（這里設(shè)x的補(bǔ)元為x’） 0'＝1，1'＝0，a'＝e，d'＝c，d'＝e， c'＝d，e'＝a，e'＝d，b無補(bǔ)元。對于圖b 0'＝1，1'＝0，a'＝d，a'＝c， b'＝d，b'＝c，c'＝a，c'＝b， d'＝a，d'＝b因此圖a不是有補(bǔ)格，圖b是有補(bǔ)格。

補(bǔ)元如果存在，不一定唯一，那么，在什么條件下可以保證補(bǔ)元是唯一的呢？2/4/2023101計算機(jī)科學(xué)與工程學(xué)院對于圖a（這里設(shè)x的補(bǔ)元為x’） 0'＝1，1'＝0，a'＝e，d'＝c，d'＝e， c'＝d，e'＝a，e'＝d，b無補(bǔ)元。對于圖b 0'＝1，1'＝0，a'＝d，a'＝c， b'＝d，b'＝c，c'＝a，c'＝b， d'＝a，d'＝b因此圖a不是有補(bǔ)格，圖b是有補(bǔ)格。

補(bǔ)元如果存在，不一定唯一，那么，在什么條件下可以保證補(bǔ)元是唯一的呢？2/4/2023102計算機(jī)科學(xué)與工程學(xué)院定理17.10在有補(bǔ)分配格(既是有補(bǔ)格又是分配格，簡稱為有補(bǔ)分配格)<L,∨,∧>中，如元素a∈L有補(bǔ)元存在，則此元素的補(bǔ)元必唯一。

證明：設(shè)a有兩個補(bǔ)元b和c，由補(bǔ)元的定義知：

a∧b＝0＝a∧c，a∨b＝1＝a∨c

由消去律（分配格所具有）知，b＝c。2/4/2023103計算機(jī)科學(xué)與工程學(xué)院定理17.10在有補(bǔ)分配格(既是有補(bǔ)格又是分配格，簡稱為有補(bǔ)分配格)<L,∨,∧>中，如元素a∈L有補(bǔ)元存在，則此元素的補(bǔ)元必唯一。

證明：

設(shè)a有兩個補(bǔ)元b和c，由補(bǔ)元的定義知：

a∧b＝0＝a∧c，a∨b＝1＝a∨c

由消去律（分配格所具有）知，b＝c。2/4/2023104計算機(jī)科學(xué)與工程學(xué)院定理17.11、17.12（教材p206）

設(shè)<L,∨,∧>是有補(bǔ)分配格，“≤”是該格的自然偏序，則對任意a,b∈L，都有；

(對合律)

；；a≤b

。(DeMorgan律)2/4/2023105計算機(jī)科學(xué)與工程學(xué)院17.4布爾代數(shù)2/4/2023106計算機(jī)科學(xué)與工程學(xué)院布爾代數(shù)定義

稱有補(bǔ)分配格<B,∨,∧>為布爾格。在有補(bǔ)分配格中每個元都有補(bǔ)元而且補(bǔ)元唯一，則可以將求元素的補(bǔ)元“ˉ”作為一種一元運(yùn)算，則此布爾格<B,∨,∧>可記為<B,∨,∧,ˉ,0,1>，此時，稱<B,∨,∧,ˉ,0,1>為布爾代數(shù)。（突出了代數(shù)特征）若一個布爾代數(shù)的元素個數(shù)是有限的，則稱此布爾代數(shù)為有限布爾代數(shù)。2/4/2023107計算機(jī)科學(xué)與工程學(xué)院布爾代數(shù)定義

稱有補(bǔ)分配格<B,∨,∧>為布爾格。在有補(bǔ)分配格中每個元都有補(bǔ)元而且補(bǔ)元惟一，則可以將求元素的補(bǔ)元“ˉ”作為一種一元運(yùn)算，則此布爾格<B,∨,∧>可記為<B,∨,∧,ˉ,0,1>，此時，稱<B,∨,∧,ˉ,0,1>為布爾代數(shù)。（突出了代數(shù)特征）若一個布爾代數(shù)的元素個數(shù)是有限的，則稱此布爾代數(shù)為有限布爾代數(shù)。2/4/2023108計算機(jī)科學(xué)與工程學(xué)院例 如圖(a)、(b)、(c)所示的圖中，圖(a)是一個布爾代數(shù)，但圖(b)、(c)都不是布爾代數(shù)。2/4/2023109計算機(jī)科學(xué)與工程學(xué)院布爾代數(shù)的性質(zhì)布爾代數(shù)是有補(bǔ)分配格，有補(bǔ)分配格<B，∨，∧>必須滿足：是格分配律成立有最大元和最小元（有界）；每個元的補(bǔ)元存在；最大元1和最小元0可以用下面的同一律和零律來描述：在L中存在兩個元素0和1，使得對任意a∈L，有：

a∧1＝a，a∨0＝a；a∨1＝1，a∧0＝0。2/4/2023110計算機(jī)科學(xué)與工程學(xué)院補(bǔ)元的存在可以用下面的互補(bǔ)律來描述：對任意a∈L，存在∈L，使得a∧＝0，a∨＝1。從本章17.1節(jié)知道格可以用交換律、結(jié)合律、吸收律、冪等律來描述。有補(bǔ)分配格就必須滿足交換律、結(jié)合律、吸