离散课件9代数系统.ppt

第九章 代数系统 n9.1 二元运算及其性质 n9.2 代数系统 n9.3 代数系统的同态与同构 思想：用抽象的数去度量和处理任意对象. 代数系统不关心具体“数”的研究，而是专 注于抽象的代数元素及其运算！ 一、二元运算 定义：设S为集合, 函数f: SSS称为S上的 二元运算，简称为二元运算 f: SS称为S上的一元运算 例如 f: NNN, f()=x+y 是N上的二元运算 f: N N, f(x)=x+1 是N上的一元运算 9.1 二元运算及其性质 通常用, *, 等符号表示二元运算,称为算符 如二元运算中 f()=z, 可用算符简记为 xy=z 一元运算中 f(x)=y, 可用算符简记为 x=y 注: (1) S上的二元运算即x, yS, xyS; (2) S上的一元运算即xS, xS. 运算封闭 例1. (1) N上加法, 乘法都是二元运算, 但减法, 除法不是. (2) Z上加法, 乘法, 减法都是二元运算, 但除法不是. Z上求相反数的运算是一元运算. (3) 非零实数集R*上的乘法和除法都是二元运算. 但加法, 减法不是, 而求倒数是一元运算. (4) Mn表示所有n阶实矩阵的集合 (n2), 则矩阵的加法 和乘法都是二元运算, 矩阵的转置是一元运算. (5) 集合S的幂集P(S)上的-都是二元运算, 而绝对补集(S为全集)是一元运算. (6) 所有命题公式的集合上的,都是二元运算, 而为一元运算. (7) SS表示集合S上的所有函数的集合, 函数的复合运 算是SS上的二元运算. 例2. 判断普通的加法和乘法运算在下列集 合中是否为二元运算. (1) S1=1, 2 (2) S2=0, 1 (3) S3=2x|xZ+ (4) S4=2x-1|xZ+ (5) S5=2n|nZ+ (1) 加法、乘法都不是； (2) 加法不是，乘法是； (3) 加法、乘法都是； (4) 加法不是，乘法是； (5) 加法不是，乘法是. 当S为有限集时, S上的一元和二元运算都可 以用运算表给出. 例3. (1) 设S=1, 2, 给出P(S)上的运算绝对 补集和对称差的运算表, 其中S为全集. (2) 设S=0, 1, 2, 3, 4, 定义S上的两个二元运算 如下: xy=(x+y)mod5, x, yS xy=(xy)mod5, x, yS 求运算和的运算表. 二、二元运算的运算律 设和是S上的二元运算，x, y, zS 1. 若x y=y x, 则称在S上可交换(满足交换律 ) 2. 若(x y) z = x (y z), 则称在S上可结合 ( 满足结合律) 3. 若x (y z) = (x y) (x z), (y z) x = (y x) (z x), 则称运算对是可分配的(对满足分配律) 4. 若xx=x, 则称满足幂等律 5. 若和均可交换, x(xy)=x, x(xy)=x, 则称和满足吸收律 例4. (1) 普通的加法和乘法在N, Z, Q, R上都 是可结合的, 且是可交换的, 乘法对加法 是可分配的. (2) 矩阵的加法和乘法在Mn上是可结合的, 加 法可交换, 但乘法不可交换, 乘法对加法是可 分配的. (3), , 在幂集P(S)上可结合, 可交换, 和 是互相可分配的, 和满足吸收律. (4) , 在全体命题公式集合上可结合, 可交换, 和是相互可分配的，且满足吸收律. 三、一些特殊元素 设是S上的二元运算， 1. 幺元e: 若eS, 对xS, ex=xe=x, 则称e 为运算的幺元 注：(1) 若幺元存在, 则必唯一. (2) 若只有elx=x或只有xer=x, 则el称为左 幺元, er称为右幺元. (3) 若左幺元和右幺元都存在, 则必相等. 例如：在N, Z, Q, R上, 加法的幺元是0, 乘法的 幺元是1. 在Z上的减法运算没有幺元, 只有右幺 元0 (x-0=x). 在Mn上, 矩阵加法的幺元是n阶0矩阵, 矩阵乘法的幺元是n阶单位矩阵. 在幂集P(S)上, 运算的幺元是, 运算 的幺元是全集 S. 例5. 在R*(非零实数集)上定义运算如下: ab=a a, bR* 则R*中任何元素都是右幺元, 但无左幺元, 从而无幺元. 2. 零元: 若S, 对xS, x=x=, 则称 为运算的零元. 注：(1) 若零元存在, 则必唯一. (2) 若只有lx=l或只有xr=r , 则l称为 左零元, r称为右零元. (3) 若左零元和右零元都存在, 则必相等. 如例4 (ab=a), R*的任何元素都是左零元,但没 有右零元, 从而没有零元. 例如：在N, Z, Q, R上加法没有零元, 乘法的零 元是0. 在Mn上矩阵加法没有零元, 矩阵乘法的 零元是n阶0矩阵. 在幂集P(S)上, 运算的零元是全集S, 运算的零元是. 定理：设为S上的二元运算, e和分别为的幺 元和零元. 如果|S|2, 则e . 3. 逆元: 设是S上的二元运算, eS为运算的 幺元. 若对xS, 存在x -1S, x -1 x=x x -1=e, 则称x -1为x的逆元. 注：(1) 逆元是针对某个元素而言的. (可能有的元素有逆元，有的没有) (2) 若只有xl-1x=e或只有xxr-1=e, xl-1称为 左逆元, xr-1称为右逆元. (3) 若二元运算满足结合律且x的左逆元 和右逆元都存在, 则左、右逆元必相等. 例如：普通加法运算在N, Z, Q, R上有幺元0， 仅在Z, Q, R上任意元素x有逆元(-x), 在N上 只有0有逆元0, 而其他自然数都没有逆元. 在Mn上矩阵的乘法只有可逆矩阵存在逆元. 幂集P(S)上关于运算有幺元, 但除了外, 其余元素都没有逆元. 例6. 在实数集R上定义运算如下： a, bR, ab=a+b+2ab (1) 是R上的二元运算吗？ (2) 在R上满足交换律、结合律吗？ (3) R关于有幺元、零元吗？ (4) R关于每个元素有逆元吗？ (1) 是； (2) 满足交换律、结合律； (3) 0为幺元，-1/2是零元； (4) -1/2无逆元，其余元素均有逆元. 例7. 设A=a, b, c, d，二元运算和如下表定 义, 问：运算和是否可交换？是否有零元？ 是否有幺元？如果有幺元, 指出哪些元素有逆 元, 逆元是什么？ (1) (2) 解：(1) 运算可交换, 没有零元, a是幺元; a, b, c, d都有逆元, a-1=a, c-1=c, b, d互为逆元; (2) 运算不可交换, a是左零元, b是幺元, 只有b有逆元, b-1=b, 由于cd=b, 故c是d的左逆 元, d是c的右逆元, 但a, c, d的逆元都不存在. 四、二元运算运算律的补充 设是S上的二元运算,为的零元, x, y, zS (1) 若xy=xz且x, 则y=z; (2) 若yx=zx且x, 则y=z; 则称满足消去律, 其中(1)称为左消去律, (2) 称为右消去律. 9.2 代数系统 一、代数系统 定义1. 非空集合S和S上的k个一元或二元运算 f1, f2, , fk组成的系统称为一个代数系统, 简称 代数, 记作. 例如: , , , , 定义2. 在某些代数系统中对于给定的二元运 算存在幺元或零元，它们对该系统的性质起着 重要作用，称为代数常数 (特异元素) 例如: 的幺元是0, 也可记为 中和的幺元分别为和S, 同 样可记为 定义3. 如果两个代数系统中运算的个数相同, 对应运算的元数相同, 且代数常数的个数也相同 , 则称这两个代数系统具有相同的构成成分(同 类型的代数系统). 例如: 和 都含有两个二元运算、一个一元运算和两个代 数常数，因而它们是同类型的代数系统. 同类型的代数系统不一定具有相同的运算性质. 定义4. 设V=是代数系统, BS, 如果B对f1, f2, , fk都是封闭的, 且B和S含有 相同的代数常数, 则称是V的 子代数系统, 简称子代数. 有时将子代数系统 简记为B. 例如： 是的子代数， 是的子代数； 但是的子代数, 却不是 的子代数. 定义4. 设V=是代数系统, BS, 如果B对f1, f2, , fk都是封闭的, 且B和S含有 相同的代数常数, 则称是V的 子代数系统, 简称子代数. 有时将子代数系统 简记为B. 注: (1)子代数与原代数是同类型的代数系统, 而且对应的二元运算都具有相同的运算性质. (2)B=V是V最大的子代数； B=V中的代数常数是V最小的子代数； 统称为平凡子代数. (3)当BV时, B是V的真子代数. 例1. 设V=, 令 nZ=, n为自然数， 则nZ是V的子代数. 证明：任取nZ中两个元素nz1, nz2 (z1, z2 Z), 则有nz1+nz2=n(z1+z2)nZ, 即nZ对+运算是封 闭的. 又0=n0 nZ, 所以nZ是V的子代数. 注：当n=1时, nZ=Z; 当n=0时, 0Z= 0 ; 它们是V的平凡子代数, 而其他的子代数 都是V的非平凡的真子代数. 二、积代数 定义5. 设V1=, V2=是同类型的代 数系统, 和为二元运算. 令S=S1S2, 对, S1S2, = , 则为代数系统, 称为V1与V2的积代数, 记 作V1V2. 也称V1和V2为V1V2的因子代数. 例如：V1=, V2= 对, ZM3, = , 故V1V2=. V1有代数常数0, V2有代数常数I3, V1V2有代数常数. 定理：设V1=, V2=是同类型的代 数系统, V1V2= . (1) 如果 和 运算是可交换(可结合、幂等)的 , 那么 运算也是可交换(可结合、幂等)的； (2) 如果e1和e2(1和2)分别为 和 运算的幺 元(零元), 那么 ()也是 运算 的幺元(零元)； (3) 如果x和y分别为 和 运算的可逆元素, 那 么也是 运算的可逆元素, 其逆元就是 . 注：积代数也保留因子代数的分配律和吸收律 等性质，但不保留消去律. 例： V1= , V2=， V1和V2中的运算都满足消去律； V1V2中运算不满足消去律 = = 不是零元,若消去,则=,错误. 9.3 代数系统的同态与同构 定义1. 设V1=,V2=是同类型的代 数系统, 如果存在映射f: S1S2满足 对x, yS1有 f(xy)=f(x)f(y), 则称f是V1到V2的同态映射,简称同态 x y f(x) f(y) xyf(xy)=f(x)f(y ) 先运算后取 像等同于 先取像后运 算 定义1. 设V1=,V2=是同类型的代 数系统, 如果存在映射f: S1S2满足 对x, yS1有 f(xy)=f(x)f(y), 则称f是V1到V2的同态映射,简称同态 注: (1) 若f是单射, 则称为单同态; 若f是满射, 则称为满同态, 记作V1V2; 若f是双射, 则称为同构, 记作V1V2 (2) 若f: VV, 则称为自同态. 例1. (1) 设V1 =, V2=, 其中是 普通加法, 是模n加法, 令 f: Z Zn , f(x)=(x)modn, 证明: f 是V1到V2的满同态. 证: 显然 f 是满射. x, yZ, f(xy)=(xy)modn=(x)modn(y)modn =f(x)f(y), 所以 f 是V1到V2的满同态. f(0)=(0)modn =0 注: 满同态映射把幺元映到幺元. 例1. (2) 设V=, 给定aZ, 令 fa: ZZ, fa(x)=ax, xZ, 证明: fa 是V的自同态. 证: 任取z1, z2Z, 有 fa(z1z2)= a(z1z2)= az1az2 = fa(z1)fa(z2), 所以 fa 是V的自同态. 注: a=0时, f0(x)=0(xZ), 称为零同态; a=1时, f1(x)=x(xZ), 称为自同构; a0, 1时, fa 都是单同态 性质1.设f 是V1=到V2=的满同态, 则 (1) 若可交换, 则也可交换; (2) 若可结合, 则也可结合; (3) 若e是关于的幺元, 则f。