当前位置：文档之家 › 《离散数学》第5章 代数系统简介

《离散数学》第5章 代数系统简介

  • 格式：ppt
  • 大小：2.11 MB
  • 文档页数：88

下载文档原格式

  / 88

合集下载

《离散数学》代数系统的一般性质-1

《离散数学》代数系统的一般性质-1


定义 设 S 为集合,函数 f：S×S→S 称为 S 上的 二元运算, 简称为二元运算. 也称 S 对 f 封闭. 特点： - 变量和函数值的取值限定在同一个集合上。 例1 - (1) N 上的二元运算：加法、乘法. - (2) Z 上的二元运算：加法、减法、乘法. - (3) 非零实数集 R* 上的二元运算: 乘法、除 法. - (4) 设 S = { a1, a2, … , an}, ai ∘aj = ai ， ∘ 为 S 上二元运算.

二元运算的特异元素 5.1 二 元 运 算 及 其 性 质 单位元
定义 设∘为S上的二元运算,如果存在el（或er）S，使得 对任意x∈S 都有 el ∘x =x (或x∘er =x)， 则称el(或er )是S中关于∘运算的左(或右)幺元（单位元）. 若e∈S关于∘运算既是左单位元又是右单位元，则称 e 为S上关于∘运算的幺元. 例：N上加法的幺元是0，乘法的幺元是1 Mn(R)上加法的么元是0矩阵，乘法的幺元是单位阵
第5章 代数系统的一般 性质
代数结构
【引例】 （1）在Z集合上，x∈Z,
5.1 二 元 运 算 及 其 性 质
则f(x)=-x是将x映为它的相反 数。-x是由x唯一确定的，它是对一个数施行求相反数运 算的结果。这个运算可表示为函数： f ：Z→Z
（2）在R+ 集合上，x∈R+,则f(x)= 1/x是将x映为它的倒 数。1/x是由x唯一确定的，它是对R+中的一个数施行倒数 运算的结果。这个元算可以表示为函数 f : R+ → R+。 （3）设a,b∈R,则f(a,b)=a+b(a-b，a×b)是将两个数a， b映为R中的唯一的一个数，它是对R中的两个数施行加 （减，乘）法运算的结果。这个运算可以表示为函数f : R2 → R。
离散数学第五章

离散数学第五章


作业：P178 (2)；P185 (1), (2)
5.3 半群和独异点
一、半群
1、定义
①具有运算封闭性的代数系统A=〈s，*〉 称为 广群，满足运算封闭、结合律的代数 系统 A=＜s，*＞，称为半群，这里*是二 元运算。 ②存在么元的半群称为独异点，也称含么 半群， 单位半群，单元半群。
5.3 半群和独异点
二、么元（单位元）和零元
例：代数A=〈{a，b，c}， ○ 〉用下表定义： ○ a b c 特殊元: b是左么元，无右么元; a是右零元，b是右零元， 无左零元; 运算:既不满足结合律，也不满足交换律。 a a a a b b b b c b c a
二、么元（单位元）和零元
例: a）〈I，x〉， I为整数集
5.2 运算及其性质
5.吸收律：设<A，*，△>，若x，y，z∈A有: x*(x △z)=x 称运算*满足吸收律; x △(x * y) =x； 运算 △满足吸收律
例:N为自然数集,x,y∈N，x*y=max{x，y},
x△y=min{x，y}
试证：*，△满足吸收律 证明：x，y∈N， x*（x△y）=max{x，min{x，y}}=x ∴*满足吸收律 x x≥y x<y x≥y =x =x
则么元为1，零元为0
b）〈（s）,∪,∩〉 对运算∪，是么元， s是零元，
对运算∩，s是么元 ，是零元。 c）〈N，+〉 有么元0，无零元。
二、么元（单位元）和零元
2、性质
性质1: 设*是s上的二元运算，满足结合律，具 有左么元el，右么元er，则el=er=e 证明： er = el* er = e
闭否，<A，+>，<A，/>呢？ 解：2r，2s∈A， 2r x 2s=2r+s∈A （r+s∈Ｎ）
《离散数学》第五章

《离散数学》第五章


