当前位置：文档之家 › 离散数学 半群与含幺半群(独异点)

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

  • 格式：ppt
  • 大小：2.52 MB
  • 文档页数：35

下载文档原格式

  / 35

合集下载

离散数学 群与半群

离散数学 群与半群

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可以不是 唯一的。

离散数学sec16-17 群

离散数学sec16-17 群
整数加群<Z,+>， 由 2 生成的子群是 <2> = { 2k | k∈Z } = 2Z
模 6 加群 <Z6, >中 由 2 生成的子群 <2> = { 0, 2, 4 }
21
特殊子群2
例 设G为群，令C是与G中所有的可交换的元素构 成的集合，即 C＝{a|a∈G∧x∈G(ax＝xa)} 则C是G的子群，称为G的中心。
限群。 群G的基数称为群G的阶，有限群G的阶记作|G|。
(2)只含单位元的群称为平凡群。
(3)若群G中的二元运算是可交换的，则称G为交 换群或阿贝尔(Abel)群。
11
群论中常用的概念－元素的n次幂
定义 设G是群，a∈G，n∈Z，则a的n次幂 P250 定义17.4
e a n a n1a
(a 1 )n
换 σ∈Sn，逆置换σ1是σ 的逆元. 这就证明了Sn关于置换的乘法构成一个群，称为 n
元对称群. n元对称群的子群称为 n元置换群.
31
例 设 S = {1, 2, 3}，3元对称群
S3的对称群是？ 运算表？ S3的子群？
32
n元置换的分解式
• k阶轮换与轮换分解方法 定义11.11 P258
定义 设<G,>是代数系统，为二元运算。如果运 算是可结合的，存在单位元e∈G，并且对G中 的任何元素x都有x-1∈G,则称G为群（group）。 (P249定义17.1)
例 <Z,+>,<Q,+>,<R,+>,<Z+,+>,<N,+>是不是群？
<Zn,>是群?
8

离散数学ch11[1]群

离散数学ch11[1]群

正规子群与商群
定义设H是群G的子群。如果a∈G 定义 都有Ha=aH,则称H是G的正规子群 正规子群,记作 正规子群 H G。 任何群G都有正规子群,因为G的两个平 凡子群,即G和{e},都是G的正规子群。 如果G是阿贝尔群,G的所有子群都是正 规子群。
正规子群与商群
正规子群的实例
设A={1,2,3},f1,f2,…,f6是A上的双射函数。 f1={<1,1>,<2,2>,<3,3>}, f2={<1,2>,<2,1>,<3,3>} f3={<1,3>,<2,2>,<3,1>}, f4={<1,1>,<2,3>,<3,2>} f5={<1,2>,<2,3>,<3,1>}, f6={<1,3>,<2,1>,<3,2>} 令G={f1,f2,…,f6},则G关于函数的复合运算构成 群。 G的全体子群是：
群的分解 :陪集定义 陪集定义
例2:设A={1,2,3},f1,f2,…,f6是A上的双射函数。其中 f1={<1,1>,<2,2>,<3,3>} f2={<1,2>,<2,1>,<3,3>} f3={<1,3>,<2,2>,<3,1>} f4={<1,1>,<2,3>,<3,2>} f5={<1,2>,<2,3>,<3,1>} f5={<1,2>,<2,3>,<3,1>} f6={<1,3>,<2,1>,<3,2>} 令G={f1,f2,…,f6},则G关于函数的复合运算构成群。 考虑G的子群H={f1,f2}。做出H的全体右陪集如下： Hf1={f1f1,f2f1}={f1,f2}=H Hf2={f1f2,f2f2}={f2,f1}=H Hf3={f1f3,f2f3}={f3,f5} Hf4={f1f4,f2f4}={f4,f6} Hf5={f1f5,f2f5}={f5,f3} Hf6={f1f6,f2f6}={f6,f4}

半群和独异点

半群和独异点

