当前位置：文档之家 › 离散数学第十三十四章 半群与群环与域.

离散数学第十三十四章 半群与群环与域.

  • 格式：ppt
  • 大小：52.50 KB
  • 文档页数：18

下载文档原格式

  / 18

合集下载

离散数学 群与半群

离散数学 群与半群

1 2 显然，a是<{a，a2，a3，…}，⊙>的生成元。
2 给定群<G，⊙>，若G是有限集，则称<G，⊙>是有限群。
1
<T，○，e >是独异点，则<S×T，，<e ， 假若群<G，⊙>为有限群，其子群是<H，⊙>，且|G|=n，|H|=m，则G的对于H的左陪集划分可表为G=a1H∪a2H∪···∪akH，其中k为不
为置换中的反置换，记为p-1。特别把置换
பைடு நூலகம்
x1 x1
x2 x2
xxnn称 为 X 中 的 幺 置 换 或
恒等置换，记为pe。
此外，用PX表示集合X中的所有置换的集 合。
为了说明n个元素的集合可以有多少不同的 置换，特给出如下定理：
定 理 7.5.1 若 X={x1 ， x2 ， … ， xn} ， 则 |PX|=n!
在正式讨论置换群以前，需要先作些 必要的准备。
定义7.5.1 令X是非空有穷集合，从X到X的 双射，称为集合X中的置换，并称|X|为置换的 阶。
若X={x1，x2，…，xn}，则n阶置换表为
pp(xx11)
x2 p(x2)
xn p(xn)
并称
p(x1)
x1
p(x2) x2
p(xn)
xn
定义7.2.1 给定两个半群<S，⊙>与<T， ○>，则
半群<S，⊙>半群<T， ○>:=(f)(f∈TS∧(x)( y)(x， y∈S→f(x⊙y)=f(x) f(y))
并称f为从<S，⊙>到<T，○>的半群同态 映射。
由定义可以知道，半群同态映射f可以不是 唯一的。

代数,半群,群,环,域的定义

代数,半群,群,环,域的定义

代数,半群,群,环,域的定义代数是一门研究数学结构和运算规则的学科。

它研究的对象可以是数字、符号、函数、向量等，通过定义运算规则和结构特征，来研究其性质和相互关系。

在代数中，有一些基本的数学结构，包括半群、群、环和域。

半群是代数中最基本的结构之一。

它由一个集合和一个二元运算组成，这个二元运算满足结合律。

换句话说，对于半群中的任意三个元素a、b和c，(a·b)·c = a·(b·c)。

例如，自然数集合N（包括0）和加法运算构成了一个半群。

因为对于任意三个自然数a、b和c，(a+b)+c = a+(b+c)。

群是半群的扩展，它在满足结合律的基础上，还满足单位元和逆元的存在。

单位元是群中的一个特殊元素，对于群中的任意元素a，有a·e = e·a = a，其中e 是单位元。

逆元是指对于群中的任意元素a，存在一个元素b，使得a·b = b·a = e。

例如，整数集合Z（包括0）和加法运算构成了一个群。

因为对于任意整数a，存在一个整数-b，使得a+(-b) = (-b)+a = 0。

环是一个更加复杂的数学结构，它由一个集合和两个二元运算组成，分别是加法和乘法。

环中的加法满足结合律、交换律和存在零元素的特点。

乘法满足结合律和分配律。

例如，整数集合Z（包括0）和加法、乘法运算构成了一个环。

域是环的进一步扩展，它在满足环的基础上，还满足乘法的逆元存在。

换句话说，对于域中的任意非零元素a，存在一个元素b，使得a·b = b·a = 1。

例如，有理数集合Q（包括0）和加法、乘法运算构成了一个域。

以上是对代数、半群、群、环和域的简要定义。

这些数学结构在代数中扮演着重要的角色，它们的性质和相互关系被广泛应用于数学和其他领域的研究中。

离散数学-群

离散数学-群
同理可证，e ◦ a = a。 所以 e = g-1 是 G 中关于 ◦ 的单位元。 对任意的 a G，令 b = g-1 a-1 g-1，有
a ◦ b = a g (g-1 a-1 g-1) = g-1。 同理可证，b ◦ a = g-1。 所以 G 的每个元素都有逆元。 综上所述，< G; ◦ > 是群。
注：
因为半群 < S; > 中 是可结合的，所以可以定义元素的幂。
对任意 a S，定义
a1 = a，an + 1 = an a (n = 1, 2, …)，
并且对于任意正整数 m 和 n，有
am an = am + n，(am)n = amn。
3
定理5-1 设 < S; > 是一个有限的半群，则必有 a S，使得 a 是一个幂等元，即 a a = a 。
第二部分 抽象代数
0
第五章 群
本章在了解了代数系统一般概念的基础上，着重讨论具有一个 二元运算的代数系统，常称为二元代数，包括半群、独异点和 群。半群和独异点在自动机理论、形式语言及程序设计的数学 基础中占有重要的地位，而群是抽象代数中最古老且发展得最 完善的代数系统，在计算机科学中，对于代码的查错和纠错、 自动机理论等各个方面的应用的研究，群是其基础。
代数系统中唯一的单位元常记为 e。 5
在独异点 < S; > 中，也可定义元素的幂：
对任意 a S，有
a0 = e，an + 1 = an a (n = 0, 1, 2, …)，
并且对于任意非负整数 m 和 n，有
am an = am + n，(am)n = amn。
设 < S; > 为独异点，则关于运算 的运算表中没有两行或 两列是相同的。

【离散数学】知识点及典型例题整理

【离散数学】知识点及典型例题整理

【半群】G非空，·为G上的二元代数运算，满足结合律。

【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。

【Abel群/交换群】·适合交换律。

可能不只有两个元素适合x2=1【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。

【子群】按照G中的乘法运算·,子集H仍是一个群。

单位子群{1}和G称为平凡子群。

【循环群】G可以由它的某元素a生成,即G=（a）。

a所有幂的集合an，n=0，±1，±2，…做成G的一个子群，由a生成的子群。

若G的元数是一个质数，则G必是循环群。

n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。

共有ϕ（n）个。

【三次对称群】{I（12）（13）（23）（123）（132）}【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。

H有限，则H的任意右陪集aH的元数皆等于H的元数。

任意两个右陪集aH和bH或者相等或者不相交。

求右陪集：H本身是一个；任取a∉H而求aH又得到一个；任取b∉H∪aH而求bH又一个。

G=H∪aH∪bH∪…【正规子群】G中任意g，gH=Hg。

（H=gHg-1对任意g∈G都成立）Lagrange定理G为有限群，则任意子群H的元数整除群G的元数。

1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。

2设G为有限群,元数为n,对任意a∈G，有an=1。

3若H在G中的指数是2，则H必然是G的正规子群。

证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。

故Ha=aH。

4G的任意多个子群的交集是G的子群。

并且，G的任意多个正规子群的交集仍是G的正规子群。

5 H是G的子群。

离散数学 半群与含幺半群(独异点)

离散数学 半群与含幺半群(独异点)
例： < R, • >是半群，<{2,4}, •}是否是半群？ < (0,1), •>是否是半群？
∵区间 (0,1) R，且•在(0,1)上封闭可结合， ∴< (0,1), •>是<R, •>的子半群
3
定理2：<S,*>是半群，若S是有限集,则必有aS，使a*a=a。
证明：对 bS ∵<S,*>是半群，*在S上封闭，∴b*b S 记 b2=b*b， 则 b2*b=(b*b)*b=b*(b*b)=b*b2 记 b3=b2*b=b*b2 则b3*b=b2*b*b=b*((b*b)*b)=b*(b2*b)=b*b3
主要内容 1 代数系统的基本概念 2 半群与含幺半群（独异点） 3 群（阿贝尔群与循环群） 4 陪集与拉格朗日定理 5 同态与同构 6 环与域
1
定义1：<S,*>是一个代数系统，S为非空集合，*是定义在S上的二元运算：
• *是封闭的， <S,*>称为广群； • *可结合的广群称为半群； • 含有幺元的半群，称为独异点（含幺半群）； • * 可交换的半群，称为交换半群。
定义3：<G,*>是群，若G是有限集，称<G,*>是有限群； G中元素的个数称为该有限群的阶数，记为 | G |； 若G无限，则<G,*>称为无限群。
定义4：<G,*>是群，a是G中任意元素，nN，定义元素a的幂为： a，……， an+1 = an * a， 定义：a-n = ( a-1) n (其中a-1是a的逆元)
∴x = b ，即元素 b 必满足 b * b = b
7
作业
• P190 （5）
8

