离散数学 第五章 代数结构

离散数学课件第五章代数结构第1页，课件共52页，创作于2023年2月由于数学和其他科学的发展，人们需要对若干不是数的事物，用类似普通计算的方法进行相似的计算。如矩阵、向量等。研究代数系统的学科称为“近世代数”或“抽象代数”。第2页，课件共52页，创作于2023年2月本章主要内容集合的概念1集合的表示方法2同态与同构6阿贝尔群与循环群4陪集与拉格朗日定理5集合的概念1集合的表示方法2群与子群3代数系统与性质1半群2第3页，课件共52页，创作于2023年2月5-1代数系统的引入定义5-1.1

如果

为An到B的一个函数，则称

为集合A上的n元运算（operater）。如果B

A，则称该n元运算在A上封闭。第4页，课件共52页，创作于2023年2月代数系统的定义定义5-1.2

一个非空集合A连同若干个定义在该集合上的运算f1,f2,…,fk

所组成的系统称为一个代数系统（代数结构），记为<A,f1,f2,…,fk>。代数结构由以下三个部分组成：非空集合S，称为代数结构的载体。载体S上的若干运算。一组刻划载体上各运算所满足性质的公理。代数系统常用一个多元序组<S，

，

，…>来表示。第5页，课件共52页，创作于2023年2月代数系统举例(1)R上的“+”、“×”运算，构成一个代数系统〈R，+，×〉；(2)ρ(S)上的“∩”、“∪”、“―”运算，构成代数系统〈ρ(S),∩,∪,―〉，称集合代数；(3)

含有n个命题变元的命题集合A与A上的“∧”、“∨”、“┐”运算，构成代数系统〈A，∧，∨，┐〉，称之为命题代数。第6页，课件共52页，创作于2023年2月5-2二元运算的性质定义可以用o、*、·、⊕、等符号表示二元或一元运算,称为算符。定义5-2.1设*是定义在集合A上的二元运算，如果对于任意的x，y∈A，都有x*y∈A，则称二元运算*在A上是封闭的。第7页，课件共52页，创作于2023年2月二元运算的主要算律定义设o为S上的二元运算,

(1)如果对于任意的x,y∈S,有xoy=yox,则称运算o在S上满足交换律。

(2)如果对于任意的x,y,z∈S有(xoy)oz=xo(yoz),则称运算o在S上满足结合律。

(3)如果对于任意的x∈S有xox=x,则称o运算在S上满足幂等律（等幂律）。第8页，课件共52页，创作于2023年2月二元运算的主要算律（续）定义设o和*为S上两个不同的二元运算,

(1)如果对于任意的x,y,z∈S有(x*y)oz=(xoz)*(yoz)和zo(x*y)=(zox)*(zoy),则称o运算对*运算满足分配律。

(2)如果o和*都可交换,并且对于任意的x,y∈S有xo(x*y)=x和x*(xoy)=x,则称o和*运算满足吸收律。第9页，课件共52页，创作于2023年2月特殊元素1：幺元（单位元）定义5-2.7

设<A,

>是二元代数系统，（1）若存在el∈A，使得对任意a∈A，都有

el

a=a，则称el是A中关于运算“

”的一个左幺元（左单位元）（2）若存在er∈A，使得对任意a∈A，都有

a

er=a，称er是A中关于运算“

”的一个右幺元（右单位元）（3）若存在e∈A，对任意a∈A，都有

a

e=e

a=a，则称e是A中关于运算“

”的一个幺元（单位元）第10页，课件共52页，创作于2023年2月幺元的性质定理5-2.1设*是定义在集合A上的一个二元运算，且在A中有关于

运算的左幺元el和右幺元er，则el=er=e，且A中的幺元是唯一的。证明：（先证左幺元el=右幺元er=e）el=el

er=er=e

（再证幺元e是唯一的）设还有一个幺元e’

A,则

e’=e’

e=e第11页，课件共52页，创作于2023年2月特殊元素2：零元定义5-2.8

设<A,

>是一个二元代数系统，（1）若存在

l∈A，使得对任意a∈A，都有

l

a=

l，则称

l是A中关于运算“

”的一个左零元；（2）若存在

r∈A，使得对任意a∈A，都有a

r=

r，则称

r是A中关于运算“

”的一个右零元。（3）若存在

∈A，使得对任意a∈A，都有a

=

a=

，则称θ是A中关于运算“

”的一个零元；第12页，课件共52页，创作于2023年2月零元的性质定理5-2.2设*是定义在集合A上的一个二元运算，且在A中有关于

