离散数学-耿素云PPT(第5版).ppt

《离散数学-耿素云PPT(第5版).ppt》由会员分享，可在线阅读，更多相关《离散数学-耿素云PPT(第5版).ppt（27页珍藏版）》请在三一办公上搜索。

1、1,代数系统简介,2,第9章 代数系统简介,9.1 二元运算及其性质9.2 代数系统9.3 几个典型的代数系统,3,9.1 二元运算及其性质,二元运算及一元运算的定义二元运算的性质交换律、结合律、幂等律、消去律分配律、吸收律 二元运算的特异元素单位元零元可逆元素及其逆元,4,二元运算的定义及其实例,定义 设 S 为集合,函数 f：SSS 称为 S 上的二元运算,简称为二元运算.也称 S 对 f 封闭.例1(1)N 上的二元运算：加法、乘法.(2)Z 上的二元运算：加法、减法、乘法.(3)非零实数集 R*上的二元运算:乘法、除法.(4)设 S=a1,a2,an,ai aj=ai，为 S 上二 元

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

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

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

5、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 则称 和 运算满足吸收律.,15,实例分析,Z,Q,R分别为整数、有理数、实数集；Mn(R)为 n 阶实矩阵集合,n2；P(B)为幂集；AA为 A上A，|A|2.,16,二元运算的特异元素,单位元定义 设为S上的二元运算,如果存在el（或er）S，使得对任意 xS 都有 el x=x(或 x er=x)，则称 el(或 er)是 S 中关于 运算的 左(或右)单位元.若 eS 关于 运算既是左单位元又是右

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

7、x 的右逆元，则称 y 为 x 的逆元.如果 x 的逆元存在，就称 x 是可逆的.,19,实例分析,20,唯一性定理,定理 设 为S上的二元运算，el 和 er 分别为 S 中关于运算的左和右单位元，则 el=er=e 为 S 上关于 运算的惟一的单位元.证 el=el er=el er=er 所以 el=er,将这个单位元记作 e.假设 e 也是 S 中的单位元，则有 e=e e=e.惟一性得证.类似地可以证明关于零元的惟一性定理.注意：当|S|2，单位元与零元是不同的；当|S|=1 时，这个元素既是单位元也是零元.,21,惟一性定理（续）,定理 设 为 S 上可结合的二元运算,e 为该运算

8、的单位元,对于 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 只有惟一的逆元，记作 x1.,22,消去律,定义 设为V上二元运算，如果 x,y,zV，若 x y=x z，且 x不是零元，则 y=z 若 y x=z x,且 x 不是零元，则

9、y=z 那么称 运算满足 消去律.实例:Z,Q,R 关于普通加法和乘法满足消去律.Mn(R)关于矩阵加法满足消去律，但是关于矩阵乘法不满足消去律.Zn关于模 n 加法满足消去律，当 n 为素数时关于模 n乘法满足消去律.当 n 为合数时关于模 n 乘法不满足消去律.,23,例题分析,解(1)运算可交换，可结合.任取x,yQ,x y=x+y+2xy=y+x+2yx=y x,任取x,y,zQ,(x y)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+4x

10、yz,例6 设 运算为 Q 上的二元运算，x,yQ,xy=x+y+2xy,(1)运算是否满足交换和结合律?说明理由.(2)求 运算的单位元、零元和所有可逆元.,24,给定 x，设 x 的逆元为 y,则有 x y=0 成立，即 x+y+2xy=0(x=1/2)因此当 x 1/2时，是 x 的逆元.,例题分析（续）,(2)设运算的单位元和零元分别为 e 和，则对于任意 x 有 xe=x 成立，即 x+e+2xe=x e=0 由于 运算可交换，所以 0 是幺元.,对于任意 x 有 x=成立，即 x+2 x=x+2 x=0=1/2,25,例题分析（续）,例7(1)说明那些运算是交换的、可结合的、幂等的

11、.(2)求出运算的单位元、零元、所有可逆元素的逆元.,解(1)满足交换、结合律；满足结合、幂等律；满足交换、结合律.,(2)的单位元为 b,没零元，a1=c,b1=b,c1=a 的单位元和零元都不存在，没有可逆元素.的单位元为 a，零元为c,a1=a.b,c不可逆.,26,例题分析（续）,例8 设 A=a,b,c,构造 A 上的二元运算*使得 a*b=c,c*b=b,且*运算是幂等的、可交换的，给出关于*运算的一个运算表，说明它是否可结合，为什么？,c,b,根据幂等律和已知条件a*b=c,c*b=b 得到运算表,根据交换律得到新的运算表,方框 可以填入a,b,c中任一选定的符号,完成运算表,不结合，因为(a*b)*b=c*b=b,a*(b*b)=a*b=c,27,由运算表判别算律的一般方法,交换律：运算表关于主对角线对称幂等律：主对角线元素排列与表头顺序一致消去律：所在的行与列中没有重复元素单位元:所在的行与列的元素排列都与表头一致零元：元素的行与列都由该元素自身构成A 的可逆元：a 所在的行中某列(比如第 j 列)元素为 e，且第 j 行 i 列的元素也是 e，那么 a 与第 j 个元素互逆结合律：除了单位元、零元之外，要对所有3个元素的组合验证表示结合律的等式是否成立,