为了强调幺元的存在,有时将独异点记为<S,˚,e>。
则称 为独异点V1到V2的同态˚
< Z+,+>是半群。
对独异点V=<S,˚,e>, <T,˚,e>构 <N,+,0>,…,<R,+,0>
❖ x1=x,
而关于幂的两个运算公式不变,只要其中的m和n是非负整数就可以了。
成V的子独异点，需要满足： 且对任意<a,b>,<c,d>∈S1×S2有
❖ xn ˚ xm= xn+m ,
在独异点V=<S,˚,e>中,如果规定x0=e(x是S中的任意元素),那么有关半群中幂的定义可以变成
x1=x,
=
=
<a,b>·<c,d>=<a˚c,b*d>
独异点的子代数叫做子独异点.
定义 如果半群V=<S,˚>中的二元运算含有幺元,则称V为含幺半群,也可叫做独异点.
，
例 独异点V=
T对V中的运算˚是封闭的，
矩阵乘法的幺元是n阶单位矩阵E.
令 : S→ S 而
不是独异点V的么元,因此,
❖ , 定义 设V1 =<S1,˚>, V2=<S2,*>为半群,
< Zn , >是半群和独异点,其中Zn ={0,1,…,n-1}, 表示模n加法。
而关于幂的两个运算公式不变,只要其中的m和n是非负整数就可以了。
如果V=<S,˚>是半群, <T,˚>就是V的子半群,需要满足：
x例1=x半, 群V❖=<S那,. 么对任意x,y∈S都有

离散数学-半群

离散数学-半群

.
半群
1.1 半群及独异点
✓定理11.3
设<S，>为一半群,那么 （1）<SS，○ >为一半群，这里SS为S上所有
一元函数的集合，○ 为函数的合成运算． （2）存在S到SS的半群同态．
.
半群
Δ 1.2 自由独异点
➢定义 11.2
称独异点<S,,e>为自由独异点（free monoid）,
如果有AS使得 （1）eA． （2）对任意uS，xA,ux e . （3）对任意u,vS，x,yA,若ux = vy, 那么u = v,x = y． （4） S由A生成,即S中元素或者为e, 或者为A的成员， 或者为A的成员的“积”:
x,
f
(w))
其中wS,xA 。
.
半群
Δ 1.2 自由独异点
✓定理11.5
设<S,•,e1>和<T,,e2>为两个自由独异点， A,B分别为它们的生成集， 且 A = B ，那么<S,•,e1>和<T,,e2>同构。
.
半群
1.3 半群及高斯半群
➢定义11.3
设<S，>为一半群，那么
（l）当 满足交换律时，称<S，>为交换半群
ai1a i2…aik (ai1,a i2,…,aikA)
集合A称为S的生成集．
.
半群
Δ 1.2 自由独异点
✓定理11.4 设<S， , e>为一自由独异点，A为它的生成集，
g: SAM→M为一已知函数，m 为M中已知元素， 那么下列等式组定义了一个S到M的函数f；
f (e) m
f
(w
x)

离散数学第四讲半群和独异点(共10张PPT)

离散数学第四讲半群和独异点(共10张PPT)
定理 4: 在任何可交换独异点〈S, *, e〉中, S的等幂元素 集合T
证: i) 任取x,y∈T, 则 x * y=(x*x)*(y*y)=x*(x*y)*y=(x*y)*(x*y)
所以, x*y∈T,
ii) T是S的子集，*在T上可结合；
iii) e*e=e, e是等幂元素,所以,e∈T。
故〈T, *, e〉是子独异点。证毕。 本定理对可交换半群也成立。
如 〈[0，1], * 〉,〈N, * 〉都是〈R, * 〉的子半群.
定理1 证： 子半群是子代数, 关于运算*封闭, 结合律是继承的,
所以是半群。 证毕。
第3页，共10页。
3
半群和独异点
定义4：如果〈S,*,1〉是独异点。T ⊆S , 且关于运算*封
闭 T, T , 1∈ 那么〈 定义 5：在半群(独异点)中, 若运算是可交换的, 则称此半 ,* ,1〉是〈S ,* ,1〉的子代
N 〉 〈R, *,1 〉 如 〈 , *,1 就是 下中面较我 高们者定；义独异点〈S, *, e〉中任意元素a的幂。
i集ii)合e*Te=可e构, e成是子等独幂异元点素。,所以,e∈T。
的子独异点.
离〈散S,数* 〉学的第子四半讲群半。群和独异点
由使于每独 一异元点素中a∈, 运S,算都*有是一可个结相合应的的, 容h∈易N证能明把如a此写定成义gh,
② 〈S,*〉，其中S是不同高度的人的集合，a*b表示a,b
又因为 ai * e ≠ aj 对任意a、 b∈S, 存在m、n∈N, 使a=gm和b=gn,
由于独异点中, 运算*是可结合的, 容易证明如此定义
*
e
,所以任意两行都不相同。
第5页，共10页。
5

