离散数学第六章(第1讲)课件.ppt

1、代代 数数 系系 统统 本篇用代数方法来研究数学结构本篇用代数方法来研究数学结构,故又叫代数结构故又叫代数结构,它将用抽象的方法来研究集合上的关系和运算。它将用抽象的方法来研究集合上的关系和运算。代数的概念和方法已经渗透到计算机科学的许多代数的概念和方法已经渗透到计算机科学的许多分支中分支中,它对程序理论它对程序理论,数据结构数据结构,编码理论的研究和编码理论的研究和逻辑电路的设计具有理论和实践的指导意义。逻辑电路的设计具有理论和实践的指导意义。本篇讨论一些典型的代数系统及其性质。本篇讨论一些典型的代数系统及其性质。第六章第六章代代 数数 结结 构构1代数系统的概念代数系统的概念2运算及其性质

2、运算及其性质3半群和含幺半群半群和含幺半群4群与子群群与子群5交换群和循环群交换群和循环群7*陪集与拉格朗日定理陪集与拉格朗日定理8同态与同构同态与同构9环与域环与域1 1 代数系统的概念代数系统的概念举例：举例：将实数集合将实数集合 R R 上的每一数上的每一数 a a 0 0 映射成它的倒数映射成它的倒数1/1/a a，就可以将该映射称为集合，就可以将该映射称为集合R R 上的一元运算；上的一元运算；在集合在集合R R上，对任意两个数所进行的普通加法和乘上，对任意两个数所进行的普通加法和乘法，都是集合法，都是集合R R上的二元运算。上的二元运算。对于集合对于集合R R上的任意三个数的运算，

3、就是集合上的任意三个数的运算，就是集合R R上的上的三元运算。三元运算。定义定义:设设Z Z是一个集合是一个集合,f,f是一个函数是一个函数,f,f：Z Zn nZ Z,则称则称f f为为Z Z中的中的n n元运算元运算,整数整数n n称为运算的阶（元称为运算的阶（元,次）。次）。例：（例：（1 1）在整数）在整数I I和实数和实数R R中中,+,-,+,-,均为二元运算均为二元运算,而而对对而言就不是二元运算而言就不是二元运算 ;（2 2）在集合）在集合Z Z的幂集的幂集(Z)(Z)中中,均为二元运算均为二元运算,而而“”是一元运算；是一元运算；若若n=1,n=1,则称则称f f：Z ZZ

4、Z为一元运算；为一元运算；若若n=2,n=2,则则f f：Z Z2 2Z Z为二元运算。为二元运算。定义定义:一个非空集合一个非空集合S S连同若干个定义在该集合上的连同若干个定义在该集合上的运算运算f f1 1,f,f2 2,.,.,f fk k所组成的系统就称为一个代数系统，所组成的系统就称为一个代数系统，记作记作S,f。一个代数系统需要满足以下条件：一个代数系统需要满足以下条件：有一个非空集合有一个非空集合S S；有一些建立在集合有一些建立在集合S S上的运算；上的运算；定义定义:设设*是集合是集合S上的二元运算上的二元运算,对任一对任一x,y S有有x yS则称则称 运算在运算在S上是

5、封闭的。上是封闭的。在在f f：Z Z2 2Z Z二元运算的定义中二元运算的定义中,定义本身要求满足运算定义本身要求满足运算是封闭的条件。是封闭的条件。2 2 运算及其性质运算及其性质例：（例：（1 1）在集合在集合A=1，2，3，4，5，1/2，1/3，1/4，1/5，求，求任意元素的倒数运算；任意元素的倒数运算；（2 2）在前例中）在前例中,R,I,R,I集合中集合中+,-,+,-,运算；运算；(Z)(Z)的元素中的元素中,运算等均为封闭的；运算等均为封闭的；（3 3）在正整偶数的集合）在正整偶数的集合E E中中,对对,+,+运算是封闭的运算是封闭的,在正整在正整奇数的集合中奇数的集合中,

