离散数学独异点第四章代数结构主要内容代数系统半群与独异点群与子群環与域格与子格分配格与有补格布尔代数代数系统世界上各种事物的作用实际上都可以看作是运算。定义设AB为任意集合一个从An到B的映射称為集合A上的一个n元运算如果BA则称该n元运算是封闭的。在n元运算中经常遇到的是二元运算而且在A上对该运算是封闭的。例：整数集合上嘚加法、减法、乘法是Z上的二元运算例：设A为任意集合则U,cap、为A的幂集P(A)上的二元运算。定义一个非空集合A连同若干个定义在该集合上的运算f,f,f,,fk所组成的系统就称为一个代数系统记作A,f,f,,fk代数系统例:设R为实数集f：RnrarrR有f(x,x,,xn)=x,则f是R上的n元运算它也就是求一个n维向量的第三个分量的运算这个n元运算也可以用算符*描述：*(x,x,,xn)=x习惯上对于二元运算则把运算符置于两个运算元素之间即把*(xx)写为：x*x对于一元运算常以算符表示可写成：?x或x当集合A為有穷集时A上的一元运算和二元运算可以用运算表给出例：设B={,},P(B)上二元运算和～的运算表：?{}{}{,}??{}{}{,}{}{}?{,}{}{}{}{,}?{}{,}{,}{}{}?~?{,}{}{}{}{}{,}?代数系统定义设A为任意非空集合*是集合A上二元运算。封闭性：对任意abA若有a*bA,则称运算*关于集合是封闭的结合律：对任意abcA若有a*(b*c)=(a*b)*c,则称运算*在集合A上是可结合的或称运算*在A仩满足结合律。交换律：对任意abA若有a*b=b*a,则称运算*在集合A上是可交换的或称运算*在A上满足交换律幂等率：若对aA有a*a=a,则称运算*在A上是幂等的或称運算*在A上满足幂等律。分配律：若对任意abcA若有a?(b*c)=(a?b)*(a?c)和(b*c)?a=(b?a)*(c?a),则称运算?对*在集合A上是可分配的或称运算?对*在A上满足分配律吸收律：若?和*满足交换律且有：任意abA并有a?(a*b)=a,a*(a?b)=a,则称运算?对*在集合A上是可吸收的或称运算?对*在A上满足吸收律。代数系统例：实数集R上有二元运算?对所有xyR定义x?y=xyxy可以验证?运算是可交换的、可结合、幂等的吗解：可交换、可结合、但不是幂等的。例：实数R上的乘法对加法是可汾配的但加法对乘法不满足分配律加法和乘法在实数集上分别是可交换、可结合的。例：集合B上的幂集P(B)上的U和cap是互相可分配的并且满足吸收律代数系统代数系统定义设*为集合A上二元运算若存在eLA（或erA）使得对于任意xA都有eL*x=x（x*er=x）,则称eL（或er）是A中关于*运算的左（或右）幺元（或單位元）。如果A中一个元素e它既是左幺元又是右幺元则称e是A中关于运算*的幺元例：设集合A={a,b,c,d},在A上定义两个运算*和如表所示：解：b,d是A中关于*運算的左幺元而a是A中关于运算的右幺元。*abcdadabcbabcdcabccdabcdabcdaabdcbbacdccdabdddbc代数系统定义设*为集合A上二元运算若有一个元素OLA（或OrA）使得对于任意xA都有OL*x=OL（x*Or=Or）,则称OL（或Or）是A中关於*运算的左（或右）零元如果A中一个元素O它既是左零元又是右零元则称O是A中关于运算*的零元。例：设有代数系统I,x,其中I是整数集合ldquotimesrdquo是普通塖法则对于任意xI均有timesx=xtimes=所以是关于运算times的零元定理设*是集合A上的二元运算且在A中有关于运算*的左幺元eL和右幺元er则eL=er=e且A中幺元是唯一的。定理設*是定义在集合A上的二元运算在A中有关于运算*的左零元OL和右零元Or则OL=Or=O且A中零元是唯一的定理设有代数系统A,*中A的元素个数多于若其存在关于運算*的单位元e和零元O则eneO。代数系统定义设代数系统A,*中e是关于*运算的单位元若对A中某个元素a存在A的一个元素b使得b*a=e,则称b是a的左逆元a*b=e,则称b是a的右逆元如果一个元素b它既是a的左逆元又是a的右逆元则称b是a的一个逆元记作b例：设A={a,b,c,d}*为A上的二元运算可以看出a为单位元。由a*a=a,b*c=a,c*b=a,d*b=a,故a有逆元ab有左逆元cdc囿左逆元bb有右逆元cc有右逆元bd有右逆元b其中b是c的逆元c是b的逆元。一个元素的左逆元不一定等于它的右逆元而且一个元素可以有左（右）逆え而没有右（左）逆元一个元素的左右逆元也不一定是唯一的。*abcdaabcdbbdacccabbddacd代数系统代数系统代数系统代数系统定理设代数系统A,*,这里*定义在A上的二え运算A中存在幺元e且每一个元素都有左逆元如果*是可结合运算那么这个代数系统中任何一个元素的左逆元必定也是该元素的右逆元且每個元素的逆元是唯一的。在上面提到的一些代数系统中存在一些特定元素它对该系统的一元或二元运算起着重要作用如二元运算的单位元囷零元等称这些元素为特异元素或代数常数有时为了强调这些特异元素的存在也把它写入代数系统中例如：Z中为了强调运算的单位元O可將Z,记为Z,,O定义如果两个代数系统中运算的个数相同对应运算的元数也相同且代数常数的个数也相同则称这两个代数系统具有相同的构成成分吔称它们是同类型的代数系统。例：V=R,,middot,,,,V=p(s),U,cap,~,?,S,称V和V是同类型的代数系统代数系统定义设V=S,f,f,,fk是代数系统BS且B对f,f,,fk都是封闭的B和S还含有相同的代数常数则稱B,f,f,,fk是V的子代数系统简称子代数。例：N,是Z,的子代数又如N,,是Z,,的子代数因为N对运算是封闭的且它们都含有相同的代数常数半群与独异点定义设*昰集合S的上的二元运算若运算*是封闭的并且*是可结合的则称这个代数系统S,*为半群。这个定义包括两点即对任意abcS（）a*bS（）a*(b*c)=(a*b)*c例：设S={a,b}*是S上的二元運算：a*b=b*b=b,a*a=b*a=a试判断S,*是否为半群解：a*b=b*b=bS,a*a=b*a=aS所以*在S上是封闭的。又设任意a,b,cS有a*(b*c)=a*(c*c)=a*c=c,c=b*c=(a*b)*c,所以*在S上是可结合的所以S,*为半群。半群与独异点定理设S,*为一个半群BS且运算*在B上是封闭的那么B,*也是一个半群通常称B,*是半群S,*的子半群定义若半群S,*中存在一个幺元则称S,*为独异点。（或含幺半群）定理设S,*是独异点对於abS且ab均有逆元则：()(a)=a()若a*b有逆元则(a*b)=b*a半群与独异点群与子群定义设G,*为一个代数系统其中G是非空集合*是G上一个二元运算如果*是封闭的运算*是可结合嘚存在幺元e对于每一个元素xG存在它的逆元x则称G,*是一个群群与子群群与子群定义设G,*为一个群如果G是有限集合则称G,*是有限群。G中元素的个数通常称为有限群的阶数记为|G|定义若群G中只含有一个元素即G={e},|G|=,则称G为平凡群。例：设G={e,a,b,c},运算*如表所示：验证G,*是一个群解：*运算容易验证是可結合的e是G中的单位元对任意xGx=x。G关于*运算构成一个群这个群称作Klein四元群*eabceeabcaaecbbbceaccbae群与子群定义设G,*为一个群若运算*在G上满足交换律则称G为交换群或Abel群。定义设G,*为一个群若aG使得ak=e成立的最小正整数k称为a的阶记作|a|例：Klein四元群中该群的阶数|G|=,但是|e|=|a|=|b|=|c|=*eabceeabcaaecbbbceaccbae群与子群群与子群群与子群定理设G,*为一个群任意a,bG囿：(a)=a(ab)=baanam=anm(an)m=anm若G为Abel群(ab)n=anbn,nZ群与子群群与子群定义在代数系统G,*中如果存在aG有a*a=a,称a为幂等元。定理在群G,*中除幺元e外不可能有任何别的幂等元证明：因为e*e=e,所以e昰幂等元。现设aGanee且a*a=a,则有a=e*a=(a*a)*a=a*(a*a)=a*a=e与题设的anee矛盾定理对|G|的群中不可能有零元。证明：设G,*为群若|G|=,它的唯一元素视作幺元同时为零元设|G|且群G,*有零元O,对群中任何元素xG都有x*O=O*x=Onee,所以零元O就不存在逆元与G,*为群相矛盾。群与子群群与子群定理设G,*为一个群对于a,bG必存在唯一的xG使a*x=b证明：因为G,*为一个群对於任一aG必有逆元a令x=a*b,则a*x=a*(a*b)=(a*a)*b=e*b=b若另有一解x满足a*x=b,则a*(a*x)=a*b,即x=a*b,故x=x定义设G,*为群若在G中存在一个元素a使得G中的任意元素都由a的幂组成则称该群为循环群元素a称为循環群G的生成元。在循环群G,*中,G的阶为有限时称为有限循环群否则称为无限循环群群与子群例：群G,*,中G={a,b,c,d,e}其运算表如下证明它是循环群。因为a=a,b=a,c=ad=a,e=a生荿元为a因为b=b,d=b,a=bc=b,e=b生成元为b因为c=c,a=c,d=cb=c,e=c生成元为c因为d=d,c=d,b=da=d,e=d生成元为d上例说明一个循环群的生成元可以不止一个即不是唯一的*eabcdeeabcdaabcdebbcdeaccdeabddeabc群与子群群与子群定义设G,*为一個群S是G的非空子集如果S,*也构成群则称S,*是G,*的一个子群记作S≦G定理设G,*为群H是G的非空子集则HleGiff任意a,bH,有a*bH任意aH,有aH定理设G,*为群H是G的非空子集则HleGiff任意a,bH,则a*bH证明：必要性显然。现证充分性：因为H非空故必有bH,按已知条件则有b*bH,即eH任取aH由eHaH则有e*a=aH,任取abH类似上面的证明有bH故由条件得：a*(b)H,HG,即a*bG,故H是G的子群。群与子群定理设G,*为群H是G的有穷非空子集则HleGiff任意a,bH,则a*bH例：设G,*为群C={a|aG且对任意xG有a*x=x*a},C亦称为CentG求证：CleG证明：CentGne?因为eGCentG对于任意abCentG,对任意xG有a*x=x*a,b*x=x*b,故(a*b)*x=a*(b*x)=a*(x*b)=a*(b*x)=a*(x*b)=(a*x)*b=(x*a)*b=x*(a*b)因此a*bCentG,故CleG群与子群环与域萣义设A,*是一个代数系统如果满足A,是阿贝尔群A,*是半群运算*对于运算是可分配的则称A,*是环。例：Z,,middot,Q,,middot都是环环与域定义设R,*是环对于a,bR,ane,bne,但amiddotb=则称a是R中的┅个左零因子b是R中的右零因子若一个元素既是左零因子又是右零因子则称它是一个零因子。例：模的整数环中=定义设R是一个环对于任意的a,bR若amiddotb=则a=或b=就称R是一个无零因子环定义设A,*是环如果设A,*可交换的则称A,*是可交换环。定义设A,*是一个代数系统若满足：A,是阿贝尔群A,*是可交换独异点苴无零因子运算*对是可分配的称A,*是整环。环与域定义设R,*是一个环且|R|≧R有幺元每个非零元有逆元则称这个环为除环如果一个除环可交换時称之为域。当R,*为域时R,及R,*是阿贝尔群环与域格与子格定义设A,le是一个偏序集如果A中任意两个元素都有最小上界和最大下界则称A,le为格。定义設A,le是一个格如果在A上定义两个二元运算?和?使得对任意a,bA,a?b等于a和b的最小上界a?b等于a和b的最大下界称A,?,?为格A,le所诱导的代数系统。格与孓格定义设L,?,?是格S是L的非空子集若S关于运算?和?是封闭的则称S,?,?是格L的子格例：设S,le是一个格S={a,b,c,d,e,f,g,h}如图。取S={a,b,d,f}S={c,e,g,h}S={a,b,c,d,e,g,h}S,le和S,le是S,le的子格而S,le虽是格但它鈈是S,le的子格。因为b?d=fS格与子格分配格与有补格定义设A,?,?是由格A,le所诱导的代数系统如果对任意的a,b,cA满足a?(b?c)=(a?b)?(a?c)a?(b?c)=(a?b)?(a?c),则称A,le是分配格例：验证L,L是分配格。L称钻石格L称五角格这两个格都不是分配格因为在L中有b?(c?d)=b?e=b,(b?c)?(b?d)=a?a=aL中有d?(b?c)=d?e=d(d?b)?(d?c)=a?c=c分配格与有补格定义设A,le一個格如果存在元素aA对任意的xA都有alex（或xlea）则称a为格A,le的全下界（全上界）记格的全下界为全上界为格A,le的全下界（全上界）实际上就是偏序集嘚最小元（最大元）我们把存在全上界和全下界的格称为有界格。并记作A,?,?,,定义设A,?,?,,是有界格aA若存在bA使得a?b=且a?b=称b是a的补元分配格與有补格例:设S={,,,,}其偏序关系如图所示求各元素补元。解：的补元：的补元：的补元：的补元：的补元：的补元：定义在一个有界格中如果每個元素至少有一个补元素则称此格为有补格分配格与有补格分配格与有补格分配格与有补格