⊕4b）⊕4c=
a
c)， 满足结合律。 ⊕4(b ⊕4c)，即⊕4满足结合律。
0是单位元，0的逆元是 ，1和3互为逆元，2的逆 是单位元， 的逆元是 的逆元是0， 和 互为逆元 互为逆元， 的逆 是单位元 元是2。 是一个群。 元是 。 <Z4； 4>是一个群。 ⊕ 是一个群
14
定义5-8:如果群 如果群<G; * >的运算 是可交换的，则称该群为 的运算*是可交换的 定义 的运算 是可交换的，
5
三、 子半群和子独异点
定义5-5 定义
<S； >的子代数，则称<T； >是<S； >的子半群。 ； 的子代数，则称 ； 是 ； 的子半群。 的子代数 的子半群
∗
设<S； >是一个半群 ，若 <T； ； 是一个半群 ； ∗
∗
例6
= {2n | n ∈ N} N3 = {3n | n ∈ N}, N4 = {4n | n ∈ N}, L
交换群或阿贝尔群。 交换群或阿贝尔群。
15
二、循环群
1．群中元素的幂 对于任意a∈ ， 对于任意 ∈G， a0=e,
anƮ=e, ( a−1)n+1 = (a−1)n ∗ a−1 (n=0,1,2,…) （*） ） 引进记号 a−n = (a−1)n = a−1 ∗ a−1 ∗ ⋅ ⋅ ⋅ ∗ a−1 ( n个a-1 ) 个 因此（ 因此（ ）式可表示为 (a −1 )0 = e, a−n−1 = a−n * a−1 对于任意整数
1
5.1 半群和独异点 一、半群 半群 定义5-1 定义
二元运算， 二元运算，如果 是半群。 是半群。∗ > < s; 是一个非空集合， 设S是一个非空集合， 是S上的一个 是一个非空集合 上的一个 是可 结 合 的 , 则 称 代 数 系 统
math-chap5-5.离散数学_代数系统

math-chap5-5.离散数学_代数系统


庄伯金 bjzhuang@
14
同态与同构

定义：设两代数系统V1=<A,*>和V2=<B,•>，如果 存在映射f:A→B，对任意的x,y∈A，有 f(x*y)=f(x)•f(y)，则称f是V1到V2的同态映射，简 称同态，记为<A,*>∼<B,•>。

若f为满射，则称f为满同态； 若f为单射，则称f为单一同态； 若f为双射，则称f为同构，记作<A,*>≌<B,•>。
庄伯金 bjzhuang@
12
子代数系统

定义：设有代数系统<A,*1,*2,...,*k>，B是A的非 空子集。如果A上的每个运算都在B上是封闭的，且A 与B含有相同的代数常数，则称代数系统 <B,*1,*2,...,*k>为代数系统<A,*1,*2,...,*k>的 子代数系统，或称代数B为代数A的子代数。
庄伯金 bjzhuang@
10
逆元

定理：设•为A上的可结合二元运算，A中存在幺元e 且每个元素都有左逆元，则在A中，每个元素的左逆 元也是该元素的右逆元，且每个元素的逆元唯一。
庄伯金 bjzhuang@
11
代数系统


定义：由非空集合A以及A上的运算*1,*2,...,*n所组 成的系统称为一个代数系统，记作 <A,*1,*2,...,*n>。 定义：如果两个代数系统中运算的个数相同，对应运 算的元数也相同，且代数常数的个数也相同，则称这 两个代数系统具有相同的构成成分，也称它们是同类 型的代数系统。
庄伯金 bjzhuang@
6
单位元


离散数学第五章 代数系统基础

离散数学第五章 代数系统基础


第五章 代数系统基础
第五章 代数系统基础
6、逆元 、 是集合A上具有单位元 的二元运算， 设 * 是集合 上具有单位元 e 的二元运算，对于元 ， 素 a ∈ A，若 ∃一个元素 a l -1∈A，使得 a l -1* a = e ， ， 则称元素a 是左可逆的， 则称元素 对于运算 * 是左可逆的，并称 a l -1为 a 的 左逆元； 左逆元；若 ∃一个元素 a r -1∈A，使得 a * a r -1 = e ， ， 则称元素a 对于运算 * 是右可逆的，并称 r -1为a的 是右可逆的，并称a 则称元素 的 右逆元； 右逆元；若 ∃一个元素 a -1∈A ，使得 a -1* a = a * a -1 = e ，则称元素 a 对于运算 * 是可逆的，并称 -1为 a 是可逆的，并称a 的逆元。 的逆元。 显然， 的逆元， 也为a 显然，若a -1为 a 的逆元，则 a 也为 -1的逆元
第五章 代数系统基础
例7：代数系统 (ρ( E), ∼) 与 (ρ( E),∪) 的类型不相同。 ： ∪ 的类型不相同。
第五章 代数系统基础
3、子系统（或子代数） 、子系统（或子代数） 定义： 定义：设 ( S ,
1
,
2
,⋯ ,
i
n
) 是代数系统， 是代数系统，
S ′ 是 S 的在每一运算
下 ( i = 1, 2, …，n ) ，
上述运算为 °( (x, y) ) = x · y (mod3)，其中 · 是普通乘法 ，
第五章 代数系统基础
A={0, 1}, 二元运算 * 的定义见下表。 的定义见下表。 * 0 1 0 0 0 1 0 1
上述运算*是集合 ， 上的逻辑合取运算 上述运算 是集合{0，1}上的逻辑合取运算 是集合
离散数学第5章 代数系统

离散数学第5章 代数系统