运算的左零元

l和右零元

r，则

l=

r=

，且A中的零元是唯一的。证明：（先证左零元

l=右零元

r=

）

l=

l

r=

r=

（再证零元

是唯一的）设还有一个零元

’

A,则

’=

’

=

第13页，课件共52页，创作于2023年2月幺元、零元举例例：代数A=〈{a，b，c}，。〉用下表定义：。abcaabbbabccaba则b是左么元，无右么元；

a是右零元，b是右零元；无左零元;运算：既不满足结合律，也不满足交换律。第14页，课件共52页，创作于2023年2月幺元、零元举例（续）例:求出下列集合的幺元，零元。（1）〈I，×〉，I为整数集则幺元为1，零元为0（2）〈

（A）,∪,∩〉对运算∪，

是幺元，A是零元，对运算∩，A是幺元，

是零元。（3）〈N，+〉有幺元0，无零元。第15页，课件共52页，创作于2023年2月幺元、零元性质定理5-2.3

如果代数结构<A，

>有关于

运算的零元

和幺元e

，且集合A中元素个数大于1，则

≠e

。

证明：用反证法：

设幺元e

=零元

，则对于任意x

A

，必有

x

=e

x=

x

=

=

e

于是，推出A中所有元素都是相同的，矛盾。

第16页，课件共52页，创作于2023年2月特殊元素3：逆元定义5-2.9

设<A,

>是二元代数系统，e是幺元，a∈A，若存在一个元素b∈A，（1）使得：b

a=e，则称b是a的一个左逆元，记为al

1；（2）使得：a

b=e，则称b是a的一个右逆元，记为ar

1。（3）使得：a

b=b

a=e，则称a可逆，并称b是a的一个逆元，记为a

1；第17页，课件共52页，创作于2023年2月逆元的性质注：一般地，一个元素的左逆元不一定等于它的右逆元。一个元素左、右逆元不一定同时存在。甚至一个元素的左（右）逆元不一定是唯一的。定理

设*为S上可结合的二元运算,e为该运算的单位元,对于x∈S如果存在左逆元yl和右逆元yr,则有yl

=yr=y，且y是x的唯一的逆元。第18页，课件共52页，创作于2023年2月证明：因为yl*x=e，x*yr=e，故

yl=yl*e=yl*(x*yr)=(yl*x)*yr=e*yr=yr令yl=yr=y,则y是x的逆元。设y＇∈S也是x的逆元,则

y'=y'*e=y'*(x*y)=(y'*x)*y=e*y=y所以y是x唯一的逆元。第19页，课件共52页，创作于2023年2月通过运算表观察二元运算的性质1）封闭性：表中的每个元素都属于A。2）可交换性：运算表关于主对角线是对称的。3）等幂性：运算表的主对角线上的每一元素与它所在行（列）的表头元素相同。4）A中关于运算

具有零元：该元素所对应的行和列中的元素都与该元素相同。5）A中关于运算

具有幺元：该元素所对应的行和列依次与运算表的首行和首列相一致。6）A中关于运算

具有幺元，a和b互逆：位于a行b列的元素以及b行a列的元素都是幺元。第20页，课件共52页，创作于2023年2月例：P182例题9，10，11，12第21页，课件共52页，创作于2023年2月例：设X={e,a,b,c,d}，*是X上的二元运算，*的运算表如下。

从本例还可以看到a的逆元也是c,d。运算*满足可交换性，但不满足等幂性。*eabcdeeabcdaaaaeebbaaeecceeccddeecc从表中可知，<X，*>是代数系统，e是关于*的幺元。X中无零元。表中b*c=c*b=e；b*d=d*b=e，故c和d均为b的逆元，即b的逆元不唯一。原因在于运算*不满足结合律。第22页，课件共52页，创作于2023年2月练习：指出下面运算的性质，并求出幺元,零元，可逆元素的逆元。1、在Q集合上，

x,yQ，x*y=x+y-xy2、在I+集合上,x,yI+，x*y=lcm(x,y)1、满足交换律、结合律，不满足幂等律，幺元为0，零元为1，x的逆元x-1=x/(x-1)(x≠1)2、满足交换律、结合律、幂等律，幺元为1，无零元，只有1有逆元，其逆元为1。第23页，课件共52页，创作于2023年2月5-3半群定义5-3.1

如果集合S上的二元运算

是封闭的，则称代数系统<S，

