离散数学代数系统.ppt

《离散数学代数系统.ppt》由会员分享，可在线阅读，更多相关《离散数学代数系统.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第5章 代数系统,离 散 数 学,本章说明,本章的主要内容 一元和二元运算定义及其实例 二元运算的性质 代数系统定义及其实例 子代数,与后面各章的关系 是后面典型代数系统的基础,5.1 二元运算及其性质 5.2 代数系统 本章小结 作 业,本章内容,5.1 二元运算及其性质,定义5.1 设S为集合，函数 f：SSS 称为S上的二元运算，简称为二元运算。 举例 f:NNN，f()x +y 是自然数集合N上的二元运算 f:NNN，f()x - y 不是自然数集合N上的二元运算 称N对减法不封闭。,说明,验证一个运算是否为集合S上的二元运算主要考虑两点： S中任何两个元素都可以进行这种运算，且运算的

2、结果是唯一的。 S中任何两个元素的运算结果都属于S，即S对该运算是封闭的。,（1）自然数集合N上的加法和乘法是N上的二元运算，但减法和除法不是。 （2）整数集合Z上的加法、减法和乘法都是Z上的二元运算，而除法不是。 （3）非零实数集R*上的乘法和除法都是R*上的二元运算，加法、减法不是。 （4）设Sa1,a2,an，aiaj =ai为S上二元运算。,例5.1,例5.1,（5）设Mn(R)表示所有n阶(n2)实矩阵的集合，即,则矩阵加法和乘法都是Mn(R)上的二元运算。 （6）S为任意集合，则、 为P(S)上的二元运算。 （7）SS为S上的所有函数的集合，则合成运算为SS上的二元运算。,一元运算

3、,定义5.2 设S为集合，函数f：SS称为S上的一元运算，简称为一元运算。 例5.3 （1）求一个数的相反数是整数集合Z、有理数集合Q和实数集合R上的一元运算。 （2）求一个数的倒数是非零有理数集合Q*、非零实数集合R*上的一元运算。 （3）求一个复数的共轭复数是复数集合C上的一元运算。,（4）在幂集P(S)上，如果规定全集为S，则求集合的绝对补运算是P(S)上的一元运算。 （5）设S为集合，令A为S上所有双射函数的集合，ASS，求一个双射函数的反函数为A上的一元运算。 （6）在n(n2)阶实矩阵的集合Mn(R)上，求一个矩阵的转置矩阵是Mn(R)上的一元运算。,一元运算举例,可以用、等符号表

4、示二元或一元运算，称为算符。 设f : SSS是S上的二元运算，对任意的x, yS，如果x与y的运算结果为z，即f()z，可以利用算符简记为xy = z。 对一元运算，x的运算结果记作x。 例题 设R为实数集合，如下定义R上的二元运算 x,yR，x y = x。 那么 3 4 = 3，0.5 (3) = 0.5。,二元与一元运算的算符,函数的解析公式 运算表（表示有穷集上的一元和二元运算）,二元与一元运算的表示,例5.4 设S=1,2，给出P(S)上的运算和的运算表 ，其中全集为S。,解答,例5.4,例5.5 设S=1,2,3,4，定义S上的二元运算如下 x y(xy) mod 5， x,yS

5、 求运算的运算表。,解答,例5.5,定义5.3 设为S上的二元运算，如果对于任意的x,yS都有xy=yx，则称运算在S上满足交换律。 定义5.4 设为S上的二元运算，如果对于任意的x,y,zS都有 (xy)z=x(yz)，则称运算在S上满足结合律。 说明：若+适合结合律，则有 (x+y)+(u+v) x+y+u+v。,二元运算的性质,二元运算的性质,定义5.5 设为S上的二元运算，如果对于任意的xS有xx=x，则称运算在S上满足幂等律。如果S中的某些x满足xx=x，则称x为运算的幂等元。 举例：普通的加法和乘法不适合幂等律。但0是加法的幂等元，0和1是乘法的幂等元。,例题,Z, Q, R分别为

6、整数、有理数、实数集；Mn(R)为n阶实矩阵集合, n2；P(B)为幂集；AA为从A到A的函数集，|A|2 。,定义5.6 设和为S上两个二元运算，如果对于任意的x,y,zS，有 x(yz) (xy) (xz)（左分配律）(yz)x (yx) (zx)（右分配律） 则称运算对运算满足分配律。 说明：若*对运算分配律成立，则*对运算广义分配律也成立。 x(y1 y2 yn ) (xy1)(x y2) (x yn) (y1 y2 yn )x (y1x) (y2x) (ynx),二元运算的性质,定义5.7 设和为S上两个可交换的二元运算，如果对于任意的x,yS，都有 x(xy)x x(xy)x 则称