代数系统的性质
十.吸收律
设和 都是X上的二元运算，若对任何x,y∈X， 有
x(xy)=x
则与 满足吸收律。
和
x(xy)=x
例如
Hale Waihona Puke 集合的∪与∩满足吸收律。软件学院
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
软件学院
代数系统基础
就专业知识而言，计算机学科中要培养学生三个能力： 理论抽象设计 理论：就是计算机科学中各种理论课。 抽象：要把实际问题抽象成数学模型(数学系统)。 设计：系统设计、程序设计。 确定数学模型，需要了解有哪些代数结构(系统)。
另外，抽象代数可以培养学生的抽象逻辑思维能力。
本章主要讨论：代数结构(系统)的概念，运算的性质、代数 结构(系统)的同构、半群、独异点、群、环、域等。
软件学院
同态与同构
设<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,>的同态(同构),称之为自同态(自构)。
离散数学 第五章 格与布尔代数

离散数学 第五章 格与布尔代数


由于这里的*和⊕就是上面格中的*运算和⊕运算，故有
a*b=glb{a,b}= GLB{a,b} a⊕b=lub{a,b}= LUB{a,b}
下面证明半序关系≤等于半序关系≤’。 1）若a≤b，则有GLB{a,b}=a ，又因为a*b=GLB{a,b}， 故有a*b=a，即a≤’b，由(a,b) 的任意性知≤ ≤’。 2）若a≤’b，则有a*b=a ，又因为a*b=GLB{a,b}，故有 a=GLB{a,b}，由下确界的定义知有a≤b，由(a,b)的任意性知 ≤’ ≤。
例2. 设I是整数集合， a,b∈I， 定义运算*和⊕如下： a*b=min{a,b} a⊕b=max{a,b} 则<I, *,⊕>是代数系统。 1）由于 a∈I, a*a=min{a,a}=a a⊕a=max{a,a}=a
故由定义1知，*和⊕运算均满足幂等律。 2）任取a,b∈I，由于有
a*(a⊕b)=min{a,max{a,b}}=a
由集合相等的定义知≤’=≤，即≤和≤’是同一个半序关 系。
由此可知，格与任意两个元素有上、下确界的半序集 是等价的，即格就是格。于是得到 格的另一种等价的定义。
定义3’ 设<L, ≤>是半序集，若L中的任意两个元素有上、 下确界存在，则称<L, ≤>是格。 由于定义3和定义3’的等价性，以后关于格，既可以用 <L,*,⊕>表示，也可以用 表示。当用<L,*,⊕>表示时，半序 关系是用a*b=a或a⊕b=b定义的。当用<L, ≤>表示时，两个运 算是用
故*运算和⊕运算满足结合律。
2）由于 a,b∈I，有 a*b=min{a,b}=min{b,a}=b*a a⊕b=max{a,b}=max{b,a}=b⊕a 故*运算和⊕运算满足交换律。
离散数学 第五章 代数系统

离散数学 第五章 代数系统


5.1 代数系统的基本概念
• 当n = 1时，称f为一元运算，当n = 2时，称f为二元 运算，等等。
• 运算的例子很多。例如，在数理逻辑中，否定是 命题集合上的一元运算，合取和析取是命题集合 上的二元运算；在集合论中，集合的补是集合上 的一元运算，并与交是集合上的二元运算；在实 数算术中，加、减、乘、除运算都是二元运算。
可交换的二元运算，如果对于任意的x，yA，都
有
x*(x⊙y)=x 和 x⊙(x*y)=x
• 即(x)(y)(x，yA→x*(x⊙y)=x∧x⊙(x*y)=x),则称 运算*和运算⊙满足吸收律，或称*对于⊙以及⊙ 对于*是可吸收的。
5.2 运算及其性质
• 例5.9 给定<N，*，⊙>，其中N是自然数集合，* 和⊙定义如下： 对任意a，bN有a*b = max(a，b)，a⊙b = min(a， b)，试证，*和⊙互为吸收的。
1*(0⊙1)=1*0=1，而 (1*0) ⊙(1*1)=1⊙0=0
5.2 运算及其性质
• 形如表5-3的表常常称为运算表或复合表，它由运 算符、行表头元素、列表头元素及复合元素四部 分组成。对于集合的基数很小，特别是2或3时， 代数系统中运算常常用这种表给出。优点是简明 直观，一目了然。
• 性质5：吸收律 设*，⊙是定义在集合A上的两个
（1）x+yZ，
（封闭性）
（2）x+y=y+x
（交换律）
（3）(x+y)+z=x+(y+z)
（结合律）
• 容易找到与<Z，+>具有相同运算规律的一些代数 系统，如表5-2所示。
5.1 代数系统的基本概念
集合
离散数学 第五-六章

离散数学 第五-六章