半群与独异点

半群与独异点

离散结构半群与独异点教学目标基本要求（1）掌握半群、独异点的定义（2）熟悉半群与独异点的性质（3）了解子系统和直积的概念重点难点（1）判断或证明给定集合和运算是否构成半群、独异点半群、独异点的定义定义：(1)设V=<S, ∘ >是代数系统，∘为二元运算，如果∘运算是可结合的，则称V为半群(semi-group)(2)设V=<S, ∘ >是半群，若e∈S是关于∘运算的单位元，则称V是含幺半群，也叫做独异点(monoid)，有时也将独异点V记作V=<S，∘，e>实例(1) <Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是半群，+是普通加法. 这些半群中除<Z+,+>外都是独异点(2) 设n是大于1的正整数，<M n(R),+>和<M n(R),×>都是半群，也都是独异点，其中+和×分别表示矩阵加法和矩阵乘法(3) <P(B),⊕>为半群，也是独异点，其中⊕为集合对称差运算(4) <Z n, ⊕>为半群，也是独异点，其中Z n={0,1,…,n−1}，⊕为模n加法(5) <A A, ∘ >为半群，也是独异点，其中◦为函数的复合运算(6) <R*, ∘ >为半群，其中R*为非零实数集合，∘运算定义如下：∀x, y∈R*, x∘y=y实例例设R*为非零实数集合, 对任意∀x, y∈R*, 规定x∘y =y, 则<R*, ∘ >为半群。

证明: ∀x, y, z∈R*,有(x∘y) ∘z = y∘z = z,x∘ (y∘z)= x∘z= z所以 (x∘y) ∘z = x∘ (y∘z), 运算∘满足结合律故 <R*, ∘ >为半群。

实例例：设Σ是一个非空有限集合，称为字母表，由Σ中有限个字母组成的有序集合（即字符串）称为Σ上的一个字，串中的字母个数m 称为字长，m=0 时，称为空字，记为ε。

几个典型的代数系统离散数学

几个典型的代数系统离散数学
几个典型的代数系统离 散数学
11/4/20211
1
第一页，共61页
§1 半群与群
DEFINITION 1.
设V=<S, ◦>是代数系统，◦为二元运算，如果 ◦是可结合的，则称V为半群。
如： (1) <Z+, +>, <N, +>, <Z, +>, <Q, +>, <R, +>都是
半群，其中+表示普通加法。
11/4/20211
a
Байду номын сангаас
11
第十一页，共61页
一些特殊的群：
交换群：群G中的二元运算可交换。也叫阿 贝尔(Abel)群。 无限群：群G中有无限多个元素。 有限群：群G中有有限个元素。有限群G中的 元素个数叫做G的阶，记作|G|。
11/4/20211
12
第十二页，共61页
如，
(1) <Z, +>, <Q, +>, <R, +>都是阿贝尔群， Klein四元群也是阿贝尔群。
使用这个定理可以通过运 算表很快地判断出哪些代 数系统G=<S, ◦>不是群。
设G为有限群，则G的运算表中的每一行（每
一列）都是G中元素的一个置换，且不同的行（ 或列）的置换都不相同。
这就是说，在G的运算表的每一行里。G的每 个元素都出现且仅出现一次，行不同，元素 的排列顺序也不同。
11/4/20211
(x ◦ y)= (x) * (y)， 则称为半群V1到V2的同态。
设V1=<S1, ◦, e1>, V2=<S2, *, e2>为独异点， : S1→S2，且x, yS1，有：

