《离散数学第讲.ppt》由会员分享，可在线阅读，更多相关《离散数学第讲.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学第讲离散数学第讲现在学习的是第1页，共23页2022/10/82022/10/81 1主要内容主要内容同态与同构同态与同构同态核同态核环环特殊环特殊环环的同构与同态环的同构与同态域域现在学习的是第2页，共23页2022/10/82022/10/82 2同态与同构同态与同构 本本节节研研究究的的是是一一个个代代数数系系统统与与另另外外一一个个代代数数系系统统之之间间的的关关系系，即即撇撇开开集集合合元元素素和和运运算算的的具具体体差差异异，只只考考虑虑两两代代数数系系统统的的运运算算性性质质上上的的差差异异，或或者者说说在在什什么么条条件件下下两两代代数数系系统统无无差差异异或者相似或者
2、相似。代代数数系系统统之之间间的的这这种种相相互互关关系系是是通通过过映映射射来来反反应应的的。映映射射有有单单射射、满满射射和和双双射射，相相应应本本节讲的是单同态、满同态和同构以及性质。节讲的是单同态、满同态和同构以及性质。现在学习的是第3页，共23页2022/10/82022/10/83 3定义定义15.915.9 设设X X，*与与Y,Y,是是两两个个代代数数系系统统，如如在在集合集合X X与与Y Y之间之间存在映射存在映射f f：X XY Y，使得对，使得对 a a，b b X X，有：，有：f(a*b)=f(a)f(b)f(a*b)=f(a)f(b)则则称称f f是是从从X X，*
3、到到Y,Y,的的同同态态映映射射，简简称称为为同同 态态，此此 时时 代代 数数 系系 统统X X，*与与 代代 数数 系系 统统Y,Y,称为称为同态的同态的，记为，记为XYXY。f(X)f(X)Y Y 称为称为X X的一个的一个同态象同态象。如果。如果现在学习的是第4页，共23页2022/10/82022/10/84 4f f：X XY Y是是一一个个单单射射，则则称称f f是是从从X,*X,*到到Y,Y,的的单一同态单一同态；f f：X XY Y是是 一一 个个满满 射射，则则 称称f f是是 从从 X,*X,*到到Y,Y,的的满同态满同态；f f：X XY Y是是一一个个双双射射，则则称
4、称f f是是从从X,*X,*到到Y,Y,的的同构同构，记为，记为XYXY。若若集集合合X=YX=Y，则则此此时时对对应应的的同同态态和和同同构构分分别别称称为为自同态自同态、单一自同态单一自同态、满自同态满自同态和和自同构自同构。现在学习的是第5页，共23页2022/10/82022/10/85 5 例例15-6.1 15-6.1 证明代数系统证明代数系统R R+，与与R R，+是同构的。是同构的。证证 明明：设设 f f：R R+R R，且且f f（x x）=ln=ln（x x），则则：1.f1.f是一个是一个R R+R R的映射；的映射；2.2.对对 y y R,R,均均 x=ex=ey
5、y R R+,使使得得f(x)=ln(x)=ln(ef(x)=ln(x)=ln(ey y)=y)=y，所所以以f f是是一个满射；一个满射；3.3.对对 x x y y R R+,有有ln(x)ln(x)ln(y)ln(y)，所所 以以 f f是是 一一 个个 单单 射射；由由1 1、2 2、3 3知：知：f f是一个双射。是一个双射。4.4.对对 x x，y y R R+，有：，有：f(xy)=ln(xy)=ln(x)+ln(y)=f(x)+f(y)f(xy)=ln(xy)=ln(x)+ln(y)=f(x)+f(y)由由1 1、2 2、3 3、4 4知：知：f f是一个是一个双射双射且满足且
6、满足 f(x*y)=f(x)f(y)f(x*y)=f(x)f(y)R R+R R现在学习的是第6页，共23页2022/10/82022/10/86 6 例例15-6.2 15-6.2 在在自自然然数数加加半半群群N N，+与与剩剩余余类类加加群群Z 之间定义映射之间定义映射f f：N NZ Z2 2 如下：如下：证明证明f f是是N N到到Z Z2 2的满同态映射。的满同态映射。证明证明：对对 n n1 1,n,n2 2 N N，1 1）当）当n n1 1和和n n2 2同奇偶时，同奇偶时，f(nf(n1 1+n+n2 2)=0)=0，而，而f(nf(n1 1)和和f(nf(n2 2)要么同为
7、要么同为00，要么同为，要么同为11，从而，从而f(nf(n1 1)f(nf(n2 2)=0)=0；2 2）当）当n n1 1和和n n2 2不不同奇偶时，同奇偶时，f(nf(n1 1+n+n2 2)=1)=1，而，而f(nf(n1 1)和和f(nf(n2 2)中一个中一个为为00，一个为，一个为11，从而，从而f(nf(n1 1)f(nf(n2 2)=1)=1；N NZ Z2 2，而而 显然是一个满射，所以，结论成立。显然是一个满射，所以，结论成立。现在学习的是第7页，共23页2022/10/82022/10/87 7性性 质质定理定理1515.1515设设X X，*与与Y,Y,是两个代数系
8、统，是两个代数系统，f f：X XY Y是是一个一个同态映射同态映射，则：，则：1 1）如如果果运运算算*在在X X中中是是封封闭闭的的运运算算在在f f（X X）Y Y中中是封闭的；是封闭的；2 2）X X，*满足结合律满足结合律f f（X X）,满足结合律；满足结合律；3 3）X X，*满足交换律满足交换律 f f（X X）,满足交换律满足交换律;4 4）X X，*满足消去律满足消去律 f f（X X）,满足消去律；满足消去律；5 5）X X，*存在幺元存在幺元e e1 1 f f（X X）,存在幺元存在幺元e e2 2；6 6）X X，*存在零元存在零元1 1 f f（X X）,存在零元
9、存在零元2 2；7 7）在在X X中中每每元元关关于于运运算算*有有逆逆元元 f f（X X）中中每每元元关关于于运运算算 有逆元。有逆元。该定理说明同态映射不仅确定该定理说明同态映射不仅确定了不同集合元素间的对应关系，了不同集合元素间的对应关系，而且还保持了代数系统的运算而且还保持了代数系统的运算性质。因此，能够建立同态映性质。因此，能够建立同态映射的代数系统之间有着很大的射的代数系统之间有着很大的一致性。一致性。现在学习的是第8页，共23页2022/10/82022/10/88 8定理定理1515.16 16 设设X X，*与与Y Y，是两个代数系统，是两个代数系统，f f：X XY Y是
10、是满同态满同态，则：，则：1)1)如果如果X X是半群是半群Y Y是半群；是半群；2)2)如果如果X X是群是群Y Y是群是群。在在同同态态映映射射下下，像像源源的的代代数数性性质质都都为为像像集集所所具具有有。但但是是，像像集集所所具具有有的的代代数数性性质质却却未未必必为为像像源源所所具有。具有。（如（如Z 是群，而是群，而N N，+不是群）不是群）如如果果f f：X XY Y是是同同构构映映射射，则则代代数数系系统统X X与与Y Y许许多多性性质质完完全全相相同同。而而且且代代数数系系统统之之间间的的同同构构关关系系是是等等价价关系关系。现在学习的是第9页，共23页2022/10/820
11、22/10/89 9同态核同态核 下下面面通通过过考考察察像像源源中中被被映映射射到到像像集集幺幺元元的的那那些些元素具有的代数特征来揭示同态的分类特征。元素具有的代数特征来揭示同态的分类特征。定义定义15.1015.10 设设f f是群是群G G，*到到H H，的同态映射，令：的同态映射，令：K KKerfKerfa|aa|a G Gf(a)f(a)ee其其中中ee是是H H的的单单位位元元，则则称称KerfKerf为为f f的的同同态态核核，f(G)f(G)f(a)|aGf(a)|aG称为称为f f的的像集像集。现在学习的是第10页，共23页2022/10/82022/10/81010定定
12、理理1515.17 17 设设f f是是群群G G，*到到H H，的的同同态态映映射射，e e，ee分分别别是是G G和和H H的的单单位位元元，则则同同态态核核KerfKerf是是G G的的不不变（正规）子群变（正规）子群。证证明明由由定定义义KerfKerfa|aGa|aGf(a)f(a)ee，因因为为f f是是同同态态映映射射，所所以以有有f(e)f(e)ee。故故eKerfeKerf，所所以以KerfKerf是是G G的的非空子集非空子集。对任意的对任意的a a，bKerfbKerf，由定义有，由定义有f(a)f(a)ee，f(b)f(b)ee又因为又因为f f是同态映射，所以有是同态
13、映射，所以有f(a*bf(a*b-1-1)f(a)f(a)f(bf(b-1-1)f(a)f(a)(f(b)(f(b)-1-1eeee-1-1ee为什么？f(b-1)=(f(b)-1现在学习的是第11页，共23页2022/10/82022/10/81111即即a*ba*b-1-1KerfKerf，由由定定理理1515.8 8所所以以Kerf 是是G 的的子群子群。另一方面，对任意的另一方面，对任意的 kKerfkKerf，aGaG，我们有，我们有f(a*k*af(a*k*a-1-1)f(a)f(a)f(k)f(k)f(af(a-1-1)f(a)f(a)ee(f(a)(f(a)-1-1f(a)f(
14、a)(f(a)(f(a)-1-1ee所以有所以有a*k*aa*k*a-1-1KerfKerf，由，由定理定理1515.1414故故Kerf 是是G 的的不变子群不变子群。在在例例15-6.215-6.2中中，00是是Z Z2 2中中的的幺幺元元，因因而而映映射射的的同同态态核是集合核是集合Kerf=0Kerf=0，2 2，4 4，6 6，。可以进一步证明，在同态映射下,像源集G具有陪集分解式，其中每个陪集是像集中某个元素的像源。现在学习的是第12页，共23页2022/10/82022/10/81212环和域环和域 前前面面讨讨论论了了具具有有一一个个二二元元运运算算的的代代数数系系统统半群、含
15、幺半群、群、子群半群、含幺半群、群、子群。下下面面讨讨论论具具有有两两个个二二元元运运算算的的代代数数系系统统。给给定定两两个个代代数数系系统统，可可将将它它们们组组合合成成一一个个具具有有两两个个二二元元运运算算的的代代数数系系统统,而而这这两两个个二元运算符二元运算符+和和*之间是有联系的之间是有联系的。环环在在计计算算机机科科学学的的很很多多领领域域，诸诸如如编编码码理理论论的的研研究究中中起起着着重重要要作作用用；而而域域，特特别别是是有有限限域域是是纠纠错码理论的基础。错码理论的基础。现在学习的是第13页，共23页2022/10/82022/10/81313环环 RingRing定义
16、定义16.116.1 一个代数系统一个代数系统，如果满足：，如果满足：（1 1）R+是阿贝尔群；是阿贝尔群；（2 2）是半群；是半群；（3 3）运运算算*在在运运算算+上上可可分分配配。即即对对任任意意a a，b b，c c R R有有 a*(b+c)=a*(b+c)=（a*ba*b）+（a*ca*c）(b+c)*a=(b+c)*a=（b*ab*a）+（c*a)c*a)则称则称是一个环。是一个环。(联系两个二元运算，否则就不是一个系统而是两个系统)现在学习的是第14页，共23页2022/10/82022/10/81414例例16-1.1 16-1.1 在在加加法法和和乘乘法法运运算算下下，整整
17、数数、实实数数、有有理数、偶数和复数都能构成环。理数、偶数和复数都能构成环。+可以交换，可以交换，0 0是是+的幺元，的幺元，i i的逆为的逆为-i-i；+,+,可结合可结合,对对+可分配可分配现在学习的是第15页，共23页2022/10/82022/10/81515例例16-1.2 16-1.2 设设Z Zk k表表示示整整数数集集Z Z上上的的模模k k剩剩余余类类集集合合，即即 Z Zk k=0=0，11，22，k-1k-1Z 是群（是群（剩余类加群剩余类加群），），Z 是半群（是半群（剩余类乘半群剩余类乘半群），），对对 ii，jj，kk Z Zk k有有ii（jj kk）=i(j+k
18、)=ij+ik=i(j+k)=ij+ik =ij =ij ikik =(i =(i j)j)(i(i kk）Z 是环，称为是环，称为（模（模k k）剩余类环）剩余类环。特别，特别，k=2k=2时，称为时，称为布尔环布尔环。现在学习的是第16页，共23页2022/10/82022/10/81616定理定理16.116.1 设设R,+,*是是一一个个环环，是是加加法法幺幺元元，对对任任意意a a，b b，c c R,R,则则 a+b=c a+b=c a+b-c=(a+b-c=(移项法则移项法则)现在学习的是第17页，共23页2022/10/82022/10/81717定理定理16.216.2 设设
19、R,+,*是是一一个个环环，是是加加法法幺幺元元，对对任任意意a a，b b，c c R R有有a*=*a=a*=*a=(加法幺元是乘法零元加法幺元是乘法零元)(-a)*b=a*(-b)=-(a*b)(-a)*b=a*(-b)=-(a*b)(-a)*(-b)=a*b(-a)*(-b)=a*b(b-c)*a=b*a-c*a(b-c)*a=b*a-c*aa*(b-ca*(b-c）=a*b-a*c=a*b-a*c 现在学习的是第18页，共23页2022/10/82022/10/81818特殊环特殊环定义定义16.316.3 设设是一个环是一个环如果如果是可交换的，称是可交换的，称是是交换环交换环；如
20、果如果是含幺半群，称是含幺半群，称是是含幺环含幺环；如如果果对对于于某某些些非非零零元元素素a,ba,b R,R,能能使使a*b=0,a*b=0,称称是是含零因子环含零因子环；a,ba,b称为称为零因子零因子；如如果果R,+,*是是可可交交换换的的，含含幺幺，而而无无零零因因子子，则称它是则称它是整环整环。现在学习的是第19页，共23页2022/10/82022/10/81919例例16-2.1 16-2.1 证证明明（模模k k）剩剩余余类类环环Z 无无零零因因子子当且仅当当且仅当k k是素数。是素数。证明：证明：当当k k是合数时，是合数时，a2a2，b2b2，k=abk=ab而而aa b
21、=k=0b=k=0，即，即aa、bb都是零因子，都是零因子，又又 当当k k是素数时，不是素数时，不 a2a2，b2b2，k=abk=ab因而无零因子因而无零因子 结论成立。结论成立。例如例如Z 中，中，22 3=03=0，44 3=03=0现在学习的是第20页，共23页2022/10/82022/10/82020定理定理16.316.3 设设是一个环，则是一个环，则R R中无零因子中无零因子当且仅当当且仅当 对对 a,x,ya,x,y R R，当，当a0a0时，时，a*x=a*y a*x=a*y x=y x=y 或或 x*a=y*a x*a=y*a x=y x=y （即在环中（即在环中无零因
22、子无零因子与与消去律消去律是等价的）是等价的）定义定义16.416.4 设设R,+,*是是一一个个环环，S S是是R R的的非非空空集集合合，如如果果也是一个环，则称也是一个环，则称S S是是R R的的子环子环。例如：例如：0 是模是模6 6剩余剩余类环类环Z 的子环。的子环。现在学习的是第21页，共23页2022/10/82022/10/82121环的同构与同态环的同构与同态定义定义16.516.5 设设和和T,是是两两个个环环，如如在在集集合合S S与与T T之间之间存在映射存在映射f f：S ST T，使得对，使得对 a a，b b S S，有：，有：f(a+b)=f(a)f(a+b)=
23、f(a)f(b)f(b)f(a*b)=f(a)f(a*b)=f(a)f(b)f(b)则则称称f f是是从从到到T,的的环环同同态态映映射射，f(S)f(S)为为S S的的一一个个同同态态象象。当当f f是是一一个个满满射射时时，则则称称f f为为满满同同态态；当当f f是是一一个个双双射射时时，则则称称f f是是环环同同构构映映射射；现在学习的是第22页，共23页2022/10/82022/10/82222定理定理16.416.4 设设f f是环是环到环到环T,的同态映射，则的同态映射，则 如如果果和和e e分分别别是是S S中中的的加加法法幺幺元元和和乘乘法法幺幺元元，则则f()f()和和f(e)f(e)分别是分别是f(S)f(S)中的中的 幺元和幺元和 幺元幺元；对对a a S S，如如果果-a-a（或或a a-1-1）是是a a的的加加法法（或或乘乘法法）逆逆元元，则则f(-a)f(-a)（或或f(af(a-1-1)）是是f(S f(S)中中的的 逆逆元元（或或 逆元）逆元）；f(S),也是环。也是环。现在学习的是第23页，共23页2022/10/82022/10/82323