离散数学第5章 代数系统

本文格式为Word版，下载可任意编辑——离散数学第5章代数系统

软件学院

第五章代数系统基础以前学过大量代数：初等代数、高等代数(线性代数)、集合代数、命题代数等等它们研究的对象分别是整数、有理数、实数、矩阵、集合、命题等等，以及这些对象上的各种运算。我们发现不同对象上的运算，可能有共同的性质。例如，集合代数与命题代数，尽管研究的对象不同，但是它们的性质完全一样，都有对合律、交换律、结合律、分派律、吸收律、底-摩根定律、同一律、零律、互补律等。这些促使我们将代数的研究引导到更高的层次—即抛开具体对象的代数—抽象代数—研究代数的共性。

软件学院

代数系统基础就专业知识而言，计算机学科中要培养学生三个能力：理论抽象设计理论：就是计算机科学中各种理论课。抽象：要把实际问题抽象成数学模型(数学系统)。设计：系统设计、程序设计。确定数学模型，需要了解有哪些代数结构(系统)。

另外，抽象代数可以培养学生的抽象规律思维能力。本章主要探讨：代数结构(系统)的概念，运算的性质、代数结构(系统)的同构、半群、独异点、群、环、域等。

软件学院

代数系统基础代数系统的定义：X是非空集合，X上的m个运算f1,f2,…fm,构成代数系统U,记作U=X,f1,f2,…fm。定义：假使两个代数系统有一致个数的运算符，每个相对应的运算符有一致的元数，则这两个代数系统具有一致的类型。例如：代数系统(N,+)与代数系统(I,)是相同类型的，由于它们都有一个二元运算符。而代数系统(I,+,)和代数系统(N,+)是不同类型的。

软件学院

代数系统基础

定义：假使两个代数系统(S,)和(S’,*)若满足以下条件：

1.S’S2.a∈S’,b∈S’则a*b=ab

则(S’,*)称为(S,)的子代数或子系统。

例如(N,+)就是(I,+)的子系统。

软件学院

代数系统的性质这一节是重要的一节。由于就是根据运算的性质将代数系统分成半群、群、交换群、环、域、格等，这些性质多数是大家所熟悉的。一.封闭性设是X上的二元运算，假使对任何x,y∈X,有xy∈X,则称在X上封闭。

例如：在N上加法+和乘法都封闭，而减法和除法不封闭。但(I,-)是封闭的，(Q,)封闭。从运算表可以很简单看出运算是否封闭。

软件学院

代数系统的性质二.交换性设是X上的二元运算，假使对任何x,y∈X,有xy=yx,则称是可交换的。

易知:加法、乘法、交、并、对称差是可交换。例如(N,+)中’+’是可交换的(N,)中’’可交换的，但减法和除法不可交换(E,∪)和(E,∩)的运算

是可交换的

(E,-)集合的差运算不可交换

软件学院

三.幂等元、幂等性设是X上的二元运算，假使有a∈X,aa=a,则称a是幂等元，假使对任何x∈X,都有xx=x,则称有幂等性。例如(E,∪)的运算有幂等性

但是(E,-)的运算没有幂等性

软件学院

代数系统的性质四.单位元

设是X上的二元运算，假使有1L∈X,使对任何x∈X,有1Lx=x,则称1L是相对的左单位元。假使有1R∈X,使得对任何x∈X,有x1R=x,则称1R是相对的右单位元。假使对任何x∈X,有1x=x1=x,称1是相对的单位元。此时符号1〞已经不是自然数1的含义。性质：假使对于一种运算存在左单位元和右单位元，则1L=1R。

软件学院

代数系统的性质五.零元

设是X上二元运算，假使有0L∈X,使得对任何x∈X,有0Lx=0L,则称0L是相对的左零元。假使有0R∈X,使得对任何x∈X,有x0R=0R,则称0R是相对的右零元。假使对任何x∈X,有0x=x0=0,称0是相对的零元。例如：对乘法,零元是0,对并运算∪,零元是全集E,对交运算∩,零元是Φ

软件学院

