离散数学代数结构部分（课堂PPT）

第三部分代数结构,1,第五章代数系统,代数结构又称为代数系统，简称代数，是抽象代数的主要研究对象。代数系统的种类很多，它们在计算机科学的自动机理论、编码理论、形式语言、时序线路、开关线路计数问题以及计算机网络纠错码的纠错能力判断、密码学、计算机理论科学等方面有着非常广泛的应用。,2,本部分主要内容二元运算及其性质。二元运算中的特殊元素幺元，零元，逆元。代数系统的定义及其性质。,3,定义5.1设为集合，函数称为上的二元运算，简称为二元运算。,5.1节二元运算及其性质,在整数集合上，对任意两个整数所进行的普通加法和乘法，都是集合上的二元运算。,4,如何判断一个运算是否为集合上的二元运算,唯一性集合S中任意的两个元素都能进行这种运算，并且结果要是唯一的。,封闭性集合S中任意的两个元素运算的结果都是属于S的，就是说S对该运算是封闭的,5,例5.1设Ax|x，nN，问在集合A上通常的乘法运算是否封闭，对加法运算呢?,解：对于任意的所以乘法运算是封闭的。而对于加法运算是不封闭的,因为至少有,6,定义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，所以运算*是可交换的。,7,定义5.1设为集合，函数称为上的二元运算，简称为二元运算。,5.1节二元运算及其性质,在整数集合上，对任意两个整数所进行的普通加法和乘法，都是集合上的二元运算。,8,定义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，所以运算*是可交换的。,9,定义5.3设*是定义在集合A上的二元运算，如果对于任意的x，y，zA，都有(x*y)*zx*(y*z)，则称该二元运算*是可结合的，或者说运算*在A上适合结合律。,例5.3设A=Z,“+”是整数中的加法：则,“+”在Z中适合结合律。,“。”是整数中的减法：则特取,而,运算“。”不满足结合律,10,定义5.4设*是定义在集合A上的一个二元运算，如果对于任意的xA，都有x*xx，则称运算*是等幂的。,例5.4设P(S)是集合S的幂集，在P(S)上定义的两个二元运算，集合的“并”运算和集合的“交”运算，验证，是等幂的。,解：对于任意的AP(S)，有AAA和AAA，因此运算和都满足等幂律。,11,定义5.5设。和*是S上的两个二元运算，如果对任意的有,例5.5在实数集R上，,对于普通的乘法和加法有,即乘法对加法是可分配的。,12,定义5.6设。和*是定义在集合A上的两个可交换二元运算，如果对于任意的x，yA，都有,则称。运算和*满足吸收律,例5.6设集合N为自然数全体，在N上定义两个二元运算*和，对于任意x，yN，有x*ymax(x，y)，xymin(x，y)，验证运算*和满足吸收律。,13,解：对于任意a，bN,a*(ab)max(a，min(a，b)aa(a*b)min(a，max(a，b)a因此，*和满足吸收律。,14,定义5.7设*是S上的二元运算，,5.2节二元运算中的特殊元素,1.幺元,15,在自然数集N上加法的幺元是0，乘法的幺元是1.,对于给定的集合和运算有的存在幺元，有的不存在幺元。,16,17,定理5.1设*是S上的二元运算，如果S中存在关于运算*的）幺元，则必是唯一的。,所以幺元是唯一的。,18,定理5.2设*是S上的二元运算，如果S中既存在关于运算*的左幺元，又存在关于运算的右幺元则S中必存在关于运算*的幺元e并且,19,定义5.8设*是S上的二元运算，,2.零元,20,在自然数集N上普通乘法的零元是0，而加法没有零元。,21,定理5.3设*是S上的二元运算，如果S中存在（关于运算*的）零元，则必是唯一的。,所以零元是唯一的。,22,定理5.4设*是S上的二元运算，如果S中既存在关于运算*的左零元又存在关于运算*的右零元,23,定义5.9设*是S上的二元运算，,2.逆元,24,例5.8整数集Z上关于加法的幺元是0，对任意的整数m，它关于加法的逆元是-m,因为,25,定理5.5设*是S上可结合的二元运算，e为幺元,如果S中元素x存在（关于运算*）的逆元，,则必是惟一的。,所以对于可结合的二元运算，逆元是惟一的。,26,定理5.6设*是S上可结合的二元运算，e为幺元,如果S中元素x既存在关于运算*的左逆元，又存在关于运算*的右逆元，则S中必存在x关于运算*的逆元并且,27,解：*运算适合交换律、结合律和消去律，不适合幂等律。单位元是a，没有零元，且,运算适合交换律、结合律和幂等律，不适合消去律。单位元是a，零元是b.只有a有逆元，,运算不适合交换律，适合结合律和幂等律，不适合消去律。没有单位元，没有零元，没有可逆元素。,28,定义5.10设S是非空集合，由S和S上若干个运算构成的系统称为代数系统，记作,5.3节代数系统,代数系统也简称为代数。,例如，R是实数集，对于普通的加法和剩法运算，,M是n阶方阵构成的集合，对于矩阵的加法和剩法运算，,29,定义5.11设,都是封闭的，且B和S含有相同的代数常数，则称,30,定义5.12设,31,例5.11设,32,定义5.13设,定义5.14设,33,34,例5.14表示求两个数的最小公倍数的运算。则,解：零元是不存在的，只有惟一的逆元。,35,例5.15在有理数集Q上定义二元运算*,解：,36,37,例5.16设有集合,解：,讨论这5个集合对普通的乘法和加法运算是否封闭。,38,例5.17设,解：,39,第六章几个典型的代数系统,本章讨论几类重要的代数结构：半群、群、环、域、格与布尔代数,40,定义6.1设,6.1节半群与群,是可结合的即：,41,定义6.2若半群,例6.1（1）普通加法是,（2）普通乘法是N,Z,Q和R上的二元运算，满足结合律且有幺元1,42,43,定义6.3设,例6.2,定义6.3设,44,定义6.4设,定义6.5设,45,例6.3设,证明G关于矩阵乘法构成一个群,故G关于矩阵乘法是Z上的代数运算，矩阵乘法满足结合律，故G关于矩阵乘法构成半群，,在G中每个矩阵的逆元都是自己，所以G关于矩阵乘法构成一个群。,46,定义6.6若群,例6.4（1）在中除0之外都没有逆元，所以它仅是含幺半群而不是群。,中每个元素都有逆元即它的相反数，且运算满足交换律，所以它们是交换群。,0没有逆元，所以它们仅是有么半群而不是群。,47,48,例6.5设G=e,a,b,c,。为G上的二元运算，它由以下运算表给出。不难证明G是一个群，称该群为Klein四元群。,49,定义6.7设,50,例6.6在群,解：,51,定理6.1设,证明：略。,52,定义6.8设,53,定义6.9,54,例6.7对于集合,列出其运算表如下表,从表中可以看出，运算满足封闭性，满足结合律和交换律，0是单位元，每个元都有逆元，,这个群的阶数是6，元素0，1，2，3，4，5的次数分别为1，6，3，2，3，6。,55,定理6.2设,下面证明唯一性,从而唯一性得证。,56,例6.8设,57,定理6.3,58,定理6.4设,59,60,定理6.5G为有限群，则G的运算表中的每一行（每一列）都是G中元素的一个置换，且不同的行（或列）的置换都不相同。,定义6.10设,61,例6.9,例6.10群,62,定理6.6(子群判定定理1)设H是群。,证明：必要性是显然的。,63,定理6.7(子群判定定理2)设H是群,证明：必要性,充分性证明：,64,定理6.8(子群判定定理3)设H是群,证明：必要性是显然的。,65,例6.11设,66,定义6.11设,6.2节陪集与拉格朗日定理,例6.12设,解：H的右陪集为,67,定理6.9设H是群,68,定理6.10设,69,70,定理6.11设,证明：略。,推论6.1,71,定理6.12设,72,定理6.13设,73,定义6.12群,定理6.14（拉格朗日定理）设,即子群的阶数一定是群的阶数的因子。,根据定理6.11的推论有,74,推论6.2设,推论6.3设,根据定理6.11的推论有,75,定义6.13设,任何群G都有正规子群，因为G的两个平凡子群,76,定理6.15设,证明：略。,77,例6.13设,78,例6.14设,79,定理6.16设,80,定义6.14设,6.3群的同态与同构,81,例6.13设,82,定义6.15设,83,定理6.17设,证明：略。,84,定义6.16设,85,定理6.18（群同态基本定理）设,86,定义6.17设,6.4循环群与置换群,87,88,定理6.19设,89,例6.16,例6.17设,90,定义6.18设,例6.18设,91,92,定义6.19设,例6.194元置换,93,定义6.20设,94,定理6.20,95,定义6.21,例6.20如图进行旋转，也可以围绕它的对称轴进行翻转，但经过旋转或翻转后仍要与原来的方格重合（方格中的数字可以改变）。如果把每种旋转或翻转看作是作用在,96,97,98,99,定义6.22设,6.5环和域,100,例6.21（1）整数集,101,定理6.21设,2,3证明略。,102,例6.22,103,定义6.23设,104,例6.23（1）整数环,105,例6.22模6整数环,106,定义6.24设,107,定义6.22设,6.5环和域,108,例6.25设,109,110,111,定义6.25设,6.6格与布尔代数,112,例6.26设n是正整数,113,