最新离散数学耿素云版第十一章 半群与群ppt课件

最新离散数学耿素云版第十一章 半群与群ppt课件
证 设|ab|=d.由ab=ba可知 (ab)nm=(an)m(bm)n=emen=e
从而有d|nm.
又由adbd=(ab)d=e可知 ad=b-d ，即|ad|=|b-d|=|bd|.再根据 (ad)n=(an)d=ed=e
得|ad||n。 同理有|bd||m。从而知道|ad|是n和m的公因子。因为n与m互
(2) 由(a-1)r=(ar)-1=e-1=e 可知a-1的阶存在。令|a-1|=t,根据上面的证明有t|r。这说明a的逆 元的阶是a的阶的因子。而a又是a-1的逆元,所以a的阶也是a-1的 阶的因子,故有r|t。从而证明了r=t,即|a|=|a-1|。
例11.7 设G是群,a,b∈G是有限阶元。证明 (1)|b-1ab|=|a| (2)|ab|=|ba|
例11.1 (1)<Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是半群,+是普通加 法。这些半群中除<Z+,+>外都是独异点。 (2)设n是大于1的正整数,<Mn(R),+>和<Mn(R),·>都是半群,也都是 独异点,其中+和·分别表示矩阵加法和矩阵乘法。 (3)<P(B), >为半群,也是独异点,其中 为集合的对乘差运算。 (4)<Zn, >为半群,也是独异点,其中Zn={0,1,…,n-1}, 为模n加 法。
1.能够构成群。 2. |0|=1 |1|=|5|=|7|=|11|=13|=|17|=18 |2|=|4|=|8|=|10|=|14|=|16|=9 |3|=|15|=6 |6|=|12|=3 |9|=2 3.设|a|=n, |xax-1|=m。由下式

离散数学教程-王元元-第12章 群环域

离散数学教程-王元元-第12章 群环域
语言<，并置>，其中||=n。
离散数学 第12章 群、环、域
12.1 半群
12.2.1 群及其基本性质
定义12.3 称代数结构<G,>为群，如果 （1）<G, >为一半群。 （2）<G, >中有幺元e。 （3）<G, >中每一元素都有逆元。 简言之，群是每个元素都可逆的独异点。
群的载体常用字母G表示，G也常用于表示一个群。
离散数学 第12章 群、环、域
12.1 半群
12.1.1 半群及独异点
定理12.3 设<S,>为一半群,那么 (1) 存在<S,>到<SS,◦ >的半群同态h。 (2) <S,>在含有幺元时同构于<h(S),◦>, 后者是<SS,◦ >的一个子代数。 证 证(1)：定义函数h:S→SS：对任意aS，h(a)= fa fa：S→S 定义如下: 对任意xS， fa(x)= ax 即将S中的一个元素a影射到一个线性变换fa。现证h为一同态。 对任何元素a,bS ， h(ab)＝fab (l2－1) 而对任何xS，fab(x)= abx = fa(fb(x))= fa◦fb (x)，故fab= fa◦fb ,
由此及式(l2－1)即得 h(ab)= fab = fa◦fb ＝h(a)◦h(b)
证(2)：只需证明a,bS，如果a≠b，则fa≠fb。因为<S,>含有幺元 e，a*e=a≠b*e=b，所以存在xS，fa(x)≠fb(x)，定理得证。
离散数学 第12章 群、环、域 12.1 半群
12.1.1 半群及独异点
（4）S由A生成，即S中元素或者为e, 或者为A的成员，或者 为

离散数学 第四章 4

离散数学 第四章 4