代数系统的性质六.可结合性设是X上的二元运算，假使对任何x,y,z∈X,有(xy)z=x(yz),则称是可结合的。可结合的：数值的加法、乘法，集合的交、并、对称差，关系的复合、函数的复合。是可结合的运算的，元素x的运算，寻常可以写成乘幂的形式。如下：xx=x2x2x=xx2=x3xmxn=xm+n(xm)n=xmn

软件学院

代数系统的性质七.逆元

设是X上有单位元的二元运算，x∈X,若xL-1∈X,使得，xL-1x=1,则称xL-1是x相对的左逆元。假使有xR-1∈X,使得xxR-1=1,则称xR-1是x对的右逆元。若xL-1=xR-1=x-1,有x-1x=xx-1=1,称x-1是x相对的逆元。也称x-1与x互为逆元。如x1∈X,也称x可逆。例：实数集合R上的+和,x∈R对加+:x-1=-x(1=0)

对乘:

x-1=1/x(x≠0)

(1=1)

软件学院

代数系统的性质任一代数系统元素的左逆元与右逆元不一定相等。性质.设是X上有单位元且可结合的二元运算，假使x∈X,x的左、右逆元都存在，则x的左、右逆元必相等。且x的逆元是唯一的。八.可消去性设是X上的二元运算，a∈X,假使对任何x,y∈X,有ax=ay或者xa=yax=y.则称a相对是可消去的。

如数的加法、乘法、减法和除法运算都是可削去的。

软件学院

代数系统的性质

九.分派律设和都是X上的二元运算，若对任何x,y,z∈X,有

x(yz)=(xy)(xz)或(xy)z=(xz)(yz)则称对可分派。例如乘法对加法可分派。集合的∪与∩相互可分派。

软件学院

代数系统的

性质

十.吸收律设和都是X上的二元运算，若对任何x,y∈X,有

x(xy)=x则与满足吸收律。

和

x(xy)=x

例如

集合的∪与∩满足吸收律。

软件学院

a)

b)ccab

c)cccc

d)cccc

aaabbcc

bbca

aaabbcc

bbac

aaabaca

bbbb

aaabbcc

bbbc

cccb

a)b)c)d)

交换性幂等元幂等性单位元有零元有可逆元素YaNaNa,b,cYa,cNaca,bNa,b,cYN,左1N,右零NYa,bNaNa

软件学院

同态与同构

有些代数系统表面上看起来不一致，但是实际上是‘一致’的，如下两个代数系统：01

001

111

*ab

aab

bbb

细心观测可发现，两个代数系统中的对应现象类似，若将其次个代数系统中元素a,b换成第一个代数系统中元素0、1,运算表的形式是不改变，为了表示代数系统之间的这种关系，我们提出同态的概念。

软件学院

同态与同构设X,,Y,是两个代数系统，和都是二元运算，

假使存在映射f:XY,使得对任何x1,x2∈X,有f(x1x2)=f(x1)f(x2)此式叫同态关系式则称f是从X,到Y,的同态映射，简称这两个代数

系统同态。并称f(X),为X,的同态像。假使f是满射的，称此同态f是满同态。假使f是单射的，称此同态f是单同态。假使f是双射的，称X,与Y,同构，记作(X,)≌(Y,)。f是X,到X,的同态(同构),称之为自同态(自构)。

软件学院

同态与同构例1.R+,:是正实数R+上的乘法;R,+:是实数R上的加法+。表面上看这两个代数系统完全不同，实际它们运算的性质却完全一样，都满足：可交换、可结合、有单位元、元素可逆。那如何反映它们的一致性呢？通过一个映射f:R+R任何x∈R+,f(x)=lnx(是双射)任何x,y∈R+,f(xy)=ln(xy)=lnx+lny=f(x)+f(y)

软件学院

同构与同态

例2.设S={4,5,6},在S上的二元运算可用下表1定义。又有P上的二元运算*,其运算组合如表2,这样所构成的两个代数系统(S,)与(P,*)是同构的。456444455556456*123112231

11

22

23

软件学院

同构和同态

证明：这两个代数系统间存在一个函数g:Sg(a)=a-3显然它是一一对应的，同时它满足条件：g(ab)=g(a)*g(b)

P,