离散数学-代数系统课件

第5章代数系统离散数学第5章代数系统离散数学本章说明本章的主要内容一元和二元运算定义及其实例二元运算的性质代数系统定义及其实例子代数

与后面各章的关系是后面典型代数系统的基础本章说明本章的主要内容与后面各章的关系5.1二元运算及其性质5.2代数系统

本章小结

作业本章内容5.1二元运算及其性质本章内容5.1二元运算及其性质定义5.1设S为集合，函数f：S×S→S

称为S上的二元运算，简称为二元运算。举例

f:N×N→N，f(<x,y>)＝x+y 是自然数集合N上的二元运算

f:N×N→N，f(<x,y>)＝x-y 不是自然数集合N上的二元运算 称N对减法不封闭。说明验证一个运算是否为集合S上的二元运算主要考虑两点：S中任何两个元素都可以进行这种运算，且运算的结果

是唯一的。S中任何两个元素的运算结果都属于S，即S对该运算是

封闭的。5.1二元运算及其性质定义5.1设S为集合，函数f：（1）自然数集合N上的加法和乘法是N上的二元运算，但减法和除法不是。（2）整数集合Z上的加法、减法和乘法都是Z上的二元运算，而除法不是。（3）非零实数集R*上的乘法和除法都是R*上的二元运算，加法、减法不是。（4）设S＝{a1,a2,…,an}，ai

aj=ai为S上二元运算。例5.1（1）自然数集合N上的加法和乘法是N上的二元运算，但减法和除例5.1（5）设Mn(R)表示所有n阶(n≥2)实矩阵的集合，即

则矩阵加法和乘法都是Mn(R)上的二元运算。（6）S为任意集合，则∪、∩、－、

为P(S)上的二元运算。（7）SS为S上的所有函数的集合，则合成运算

为SS上的二元运算。例5.1（5）设Mn(R)表示所有n阶(n≥2)实矩阵的集合一元运算定义5.2

设S为集合，函数f：S→S称为S上的一元运算，简称为一元运算。例5.3

（1）求一个数的相反数是整数集合Z、有理数集合Q和实数集合R上的一元运算。（2）求一个数的倒数是非零有理数集合Q*、非零实数集合R*上的一元运算。（3）求一个复数的共轭复数是复数集合C上的一元运算。

一元运算定义5.2设S为集合，函数f：S→S称为S上的一（4）在幂集P(S)上，如果规定全集为S，则求集合的绝对补运算是P(S)上的一元运算。

（5）设S为集合，令A为S上所有双射函数的集合，A

SS，求一个双射函数的反函数为A上的一元运算。（6）在n(n≥2)阶实矩阵的集合Mn(R)上，求一个矩阵的转置矩阵是Mn(R)上的一元运算。一元运算举例（4）在幂集P(S)上，如果规定全集为S，则求集合的绝对补运可以用

、

、·、

、

、

等符号表示二元或一元运算，称为算符。设f:S×S→S是S上的二元运算

，对任意的x,y∈S，如果x与y的运算结果为z，即f(<x,y>)＝z，可以利用算符

简记为

x

y=z。对一元运算

，x的运算结果记作

x。例题

设R为实数集合，如下定义R上的二元运算

x,y∈R，x

y=x。 那么3

4=3，0.5

(

3)=0.5。二元与一元运算的算符可以用、、·、、、等符号表示二元或一元运算，称为算函数的解析公式运算表（表示有穷集上的一元和二元运算）

二元运算的运算表an

an

…

an

a2

an

a1

an……………a2

an

…

a2

a2

a2

a1

a2a1

an

…

a1

a2

a1

a1

a1an…

a2a1

一元运算的运算表

an

an……

a2

a2

a1

a1

ai

ai二元与一元运算的表示函数的解析公式二元运算的运算表anan…ana2例5.4

设S={1,2}，给出P(S)上的运算

和~的运算表，其中全集为S。

的运算表

{1}{2}{1,2}{1,2}{1}

{1,2}{2}{2}{2}{1,2}

{1}{1}{1,2}{2}{1}

{1,2}{2}{1}

~的运算表

{1,2}{1}{2}{2}{1}{1,2}

~

ai

ai解答例5.4例5.4设S={1,2}，给出P(S)上的运算和~的运例5.5

设S={1,2,3,4}，定义S上的二元运算

如下x

y＝(xy)mod5，

x,y∈S 求运算的运算表。解答例5.5

123411234224133314244321例5.5设S={1,2,3,4}，定义S上的二元运算如定义5.3

