离散数学-14.1代数系统.ppt

《离散数学-14.1代数系统.ppt》由会员分享，可在线阅读，更多相关《离散数学-14.1代数系统.ppt（23页珍藏版）》请在三一办公上搜索。

1、1,第14章 代数系统,2,第14章 代数系统,14.1 二元运算及其性质14.2 代数系统14.3 几个典型的代数系统,3,14.1 二元运算及其性质,14.1.1 二元运算与一元运算的定义二元运算定义及其实例 一元运算定义及其实例 运算的表示14.1.2 二元运算的性质交换律、结合律、幂等律、分配律、吸收律特异元素：单位元、零元、可逆元消去律,4,二元运算的定义及其实例,定义14.1 设 S 为集合,函数 f:SSS 称为S上的二元运算,简称为二元运算.也称 S 对 f 封闭.例1(1)N上的二元运算：加法、乘法.(2)Z上的二元运算：加法、减法、乘法.(3)非零实数集 R*上的二元运算:

2、乘法、除法.(4)设 S=a1,a2,an,ai aj=ai，为S上二元运算.(5)设Mn(R)表示所有n 阶(n2)实矩阵的集合，即 矩阵加法和乘法都是Mn(R)上的二元运算.(6)幂集 P(S)上的二元运算：、.(7)SS为S上的所有函数的集合,SS的合成运算.,5,一元运算的定义与实例,定义14.2 设S为集合，函数 f:SS 称为S上的一元运算，简称为一元运算.例2(1)Z,Q 和 R上求相反数的运算(2)非零有理数集Q*，非零实数集 R*上求倒数运算(3)复数集合C上求共轭复数的运算(4)幂集P(S)上,全集为S，求绝对补运算(5)A 为S上所有双射函数的集合，ASS，求反函数(6)

3、在 Mn(R)(n2)上求转置矩阵,6,二元与一元运算的表示,算符：,等符号 表示二元或一元运算 对二元运算，如果 x 与 y 运算得到 z，记做 xy=z；对一元运算,x 的运算结果记作 x 表示二元或一元运算的方法：公式、运算表注意：在同一个问题中不同的运算使用不同的算符,7,公式表示 例3 设 R 为实数集合，如下定义 R 上的二元运算：x,yR,x y=x.那么 3 4=3，0.5(3)=0.5运算表（表示有穷集上的一元和二元运算）二元运算的运算表 一元运算的运算表,实例,8,运算表的实例,例4 A=P(a,b),分别为对称差和绝对补运算（a,b为全集）的运算表 的运算表,9,运算表的

4、实例(续),例5 Z5=0,1,2,3,4,分别为模 5 加法与乘法 的运算表 的运算表,10,二元运算的性质,定义14.3 设 为 S 上的二元运算,(1)如果对于任意的 x,yS 有 x y=y x,则称运算在 S 上满足交换律.(2)如果对于任意的 x,y,zS 有(x y)z=x(y z),则称运算在 S 上满足结合律.(3)如果对于任意的 xS 有 x x=x,则称运算在 S 上满足幂等律.,11,实例,例6 Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为A上A，|A|2.,12,二元运算的性质(续),定义14.4 设 和 为 S 上两

5、个不同的二元运算,(1)如果对于任意的 x,y,zS 有(x y)z=(x z)(y z)z(x y)=(z x)(z y)则称 运算对 运算满足分配律.(2)如果 和 都可交换,并且对于任意的 x,yS 有 x(x y)=x x(x y)=x 则称 和 运算满足吸收律.,13,实例分析,例7 Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为A上A，|A|2.,14,二元运算的特异元素,单位元定义14.5 设 为S上的二元运算,如果存在el（或er）S，使得对任意 xS 都有 el x=x(或 x er=x)，则称 el(或 er)是 S 中关于