西北工业大学《离散数学》课件-第14章

西北工业大学《离散数学》课件-第14章
{a} {a}{b} {b{}a,b{}a,b} x x ∼x ∼x {a} {a}{b} {b}{a,b{}a,b} {a,b{}a,b} {a} {a} {a} {a} {a.b{}a.b{}b} {b} {a} {a} {a} {a} {b} {b} {b} {b{}a,b{}a,b} {a} {a} {b} {b} {b} {b} {a,b{}a,b}{a,b{}a,{bb}} {b}{a} {a} {a,b{}a,b}
的逆元
12
实例
集合 运算
Z,Q,R 普通加法+ 普通乘法
单位元
0 1
零元 无 0
Mn(R) P(B)
矩阵加法+ 矩阵乘法
并 交 对称差
n阶全0矩阵 n阶单位矩阵
B
无 n阶全0
矩阵
B 无
逆元
x逆元x x逆元x1 (x1给定集合)
X逆元X X的逆元X1 （X可逆）
的逆元为 B的逆元为B X的逆元为X
交与对称差 对可分配 无
10
特异元素：单位元、零元
定义14.7-9 设◦为S上的二元运算, (1) 如果存在el (或er)S，使得对任意 x∈S 都有
el◦x = x (或 x◦er = x)， 则称el (或er)是S中关于◦运算的左(或右)单位元. 若e∈S关于◦运算既是左单位元又是右单位元，则称e为S上 关于◦运算的单位元. 单位元也叫做幺元.
2
14.1 代数系统的基本概念
定义14.1 设S为集合，函数f：SSS 称为S上的二元运算， 简称为二元运算．函数 f:S→S 称为S上的一元运算，简 称一元运算. S 中任何元素都可以进行运算，且运算的结果惟一． S 中任何元素的运算结果都属于 S，即 S 对该运算封闭．

