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

陳瑜Email：chenyu.inbox@31一月2023離散數(shù)學(xué)計(jì)算機(jī)學(xué)院2023/1/31計(jì)算機(jī)學(xué)院2/128第16章：環(huán)和域16.1環(huán)的定義及其性質(zhì)2023/1/31計(jì)算機(jī)學(xué)院3/128環(huán)和域

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

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

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

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

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

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

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

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

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

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

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

，>是半群（剩余類乘半群），∵對(duì)[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時(shí)，稱為布爾環(huán)。2023/1/31計(jì)算機(jī)學(xué)院7/128例16.2設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即:Zk={[0]，[1]，[2]，…，[k-1]}<Zk

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

，>是半群（剩余類乘半群），∵對(duì)[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時(shí)，稱為布爾環(huán)。2023/1/31計(jì)算機(jī)學(xué)院8/128例16.2設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即:Zk={[0]，[1]，[2]，…，[k-1]}<Zk

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

，>是半群（剩余類乘半群），∵對(duì)[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時(shí)，稱為布爾環(huán)。2023/1/31計(jì)算機(jī)學(xué)院9/128定理16.1(移項(xiàng)法則)設(shè)<R,+,*>是一個(gè)環(huán)，θ是加法幺元，對(duì)任意a，b，cR有:a+b=ca+b-c=θ2023/1/31計(jì)算機(jī)學(xué)院10/128定理16.2設(shè)<R,+,*>是一個(gè)環(huán)，θ是加法幺元，對(duì)任意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*c2023/1/31計(jì)算機(jī)學(xué)院11/128定理16.2設(shè)<R,+,*>是一個(gè)環(huán)，θ是加法幺元，對(duì)任意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

證明:

因?yàn)閍*θ=a*（θ+θ）=(a*θ)+(a*θ)，由移項(xiàng)法則a*θ=θ。同樣，可得θ*a=θ。2023/1/31計(jì)算機(jī)學(xué)院12/128定理16.2設(shè)<R,+,*>是一個(gè)環(huán)，θ是加法幺元，對(duì)任意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*c2023/1/31計(jì)算機(jī)學(xué)院13/128定理16.2設(shè)<R,+,*>是一個(gè)環(huán)，θ是加法幺元，對(duì)任意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證明：因?yàn)?a*(-b))+(a*b)=a*(-b+b)=a*θ=θ,

所以a*(-b)=-(a*b)。同理，(a*b)+((-a)*b)=(a-a)*b=θ,

所以（-a)*b=-(a*b).2023/1/31計(jì)算機(jī)學(xué)院14/128定理16.2設(shè)<R,+,*>是一個(gè)環(huán)，θ是加法幺元，對(duì)任意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*c2023/1/31計(jì)算機(jī)學(xué)院15/128定理16.2設(shè)<R,+,*>是一個(gè)環(huán)，θ是加法幺元，對(duì)任意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).2023/1/31計(jì)算機(jī)學(xué)院16/128定理16.2設(shè)<R,+,*>是一個(gè)環(huán)，θ是加法幺元，對(duì)任意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).2023/1/31計(jì)算機(jī)學(xué)院17/128定理16.2設(shè)<R,+,*>是一個(gè)環(huán)，θ是加法幺元，對(duì)任意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)2023/1/31計(jì)算機(jī)學(xué)院18/128定理16.2設(shè)<R,+,*>是一個(gè)環(huán)，θ是加法幺元，對(duì)任意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)

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

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

>中，[2][3]=[0],[4][3]=[0]。2023/1/31計(jì)算機(jī)學(xué)院19/128定義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是素?cái)?shù)。因?yàn)楫?dāng)m是合數(shù)時(shí)，必有a≥2,b≥2使m=ab，從而[a][b]=[m]=[0],而且[a]和[b]都是零因子。當(dāng)m是素?cái)?shù)時(shí)，不存在a≥2和b≥2使m=ab，因而無(wú)零因子。

2023/1/31計(jì)算機(jī)學(xué)院20/128定義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是素?cái)?shù)。因?yàn)楫?dāng)m是合數(shù)時(shí)，必有a≥2,b≥2使m=ab，從而[a][b]=[m]=[0],而且[a]和[b]都是零因子。當(dāng)m是素?cái)?shù)時(shí)，不存在a≥2和b≥2使m=ab，因而無(wú)零因子。

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

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

