《离散数学》第六章几个典型的代数系统讲稿Word格式文档下载.docx

资源描述

《离散数学》第六章几个典型的代数系统讲稿Word格式文档下载.docx

《《离散数学》第六章几个典型的代数系统讲稿Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《《离散数学》第六章几个典型的代数系统讲稿Word格式文档下载.docx（27页珍藏版）》请在冰点文库上搜索。

《离散数学》第六章几个典型的代数系统讲稿Word格式文档下载.docx

定义设V=<

是半群

（1）若运算是可交换的，则称V为交换半群.

（2）若e∈S是关于运算的幺元，则称V是含幺半群，也叫做独异点.

独异点V记作V=<

S,,e>

独异点的幂

独异点的幂运算定义

x0=e

xn+1=xnx,n∈N

幂运算规则

xnxm=xn+m

（xn）m=xnmm,n∈N

交换半群和独异点的实例

例1

（1）<

N,+,0>

Z,+,0>

Q,+,0>

R,+,0>

都是交

换半群，也是独异点，+是普通加法.

（2）设n是大于1的正整数，<

都是

独异点，其中+和·

分别表示矩阵加法和矩阵乘法.加

法构成交换半群，乘法不是交换半群.

P（B）,,>

为交换半群和独异点，其中为集合的对

称差运算.

Zn,,0>

为交换半群与独异点，其中Zn={0,1,…,

n1}，为模n加法.

AA,,IA>

为独异点，不是交换半群，其中为函数的

复合运算.

半群与独异点的子代数

定义半群的子代数称为子半群，独异点的子代数称

为子独异点

判断方法

设V=<

S,>

为半群，T是S的非空子集，

T是V的子半群当且仅当T对o运算封闭.

设V=<

为独异点，T是V的子独异点当且仅当T对o运算封闭，且eT

实例：

是<

的子半群，<

的子独异点，<

不是<

的子独异点.

半群与独异点的积代数

定义设V1=<

S1,>

，V2=<

S2,∗>

是半群（或独异

点），令S=S1×

S2，定义S上的·

运算如下：

a,b>

c,d>

∈S，

ac,b∗d>

称<

S,·

为V1和V2的积半群（直积），记作

V1×

V2.若V1=<

S1,,e1>

和V2=<

S2,∗,e2>

是独

异点，则V1×

V2=<

S1×

S2,·

e1,e2>

也是独异

点,称为独异点的积独异点（直积）.

半群和独异点的同态

定义

（1）设V1=<

，V2=<

是半群，：

S1→S2.若对任意的x,y∈S1有

（xy）=（x）∗（y）

则称为半群V1到V2的同态映射，简称同态.

（2）设V1=<

S1,,e1>

，V2=<

S2,∗,e2>

是独异点，

S1→S2.若对任意的x,y∈S1有

（xy）=（x）∗（y）且（e1）=e2,

则称为独异点V1到V2的同态映射，简称同态.

同态的实例

例2设半群V1=<

，独异点V2=<

.其中·

为矩阵乘法，e为2阶单位矩阵,

令：

SS,,是半群V1的自同

态,不是独异点V2的自同态，因为它没有将V2的单位元映到V2的单位元.

群的定义与实例

定义设<

G,>

是代数系统，为二元运算.如果

运算是可结合的，存在幺元e∈G，并且对G中

的任何元素x都有x1∈G，则称G为群.

群的实例

（1）<

是群；

不是群.

（2）<

是群，而<

（3）<

是群，为对称差运算.

（4）<

Zn,>

是群.Zn={0,1,…,n1}，为模n加.

Klein四元群

设G={e,a,b,c}，G上的运算由下表给出，

eabc

aecb

bcea

cbae

称为Klein四元群

群中的术语

实例

和<

是无限群

是有限群，也是n阶群

Klein四元群G={e,a,b,c}是4阶群

上述群都是交换群

n阶（n≥2）实可逆矩阵集合关于矩阵乘法构成的群是非交换群.

群中的术语（续

定义设G是群，x∈G，n∈Z，则x的n次幂xn

定义为

群中的术语

设G是群，x∈G，使得等式xk=e成立的最小正

整数k称为x的阶（或周期），记作|x|=k，称

x为k阶元.若不存在这样的正整数k，则称x为

无限阶元.

群的性质---幂运算规则

群的性质---群方程存在唯一解

群的性质---消去律

群的性质---运算表排列规则

定理4设G为有限群，则G的运算表中每行每列

都是G中元素的一个置换，且不同的行（或列）

的置换都不相同.

注意：

必要条件，用于判断一个运算表不是群.

abcd

bcda

bacd

cdba

dbac

cdab

dabc

子群的定义

子群判定定理

判定定理