(3)
S={1,2,3,…,n}到自身的双射称为 元置换, 到自身的双射称为n元置换 到自身的双射称为 元置换 记为σ 记为σ，可表示为
2 n 1 σ = σ (1) σ (2) σ ( n )
上的双射即置换的个数共n!个 上置换 注：S上的双射即置换的个数共 个,S上置换 上的双射即置换的个数共 的全体记作S 的全体记作 n
2 设f是含有格中元素以及符号 是含有格中元素以及符号=,≤,≥，∨和∧ 是含有格中元素以及符号 ， 的公式， 是将f中的符号分别替换成 的公式，令f*是将 中的符号分别替换成 ， 是将 中的符号分别替换成=， ≥ ,≤, ∧与∨所得到的公式，则称 为f的对偶 所得到的公式，则称f*为 的对偶 命题。 命题。 3 对偶原理：f* f 对偶原理：
第六章
几个典型的代数系统
半群与群
格与布尔代数
6.1 半群与群
是一个代数系统, 设V=(G, )是一个代数系统 是一个代数系统 上的二元运算, 是G上的二元运算 上的二元运算 1 若 在G上成立结合律 则称 为半群。 上成立结合律 则称V为半群。 上成立结合律,则称 如：〈Z+, +〉, 〈N, +〉, 〈Z,+〉 〉 〉 〉 2 若 在G上成立结合律 且有单位元，则称 为 上成立结合律 上成立结合律, 有单位元，则称V为 独异点（含幺半群） 独异点（含幺半群）。 如： N, +〉, 〈Z,+〉 〈 〉 〉
轮换其乘法
例 设f=(15342), g=(125)(34) 求fg, g f, f-1, g-1
(4) 设M是非空集合 有n个元素 上所有置换 是非空集合,有 个元素 个元素,M上所有置换 是非空集合
的集合关于置换的乘法(函数的复合运算 构成 的集合关于置换的乘法 函数的复合运算)构成 函数的复合运算 一个群,称为 元对称群， 称为n元对称群 一个群 称为 元对称群， 它的任何子群称为n元置换群 元置换群。 它的任何子群称为 元置换群。 例题: 元对称群。 例题 S3是3元对称群。 元对称群

离散数学 半群和独异点、群与子群

离散数学 半群和独异点、群与子群
定理 设<S,*>是一个独异点，则在关于运算*的运算表中任何
两行或两列都是不相同的。 证明 设S中关于运算*的幺元是e。因为a,bS且a≠b，总有
e*a=a≠b=e*b 和 a*e=a≠b=b*e 所以，在*的运算表中任何两行或两列都是不相同的。
定理
设<S, * >是独异点，对于任意a,b∈S,且a,b均有逆元，则 1) (a-1)-1=a 2) a * b有逆元，且(a * b)-1=b-1 * a-1
则称代数系统 <S，*>为半群。
例 设集合Sk={x|x ∈I ∧ x≥k}，k≥0，那么<Sk,+>是一个
半群吗？（其中+是普通加法运算） 分析 因为加法运算在Sk上是封闭的，并且该运算可结合，
所以<Sk,+>是一个半群。 注意 若k＜0，则运算+在Sk上是不封闭的。
？ 代数系统<I+,－>是半群吗？<R，/>呢？
定理 设<S，*>是一个半群，如果S是一个有限集，则必有
a∈S，使得a*a=a。
证明
因为<S，*>是一个半群。对于bS ，由*的封闭性可知 b*bS，记b2=b*b b2*b=b*b2S，记b3=b2*b=b*b2
……
由于S是有限集，所以必存在 j>i，使得bi=bj 令p=j－i，有bi=bp*bi，所以对q≥i，有bq=bp*bq 因为p≥1，所以总可以找到k≥1，使得kp≥i 就有bkp= bp*bkp
构成群，则称 <S，*>是<G,*>的一个子群。
定理 设<G,*>是一个群， <S，*>是<G,*>的一个子群，那末， <G,*>中的幺元 e 必定也是<S,*>中的幺元。

第十六章半群与独异点SemigroupandMonoid

第十六章半群与独异点SemigroupandMonoid