證明（模k）剩余類環(huán)<Zk

，，>無(wú)零因子當(dāng)且僅當(dāng)k是素?cái)?shù)。證明：∵當(dāng)k是合數(shù)時(shí)，必有a≥2、b≥2，使得k=ab，從而[a][b]=[k]=[0]，即[a]、[b]都是零因子。又∵當(dāng)k是素?cái)?shù)時(shí)，不存在a≥2、b≥2，使得k=ab，從而無(wú)零因子。

∴結(jié)論成立。2023/1/31計(jì)算機(jī)學(xué)院24/128定理16.3

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

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

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

2023/1/31計(jì)算機(jī)學(xué)院25/128定理16.3

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

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

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

2023/1/31計(jì)算機(jī)學(xué)院26/128定理16.3

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

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

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

2023/1/31計(jì)算機(jī)學(xué)院27/128定理16.3設(shè)<R,+,*>是一個(gè)環(huán)，則R中無(wú)零因子當(dāng)且僅當(dāng)對(duì)a,x,yR，當(dāng)a≠0時(shí)，

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

（即滿足可約律）定義16.4

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

設(shè)<S,+,*>和<T,,>是兩個(gè)環(huán)，如在集合S與T之間存在映射f：ST，使得對(duì)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的一個(gè)同態(tài)象。當(dāng)f是一個(gè)滿射時(shí)，則稱f為滿同態(tài)；當(dāng)f是一個(gè)雙射時(shí)，則稱f是環(huán)同構(gòu)映射；2023/1/31計(jì)算機(jī)學(xué)院29/128例16.5存在整數(shù)環(huán)<Z,+,*>到模m剩余類環(huán)<Zm,,>的同態(tài)，因?yàn)槲覀兛梢远x映射f：Z→Zm如下：使對(duì)所有x∈Z，

f(x)=xmodm.

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

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

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

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

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

一般情況下，整環(huán)不是域，但當(dāng)環(huán)的元素個(gè)數(shù)有限時(shí)，有以下結(jié)論：定理16.5有限整環(huán)<R,+,*>必是域。(教材p198)θ是加法幺元2023/1/31計(jì)算機(jī)學(xué)院32/128例16.6實(shí)數(shù)環(huán)<R,+,×>、有理數(shù)環(huán)<Q,+,×>、剩余類環(huán)<Zp，，>(p是素?cái)?shù)）都是域。整數(shù)環(huán)<Z,+,×>、剩余類環(huán)<Zm，，>(m是合數(shù)）都不是域。因?yàn)?lt;Z-{0}，×>、<Zm–{[0]}，>都不是群。2023/1/31計(jì)算機(jī)學(xué)院33/128習(xí)題熟記相關(guān)概念2023/1/31計(jì)算機(jī)學(xué)院34/128第17章格與布爾代數(shù)17.1格的定義與性質(zhì)2023/1/31計(jì)算機(jī)學(xué)院35/128格與布爾代數(shù)

下面討論另外兩個(gè)重要的代數(shù)系統(tǒng)—格與布爾代數(shù)，這兩個(gè)代數(shù)系統(tǒng)與前面討論的代數(shù)系統(tǒng)之間存在著一個(gè)重要區(qū)別：在格與布爾代數(shù)中，偏序關(guān)系具有重要意義。2023/1/31計(jì)算機(jī)學(xué)院36/128本章主要介紹以下幾點(diǎn)：格的概念和基本性質(zhì)子格的定義特殊的格及性質(zhì)布爾代數(shù)的概念和基本性質(zhì)2023/1/31計(jì)算機(jī)學(xué)院37/128格的定義定義17.1（代數(shù)格）設(shè)<L，∨，∧>是一個(gè)代數(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，∨，∧>是一個(gè)代數(shù)格。2個(gè)典型的格:

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

命題邏輯系統(tǒng)<，∨，∧>代數(shù)格2023/1/31計(jì)算機(jī)學(xué)院38/128定理17.1

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

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

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

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

證明

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

a=a∧b(a≤b)=b∧a(交換律)=b,(b≤a),

即反對(duì)稱性成立。

2023/1/31計(jì)算機(jī)學(xué)院44/128定理17.2設(shè)<L，∨，∧>是一個(gè)代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個(gè)偏序格；

證明

（首先證明<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，傳遞性成立。2023/1/31計(jì)算機(jī)學(xué)院45/128定理17.2設(shè)<L，∨，∧>是一個(gè)代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個(gè)偏序格；

證明其次，證明對(duì)任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)