设

为S上的二元运算，如果对于任意的x,y∈S都有x

y=y

x，则称运算

在S上满足交换律。定义5.4

设

为S上的二元运算，如果对于任意的x,y,z∈S都有

(x

y)

z=x

(y

z)，则称运算

在S上满足结合律。说明：若+适合结合律，则有(x+y)+(u+v)＝x+y+u+v。二元运算的性质定义5.3设为S上的二元运算，如果对于任意的x,y∈S二元运算的性质定义5.5

设

为S上的二元运算，如果对于任意的x∈S有x

x=x，则称运算

在S上满足幂等律。如果S中的某些x满足x

x=x，则称x为运算

的幂等元。举例：普通的加法和乘法不适合幂等律。但0是加法的幂等元，0和1是乘法的幂等元。二元运算的性质例题 Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n

2；P(B)为幂集；AA为从A到A的函数集，|A|

2。集合运算交换律结合律幂等律Z,Q,R普通加法+普通乘法

有有有有无无Mn(R)矩阵加法+矩阵乘法

有无有有无无P(B)并∪交∩相对补对称差有有无有有有无有有有无无AA函数复合

无有无例题 Z,Q,R分别为整数、有理数、实数集；Mn(R)为定义5.6

设

和

为S上两个二元运算，如果对于任意的x,y,z∈S，有

x

(y

z)＝(x

y)

(x

z) （左分配律）

(y

z)

x＝(y

x)

(z

x) （右分配律）

则称运算

对运算

满足分配律。说明：若*对运算分配律成立，则*对运算广义分配律也成立。

x

(y1

y2

…

yn

)＝(x

y1)

(x

y2)

…

(x

yn) (y1

y2

…

yn

)

x＝(y1

x)

(y2

x)

…

(yn

x)二元运算的性质定义5.6设和为S上两个二元运算，如果对于任意的x定义5.7

设

和

为S上两个可交换的二元运算，如果对于任意的x,y∈S，都有

x

(x

y)＝x

x

(x

y)＝x

则称运算

和

满足吸收律。二元运算的性质定义5.7设和为S上两个可交换的二元运算，如果对于任 Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合，n

2；P(B)为幂集；AA为从A到A的函数集，|A|

2。

集合运算分配律吸收律Z,Q,R普通加法+与乘法

对+可分配+对不分配无Mn(R)矩阵加法+与乘法

对+可分配+对不分配无P(B)并∪与交∩

∪对∩可分配∩对∪可分配有交∩与对称差

∩对

可分配无例题 Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶定义5.8

设

为S上的二元运算，如果存在元素el（或er）

S，使得对任意x∈S都有 el

x=x(或x

er=x)

则称el(或er)是S中关于

运算的一个左单位元(或右单位元)。若e∈S关于

运算既是左单位元又是右单位元，则称e为S上关于

运算的单位元。单位元也叫做幺元。

运算可以没有左单位元和右单位元。运算可以只有左单位元。运算可以只有右单位元。运算可以既有左单位元，又有右单位元。说明二元运算中的特异元素—单位元定义5.8设为S上的二元运算，运算可以没有左单位元和右二元运算中的特异元素—零元定义5.9

设

为S上的二元运算，如果存在元素θl（或θr）∈S，使得对任意x∈S都有 θl

x=θl(或x

θr=θr)，

则称θl(或θr)是S上关于

运算的左零元(或右零元)。若θ∈S关于

运算既是左零元又是右零元，则称θ为S上关于运算

的零元。

运算可以没有左零元和右零元。运算可以只有左零元。运算可以只有右零元。运算可以既有左零元，又有右零元。说明二元运算中的特异元素—零元定义5.9设为S上的二元运二元运算中的特异元素—逆元定义5.10

设

为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是可逆的。运算可以没有左逆元和右逆元。运算可以只有左逆元。运算可以只有右逆元。运算可以既有左逆元，又有右逆元。说明二元运算中的特异元素—逆元定义5.10设为S上的二元运特异元素的实例集合运算单位元零元逆元Z,Q,R普通加法普通乘法01无0x的逆元

xx的逆元x

1Mn(R)矩阵加法矩阵乘法n阶全0矩阵n阶单位矩阵无n阶全0矩阵x逆元

xx的逆元x

1（x可逆）P(B)并∪交∩

BB

的逆元为

B的逆元为B特异元素的实例集合运算单位元零元逆元Z,Q,R普通加法0无x定理5.1定理5.1

设

为S上的二元运算，el、er分别为

运算的左单位元和右单位元，则有 el=er=e