例如 实数集上对+可分配,但+ 对不可分配; 集合上的运算, ;,命题集合P上的,都是相互可分配
例 题4
设集合A={ ,}, A上定义的二元运算如表所示. 对*可分配吗? * 对 ?
代数结构 >运算性质
定义5-2.6 设,△是定义在集合A上的两个二元运 算,如果对 x y∈A,都有 x (x△y) = x x△(x y) =x 则称运算和运算△满足吸收律。
代数系统 >代数系统的引入
二元运算的例子 • N上 +, 是N上二元运算,而-, 不是. • 整数集I上 +,-, 是I上的二元运算, 而 不是. • R-{0}上的 , 是R-{0}上的二元运算,而+,-不是. • 矩阵的 +, 是N阶实矩阵集合上的二元运算,但不是 全体实矩阵集合上的二元运算. • ,,, 是真值集合{0,1}上 的二元运算. • ,, 是幂集P(A)上的二元运算. 一元运算的例子 • R上的 求绝对值|X|运算. • 整数 I上求负运算是一元运算,但不是N上的一元运算.
n 例如 实数集上的+, ; 集合上的运算, ;,命题 集合P上的,都是可结合的.
例题3
A为非空集合,*定义为:对任意的a,bA,有 a*b=b. 证*可结合的.
代数结构 >运算性质
定义5-2.4 设是定义在集合A上的一个二元运算, x∈A,若xx=x,称x是等幂元; 若对x∈A,都有
2 独异点(monoid)
定义5-3.3 含有幺元的半群称为独异点。 独异点的判定: 对给定集合S 及运算*, 1)是封闭的, 即对x,y∈S, 有 xy∈S (是代数系统) 2)是可结合的,即对x,y,z∈S, 有(x y) z= x (y z) 3) 有幺元,即e∈S, 对x∈S,有ex=xe=x. 例如 <R, +>是独异点,幺元为0, <I+,+ >不是. <R, * >, <I, * >都是独异点,幺元为1 <{0,1}, > , <{0,1}, >都是独异点,幺元分别为0和1. < P(S), >和 < P(S), >是独异点?
离散数学第5章代数系统(学生用)

离散数学第5章代数系统(学生用)


运算的分类
一元运算
只对一个元素进行操作的 运算。
二元运算
对两个元素进行操作的运 算。
n元运算
对n个元素进行操作的运算。
运算的实例
加法
是二元运算，满足结合性和交换性，不满足 幂等性和消去性。
指数运算
是二元运算，满足结合性和交换性，不满足 幂等性和消去性。
乘法
是二元运算，满足结合性和交换性，满足幂 等性和消去性。
离散数学第5章代数系统( 学生用)
• 代数系统的基本概念 • 代数系统的运算 • 代数系统的同态与同构 • 代数系统的子代数与商代数 • 代数系统的应用
01
代数系统的基本概念
定义与性质
定义
代数系统是一个有序的三元组 (A,F,D)，其中A是一个非空集合， F是A上的一组二元运算，D是A上 的一组一元运算。
同构实例
例如，矩阵代数中的矩阵集合M与向量空间中的向量集合V之间存在一个一一对应的映射f，使得M中的每一个元 素x经过f的映射后，都对应于V中的某个元素y，并且M中的加法、数乘和乘法运算也对应于V中的加法、数乘和 外积运算，因此M与V同构。
04
代数系统的子代数与商代数
子代数与商代数的定义
子代数
如果代数系统的一个非空子集在给定的运算下仍然是一个代 数系统，则称这个子集为原代数系统的子代数。
同构性质
同构关系具有自反性、对称性和传递性，即如果A同构于B，那么B一定同构于A；如 果A同构于B，B同构于C，那么A一定同构于C。
同态与同构的实例
同态实例
例如，整数集合Z与有理数集合Q之间存在一个一一对应的映射f，使得Z中的每一个元素x经过f的映射后，都对应 于Q中的某个元素y，并且Z中的加法运算也对应于Q中的加法运算，因此Z与Q同态。
《离散数学》第5章 代数系统简介

《离散数学》第5章 代数系统简介

x ( x) 0, ( x) x 0 .
在 M n (R) 上，对于矩阵乘法只有可逆矩阵 M M n (R) 存在逆元
M 1 ， M M 1 E 和 M 1 M E 成立， 使得 其中 E 为 n 阶 单位矩阵.
9、设 为 S 上的二元运算，如果对任意的 x, y, z S 满足以下条件 （1）若 x y x z 且 x 不是零元，则 y z ， （2）若 y x z x 且 x 不是零元，则 y z ， 就称运算 满足消去律
例如: 在幂集 P ( S ) 上的 和 是满足吸收律的.
若 算“”满足左分配律； b c a b a c a ， 则运算“ ”对运算“ ”满足右分配律.若左右分配律 均满足， 称运算“ ”对运算“ ”满足分配律. 则

5、 设 是 A 上的二元运算，若存在 a A ，有
1、若 a b b a ，则称运算“ ”在A上是可换的 ，或 者说运算“ ”满足交换律.
例如：在实数集R上，通常的加法和乘法都满足交换律，但减法 和除法不满足交换律.因为2和4都是实数.因为2-4≠4-2.在幂集 P(S)上 , , 都满足交换律，但相对补不满足交换律.
2、若a b c a b c，则称运算“*”在A上是可结合 的.或称“*”满足结合律.
这些相当于前缀表示法，但对二元运算用得较多的还是 a1 a2 b .我们在本书中所涉及的代数运算仅限于一元. 和二元运算．
如果集合Ｓ是有穷集，Ｓ上的一元和二元运算也可以用 运算表给出.表5―1和表5－2是一元和二元运算表的一 般形式.
表5－1
表5－1
例2、(2) 设 S 0,1, 2,3, 4 ，定义 S 上的两个 二元运算如下：

