离散数学代数结构部分.pptx

《离散数学代数结构部分.pptx》由会员分享，可在线阅读，更多相关《离散数学代数结构部分.pptx（126页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章 代数系统代数系统代数结构又称为代数系统，简称代数，是抽象代数的主要研究对象。代数系统的种类很多，它们在计算机科学的自动机理论、编码理论、形式语言、时序线路、开关线路计数问题以及计算机网络纠错码的纠错能力判断、密码学、计算机理论科学等方面有着非常广泛的应用。第1页/共126页本部分主要内容二元运算及其性质。二元运算中的特殊元素幺元，零元，逆元。代数系统的定义及其性质。第2页/共126页定义5.1 设 为集合，函数 称为 上的二元运算，简称为二元运算。5.15.1节节二元运算及其性质二元运算及其性质在整数集合上，对任意两个整数所进行的普通加法和乘法，都是集合上的二元运算。第3页/共1

2、26页如何判断一个运算是否为集合 上的二元运算 1唯一性集合S中任意的两个元素都能进行这种运算，并且结果要是唯一的。2封闭性集合S中任意的两个元素运算的结果都是属于S的，就是说S对该运算是封闭的第4页/共126页例5.1设Ax|x ，nN，问在集合A上通常的乘法运算是否封闭，对加法运算呢?解：对于任意的 所以乘法运算是封闭的。而对于加法运算是不封闭的,因为至少有 第5页/共126页定义5.2 设*是定义在集合A上的二元运算，如果对于任意的x,yA，都有x*yy*x，则称该二元运算*是可交换的。例5.2设Q是有理数集合，*是Q上的二元运算，对任意的a，b Q，a*ba+b-ab，问运算*是否可交

3、换。解：因为a*ba+b-abb+a-bab*a，所以运算*是可交换的。第6页/共126页定义5.1 设 为集合，函数 称为 上的二元运算，简称为二元运算。5.15.1节节二元运算及其性质二元运算及其性质在整数集合上，对任意两个整数所进行的普通加法和乘法，都是集合上的二元运算。第7页/共126页定义5.2 设*是定义在集合A上的二元运算，如果对于任意的x,yA，都有x*yy*x，则称该二元运算*是可交换的。例5.2设Q是有理数集合，*是Q上的二元运算，对任意的a，b Q，a*ba+b-ab，问运算*是否可交换。解：因为a*ba+b-abb+a-bab*a，所以运算*是可交换的。第8页/共126

4、页定义5.3 设*是定义在集合A上的二元运算，如果对于任意的x，y，zA，都有(x*y)*zx*(y*z)，则称该二元运算*是可结合的，或者说运算*在A上适合结合律。例5.3设A=Z,“+”是整数中的加法：则“+”在Z中适合结合律。“。”是整数中的减法：则特取而运算“。”不满足结合律第9页/共126页定义5.4 设*是定义在集合A上的一个二元运算，如果对于任意的xA，都有x*xx，则称运算*是等幂的。例5.4设P(S)是集合S的幂集，在P(S)上定义的两个二元运算，集合的“并”运算和集合的“交”运算，验证，是等幂的。解：对于任意的A P(S)，有A AA和AAA，因此运算和都满足等幂律。第10