6、运算的 左(或右)单位元.若 eS 关于 运算既是左单位元又是右单位元，则称 e 为 S 上关于 运算的单位元.单位元也叫做幺元.,15,二元运算的特异元素(续),零元定义 设 为 S 上的二元运算,如果存在l(或r)S，使得对任意 xS 都有 l x=l(或 x r=r)，则称l(或r)是 S 中关于 运算的 左(或右)零元.若S关于 运算既是左零元又是右零元，则称为 S 上关于运算的零元.,16,二元运算的特异元素(续),可逆元素及其逆元 定义 令 e 为 S 中关于运算 的单位元.对于 xS，如果存在yl（或 yr）S 使得 yl x=e（或 x yr=e），则称 yl(或 yr)是 x

7、 的左逆元(或右逆元).关于 运算，若 yS 既是 x 的左逆元又是 x 的右逆元，则称 y 为 x 的逆元.如果 x 的逆元存在，就称 x 是可逆的.,17,实例分析,和 E 分别表示n 阶全0 矩阵 和 单位实数矩阵,18,惟一性定理,定理14.1 设 为S上的二元运算，el 和 er 分别为 S 中关于运算的左和右单位元，则 el=er=e 为 S 上关于 运算的惟一的单位元.证 el=el er=er 所以 el=er,将这个单位元记作 e.假设 e 也是 S 中的单位元，则有 e=e e=e.惟一性得证.类似地可以证明关于零元的惟一性定理.注意：当|S|2，单位元与零元是不同的；当|

8、S|=1时，这个元素既是单位元也是零元.,19,惟一性定理(续),定理14.2 设 为 S 上可结合的二元运算,e 为该运算的单位元,对于 xS 如果存在左逆元 yl 和右逆元 yr,则有 yl=yr=y,且 y 是 x 的惟一的逆元.证 由 yl x=e 和 x yr=e 得 yl=yl e=yl(x yr)=(yl x)yr=e yr=yr令 yl=yr=y,则 y 是 x 的逆元.假若 yS 也是 x 的逆元,则 y=y e=y(x y)=(y x)y=e y=y所以 y 是 x 惟一的逆元.说明：对于可结合的二元运算，可逆元素 x 只有惟一的逆元，记作 x-1.,20,消去律,定义14

9、.6 设 为集合S上二元运算，如果对于任意元素 x,y,zS,x，都有 x y=x z y=z,y x=z x y=z成立，则称 运算满足消去律.例如，普通加法和乘法满足消去律，矩阵加法满足消去律，矩阵乘法不满足消去律.集合的并和交运算也不满足消去律，例如11,2=21,2，但是12.,21,例题分析,例7 设 运算为 Q 上的二元运算，x,yQ,x y=x+y+2xy,(1)判断 运算是否满足交换律和结合律，并说明理由.(2)求出 运算的单位元、零元和所有可逆元素的逆元.,解(1)运算可交换.任取x,yQ,x y=x+y+2xy=y+x+2yx=y x,运算可结合，任取x,y,zQ,(x y

10、)z=(x+y+2xy)+z+2(x+y+2xy)z=x+y+z+2xy+2xz+2yz+4xyz x(y z)=x+(y+z+2yz)+2x(y+z+2yz=x+y+z+2xy+2xz+2yz+4xyz,22,(2)设 运算的单位元和零元分别为 e 和，则对于任意 x 有 x e=x 成立，即 x+e+2xe=x e=0 由于 运算可交换，所以 0 是幺元.,给定 x，设 x 的逆元为 y,则有 x y=0 成立，即 x+y+2xy=0(x=1/2)是 x 的逆元,x 1/2.,例题分析(续),对于任意 x 有 x=成立，即 x+2x=x+2x=0=1/2 1/2为零元.,23,例题分析(续),下面是三个运算表(1)说明那些运算是可交换的、可结合的、幂等的.(2)求出每个运算的单位元、零元、所有可逆元素的逆元.,解(1)满足交换律、结合律；满足结合律、幂等律；满足交换律、结合律.,(2)的单位元为 b,没有零元，a1=c,b1=b,c1=a 的单位元和零元都不存在，没有可逆元素.的单位元为 a，零元为c,a1=a.b,c不是可逆元素,