>为广群。定义5-3.2

如果集合S上的二元运算

是封闭的并且满足结合律，则称代数结构<S，

>为半群。例：P186例题1，例题2第24页，课件共52页，创作于2023年2月子半群定理5-3.1设<S,

>为一半群,B

S且在B上封闭，那么<B,>也是一个半群，称为<S,

>的子半群。例：乘法运算在某些集合上构成<R,×>的子半群。第25页，课件共52页，创作于2023年2月含幺半群（独异点）定义5-3.3

设代数结构<S,

>为半群，若<S,

>含有关于

运算的幺元,则称它为独异点，或含幺半群，有时也记为<S,

,e>。第26页，课件共52页，创作于2023年2月独异点的性质——运算表中任两行两列不相同定理5-3.3

设<S,

,e>是一个独异点,则在关于运算

的运算表中任何两行或两列都是不相同的。例:设I是整数集合，m是任意正整数，Zm是由模m的同余类组成的同余类集，在Zm上定义两个二元运算+m和×m分别如下：对于任意的[i]，[j]

Zm，有

[i]+m[j]=[(i+j)(modm)][i]×m[j]=[(i×j)(modm)]

试证明在这两个二元运算的运算表中任何两行或两列都是不相同的。第27页，课件共52页，创作于2023年2月证明思路：1、证明运算的封闭性；

Zm＝｛[0],[1],[2],…,[m－1]｝,

任意[x],[y]∈Zm,

显然[x]+m[y]∈Zm,[x]×m[y]∈Zm,

所以+m、×m运算封闭性成立。2、证明运算满足结合律；任意[x],[y],[z]∈Zm,有([x]＋m[y])＋m[z]

＝([x]＋[y]+[z])(modm)＝[x]＋m([y]＋m[z])所以+m满足结合律，同理可证×m满足结合律。3、显然，[0]、[1]分别为+m和×m的幺元。第28页，课件共52页，创作于2023年2月综上所述，<Zm,+m>和<Zm,×m>都是独异点。由定理5-3.3可知，这两个运算的运算表中任两行或两列都不相等。第29页，课件共52页，创作于2023年2月独异点的性质定理5-3.4

设<S,

,e>是一个独异点,如果对于任意a,b

S，且a,b均有逆元，则a)(a-1)-1=ab)ab有逆元，且(ab)-1=b-1

a-1。证明:a)因a-1和a为互为逆元，直接得到结论。b)必须证明两种情况：(ab)(b-1

a-1)

=e

和(b-1

a-1)

(ab)=e利用结合律容易得出。第30页，课件共52页，创作于2023年2月子独异点定义5-3.3

设代数结构<S,

>为半群，若B

S且在B上封闭，B含有<S,

>关于

运算的幺元,那么<B,>称为子独异点，或子幺半群。第31页，课件共52页，创作于2023年2月独异点举例设Σ是一个非空有限集合，称为字母表，由Σ中有限个字母组成的有序集合（即字符串）称为Σ上的一个字，串中的字母个数m称为字长，m=0时，称为空字，即为单位元，记为e。Σ∗表示Σ上的字的集合，Σ∗上的连接运算·定义为α，β∈Σ∗，α·β=αβ，则<Σ∗，·>是一个代数系统，而且是一个独异点,是在计算机科学中自动机理论及形式语言中最基本的结构。Σ∗的任一子集就称为语言。第32页，课件共52页，创作于2023年2月5-4群与子群定义5-4.1

称代数结构<G,

>为群(groups),如果（1）<G，

>中运算

是封闭的；（2）<G，

>中运算

是可结合的；（3）<G，

>中有幺元e；（4）<G，

>中每一元素x都有逆元x-1。第33页，课件共52页，创作于2023年2月群举例例题1R={0°,60°,120°,180°,240°,300°},*是R上的二元运算，a*b表示先旋转a再旋转b的角度，并规定旋转360°等于原来的状态。运算表如表5-4.1所示。验证代数结构<R,*>为群。解题思路：需证明<R,*>：（1）运算*封闭；（2）运算*是可结合的；（3）有幺元0°;（4）每一元素x都有逆元x-1。第34页，课件共52页，创作于2023年2月典型的群1、<Z,+>

2、<R+,×>

3、<Z6，+6>,其中Z6={0，1，2，3，4，5}，单位元是0；1、5互为逆元，2、4互为逆元，3的逆元为3，0的逆元为0。注：<Z+,+>不是群，其不存在幺元，且每个元素也不存在逆元。而<N,+>存在幺元，除0以外，均不存在逆元，故其只是半群。第35页，课件共52页，创作于2023年2月代数结构总图封闭<G,