离散数学代数系统总结

离散数学代数系统总结离散数学是数学的一个分支，主要研究离散对象和离散结构。

而代数系统是离散数学的一个重要分支，它研究的是一类具有特定性质的运算集合。

在这篇文章中，我们将从代数系统的基本概念、性质和应用几个方面对离散数学中的代数系统进行总结。

一、代数系统的基本概念代数系统是指一个非空集合A，以及在这个集合上定义的一个或多个运算。

根据运算的性质，代数系统可以分为不同的类型，包括群、环、域等。

其中，群是最基本的代数系统，它具有封闭性、结合律、单位元、逆元等性质。

环则在群的基础上增加了乘法运算，并满足了分配律。

域是环的一种扩充，它除了满足环的性质外，还具有乘法逆元。

二、代数系统的性质1. 封闭性：代数系统中的运算结果仍属于该系统，即对于任意a、b∈A，a运算b的结果仍然属于A。

2. 结合律：对于代数系统中的任意元素a、b、c，(a运算b)运算c 与a运算(b运算c)的结果相同。

3. 单位元：代数系统中存在一个元素e，对于任意元素a，a运算e与e运算a的结果均为a。

4. 逆元：代数系统中的每个元素a都存在一个逆元，使得a运算它的逆元等于单位元。

5. 交换律：对于代数系统中的任意元素a、b，a运算b与b运算a 的结果相同。

这些性质是代数系统的基本特征，不同类型的代数系统在这些性质上有所区别，比如群具有结合律和单位元，但不一定满足交换律。

三、代数系统的应用代数系统在数学及其他学科中有着广泛的应用。

以下是几个代数系统应用的例子：1. 编码理论：代数系统的运算可以用于编码和解码信息，例如循环冗余校验码（CRC）就是通过代数系统中的运算实现数据校验。

2. 密码学：代数系统中的数学运算被广泛应用于密码学中，用于加密和解密信息，保护数据的安全。

3. 图论：代数系统的概念和性质在图论中有着重要的应用，例如邻接矩阵和关联矩阵可以用于描述和分析图的结构和特性。

4. 计算机科学：代数系统在计算机科学中有着广泛的应用，例如布尔代数在逻辑电路设计和逻辑编程中的应用。

离散数学代数结构部分演示精品PPT课件

例5.2 设Q是有理数集合，*是Q上的二元 运算，对任意的a，b∈Q，a*b＝a+ba·b，问运算*是否可交换。
解：因为 a*b＝a+b-a·b＝b+a-b·a＝b*a， 所以运算*是可交换的。
7
5.1节 二元运算及其性质
➢定义5.1 设 S 为集合，函数 f : S S S 称 为 S 上的二元运算，简称为二元运算。
义两个二元运算*和★，对于任意 x，y∈N，有x*y＝max(x，y)， x★y＝min(x，y)，
验证运算*和★满足吸收律。
13
解：对于任意a，b∈N a*(a★b)＝max(a，min(a，b))＝a
a★(a*b)＝min(a，max(a，b))＝a 因此，*和★满足吸收律。
14
5.2节 二元运算中的特殊元素 1. 幺元 ➢定义5.7 设*是S上的二元运算，
23
2. 逆元 ➢定义5.9 设*是S上的二元运算，
24
例5.8 整数集Z上关于加法的幺元是0，对 任意的整数m，它关于加法的逆元是-m, 因为
25
➢定理5.5 设*是S上可结合的二元运算， e为幺元,如果S中元素x存在（关于运 算* ）的逆元， 则必是惟一的。
所以对于可结合的二元运算，逆元是惟一的。
15
➢在自然数集N上加法的幺元是0，乘法 的幺元是1. 对于给定的集合和运算有的存在幺 元，有的不存在幺元。
16
17
➢ 定理5.1 设*是S上的二元运算， 如果S中存在关于运算*的）幺元， 则必是唯一的。
所以幺元是唯一的。
18
➢定理5.2 设*是S上的二元运算，
如果S中既存在关于运算*的左幺元 el ，
2 封闭性 集合S中任意的两个元素运算的结果都是 属于S的，就是说S对该运算是封闭的

《离散数学》代数系统--代数系统的基本概念 ppt课件