所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y

是{x，y}的一個(gè)下界?，F(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，只需在上述證明中把∧換成∨，把∨換成∧即可。2023/1/31計(jì)算機(jī)學(xué)院46/128定理17.2設(shè)<L，∨，∧>是一個(gè)代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個(gè)偏序格；

證明

其次，證明對(duì)任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)

所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y

是{x，y}的一個(gè)下界。

現(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，只需在上述證明中把∧換成∨，把∨換成∧即可。2023/1/31計(jì)算機(jī)學(xué)院47/128定理17.2設(shè)<L，∨，∧>是一個(gè)代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個(gè)偏序格；

證明

其次，證明對(duì)任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)

所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y

是{x，y}的一個(gè)下界。現(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，只需在上述證明中把∧換成∨，把∨換成∧即可。2023/1/31計(jì)算機(jī)學(xué)院48/128定理17.2設(shè)<L，∨，∧>是一個(gè)代數(shù)格，定義格上的自然偏序“”：ab當(dāng)且僅當(dāng)a∧b=a，則<L，>是一個(gè)偏序格；

證明

其次，證明對(duì)任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)

所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y

是{x，y}的一個(gè)下界。

現(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é)論，命題得證。2023/1/31計(jì)算機(jī)學(xué)院49/128定理17.3設(shè)<L，>是一個(gè)偏序格，在格上定義“∨”、“∧”：a∧b=glb（a，b），a∨b=lub（a，b），則<L，∨，∧>是一個(gè)代數(shù)格。

證明從運(yùn)算和的定義可以看出，它們滿足交換律、結(jié)合律和冪等律?，F(xiàn)證明吸收律成立。事實(shí)上，由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表明：格的兩種定義是完全等價(jià)的。以后我們將不特別加以區(qū)分，而是根據(jù)需要采用相應(yīng)的定義來(lái)說明問題。2023/1/31計(jì)算機(jī)學(xué)院50/128定理17.3設(shè)<L，>是一個(gè)偏序格，在格上定義“∨”、“∧”：a∧b=glb（a，b），a∨b=lub（a，b），則<L，∨，∧>是一個(gè)代數(shù)格。

證明從運(yùn)算和的定義可以看出，它們滿足交換律、結(jié)合律和冪等律。現(xiàn)證明吸收律成立。事實(shí)上，由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表明：格的兩種定義是完全等價(jià)的。以后我們將不特別加以區(qū)分，而是根據(jù)需要采用相應(yīng)的定義來(lái)說明問題。2023/1/31計(jì)算機(jī)學(xué)院51/128定理17.3設(shè)<L，>是一個(gè)偏序格，在格上定義“∨”、“∧”：a∧b=glb（a，b），a∨b=lub（a，b），則<L，∨，∧>是一個(gè)代數(shù)格。

證明從運(yùn)算和的定義可以看出，它們滿足交換律、結(jié)合律和冪等律。現(xiàn)證明吸收律成立。事實(shí)上，由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表明：格的兩種定義是完全等價(jià)的。以后我們將不特別加以區(qū)分，而是根據(jù)需要采用相應(yīng)的定義來(lái)說明問題。2023/1/31計(jì)算機(jī)學(xué)院52/128例如圖所示的八個(gè)偏序集都是格；2023/1/31計(jì)算機(jī)學(xué)院53/1282023/1/31計(jì)算機(jī)學(xué)院54/128如圖所示的四個(gè)偏序集都不是格。2023/1/31計(jì)算機(jī)學(xué)院55/128作業(yè)熟練掌握相關(guān)概念、定理2023/1/31計(jì)算機(jī)學(xué)院56/12817.2子格與格同態(tài)2023/1/31計(jì)算機(jī)學(xué)院57/128定義17.3

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

