离散数学代数结构

2020/4/29数学的基本结构序结构：数的大小，次序拓扑结构：平面几何，立体几何（欧氏空间）代数结构：群2020/4/29Chapter4AlgebraSystem2020/4/29§4.1代数系统的引入(1)一个代数系统需要满足下面三个条件：（1）有一个非空集合S；（2）有一些建立在S上的运算；（3）这些运算在集合S上是封闭的。2020/4/29§4.2运算(1)4.2.1运算的概念定义假设A是一个集合，AA到A的映射称为A上的二元运算。一般地，An到A的映射称为A上的n元运算。2020/4/29§4.2运算(2)4.2.2运算的性质（1）封闭性如果SA，对任意的a,bS，有a*bS，则称S对运算*是封闭的。假设*,+都是集合A上的运算2020/4/29§4.2运算(3)4.2.2运算的性质（2）交换律如果对任意的a,bA，都有a*b=b*a，则称运算*是可交换的。（3）结合律如果对任意的a,b,cA，都有(a*b)*c=a*(b*c)，则称运算*是可结合的。2020/4/29§4.2运算(4)（4）分配律如果对任意的a,b,cA，都有a*(b+c)=(a*b)+(a*c)则称*对+运算满足左分配；如果对任意的a,b,cA，都有(b+c)*a=(b*a)+(c*a)则称*对+运算满足右分配。如果运算*对+既满足左分配又满足右分配，则称运算*对+满足分配律。2020/4/29§4.2运算(5)（5）消去律如果对任意的a,b,cA，当a*b=a*c，必有b=c，则称运算*满足左消去律；如果对任意的a,b,cA，当b*a=c*a，必有b=c，则称运算*满足右消去律；如果运算*既满足左消去律又满足右消去律，则称运算*满足消去律。2020/4/29§4.2运算(6)（6）吸收律如果对任意的a,bA，都有a*(a+b)=a，则称运算*关于运算+满足吸收律。（7）等幂律如果对任意的aA，都有a*a=a，则称运算*满足等幂律。2020/4/29§4.2运算(7)bacabccbaacbbac2020/4/29§4.3代数系统(1)4.3.1代数系统的概念定义假设A是一个非空集合，f1,f2,…,fn是A上的运算（运算的元素可以是不相同的），则称A在运算f1,f2,…,fn下构成一个代数系统，记为：A,f1,f2,…,fn2020/4/29§4.3代数系统(2)4.3.1代数系统的概念定义假设A,*是一个代数系统，SA，如果S对*是封闭的，则称S,*为A,*的子代数系统。2020/4/29§4.3代数系统(3)4.3.2代数系统中的特殊元素（1）单位元（幺元）假设A,*是一个代数系统，如果eLA,对于任意元素xA，都有eL*x=x,则称eL为A中关于运算*的左单位元;如果erA,对于任意元素xA，都有x*er=x,则称er为A中关于运算*的右单位元;如果A中一个元素e既是左单位元又是右单位元，则称e为A中关于运算*的单位元。2020/4/29§4.3代数系统(4)bacabccbaacbbacbacabccbacbacbabacabcaaabbbccc2020/4/29§4.3代数系统(5)4.3.2代数系统中的特殊元素（1）单位元（幺元）定理假设A,*是代数系统，并且A关于运算*有左单位元eL和右单位元er，则eL=er=e并且单位元唯一。2020/4/29§4.3代数系统(6)4.3.2代数系统中的特殊元素（2）零元假设A,*是一个代数系统，如果LA,对于任意元素xA，都有L*x=L,则称L为A中关于运算*的左零元;如果rA,对于任意元素xA，都有x*r=r,则称r为A中关于运算*的右零元;如果A中一个元素既是左零元又是右零元，则称为A中关于运算*的零元。2020/4/29bacabccbabbbbbcbacabccbacbacbabacabcaaabbbccc§4.3代数系统(7)2020/4/29§4.3代数系统(8)4.3.2代数系统中的特殊元素（2）零元定理假设A,*是代数系统，并且A关于运算*有左零元L和右零元r，则L=r=并且零元唯一。2020/4/29§4.3代数系统(9)4.3.2代数系统中的特殊元素（3）逆元假设A,*是一个代数系统，e是A,*的单位元。对于元素aA，如果存在bA，使得b*a=e，则称a为左可逆的，b为a的左逆元；如果存在cA，使得a*c=e，则称元素a是右可逆的，c为a的右逆元。如果存在a’A，使得a’*a=a*a’=e，则称a是可逆的，a’为a的逆元。a的逆元记为：a-1。2020/4/29bacabccbaacbbac§4.3代数系统(10)2020/4/29§4.3代数系统(11)4.3.2代数系统中的特殊元素（3）逆元定理设A,*是一个代数系统，且A中存在单位元e，每个元素都存在左逆元。如果运算*是可结合的，那么，任何一个元素的左逆元也一定是该元素的右逆元，且每个元素的逆元唯一。2020/4/29§4.3代数系统(12)4.3.2代数系统中的特殊元素（4）幂等元定义：在代数系统A,*中，如果元素a满足a*a=a，那么称a是A中的幂等元。2020/4/29运算4运算3运算2运算1ba*cabccbaacbbacba*cabccbacabcccba*cabccbacbacbaba*cabccbacbbbcc§4.3代数系统(12)2020/4/29§4.4同态与同构(1)4.4.1基本概念定义设A,*和B,是代数系统，f:AB,如果f保持运算，即对x,yA,有f(x*y)=f(x)f(y)。称f为代数系统A,*到B,的同态映射，简称同态。也称之为两代数系统同态。2020/4/29§4.4同态与同构(2)4.4.1基本概念定义设A,*和B,是代数系统，f是A到B的同态。如果f是单射的，称f为单同态；如果f是满射的，称f为满同态；如果f是双射的，称f为同构映射，简称为同构。2020/4/29§4.4同态与同构(3)4.4.1基本概念定义设A,*是代数系统，若存在函数f:AA,并且对x,yA,有f(x*y)=f(x)*f(y)。称f为A,*的自同态；如果f是双射的，则称f为A,*的自同构。2020/4/29§4.4同态与同构(4)4.4.2同态、同构的性质（1）如果两函数是同态、同构的，则复合函数也是同态、同构的。定理假设f是A,*到B,的同态，g是B,到C,的同态，则gf是A,*到C,的同态；如果f和g是单同态、满同态、同构时，则gf也是单同态、满同态和同构。2020/4/29§4.4同态与同构(5)4.4.2同态、同构的性质（2）满同态保持结合律定理假设f是A,*到B,的满同态。如果*运算满足结合律，则运算也满足结合律，即满同态保持结合律。（3）满同态保持交换律2020/4/29§4.4同态与同构(6)4.4.2同态、同构的性质定理假设f是A,*到B,的满同态。e是A,*的单位元，则f(e)是B,的单位元。（4）满同态保持单位元2020/4/29§4.4同态与同构(7)4.4.2同态、同构的性质定理假设f是A,*到B,的满同态。eA和eB分别是A,*和B,的单位元，如果A中元素x和x’互逆，则B中元素f(x)和f(x’)也互逆。（5）满同态保持逆元2020/4/29§4.4同态与同构(8)4.4.2同态、同构的性质定理假设f是A,*到B,的满同态。是A,*的零元，则f()是B,的零元。（6）满同态保持零元2020/4/29§4.4同态与同构(9)4.4.2同态、同构的性质定理假设f是A,*到B,的满同态。并且xA是A,*的幂等元，则f(x)B是B,的幂等元。（7）满同态保持幂等元2020/4/29§4.4同态与同构(10)4.4.2同态、同构的性质定理假设f是A,*到B,的同构映射。则f-1是B,到A,*的同构映射。（8）同构映射运算性质双向保持2020/4/29§4.5同余关系与商代数选讲4.5.1同余关系定义假设A,*是一个代数系统，E是A上的等价关系。如果对x1,x2,y1,y2A，当x1Ex2,y1Ey2时，必有(x1*y1)E(x2*y2)，则称E是A上的同余关系。2020/4/29§4.6直积(1)定义：设A,*和B,为两个代数系统，AB,称为两代数系统的直积。其中AB是A和B的笛卡尔乘积，定义如下：对任意的x,y,u,vAB，x,yu,v=x*u,yv。2020/4/29§4.6直积(2)定理：假设A,*和B,为两个代数系统，且分别有单位元eA,eB，在两代数系统的直积AB,中存在子代数系统S,T，使得A,*S,，B,T,。2020/4/29Chapter5Grouptheory2020/4/29§5.1半群(1)5.1.1半群的定义定义：设S,*是一个代数系统，如果*运算满足结合律，则称S,*是一个半群。2020/4/29§5.1半群(2)例：假设S={a,b,c}，在S上定义运算，如运算表给出。证明S,是半群。bacabccbacbacba2020/4/29§5.1半群(3)5.1.1半群的定义定义：假设S,*是一个半群，aS，n是正整数，则an表示n个a的计算结果，即an=a*a*…*a。对任意的正整数m,n，am*an=am+n，(am)n=amn。2020/4/29§5.1半群(4)5.1.2交换半群定义：如果半群S,*中的*运算满足交换律，则称S,*为交换半群。在交换半群S,*中，若a,bS，n是任意正整数，则(a*b)n=an*bn2020/4/29§5.1半群(5)5.1.3独异点（含幺半群）定义：假设S,*是一个半群，如果S,*中有单位元，则称S,*是独异点，或含幺半群。2020/4/29§5.1半群(6)5.1.3独异点（含幺半群）定理：假设S,*是独异点，如果a,bS，并且a,b有逆元a-1,b-1存在，则：（1）(a-1)-1=a；（2）(a*b)-1=b-1*a-1。2020/4/29§5.1半群(7)5.1.4子半群定义：假设S,*是一个半群，若TS，且在*运算下也构成半群，则称T,*是S,*的子半群。2020/4/29§5.1半群(8)假设A={a,b}，P(A),是一个含幺半群。{a,b}{a,b}{b}{a}{a}{b}{a}{b}{a}{b}{a}{b}{a,b}若B={a}则P(B)P(A)并且P(B),构成半群，是P(A),的子半群。2020/4/29§5.1半群(9)5.1.4子半群定义：设S,*是含幺半群，若T,*是它的子半群，并且S,*的单位元e也是T,*单位元，则称T,*是S,*的子含幺半群。2020/4/29§5.1半群(10)例：设S,*是可交换的含幺半群，T={a|aS，且a*a=a}，则T,*是S,*的子含幺半群。2020/4/29§5.2群的概念及其性质(1)5.2.1群的基本概念定义：设G,*是一代数系统，如果满足以下几点：(1)运算是可结合的；(2)存在单位元e；(3)对任意元素a都存在逆元a-1；则称G,*是一个群。2020/4/29§5.2群的概念及其性质(2)例：假设R={0,60,120,180,240,300}表示平面几何上图形绕形心顺时针旋转的角度集合。*是定义在R上的运算。定义如下：对任意的a,bR，a*b表示图形顺时针旋转a角度，再顺时针旋转b角度得到的总旋转度数。并规定旋转