解：(1) 封闭、可交换、等幂、幺元是b、无零元
b-1=b a-1=c c-1=a
(2) 封闭、不可交换、无等幂性、幺元是a、
无零元，d是左零元、
a-1=a b-1=b c-1=b b-1=c
23
P184
作业
(1)(2)
24
16
定理2：*是A上的二元运算，且在A中有关于*的左零元l和右零元 r，则l = r = ，且A中零元是唯一的。
证明：(1) r = l * r = l = (2) 设’也是A中关于*的零元，则 * ’= ’ 又∵ 是A中关于*的零元， ∴ * ’= ∴ = ’
定理3：设<A,*>是一个代数系统，且 | A |>1，若<A,*>中存在幺元e 和零元，则e ≠ 。 证明： 假设 = e ，则 对于A中任意元素，有x=e*x= *x= =e 即A中所有元素都是 ，也都是e，所有元素都相同， ∴ | A |=1 与已知矛盾，假设错 ∴e≠
例：代数系统<I,+>满足消去律。
11
代数系统的组成
N元运算法则
如＋、－
×………
特异元素
如×中的1和0
代数载体
(集合：如实数集、整数集)
代数系统
12
4. 代数常元
幺元
定义3：设*是集合A上的二元运算 若elA，对于xA ，都有el*x=x，则称el为A中 关于运算*的左幺元； 若erA，对于xA ，都有x*er=x，则称er为A中 关于运算*的右幺元； 若eA，对于xA ，都有e*x=x*e=x，则称e为A 中关于运算*的幺元。
15
零元
定义4：设*是集合A上的二元运算 若lA，对于xA ，都有l*x=l ，则称l为A中关于运 算*的左零元； 若rA，对于xA ，都有x*r=r ，则称r为A中关于 运算*的右零元； 若A，对于xA ，都有*x=x*=，则称为A中关于 运算*的零元。

离散数学 代数系统


二元运算的性质
定义5.7 设°和∗为S上两个可交换的二元运算， 定义5.7 上两个可交换的二元运算， 上两个可交换的二元运算 如果对于任意的x,y∈ ， 如果对于任意的 ∈S，都有 x∗(x°y)＝x ∗ ° ＝ x°(x∗y)＝x ° ∗ ＝ 则称运算° 满足吸收律 吸收律。 则称运算°和∗满足吸收律。
说 明
不是自然数集合N 不是自然数集合N上的二元运算
验证一个运算是否为集合S上的二元运算主要考虑两点： 验证一个运算是否为集合S上的二元运算主要考虑两点： 不封闭。 对减法不封闭 称N对减法不封闭。 中任何两个元素都可以进行这种运算， S中任何两个元素都可以进行这种运算，且运算的结果 是唯一的。 是唯一的。 中任何两个元素的运算结果都属于S S中任何两个元素的运算结果都属于S，即S对该运算是 封闭的。 封闭的。
ai ∅ {1} {2} {1,2}
~ ai {1,2} {2} {1} ∅
{2} {1,2}
{1,2} {1,2} {2}
例5.5
上的二元运算° 例5.5 设S={1,2,3,4}，定义 上的二元运算°如下 ，定义S上的二元运算 x ° y＝(xy) mod 5， ∀x,y∈S ＝ ， , ∈S
离散数学
第5章 代数系统
本章说明 本章的主要内容
–一元和二元运算定义及其实例 一元和二元运算定义及其实例 –二元运算的性质 二元运算的性质 –代数系统定义及其实例 代数系统定义及其实例 –子代数 子代数
与后面各章的关系
–是后面典型代数系统的基础 是后面典型代数系统的基础
本章内容
5.1 二元运算及其性质 5.2 代数系统 本章小结 作 业
二元与一元运算的算符
可以用° 可以用°、∗、·、⊕、⊗、∆等符号表示二元或一 、 元运算，称为算符 算符。 元运算，称为算符。

离散数学 第五章：2代数系统及其子代数和积代数 3代数系统的同态与同构