>广群半群独异点群结合含幺可逆

<G,

>广群半群独异点群第36页，课件共52页，创作于2023年2月有限群与无限群定义5-4.2

设<G,

>为一群。若G为无限集，则称<G,

>为无限群；否则，称<G,

>为有限群，此时G的元素个数称为G的阶,记为|G|。第37页，课件共52页，创作于2023年2月有限群举例第38页，课件共52页，创作于2023年2月Klein四元群*eabceeabcaaecbbbceaccbaeKlein四元群:e为G中的单位元；运算是可交换的；

G中任何元素的逆元就是它自己；在a,b,c三个元素中,任何两个元素运算的结果都等于另一个元素。第39页，课件共52页，创作于2023年2月群的性质1——阶数大于1的群中无零元定理5-4.1

设<G，

>为群，那么当G

{e}时,G无零元。证明:

设|G|>1

且群有零元。那么群中任何元素x

G，都有

x

=

x=

≠

e，所以，零元

就不存在逆元，与<G，

>是群的假设矛盾。第40页，课件共52页，创作于2023年2月群的性质2——群方程存在唯一解定理5-4.2

设<G，

>为群，对于a,bG，必存在xG，使得关于x的方程a

x＝b有唯一解。证明:1）先证解存在性；

设a的逆元a-1，令x=a-1

b（构造一个解）

a

x＝a(a-1

b)＝（a

a-1）

b

＝e

b＝b

2）再证解唯一性;

若另有解x1满足a

x1

＝b，则

x1

＝（

a-1

a

）*x1

＝a-1

（a

*x1）＝a-1

b＝x第41页，课件共52页，创作于2023年2月群的性质3——群满足消去律定理5-4.3

设<G，

>为群，那么，对任意a,x,y

G

如果a

x=a

y，则x=y；（左乘a-1可证）如果x

a=y

a，则x=y

。（右乘a-1可证）

第42页，课件共52页，创作于2023年2月群的性质4——幺元是群中唯一等幂元定义5-4.4设<G，

>为群，如果存在a

G，有a

a=a，则称a为等幂元。定理5-4.5

在群<G，

>中，除幺元e之外，不可能有任何别的等幂元。证明:因为e

e=e，所以e是等幂元。现设a

G，a≠e且a

a=a则有a=e

a=(a-1

a)

a=a-1(a

a)=a-1

a=e

与假设a≠e矛盾。第43页，课件共52页，创作于2023年2月子群及子群的性质定义5-4.5设<G，

>为群。如果S

G，且<S，

>为一群，则称<S，

>为<G，

>的子群；若S真包含于G，则为真子群。定理5-4.6

设<G,

>为群，<S,

>为G的子群，那么，<G,

>中的幺元e必定也是<S,

>中的幺元。证明:设<G,

>中的幺元为e1，对于任意一个元素xSG,必有e1

x=e

x，因为群满足消去律，所以e1=e。第44页，课件共52页，创作于2023年2月子群举例<Z6,+6>是群，H1={0,2,4},H2={0,1,5},H3={0,3},问：<H1,+6>,<H2,+6>,<H3,+6>是<Z6,+6>的子群吗？解：<H1,+6>是<Z6,+6>的子群；

<H2,+6>不是<Z6,+6>的子群；（因为运算不封闭）

<H3,+6>是<Z6,+6>的子群。第45页，课件共52页，创作于2023年2月平凡子群定义5-4.6对任何群G都存在子群。G和{e}都是G的子群,称为G的平凡子群。第46页，课件共52页，创作于2023年2月子群的判定定理定理5-4.7

设<G,

>为群，B为G的非空子集，如果B是一个有限集,那么,只要运算

在B上封闭（即任意a,bB有a*bB),<B,

>必定是<G,

>的子群。定理5-4.8

设<G,△>为群,S为G的非空子集,如果对于任意元素a,bS有a△b-1S,那么,<S,△>必定是<G,△>的子群。第47页，课件共52页，创作于2023年2月典型子群：生成子群定义设G为群,a∈G,令H={ak|k∈Z}，即a的所有的幂构成的集合,则H是G的子群,称为由a生成的子群,记作<a>。

例1：整数加群,由2生成的子群是：

<2>={2k|k∈Z}

例2：群<Z6,+6>中,由2生成的子群是：20