6、对对运算是封闭的运算是封闭的,而对而对+运算不是封闭的。运算不是封闭的。2 2运算及其性质运算及其性质在整数集合在整数集合 I 上定义上定义 如下：如下：其中的其中的+，分别表示数的加法和乘法。分别表示数的加法和乘法。,a bIa baba b 在集合在集合 I I 上是封闭的，上是封闭的，I 是一个代数系统。是一个代数系统。定义定义:设设*是集合是集合S S上的二元运算上的二元运算,对任一对任一x,yx,y S S有有x x y=y y=y x,x,则称则称 运算在运算在S S上是可交换的（或者说上是可交换的（或者说 在在S S上满足交换律）。上满足交换律）。例：例：在整合集合在整合集合 I

7、 I 上定义运算上定义运算 ：对任何对任何a,ba,b I,aI,a b=b=abab-(-(a+ba+b)其中的其中的 +，分别表示数的加法和乘法。分别表示数的加法和乘法。是否满足交换律？是否满足交换律？定义定义:设设*是集合是集合S上的二元运算上的二元运算,对任一对任一x,y,z S都有（都有（x y）z=x （y z）,则称则称 运算在运算在S上上是可结合的（或者说是可结合的（或者说*在在S上满足结合律）。上满足结合律）。例：设例：设A A是一个非空集合，是一个非空集合，是是A A上的二元运算，对上的二元运算，对于任意于任意a a，b b A A，有，有a ab b=b=b，证明：是满足

8、结合律的。，证明：是满足结合律的。证：证：对于任意的对于任意的a a，b b，c c A A，（a a b b）c=b c=b c=cc=c而而a a（b bc c）=a=a c=c c=c，（a ab b）c=ac=a（b bc c）是满足结合律的是满足结合律的例：代数系统（例：代数系统（N N，+，）。其中）。其中+，分别代表数分别代表数的加法和乘法。的加法和乘法。对对+满足分配律满足分配律 。定义定义:设设 和和 是集合是集合S S上的二个二元运算上的二个二元运算,对任一对任一x,y,zx,y,z S S有有 x x （y y z z）=（x x y y）（x x z z）（y y z

9、z）x=x=（y y x x）（z z x x）,则称运算则称运算 对对 是可分配的（或称是可分配的（或称 对对 满足分配律）。满足分配律）。定义定义:设设，是定义在集合是定义在集合S S上的两个可交换二上的两个可交换二 元运算，如果对于任意的元运算，如果对于任意的x,yx,y S S，都有：，都有：x x (x(x y)=xy)=x；x x (x x y y)=x)=x则称运算则称运算 和运算和运算 满足吸收律。满足吸收律。定义定义:设设*是是S上的二元运算上的二元运算,若对任一若对任一x S有有x x=x,则称则称 满足等幂律。满足等幂律。讨论定义：讨论定义：1)S上每一个元素均满足上每一

10、个元素均满足x x=x,才称才称 在在S上满足幂等律；上满足幂等律；2)若在若在S上存在某一元素上存在某一元素x，满足，满足x x=x,则称则称x为为S上的幂上的幂等元素；等元素；3)若若x是幂等元素是幂等元素,则有则有xn=x成立。成立。例例:（1）在实数集合）在实数集合R中中,+,是可交换是可交换,可结合的可结合的,对对+是满足是满足分配律的分配律的,“0”对对+是等幂元素是等幂元素,而其它不是等幂元素而其它不是等幂元素,在实数集在实数集合合R中中,“-”法是不可交换法是不可交换,不可结合的；不可结合的；（4 4）在）在(Z)(Z)中中,对称差对称差 是可交换是可交换,可结合的。可结合的。

11、=,而除而除 以外的元素以外的元素A A (Z)(Z)，有有A A AA AA。在集合在集合(Z)(Z)中，中，是等幂元素，其它不是。是等幂元素，其它不是。不不满足等幂满足等幂律。律。（2 2）在）在(Z)(Z)中中,均是可交换均是可交换,可结合的可结合的,对对,对对均满足分配律；均满足分配律；（3 3）(Z)(Z)中任一元素中任一元素,对对,均是等幂元素。均是等幂元素。,满足等幂律；满足等幂律；定义定义：设：设*是集合是集合Z中的二元运算中的二元运算,(1)若存在元素若存在元素el Z,对任意对任意x Z有有el*x=x；则称；则称el为为Z中对于中对于*的左幺元；的左幺元；(2)若存在元素