5、页/共126页定义5.5 设。和*是S上的两个二元运算，如果对任意的 有 例5.5在实数集R上，对于普通的乘法和加法有即乘法对加法是可分配的。第11页/共126页定义5.6 设。和*是定义在集合A上的两个可交换二元运算，如果对于任意的x，yA，都有则称。运算和*满足吸收律例5.6设集合N为自然数全体，在N上定义两个二元运算*和，对于任意x，y N，有x*ymax(x，y)，xymin(x，y)，验证运算*和满足吸收律。第12页/共126页解：对于任意a，b Na*(ab)max(a，min(a，b)aa(a*b)min(a，max(a，b)a因此，*和满足吸收律。第13页/共126页定义5.7

6、 设*是S上的二元运算，5.25.2节 二元运算中的特殊元素1.1.幺元第14页/共126页在自然数集N上加法的幺元是0，乘法的幺元是1.对于给定的集合和运算有的存在幺元，有的不存在幺元。第15页/共126页第16页/共126页定理5.1 设*是S上的二元运算，如果S中存在关于运算*的）幺元，则必是唯一的。所以幺元是唯一的。第17页/共126页定理5.2 5.2 设*是S S上的二元运算，如果S S中既存在关于运算*的左幺元 ，又存在关于运算的右幺元 则S中必存在关于运算*的幺元e并且 第18页/共126页定义5.8 设*是S上的二元运算，2.2.零元第19页/共126页在自然数集N上普通乘法

7、的零元是0，而加法没有零元。第20页/共126页定理5.3 设*是S上的二元运算，如果S中存在（关于运算*的）零元，则必是唯一的。所以零元是唯一的。第21页/共126页定理5.4 设*是S上的二元运算，如果S中既存在关于运算*的左零元 又存在关于运算*的右零元 第22页/共126页定义5.9 设*是S上的二元运算，2.2.逆元第23页/共126页例5.8整数集Z上关于加法的幺元是0，对任意的整数m，它关于加法的逆元是-m,因为第24页/共126页定理5.5 设*是S上可结合的二元运算，e为幺元,如果S中元素x存在（关于运算*）的逆元，则必是惟一的。所以对于可结合的二元运算，逆元是惟一的。第25

8、页/共126页定理5.6 设*是S上可结合的二元运算，e为幺元,如果S中元素x既存在关于运算*的左逆元 ，又存在关于运算*的右逆元 ，则 S中必存在x关于运算*的逆元并且 第26页/共126页解：*运算适合交换律、结合律和消去律，不适合幂等律。单位元是a，没有零元，且运算适合交换律、结合律和幂等律，不适合消去律。单位元是a，零元是b.只有a有逆元，运算不适合交换律，适合结合律和幂等律，不适合消去律。没有单位元，没有零元，没有可逆元素。第27页/共126页定义5.10 设S是非空集合，由S和S上若干个运算 构成的系统称为代数系统，记作 5.35.3节 代数系统 代数系统也简称为代数。例如，R是实

9、数集，对于普通的加法和剩法运算，M是n阶方阵构成的集合，对于矩阵的加法和剩法运算，第28页/共126页定义5.11 设 都是封闭的，且B和S含有相同的代数常数，则称第29页/共126页定义5.12 设 第30页/共126页例5.11设第31页/共126页定义5.13 设定义5.14设第32页/共126页第33页/共126页例5.14表示求两个数的最小公倍数的运算。则解：零元是不存在的，只有惟一的逆元。第34页/共126页例5.15在有理数集Q上定义二元运算*解：第35页/共126页第36页/共126页例5.16设有集合解：讨论这5个集合对普通的乘法和加法运算是否封闭。第37页/共126页例5.

10、17设解：第38页/共126页第六章第六章 几个典型的代数系统几个典型的代数系统本章讨论几类重要的代数结构：半群、群、环、域、格与布尔代数第39页/共126页定义6.1 设 6.16.1节 半群与群是可结合的即：第40页/共126页定义6.2若半群 例6.1（1）普通加法是（2）普通乘法是N,Z,Q和R上的二元运算，满足结合律且有幺元1第41页/共126页第42页/共126页定义6.3 设例6.2定义6.3设第43页/共126页定义6.4 设定义6.5设第44页/共126页例6.3设证明G关于矩阵乘法构成一个群故G关于矩阵乘法是Z上的代数运算，矩阵乘法满足结合律，故G关于矩阵乘法构成半群，在G

11、中每个矩阵的逆元都是自己，所以G关于矩阵乘法构成一个群。第45页/共126页定义6.6 若群例6.4（1）在中除0之外都没有逆元，所以它仅是含幺半群而不是群。中每个元素都有逆元即它的相反数，且运算满足交换律，所以它们是交换群。0没有逆元，所以它们仅是有么半群而不是群。第46页/共126页第47页/共126页例6.5设G=e,a,b,c,。为G上的二元运算，它由以下运算表给出。不难证明G是一个群，称该群为Klein四元群。第48页/共126页定义6.7 设第49页/共126页例6.6在群解：第50页/共126页定理6.1 设 证明：略。第51页/共126页定义6.8 设第52页/共126页定义6

12、.9第53页/共126页例6.7对于集合列出其运算表如下表从表中可以看出，运算满足封闭性，满足结合律和交换律，0是单位元，每个元都有逆元，这个群的阶数是6，元素0，1，2，3，4，5的次数分别为1，6，3，2，3，6。第54页/共126页定理6.2设下面证明唯一性从而唯一性得证。第55页/共126页例6.8设第56页/共126页定理6.3 第57页/共126页定理6.4 设 第58页/共126页第59页/共126页定理6.5 G为有限群，则G的运算表中的每一行（每一列）都是G中元素的一个置换，且不同的行（或列）的置换都不相同。定义6.10设第60页/共126页例6.9例6.10群第61页/共1

13、26页定理6.6(子群判定定理1)设H是群。证明：必要性是显然的。第62页/共126页定理6.7(子群判定定理2)设H是群 证明：必要性充分性证明：第63页/共126页定理6.8(子群判定定理3)设H是群 证明：必要性是显然的。第64页/共126页例6.11设第65页/共126页定义6.11 设 6.26.2节 陪集与拉格朗日定理例6.12设解：H的右陪集为第66页/共126页定理6.9 设H是群 第67页/共126页定理6.10 设第68页/共126页第69页/共126页定理6.11 设证明：略。推论6.1第70页/共126页定理6.12 设第71页/共126页定理6.13 设第72页/共1

14、26页定义6.12 群 定理6.14（拉格朗日定理）设即子群的阶数一定是群的阶数的因子。根据定理6.11的推论有第73页/共126页推论6.2 设 推论6.3设根据定理6.11的推论有第74页/共126页定义6.13 设 任何群G都有正规子群，因为G的两个平凡子群第75页/共126页定理6.15 设 证明：略。第76页/共126页例6.13设第77页/共126页例6.14设第78页/共126页定理6.16 设 第79页/共126页定义6.14 设6.3 6.3 群的同态与同构群的同态与同构 第80页/共126页例6.13设第81页/共126页定义6.15 设第82页/共126页定理6.17 设

15、 证明：略。第83页/共126页定义6.16 设第84页/共126页定理6.18 （群同态基本定理）设 第85页/共126页定义6.17 设6.4 6.4 循环群与置换群循环群与置换群第86页/共126页第87页/共126页定理6.19 设 第88页/共126页例6.16例6.17设第89页/共126页定义6.18 设 例6.18设第90页/共126页第91页/共126页定义6.19 设 例6.194元置换第92页/共126页定义6.20设 第93页/共126页定理6.20第94页/共126页定义6.21例6.20如图进行旋转，也可以围绕它的对称轴进行翻转，但经过旋转或翻转后仍要与原来的方格重

16、合（方格中的数字可以改变）。如果把每种旋转或翻转看作是作用在第95页/共126页第96页/共126页第97页/共126页第98页/共126页定义6.22 设 6.5 6.5 环和域环和域第99页/共126页例6.21（1）整数集 第100页/共126页定理6.21 设 2,3证明略。第101页/共126页例6.22 第102页/共126页定义6.23 设 第103页/共126页例6.23（1）整数环 第104页/共126页例6.22模6整数环 第105页/共126页定义6.24 设 第106页/共126页定义6.22 设 6.5 6.5 环和域环和域第107页/共126页例6.25 设 第10

17、8页/共126页第109页/共126页第110页/共126页定义6.25 设 6.6 6.6 格与布尔代数格与布尔代数 第111页/共126页例6.26 设n是正整数 第112页/共126页例6.27（1）对于偏序集 第113页/共126页第114页/共126页定理6.22设 第115页/共126页定理6.23 设 第116页/共126页定义6.26 设 定义6.27设第117页/共126页例6.28 设格 第118页/共126页定义6.28 设 第119页/共126页例6.29 说明下图中的格是否为分配格，为什么？第120页/共126页第121页/共126页定义6.29 设 第122页/共126页定义6.30 设 例6.30例6.31第123页/共126页定义6.31 设 第124页/共126页定义6.32 设 定义6.33如果一个格是有补分配格，则称它为布尔格或布尔代数。第125页/共126页感谢您的观看！第126页/共126页