離散數(shù)學(xué).環(huán)與域

1第1頁，共38頁，2023年，2月20日，星期二環(huán)的定義定義

設(shè)<R,+,·>是代數(shù)系統(tǒng)，+和·是二元運算.如果滿足以下條件:

（1）<R,+>構(gòu)成交換群

（2）<R,·>構(gòu)成半群

（3）·運算關(guān)于+運算適合分配律則稱<R,+,·>是一個環(huán).

2第2頁，共38頁，2023年，2月20日，星期二環(huán)中的術(shù)語通常稱+運算為環(huán)中的加法，·運算為環(huán)中的乘法.環(huán)中加法幺元記作0.乘法幺元（如果存在）記作1.環(huán)中加法幺元0恰好是乘法的零元.對任何元素x，稱x的加法逆元為負元，記作x.若x存在乘法逆元的話，則稱之為逆元，記作x1.3第3頁，共38頁，2023年，2月20日，星期二環(huán)的實例

(1)整數(shù)集、有理數(shù)集、實數(shù)集和復(fù)數(shù)集關(guān)于普通的加法和乘法構(gòu)成環(huán)，分別稱為整數(shù)環(huán)Z，有理數(shù)環(huán)Q，實數(shù)環(huán)R和復(fù)數(shù)環(huán)C.

(2)n(n≥2)階實矩陣的集合Mn(R)關(guān)于矩陣的加法和乘法構(gòu)成環(huán)，稱為n階實矩陣環(huán).(3)集合的冪集P(B)關(guān)于集合的對稱差運算和交運算構(gòu)成環(huán).

(4)設(shè)Zn＝{0,1,...,n－1}，和分別表示模n的加法和乘法，則<Zn,,>構(gòu)成環(huán)，稱為模n的整數(shù)環(huán).

4第4頁，共38頁，2023年，2月20日，星期二特殊的環(huán)定義

設(shè)<R,+,·>是環(huán)，

(1)若環(huán)中乘法·適合交換律，則稱R是交換環(huán).

(2)若環(huán)中乘法·存在幺元，則稱R是含幺環(huán).

(3)若a,b∈R，ab=0

a=0∨b=0，則稱R是無零因子環(huán).

(4)若R既是交換環(huán)、含幺環(huán)，也是無零因子環(huán)，則稱R是整環(huán).(5)若R為整環(huán)，|R|>1,且aR*=R-{0}，a-1R,則稱R為域.5第5頁，共38頁，2023年，2月20日，星期二

零因子的定義與存在條件設(shè)<R,+,>是環(huán)，若存在ab=0,且a0,b0,稱a為左零因子，b為右零因子，環(huán)R不是無零因子環(huán).實例<Z6,,>，其中23=0，2和3都是零因子.無零因子環(huán)的條件：可以證明：ab=0a=0b=0消去律6第6頁，共38頁，2023年，2月20日，星期二特殊環(huán)的實例(1)整數(shù)環(huán)Z、有理數(shù)環(huán)Q、實數(shù)環(huán)R、復(fù)數(shù)環(huán)C都是交換環(huán)、含幺環(huán)、無零因子環(huán)和整環(huán).其中除Z之外都是域(2)令2Z={2z|z∈Z}，則<2Z,+,·>構(gòu)成交換環(huán)和無零因子環(huán).但不是含幺環(huán)和整環(huán).(3)設(shè)nZ,n2,則n階實矩陣的集合Mn(R)關(guān)于矩陣加法和乘法構(gòu)成環(huán)，它是含幺環(huán)，但不是交換環(huán)和無零因子環(huán)，也不是整環(huán).(4)<Z6,,>構(gòu)成環(huán)，它是交換環(huán)、含幺環(huán)，但不是無零因子環(huán)和整環(huán).注意：對于一般的n,Zn是整環(huán)且是域n是素數(shù).7第7頁，共38頁，2023年，2月20日，星期二例題判斷下列集合和給定運算是否構(gòu)成環(huán)、整環(huán)和域.(1)A={a+bi|a,bQ},i2=1,運算為復(fù)數(shù)加法和乘法.(2)A={2z+1|zZ},運算為普通加法和乘法