0 = 0⋅ n ∈nZ,
6
三. 代数系统的积代数
定义5－ 定义 －14 其中 ∗ 和 设代数系统 V =< S1,∗> 和 1
V2 =< S2 , >
积代数是一个代数系统 都是二元运算 。V和 V2 的积代数是一个代数系统 1
其中 V ×V2 即 V1 ×V2 =< S , ⊕> ,其中 1
S = S1 × S2 ={(x1, y1)| x1 ∈S1, y1 ∈S2} 是二元运算， ⊕是二元运算，定义为对任意的 ( x1, y1 ),( x2 , y2 ) ∈ S
1
, 2 ,⋯,
k
满足B S,则称 则称V >满足B⊂S,则称V’是
5
例1. 设 V =< Z , +,0 >, 令
nZ = {nz z ∈Z} , n 为自然数, 为自然数,
证明: nZ是 的子代数. 证明: nZ是V的子代数. 证明: 证明: 任取nZ中的两个元素 任取nZ中的两个元素nz1, nz2 (z1, z2 ∈Z), 则有
.
11
3个代数系统的积代数: 个代数系统的积代数:
例如 V
=< Z, +,0 >, 那么有
V ×V ×V =< Z × Z × Z,∗, 0,0,0 >, 并且对任意的 < x1, y1, z1 >, < x2 , y2 , z2 >∈Z × Z × Z, 有
< x1, y1, z1 >∗< x2 , y2 , z2 >=< x1 + x2 , y1 + y2 , z1 + z2 >
< Z , +, 0 >
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
b R 都有 b a b ，所以，任意 R 的元素 a 都是
运算 的右幺元. R 中有无数多个右幺元，但是没有 幺元. 例 5.3 代数系统 R, 中，其中 R 为实数， ” “ 是普通乘法，问 1 是它的幺元吗？ 解：代数系统 R, ，其中 R 为实数， ”是普 “ 通乘法， 并且对任意的实数 m R ， m 1 1 m m ， 有
于运算“ ”的零元.
注意：零元的符号“ ”有时候也用“ 0 ”表示， 但“ 0 ”不一定具有自然数 0 的含义，它只是零元的记 号.
例 5.4 代数系统 Z , 中，其中 Z 为整数， ”是 “ 普通乘法，问 0 是它的零元吗？
0 解： Z 且对任意的 m Z ， 均有 m 0 0 m 0 ，
运算的左零元， R 中没有右零元，也没有零元.
定理 5.3 设 为集合 A 上的二元运算， l 和 r 分别为运 算 的左零元和右零元，则有 l r 且 是 A 上关于 运算 的惟一零元. 证明略. 8、设 为集合 A 上的二元运算，且在集合 A 中存在单 位元 e ，对任意的 m A 若存在 yl A ，有 yl m e ，则称 yl 为 m 的左逆元. 若存在 yr A ， m yr e ， 有 则称 yr 为 m 的右逆元. 若存在 y A ，有 m y y m e ，则称 y 为 m 的 逆元.
例如， 在整数集合上加法是满足消去律的.对任意的 整数 x, y , z 由 x y x z或y x z x 可得 y z . 消去了 x .类似地，对乘法也有消去律.但在幂集 P(S ) 上，取 A,, B, C P(S ) ，由 A B A C 不一定能得到
例如: 在幂集 P ( S ) 上的 和 是满足吸收律的.
若 算“”满足左分配律； b c a b a c a ， 则运算“ ”对运算“ ”满足右分配律.若左右分配律 均满足， 称运算“ ”对运算“ ”满足分配律. 则

5、 设 是 A 上的二元运算，若存在 a A ，有
注意：验证一个运算为集合上A的二元运算，要满足 以下两个条件： ⑴ A中的任何元素都可以进行这种运算，且运算 的结果是唯一的. ⑵ A中的任何元素的运算结果都属于A ，即运算 在A上是封闭的.
例1 判断下列几个命题哪些是正确的，哪些是不正确的. (1) 自然数集合N 上的加法，乘法都是二元运算，但减 法，除法不是。 (2) Z 上的加法，乘法，减法都是二元运算， 但除法不 是。Z 上求相反数的运算是一元运算。 (3)A为任意集合，则并、交、差、补为集合A上的幂 集Ｐ(Ｓ) 上的二元运算. (4) M n ( R) 表示所有 n 阶实矩阵的集合(n 2) ，
a a a ，则称 a 是关于运算“ ”的幂等元.如果
对任意的 a A ，都有 a a a ，则称运算“ ”满 足幂等律. 例如， 幂集 P( S ) 上的 和 运算适合幂等律， 但对 称差运算不适合幂等律（除非 P(S ) ）. 定理 5.1 设 是非空集合 A 上的二元运算， m 为 运算 的幂等元，对于任意的正整数 n ，则有
元；若 A 中有一个元素 e ，它既是左幺元又是右幺元， 则称 e 为 A 中关于运算 的幺元. 对于给定的集合和运算有的存在幺元，有的不存在 幺元.例如， R 是非零实数集， 是 R 上的二元运算， 任取 a, b R .对所有的 b R 都有

