离散数学第章代数结构.pptx

离散数学第章代数结构 2 5、1 代数结构简介 1、 代数结构得定义 定义 设A就是非空集合, f1, f2,…, fk(k  1)就是A上得代数(封闭)运算, 则集合A连同其上得代数运算称为代数结构或代数系统或简称代数, 记为(A, f1, f2,…, fk), 在已知运算得情况下可简记为A、 若A就是有限集合,则称为有限代数结构,否则为无限代数结构。 3 对于代数结构得理解, 需注意以下几点: (1) A非空; (2) f1, f2,…, fk为代数运算; (3) (k + 1)-元组(A, f1, f2,…, fk); (4) 运算得元数可以不同、 例 (1) (R, +): Group、 (2) (R, +, ): Ring、 (3) Boolean Algebra、 4 5 6 7 8 9 10 2、 两种最简单得代数结构: 半群及独异点 定义 设*就是非空集合 S 上得2元代数运算, 若*满足结合律, 即对于任意x, y, z S, 有(x*y)*z = x*(y*z), 则(S, *)称就是半群、 例 (Z, +), (R, )、 (Z, -), (R, /) 不就是半群、 11 例 设  就是若干个字母组成得集合, 称为字母表, 由  中有限个字母组成得序列称为上得串, 不含任何字母得串称为空串, 记为、 令 * 就是所有  上得串组成得集合, 其上得运算◦为 *上得连接运算: 易证: (*, ◦)就是半群、  上得所有非空串组成得集合+, 关于其上得串得连接运算也构成一个半群(+, ◦)、 大家学习辛苦了,还就是要坚持 继续保持安静 13 定义 设*就是非空集合M上得2元代数运算, 若*满足结合律且M关于*有幺元e, 即对于任意xM, 有e*x = x*e = x, 则称(M, *, e)为独异点、 含幺半群就就是独异点、 (Z, +),(R, )? (Z, +,0), (R, ,1) 例 (*, ◦, ) 就是独异点, 而(+, ◦)不就是、 14 备注 (1)在(*, ◦ , )中得称为代数常数、 代数结构 中得代数常数可以不止一个, 也可以没有代数 常数、 (2) (*, ◦)就是半群, (*, ◦ , )就是独异点, 它们就是 两个不同得代数结构、 我们可以将代数常数瞧作就是0元运算,(*, ◦, )有1个0元运算(及1个二元运算)、 (1) * 封闭, 因此 (I, *) 就是代数系统; 例:定义 I上* : 证明 (I, *) 就是独异点、 证 15 综上,(I, *,e) 就是独异点、 16 17 Theorem 设(S, *)就是有限半群, 则(S, *)中存在幂等元素、 先定义任意元素a得正整数方幂: R, : R, +: Proof 取 Theorem 设(S, *)就是有限半群, 则(S, *)中存在幂等元素、 18 19 3、 子代数 定义 设 (A, f1, f2,…, fk) 就是代数结构,   S  A, 若(S, f1, f2,…, fk)就是代数结构, 则称其为(A, f1, f2,…, fk)得子代数, 或在不强调运算情况下简称S就是A得子代数、 一般地, 要验证 S 就是否就是 A 得子代数, 只要验证 S 关于 A 中运算就是否封闭即可、 例 (Z, +, 、)就是(R, +, 、)得子代数, 因为整数集合Z关于加法运算与乘法运算就是封闭得、 20 例 由第1章1-3节可知,(Z8, 8, 1)就是独异点, 其中Z8 = {0, 1, 2, 3, 4, 5, 6, 7}, 8就是模8得乘法运算,即x 8 y = (xy)(mod 8)、 取S = {0, 2, 4} S关于运算就是封闭得, 但因为1 S,即S关于Z8中得0元运算不封闭, 所以S不就是Z8得子代数、 21 4、 代数结构得同态与同构 借助于映射也就是研究代数结构得方法之一: 映射得作用体现、 定义 设 (A, f1, f2,…, fk) 与 (B, g1, g2,…, gk) 就是代数结构, 若fi与gi有相同得运算元数, i = 1, 2, …, k, 则称这两个代数结构就是同类型得、 22 定义 设(A, f1, f2,…, f