(3)A={2z|zZ},運算為普通加法和乘法

(4)A={x|x≥0∧xZ},運算為普通加法和乘法.(5)，運算為普通加法和乘法解(2),(4),(5)不是環(huán).為什么？

(1)是環(huán),是整環(huán),也是域.(3)是環(huán),不是整環(huán)和域.

8第8頁，共38頁，2023年，2月20日，星期二環(huán)的性質(zhì)定理設(shè)<R,+,·>是環(huán)，則

(1)a∈R，a·0=0·a=0

(2)a,b∈R，(a)b=a(b)=ab

(3)a,b∈R，(a)(b)=ab

(4)a,b,c∈R，a(bc)=abac，

(bc)a=baca9第9頁，共38頁，2023年，2月20日，星期二環(huán)中的運算環(huán)中加法的交換律、結(jié)合律；乘法的結(jié)合律；乘法對加法的分配律.例在環(huán)中計算(a+b)3,(ab)2解(a+b)3=(a+b)(a+b)(a+b)

=(a2+ba+ab+b2)(a+b)

=a3+ba2+aba+b2a+a2b+bab+ab2+b3

(ab)2=(ab)(ab)=a2baab+b2注：在初等代數(shù)中的加法和乘法運算都是在實數(shù)域中進行，乘法可交換10第10頁，共38頁，2023年，2月20日，星期二6.3格與布爾代數(shù)格的定義與實例格的性質(zhì)對偶原理交換律、結(jié)合律、冪等律、吸收律格的等價定義子格格的同構(gòu)特殊的格：分配格、有界格、有補格、布爾格11第11頁，共38頁，2023年，2月20日，星期二格的定義定義設(shè)<S,?>是偏序集，如果x,y?S，{x,y}都有最小上界和最大下界，則稱S關(guān)于偏序?構(gòu)成一個格。

由于最小上界和最大下界的惟一性，可以把求{x,y}的最小上界和最大下界看成x與y的二元運算∨和∧，即x∨y和x∧y分別表示x與y的最小上界和最大下界.注意：這里出現(xiàn)的∨和∧符號只代表格中的運算，而不再有其他的含義.