设G为群，H是G的非空子集.H是G的子群当且仅当x,y∈H有xy1∈H.

证明H为G的子群的步骤：

通过给出H中的元素说明H是G的非空子集

任取x,y属于H，证明xy-1属于H

重要子群

生成子群

定义设G为群，a∈G，令H={ak|k∈Z}，

则H是G的子群，称为由a生成的子群，记作

证首先由a∈<

知道<

≠.任取am,al∈<

，则

am（al）1=amal=aml∈<

根据判定定理可知<

≤G.

整数加群<

，

由2生成的子群是<

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

模6加群<

Z6,>

中

由2生成的子群<

={0,2,4}

Klein四元群G={e,a,b,c}的所有生成子群是：

={e},

={e,a},<

={e,b},<

={e,c}.

重要子群

群G的中心C

设G为群,令C={a|a∈G∧x∈G（ax=xa）}，则C

是G的子群，称为G的中心.

证e∈C.C是G的非空子集.

任取a,b∈C，证明ab1与G中所有的元素都可交换.x∈G，有

（ab1）x=ab1x=ab1（x1）1=a（x1b）1=a（bx1）1

=a（xb1）=（ax）b1=（xa）b1=x（ab1）

由判定定理可知C≤G.

循环群的定义

定义设G是群，若存在a∈G使得

G={ak|k∈Z}

则称G是循环群，记作G=<

，称a为G的生成

元.

实例

整数加群G=<

-1>

模6加群G=<

Z6,>

循环群的分类

设循环群G=<

，根据生成元a的阶可以分

成两类：

n阶循环群和无限循环群.

设G=<

是循环群，若a是n阶元，则

G={a0=e,a1,a2,…,an1}

那么|G|=n，称G为n阶循环群.

若a是无限阶元，则

G={a±

0=e,a±

1,a±

2,…}

这时称G为无限循环群.

循环群的生成元

定理

是循环群.

（1）若G是无限循环群，则G只有a和a1两个生

成元.

（2）若G是n阶循环群，则ar是G的生成元当且

仅当r是小于等于n且与n互质的正整数.

生成元的实例

（1）设G={e,a,…,a11}是12阶循环群，则小于或等于12且与12互素的数是1,5,7,11,由定理可知a，a5，a7和a11是G的生成元.

（2）设G=<

Z9,>

是模9的整数加群，则小于或等于9且与9互素的数是1,2,4,5,7,8.根据定理，G的生成元是1,2,4,5,7和8.

（3）设G=3Z={3z|z∈Z},G上的运算是普通加法.那么G只有两个生成元：

3和3.

循环群的子群

设G=<

是循环群.

（1）设G=<

是循环群，则G的子群仍是循环群.

（2）若G=<

是无限循环群，则G的子群除{e}以外都是无限循环群.

（3）若G=<

是n阶循环群，则对n的每个正因子d，G恰好含有一个d阶子群.

子群的实例

（1）G=<

是1无限循环群，对于自然数m∈N，1的m次幂是m，m生成的子群是mZ，m∈N.即

={0}=0Z

={mz|z∈Z}=mZ，m>

（2）G=<

Z12,>

是12阶循环群.12的正因子是1,2,3,4,6和12，因此G的子群是（an/d）：

1阶子群<

12>

={0}，2阶子群<

={0,6}

3阶子群<

={0,4,8}，4阶子群<

={0,3,6,9}

6阶子群<

={0,2,4,6,8,10}，12阶子群<

=Z12

n元置换的定义

n元置换的表示

置换符号表示

轮换表示

对换表示

k阶轮换与对换

定义设σ是S={1,2,…,n}上的n元置换.若

σ（i1）=i2,σ（i2）=i3,…,σ（ik1）=ik,σ（ik）=i1

且保持S中的其他元素不变，则称σ为S上的k次

轮换，记作（i1i2…ik）.若k=2，称σ为S上的对换.

例如5元置换

分别是5阶和2阶轮换σ=（12345）,τ=（13）,其中τ也叫做对换

n元置换分解为轮换

设S={1,2,…,n}，对于任何S上的n元置换σ，一

定存在着一个有限序列i1,i2,…,ik,k≥1,（可以取

i1=1）使得σ（i1）=i2,σ（i2）=i3,…,σ（ik1）=ik,σ（ik）=i1，

令σ1=（i1i2…ik），它是从σ中分解出来的第一个

轮换.根据函数复合定义可将σ写作σ1σ’，其中σ’

作用于S{i1,i2,…,ik}上的元素.继续对σ’进行类

似的分解.由于S中只有n个元素,经过有限步以

后，必得到σ的轮换分解式

σ=σ1σ2…σt

分解实例

例设S={1,2,…,8},

