离散数学II_考试题型及复习提纲.

1大概的考试题型选择题20填空题20计算（简答）题30证明题20综合题102第三部分代数结构主要内容代数系统:二元运算及其性质、代数系统和子代数半群与群:半群、独异点、群环与域:环、整环、域3第九章代数系统主要内容二元运算及其性质一元和二元运算定义及其实例二元运算的性质代数系统代数系统定义及其实例子代数积代数代数系统的同态与同构4基本要求判断给定集合和运算能否构成代数系统判断给定二元运算的性质求而二元运算的特异元素了解同类型和同种代数系统的概念了解子代数的基本概念计算积代数判断函数是否为同态映射和同构映射5一、二元运算及其性质定义9.1设S为集合，函数f：SSS称为S上的二元运算，简称为二元运算．S中任何两个元素都可以进行运算，且运算的结果惟一．S中任何两个元素的运算结果都属于S，即S对该运算封闭．定义9.2设S为集合，函数f:S→S称为S上的一元运算，简称一元运算.6二元运算的性质定义9.3设◦为S上的二元运算,(1)若对任意x,y∈S有x◦y=y◦x,则称运算在S上满足交换律.(2)若对任意x,y,z∈S有(x◦y)◦z=x◦(y◦z),则称运算在S上满足结合律.(3)若对任意x∈S有x◦x=x,则称运算在S上满足幂等律.定义9.4设◦和∗为S上两个不同的二元运算,(1)若对任意x,y,z∈S有(x∗y)◦z=(x◦z)∗(y◦z)，z◦(x∗y)=(z◦x)∗(z◦y),则称◦运算对∗运算满足分配律.(2)若和∗都可交换,且对任意x,y∈S有x◦(x∗y)=x，x∗(x◦y)=x,则称◦和∗运算满足吸收律.7特异元素：单位元、零元定义9.5设◦为S上的二元运算,(1)如果存在el(或er)S，使得对任意x∈S都有el◦x=x(或x◦er=x)，则称el(或er)是S中关于◦运算的左(或右)单位元.若e∈S关于◦运算既是左单位元又是右单位元，则称e为S上关于◦运算的单位元.单位元也叫做幺元.(2)如果存在l(或r)∈S，使得对任意x∈S都有l◦x=l(或x◦r=r)，则称l(或r)是S中关于◦运算的左(或右)零元.若∈S关于◦运算既是左零元又是右零元，则称为S上关于运算◦的零元.8可逆元素和逆元(3)设◦为S上的二元运算,令e为S中关于运算的单位元.对于x∈S，如果存在yl(或yr)∈S使得yl◦x=e（或x◦yr=e）则称yl(或yr)是x的左逆元（或右逆元）.关于◦运算，若y∈S既是x的左逆元又是x的右逆元，则称y为x的逆元.如果x的逆元存在，就称x是可逆的.9惟一性定理定理9.1设◦为S上的二元运算，el和er分别为S中关于运算的左和右单位元，则el=er=e为S上关于◦运算的惟一的单位元.类似地可以证明关于零元的惟一性定理.注意：当|S|2，单位元与零元是不同的；当|S|=1时，这个元素既是单位元也是零元.定理9.2设◦为S上可结合的二元运算,e为该运算的单位元,对于x∈S如果存在左逆元yl和右逆元yr,则有yl=yr=y,且y是x的惟一的逆元.109.2代数系统定义9.6非空集合S和S上k个一元或二元运算f1,f2,…,fk组成的系统称为代数系统,简称代数，记做S,f1,f2,…,fk.构成代数系统的成分：集合（也叫载体，规定了参与运算的元素）运算（这里只讨论有限个二元和一元运算）代数常数（通常是与运算相关的特异元素：如单位元等）研究代数系统时，如果把运算具有它的特异元素也作为系统的性质之一，那么这些特异元素可以作为系统的成分，叫做代数常数.11子代数系统定义9.8设V=S,f1,f2,…,fk是代数系统，B是S的非空子集，如果B对f1,f2,…,fk都是封闭的，且B和S含有相同的代数常数，则称B,f1,f2,…,fk是V的子代数系统，简称子代数.有时将子代数系统简记为B.说明：子代数和原代数是同种的代数系统对于任何代数系统V=S,f1,f2,…,fk，其子代数一定存在.12第十章群与环主要内容群的定义与性质子群与群的陪集分解循环群与置换群环与域13基本要求判断或证明给定集合和运算是否构成半群、独异点和群熟悉群的基本性质能够证明G的子集构成G的子群熟悉陪集的定义和性质熟悉拉格朗日定理及其推论，学习简单应用会求循环群的生成元及其子群熟悉n元置换的表示方法、乘法以及n元置换群能判断给定代数系统是否为环和域14半群、独异点与群的定义半群、独异点、群的实例群中的术语群的基本性质10.1群的定义与性质15半群、独异点与群的定义定义10.1(1)设V=S,∘是代数系统，∘为二元运算，如果∘运算是可结合的，则称V为半群.(2)设V=S,∘是半群，若e∈S是关于∘运算的单位元，则称V是含幺半群，也叫做独异点.有时也将独异点V记作V=S,∘,e.(3)设V=S,∘是独异点，eS关于∘运算的单位元，若aS，a1S，则称V是群.通常将群记作G.16有关群的术语定义10.2(1)若群G是有穷集，则称G是有限群，否则称为无限群.群G的基数称为群G的阶，有限群G的阶记作|G|.(2)只含单位元的群称为平凡群.(3)若群G中的二元运算是可交换的，则称G为交换群或阿贝尔(Abel)群.定义10.4设G是群，a∈G，使得等式ak=e成立的最小正整数k称为a的阶，记作|a|=k，称a为k阶元.若不存在这样的正整数k，则称a为无限阶元.17群的性质：幂运算规则定理10.1设G为群，则G中的幂运算满足：(1)a∈G，(a1)1=a(2)a,b∈G，(ab)1=b1a1(3)a∈G，anam=an+m，n,m∈Z(4)a∈G，(an)m=anm，n,m∈Z(5)若G为交换群，则(ab)n=anbn.18群的性质：消去律；元素的阶定理10.3G为群，则G中适合消去律，即对任意a,b,c∈G有(1)若ab=ac，则b=c.(2)若ba=ca，则b=c.例5设G是群，a,b∈G是有限阶元.证明(1)|b1ab|=|a|(2)|ab|=|ba|定理10.4G为群，a∈G且|a|=r.设k是整数，则(1)ak=e当且仅当r|k(2)|a1|=|a|1910.2子群与群的陪集分解定义10.5设G是群，H是G的非空子集，(1)如果H关于G中的运算构成群，则称H是G的子群,记作H≤G.(2)若H是G的子群，且HG，则称H是G的真子群，记作HG.例如nZ(n是自然数)是整数加群Z,+的子群.当n≠1时,nZ是Z的真子群.对任何群G都存在子群.G和{e}都是G的子群，称为G的平凡子群.20子群判定定理定理10.5（判定定理一）设G为群，H是G的非空子集，则H是G的子群当且仅当(1)a,b∈H有ab∈H(2)a∈H有a1∈H.定理10.6（判定定理二）设G为群，H是G的非空子集.H是G的子群当且仅当a,b∈H有ab1∈H.定理10.7（判定定理三）设G为群，H是G的非空有穷子集，则H是G的子群当且仅当a,b∈H有ab∈H.21典型子群的实例定义10.6设G为群，a∈G，令H={ak|k∈Z}，则H是G的子群，称为由a生成的子群，记作a.定义10.7设G为群,令C={a|a∈G∧x∈G(ax=xa)}，则C是G的子群，称为G的中心.例6设G是群，H,K是G的子群.证明(1)H∩K也是G的子群(2)H∪K是G的子群当且仅当HK或KH22陪集定义10.9设H是G的子群，a∈G.令Ha={ha|h∈H}称Ha是子群H在G中的右陪集.称a为Ha的代表元素.定理10.8设H是群G的子群，则(1)He=H(2)a∈G有a∈Ha定理10.9设H是群G的子群，则a,b∈G有a∈Hbab1∈HHa=Hb23推论推论设H是群G的子群,则(1)a,b∈G，Ha=Hb或Ha∩Hb=(2)∪{Ha|a∈G}=G证明：由等价类性质可得.定理10.10设H是群G的子群，在G上定义二元关系R：a,b∈G,a,b∈Rab1∈H则R是G上的等价关系，且[a]R=Ha.24左陪集的定义与性质设G是群，H是G的子群，H的左陪集，即aH={ah|h∈H}，a∈G关于左陪集有下述性质：(1)eH=H(2)a∈G，a∈aH(3)a,b∈G，a∈bHb1a∈HaH=bH(4)若在G上定义二元关系R，a,b∈G，a,b∈Rb1a∈H则R是G上的等价关系，且[a]R=aH.(5)a∈G，H≈aH25Lagrange定理定理10.12（Lagrange）设G是有限群，H是G的子群，则|G|=|H|·[G:H]其中[G:H]是H在G中的不同右陪集(或左陪集)数，称为H在G中的指数.推论1设G是n阶群，则a∈G，|a|是n的因子，且有an=e.推论2对阶为素数的群G，必存在a∈G使得G=a.26Lagrange定理的应用命题：如果群G只含1阶和2阶元，则G是Abel群.例8证明6阶群中必含有3阶元.证设a为G中任意元素，有a1=a.任取x,y∈G，则xy=(xy)1=y1x1=yx，因此G是Abel群.证设G是6阶群，则G中元素只能是1阶、2阶、3阶或6阶.若G中含有6阶元，设为a，则a2是3阶元.若G中不含6阶元，下面证明G中必含有3阶元.如若不然，G中只含1阶和2阶元，即a∈G，有a2=e，由命题知G是Abel群.取G中2阶元a和b，ab，令H={e,a,b,ab}，则H是G的子群，但|H|=4，|G|=6，与拉格朗日定理矛盾.2710.3循环群与置换群定义10.10设G是群，若存在a∈G使得G={ak|k∈Z}则称G是循环群，记作G=a，称a为G的生成元.循环群的分类：n阶循环群和无限循环群.设G=a是循环群，若a是n阶元，则G={a0=e,a1,a2,…,an1}那么|G|=n，称G为n阶循环群.若a是无限阶元，则G={a0=e,a±1,a±2,…}称G为无限循环群.28循环群的生成元定理10.13设G=a是循环群.(1)若G是无限循环群，则G只有两个生成元，即a和a1.(2)若G是n阶循环群，则G含有(n)个生成元.对于任何小于n且与n互质的数r∈{0,1,…,n-1},ar是G的生成元.(n)成为欧拉函数，例如n=12，小于或等于12且与12互素的正整数有4个：1,5,7,11，所以(12)=4.29循环群的子群定理10.14设G=a是循环群.(1)设G=a是循环群，则G的子群仍是循环群.(2)若G=a是无限循环群，则G的子群除{e}以外都是无限循环群.(3)若G=a是n阶循环群，则对n的每个正因子d，G恰好含有一个d阶子群.3010.4环与域定义10.12设R,+,·是代数系统，+和·是二元运算.如果满足以下条件:(1)R,+构成交换群(2)R,·构成半群(3)·运算关于+运算适合分配律则称R,+,·是一个环.通常称+运算为环中的加法，·运算为环中的乘法.环中加法单位元记作0，乘法单位元（如果存在）记作1.对任何元素x，称x的加法逆元为负元，记作x.若x存在乘法逆元的话，则称之为逆元，记作x1.31定理10.16设R,+,·是环，则(1)a∈R，a0=0a=0(2)a,b∈R，(a)b=a(b)=ab(3)a,b,c∈R，a(bc)=abac，(bc)a=baca(4)a1,a2,...,an,b1,b2,...,bm∈R(n,m≥2)babajnimjimjjnii1111)()(环的运算性质32特殊的环定义10.13设R,+,·是环(1)若环中乘法·适合交换律，则称R是交换环(2)若环中乘法·存在单位元，则称R是含幺环(3)若a,b∈R，ab=0a=0∨b=0，则称R是无零因子环(4)若R既是交换环、含幺环、无零因子环，则称R是整环(5)设R是整环，且R中至少含有两个元素.若a∈R*，其中R*=R{0}，都有a－1∈R，则