12第12頁，共38頁，2023年，2月20日，星期二格的實例例設(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>.13第13頁，共38頁，2023年，2月20日，星期二例判斷下列偏序集是否構(gòu)成格，并說明理由.(1)<P(B),>，其中P(B)是集合B的冪集.(2)<Z,≤>，其中Z是整數(shù)集，≤為小于等于關(guān)系.(3)偏序集的哈斯圖分別在下圖給出.格的實例（續(xù)）解(1)是格.稱<P(B),>為B的冪集格.

(2)是格.

(3)都不是格.14第14頁，共38頁，2023年，2月20日，星期二格的性質(zhì)：對偶原理定義設(shè)f是含有格中元素以及符號=,?,?,∨和∧的命題.令f*是將f中的?替換成?,?替換成?,∨替換成∧,∧替換成∨所得到的命題.稱f*為f的對偶命題.例如,在格中：f是(a∨b)∧c?c,f*是(a∧b)∨c?c.格的對偶原理：設(shè)f是含格中元素以及符號=,?,?,∨和∧等的命題.若f對一切格為真,則f的對偶命題f*也對一切格為真.

例如,若對一切格L都有a,b∈L,a∧b?a，那么對一切格L都有a,b∈L,a∨b?a

15第15頁，共38頁，2023年，2月20日，星期二格的性質(zhì)：算律定理設(shè)<L,?>是格,則運算∨和∧適合交換律、結(jié)合律、冪等律和吸收律,即

(1)a,b∈L

有

a∨b=b∨a,a∧b=b∧a

(2)a,b,c∈L

有

(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)

(3)a∈L

有

a∨a=a,a∧a=a

(4)a,b∈L

有

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

16第16頁，共38頁，2023年，2月20日，星期二算律的證明證(1)交換律.

a∨b是{a,b}的最小上界

b∨a是{b,a}的最小上界

{a,b}={b,a}

a∨b=b∨a.

由對偶原理,a∧b=b∧a得證.17第17頁，共38頁，2023年，2月20日，星期二算律的證明（續(xù)）

(2)結(jié)合律.由最小上界的定義有

(a∨b)∨c?a∨b?a(I)(a∨b)∨c?a∨b?b(II)

(a∨b)∨c?c(III)

由式(II)和(III)有

(a∨b)∨c?b∨c(IV)

由式(I)和(IV)有(a∨b)∨c?a∨(b∨c).同理可證

(a∨b)∨c?a∨(b∨c).根據(jù)偏序的反對稱性得到

(a∨b)∨c=a∨(b∨c).由對偶原理,(a∧b)∧c=

a∧(b∧c)得證.

18第18頁，共38頁，2023年，2月20日，星期二算律的證明（續(xù)）

(3)

冪等律.顯然a?a∨a,又由a?a得a∨a?a.由反對稱性a∨a=a.用對偶原理,a∧a=a得證.

(4)吸收律.顯然有

a∨(a∧b)?a(V)由a?a,a∧b?a可得

a∨(a∧b)?a(VI)由式(V)和(VI)可得a∨(a∧b)=a根據(jù)對偶原理,a∧(a∨b)=a得證.19第19頁，共38頁，2023年，2月20日，星期二格作為代數(shù)系統(tǒng)的定義定理設(shè)<S,?,°>是具有兩個二元運算的代數(shù)系統(tǒng),若對于?和運算適合交換律、結(jié)合律、吸收律,則可以適當(dāng)定義S中的偏序?,使得<S,?>構(gòu)成格,且a,b∈S有

a∧b=a?b,a∨b=a

°

b.根據(jù)定理,可以給出格的另一個等價定義.

定義設(shè)<S,?,°>是代數(shù)系統(tǒng),?和

°是二元運算,如果?和

°

運算滿足交換律、結(jié)合律和吸收律,則<S,?,°>構(gòu)成格.20第20頁，共38頁，2023年，2月20日，星期二子格的定義及判別定義設(shè)<L,∧,∨>是格,S是L的非空子集,若S關(guān)于L中運算∧和∨仍構(gòu)成格,則稱S是L的子格.

例設(shè)格L如圖所示.令

S1={a,e,f,g},S2={a,b,e,g}S1不是L的子格,S2是L的子格.因為對于

e,fS1，e∧fS1.

21第21頁，共38頁，2023年，2月20日，星期二格同態(tài)定義設(shè)L1和L2是格,f:L1→L2,若a,b∈L1有

f(a∧b)=f(a)∧f(b),f(a∨b)=f(a)∨f(b)成立,則稱f為格L1到L2的同態(tài)映射,簡稱格同態(tài).

22第22頁，共38頁，2023年，2月20日，星期二分配格定義定義設(shè)<L,∧,∨>是格,若a,b,c∈L,有

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

a∨(b∧c)=(a∨b)∧(a∨c)則稱L為分配格.注意：以上條件互為充分必要條件這兩個等式中只要有一條成立，另一條一定成立.在證明L為分配格時,只須證明其中的一個等式即可.23第23頁，共38頁，2023年，2月20日，星期二分配格的定義（續(xù)）L1和L2是分配格,L3和L4不是分配格.在L3中,b∧(c∨d)=b，(b∧c)∨(b∧d)=a

在L4中,c∨(b∧d)=c，(c∨b)∧(c∨d)=d

稱L3為鉆石格,L4為五角格.24第24頁，共38頁，2023年，2月20日，星期二分配格的判定及其性質(zhì)定理設(shè)L是格,則L是分配格當(dāng)且僅當(dāng)L不含有與鉆石格或五角格同構(gòu)的子格.

證明省略.定理格L是分配格當(dāng)且僅當(dāng)a,b,c∈L,

a∧b=a∧c且a∨b=a∨cb=c.

推論

(1)小于五元的格都是分配格.

(2)任何一條鏈都是分配格.

25第25頁，共38頁，2023年，2月20日，星期二分配格的判定（續(xù)）解L1,L2和L3都不是分配格.{a,b,c,d,e}是L1的子格,并且同構(gòu)于鉆石格；{a,b,c,e,f}是L2的子格,并且同構(gòu)于五角格；{a,c,b,e,f}是L3的子格,也同構(gòu)于鉆石格.例說明圖中的格是否為分配格,為什么？26第26頁，共38頁，2023年，2月20日，星期二全上界與全下界定義設(shè)L是格,若存在a∈L使得x∈L有a?x,則稱a為L的全下界；若存在b∈L使得x∈L有x?b,則稱b為L的全上界.

說明：格L若存在全下界或全上界,一定是惟一的.

一般將格L的全下界記為0,全上界記為1.

27第27頁，共38頁，2023年，2月20日，星期二有界格定義及其性質(zhì)定義設(shè)L是格,若L存在全下界和全上界,則稱L為有界格,全下界記為0，全上界記為1.有界格L記為<L,∧,∨,0,1>.注意：有限格L={a1,a2,…,an}是有界格,a1∧a2∧…∧an是L的全下界,a1∨a2∨…∨an是全上界.0是關(guān)于∧運算的零元,∨運算的單位元.1是關(guān)于∨運算的零元,∧運算的單位元.

對于涉及有界格的命題,如果其中含有全下界0或全上界1,求其對偶命題時,必須將0與1互換.28第28頁，共38頁，2023年，2月20日，星期二補元的定義定義設(shè)<L,∧,∨,0,1>是有界格,a∈L,若存在b∈L

使得

a∧b=0和a∨b=1成立,則稱b是a的補元.

注意：若b是a的補元,那么a也是b的補元.a和b互為補元.29第29頁，共38頁，2023年，2月20日，星期二實例:求補元解：L1中a,c互補,b沒補元.

L2中a,d互補,b,c

互補.

L3中a,e互補,b的補元是c和d,c的補元是b和d,d的補元是b和c.

L4中的a,e互補,b的補元是c和d,c的補元是b,d的補元是b.30第30頁，共38頁，2023年，2月20日，星期二有界分配格中補元惟一性定理設(shè)<L,∧,∨,0,1>是有界分配格.若L中元素a存在補元,則存在惟一的補元.

證假設(shè)b,c是a的補元,則有

a∨c=1,a∧c=0,a∨b=1,a∧b=0從而得到a∨c=a∨b,a∧c=a∧b,由于L是分配格,b=c.31第31頁，共38頁，2023年，2月20日，星期二有補格的定義定義設(shè)<L,∧,∨,0,1>是有界格,若L中所有元素都有補元存在,則稱L為有補格.例如,下圖中的L2,L3和L4是有補格,L1不是有補格.

32第32頁，共38頁，2023年，2月20日，星期二布爾代數(shù)的定義定義

如果一個格是有補分配格,則稱它為布爾格或布爾代數(shù).在布爾代數(shù)中，如果一個元素存在補元,則是惟一的.可以把求補元的運算看作是布爾代數(shù)中的一元運算.布爾代數(shù)標記為<B,∧,∨,’,0,1>,其中’為求補運算33第33頁，共38頁，2023年，2月20日，星期二布爾代數(shù)的實例例設(shè)S110={1,2,5,10,11,22,55,110}是110的正因子集合.gcd表示求最大公約數(shù)的運算

lcm表示求最小公倍數(shù)的運算.則<S110,gcd,lcm>是否構(gòu)成布爾代數(shù)？

34第34頁，共38頁，2023年，2月20日，星期二布爾代數(shù)的等價定義定義設(shè)<B,?,°>是代數(shù)系統(tǒng),?和°是二元運算.若?和°運算滿足交換律、結(jié)合律、冪等律、吸收律,即

(1)a,b∈B有a?b=b?a,a°b=b°a

(2)a,b,c∈B有a?(b°c)=(a?b)°(a?c),

a°(b?c)=(a°b)?(a°c)

(3)即存在0,1∈B,使