离散数学第5章.

1第3篇代数系统（AlgebraicSystem）2第5章代数结构（algebraicstructure）§1代数系统的引入§2运算及其性质§3半群§4群与子群§5阿贝尔群和循环群§6陪集与拉格朗日定理§7同态与同构§8环和域3§1代数系统的引入定义：如果为An到B的一个函数，则称为集合A上的n元运算（operater）。如果BA，则称该n元运算在A上封闭。4§1代数系统的引入本章主要讨论一元运算和二元运算。例：（1）在整数I和实数R中,+,-,×均为二元运算。（2）在集合Z的幂集(z)中,,均为二元运算,而“~”是一元运算；5§1代数系统的引入（3）{命题公式}中,∨,∧均为二元运算,而“”为一元运算（4）{双射函数}中,函数的合成运算是二元运算；二元运算常用符号：+,,,,,,,等等。6§1代数系统的引入定义:一个非空集合A连同若干个定义在该集合上的运算f1,f2,….,fk所组成的系统就称为一个代数系统，记作A,f1,f2,….,fk。7§2运算及其性质定义:设*是集合S上的二元运算,对任一x,yS有xy∈S则称运算在S上是封闭的。8§1代数系统的引入例：（1）在正整偶数的集合E中,对×,+运算是封闭的；在正整奇数的集合中,对×运算是封闭的,而对+运算不是封闭的。（2）在前例中,R,I集合中+,-,×运算；(z)的元素中,,~,运算等均为封闭的。9§2运算及其性质例题:设A={x|x=2n,nN},问乘法运算是否封闭？对加法运算呢？解对于任意的2r,2sA，r，sN，因为2r·2s=2r+sA,所以乘法运算是封闭。对于加法运算是不封闭的，因为至少有2+22=6A10§2运算及其性质定义:设*是集合S上的二元运算,对任一x,yS有xy=yx,则称运算在S上是可交换的（commutative）或者说在S上满足交换律。11§2运算及其性质例题:设Q是有理数集合，Δ是Q上的二元运算，对任意的a,bR，aΔb=a+b-a·b，问运算Δ是否可交换。解因为aΔb=a+b-a·b=b+a-b·a=bΔa所以运算Δ是可交换的。12§2运算及其性质定义:设*是集合S上的二元运算,对任一x,y,zS都有（xy）z=x（yz）,则称运算在S上是可结合的（associative）或者说*在S上满足结合律。13§2运算及其性质例题:设A是一个非空集合，★是A上的二元运算，对于任意a,bA,有a★b=b，证明★是可结合运算。证明因为对于任意的a,b,cA(a★b)★c=b★c=c而a★(b★c)=a★c=c所以(a★b)★c=a★(b★c)14§2运算及其性质定义:设和是集合S上的二个二元运算,对任一x,y,zS有x（yz）=（xy）（xz）；（yz）x=（yx）（zx）,则称运算对是可分配的（distributive）或称对满足分配律。15§2运算及其性质例题：设集合A＝｛α，β｝，定义A上的二元运算，，运算表如下：问：对可分配吗？αβααβββααβαααβαβ16从*和△的运算表中可以看出*和△两种运算都是可交换的。故只须验证α△(α*α)=(α△α)*(α△α)α△(α*β)=(α△α)*(α△β)α△(β*β)=(α△β)*(α△β)β△(α*α)=(β△α)*(β△α)β△(α*β)=(β△α)*(β△β)β△(β*β)=(β△β)*(β△β)α△(α*α)=α△α=α(α△α)*(α△α)=α*α=αα△(α*β)=α△β=α(α△α)*(α△β)=α*α=αα△(β*β)=α△α=α(α△β)*(α△β)=α*α=αβ△(α*α)=β△α=α(β△α)*(β△α)=α*α=αβ△(α*β)=β△β=β(β△α)*(β△β)=α*β=ββ△(β*β)=β△α=α(β△β)*(β△β)=β*β=α验证运算△对于运算*是可分配的。17β*(α△β)≠(β*α)△(β*β)β*(α△β)＝β(β*α)△(β*β)＝α运算*对于运算△是不可分配的。18§2运算及其性质定义:设，是定义在集合S上的两个可交换二元运算，如果对于任意的x,yS，都有：x(xy)=x；x(xy)=x则称运算和运算满足吸收律（assimilate）。19§2运算及其性质例题：设集合N为自然数全体，在N上定义两个二元运算*和★，对于任意x,yN，有x*y=max(x,y)x★y=min(x,y)验证运算*和★的吸收律。20§2运算及其性质解对于任意a,bNa*(a★b)=max(a,min(a,b))=aa★(a*b)=min(a,max(a,b))=a因此，*和★满足吸收律。21§2运算及其性质定义:设*是S上的二元运算,若对任一xS有xx=x,则称满足等幂律（idempotent）。22§2运算及其性质例题：设(S)是集合S的幂集，在(S)上定义的两个二元运算，集合的“并”运算∪和集合的“交”运算∩，验证是∪、∩等幂的。23§2运算及其性质讨论定义：1)S上每一个元素均满足xx=x,才称在S上满足幂等律；2)若在S上存在元素xS有xx=x,则称x为S上的等幂元；3)由此定义,若x是幂等元素,则有xx=x和xn=x成立。24§2运算及其性质例：（1）在实数集合R中,+,×是可交换,可结合的,×对+是满足分配律的,“0”对+是等幂元素,而其它不为等幂元素,对“-”法是不可交换,不可结合的；25§2运算及其性质（2）在(z)中,,均是可交换,可结合的,对,对均是可分配的；(z)中任一元素,对,均是等幂元素。∴满足等幂律；而(z)中,对称差分是可交换,可结合的。26§2运算及其性质除(s)={}以外不满足等幂律。∵=,而除以外的A(z)有AA≠A。27§2运算及其性质下面定义特异元素幺元,零元和逆元。定义：设*是集合Z中的二元运算,(1)若有一元素elZ,对任一xZ有el*x=x；则称el为Z中对于*的左幺元(左单位元素)；28§2运算及其性质(2)若有一元素erZ,对任一xZ有x*er=x；则称er为Z中对于*的右幺元（右单元元素）。29§2运算及其性质定理：若el和er分别是Z中对于*的左幺元和右幺元,则对于每一个xZ，可有el=er=e和e*x=x*e=x，则称e为Z中关于运算*的幺元，且eZ是唯一的。30§2运算及其性质∵el和er分别是对*的左,右左元，则有el*er=er=el∴有el=er=e成立。31§2运算及其性质（2）幺元e是唯一的。用反证法：假设有二个不同的幺元e1和e2,则有e1*e2=e2=e1,这和假设相矛盾。∴若存在幺元的话一定是唯一的。32§2运算及其性质例：（1）在实数集合R中,对+而言,e+=0；对×而言,e*=1；（2）在(E)中,对而言,e=E（全集合）；对而言,e=（空集）；33§2运算及其性质（3）{双射函数}中,对“”而言，e=Ix（恒等函数）；（4）{命题逻辑}中，对∨而言，e∨=F（永假式）；对∧而言，e∧=T（永真式）。34§2运算及其性质例:设集合S={α,β,γ,δ}，在S上定义的两个二元运算*和★如表所示。试指出左幺元或右幺元。*αβγδαβγδδαβγαβγδαβγγαβγδ★αβγδαβγδαβδγβαγδγδαβδδβγ35§2运算及其性质定义：设*是对集合Z中的二元运算，（1）若有一元素θlZ，且对每一个xZ有θl*x=θl，则称θl为Z中对于*的左零元；（2）若有一元素θrZ，且对每一个xZ有x*θr=θr，则称θr为Z中对于*的右零元。36§2运算及其性质定理：若θl和θr分别是Z中对于*的左零元和右零元，于是对所有的xZ，可有θl=θr=θ，能使θ*x=x*θ=θ。在此情况下，θZ是唯一的，并称θ是Z中对*的零元。37§2运算及其性质例：（1）在实数集合R中，对×而言,，θL=θr=0（2）在(E)中，对而言，θ=；对而言，θ=E；（3）{命题逻辑}中，对∨而言，θ∨=T；对∧而言，θ∧=F。38§2运算及其性质例题8设集合S={浅色，深色}，定义在S上的一个二元运算*如表所示。试指出零元和幺元。*浅色深色浅色深色浅色深色深色深色39§2运算及其性质1）运算具有封闭性，当且仅当运算表中的每个元素都属于A。2）运算具有可交换性，当且仅当运算表关于主对角线是对称的。3）运算具有等幂性，当且仅当运算表的主对角线上的每一元素与它所在行（列）的表头元素相同。40§2运算及其性质定义:设代数结构A，，e中为二元运算，e为么元，a,b为A中元素,若ba＝e，那么称b为a的左逆元，a为b的右逆元。若ab＝ba＝e，那么称a(b)为b(a)的逆元。x的逆元通常记为x-1;但当运算被称为“加法运算”（记为+）时，x的逆元可记为-x。41§2运算及其性质1）A中关于运算具有幺元，当且仅当该元素所对应的行和列依次与运算表的行和列相一致。2）A中关于运算具有零元，当且仅当该元素所对应的行和列中的元素都与该元素相同。3）设A中关于运算具有幺元，a和b互逆，当且仅当位于a所在行和b所在列的元素及b所在行和a所在列的元素都是幺元。42§2运算及其性质例:设集合S={α,β,γ,δ,ζ},定义在S上的一个二元运算*如表所示。试指出代数系统S,*中各个元素的左、右逆元情况。43§2运算及其性质*αβγδζααβγδζββδαγδγγαβαβδδαγδγζζδαγζ44§2运算及其性质一般地，一个元素的左逆元不一定等于它的右逆元。一个元素可以有左逆元不一定有右逆元。甚至一个元素的左（右）逆元不一定是唯一的。45§2运算及其性质定理：设Z,*是代数系统，*是定义在Z上的一个二元运算，Z中含有幺元e。且每一个元素都有左逆元。如果*是可结合的运算。那么，这个代数系统中的任何一个元素的左逆元必定是该元素的右逆元，且每个元素的逆元是唯一的。46§2运算及其性质证明：（1）先证左逆元=右逆元：设a,b,c，且b是a的左逆元，c是b的左逆元。因为：（ba）b=eb=b所以：e=cb=c(（ba）b)=(c（ba）)b=(（cb）a)b=(（e）a)b=ab(即b也是a的右逆元)47§2运算及其性质（2）证明逆元是唯一的。设a有两个逆元b1和b2，则有b1=b1e=b1（ab2）=（b1a）b2=eb2=b248§2运算及其性质例：试构造一个代数系统，使得其中只有一个元素具有逆元。解：设m,nI,T={x|xI,m≤x≤n},那么，代数系统T,max中有一个幺元是m,且只有m有逆元，因为m=max(m,m)。49§2运算及其性质例：对于代数系统R,·，这里R是实数的全体，是普通的乘法运算，是否每个元素都有逆元。解：该代数系统中的幺元是1，除了零元素0外，所有的元素都有逆元。50§2运算及其性质例：对于代数系统Nk,+k，这里Nk={0,1,2,…,k-1},+k是定义在Nk上的模k加法运算，定义如下：对于任意x,yNkx+y若x+ykx+ky=x+y-k若x+y≥k试问是否每个元素都有逆元。51§2运算及其性质解:可以验证，+k是一个可结合的二元运算，Nk中关于运算+k的幺元是0，Nk中的每一个元素都有唯一的逆元，即0的逆元是0，每个非零元素x的逆元是k-x。52§2运算及其性质推论：(x-1)-1=x,e-1=e证明：∵x-1*x=(x-1)-1*（x-1）=x*x-1=e∴有(x-1)-1=x∵e-1*e=e=e*e∴有e-1=e53§2运算及其性质例：（1）在实数集合R中，对“+”运算，任一xR有x-1=-x，∵x+（-x）=0，加法幺元对“×”运算，对任一xR有x-1=1x（x0）∵x×1x=1，乘法幺元；54§2运算及其性质（2）在函数的合成运算中,