7、运算和满足吸收律。,二元运算的性质,Z, Q, R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合，n2；P(B)为幂集；AA为从A到A的函数集，|A|2 。,例题,定义5.8 设为S上的二元运算， 如果存在元素el（或er）S，使得对任意xS都有 elx = x (或xer = x) 则称el (或er)是S中关于运算的一个左单位元(或右单位元)。 若eS关于运算既是左单位元又是右单位元，则称e为S上关于运算的单位元。单位元也叫做幺元。,运算可以没有左单位元和右单位元。 运算可以只有左单位元。 运算可以只有右单位元。 运算可以既有左单位元，又有右单位元。,说明,二元运算中的特异元素单位

8、元,二元运算中的特异元素零元,定义5.9 设为S上的二元运算， 如果存在元素l（或r）S，使得对任意xS都有 lx = l (或xr = r)， 则称l (或r)是S上关于运算的左零元(或右零元)。 若S关于运算既是左零元又是右零元，则称为S上关于运算的零元。,运算可以没有左零元和右零元。 运算可以只有左零元。 运算可以只有右零元。 运算可以既有左零元，又有右零元。,说明,二元运算中的特异元素逆元,定义5.10 设为S上的二元运算，eS为运算的单位元，对于xS， 如果存在yl（或yr）S使得 ylxe（或xyre） 则称yl（或yr）是x的左逆元（或右逆元）。 若yS既是x的左逆元又是x的右逆

9、元，则称y为x的逆元。 如果x的逆元存在，则称x是可逆的。,运算可以没有左逆元和右逆元。 运算可以只有左逆元。 运算可以只有右逆元。 运算可以既有左逆元，又有右逆元。,说明,特异元素的实例,定理5.1,定理5.1 设为S上的二元运算，el、er分别为运算的左单位元和右单位元，则有 el = er = e 且e 为S上关于运算的唯一的单位元。,el eler (er为右单位元) eler er (el为左单位元) 所以el = er，将这个单位元记作e。 假设e也是S中的单位元，则有 e = ee = e 所以，e 是S中关于运算的唯一的单位元。,证明,定理5.2,定理5.2 设为S上的二元运算

10、，l和r分别为运算的左零元和右零元，则有 l = r = 且为S上关于运算的唯一的零元。,l lr (r为左零元) lr r (l为右零元) 所以l = r，将这个零元记作 。 假设 也是S中的零元，则有 = = 所以， 是S中关于运算的唯一的零元。,证明,定理5.3,定理5.3 设为S上的二元运算，e 和分别为运算的单位元和零元，如果S至少有两个元素，则e。,用反证法。 假设 e = ，则xS有 x x e x 这与S中至少含有两个元素矛盾。 所以，假设不 成立，即e。,证明,定理5.4,定理5.4 设为S上可结合的二元运算，e为该运算的单位元，对于xS，如果存在左逆元yl和右逆元yr，则有

11、 yl = yr= y 且y是x的唯一的逆元。,由 ylx = e 和 xyr = e ，得,证明,yl = yle,令yl = yr = y，则y是x的逆元。,= yl (xyr),= (ylx) yr,= eyr,= yr,假若yS也是x的逆元，则,y= ye,= y (xy),= (yx) y,= ey,= y,所以y是x唯一的逆元，记作x1。,消去律,定义5.11 设为S上的二元运算，如果对于任意的x,y,zS，满足以下条件： （1）若xy xz且x ，则y z （左消去律） （2）若yx zx且x ，则yz （右消去律） 则称运算满足消去律。 例如： 整数集合上的加法和乘法都满足消去

12、律。 幂集P(S)上的并和交运算一般不满足消去律。,例5.6,例5.6 对于下面给定的集合和该集合上的二元运算，指出该运算的性质，并求出它的单位元、零元和所有可逆元素的逆元。 （1）Z+，x,yZ+，xylcm(x,y)，即求x和y的最小公倍数。 （2）Q，x,yQ，xy=x+y-xy,解答,（1）运算可交换、可结合、是幂等的。 xZ+，x1=x ， 1x=x ，1为单位元。 不存在零元。 只有1有逆元，是它自己，其他正整数无逆元。,（2） Q，x,yQ，xy=x+y-xy 运算满足交换律，因为x,yQ，有 xy =x+y-xy = y+x-yx = yx 运算满足结合律，因为x,y,zQ，有

13、 (xy)z=(x+y-xy)z=x+y-xy+z-(x+y-xy)z= x+y+z-xy-xz-yz+xyz x(yz)=x(y+z-yz)=x+(y+z-yz)-x(y+z-yz)=x+y+z-xy-xz-yz+xyz 运算不满足幂等律，因为2Q，但22 =2+2-2202 运算满足消去律，因为x,y,zQ，x1(1为零元)，有 xy = xz x+y-xy=x+z-xz y-z = x(y-z) y=z 由于是可交换的，所以右消去律成立。同理可证明左消去律成立，所以消去律成立。,例5.6,0是运算的单位元，因为 xQ，有 x0=x+0-x0=x=0 x 1是运算的零元，因为 xQ，有 x