設(shè)L是由18的正因子組成的集合，則L關(guān)于整除關(guān)系構(gòu)成的逆關(guān)系是倍數(shù)關(guān)系；設(shè)倍數(shù)關(guān)系用“‖”表示，那么<L，‖>是格，并和<L，∣>互為對(duì)偶。在一個(gè)格中的最大（?。┰厥菍?duì)偶格中的最?。ù螅┰患磧蓚€(gè)對(duì)偶格的Hasse圖是相互顛倒的。2023/1/31計(jì)算機(jī)學(xué)院59/128格的性質(zhì)與同態(tài)定義17.4設(shè)<L，>和<L，′>是兩個(gè)偏序格，如果偏序關(guān)系′是的逆關(guān)系，則稱此兩個(gè)偏序格為對(duì)偶格。設(shè)L是由18的正因子組成的集合，則L關(guān)于整除關(guān)系構(gòu)成的逆關(guān)系是倍數(shù)關(guān)系；設(shè)倍數(shù)關(guān)系用“‖”表示，那么<L，‖>是格，并和<L，∣>互為對(duì)偶。

在一個(gè)格中的最大（?。┰厥菍?duì)偶格中的最?。ù螅┰?；即兩個(gè)對(duì)偶格的Hasse圖是相互顛倒的。2023/1/31計(jì)算機(jī)學(xué)院60/128格的性質(zhì)與同態(tài)定義17.4設(shè)<L，>和<L，′>是兩個(gè)偏序格，如果偏序關(guān)系′是的逆關(guān)系，則稱此兩個(gè)偏序格為對(duì)偶格。設(shè)L是由18的正因子組成的集合，則L關(guān)于整除關(guān)系構(gòu)成的逆關(guān)系是倍數(shù)關(guān)系；設(shè)倍數(shù)關(guān)系用“‖”表示，那么<L，‖>是格，并和<L，∣>互為對(duì)偶。

在一個(gè)格中的最大（?。┰厥菍?duì)偶格中的最?。ù螅┰?；即兩個(gè)對(duì)偶格的Hasse圖是相互顛倒的。2023/1/31計(jì)算機(jī)學(xué)院61/128定義17.5設(shè)<L，∨，∧>是一個(gè)格，E是格中的公式。將E中的0（最小元）和1（最大元）互換、∨和∧互換后得到的新公式E*稱為E的對(duì)偶公式。對(duì)偶原理：設(shè)X和Y是格<L，∨，∧>上的兩個(gè)公式，X*和Y*是相對(duì)應(yīng)的對(duì)偶公式。如果X=Y，則X*=Y*。定理17.4設(shè)X和Y是格<L，∨，∧>上的兩個(gè)公式，是對(duì)應(yīng)的偏序。如果XY，則Y*X*。2023/1/31計(jì)算機(jī)學(xué)院62/128定義17.5設(shè)<L，∨，∧>是一個(gè)格，E是格中的公式。將E中的0（最小元）和1（最大元）互換、∨和∧互換后得到的新公式E*稱為E的對(duì)偶公式。對(duì)偶原理：設(shè)X和Y是格<L，∨，∧>上的兩個(gè)公式，X*和Y*是相對(duì)應(yīng)的對(duì)偶公式。如果X=Y，則X*=Y*。定理17.4設(shè)X和Y是格<L，∨，∧>上的兩個(gè)公式，是對(duì)應(yīng)的偏序。如果XY，則Y*X*。2023/1/31計(jì)算機(jī)學(xué)院63/128定義17.5設(shè)<L，∨，∧>是一個(gè)格，E是格中的公式。將E中的0（最小元）和1（最大元）互換、∨和∧互換后得到的新公式E*稱為E的對(duì)偶公式。對(duì)偶原理：設(shè)X和Y是格<L，∨，∧>上的兩個(gè)公式，X*和Y*是相對(duì)應(yīng)的對(duì)偶公式。如果X=Y，則X*=Y*。定理17.4設(shè)X和Y是格<L，∨，∧>上的兩個(gè)公式，是對(duì)應(yīng)的偏序。如果XY，則Y*X*。

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

XYX∧Y=X（偏序定義）X*∨Y*=X*

（對(duì)偶原理）Y*X*

（偏序定義）2023/1/31計(jì)算機(jī)學(xué)院64/128定理17.5、17.6設(shè)<L，∨，∧>是一個(gè)格，是對(duì)應(yīng)的偏序，a,b,c,dL，則：(教材p202)a≤ba∨c≤b∨c a≤ba∧c≤b∧c a≤b且c≤da∧c≤b∧da≤b且c≤da∨c≤b∨da≤b且a≤ca≤b∧ca≤c且b≤ca∨b≤ca∨(b∧c)≤(a∨b)∧(a∨c) (a∧b)∨(a∧c)≤a∧(b∨c)

