离散数学第5章 代数系统

软件学院

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

软件学院

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

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

软件学院

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

软件学院

代数系统基础

定义：如果两个代数系统(S, )和(S’, *)若满 足下列条件：

1. S’ S 2. a∈S’ ,b∈S’ 则a*b=a b

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

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

软件学院

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

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

软件学院

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

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

是可交换的

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

软件学院

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

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

软件学院

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

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

软件学院

代数系统的性质 五. 零元

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

软件学院

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

软件学院

代数系统的性质 七.逆元

设 是X上有单位元的二元运算，x∈X,若xL-1∈X, 使得，xL-1 x=1,则称xL-1是x相对 的左逆元。如果有xR-1∈X,使得x xR -1 =1,则称xR -1是x对 的右逆元。 若xL-1 = xR-1 =x-1 ,有x-1 x=x x-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, 有a x=a y或者x a=y a x=y.则称 a相对 是可消去的。

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

软件学院

代数系统的性质

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

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

软件学院

代数系统的

性质

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

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

和

x (x y)=x

例如

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

软件学院

a)

b)c c a b

c)c c c c

d)c c c c

a a a b b c c

b b c a

a a a b b c c

b b a c

a a a b a c a

b b b b

a a a b b c c

b b b c

c c c b

a) b) c) d)

交换性 幂等元 幂等性 单位元 有零元 有可逆元素 Y a N a N a,b,c Y a,c N a c a,b N a,b,c Y N,左1 N,右零 N Y a,b N a N a

软件学院

同态与同构

有些代数系统表面上看起来不相同，但是实际上是 ‘相同’的，如下两个代数系统： 0 1

00 1

11 1

* a b

aa b

bb b

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

软件学院

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

如果存在映射f:X Y,使得对任何x1 ,x2∈X,有f(x1 x2)=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(x×y)=ln(x×y)=lnx+lny=f(x)+f(y)

软件学院

同构与同态

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

11

22

23

软件学院

同构和同态

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

P,

故这两个代数系统是同构的。 同构不但使两个代数系统具有相同的基数，而且 对运算保持相同的性质。

软件学院

注意：代数系统<X, > 和<Y, >同构的必要条件：1.X和Y的基数相同，即K[X]=K[Y]。

2. 运算 和 是同类型的。3.存在双射 f:X Y,且满足同构关系式。 f(x1 x2)=f(x1) f(x2) 因为并不是所有双射都满足同构关系式。

本文来源：https://www.bwwdw.com/article/rce1.html