离散数学-近世代数-代数结构

添加标题
例：代数系统(N，+，×)。其中+，×分别代表通常数的加法和乘法。
添加标题
是否满足交换律？
添加标题
单位元( 幺元)
一个代数系统(S，*)， 若存在一个元素eU，使得对 xS，有：e * x =x * e = x，则称 e 为对于运算“ * ”的单位元,也称幺元 。 注意： 单位元是跟运算有关系的，不同的运算可能单位元是不一样的。
解： 作双射 f：A1A2，f(1)=b, f(2)=d, f(3)=c, f(4)=a
a
b
c
d
a
b
b
b
d
b
a
a
d
b
c
c
b
c
a
d
a
a
c
d
*
1
2
3
4
1
4
1
2
4
2
4
2
3
4
3
1
4
3
3
4
1
2
1
1
设代数系统V1=(A1，*)，V2=(A2，º)， 其中A1={1，2，3，4}， A2={a，b，c，d}， * 和 º 的运算分别如下表，V1 和 V2 是否同构？
等幂律
设 * 是定义在集合A上的一个二元运算，如果对于任意的xA，都有x * x = x，则称 * 运算是等幂的。 例: S={1,2,4}，在集合 p(S) 定义两个二元运算，∩，∪，分别表示集合的“并”运算和集合的“交”运算，∩，∪是等幂的？ 解：对于任意的A p(S) ，有A∩A=A；A∪A=A 因此运算∩，∪都满足等幂律。
性质、定理
定理 一个代数系统，其零元若存在，则唯一。 定理 一个代数系统(S，)，若集合 A 中元素的个数大于1，且该代数系统存在幺元 e 和零元θ，则θe。 证明：用反证法，设θ=e，则对于任意的xA，必有 x = ex = θx =θ= e， 即对于A中所有元素都是相同的，这与A中含有多个元素相矛盾。