且e

为S上关于

运算的唯一的单位元。 el

＝el

er (er为右单位元)

el

er

＝er (el为左单位元)所以el=er，将这个单位元记作e。假设e

也是S中的单位元，则有

e

=e

e

=e所以，e

是S中关于

运算的唯一的单位元。证明定理5.1定理5.1设为S上的二元运算，el、er分别为定理5.2定理5.2

设

为S上的二元运算，

l和

r分别为

运算的左零元和右零元，则有

l=

r=

且

为S上关于

运算的唯一的零元。

l

＝

l

r (

r为左零元)

l

r

＝

r (

l为右零元)所以

l=

r，将这个零元记作

。假设

也是S中的零元，则有

=

=

所以，

是S中关于

运算的唯一的零元。证明定理5.2定理5.2设为S上的二元运算，l和r分别定理5.3定理5.3

设

为S上的二元运算，e

和

分别为

运算的单位元和零元，如果S至少有两个元素，则e

。用反证法。假设e=

，则

x∈S有

x＝

x

e＝

x

＝

这与S中至少含有两个元素矛盾。所以，假设不成立，即e

。证明定理5.3定理5.3设为S上的二元运算，e和分别为定理5.4定理5.4

设

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

=yr=y

且y是x的唯一的逆元。由

yl

x=e

和

x

yr

=e，得证明yl

=yl

e令yl

=yr

=y，则y是x的逆元。=yl

(x

yr)=(yl

x)

yr=e

yr=yr假若y

S也是x的逆元，则y

=y

e=y

(x

y)=(y

x)

y=e

y=y所以y是x唯一的逆元，记作x

1。定理5.4定理5.4设为S上可结合的二元运算，e为该消去律定义5.11

设

为S上的二元运算，如果对于任意的x,y,z∈S，满足以下条件：（1）若x

y＝x

z且x

，则y

＝z（左消去律）（2）若y

x

＝z

x且x

，则y＝z（右消去律）则称

运算满足消去律。例如：整数集合上的加法和乘法都满足消去律。幂集P(S)上的并和交运算一般不满足消去律。

消去律定义5.11设为S上的二元运算，如果对于任意的x,例5.6例5.6

对于下面给定的集合和该集合上的二元运算，指出该运算的性质，并求出它的单位元、零元和所有可逆元素的逆元。（1）Z+，

x,y∈Z+，x

y＝lcm(x,y)，即求x和y的最小公倍数。（2）Q，

x,y

Q，x

y=x+y-xy解答（1）

运算可交换、可结合、是幂等的。

x

Z+，x

1=x，1

x=x，1为单位元。

不存在零元。

只有1有逆元，是它自己，其他正整数无逆元。例5.6例5.6对于下面给定的集合和该集合上的二元运算，（2）Q，

x,y

Q，x

y=x+y-xy

运算满足交换律，因为

x,y

Q，有

x

y=x+y-xy=y+x-yx=y

x运算满足结合律，因为

x,y,z

Q，有

(x

y)

z=(x+y-xy)

z=x+y-xy+z-(x+y-xy)z=x+y+z-xy-xz-yz+xyz

x

(y

z)=x

(y+z-yz)=x+(y+z-yz)-x(y+z-yz)=x+y+z-xy-xz-yz+xyz运算不满足幂等律，因为2Q，但2

2=2+2-2

2＝02

运算满足消去律，因为

x,y,z

Q，x1(1为零元)，有

x

y=x

z

x+y-xy=x+z-xz

y-z=x(y-z)

y=z

由于是可交换的，所以右消去律成立。同理可证明左消去律成立，所以消去律成立。（2）Q，x,yQ，xy=x+y-xy例5.60是运算的单位元，因为

x

Q，有

x

0=x+0-x

0=x=0

x1是运算的零元，因为

x

Q，有

x

1=x+1-x

1=1=1

x

x

Q，欲使

x

y=0和

y

x=0成立，即

x+y-xy=

0

得所以，例5.60是运算的单位元，因为xQ，有

x0=例5.7例5.7

设A={a,b,c}，A上的二元运算、、如表所示。(1)说明、、运算是否满足交换律、结合律、消去律和幂等律。(2)求出关于、、运算的单位元、零元和所有可逆元素的逆元。

abcaabcbbcaccab

运算满足交换律、结合律和消去律，不满足幂等律。单位元是a，没有零元，且a-1=a，b-1=c，c-1=b。

