离散数学讲稿——6代数结构

代数系统本篇用代数方法来研究数学结构,故又叫代数结构,它将 用抽象的方法来研究集合上的关系和运算 代数的概念和方法已经渗透到计算机科学的许多分支中 ,它对程序理论,数据结构,编码理论的研究和逻辑电 路的设计已具有理论和实践的指导意义 本篇讨论一些典型的代数系统及其性质（包括格） 代数系统第五章代 数 结 构§1代数系统的引入§2运算及其性质§3半群§4群与子群§5阿贝尔群和循环群§6*陪集与拉格朗日定理§7同态与同构§1 代数系统的引入《定义》:设Z是一个集合,f是一个函数,f：ZnZ,则称f为 Z中的n元运算,整数n称为运算的阶（元,次） 若n=1,则称f： ZZ为一元运算；若n=2,则f： Z2Z为二元运算本章主要讨论一元运算和二元运算例：（1）在整数I和实数R中,+,-,×均为二元运算,而对÷ 而言就不是二元运算 （2）在集合Z的幂集(z)中,,均为二元运算,而 “~”是一元运算；§1 代数系统的引入（3）{命题公式}中,∨,∧均为二元运算,而“”为一元 运算（4）{双射函数}中,函数的合成运算是二元运算；二元运算常用符号：+,,,,,,,等等《定义》:一个非空集合A连同若干个定义在该集合上的运 算f1,f2,….,fk所组成的系统就称为一个代数系统，记作。

§1 代数系统的引入《定义》:若对给定集合中的元素进行运算,而产生的象 点仍在该集合中,则称此集合在该运算的作用下是封闭 的 在f：Z2Z二元运算的定义中,本身要求满足运算是封 闭的 例：（1）在正整偶数的集合E中,对×,+运算是封闭的；在正整奇数的集合中,对×运算是封闭的 ,而对+运算不是封闭的 （2）在前例中,R,I集合中+,-,×运算； (z)的元 素中, ,~,运算等均为封闭的§2运算及其性质《定义》:设*是集合S上的二元运算,对任一x,yS有 xy∈S则称运算在S上是封闭的《定义》:设*是集合S上的二元运算,对任一x,yS有 xy=y  x,则称运算在S上是可交换的（或者说在S 上满足交换律）§2运算及其性质《定义》:设*是集合S上的二元运算,对任一x,y,z S 都有（x  y）  z=x  （y  z）,则称运算在S上是可结 合的（或者说*在S上满足结合律）《定义》:设和是集合S上的二个二元运算,对任一x,y,z S有x  （y  z）=（x  y）  （x  z）；（y  z）  x=（y  x）  （z  x）,则称运算对是 可分配的（或称对满足分配律）。

§2运算及其性质《定义》:设，是定义在集合S上的两个可交换二元运 算，如果对于任意的x,yS，都有： x (x y)=x；x (xy)=x 则称运算和运算满足吸收律 《定义》:设*是S上的二元运算,若对任一 x S有x  x=x,则称满足等幂律 讨论定义： 1)S上每一个元素均满足xx=x,才称在S上满足幂等律； 2)若在S上存在元素xS有x  x=x,则称x为S上的幂等元 素； 3)由此定义,若x是幂等元素,则有x  x=x和xn=x成立§2运算及其性质例：（1）在实数集合R中,+,×是可交换,可结合的,×对+是 满足分配律的,“0”对+是等幂元素,而其它不为等幂元素, 对“-”法是不可交换,不可结合的；（2）在(z)中, ,均是可交换,可结合的, 对, 对 均是可分配的；(z)中任一元素,对,均是等幂元素∴满足等幂律 ； 而(z)中,对称差分是可交换,可结合的 除(s) ={}以外不满足等幂律∵    = ,而除 以外的A (z)有A  A≠A§2运算及其性质《定义》：设*是S上的二元运算,对任一xS,则： x1=x, x2=x*x,…xn=xn-1*x 《定理》：设*是S上的二元运算,且x S,对任一m,n I+ 有（1）xmxn=xm+n （2）(xm)n=xmn 证明： （1） xmxn= (xm x)  x… x = (xm+1 x)  x… x n n-1 =….= xm+n （2）(xm)n= xm …  xm= xm+m xm … xm=…=xmnn n-1§2运算及其性质下面定义特异元素幺元,零元和逆元。

《定义》：设*是集合Z中的二元运算, (1)若有一元素el Z,对任一x Z有el*x=x；则称el为Z 中对于*的左幺元(左单位元素)； (2)若有一元素er Z,对任一x Z有x* er=x；则称er为Z 中对于*的右幺元（右单元元素） 《定理》：若el和er分别是Z中对于*的左幺元和右幺元, 则对于每一个x Z，可有el= er = e和e*x=x* e=x，则 称e为Z中关于运算* 的幺元，且e Z是唯一的§2运算及其性质∵ el和er分别是对*的左,右左元，则有el * er = er = el∴有el = er = e成立2）幺元e是唯一的用反证法：假设有二个不同的幺 元e1和e2,则有e1* e2= e2= e1,这和假设相矛盾 ∴若存在幺元的话一定是唯一的例： （1）在实数集合R中,对+而言, e+=0；对×而言, e*=1 ； （2）在(E)中,对而言, e  =E（全集合）；对而言, e  =（空集）；§2运算及其性质（3）{双射函数}中,对“”而言，e  =Ix（恒等函数）； （4）{命题逻辑}中，对∨而言，e ∨ =F（永假式）；对∧而言， e ∧ =T（永真式）。