(保序性)(準(zhǔn)分配關(guān)系)2023/1/31計(jì)算機(jī)學(xué)院65/128定理17.5、17.6設(shè)<L，∨，∧>是一個(gè)格，是對(duì)應(yīng)的偏序，a,b,c,dL，則：(教材p202)a≤ba∨c≤b∨c a≤ba∧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。2023/1/31計(jì)算機(jī)學(xué)院66/128格的同態(tài)與同構(gòu)

將代數(shù)系統(tǒng)的同態(tài)與同構(gòu)應(yīng)用于格，可以獲得格的同態(tài)與同構(gòu)定義：定義17.6設(shè)<L,∨，∧>和<S，，>是兩個(gè)格，ψ是L到S的映射。如果對(duì)任意x,y∈L，都有：

ψ(x∨y)＝ψ(x)ψ(y)ψ(x∧y)＝ψ(x)ψ(y)，則稱ψ為從格<L,∨，∧>到格<S，，>的格同態(tài)映射，當(dāng)ψ分別是單射、滿射和雙射時(shí)，ψ分別稱為單一格同態(tài)、滿格同態(tài)和格同構(gòu)。2023/1/31計(jì)算機(jī)學(xué)院67/128格的同態(tài)與同構(gòu)

將代數(shù)系統(tǒng)的同態(tài)與同構(gòu)應(yīng)用于格，可以獲得格的同態(tài)與同構(gòu)定義：定義17.6設(shè)<L,∨，∧>和<S，，>是兩個(gè)格，ψ是L到S的映射。如果對(duì)任意x,y∈L，都有：

ψ(x∨y)＝ψ(x)ψ(y)ψ(x∧y)＝ψ(x)ψ(y)，則稱ψ為從格<L,∨，∧>到格<S，，>的格同態(tài)映射，當(dāng)ψ分別是單射、滿射和雙射時(shí)，ψ分別稱為單一格同態(tài)、滿格同態(tài)和格同構(gòu)。2023/1/31計(jì)算機(jī)學(xué)院68/128例設(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

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

，lcm，gcd><2{a,b}，>對(duì)應(yīng)的代數(shù)格為<2{a,b}，∪，∩>∴f(lcm(1,3))=f(3)==∪=f(1)∪f(wàn)(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(wàn)(3)f(gcd(2,3))=f(1)=={a}∩=f(2)∩f(3)

其余情況也可一一驗(yàn)證，又因?yàn)槭请p射，所以，命題得證。2023/1/31計(jì)算機(jī)學(xué)院69/128例設(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

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

，lcm，gcd><2{a,b}，>對(duì)應(yīng)的代數(shù)格為<2{a,b}，∪，∩>∴f(lcm(1,3))=f(3)==∪=f(1)∪f(wàn)(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(wàn)(3)f(gcd(2,3))=f(1)=={a}∩=f(2)∩f(3)

其余情況也可一一驗(yàn)證，又因?yàn)槭请p射，所以，命題得證。2023/1/31計(jì)算機(jī)學(xué)院70/128例設(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

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

，lcm，gcd><2{a,b}，>對(duì)應(yīng)的代數(shù)格為<2{a,b}，∪，∩>∴f(lcm(1,3))=f(3)==∪=f(1)∪f(wàn)(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(wàn)(3)f(gcd(2,3))=f(1)=={a}∩=f(2)∩f(3)

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

f(a)

f(b)；

證明：對(duì)a，bL1，由f是函數(shù)，所以有f(a)、f(b)L2， 因?yàn)閍ba∧b＝a，于是，由同態(tài)等式知：f(a)＝f(a∧b)＝f(a)f(b)

所以：f(a)f(b)。 即：對(duì)a，bL1，abf(a)f(b)2023/1/31計(jì)算機(jī)學(xué)院72/128保序定理定理17.7設(shè)<L1，∨，∧>和<L2，，>是兩個(gè)格，對(duì)應(yīng)的偏序關(guān)系為、，則有：如果f：L1→L2是一個(gè)格同態(tài)，則對(duì)a，bL1，abf(a)

f(b)；

證明：對(duì)a，bL1，由f是函數(shù)，所以有f(a)、f(b)L2， 因?yàn)閍ba∧b＝a，于是，由同態(tài)等式知：f(a)＝f(a∧b)＝f(a)f(b)

所以：f(a)f(b)。 即：對(duì)a，bL1，abf(a)f(b)2023/1/31計(jì)算機(jī)學(xué)院73/128定理17.8

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

證明：

2023/1/31計(jì)算機(jī)學(xué)院74/128定理17.8

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

證明：當(dāng)f是L到P的格同構(gòu)時(shí)，它必須滿足保序定理，因此保序?yàn)楸匾獥l件是成立的。至于充分條件，只需證明由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)的一個(gè)上界。2023/1/31計(jì)算機(jī)學(xué)院75/128定理17.8

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