群、环、域的基本概念与性质


群的同态与同构
群的同态
设$(G,cdot)$和$(H,*)$是两个群，如果存在一个映射$varphi:Gto H$，使得对于任意两 个元素$a,bin G$，都有$varphi(a*b)=varphi(a)cdotvarphi(b)$，则称$varphi$为从 $(G,cdot)$到$(H,*)$的一个同态映射。
群的同构
如果同态映射$varphi:Gto H$既是单射又是满射，则称$varphi$为从$(G,cdot)$到 $(H,*)$的一个同构映射，此时称群$(G,cdot)$和$(H,*)$是同构的。
同态核
设$varphi:Gto H$是一个同态映射，称集合${ain G|varphi(a)=e_H}$为$varphi$的核， 记作$kervarphi$。其中$e_H$是群$(H,*)$的单位元。同态核是群$(G,cdot)$的一个正规 子群。
感谢观看
域在代数几何中的应用
代数曲线与曲面
域上的多项式环与代数曲线、曲面密切相关， 是代数几何的基本研究对象。
有限域上的代数几何
有限域上的代数几何在密码学、编码理论等领 域有广泛应用。
域扩张与Galois理论
域的扩张与Galois理论是代数几何中的重要工具，可用于研究代数方程的可解 性等问题。
THANKS
子环、理想与商环
子环
设$(S,+,*)$是$(R,+,*)$的子集，若$S$对$+$和$*$也构 成环，则称$(S,+,*)$是$(R,+,*)$的子环。
理想
设$I$是环$R$的子集，若$I$对加法构成阿贝尔群，且对 于任意$rin R$和任意$iin I$，有$r*iin I$和$i*rin I$，则 称$I$是环$R$的理想。

半群与群的基本概念

第一节 半群与群的基本概念定义1.1 设代数系统<S,*>，其中*为二元运算。

如果*是可结合的,则称<S,*>为一个半群（semigroup ），如果半群的二元运算有单位元，则称此半群为独异点（含幺半群）。

如果独异点的每个元素都是可逆的，则称它为群(group)。

根据定义，代数系统<G ,*>为成一个群当且仅当二元运算*满足下述条件： (1)适合结合律(*)**(*),,,a b c a b c a b c G =∀∈。

(2)有单位元e G ∈∀∈==，**a G a e e a a 。

(3)a G ∀∈,有逆元1a G −∈，使得11**a a a a e −−==群<G ,*>可简记作G ，a*b 可略去*，简记作ab 。

如果半群，独异点和群中的运算是可交换的，则分别称作为交换半群，交换独异点和交换群。

交换群又称作阿贝尔（Abel ）群。

如果群中的运算不是可交换的，则称它为非交换群。

习惯上，常将群中的二元运算叫作乘法，记做 。

定义1.2 若群G 所含元素个数有限，则称G 是有限群,否则称G 是无限群。

群G 中元素个数称作群的阶。

当G 是有限群时，用|G|表示它的阶。

例1.1，,Z +<+>是半群，但不是独异点，因为它没有单位元，,N <+>是独异点，但不是群,因为除0外其它元素无逆元。

而,Z +是一个群，并且是一个交换群，叫作整数加法群。

例1.2模n剩余类加法群<⊕>,n Z 是阿贝尔群,这里{[0],[1],,[1]}n Z n =−L ,[][][()mod ]x y x y n ⊕=+, [0]是它的单位元，对于每个x=0,1,2,…,n-1，[x]的逆元是[-x]=[n-x]。

例1.3 (),n M R <•>是独异点，这里•是矩阵乘法，n 阶单位矩阵是单位元，但它不是可交换的,而且不是每一个矩阵都是可逆的。

6.2-群的定义(离散数学)