ab a
，
所以，运算 没有左幺元.但对任意的 a R .对所有的
n个
当n=1时，函数 f 称为集合A上的一个一元运算； 当n=2时，函数 f 称为集合A上的一个二元运算； 二元运算是最常见的代数运算.
f : N N N , f a, b a b 就是自然数 例如: 集合N上的一个二元运算.但普通的减法运算不是N 上的二元运算，因为两个自然数相减可能为负数， 而负数不属于自然数.这时也称集合N对减法不封闭.
所以 0 是代数系统 Z , 的零元.
M n (R) 上矩阵乘法的零元是 n 阶零矩阵，而矩阵加
法没有零元.在幂集 P(S ) 上 运算的零元是 S ， 运算 的 零 元 是 . 在 R 上 如 果 定 义 运 算 ， 使 得 对 任 意
a, b R 满足 a b a ,那么 R 的任何元素都是关于
mn m .
6、设 是 A 上的二元运算，如果有一个元素 el A ， 使得对于任何 x A 都有 el x x ，则称 el 为 A 中关于运 算 的左幺元；如果有一个元素 er A ，使得对任何
x A 都有 x er x ，则称 e r 为 A 中关于运算 的右幺
则矩阵的加法、减法、乘法和除法都是二元运算。
解：在上述个命题中，⑴、⑵和⑶是正确的，⑷是 错误的.
我们通常用 ,,, 等符号表示二元运算，称为算符.
设 : A A
A 是Ａ上的二元运算，对任意的
x, y A, x, y z 可记作
x y z ．
和二元运算一样，也可以使用算符来表示ｎ元运算.若 f ( a1 , a2 ,, an ) b ，则可记为 a1 , a2 ,, an b ． 例如， 一元运算， (a) b a1 , a2 b 二元运算， a1 , a2 , a3 b 三元运算.
B C .所以， 运算不满足消去律.但是对称差运算
满足消去律. 注意：在使用消去律时要注意，消去的元素不能 是该运算的零元.例如， 普通乘法适合消去律.但是， 不 能由 0 4 0 6 得到 4 6 .因为 0 是乘法的零元.
习题 5.1
1、判断下列集合对所给的二元运算是否封闭 ⑴整数集合 I 和普通的减法运算 ⑵非零整数集合 I 和普通的除法运算
n个
a b c a b c a b c
满足结合律时，用数学归纳法很容易证明
a a a ， a
m n
m n

m n
a
mn
，m,n为正整数.
3、若 a b c a b a c ，则称运算“ ”对运
4、若 a a c a ，则 称运算“ ”对运算“ ”满足 若 左吸收律；若 a b a a ，则 称运算“ ”对运算 ”对运 “ ”满足右吸收律.若左右吸收律均满足，则称运算 “ ”对运算“ ”满足吸收律.
这些相当于前缀表示法，但对二元运算用得较多的还是 a1 a2 b .我们在本书中所涉及的代数运算仅限于一元. 和二元运算．
如果集合Ｓ是有穷集，Ｓ上的一元和二元运算也可以用 运算表给出.表5―1和表5－2是一元和二元运算表的一 般形式.
表5－1
表5－1
例2、(2) 设 S 0,1, 2,3, 4 ，定义 S 上的两个 二元运算如下：
2x 1 | x I 和乘法运算 ⑶
⑷ 0,1和普通的加法和乘法运算 2、 N 是自然数集，定义 N 上的运算“ ”，
n, m N , n m n 2m ，问“ ”是否是 N 上可结合
注意：一般来讲，左，右逆元未必同时存在，即使一个代数系 统中的某个元素既有左逆元又有右逆元，它们也未必相等. 例如，自然数集 N 关于加法运算只有 0 N 有逆元 0 ，其他的 自然数都没有加法逆元.在整数集 Z 中，加法幺元为 0 ，对相反数 x .因为
x ( x) 0, ( x) x 0 .
在 M n (R) 上，对于矩阵乘法只有可逆矩阵 M M n (R) 存在逆元
M 1 ， M M 1 E 和 M 1 M E 成立， 使得 其中 E 为 n 阶 单位矩阵.
9、设 为 S 上的二元运算，如果对任意的 x, y, z S 满足以下条件 （1）若 x y x z 且 x 不是零元，则 y z ， （2）若 y x z x 且 x 不是零元，则 y z ， 就称运算 满足消去律
x y ( x y) mod 5 x y ( xy) mod 5
(x, y S ) (x, y S )
求运算 和 的运算表。 解：( x y) mod 5 ， xy ) mod 5 分别是 x, y 的和 ( 与积除以5的余数，运算表如下：
二、有关运算律。 设 , 是 A上的二元运算，如果对A内的任意元素 a,b,c
例如：实数R上的全体n阶方阵构成的集合 M n R 上的方阵的乘 法满足结合律，而减法不满足结合律. 在幂集P(S)上 , , 也是 可结合的.
注意：⑴一个代数运算如果满足结合律，则进行
运算时常省略括号，如： ⑵如果每一次参与运算的都是同一个元素，还可以用 该元素的幂来表示，如 a n a a ，当运算 a
1、若 a b b a ，则称运算“ ”在A上是可换的 ，或 者说运算“ ”满足交换律.
例如：在实数集R上，通常的加法和乘法都满足交换律，但减法 和除法不满足交换律.因为2和4都是实数.因为2-4≠4-2.在幂集 P(S)上 , , 都满足交换律，但相对补不满足交换律.
2、若a b c a b c，则称运算“*”在A上是可结合 的.或称“*”满足结合律.
第五章 代数系统简介 初等代数研究的对象是数,运算是数的加法、 减法、乘法等.由于数学和科学的发展，我们需 要对许多不是数的对象进行研究，并按照类似于 以上运算的规则进行计算.因此，我们将这些东 西抽象出来统一研究，就产生了抽象代数. 由集合和集合上的运算所构成的系统称为代数 系统.本章将给出代数系统的一般定义与实例， 并讨论一些典型的代数系统.
7、 是 A 上的二元运算， 设 如果存在元素 l ， r ， A .