證明：當(dāng)f是L到P的格同構(gòu)時(shí)，它必須滿足保序定理，因此保序?yàn)楸匾獥l件是成立的。至于充分條件，只需證明由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)的一個(gè)上界。a≤c且b≤ca∨b≤c2023/1/31計(jì)算機(jī)學(xué)院76/128定理17.8

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

證明：

剩下的任務(wù)要證明f(c)是f(a)和f(b)的最小上界。設(shè)f(d)是f(a)和f(b)的任意一個(gè)上界，即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)。2023/1/31計(jì)算機(jī)學(xué)院77/128定理17.8

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

證明：剩下的任務(wù)要證明f(c)是f(a)和f(b)的最小上界。設(shè)f(d)是f(a)和f(b)的任意一個(gè)上界，即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)。2023/1/31計(jì)算機(jī)學(xué)院78/128例設(shè)L={1，2，3，12}，在<L，|>和冪集格<2L，>之間構(gòu)造映射f：L→2L，使得對(duì)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時(shí),f(x)f(y)

所以，f是保序映射。

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

即f(lcm(2,3))≠f(2)∪f(wàn)(3)

所以f不是<L，|>到<2L，>的格同態(tài)。2023/1/31計(jì)算機(jī)學(xué)院79/128例設(shè)L={1，2，3，12}，在<L，|>和冪集格<2L，>之間構(gòu)造映射f：L→2L，使得對(duì)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時(shí),f(x)f(y)

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

即f(lcm(2,3))≠f(2)∪f(wàn)(3)

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

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

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

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

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

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

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

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

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

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

對(duì)任意P、Q、R∈2A

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

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

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

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

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

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

2)

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

所以，格<P,∧,∨>是一個(gè)分配格。2023/1/31計(jì)算機(jī)學(xué)院87/128例

證明圖中a）、b）所示的兩個(gè)格都不是分配格。2023/1/31計(jì)算機(jī)學(xué)院88/128證明在圖a）、b）中都取b,c,d三個(gè)元素來(lái)驗(yàn)證。用“∧”和“∨”表示它們的交和并運(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)。故它們都不是分配格。2023/1/31計(jì)算機(jī)學(xué)院89/128證明在圖a）、b）中都取b,c,d三個(gè)元素來(lái)驗(yàn)證。用“∧”和“∨”表示它們的交和并運(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)。故它們都不是分配格。2023/1/31計(jì)算機(jī)學(xué)院90/128結(jié)論一個(gè)格是分配格，當(dāng)且僅當(dāng)該格中沒有任何子格與圖中的兩個(gè)五元素格中的任何一個(gè)同構(gòu)。2023/1/31計(jì)算機(jī)學(xué)院91/128如圖a）～h）所示的八個(gè)圖都是分配格嗎？結(jié)論：1）四個(gè)元素以下的格都是分配格；

2）五個(gè)元素的格僅有兩個(gè)格是非分配格(前一個(gè)頁(yè)面中圖a）、b)），其余三個(gè)格(上圖中的圖f、圖g、圖h)都是分配格。2023/1/31計(jì)算機(jī)學(xué)院92/128定理17.9

設(shè)<L,∨,∧>是分配格，對(duì)于任何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三者缺一不可。2023/1/31計(jì)算機(jī)學(xué)院93/128定理17.9