理解群的定义
例.群中消去律一定成立。 群中消去律一定成立。 证明： 是群， 证明：设(G, *)是群，其单位元是 ， 是群 其单位元是1， 对于G中任意三个元素 中任意三个元素a， ， ， 对于 中任意三个元素 ，b，c， （1）若 a * b = a * c，则 ） ， a-1 * (a * b) = a-1 *( a * c)，即 ， (a-1 * a) * b =(a-1 * a) * c，亦即 ， 1 * b =1 * c， ， 故b = c。 。 （2）同理可证：若 b * a = c * a，则b = c ）同理可证： ，
6.2.2 群 -- 群的定义
如果满足下面条件： 设（G， ）为半群，如果满足下面条件： ， ） (1) 有壹（单位元）：G中有一个元素 ，适合 有壹（单位元） 中有一个元素1， 中有一个元素 对于G中任意元素 都有1a 中任意元素a， 对于 中任意元素 ，都有 = a1 = a; (2) 有逆：对于G中任意 ，都可找到G中一个 对于 中任意a，都可找到 中一个 中任意 元素a 满足aa 元素 -1，满足 -1 = a-1a = 1， ， 则称（G， ）为群。 则称（ ， ）为群。 如果群G包含的元素个数有限，则称 为 如果群 包含的元素个数有限，则称G为有 包含的元素个数有限 限群，否则称G为无限群。 否则称 为
6.2.2 群 -- 群的例
为自然数集， 设N为自然数集，规定 上的运算“⊙”如 为自然数集 规定N 上的运算“ 下：a ⊙ b = a + b + ab。 。 已证： 为半群。 已证：（N， ⊙）为半群。 ， 不是群。 但（N， ⊙）不是群。 ， 反证：若不然， 是群， 反证：若不然， （N， ⊙）是群，则一定有 ， 单位元素，设为e 则对N中任意元素a 单位元素，设为e，则对N中任意元素a，都有 e ⊙ a = a，即e + a + ea = a， a 因此，e=0 矛盾。因此， 因此 ， e=0 ， 但 0N ， 矛盾 。 因此 ， （ N， ⊙ ） ， 无单位元素，故不是群。 无单位元素，故不是群。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