从σ中分解出来的第一个轮换式（15236）；

第二

个轮换为（4）；

第三个轮换为（78）.σ的轮换表示式

σ=（15236）（4）（78）=（15236）（78）

用同样的方法可以得到τ的分解式

τ=（18342）（567）

在轮换分解式中，1阶轮换可以省略.

n元置换的乘法与求逆

n元置换群及其实例

考虑所有的n元置换构成的集合Sn

Sn关于置换的乘法是封闭的.置换的乘法满足结合

律.恒等置换

（1）是Sn中的单位元.对于任何n元置换

σ∈Sn，逆置换σ1是σ的逆元.这就证明了Sn关

于置换的乘法构成一个群，称为n元对称群.n元对

称群的子群称为n元置换群.

例设S={1,2,3}，3元对称群

S3={

（1）,（12）,（13）,（23）,（123）,（132）}

S3的运算表

（1）（12）（13）（23）（123）（132）

（1）

（12）

（13）

（23）

（123）

（132）

（12）

（1）（123）（132）（13）（23）

（13）（132）

（1）（123）（23）（12）

（23）（123）（132）

（1）（12）（13）

（123）（23）（12）（13）（132）

（1）

（132）（13）（23）（12）

（1）（123）

S3的子群

S3={

（1）,（12）,（13）,（23）,（123）,（132）}，

A3=<

（123）>

（1）,（123）,（132）}，

（1）>

（1）}

（12）>

（1）,（12）},

（13）>

（1）,（13）},

（23）>

（1）,（23）}

6.2环与域

环的定义与实例

特殊的环

交换环

含幺环

无零因子环

整环

域

环的定义

R,+,·

是代数系统，+和·

是二元运算.

如果满足以下条件:

（1）<

构成交换群

（2）<

R,·

构成半群

（3）·

运算关于+运算适合分配律

则称<

是一个环.

环中的术语

通常称+运算为环中的加法，·

运算为环中的乘法.

环中加法幺元记作0.

乘法幺元（如果存在）记作1.

环中加法幺元0恰好是乘法的零元.

对任何元素x，称x的加法逆元为负元，记作x.

若x存在乘法逆元的话，则称之为逆元，记作x1.

环的实例

（1）整数集、有理数集、实数集和复数集关于普

通的加法和乘法构成环，分别称为整数环Z，有

理数环Q，实数环R和复数环C.

（2）n（n≥2）阶实矩阵的集合Mn（R）关于矩阵的加

法和乘法构成环，称为n阶实矩阵环.

（3）集合的幂集P（B）关于集合的对称差运算和

交运算构成环.

（4）设Zn＝{0,1,...,n－1}，和分别表示模n的

加法和乘法，则<

Zn,,>

构成环，称为模n的整

数环.

是环，

（1）若环中乘法·

适合交换律，则称R是交换环.

（2）若环中乘法·

存在幺元，则称R是含幺环.

（3）若a,b∈R，ab=0a=0∨b=0，则称R是无零因子环.

（4）若R既是交换环、含幺环，也是无零因子环，则称R是整环.

（5）若R为整环，|R|>

1,且aR*=R-{0}，a-1R,则称R为域.

零因子的定义与存在条件

特殊环的实例

（1）整数环Z、有理数环Q、实数环R、复数环C都是交换环、含幺环、无零因子环和整环.其中除Z之外都是域

（2）令2Z={2z|z∈Z}，则<

2Z,+,·

构成交换环和无零因子环.但不是含幺环和整环.

（3）设nZ,n2,则n阶实矩阵的集合Mn（R）关于矩阵加法和乘法构成环，它是含幺环，但不是交换环和无零因子环，也不是整环.

Z6,,>

构成环，它是交换环、含幺环，但不是无零因子环和整环.

对于一般的n,Zn是整环且是域n是素数.

例题

判断下列集合和给定运算是否构成环、整环和域.

（1）A={a+bi|a,bQ},i2=1,运算为复数加法和乘法.

（2）A={2z+1|zZ},运算为普通加法和乘法

（3）A={2z|zZ},运算为普通加法和乘法

（4）A={x|x≥0∧xZ},运算为普通加法和乘法.

（5），运算为普通加法和乘法

环的性质

定理设<

是环，则

（1）a∈R，a·

0=0·

a=0

（2）a,b∈R，（a）b=a（b）=ab

（3）a,b∈R，（a）（b）=ab

（4）a,b,c∈R，a（bc）=abac，

（bc）a=baca

环中的运算

环中加法的交换律、结合律；

乘法的结合律；

乘法对加法的分配律.

例在环中计算（a+b）3,（ab）2

解（a+b）3=（a+b）（a+b）（a+b）

=（a2+ba+ab+b2）（a+b）

