《离散数学代数结构部分》由会员分享,可在线阅读,更多相关《离散数学代数结构部分(126页珍藏版)》请在金锄头文库上搜索。
1、第三部分 代数结构,第五章 代数系统,代数结构又称为代数系统,简称代数,是抽象代数的主要研究对象。 代数系统的种类很多,它们在计算机科学的自动机理论、编码理论、形式语言、时序线路、开关线路计数问题以及计算机网络纠错码的纠错能力判断、密码学、计算机理论科学等方面有着非常广泛的应用。,本部分主要内容 二元运算及其性质。 二元运算中的特殊元素幺元,零元,逆元。 代数系统的定义及其性质。,定义5.1 设 为集合,函数 称为 上的二元运算,简称为二元运算。,5.1节 二元运算及其性质,在整数集合 上,对任意两个整数所进 行的普通加法和乘法,都是集合上的二 元运算。,如何判断一个运算是否为集合 上的 二元
2、运算,唯一性 集合S中任意的两个元素都能进行这种运 算,并且结果要是唯一的。,封闭性 集合S中任意的两个元素运算的结果都是 属于S的,就是说S对该运算是封闭的,例5.1设Ax|x ,nN,问在集合A上通常的乘法运算是否封闭,对加法运算呢?,解:对于任意的 所以乘法运算是封闭的。 而对于加法运算是不封闭的 , 因为至少有,定义5.2 设*是定义在集合A上的二元运算,如果对于任意的x,yA,都有x*yy*x,则称该二元运算*是可交换的。,例5.2 设Q是有理数集合,*是Q上的二元运算,对任意的a,bQ,a*ba+b-ab,问运算*是否可交换。,解:因为 a*ba+b-abb+a-bab*a, 所以
3、运算*是可交换的。,定义5.1 设 为集合,函数 称为 上的二元运算,简称为二元运算。,5.1节 二元运算及其性质,在整数集合 上,对任意两个整数所进 行的普通加法和乘法,都是集合上的二 元运算。,定义5.2 设*是定义在集合A上的二元运算,如果对于任意的x,yA,都有x*yy*x,则称该二元运算*是可交换的。,例5.2 设Q是有理数集合,*是Q上的二元运算,对任意的a,bQ,a*ba+b-ab,问运算*是否可交换。,解:因为 a*ba+b-abb+a-bab*a, 所以运算*是可交换的。,定义5.3 设*是定义在集合A上的二元运算,如果对于任意的x,y,zA,都有(x*y)*zx*(y*z)
4、,则称该二元运算*是可结合的,或者说运算*在A上适合结合律。,例5.3 设A=Z,“+”是整数中的加法:则,“+”在Z中适合结合律。,“。”是整数中的减法:则特取,而,运算“。”不满足结合律,定义5.4 设*是定义在集合A上的一个二元运算,如果对于任意的xA,都有x*xx,则称运算*是等幂的。,例5.4 设P(S)是集合S的幂集,在P(S)上定义的两个二元运算,集合的“并”运算和集合的“交”运算,验证,是等幂的。,解: 对于任意的AP(S), 有AAA和AAA, 因此运算和都满足等幂律。,定义5.5 设。和*是S上的两个二元运算,如果对任意的 有,例5.5 在实数集R上,,对于普通的乘法和加法
5、有,即乘法对加法是可分配的。,定义5.6 设。和*是定义在集合A上的两个可交换二元运算,如果对于任意的x,yA,都有,则称。运算和*满足吸收律,例5.6 设集合N为自然数全体,在N上定义两个二元运算*和,对于任意 x,yN,有x*ymax(x,y), xymin(x,y), 验证运算*和满足吸收律。,解:对于任意a,bN,a*(ab)max(a,min(a,b)a a(a*b)min(a,max(a,b)a 因此,*和满足吸收律。,定义5.7 设*是S上的二元运算,,5.2节 二元运算中的特殊元素,1. 幺元,在自然数集N上加法的幺元是0,乘法的幺元是1.,对于给定的集合和运算有的存在幺 元,
6、有的不存在幺元。,定理5.1 设*是S上的二元运算, 如果S中存在关于运算*的)幺元, 则必是唯一的。,所以幺元是唯一的。,定理5.2 设*是S上的二元运算, 如果S中既存在关于运算*的左幺元 , 又存在关于运算的右幺元 则S中必存在关于运算*的幺元e并且,定义5.8 设*是S上的二元运算,,2. 零元,在自然数集N上普通乘法的零元是0,而加法没有零元。,定理5.3 设 *是S上的二元运算,如果S中存在(关于运算*的)零元,则必是唯一的。,所以零元是唯一的。,定理5.4 设 *是S上的二元运算,如果S中既存在关于运算*的左零元 又存在关于运算*的右零元,定义5.9 设*是S上的二元运算,,2.
7、 逆元,例5.8 整数集Z上关于加法的幺元是0,对任意的整数m,它关于加法的逆元是-m,因为,定理5.5 设*是S上可结合的二元运算,e为幺元,如果S中元素x存在(关于运算* )的逆元,,则必是惟一的。,所以对于可结合的二元运算,逆元是惟一的。,定理5.6 设*是S上可结合的二元运算,e为幺元,如果S中元素x既存在关于运算*的左逆元 ,又存在关于运算*的右逆元 , 则 S中必存在x关于运算*的逆元并且,解:*运算适合交换律、结合律和消去律,不适合幂等律。单位元是a,没有零元,且,运算适合交换律、结合律和幂等律,不适合消去律。单位元是a,零元是b.只有a有逆元,,运算不适合交换律,适合结合律和幂
8、等律,不适合消去律。没有单位元,没有零元,没有可逆元素。,定义5.10 设S是非空集合,由S和S上若干个运算 构成的系统称为代数系统,记作,5.3节 代数系统,代数系统也简称为代数。,例如,R是实数集,对于普通的加法和剩法运算,,M是n阶方阵构成的集合,对于矩阵的加法和剩法运算,,定义5.11 设,都是封闭的,且B和S含有相同的代数常数, 则称,定义5.12 设,例5.11 设,定义5.13 设,定义5.14 设,例5.14 表示求两个数的最小公倍数的运算。则,解: 零元是不存在的, 只有惟一的逆元。,例5.15 在有理数集Q上定义二元运算*,解:,例5.16 设有集合,解:,讨论这5个集合对
9、普通的乘法和加法运算是否封闭。,例5.17 设,解:,第六章 几个典型的代数系统,本章讨论几类重要的代数结构: 半群、群、环、域、格与布尔代数,定义6.1 设,6.1节 半群与群,是可结合的即:,定义6.2若半群,例6.1(1)普通加法是,(2)普通乘法是N,Z,Q和R上的二元运算,满足 结合律且有幺元1,定义6.3 设,例6.2,定义6.3 设,定义6.4 设,定义6.5 设,例6.3 设,证明G关于矩阵乘法构成一个群,故G关于矩阵乘法是Z上的代数运算,矩阵乘法满足结合律,故G关于矩阵乘法构成半群,,在G中每个矩阵的逆元都是自己, 所以 G关于矩阵乘法构成一个群。,定义6.6 若群,例6.4
10、 (1)在 中除0之外都没有逆元,所以它仅是含幺半群而不是群。,中每个元素都有逆元即它的相反数,且运算满足交换律,所以它们是交换群。,0没有逆元,所以它们仅是有么半群而不是群。,例6.5设G=e,a,b,c,。为G上的二元运算,它由以下运算表给出。不难证明G是一个群,称该群为Klein四元群。,定义6.7 设,例6.6 在群,解:,定理6.1 设,证明:略。,定义6.8 设,定义6.9,例6.7 对于集合,列出其运算表如下表,从表中可以看出,运算满足封闭性,满足结合律和交换律,0是单位元,每个元都有逆元 ,,这个群的阶数是6,元素0,1,2,3,4,5的次数分别为1,6,3,2,3,6。,定理
11、6.2 设,下面证明唯一性,从而唯一性得证。,例6.8 设,定理6.3,定理6.4 设,定理6.5 G为有限群,则G的运算表中的每一行(每一列)都是G中元素的一个置换,且不同的行(或列)的置换都不相同。,定义6.10 设,例6.9,例6.10 群,定理6.6(子群判定定理1)设H是群 。,证明:必要性是显然的。,定理6.7( 子群判定定理2) 设H是群,证明:必要性,充分性证明:,定理6.8(子群判定定理3)设H是群,证明:必要性是显然的。,例6.11 设,定义6.11 设,6.2节 陪集与拉格朗日定理,例6.12 设,解: H的右陪集为,定理6.9 设H是群,定理6.10 设,定理6.11
12、设,证明: 略。,推论6.1,定理6.12 设,定理6.13 设,定义6.12 群,定理6.14(拉格朗日定理)设,即子群的阶数一定是群的阶数的因子。,根据定理6.11的推论有,推论6.2 设,推论6.3 设,根据定理6.11的推论有,定义6.13 设,任何群G都有正规子群,因为G的两个平凡子群,定理6.15 设,证明:略。,例6.13 设,例6.14 设,定理6.16 设,定义6.14 设,6.3 群的同态与同构,例6.13 设,定义6.15 设,定理6.17 设,证明:略。,定义6.16 设,定理6.18 (群同态基本定理)设,定义6.17 设,6.4 循环群与置换群,定理6.19 设,例
13、6.16,例6.17 设,定义6.18 设,例6.18 设,定义6.19 设,例6.19 4元置换,定义6.20设,定理6.20,定义6.21,例6.20 如图 进行旋转,也可以围绕它的对称轴进行翻转,但 经过旋转或翻转后仍要与原来的方格重合(方格 中的数字可以改变)。如果把每种旋转或翻转看 作是作用在,定义6.22 设,6.5 环和域,例6.21 (1)整数集,定理6.21 设,2,3证明略。,例6.22,定义6.23 设,例6.23 (1)整数环,例6.22模6整数环,定义6.24 设,定义6.22 设,6.5 环和域,例6.25 设,定义6.25 设,6.6 格与布尔代数,例6.26 设n是正整数,例6.27(1)对于偏序集,定理6.22 设,定理6.23 设,定义6.26 设,定义6.27 设,例6.28 设格,定义6.28 设,例6.29 说明下图中的格是否为分配格, 为什么?,定义6.29 设,定义6.30 设,例6.30,例6.31,定义6.31 设,定义6.32 设,定义6.33 如果一个格是有补分配格,则称它为布尔格或布尔代数。,