13.4 群的基本定义
定义13.4.1 给定<G，⊙>，若<G，⊙>是独 异点且每个元素存在逆元，或者说
①⊙是可结合的，②关于⊙存在幺元，③ G
中每个元素关于⊙是可逆的，则称<G，⊙>是群。
可见，群是独异点的特例，或者说，群比独
异点有更强的条件。
例13.4.1 给定<Z，+>和<Q，×>，其中Z和
例14.1.1 <Z，+，· >，<R，+，· >，<Q， +，· >，<E，+，· >和<C，+，· >等都是环。而且
除<E，+，· >外都是拥有加法幺元——数0和乘
法幺元——数1的可交换含幺环。这里Z、R、Q、
E、C分别为整数集合、实数集合、有理数集合、
偶数集合和复数集合，而+和×分别是大家熟悉
定义 环的加法群的幺元或乘法零元称为环 的零元，以0示之。若a∈R，则其加法逆元以－a 表之。
常常又根据环中乘法半群满足不同性质，将
环冠于不同的名称。
定义14.1.2 给定环<R，+，· >，若<R，· >是
可交换半群，则称<R，+，· >是可交换环；若
<R，· >是独异点，则称<R，+，· >是含幺环(即 <R，· >的幺元就称为环的幺元)；若<R，· >满足 等幂律，则称<R，+，· >是布尔环。 通常用1表示<R，· >的幺元。在<R，· >中， 若a∈R的逆元存在，则以a-1表示其对于+是可分配的，即：对任意x,y,z∈R，
x ·(y+z) = x ·y + x ·z
(y+z) ·x = y ·x + z ·x
所以加法的幺元(我们用0表示)必是乘法的零
元，故<R，· >有零元。但我们知道，群中一定不 出现零元，因此<R，· >不可能是群，只是一个半 群。
Q分别是整数集合和有理数集合，+和×是一般加
法和乘法。可知<Z，+>是群，0是幺元，每个元
素i∈Z的逆元是-i；<Q，×>不是群，1是幺元，0
无逆元。但<Q-{0}，×>便成为群。
这里我们只介绍群的一个重要性质：
定理13.4.1 <G，⊙>是群∧|G|＞1<G，⊙>
无零元。
其中|G|表示集合G的基数（势） 证明见p255
的加法和乘法运算。
例 <Mn(R),+,· >是环，其中Mn(R)是n阶实矩
阵的集合，+、· 分别是矩阵加法和乘法。
14.4 域
对于环 <R ， + ， · > 施加进一步限制，即 <R{0} ， · >是可交换群，便得到另外一个代数结 构——域。 定义14.4.1 给定可交换环<R，+，· >，若<R{0}，· >为群，则称<R，+，· >为域。
定义13.1.2 给定<M，○>，若<M，○>是半群 且○有幺元或○满足结合律且拥有幺元，则称<M， ○>为独异点。
可以看出，独异点是含有幺元的半群。因此 有些著作者将独异点叫做含幺半群。有时为了强 调幺元e，独异点表为<M，○，e>。 例13.1.1 给定<N，+>和<N，×>，其中N为 自然数集合， + 和×为普通加法和乘法。由普通 加法和乘法满足结合律易知，<N，+>和<N，×> 都是半群，而且还是独异点。因为0是+的幺元， 1是×的幺元。
例14.4.1 <R，+，· >和<Q，+，· >皆为域，
而<Z，+，· >不为域，其中R、Q和Z分别为实数
集合、有理数和整数集合，+和· 是普通加法和乘
法。
定义13.1.3 给定半群<S，⊙>，若⊙是可交换 的，则称<S，⊙>是可交换半群。类似地可定义可 交换独异点<M，○，e>。 例13.1.2 给定<P(S)，∪>和<P(S)，∩>，其中 P(S) 是集合 S 的幂集， ∩ 和∪为集合上的并与交运 算。可知<P(S)，∪>和<P(S)，∩>都是可交换半群。 不仅如此，它们还都是可交换独异点，因为与S 分别是它们的幺元。
为了方便，通常将+称为加法，将· 称为乘法， 把 <R ， +> 称为加法群， <R ， · > 称为乘法半群。
而且还规定，运算的顺序先乘法后加法。
注意这里加法和乘法不一定仅限于初等数学
的加与乘。同样，加运算的幺元我们用“0”表示，
乘运算的幺元用“1”表示，0与1的含义也不一定 仅限于初等代数中的0与1.
定义13.4.4 给定群<G，⊙>，若⊙是可交 换的，则称<G，⊙>是可交换群或<G，⊙>是 Abel群。 例13.4.3 例13.4.1中< Z，+>和例12.1.2中 <P(S)， >都是Abel群。
14.1 环
定义14.1.1 给定<R，+，· >，其中+和· 都是 二元运算，若 ①<R，+>是Abel群， ②<R，· >是半群， ③· 对于+是可分配的，即：对任意x,y,z∈R， x ·(y+z) = x ·y + x ·z (y+z) ·x = y ·x + z ·x 则称<R，+，· >是环。
第十三、十四章 半群与群、环与域

13.1 半群和独异点的定义 13.4 群的基本定义


14.1 环的定义
14.4 域的定义
13.1 半群和独异点的定义
定义13.1.1 给定<S，⊙>，若⊙满足结合律， 则称 <S ，⊙ > 为半群。即对 S 中的任意元素 x,y,z ， 有 (x⊙y)⊙z=x⊙(y⊙z)。 可见，半群就是由集合及其上定义的一个可结 合的二元运算组成的代数结构。
例 由有限字母表Σ所组成的字母串集合Σ*与 并置运算∥所构成的代数结构<Σ*，∥>是个特异 点。
因为首先它满足结合律，例如 ab//(cd//ef ) = (ab//cd)//ef = abcdef.
其次，它有一个幺元——，使得对Σ*内任意 一元素A，有 //A=A//=A.
故<Σ*，∥>是个特异点。 显然，我们令∑+＝ ∑*－{}，则<∑+，//>是 一个半群。