26
扩展的有穷自动机
有穷半自动机: 三元组M*=<Q,Σ*,δ*>,Q 为有穷状态集, Σ*为Σ上的串的集合, δ* ： Q×Σ*Q为状态转移函数
有穷自动机：五元组M*=<Q,Σ*,Γ*,δ*, λ*>, Γ*为Γ上的串的集合,λ*: Q×Σ* Γ* 为输出函数
© Peking University
例. <N,+>,<Z,+>,<R,+> , <N,×>,<Z,×>,<R,×>, <P(B), ∩>,<P(B), ∪>,<P(B), >都是半群。
© Peking University
2
二. 独异点 ( Monoid )
1.独异点定义：设<M,>是个半群,如果对有幺元(identity) 。 则称<M,>是个独异点，也称它是含幺半群。 <Z,+>,<R,+> 幺元是0 <Z,×>,<R,×> 幺元是1 <P(B), ∩>,幺元是B <P(B), ∪>,幺元是Φ <P(B), >幺元是Φ 所以它们都是独异点。
© Peking University
25
16.2有穷自动机(有限状态自动机)
有穷半自动机: 三元组M=<Q,Σ,δ>,Q为有穷 状态集, Σ为有穷输入字符表,δ： Q×ΣQ为 状态转移函数
有穷自动机：五元组M=<Q,Σ,Γ,δ, λ>, Γ 为有穷输出字符表,λ: Q×Σ Γ为输出函 数
© Peking University

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

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

定义 环的加法群的幺元或乘法零元称为环 的零元，以0示之。若a∈R，则其加法逆元以－a 表之。 常常又根据环中乘法半群满足不同性质，将 环冠于不同的名称。
定义14.1.2 给定环<R，+，·>，若<R，·>是 可交换半群，则称<R，+，·>是可交换环；若 <R，·>是独异点，则称<R，+，·>是含幺环(即 <R，·>的幺元就称为环的幺元)；若<R，·>满足等 幂律，则称<R，+，·>是布尔环。 通常用1表示<R，·>的幺元。在<R，·>中， 若a∈R的逆元存在，则以a-1表示其乘法逆元。
定义13.1.3 给定半群<S，⊙>，若⊙是可交换 的，则称<S，⊙>是可交换半群。类似地可定义可 交换独异点<M，○，e>。 例13.1.2 给定<P(S)，∪>和<P(S)，∩>，其中 P(S)是集合S的幂集，∩和∪为集合上的并与交运 算。可知<P(S)，∪>和<P(S)，∩>都是可交换半群。 不仅如此，它们还都是可交换独异点，因为∅与S 分别是它们的幺元。
例 由有限字母表Σ所组成的字母串集合Σ*与 并置运算∥所构成的代数结构<Σ*，∥>是个特异 点。 因为首先它满足结合律，例如 ab//(cd//ef ) = (ab//cd)//ef = abcdef. 其次，它有一个幺元——Λ，使得对Σ*内任意 一元素A，有 Λ//A=A//Λ=A. 故<Σ*，∥>是个特异点。 显然，我们令∑+＝ ∑*－{Λ}，则<∑+，//>是 一个半群。
例14.4.1 <R，+，·>和<Q，+，·>皆为域， 而<Z，+，·>不为域，其中R、Q和Z分别为实数 集合、有理数和整数集合，+和·是普通加法和乘 法。

【推荐文档】离散数学半群PPT

【推荐文档】离散数学半群PPT
离散数学半群
一、广群与半群
半群是一种特殊的代数系统，在计算机科学领域中，如形 式语言，自动机理论等方面，已得到了卓有成效的应用。
定义 <S, *>为一个代数系统，集合S 。*是S上的一 个二元运算，如果运算*是封闭的，则称代数系统 <S, *>为广群。 定义 若<S, *>为广群，且*在S上可结合，，则称<S, *> 为半群。 例如： 1）幂集P（A）上对称差运算构成半群。 2）设Z为整数集，+、-、*是数的加法、减法和乘法，则 （Z， +）、（Z，*）都是半群；（Z，-）不是半群。 3）Nk= {0, 1, 2, , k-1}上模k加法成半群。
证明：（这仅需证明< Zm , +m >, < Zm , m >都为独异点即可。） 事实上：
1）+m, m在Zm上封闭。 2）对任[ i ], [ j ], [ k ] Zm ([i] +m [j] ) +m [k] = [i] +m ([i] +m [j]) = [(i + j + k ) mod m ]
b3 = b2*b S,
即是说序列 b, b2, b3, …, bi … bj …都为S中元
一、广群与半群
因S有限，故存在j>i使 bi = bj 设 P = j-i 则 bj = bp*bi = bi 故 bp*bi*b = bi*b 即 bp*bi+1 = bi+1 对 q>i有 bp*bq = bq 由于 p1 ，故存在k1使kp i 即 bp*bkp = bkp 这是一个递推关系，即 bkp = bp*bkp = bp* (bp*bkp) =… = bkp*bkp 令 bkp = a，即有a*a = a。 *本定理说明有限半群必有幂等元。

