复旦大学：《离散数学 Discrete Mathematics（下）》英文课件（赵一鸣）02/32

1苗冬青 Email:09210240028@fudan.edu.cn 。实验室软件楼401 2.王小威 BBS ID lengyan: Email: 09210240040afudan.edu.cn 。实验室软件楼405 3赵一鸣 BBS: Zhym Email: zhym fudan. edu.cn 每周三交作业

• 1. 苗冬青 • Email:09210240028@fudan.edu.cn • 实验室:软件楼401 • 2. 王小威 BBS ID lengyan: • Email:09210240040@fudan.edu.cn • 实验室:软件楼405 • 3.赵一鸣 • BBS: zhym • Email: zhym@fudan.edu.cn • 每周三交作业

参考书 近世代数吴品三人民教育出版社 代数结构与组合数学曲婉玲北京大学 出版社 近世代数及其应用阮传概孙伟北京邮 电大学出版社

• 参考书 • 近世代数 吴品三人民教育出版社 • 代数结构与组合数学 曲婉玲北京大学 出版社 • 近世代数及其应用 阮传概孙伟北京邮 电大学出版社

定义:如果映射o是代数系统S;到;°l 的同态映射当q是一一对应时称两个代 数系统是同构的,就是它们的一个同构 映射。 2个代数系统在结构上就完全一致了,它 们的不同只不过是元素与运算的表现形 式不同而已。 两个同构的代数系统S与T就可看作“同 个”代数系统并表示成S;]T;·简 写成S≌T

• 定义:如果映射是代数系统[S;*]到[T;•] 的同态映射,当是一一对应时,称两个代 数系统是同构的,就是它们的一个同构 映射。 • 2个代数系统在结构上就完全一致了，它 们的不同只不过是元素与运算的表现形 式不同而已。 • 两个同构的代数系统S与T就可看作“同 一个”代数系统,并表示成[S;*][T;•],简 写成ST

证明S;与T;两个系统同态或同构则 要找到一个满同态或同构映射 证明S;与[;两个系统不同态(不同 构),则要证明所有S到T的映射都不是满 同态(同构映射) 例1:证明[R;+与R;×同构 例2:证明Q;+与[Q-0};×不同构

• 证明[S;*]与[T;•]两个系统同态或同构,则 要找到一个满同态或同构映射 • 证明[S;*]与[T;•]两个系统不同态(不同 构),则要证明所有S到T的映射都不是满 同态(同构映射) • 例1:证明[R;+]与[R+ ;]同构 • 例2：证明[Q;+]与[Q-{0};]不同构

二、商结构 |S;为代数系统 S的等价类全体用§表示,即S={l∈S} 这里a={xa-x,eS} 对任意ab∈S,[a△b]={a*b 定义:设“”为S上的等价关系,““ 为S上的二元运算。若对任意a,b,c,d∈S 当a~b,c~时,必有a*Cb*l,则称等价 关系~与运算*是相容的,称~为代数系统 IS;*的相容等价关系

二、商结构 • [S;*]为代数系统 • S的等价类全体用Š表示,即Š={[a]|aS}。 这里[a]={x|a~x,xS} • 对任意[a],[b]Š, [a][b]=[ab] • 定义：设“~”为S上的等价关系，“*” 为S上的二元运算。若对任意a,b,c,dS， 当a~b，c~d时，必有ac~bd，则称等价 关系~与运算 是相容的，称~为代数系统 [S;]的相容等价关系

·对任意|bes,al△b=|a*b,则 由~关于*的相容性,保证运算△的结 果与等价类的代表元选取无关。称 s;△为S;*的商结构或商系统 例:zZ上模5同余关系 与代表元选取无关

• 对任意[a],[b]Š, [a][b]=[ab]，则 由~关于的相容性，保证运算的结 果与等价类的代表元选取无关。称 [Š;]为 [S;]的商结构或商系统。 • 例:Z上模5同余关系 • 与代表元选取无关

第十四章群 群是最简单的一类代数系统。群论 是近世代数中发展最早、内容最丰 富、应用最广泛的部分,也是建立 其他代数系统的基础

第十四章 群 • 群是最简单的一类代数系统。群论 是近世代数中发展最早、内容最丰 富、应用最广泛的部分, 也是建立 其他代数系统的基础

§1半群、拟群与群 、半群和拟群 定义141:代数系统S;2当其二元运算 是可结合的,即对任a,b,ceS有:“(b*c (a*b)c,则称该系统为半群 例: 定义142:设S;为半群,当*在S中有单 位元e,即对任意a∈S有:a*e=e*a=a,称该 半群为含单位元半群或称为拟群

§1半群、拟群与群 • 一、半群和拟群 • 定义14.1：代数系统[S;*],当其二元运算* 是可结合的,即对任 a,b,cS有 :a*(b*c) =(a*b)*c，则称该系统为半群。 • 例: • 定义14.2：设[S;*]为半群,当*在S中有单 位元e,即对任意aS,有:a*e=e*a=a，称该 半群为含单位元半群或称为拟群

·例2=(x|=1,,n E+∑中元素组成的有限长度的非空字符串全体 运算 :0=a1…k5B=b1…b∈Σ B=a-…akb1…b∈2 [Σ+;·是半群,但没有单位元。 Σ:有限长度的字符串全体构成的集合, [Σ;是半群,为空串(即长度为0的字符串) a∈∑+,有·=λ●a=0, λ为单位元, 「Σ;是拟群

• 例:={xi |i=1,…,n} •  + :中元素组成的有限长度的非空字符串全体 • 运 算 • :=a1ak ,=b1bl+ ， •=a1akb1bl+ ， • [ + ;•]是半群，但没有单位元。 •  * :有限长度的字符串全体构成的集合， • [ * ;•]是半群，为空串(即长度为0的字符串)， • + ，有•=•=， • 为单位元， • [ * ;•]是拟群

二、群 1群的概念 定义143:S;为拟群,当S中的每一个元素都 有逆元时称为群。 还可以更清楚地叙述为: S;是一个代数系统,为定义在S上的二元运算, 若满足: (1)对任意的a,bc∈S有a(b*c)=(a*b)c(结合律); (2)存在e∈S使ae=e*a=a(单位元); (3)对任意的a∈S,存在a∈S,使得a*a1=a1*a=e 则称|S;为群

二、群 • 1.群的概念 • 定义14.3：[S;*]为拟群,当S中的每一个元素都 有逆元时,称为群。 • 还可以更清楚地叙述为: [S;*]是一个代数系统,*为定义在S上的二元运算, 若满足: (1)对任意的a,b,cS有a*(b*c)=(a*b)*c(结合律); (2)存在eS,使a*e=e*a=a(单位元); (3)对任意的aS，存在a -1S,使得a*a-1=a-1*a=e 则称 [S;*]为群