运算满足交换律、结合律和幂等律，不满足消去律。单位元是a，零元是b，只有a有逆元，a-1=a。运算满足结合律和幂等律，不满足交换律和消去律。没有单位元，没有零元，没有可逆元。解答

abcaabcbbbbccbc

abcaabcbabccabc复习分析例5.7例5.7设A={a,b,c}，A上的二元运算、5.2代数系统

定义5.12非空集合S和S上k个一元或二元运算f1,f2,…,fk组成的系统称为一个代数系统，简称代数，记做<S,f1,f2,…,fk>。5.2代数系统定义5.12非空集合S和S上k个一元或二5.2代数系统

实例：<N,＋>、<Z,＋,

>、<R,＋,

>都是代数系统，其中+和

分别表示普通加法和乘法。<Mn(R),＋,

>是代数系统，其中＋和

分别表示n阶(n≥2)实矩阵的加法和乘法。

<P(S),∪,∩,~>是代数系统，其中∪和∩为并和交，~为绝对补。<Zn,

,

>是代数系统，其中Zn＝{0,1,2,…,n-1}和分别表示模n的加法和乘法。

5.2代数系统实例：集合（规定了参与运算的元素）运算（只讨论有限个二元和一元运算）代数常数在定义代数系统的时候，如果把零元和单位元也作为系统的性质，称这些元素为该代数系统的特异元素或代数常数。有时为了强调某个代数系统是含有代数常数的系统，也可以把这些代数常数列到系统的表达式中。

例如：代数系统<Z,+,0>。代数系统的成分集合（规定了参与运算的元素）代数系统的成分列出所有的成分：集合、运算、代数常数(如果存在)例如

<Z,+,0>，<P(S),∪,∩,

,S>列出集合和运算，在规定系统性质时不涉及具有单位元的性质（无代数常数）

例如<Z,+>，<P(S),∪,∩>用集合名称简单标记代数系统 例如在前面已经对代数系统作了说明的前提下，上述两个代数系统可以简记为Z,P(S)代数系统的表示列出所有的成分：集合、运算、代数常数(如果存在)例如<Z定义5.13如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分，也称它们是同类型的代数系统。同类型的代数系统定义5.13如果两个代数系统中运算的个数相同，对应运算的元例如V1=<R,+,·,0,1>V2=<P(B),∪,∩,

,B>V1、V2是同类型的代数系统，因为它们都含有2个二元运算，1个一元运算，2个代数常数。但是它们的运算性质不一样。同类型的代数系统V1=<R,+,·,0,1>V2=<P(B),∪,∩,

,B>+和·可交换、可结合·对+可分配+和·不满足幂等律+与·没有吸收律+和·满足消去律∪和∩可交换、可结合∪和∩互相可分配∪和∩都有幂等律∪和∩满足吸收律∪和∩一般不满足消去律

例如V1=<R,+,·,0,1>V2=<P(B)在规定了一个代数系统的构成成分，即集合、运算以及代数常数以后，如果在对这些性质所遵从的算律加以限制，那么满足这些条件的代数系统就具有完全相同的性质，从而构成了一类特殊的代数系统。 例如：代数系统V＝<S,*>，如果*是可结合的，则称V为半群。如<Z,+>、<P(B),∪>等都是半群。从代数系统的构成成分和遵从的算律出发，将代数系统分类，然后研究每一类代数系统的共同性质，并将研究的结果运用到具体的代数系统中去。(抽象代数的基本方法)代数系统地说明在规定了一个代数系统的构成成分，即集合、运算以及代数常数以后定义5.14

设V＝<S,f1,f2,…,fk>是代数系统，B

S，如果B对f1,f2,…,fk

都是封闭的，且B和S含有相同的代数常数，则称<B,f1,f2,…,fk>是V的子代数系统，简称子代数。简记为B。例如：N是<Z,＋>的子代数，N也是<Z,＋,0>的子代数N{0}是<Z,＋>的子代数，但不是<Z,＋,0>的子代数。子代数和原代数具有相同的成分，运算性质也相同，是同类型的代数系统，在许多方面与原代数非常相似，不过可能小一些。对于任何代数系统，其子代数一定存在。说明子代数定义5.14设V＝<S,f1,f2,…,fk>是代最大的子代数：就是V本身。最小的子代数：如果令V中所有代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则B就构成了V的最小的子代数。平凡的子代数：最大和最小的子代数称为V的平凡的子代数。真子代数：若B是S的真子集，则B构成的子代数称为V的真子代数。子代数的相关概念最大的子代数：就是V本身。子代数的相关概念例5.8

设V=<Z,+,0>，令