离散数学 ch6.1半群与单元半群

离散数学 ch6.1半群与单元半群

练习5-2
1 判断下述论断正确与否，在相应的括号中键入“Y”或“N”， （1）在实数集R上定义二元运算 为：对于任意的 a,b ∈R a*b=a+b+ab (a) （R ； ）是一个代数系统； (b) （R ； ）是一个半群； （ Y ） （ Y）
（c） （R ； ）是一个独异点。 （ Y ） (2) 在实数集R上定义二元运算为，对任意 a, b ∈ R ， a b=|a|· b(其中· 表示通常数的乘法运算)
例如： 判断（I,+）,（R,+） ，（P(E), ）， （R,×） 及（P(E), ∩）是否为群？请说明理由。 解：（I,+）,（R,+）幺元是 0，每个x的逆元是 -x 。 （P(E), ）幺元是Φ ，因任何X∈P(E) XX=Φ ∴X-1=X， ∴（I,+）,（R,+）,（P(E), ）是群。 而 （R,×） ,（P(E), ∩）都有幺元，但不是群。
（a） （R ； ）是一个代数系统； (b) （R ； ）是一个半群； （ Y ） （ Y ） （ N ）
(c) （R ； ）是一个独异点。
6-2.1 群 Group
群是抽象代数中最重要的，所以对它的研究也比较多。 一. 概念 半群: 1.群的定义：设（G, * ）是个
封闭
代数系统，如果*满足 独异点: 结合 有幺元 可结合、有幺元且每个元素 群 可逆，则称它是个群。 可逆 即群定义： 设（G, * ）是代数系统, （1） （a * b）* c=a * (b * c) (结合律) （2）幺元 e∈S, (有幺元) （3）任何a∈S 有a-1∈S, (可逆) 则称（G, * ）是个群。
运算由下表定义,容易验证 a b a q p 运算满足结合律，如 b b b a (b p)= a b= p p p p q a b (a b ) p= p p= p, 同理结合律对于任意三个元素都成立

第五章 2半群

第五章 2半群

