近世代数单元测试题（二） （院系：软件学院 年级：2007级） 一、选择题（在每个小题四个备选答案中选出一个正确答案，填在题末括号里） 1．下列运算中，哪中运算关于整数集不能构成半群（ ）。 A ．max{,}a b a b = B ．a b b = C ．||a b a b =- D ． 2a b ab = 2．在自然数集合N 上定义运算*为：对任意a ，b ∈N ，a *b =a +b +a b ， 则下面说法正确的是（ ）。 A ． D.
第九章半群与群（Semigroups and Groups）本章讨论含一个二元运算的特殊的代数系统――半群与群。群论近世代数中发展最早、内容最丰富、应用最广泛的部分，也是建立其他代数系统的基础。群论在自动机政论、形式语言，语法分析快速加法器设计、纠错码制定等方面均有卓有成效的应用。 2－1 半群与含幺半群 定义2－1.1 满足结合律的代数系统U=和，因为( ) =<(s 1*s 2 )*s 3 ,(t 1 t 2 ) t 3 >== ( ) 故
第六章群与环 1. S={2n | n N}，加法是S上的二元代数运算吗？乘法呢？ 解：加法不是S上的二元代数运算，乘法是。 2. 自然数集N 上的二元代数运算* 定义为x * y = x y，* 是否满足结合律？是否满足交换律？ 解：都不满足。 3. 设* 是集合S上的二元代数运算，且满足结合律，设x，y是S中任意元素，如果x * y = y * x，则x = y。试证明* 满足等幂律。 证明：由于对S中任意的x，y和z，有x*(y*z)=(x*y)*z，故x*(x*x)=(x*x)*x，于是有x*x=x。
4. 设（G，·）是代数系统，则（G×G，*）是代数系统，这里G×G的运算“*”规定如下： （a，b）*（c，d）=（a·c，b·d）， 其中，a，b，c，d为G中任意元素。证明：当（G，·）是半群时，（G×G，*）是半群；当（G，·）有单位元素时，（G×G，*）有单位元素；当（G，·）是群时，（G×G，*）是群； 证明：设（G，·）是半群，a，b，c，d，e，f为G中任意元素，若有(a，b),(c，d)，(e，f)属于G×G，则有 (a，b)*((c，d)*(e，f))=(a，b)*(c·e，d·f)=(a·(c·e)，b·(d·f)) =((a·c)·e，(b·d)·f))=((a·c)，(b·d))*(e，f)=((a，b)*(c，d))*(e，f)， 这就证明了当（G，·）是半群时，（G×G，*）是半群。 设（G，·）有单位元素1，(a，b)是（G×G，*）中任意元素，则有(a，b)=(a·1，b·1)=(a，b)*(1，1)且(a，b)=(1·a，1·b)=(1，1)*(a，b)，故(1，1)就是（G×G，*）的单位元素。 设（G，·）是群，1是群（G，·）的单位元素，则由前面的证明知(1，1)就是（G×G，*）的1且（G×G，*）是半群。 我们来证明（G×G，*）中的任意元素(a，b)有逆元素。(1，1)=(a·a’，b·b’)=(a，b)*(a’，b’)，其中a’和b’分别是a和b在群（G，·）中的逆元素。同样有(1，1)=(a’·a，b’·b )=(a’，b’ )*(a，b )，这就证明了(a’，b’ )是(a，b)的逆元素，从而说明（G×G，*）是群。
§4.5 陪集与商群 习题4.5 1. 集合}19210{20，，，， =Z 在“模20加法20+”下构成群。设H 是由元素5生成的20Z 的子群。 （1）求H 的每个元素及其次数。 （2）求H 在20Z 中的所有左陪集。 解 （1）}151050{，，， =H ，151050，，，的次数分别为：1，4，2，4。 （2）H 在20Z 中的所有左陪集如下： }151050{，，，=H ，}161161{1，，，=H ，}171272{2，，，=H }181383{3，，，=H ，}191494{4，，，=H 2. 求12阶循环群}{11432a a a a a e G ，，，，，， =的子群}{84a a e H ，，=在G 中的所有左陪集。 解 所有左陪集如下： }{84a a e H ，，=，}{95a a a aH ，，=，}{10622a a a H a ，，= 3. 设H 是群>*<， G 的子群，证明H 的所有不同左陪集（右陪集）中有且仅又一个在*下构成>*<， G 的子群。 解 略 4. 证明6阶群必含有3次元。 解 略 5. 证明偶数阶群必含2次元。 解 设>*<， G 是偶数阶群，若它无二次元，则对G 中的非单位元a ，有 1-≠a a 所以，G 中的元素，除单位元外，其他都是成对出现的，所以G 中的元素是偶数个，矛盾。故偶数阶群必含2次元。 6. 证明在有限群中次数大于2的元素的个数必定是偶数。 解 略 7. 设>*<， G 是一个阶数为p 的有限群，其中p 是质数，证明G 是循环群并求它的所有子群。 解 略 8. 设H 和K 分别是群>*<，G 的s r ，阶子群，若s r ，互质，证明}{e K H = 。 解 略 9. 设i 为虚数单位，即12-=i ，令 ?????????? ??±???? ??-±???? ??-±???? ? ?±=000110001001i i i i G ，，， 证明G 在矩阵乘法下构成群，并 （1）给出G 的运算表。 （2）找出G 的所有子群。
11.群和编码Group and coding §11.1 二进编码和查错 coding of binary information and error detection Alphabet 字母集。B ＝{0,1}. message 从有限alphabet 中选取有限多个符号组成的一个序列。 word m 个0和1组成的一个序列。 B ＝B ×B ×……×B （m 个）。 B m 的加法⊕： (x 1,x 2,…,x m )⊕(y 1,y 2,…,y m ) =(x 1+y 1 ,x 2+y 2,…,x m +y m ) B m 中共有2m 个元素, B m 的阶是2m 。 0＝(0,0,……,0). 由于disterbance （noise ）x ≠x t 。 用编码方法查错、纠错。 取n>m ，一一对应 e ：B m →B n ，
称e是（m,n）编码函数。 b∈B m，e(b)∈B n叫做b的码词Code word e(b)比b多几位0，1用来查错和纠错。 将要发出的word b编码得到x=e(b),发送后接收到x t，如果没有干扰，x＝x t，b＝e-1(x t). 如果有干扰，x和x t有≤k位出错，即有1位到k位错误。 x的权（weight）：x含有1的个数，记做|x|. 奇偶校验码parity check code： 如果b＝b1b2…b m， 令e(b)＝b1b2…b m b m+1, b m+1=0, if |b|是偶数， b m+1=1, if |b|是奇数。 b m+1=0, 当且仅当b含有偶数个1。 m＝3 e(000)=0000 e(001)=0011 e(010)=0101 e(011)=0110 e(100)=1001 e(101)=1010 e(110)=1100 e(111)=1111 对任意b，e(b)的权总是偶数。 设b=111，x＝e(b)=1111. 如果接收到有一位错x t＝1101， x t的权是奇数，发现有错。 x t的权是偶数，无法判断有错。 例3．（m，3m）编码函数： e：B m→B3m， b＝b1b2…b m， e(b)＝b1b2…b m b1b2…b m b1b2…b m. e(000)=000000000
第9章半群和群semigroup and group §9.1 二元运算复习binary operation revisited A上二元运算 f：A×A→A f处处有定义的函数。 Dom（f）＝A×A， 对任意a，b∈A，f(a，b)∈A，唯一确定。 二元运算常记做＋，－，×，*，?，等等 对任意a，b∈A，a?b∈A 说成A对?封闭。 A＝{a1,a2,……,a n}时，二元运算可以用运算表给出。 二元运算的性质 1可换commutative a*b=b*a 2 结合associative a*(b*c)=(a*b)*c 3 幂等idempotent
a*a=a 特殊元素 单位元 对任意a∈A，e*a=a*e＝a. 单位元也叫恒等元 零元 对任意a∈A，0*a=a*0＝0
逆元 对任意a，b∈A，a*b=b*a＝e a,b互为逆元 代数结构 (A,*)A上定义了二元运算满足 1)封闭性 2)结合律-----------半群 3)有单位元---------独异点 4)有逆元-----------群 5)可交换-----------交换群例子： 1)(Z n +), (Z n, ) 2)(A*, *) 字符串的连接Homework P323－324 16，20，22，24，25，26
§9.2 半群semigroup 半群定义： (S,*) *是S上乘法，满足结合律。 半群的例 (Z，＋），（Z，×）， （N，×），（N，＋）， （Q，＋），（R，×）， （P(S),∪），（P(S), ∩）， （M n，＋），（Mn，×）， S上全体映射，对于复合， （L，∧），（L，∨），L是格 （A*, ）, 定理1. 半群中，n个元素的乘积与乘法的次序无关。幂power： 设（S，*）是半群，a∈S，定义a的幂power：
面向对象中类概念与群的概念的相关性 一：群 对任意代数系统（G，·），若满足：①对任意x,y∈G.x·y=c∈G； ②对任意x,y,z∈G，x·（y·z）=（x·y）·z； ③G中有一个元素e, 对任意x∈G,使x·e=e·x=x； ④对任意x∈G，存在x-1∈G,使x· x-1 =x-1·x=e； 则（G，·）就是一个群。 二：类 类是对自然现象或实体的程序语言描述，具有相同或相似性质的对象的抽象就是类。因此，对象的抽象是类，类的具体化就是对象，也可以说类的实例是对象。类具有属性，它是对象的状态的抽象，用数据结构来描述类的属性。类具有操作，它是对象的行为的抽象，用操作名和实现该操作的方法来描述。 属性说明了这个类的特性，方法是对属性的操作。 三：类与群 有群的定义可知，群也就是一个满足各种条件的多个以非空集合和其上的二元代数运算为元素的集合，而类是具有共同属性、共同方法、共同事件的对象的集合。所以二者就有了共同之处。若我们可以用（G，·）中的“G”表示类中的属性，“·”表示类中的方法，则群（G，·）就可以表示一个类。从而用“群”概念可以很简单明了地表示出“类”的概念，这样也方便我们将数学的知识应用到计算机领域。四：继承与群
面向对象中继承是指面向对象中一个类自动拥有另一个类的全部属性和方法，是子类自动共享父类数据结构和方法的机制，这是类之间的一种关系。在定义和实现一个类的时候，可以在一个已经存在的类的基础之上来进行，把这个已经存在的类所定义的内容作为自己的内容，并加入若干新的内容。继承性是面向对象程序设计语言不同于其它语言的最重要的特点，是其他语言所没有的。 由于子群享有群的任意性质和方法，并且子群中的单位元和原群的单位元一致，所以也可以将其的关系看作是继承。 五：子类与子群 面向对象中通过继承创建的新类称为“子类”或“派生类”。被继承的类称为“基类”、“父类”或“超类”。“子类”的定义使得在程序的编译过程更加的清楚简洁，大大地提高了编程的效率。同样的，在离散数学中，“子群”的提出也是更利于数学的研究，相同于“类”可以用“群”的概念表示，面向对象中的“子类“也可以用“子群”的概念表示。 设群（H，·）为群（G，·）的子群，因为G的子群H不只是一个包含在G中的群，而且H的运算必须与G的运算一样。所以子群与群的关系同子类与类的关系，又因为群可以表示类的概念，所以可以用子群表示子类的概念。 A09计算机张海燕 090604135