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

1、陳瑜,Email： 2020年9月4日星期五,離散數(shù)學(xué),計算機學(xué)院,2020/9/4,計算機學(xué)院,2/128,第16章： 環(huán)和域 16.1 環(huán)的定義及其性質(zhì),2020/9/4,計算機學(xué)院,3/128,環(huán)和域,前面討論了具有一個二元運算的代數(shù)系統(tǒng)半群、含幺半群、群、子群。 下面討論具有兩個二元運算的代數(shù)系統(tǒng)。給定兩個代數(shù)系統(tǒng)，可將它們組合成一個具有兩個二元運算的代數(shù)系統(tǒng),而這兩個二元運算符+和*之間是有聯(lián)系的。 環(huán),域，特別是有限域是糾錯碼理論的基礎(chǔ)。,2020/9/4,計算機學(xué)院,4/128,環(huán) Ring,定義16.1 一個代數(shù)系統(tǒng)，如果滿足： （1）是阿貝爾群； （2）是半群； （3）乘法*

2、在加法+上可分配。即對任意a，b，c R有 a*(b+c)=（a*b）+（a*c） (b+c)*a=（b*a）+（c*a) 則稱是一個環(huán)。,(聯(lián)系兩個二元運算， 否則就不是一個系統(tǒng) 而是兩個系統(tǒng)),2020/9/4,計算機學(xué)院,5/128,例16.1 在加法和乘法作用下，整數(shù)、實數(shù)、有理數(shù)、偶數(shù)和復(fù)數(shù)都能構(gòu)成環(huán)。 +可以交換，0是+的幺元， i的逆為-i；+, 可結(jié)合, 對+可分配,2020/9/4,計算機學(xué)院,6/128,例16.2 設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即: Zk=0，1，2，k-1 是群（剩余類加群）， 是半群（剩余類乘半群）， 對 i，j，k Zk 有i（jk）=i(j

3、+k)=ij+ik =ijik =(ij)(ik） 是環(huán)，稱為（模k）剩余類環(huán)。 特別， k=2時，稱為布爾環(huán)。,2020/9/4,計算機學(xué)院,7/128,例16.2 設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即: Zk=0，1，2，k-1 是群（剩余類加群）， 是半群（剩余類乘半群）， 對 i，j，k Zk 有i（jk）=i(j+k)=ij+ik =ijik =(ij)(ik） 是環(huán)，稱為（模k）剩余類環(huán)。 特別， k=2時，稱為布爾環(huán)。,2020/9/4,計算機學(xué)院,8/128,例16.2 設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即: Zk=0，1，2，k-1 是群（剩余類加群）， 是半群（剩余

4、類乘半群）， 對 i，j，k Zk 有i（jk）=i(j+k)=ij+ik =ijik =(ij)(ik） 是環(huán)，稱為（模k）剩余類環(huán)。 特別， k=2時，稱為布爾環(huán)。,2020/9/4,計算機學(xué)院,9/128,定理16.1(移項法則)設(shè)是一個環(huán)，是加法幺元，對任意a，b，c R有: a+b=c a+b-c=,2020/9/4,計算機學(xué)院,10/128,定理16.2設(shè)是一個環(huán)，是加法幺元，對任意a，b，c R有: a*=*a=(加法幺元是乘法零元) (-a)*b=a*(-b)=-(a*b) (-a) *(-b)=a*b (b-c) *a=b*a-c*a a* (b-c）=a*b-a*c,202

5、0/9/4,計算機學(xué)院,11/128,定理16.2設(shè)是一個環(huán)，是加法幺元，對任意a，b，c R有: a*=*a=(加法幺元是乘法零元) (-a)*b=a*(-b)=-(a*b) (-a) *(-b)=a*b (b-c) *a=b*a-c*a a* (b-c）=a*b-a*c,證明: 因為a*=a*（+）=(a*)+(a*)， 由移項法則a*=。同樣，可得*a=。,2020/9/4,計算機學(xué)院,12/128,定理16.2設(shè)是一個環(huán)，是加法幺元，對任意a，b，c R有: a*=*a=(加法幺元是乘法零元) a*(-b)=-(a*b)=(-a)*b (-a) *(-b)=a*b (b-c) *a=b

6、*a-c*a a* (b-c）=a*b-a*c,2020/9/4,計算機學(xué)院,13/128,定理16.2設(shè)是一個環(huán)，是加法幺元，對任意a，b，c R有: a*=*a=(加法幺元是乘法零元) a*(-b)=-(a*b)=(-a)*b (-a) *(-b)=a*b (b-c) *a=b*a-c*a a* (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).,2020/9/4,計算機學(xué)院,14/128,定理16.2設(shè)是一個環(huán)，是加法幺元

7、，對任意a，b，c R有: a*=*a=(加法幺元是乘法零元) a*(-b)=-(a*b)=(-a)*b (-a) *(-b)=a*b (b-c) *a=b*a-c*a a* (b-c）=a*b-a*c,2020/9/4,計算機學(xué)院,15/128,定理16.2設(shè)是一個環(huán)，是加法幺元，對任意a，b，c R有: a*=*a=(加法幺元是乘法零元) a*(-b)=-(a*b)=(-a)*b (-a) *(-b)=a*b (b-c) *a=b*a-c*a a* (b-c）=a*b-a*c,證明： 利用式的結(jié)果， (-a)*(-b)-(a*b)=(-a)*(-b)）+(-a)*b)） =(-a)*(-b

8、+b) =(-a)*=, 但是，-(a*b)又是a*b的逆，根據(jù)群中逆的唯一性，a*b=(-a)*(-b).,2020/9/4,計算機學(xué)院,16/128,定理16.2設(shè)是一個環(huán)，是加法幺元，對任意a，b，c R有: a*=*a=(加法幺元是乘法零元) a*(-b)=-(a*b)=(-a)*b (-a) *(-b)=a*b a*(b-c)=(a*b)-(b*c),證明： a*(b-c)=a*(b+(-c) =(a*b)+(a*(-c) =(a*b)-(a*c).,2020/9/4,計算機學(xué)院,17/128,定理16.2設(shè)是一個環(huán)，是加法幺元，對任意a，b，c R有: a*=*a=(加法幺元是乘法

9、零元) a*(-b)=-(a*b)=(-a)*b (-a) *(-b)=a*b a*(b-c)=(a*b)-(b*c) （b-c）*a=(b*a)-(c*a),2020/9/4,計算機學(xué)院,18/128,定理16.2設(shè)是一個環(huán)，是加法幺元，對任意a，b，c R有: a*=*a=(加法幺元是乘法零元) a*(-b)=-(a*b)=(-a)*b (-a) *(-b)=a*b a*(b-c)=(a*b)-(b*c) （b-c）*a=(b*a)-(c*a),這個定理表明，普通環(huán)的運算性質(zhì)在很多方面類似于數(shù)的運算性質(zhì)，但是在某些方面它們卻有不同。例如在模m剩余類環(huán)中，我們特別注意到一種情況：當(dāng)i0,j0

10、時，卻可能ij=0。 例如在中，23=0,43=0。,2020/9/4,計算機學(xué)院,19/128,定義16.2設(shè)是環(huán)，a,bR。如果a且b,而a*b=，則稱a和b是R中的零因子。 例16-3 模m剩余類環(huán)沒有零因子當(dāng)且僅當(dāng)m是素數(shù)。因為當(dāng)m是合數(shù)時，必有a2,b2使m=ab，從而ab=m=0,而且a和b都是零因子。當(dāng)m是素數(shù)時，不存在a2和b2使m=ab，因而無零因子。,2020/9/4,計算機學(xué)院,20/128,定義16.2設(shè)是環(huán)，a,bR。如果a且b,而a*b=，則稱a和b是R中的零因子。 例16.3 模m剩余類環(huán)沒有零因子當(dāng)且僅當(dāng)m是素數(shù)。因為當(dāng)m是合數(shù)時，必有a2,b2使m=ab，從而

11、ab=m=0,而且a和b都是零因子。當(dāng)m是素數(shù)時，不存在a2和b2使m=ab，因而無零因子。,合數(shù)是除了1和它本身還能被其他的正整數(shù)整除的正整數(shù).除2之外的偶數(shù)都是合數(shù).(除0以外),2020/9/4,計算機學(xué)院,21/128,16.2 整環(huán)與域,2020/9/4,計算機學(xué)院,22/128,特殊環(huán),定義16.3 設(shè)是一個環(huán): 如果是可交換的，稱是交換環(huán)； 如果是含幺半群，稱是含幺環(huán)； 如果對于R中某些非零元素a、b,能使a*b=,稱是含零因子環(huán)；a、b稱為零因子； 如果是可交換的、含幺、而無零因子，則稱它是整環(huán)。,2020/9/4,計算機學(xué)院,23/128,例16.4 （同前例16.3） 證明

12、（模k）剩余類環(huán)無零因子當(dāng)且僅當(dāng)k是素數(shù)。 證明： 當(dāng)k是合數(shù)時，必有a2、b2，使得 k=ab，從而ab=k=0，即a、b都是零因子。 又 當(dāng)k是素數(shù)時，不存在a2、b2，使得 k=ab，從而無零因子。 結(jié)論成立。,2020/9/4,計算機學(xué)院,24/128,定理16.3 設(shè)是一個環(huán)，則R中無零因子當(dāng)且僅當(dāng)對a,x,yR，當(dāng)a0時， a*x=a*y x=y 或 x*a=y*a x=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

13、必然得出x=y的結(jié)論， 如果R中存在b和c使b*c=，那么由b*c=b*就導(dǎo)出c=。 這說明R中必?zé)o零因子。,2020/9/4,計算機學(xué)院,25/128,定理16.3 設(shè)是一個環(huán)，則R中無零因子當(dāng)且僅當(dāng)對a,x,yR，當(dāng)a0時， a*x=a*y x=y 或 x*a=y*a x=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零因子。

14、,2020/9/4,計算機學(xué)院,26/128,定理16.3 設(shè)是一個環(huán)，則R中無零因子當(dāng)且僅當(dāng)對a,x,yR，當(dāng)a0時， a*x=a*y x=y 或 x*a=y*a x=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零因子。,2020/9/4,計算機學(xué)院,27/128,定理16.3 設(shè)是一個環(huán)，則R中無零因子當(dāng)且僅當(dāng)對a,x,yR

15、，當(dāng)a0時， a*x=a*y x=y 或 x*a=y*a x=y （即滿足可約律）,定義16.4 設(shè)是一個環(huán)，S是R的非空集合，如果也是一個環(huán)，則稱S是R的子環(huán)。 例如： 是模6剩余類環(huán)的子環(huán)。,2020/9/4,計算機學(xué)院,28/128,環(huán)的同構(gòu)與同態(tài),定義16.5 設(shè)和是兩個環(huán)，如在集合S與T之間存在映射f：ST，使得對a，bS，有： f(a+b)=f(a)f(b) f(a*b)=f(a)f(b) 則稱f是從到的環(huán)同態(tài)映射， f(S)為S的一個同態(tài)象。當(dāng)f是一個滿射時，則稱f為滿同態(tài)；當(dāng)f是一個雙射時，則稱f是環(huán)同構(gòu)映射；,2020/9/4,計算機學(xué)院,29/128,例16.5 存在整數(shù)環(huán)

16、到模m剩余類環(huán)的同態(tài)，因為我們可以定義映射f：ZZm如下：使對所有xZ， f(x)=x mod m. 在此映射下，設(shè)a,bZ,由同余的性質(zhì)， a+b=ab, a*b=ab， 所以 。,2020/9/4,計算機學(xué)院,30/128,定理16.4 設(shè)f是環(huán)到環(huán)的同態(tài)映射，則: 如果和e分別是S中的加法幺元和乘法幺元，則f()和f(e)分別是f(S )中的幺元和幺元； 對aS，如果-a（或a-1）是a的加法（或乘法）逆元，則f(-a)（或f(a-1)）是f(S )中的逆元（或逆元）； 也是環(huán)。,2020/9/4,計算機學(xué)院,31/128,域,給環(huán)施加進(jìn)一步的限制，從而得到另一個代數(shù)系統(tǒng)域。 問題歸結(jié)為

17、是否是一個群。 定義16.6 設(shè)是一個環(huán)，如果和都是交換群，則稱是域。 一般情況下，整環(huán)不是域，但當(dāng)環(huán)的元素個數(shù)有限時，有以下結(jié)論：,定理16.5有限整環(huán)必是域。 (教材p198),是加法幺元,2020/9/4,計算機學(xué)院,32/128,例16.6 實數(shù)環(huán) 、有理數(shù)環(huán) 、剩余類環(huán)(p是素數(shù)）都是域。 整數(shù)環(huán)、剩余類環(huán)(m是合數(shù)）都不是域。 因為、都不是群。,2020/9/4,計算機學(xué)院,33/128,習(xí)題,熟記相關(guān)概念,2020/9/4,計算機學(xué)院,34/128,第17章 格與布爾代數(shù) 17.1 格的定義與性質(zhì),2020/9/4,計算機學(xué)院,35/128,格與布爾代數(shù),下面討論另外兩個重要的代

18、數(shù)系統(tǒng)格與布爾代數(shù)，這兩個代數(shù)系統(tǒng)與前面討論的代數(shù)系統(tǒng)之間存在著一個重要區(qū)別：在格與布爾代數(shù)中，偏序關(guān)系具有重要意義。,2020/9/4,計算機學(xué)院,36/128,本章主要介紹以下幾點： 格的概念和基本性質(zhì) 子格的定義 特殊的格及性質(zhì) 布爾代數(shù)的概念和基本性質(zhì),2020/9/4,計算機學(xué)院,37/128,格的定義,定義17.1（代數(shù)格）設(shè)是一個代數(shù)系統(tǒng)，如果，滿足： 交換律：ab=ba，ab=ba, 結(jié)合律：a(bc)=(ab)c, a(bc)=(ab)c 吸收律：a(ab)=a，a(ab)=a 則稱是一個代數(shù)格。 2個典型的格: 集合代數(shù)系統(tǒng) 命題邏輯系統(tǒng),代數(shù)格,2020/9/4,計算機學(xué)院,38/128,定理17.1 (冪等律) 設(shè)是一個代數(shù)格，aL，則必有aa=a, aa=a。 證明： aa=a(a(aa) (吸收律) =a. (吸收律) 在上兩式中，把換成，把換成后，可以證明aa=a。,2020/9/4,計算機學(xué)院,39/128,復(fù)習(xí)：偏序關(guān)系是集合上的自反的、可傳遞、反對稱關(guān)系,它提供比較集合元素的工具。 定義：設(shè)R是集合A上的自反的、反對稱的、傳遞