12、若存在元素er Z,对任意对任意x Z有有x*er=x；则称则称er为为Z中对于中对于*的右幺元。的右幺元。(3)如果如果Z中存在元素中存在元素 e,它既是左幺元它既是左幺元,又是右幺元又是右幺元,则称则称e为为Z中关于运算中关于运算*的幺元。即对于任意的幺元。即对于任意xZ,有有e*x=x*e.下面介绍左幺元，右幺元，幺元下面介绍左幺元，右幺元，幺元例：例：（1 1）在实数集合）在实数集合R R中中,对对+而言而言,e e+=0=0；对；对而言而言,e e=1=1 （2 2）在）在(Z)(Z)中中,对对而言而言,e e =Z=Z ；对；对而言而言,e e =（3 3）命题逻辑命题逻辑 中，对

13、中，对而言，而言，e e =F=F（永假式）（永假式）对对而言，而言，e e =T=T（永真式）（永真式）定理定理：若：若el和和er分别是分别是Z中对于中对于*的左幺元和右幺元的左幺元和右幺元,则则 el=er=e，且，且e Z是唯一的。是唯一的。证明：证明：el和和er分别是对分别是对*的左的左,右幺元，右幺元，则有则有el*er=er=el 有有el=er=e成立。成立。再证明幺元再证明幺元e是唯一的。是唯一的。用反证法：假设有二个不同的幺元用反证法：假设有二个不同的幺元e1和和e2,则有则有 e1*e2=e2=e1,这和假设相矛盾。这和假设相矛盾。若存在幺元，则幺元一定是唯一的。若存在

14、幺元，则幺元一定是唯一的。例：例：设代数系统（设代数系统（N，*），），*的定义为：的定义为：对对那么，（那么，（N，*）有没有幺元？左幺元？右幺元？）有没有幺元？左幺元？右幺元？,*ba bNa ba解：对任何解：对任何a a N,aN,a*1=a1=a1 1=a=a，因此，因此 1 1 是右幺元。是右幺元。但但 1 1 不是左幺元，因为不是左幺元，因为 1 1*2=12=12 2=1 2=1 2。所以所以 N 没有左幺元，当然也就没有幺元。没有左幺元，当然也就没有幺元。定义定义：设：设*是对集合是对集合Z Z中的二元运算，中的二元运算，(1)(1)若存在元素若存在元素l l Z Z，且对任

15、意且对任意x x Z Z有有 l l *x=x=l l ，则称，则称l l 为为Z Z中对于中对于*的左零元；的左零元；(2)(2)若存在元素若存在元素r r Z Z，且对任意且对任意x x Z Z有有 x x*r r=r r ，则称则称r r为为Z Z中对于中对于*的右零元。的右零元。(3)(3)如果如果Z Z中存在元素中存在元素,它既是左零元它既是左零元,又是右零元又是右零元,则称则称为为Z Z中关于运算中关于运算*的零元。对于任意的零元。对于任意xZxZ,有有 *x=xx=x*=下面介绍左零元，右零元，零元下面介绍左零元，右零元，零元例：例：（1）在实数集合）在实数集合R中，对中，对而言

16、而言,L=r=0（2）在）在(Z)中，对中，对而言，而言，=对对而言，而言，=Z （3）命题逻辑命题逻辑中，对中，对而言，而言，=T 对对而言，而言，=F 证明：证明：l和和r分别是对分别是对*的左的左,右零元，右零元，则有则有l*r=r=l 有有l=r=成立。成立。再证明零元再证明零元是唯一的。是唯一的。用反证法：假设有二个不同的零元用反证法：假设有二个不同的零元 1和和 2,则有则有 1*2=2=1,这和假设相矛盾。这和假设相矛盾。若存在零元，则零元一定是唯一的。若存在零元，则零元一定是唯一的。定理定理：若：若l和和r分别是分别是Z中对于中对于*的左零元和右零的左零元和右零元，则元，则l=