《定义》：设*是对集合Z中的二元运算，（1）若有一元素θl Z，且对每一个x Z有θl *x= θl ，则称θl 为Z中对于*的左零元； （2）若有一元素θr Z，且对每一个x Z有x* θr= θr ，则称θr为Z中对于*的右零元§2运算及其性质《定理》：若θl和θr分别是Z中对于*的左零元和 右零元，于是对所有的x Z，可有θl = θr =θ， 能使θ*x=x*θ=θ在此情况下，θ Z是唯一的 ，并称θ是Z中对*的零元 证明：方法同幺元 例： （1）在实数集合R中，对×而言,，θL = θr =0 （2）在(E)中，对而言，θ  =  ；对而言，θ  = E ； （3）{命题逻辑}中，对∨而言，θ ∨ =T ；对∧而言，θ ∧ = F§2运算及其性质《定义》：设*是Z中的二元运算，且Z中含幺元e， 令x Z， （1）若存在一xlZ，能使xl *x= e，则称xL是x的左逆 元,并且称x是左可逆的； （2）若存在一xr Z，能使x* xr = e，则称xr是x的右 逆元，并且称x是右可逆的； （3）若元素x既是左可逆的，又是右可逆的，则称x 是可逆的，且x的逆元用x-1表示。

§2运算及其性质《定理》：设Z是集合，并含有幺元e 是定义在Z上的 一个二元运算，并且是可结合的若x Z是可逆的， 则它的左逆元等于右逆元，且逆元是唯一的 证明：（1）先证左逆元=右逆元：设xL和xr分别是x Z的左逆元和右逆元， ∵x是可逆的和*是可结合的（条件给出） ∴ xl *x=x* xr = e ∵ xl *x* xr =（ xl*x）* xr = e * xr= xr ； xl *x* xr = xl*(x* xr) = xl* e = xl ∴ xr = xl§2运算及其性质（2）证明逆元是唯一的（若有的话）： 假设x1-1和x2-1均是x的二个不同的逆元，则x1-1= x1-1*e= x1-1 *（x* x2-1 ）=（ x1-1 *x）* x2-1 = e * x2-1 = x2-1， 这和假设相矛盾 ∴x若存在逆元的话一定是唯一的 《推论》(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= e 例：（1）在实数集合R中，对“+”运算，对任一xR有x-1 =-x，∵x+（-x）=0，加法幺元§2运算及其性质对“×”运算，对任一x R有x-1 =1x（x0）∵x× 1x =1，乘法幺元；（2）在函数的合成运算中,每一个双射函数都是可逆的，f-1（f的逆关系）； （3）在所有的二元运算中,零元一定不存在逆元，∵θ*x=x*θ=θ。

《定义》设*是Z集合中的二元运算，且a Z和x,y Z， 若对每一x，y有 （a*x=a*y）（x*a=y*a）（x=y），则称a是可约的（或称可消去 的）§2运算及其性质《定理》设*是Z集合中的二元运算,且*是可结合的 ,若元素a Z,且对于*是可逆的,则a也是可约的 （反之不一定,即可约的不一定是可逆的证明：设任一x，y Z,且有a*x=a*y，下面证明， 在*可结合和a对*是可逆的条件下，a是可约的∵*是可结合的和a Z对*是可逆的（条件给出）∴a-1*（a*x）=（ a-1 *a）*x=e*x=x 而 a-1 *（a*y）=（ a-1 *a）*y= e *y=y,即x=y由定义可知a是可约的§2运算及其性质下面举例证明，若元素是可约的，但不一定是可逆的 例：I为整数集合，对“”运算，运算是可结合的任何 非零元素均是可约的，但除1和（-1）以外其他元素均 没有逆元1-1=1 ，(-1)-1=(-1) 例：Z={0,1,2,3,4},定义Z中二个运算为，对任一x，y Z有x+5y=（x+y）mod 5 x5y=（xy）mod 5§2运算及其性质e+5=0, 0-1=0, 1-1=4, 2-1=3, 3 -1 =2, 4-1=1。

e*5= 1, θ*5=1,1-1=1, 2-1=3, 3-1=2, 4-1=4, 0没有逆元以上二元运算的性质均可运用到代数系统进行讨论50 1 2 3 40 1 2 3 40 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3*50 1 2 3 40 1 2 3 40 0 0 0 0 0 1 2 3 4 0 2 4 1 3 0 3 1 4 2 0 4 3 2 1§3 半群《定义》：一个代数系统， S为非空集合， 是S上的二元运算，如果运算是封闭 的，则称代数系统为广群 《定义》：设是一代数系统，S为非空集合，  是S上的二元运算，若 (1)运算是封闭的 (2) 运算满足结合律，则称为半群 例： , , ,均为半群 《定义》：对于*运算，拥有幺元的半群称为含 幺半群。

拟群，幺半群，独异点） 例： , 均为含幺半群，而就不为幺半群 §3 半群例：设S为非空集合， (S)是S的幂集， 则 ,均为含幺半群 而，其中max(x1,x2)取二者之大值；，其中min(x1,x2)取二者之小值，均不为幺半群 （不存在幺元）则为含幺半群，其中 e =0 《定义》：设是一半群，TS，且*在T上是 封闭的，那么也是半群，称是的子半群§3 半群讨论定义： （1）因为*在S上是可结合的，而TS且*在T上是封 闭的，所以*在T上也是可结合的。