設(shè)<L,∨,∧>是分配格，對(duì)于任何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三者缺一不可。2023/1/31計(jì)算機(jī)學(xué)院94/128有界格定義17.8設(shè)<L,≤>（或<L,∨，∧>）是一個(gè)格，若存在元素a∈L，使得對(duì)任意x∈L，都有a≤x(或x≤a)，則稱a為格<L,≤>的最小元(或最大元)，分別記為0(或1)，而具有最大元和最小元的格稱為有界格。根據(jù)最大元“1”和最小元“0”的定義，對(duì)任意x∈L，1∧x＝x∧1＝x， 1∨x＝x∨1＝10∧x＝x∧0＝0， 0∨x＝x∨0＝x2023/1/31計(jì)算機(jī)學(xué)院95/128有界格定義17.8設(shè)<L,≤>（或<L,∨，∧>）是一個(gè)格，若存在元素a∈L，使得對(duì)任意x∈L，都有a≤x(或x≤a)，則稱a為格<L,≤>的最小元(或最大元)，分別記為0(或1)，而具有最大元和最小元的格稱為有界格。根據(jù)最大元“1”和最小元“0”的定義，對(duì)任意x∈L，1∧x＝x∧1＝x， 1∨x＝x∨1＝10∧x＝x∧0＝0， 0∨x＝x∨0＝x2023/1/31計(jì)算機(jī)學(xué)院96/128例如下圖a、b、c所示的格是有界格，其最大元和最小元都是1，0。有限格一定是有界格。但一個(gè)有界格則不一定是有限格，如<[0,1]，≤>。2023/1/31計(jì)算機(jī)學(xué)院97/128例如下圖a、b、c所示的格是有界格，其最大元和最小元都是1，0。圖12-3．2有限格一定是有界格。但一個(gè)有界格則不一定是有限格，如<[0,1]，≤>。2023/1/31計(jì)算機(jī)學(xué)院98/128有補(bǔ)格定義17.9、17.10設(shè)<L,∨,∧>為有界格，1和0分別為它的最大元和最小元，對(duì)于a∈L。如果存在b∈L，使得：a∧b＝0，a∨b＝1（同時(shí)成立），則稱a和b互為補(bǔ)元。若對(duì)任意a∈L，都有補(bǔ)元存在，則稱<L,∨,∧>為有補(bǔ)格。2023/1/31計(jì)算機(jī)學(xué)院99/128例

如下圖所示的圖，求其所有元素的補(bǔ)元(如果有的話)。2023/1/31計(jì)算機(jī)學(xué)院100/128對(duì)于圖a（這里設(shè)x的補(bǔ)元為x’）

0'＝1，1'＝0，a'＝e，d'＝c，d'＝e，

c'＝d，e'＝a，e'＝d，b無(wú)補(bǔ)元。對(duì)于圖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ǔ)元是唯一的呢？2023/1/31計(jì)算機(jī)學(xué)院101/128對(duì)于圖a（這里設(shè)x的補(bǔ)元為x’）

0'＝1，1'＝0，a'＝e，d'＝c，d'＝e，

c'＝d，e'＝a，e'＝d，b無(wú)補(bǔ)元。對(duì)于圖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ǔ)元是唯一的呢？2023/1/31計(jì)算機(jī)學(xué)院102/128對(duì)于圖a（這里設(shè)x的補(bǔ)元為x’）

0'＝1，1'＝0，a'＝e，d'＝c，d'＝e，

c'＝d，e'＝a，e'＝d，b無(wú)補(bǔ)元。對(duì)于圖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ǔ)元是唯一的呢？2023/1/31計(jì)算機(jī)學(xué)院103/128定理17.10在有補(bǔ)分配格(既是有補(bǔ)格又是分配格，簡(jiǎn)稱為有補(bǔ)分配格)<L,∨,∧>中，如元素a∈L有補(bǔ)元存在，則此元素的補(bǔ)元必唯一。

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

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

由消去律（分配格所具有）知，b＝c。2023/1/31計(jì)算機(jī)學(xué)院104/128定理17.10在有補(bǔ)分配格(既是有補(bǔ)格又是分配格，簡(jiǎn)稱為有補(bǔ)分配格)<L,∨,∧>中，如元素a∈L有補(bǔ)元存在，則此元素的補(bǔ)元必唯一。

證明：

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

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

由消去律（分配格所具有）知，b＝c。2023/1/31計(jì)算機(jī)學(xué)院105/128定理17.11、17.12（教材p206）

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

；；a≤b

。(DeMorgan律)2023/1/31計(jì)算機(jī)學(xué)院106/12817.4布爾代數(shù)2023/1/31計(jì)算機(jī)學(xué)院107/128布爾代數(shù)定義稱有補(bǔ)分配格<B,∨,∧>為布爾格。在有補(bǔ)分配格中每個(gè)元都有補(bǔ)元而且補(bǔ)元唯一，則可以將求元素的補(bǔ)元“ˉ”