17、r=，且，且 Z是唯一的。是唯一的。定义定义：设：设*是是Z Z中的二元运算，中的二元运算，且且Z Z中含幺元中含幺元e e，令，令x x Z Z，（1 1）若存在一）若存在一x xl l Z Z，能使，能使x xl l *x=x=e e，则称，则称x xl l是是x x的左的左逆元逆元,并且称并且称x x是左可逆的；是左可逆的；（3 3）若元素）若元素x x既是左可逆的，又是右可逆的，则称既是左可逆的，又是右可逆的，则称x x是可逆的，且是可逆的，且x x的逆元用的逆元用x x-1-1表示。表示。（2 2）若存在一）若存在一x xr r Z Z，能使，能使x x*x xr r=e e，则称，

18、则称x xr r是是x x的右逆元，并且称的右逆元，并且称x x是右可逆的；是右可逆的；下面介绍左逆元，右逆元，逆元下面介绍左逆元，右逆元，逆元讨论逆元定义：讨论逆元定义：(1)(1)只有当幺元存在时，才考虑逆元。只有当幺元存在时，才考虑逆元。(2)(2)逆元是逆元是“局部局部”的，逆元是针对具体元素而定的，的，逆元是针对具体元素而定的，有些元素可能有逆元，有些元素可能没有逆元。如有些元素可能有逆元，有些元素可能没有逆元。如果果 a a 和和 b b 都有逆元且都有逆元且 a a b b，则，则 a a-1-1 和和 b b-1-1 也不也不相同。相同。(3)(3)设设 e e 为幺元，只有当

19、为幺元，只有当 a a b=e b=e 和和 b b a=e a=e 同时成立时，同时成立时，a,ba,b才能互为逆元，即才能互为逆元，即a a-1-1=b,b=b,b-1-1=a=a。证明：（证明：（1 1）先证左逆元）先证左逆元=右逆元：右逆元：设设 x xl l和和 x xr r分别是分别是x x Z Z的左逆元和右逆元，的左逆元和右逆元，x x是可逆的和是可逆的和*是可结合的是可结合的 定理定理：设：设Z Z是集合，并含有幺元是集合，并含有幺元e e 。*是定义在是定义在Z Z上的一个上的一个二元运算，并且是可结合的。若二元运算，并且是可结合的。若x x Z Z是可逆的，则它的左逆是可

20、逆的，则它的左逆元等于右逆元，且逆元是唯一的。元等于右逆元，且逆元是唯一的。x xl l *x=xx=x*x xr r =e e x xl l *x x*x xr r=（x xl l*x x）*x xr r=e e *x xr r=x xr r ；x xl l *x x*x xr r=x=xl l*(x(x*x xr r)=x)=xl l*e e=x=xl l x xl l=x xr r（2 2）证明逆元是唯一的：）证明逆元是唯一的：假设假设x x1 1-1-1和和x x2 2-1-1均是均是x x的二个不同的逆元，则的二个不同的逆元，则 x x1 1-1-1=x=x1 1-1-1*e e=x

21、 x1 1-1-1 *（x x*x x2 2-1-1 ）=（x x1 1-1-1 *x x）*x x2 2-1-1 =e e *x x2 2-1-1=x=x2 2-1-1，这和假设相矛盾。这和假设相矛盾。x x 若存在逆元，则若存在逆元，则x x 的逆元一定是唯一的。的逆元一定是唯一的。推论推论(x-1)-1=x,e-1=e 例：例：在实数集合在实数集合R中，对中，对“+”运算，对任一运算，对任一x R有有 x+（-x）=0，0为加法幺元为加法幺元 所以所以x-1=-x,(x-1)-1=x，0-1=0 对对“”运算，乘法幺元为运算，乘法幺元为1，x 1 x=1，则对任一则对任一x R有有x-1=1 x（x 0）,(x-1)-1=x，1-1=1 定理：设定理：设是一个代数系统是一个代数系统,且集合且集合A中的元素个中的元素个数大于数大于1,如果该代数系统中存在幺元如果该代数系统中存在幺元e和零元和零元，则，则 e。若若是一个代数系统是一个代数系统,且且|A|1,如果该代数系如果该代数系 统统 有零元，有零元，*x=x*=e 则零元一定不存在逆元。则零元一定不存在逆元。