14、1=x+1-x1=1=1x xQ，欲使 xy=0和 yx=0成立，即 x+y-xy = 0 得,所以，,例5.7,例5.7 设A=a,b,c，A上的二元运算、如表所示。 (1)说明、运算是否满足交换律、结合律、消去律和幂等律。 (2)求出关于、运算的单位元、零元和所有可逆元素的逆元。,运算满足交换律、结合律和消去律，不满足幂等律。单位元是a，没有零元，且a-1=a，b-1=c，c-1=b。 运算满足交换律、结合律和幂等律，不满足消去律。单位元是a，零元是b，只有a有逆元，a-1=a。 运算满足结合律和幂等律，不满足交换律和消去律。没有单位元，没有零元，没有可逆元。,解答,复习,分析,5.2 代

15、数系统,定义5.12 非空集合S和S上k个一元或二元运算f1,f2, fk组成的系统称为一个代数系统，简称代数，记做。,5.2 代数系统,实例： 、都是代数系统，其中+和分别表示普通加法和乘法。 是代数系统，其中和分别表示n阶(n2)实矩阵的加法和乘法。 是代数系统，其中和为并和交，为绝对补。 是代数系统，其中Zn0,1,2, ,n-1 和分别表示模n的加法和乘法。,集合（规定了参与运算的元素） 运算（只讨论有限个二元和一元运算） 代数常数 在定义代数系统的时候，如果把零元和单位元也作为系统的性质，称这些元素为该代数系统的特异元素或代数常数。 有时为了强调某个代数系统是含有代数常数的系统，也可

16、以把这些代数常数列到系统的表达式中。 例如：代数系统。,代数系统的成分,列出所有的成分：集合、运算、代数常数(如果存在)例如 ， 列出集合和运算，在规定系统性质时不涉及具有单位元的性质（无代数常数） 例如 ， 用集合名称简单标记代数系统 例如 在前面已经对代数系统作了说明的前提下，上述两个代数系统可以简记为Z, P(S),代数系统的表示,定义5.13 如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分，也称它们是同类型的代数系统。,同类型的代数系统,例如 V1= V2= V1、V2是同类型的代数系统，因为它们都含有2个二元运算，

17、1个一元运算， 2个代数常数。但是它们的运算性质不一样。,同类型的代数系统,在规定了一个代数系统的构成成分，即集合、运算以及代数常数以后，如果在对这些性质所遵从的算律加以限制，那么满足这些条件的代数系统就具有完全相同的性质，从而构成了一类特殊的代数系统。 例如：代数系统V，如果*是可结合的，则称V为半群。如、等都是半群。 从代数系统的构成成分和遵从的算律出发，将代数系统分类，然后研究每一类代数系统的共同性质，并将研究的结果运用到具体的代数系统中去。(抽象代数的基本方法),代数系统地说明,定义5.14设V是代数系统，BS，如果B对f1, f2, , fk 都是封闭的，且B和S含有相同的代数常数，

18、则称是V的子代数系统，简称子代数。简记为B。 例如： N是的子代数，N也是的子代数 N0是的子代数，但不是的子代数。,子代数和原代数具有相同的成分，运算性质也相同，是同类型的代数系统，在许多方面与原代数非常相似，不过可能小一些。 对于任何代数系统，其子代数一定存在。,说明,子代数,最大的子代数：就是V本身。 最小的子代数：如果令V中所有代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则B就构成了V的最小的子代数。 平凡的子代数：最大和最小的子代数称为V的平凡的子代数。 真子代数：若B是S的真子集，则B构成的子代数称为V的真子代数。,子代数的相关概念,例5.8 设V=，令 nZ=nz |

19、 zZ，n为自然数， 则nZ是V的子代数。,任取nZ中的两个元素nz1和nz2(z1,z2Z )，则有 nz1+nz2 n(z1+z2 )nZ 即nZ对+运算是封闭的。又 0=n0 nZ 所以，nZ是V的子代数。,证明,当n=1和0时，nZ是V的平凡子代数，其他的都是V的非平 凡的真子代数。,说明,例5.8,试讨论 的运算性质,有单位元,例 在 中, 为有理数,零元、逆元吗？,解: 对任意,集. 对,设单位元为e,设零元为,逆元,时,设a的逆元为x,单位元也是零元,问A是什么集合?,例 * 为 上的二元运算,它的,解: 设aA, 且a为A上*的单位元,和零元,对任意xA, 有,单位元,零 元,