=a3+ba2+aba+b2a+a2b+bab+ab2+b3

（ab）2=（ab）（ab）=a2baab+b2

注：

在初等代数中的加法和乘法运算都是在实数域中进行，乘法可交换

6.3格与布尔代数

格的定义与实例

格的性质

对偶原理

交换律、结合律、幂等律、吸收律

格的等价定义

子格

格的同构

特殊的格：

分配格、有界格、有补格、布尔格

格的定义

S,≼>

是偏序集，如果x,y≼S，{x,y}都有

最小上界和最大下界，则称S关于偏序≼构成一个格。

由于最小上界和最大下界的惟一性，可以把求{x,y}

的最小上界和最大下界看成x与y的二元运算∨和

∧，即x∨y和x∧y分别表示x与y的最小上界和

最大下界.

这里出现的∨和∧符号只代表格中的运算，

而不再有其他的含义.

格的实例

例设n是正整数，Sn是n的正因子的集合.D为

整除关系，则偏序集<

Sn,D>

构成格.x,y∈Sn，

x∨y是lcm（x,y），即x与y的最小公倍数.x∧y

是gcd（x,y），即x与y的最大公约数.

下图给出了格<

S8,D>

，<

S6,D>

S30,D>

格的实例

例判断下列偏序集是否构成格，并说明理由.

（1）<

P（B）,>

，其中P（B）是集合B的幂集.

（2）<

Z,≤>

，其中Z是整数集，≤为小于等于关系.

（3）偏序集的哈斯图分别在下图给出.

格的性质：

对偶原理

定义设f是含有格中元素以及符号=,≼,≽,∨和∧的

命题.令f*是将f中的≼替换成≽,≽替换成≼,∨替换成

∧,∧替换成∨所得到的命题.称f*为f的对偶命题.

例如,在格中：

f是（a∨b）∧c≼c,f*是（a∧b）∨c≽c.

格的对偶原理：

设f是含格中元素以及符号=,≼,≽,∨

和∧等的命题.若f对一切格为真,则f的对偶命题

f*也对一切格为真.

例如,若对一切格L都有a,b∈L,a∧b≼a，那么对一

切格L都有a,b∈L,a∨b≽a

算律

L,≼>

是格,则运算∨和∧适合交换律、结

合律、幂等律和吸收律,即

（1）a,b∈L有

a∨b=b∨a,a∧b=b∧a

（2）a,b,c∈L有

（a∨b）∨c=a∨（b∨c）,

（a∧b）∧c=a∧（b∧c）

（3）a∈L有

a∨a=a,a∧a=a

（4）a,b∈L有

a∨（a∧b）=a,a∧（a∨b）=a

算律的证明

证

（1）交换律.

a∨b是{a,b}的最小上界

b∨a是{b,a}的最小上界

{a,b}={b,a}

a∨b=b∨a.

由对偶原理,a∧b=b∧a得证.

算律的证明

（2）结合律.由最小上界的定义有

（a∨b）∨c≽a∨b≽a（I）

（a∨b）∨c≽a∨b≽b（II）

（a∨b）∨c≽c（III）

由式（II）和（III）有

（a∨b）∨c≽b∨c（IV）

由式（I）和（IV）有（a∨b）∨c≽a∨（b∨c）.同理可证

（a∨b）∨c≼a∨（b∨c）.根据偏序的反对称性得到

（a∨b）∨c=a∨（b∨c）.由对偶原理,（a∧b）∧c=

a∧（b∧c）得证.

（3）幂等律.显然a≼a∨a,又由a≼a得a∨a≼a.

由反对称性a∨a=a.用对偶原理,a∧a=a得证.

（4）吸收律.显然有

a∨（a∧b）≽a（V）

由a≼a,a∧b≼a可得

a∨（a∧b）≼a（VI）

由式（V）和（VI）可得a∨（a∧b）=a

根据对偶原理,a∧（a∨b）=a得证.

格作为代数系统的定义

S,∗,∘>

是具有两个二元运算的代数系统,

若对于∗和运算适合交换律、结合律、吸收律,则

可以适当定义S中的偏序≼,使得<

构成格,且

a,b∈S有a∧b=a∗b,a∨b=a∘b.

根据定理,可以给出格的另一个等价定义.

S,∗,∘>

是代数系统,∗和∘是二元运算,如果

∗和∘运算满足交换律、结合律和吸收律,则<

构成格.

子格的定义及判别

L,∧,∨>

是格,S是L的非空子集,若S

关于L中运算∧和∨

展开阅读全文

《离散数学》第六章 几个典型的代数系统 讲稿Word格式文档下载.docx

《离散数学》第六章几个典型的代数系统讲稿Word格式文档下载.docx