《离散数学 复习 华师计算机学院》由会员分享，可在线阅读，更多相关《离散数学 复习 华师计算机学院（76页珍藏版）》请在金锄头文库上搜索。
1、1,大概的考试题型,选择题 20 填空题 30 计算（简答）题 20 证明题 30,2,第三部分 代数结构,主要内容 代数系统: 二元运算及其性质、代数系统和子代数 半群与群: 半群、独异点、群 环与域: 环、整环、域,3,第九章 代数系统,主要内容 二元运算及其性质 一元和二元运算定义及其实例 二元运算的性质 代数系统 代数系统定义及其实例 子代数 积代数 代数系统的同态与同构,4,基本要求,判断给定集合和运算能否构成代数系统 判断给定二元运算的性质 求而二元运算的特异元素 了解同类型和同种代数系统的概念 了解子代数的基本概念 计算积代数 判断函数是否为同态映射和同构映射,5,一、二元运算及
2、其性质,定义9.1 设S为集合，函数f：SSS 称为S上的二元运算，简 称为二元运算 S中任何两个元素都可以进行运算，且运算的结果惟一 S中任何两个元素的运算结果都属于S，即S对该运算封闭 定义9.2 设S为集合，函数 f:SS 称为S上的一元运算，简 称一元运算.,6,二元运算的性质,定义9.3 设为S上的二元运算, (1) 若对任意x,yS 有 xy=yx, 则称运算在S上满足交换律. (2) 若对任意x,y,zS有 (xy)z=x(yz), 则称运算在S上满足结 合律. (3) 若对任意xS 有 xx=x, 则称运算在S上满足幂等律.,定义9.4 设和为S上两个不同的二元运算, (1)
3、若对任意x,y,zS有 (xy)z=(xz)(yz)， z(xy)=(zx)(zy), 则称运算对运算满足分配律. (2) 若和都可交换,且对任意x,yS有 x(xy)=x，x(xy)=x, 则称和运算满足吸收律.,7,特异元素：单位元、零元,定义9.5 设为S上的二元运算, (1) 如果存在el (或er)S，使得对任意 xS 都有 elx = x (或 xer = x)， 则称el (或er)是S中关于运算的左(或右)单位元. 若eS关于运算既是左单位元又是右单位元，则称e为S上 关于运算的单位元. 单位元也叫做幺元. (2) 如果存在 l (或 r)S，使得对任意 xS 都有 l x =
4、 l (或 x r = r)， 则称 l (或 r)是S 中关于运算的左(或右)零元. 若 S 关于运算既是左零元又是右零元，则称为S上关 于运算的零元.,8,可逆元素和逆元,(3) 设为S上的二元运算, 令e为S中关于运算的单位元. 对于xS，如果存在yl (或yr)S使得 ylx=e（或xyr=e） 则称yl (或 yr)是x的左逆元（或右逆元）. 关于运算，若yS 既是 x 的左逆元又是 x 的右逆元，则称 y为x的逆元. 如果 x 的逆元存在，就称 x 是可逆的.,9,惟一性定理,定理9.1 设为S上的二元运算，el和er分别为S中关于运算的 左和右单位元，则el = er = e为S
5、上关于运算的惟一的单位元. 类似地可以证明关于零元的惟一性定理. 注意： 当 |S| 2，单位元与零元是不同的； 当 |S| = 1时，这个元素既是单位元也是零元. 定理9.2 设为S上可结合的二元运算, e为该运算的单位元, 对于xS 如果存在左逆元 yl 和右逆元 yr, 则有 yl = yr= y, 且 y 是 x 的惟一的逆元.,10,9.2 代数系统,定义9.6 非空集合S和S上k个一元或二元运算f1, f2, fk组成 的系统称为代数系统, 简称代数，记做. 构成代数系统的成分： 集合（也叫载体，规定了参与运算的元素） 运算（这里只讨论有限个二元和一元运算） 代数常数（通常是与运算
6、相关的特异元素：如单位元等） 研究代数系统时，如果把运算具有它的特异元素也作为系统 的性质之一，那么这些特异元素可以作为系统的成分，叫做 代数常数.,11,子代数系统,定义9.8设V=是代数系统，B是S的非空子 集，如果B对f1, f2, , fk 都是封闭的，且B和S含有相同的代 数常数，则称是V的子代数系统，简称子代 数. 有时将子代数系统简记为B.,说明： 子代数和原代数是同种的代数系统 对于任何代数系统V=，其子代数一定存在.,12,第十章 群与环,主要内容 群的定义与性质 子群与群的陪集分解 循环群与置换群 环与域,13,基本要求,判断或证明给定集合和运算是否构成半群、独异点和群 熟
7、悉群的基本性质 能够证明G的子集构成G的子群 熟悉陪集的定义和性质 熟悉拉格朗日定理及其推论，学习简单应用 会求循环群的生成元及其子群 熟悉n元置换的表示方法、乘法以及n元置换群 能判断给定代数系统是否为环和域,14,半群、独异点与群的定义 半群、独异点、群的实例 群中的术语 群的基本性质,10.1 群的定义与性质,15,半群、独异点与群的定义,定义10.1 (1) 设V=是代数系统，为二元运算，如果运算是可 结合的，则称V为半群. (2) 设V=是半群，若eS是关于运算的单位元，则称V 是含幺半群，也叫做独异点. 有时也将独异点V 记作 V=. (3) 设V=是独异点，eS关于运算的单位元，
8、若 aS，a1S，则称V是群. 通常将群记作G.,16,有关群的术语,定义10.2 (1) 若群G是有穷集，则称G是有限群，否则称为无 限群. 群G 的基数称为群 G 的阶，有限群G的阶记作|G|. (2) 只含单位元的群称为平凡群. (3) 若群G中的二元运算是可交换的，则称G为交换群或阿贝 尔 (Abel) 群.,定义10.4 设G是群，aG，使得等式 ak=e 成立的最小正整数k 称为a 的阶，记作|a|=k，称 a 为 k 阶元. 若不存在这样的正整数 k，则称 a 为无限阶元.,17,群的性质：幂运算规则,定理10.1 设G 为群，则G中的幂运算满足： (1) aG，(a1)1=a
9、(2) a,bG，(ab)1=b1a1 (3) aG，anam = an+m，n, mZ (4) aG，(an)m = anm，n, mZ (5) 若G为交换群，则 (ab)n = anbn.,18,群的性质：消去律；元素的阶,定理10.3 G为群，则G中适合消去律，即对任意a,b,cG 有 (1) 若 ab = ac，则 b = c. (2) 若 ba = ca，则 b = c.,例 5 设G是群，a,bG是有限阶元. 证明 (1) |b1ab| = |a| (2) |ab| = |ba|,定理10.4 G为群，aG且 |a| = r. 设k是整数，则 (1) ak = e当且仅当r | k
10、 (2 )|a1| = |a|,19,10.2 子群与群的陪集分解,定义10.5 设G是群，H是G的非空子集， (1) 如果H关于G中的运算构成群，则称H是G的子群, 记作HG. (2) 若H是G的子群，且HG，则称H是G的真子群，记作HG.,例如 nZ (n是自然数) 是整数加群 的子群. 当n1时, nZ是Z的真子群. 对任何群G都存在子群. G和e都是G的子群，称为G的平凡 子群.,20,子群判定定理,定理10.5（判定定理一） 设G为群，H是G的非空子集，则H是G的子群当且仅当 (1) a,bH有abH (2) aH有a1H.,定理10.6 （判定定理二） 设G为群，H是G的非空子集.
11、 H是G的子群当且仅当a,bH 有ab1H.,定理10.7 （判定定理三） 设G为群，H是G的非空有穷子集，则H是G的子群当且仅当 a,bH有abH.,21,典型子群的实例,定义10.6 设G为群，aG，令H=ak| kZ， 则H是G的子群，称为由 a 生成的子群，记作.,定义10.7 设G为群,令 C=a| aGxG(ax=xa)， 则C是G的子群，称为G的中心.,例6 设G是群，H,K是G的子群. 证明 (1) HK也是G的子群 (2) HK是G的子群当且仅当 HK 或 KH,22,陪集,定义10.9 设H是G的子群，aG.令 Ha=ha | hH 称Ha是子群H在G中的右陪集. 称a为H
12、a的代表元素.,定理10.8 设H是群G的子群，则 (1) He = H (2) aG 有aHa,定理10.9 设H是群G的子群，则a,bG有 aHb ab1H Ha=Hb,23,推论,推论 设H是群G的子群, 则 (1) a,bG，Ha = Hb 或 HaHb = (2) Ha | aG = G 证明：由等价类性质可得.,定理10.10 设H是群G的子群，在G上定义二元关系R： a,bG, R ab1H 则 R是G上的等价关系，且aR = Ha.,24,左陪集的定义与性质,设G是群，H是G的子群，H 的左陪集，即 aH = ah | hH，aG 关于左陪集有下述性质： (1) eH = H
13、(2) aG，aaH (3) a,bG，abH b1aH aH=bH (4) 若在G上定义二元关系R， a,bG，R b1aH 则R是G上的等价关系，且aR = aH. (5) aG，H aH ,25,Lagrange定理,定理10.12 （Lagrange）设G是有限群，H是G的子群，则 |G| = |H|G:H 其中G:H 是H在G中的不同右陪集(或左陪集) 数，称为H在 G 中的指数.,推论1 设G是n阶群，则aG，|a|是n的因子，且有an = e. 推论2 对阶为素数的群G，必存在aG使得G = .,26,Lagrange定理的应用,命题：如果群 G 只含 1 阶和 2 阶元，则 G
14、 是Abel群.,例8 证明 6 阶群中必含有 3 阶元.,证 设a为G中任意元素，有a1 = a. 任取 x, yG，则 xy = (xy)1 = y1x1 = yx， 因此G是Abel群.,证 设G是6 阶群，则G中元素只能是1阶、2阶、3阶或6阶. 若G中含有6 阶元，设为a，则 a2是3 阶元. 若G中不含6 阶元，下面证明G中必含有3阶元. 如若不然，G 中只含1阶和2阶元，即aG，有a2=e，由命题知G是Abel 群. 取G中2阶元 a 和 b，a b，令 H = e, a, b, ab，则H 是 G的子群，但 |H| = 4，|G| = 6，与拉格朗日定理矛盾.,27,10.3
15、循环群与置换群,定义10.10 设G是群，若存在aG使得 G=ak| kZ 则称G是循环群，记作G=，称 a 为G 的生成元.,循环群的分类：n 阶循环群和无限循环群. 设G=是循环群，若a是n 阶元，则 G = a0=e, a1, a2, , an1 那么|G| = n，称 G 为 n 阶循环群. 若a 是无限阶元，则 G = a0=e, a1, a2, 称 G 为无限循环群.,28,循环群的生成元,定理10.13 设G=是循环群. (1) 若G是无限循环群，则G只有两个生成元，即a和a1. (2) 若G是 n 阶循环群，则G含有(n)个生成元. 对于任何小 于n且与 n 互质的数r0,1,n-1, ar是G的生成元. (n)成为欧拉函数，例如 n=12，小于或等于12且与12互素的 正整数有4个： 1, 5, 7, 11， 所以(12)=4.,29,循环群的子群,定理10.14 设G=是循环群. (1) 设G=是循环群，则G的子群仍是循环