20、必为单元素集.,即,例 设 上 满足结合律,且对,试证 对任意的自然数 , 有,证明: 对 用归纳法,由,得,当 时,得,时,成立,时,结合,所以对任意的 ,有,5.3代数系统的同构与同态,两个代数系统(0,1, )和(a,b,*),0 a 1 b,两个代数系统同构的条件 1.必须是同型代数系统 2.两个集合的元素个数应相等 3.运算定义法则相同，即对应元素运算后的结果也对应 代数系统(0,1, )和(a,b,*)满足上述条件, 即同构,定义：设(X ,)和(Y ,*)是两个相同类型的代数系统，其运算都是二元运算，如果存在一个一一对应的函数g：X Y， 使得g(x1 x2)= g(x1) *g

21、(x2) x1 , x2X 则称g 是一个从(X ,)到(Y ,*)的同构函数 或者称(X ,)和(Y ,*)同构 可记为：(X ,) (Y ,*),(X ,) (Y ,*),X1 X2 x1 x2,g(x1) g(x2 ) g(x1) *g(x2),看例题书,定理：代数系统(X ,) (Y ,*) 1.若(X ,) 满足结合律,则(Y ,*)也满足结合律 2.若(X ,) 满足交换律,则(Y ,*)也满足交换律 3.若(X ,) 有单位元1x,则(Y ,*)也有单位元1y， 且1y = g(1x) 4.若(X ,) 对xX都存在逆元素x-1，则(Y ,*)也对yY都存在逆元素y-1 , 并且

22、若g(x) =y，则g(x-1) =y-1 5.若(X ,) 有零元0 x,则(Y ,*)也有零元0y， 且0y = g(0 x),定理：代数系统(X ,，*) (Y , ，) 若(X ,，*) 满足分配律，则(Y , ，)也满足分配律 定理：代数系统之间的同构关系是等价关系 一个代数系统和自身的同构称为自同构,定义：设(X ,)和(Y ,*)是两个相同类型的代数系统，其运算都是二元运算，如果存在一个一一对应的函数g：X Y， 使得g(x1 x2)= g(x1) *g(x2) x1 , x2X 则称g 是一个从(X ,)到(Y ,*)的同构函数 或者称(X ,)和(Y ,*)同构 可记为：(X

23、 ,) (Y ,*),单 射,映射 函数,满(单、双)射,满射,定义：设(X ,)和(Y ,*)是两个相同类型的代数系统，其运算都是二元运算，如果存在一个函数g：X Y，使得 g(x1 x2)= g(x1) *g(x2) x1 , x2X 则称g 是一个从(X ,)到(Y ,*)的同态映射 或者称(X ,)和(Y ,*)同态 如函数为满函数，则称(X ,)和(Y ,*)满同态 如函数为单射函数，则称(X ,)和(Y ,*)单同态 一个代数系统和自身的同态称为自同态,U= (I, +) V=(S, )是代数系统 f: UV 偶数0 奇数1 f是U到V的同态，不是满也不是单,U= (I, +) V

24、=(S, )是代数系统 f: UV 偶数0 奇数1 f是U到V的满同态，不是单同态,例题：U=(N,+)，V=(I,+) f: x2x 是U到V的单同态，不是满同态,例题：U=(I,+)，V=(2I,+) f: I2I定义为：x 2x 是U到V的同构,例题:,则（T，*）是代数系统 对U=（I，+）和V=（T，*） 讨论U和V的关系,本章主要内容,构成代数系统的基本成分 非空集合 集合上若干个封闭的二元和一元运算 代数常数 二元运算性质和特异元素 同类型的与同种的代数系统 子代数的定义与实例,本章学习要求,判断给定集合和运算能否构成代数系统。 判断给定二元运算的性质和特异元素。 了解同类型和同

25、种代数系统的概念。 了解子代数的基本概念 。,作业,习题：,运算的性质与特异元素,二元运算f：SSS 一元运算f：SS 交换律x,yS， xy yx 结合律x,y,z S，(xy)z x(yz) 幂等律xS， x x x 消去律 x,yS， xy xz且x y z y xzx且x y z,运算的性质与特异元素,分配律x,y,z S， x(yz) (xy) (xz)， (yz)x (yx) (zx) 吸收律x,yS， x(xy)x，x(xy)x 单位元exS， x e e x x 零元xS， x x 幂等元x x x 可逆元x y y x e,通过运算表判别运算性质的方法,交换律的表沿主对角线对称。 幂等律的表主对角线与每一行和每一列元素相同。 如果在运算表中的某行或某列(除了零元所在的行或列之外)有两个相同的元素，那么运算不满足消去律。 有零元的表，当且仅当该元素所对应的行和列与该元素相同。,通过运算表判别运算性质的方法,有单位元的表，当且仅当该元素所对应的行和列依次与运算表的行和列相同。 a与b互逆，当且仅当以这两个元素为行和列的交点处为单位元。 如果元素x在主对角线中排列的位置与表头中的位置一致，那么该元素是幂等元。,