5-3 半群(Semigroups)
例5 对任意a, b∈R，规定a b= (a+b)/2，则 是半群。
证明 对于1, 2, 3∈R，有
(1 2) 3
1 2 3
3 2
3
9
2
24
1 (2 3) 1
2
3
1
5 2
7
2
24
所以 “ ” 不满足结合律。
故 R, 不是半群。
R,不
5-3 半群(Semigroups)
(6) A≠ ， 2A,
逆元，所以不是群。
是半群，幺元为A，非空集合无
5-4 群与子群(Groups & Subgroups)
(7) A≠ ， 2A,
是半群。 S∈2A，因为
所以幺元为 。 S S S
又因为
所以2A的每个元素以其自S身为逆S 元 。故
是群。
2 A ,
5-4 群与子群(Groups & Subgroups)
5-3 半群(Semigroups)
(a b) b = a b = a = a b =
a (b b)
(b a) a = a a = b = b b =
b (a a)
(b a) b = a b = a = b a =
b (a b)
故 b S(,b
为半(群b。b) a)
a
=
b
a
=
a
=
b
a
=
(b b) b = b b = b = b b =
(b)
(a b) (b1 a1) a (b b1) a1 a e a1 a a1 e,
(b1 a1) (a b) b1 (a1 a) b b1 e b b1 b e.
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
例： < 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
主要内容
1 代数系统的基本概念 2 半群与含幺半群（独异点） 3 群（阿贝尔群与循环群） 4 子群与陪集 5 同态与同构 6 环与域
9
1. 群的概念
定义1：每个元素都有逆元的独异点，称为群。 定义2：若群还满足交换律，则称为交换群（阿贝尔群）。
例： < R, - >是代数系统，是否是半群？ 因为-在R上封闭，但不可结合；不是半群！ < R, • >是半群，而且含有幺元1 所以也是独异点，是可交换的独异点。
2
定理1：<S,*>是半群，BS，且*在B上封闭，则<B,*>是半 群。通常称<B,*>是<S,*>的子半群。
证明：要证明<B,*>是半群，只要证*在B上封闭、可结合 已知*在B上封闭 ∵<S,*>是半群， BS， ∴a,b,c B，a,b,c S， *在S上可结合，有 a*(b*c)=(a*b)*c，即*在B上可结合 ∴<B,*>是半群
a0 = e，a1 =
显然，a m * a k = a m + k ，( a m ) k = a m k（m,k I）
10
ቤተ መጻሕፍቲ ባይዱ
定义5：<G,*>是群，a是G中任意元素，若存在nZ+，使an = e， 则称元素 a 的阶是有限的，最小的正整数n称为元素a的阶； 若不存在这样的正整数n，则称元素a具有无限阶。
= b * e * b-1 = b * b-1 = e ∴ (a * b) -1 = b -1 * a -1
6
例1：< {a,b},* >是半群， 其中 a * a = b，求证： (1) a * b = b * a ； (2) b * b = b 。
证明： (1) a * b = a * (a * a) = (a * a) * a = b * a (2) b * b = b * (a * a) = (b * a) * a
∵ < {a,b},* >是半群，∴* 在{a,b}上封闭， ∴ b * a = a 或者 b * a = b 若 b * a = a ，则 b * b = (b * a) * a = a * a = b 若 b * a = b，则 b * b = (b * a) * a = b * a = b 证法2：(2) ∵ < {a,b},* >是半群，{a,b}是有限集， ∴必有一个元素 x {a,b}，使 x * x = x ∵a * a = b ≠ a ，∴x ≠a
…… 记 bn=bn-1*b=b*bn-1 …… ∵S是有限集，∴根据鸽巢原理，存在 j>i，使得bi=bj 记 p=j-i (则 p≥1)，则 j=p+i ∴bi = bj = bp+i = bp * bi ，∴ bi * b = bp * bi * b
∴bi+1 = bp * bi+1 ，bi+2 = bp * bi+1 *b= bp * bi+2 … br = bp * br (r ≥i ) ∵p ≥1， ∴总可以找到 k ≥1 使得kp ≥i ∴bkp = bp * bkp = bp * (bp * bkp) = b2p * bkp = b2p * (bp * bkp) =
证明：令e是<S,*>的幺元， (1) ∵ a-1 * a = e = a * a-1 ，∴a -1与 a 互为逆元，
∴ (a -1) -1=a (2) ∵(a * b) * (b -1 * a -1) = a *( b * b-1) * a-1
= a * e * a-1 = a * a-1 = e (b -1 * a -1) * (a * b) = b -1 * (a -1 * a) * b
例：
*eab e e ab aabe bbe a
b3p * bkp = … = bkp * bkp ∵ *在S上封闭， ∴bkp S， 令 a = bkp，则 a * a = a
4
定理3：<S,*>是独异点，则在关于*的运算表中，任何两 行或两列都是不同的。
证明：令e是<S,*>的幺元，则a，bS，且a ≠b， ∵e * a = a ≠ b = e * b ，∴任意两列在e这一行中不同 ∵a * e = a ≠ b = b * e ，∴任意两行在e这一列中不同
* …… e …… a …… b …...
e …… e …… a …… b …... a …… a …… …… …...
b …… b …… …… …...
5
定理4：<S,*>是独异点， a，bS，且都有逆元，则 (1) (a -1) -1=a ； (2) a * b有逆元，且 (a * b) -1 = b -1 * a -1。