nZ={nz|z

Z}，n为自然数，

则nZ是V的子代数。

任取nZ中的两个元素nz1和nz2(z1,z2

Z)，则有 nz1+nz2＝n(z1+z2)

nZ即nZ对+运算是封闭的。又 0=n0

nZ所以，nZ是V的子代数。

证明当n=1和0时，nZ是V的平凡子代数，其他的都是V的非平

凡的真子代数。说明例5.8例5.8设V=<Z,+,0>，令

试讨论的运算性质,有单位元例在中,为有理数零元、逆元吗？解:对任意集.对试讨论的运算性质,有单位元例在离散数学-代数系统ppt课件设单位元为e设零元为θ设单位元为e设零元为θ逆元时设a的逆元为x逆元时设a的逆元为x单位元也是零元,问A是什么集合?例*为上的二元运算,它的解:设a∈A,且a为A上*的单位元和零元,对任意x∈A,有单位元零元

必为单元素集.即单位元也是零元,问A是什么集合?例*为上的例设上满足结合律,且对试证对任意的自然数,有证明:对用归纳法由得例设上满足结合律,且对试证对任意的自当时,得时成立时,结合当时,得时成立时,结合所以对任意的,有所以对任意的,有5.3代数系统的同构与同态两个代数系统({0,1},∨)和({a,b},*)∨01011101*ababbbab0a1b5.3代数系统的同构与同态两个代数系统({0,1},∨)和两个代数系统同构的条件1.必须是同型代数系统2.两个集合的元素个数应相等3.运算定义法则相同，即对应元素运算后的结果也对应代数系统({0,1},∨)和({a,b},*)满足上述条件,即同构两个代数系统同构的条件定义：设(X,○)和(Y,*)是两个相同类型的代数系统，其运算都是二元运算，如果存在一个一一对应的函数g：X→Y，使得g(x1

○x2)=g(x1)*g(x2)x1,x2∈X则称g是一个从(X,○)到(Y,*)的同构函数或者称(X,○)和(Y,*)同构可记为：(X,○)～(Y,*)定义：设(X,○)和(Y,*)是两个相同类型的代数系统，(X,○)(Y,*)X1X2x1

○x2g(x1)g(x2)g(x1)*g(x2)看例题书(X,○)(Y,*)X1g(x1)定理：代数系统(X,○)～(Y,*)1.若(X,○)满足结合律,则(Y,*)也满足结合律2.若(X,○)满足交换律,则(Y,*)也满足交换律3.若(X,○)有单位元1x,则(Y,*)也有单位元1y，且1y=g(1x)4.若(X,○)对∨x∈X都存在逆元素x-1，则(Y,*)也对∨y∈Y都存在逆元素y-1,并且若g(x)=y，则g(x-1)=y-15.若(X,○)有零元0x,则(Y,*)也有零元0y，且0y=g(0x)定理：代数系统(X,○)～(Y,*)定理：代数系统(X,○，*)～(Y,◎，⊕)若(X,○，*)满足分配律，则(Y,◎，⊕)也满足分配律定理：代数系统之间的同构关系是等价关系一个代数系统和自身的同构称为自同构定理：代数系统(X,○，*)～(Y,◎，⊕)定义：设(X,○)和(Y,*)是两个相同类型的代数系统，其运算都是二元运算，如果存在一个一一对应的函数g：X→Y，使得g(x1

○x2)=g(x1)*g(x2)x1,x2∈X则称g是一个从(X,○)到(Y,*)的同构函数或者称(X,○)和(Y,*)同构可记为：(X,○)～(Y,*)定义：设(X,○)和(Y,*)是两个相同类型的代数系统，单射映射函数满(单、双)射满射单射映射函数满(单、双)射满射定义：设(X,○)和(Y,*)是两个相同类型的代数系统，其运算都是二元运算，如果存在一个函数g：X→Y，使得g(x1○x2)=g(x1)*g(x2)x1,x2∈X则称g是一个从(X,○)到(Y,*)的同态映射或者称(X,○)和(Y,*)同态如函数为满函数，则称(X,○)和(Y,*)满同态如函数为单射函数，则称(X,○)和(Y,*)单同态一个代数系统和自身的同态称为自同态定义：设(X,○)和(Y,*)是两个相同类型的代数系统，U=(I,+)V=(S,⊕)是代数系统f:U→V偶数→0奇数→1f是U到V的同态，不是满也不是单U=(I,+)V=(S,⊕)是代数系统f:U→V偶数→0奇数→1f是U到V的满同态