当前位置：文档之家 › 离散数学sec16-17 群

离散数学sec16-17 群

  • 格式：pptx
  • 大小：533.09 KB
  • 文档页数：15

下载文档原格式

  / 15

合集下载

离散数学(第16-17章)陈瑜

离散数学(第16-17章)陈瑜
2019/1/16 计算机学院 8/128
定理16.1(移项法则)设<R,+, *>是一个环， θ是加法幺元，对任意a，b，c R有: a+b=c a+b-c=θ
2019/1/16
计算机学院
9/128
定理16.2设<R,+, *>是一个环，θ是加法幺 元，对任意a，b，c R有: ① a*θ=θ*a=θ(加法幺元是乘法零元) ② (-a)*b=a*(-b)=-(a*b) ③ (-a) *(-b)=a*b ④ (b-c) *a=b*a-c*a ⑤ a* (b-c）=a*b-a*c
2019/1/16 计算机学院 7/128
例 16.2 设 Zk 表示整数集 Z 上的模 k 剩余类集 合，即: Zk={[0]，[1]，[2]，…，[k-1]} <Zk ，>是群（剩余类加群）， <Zk ，>是半群（剩余类乘半群）， ∵ 对 [i]，[j]，[k] Zk 有[i]（[j][k]）=[i(j+k)]=[ij+ik] =[ij][ik] =([i][j])([i][k]） ∴ <Zk ，，>是环，称为（模k）剩余类环。 特别， k=2时，称为布尔环。
2019/1/16 计算机学院 6/128
例 16.2 设 Zk 表示整数集 Z 上的模 k 剩余类集 合，即: Zk={[0]，[1]，[2]，…，[k-1]} <Zk ，>是群（剩余类加群）， <Zk ，>是半群（剩余类乘半群）， ∵ 对 [i]，[j]，[k] Zk 有[i]（[j][k]）=[i(j+k)]=[ij+ik] =[ij][ik] =([i][j])([i][k]） ∴ <Zk ，，>是环，称为（模k）剩余类环。 特别， k=2时，称为布尔环。

离散数学 群

离散数学 群
定理7.1.4 任何一个循环半群（或含幺循环半群）都是可 交换半群（或含幺可交换半群）。 定理7.1.5 设<S, *>是一个半群，H 是S中任一元素的幂所 构成的集合，则<H,*>是<S, *>的子半群，且是个循环子 半群。 (该定理的证明自己练习)
5 半群同态
定义7.1.5 设U=<X,ο >和V=<Y, *>是两个半群，ο和*都是 二元运算，函数f：X→Y，若对任意的x,y∈X，有：
定理 群的运算表中每一行或每一列都是G中元素的双变换。 G中每个元素在每一行必出现且仅出现一次。
例 P198习题-18 若群<G,*>中每个元素的逆是其自身， 证该群是阿贝尔群。
证 只需证运算*可交换。 对任意的a,b∈G, a*b=a-1*b-1=(b*a)-1=b*a 故<G,*>是阿贝尔群。
= x*(a*b) 故 a*b∈C; ② 可逆性：若a∈C, 证a-1∈C。明显e∈C，对任x∈G，
a-1*x = a-1*x*a* a-1 = a-1*(x*a)* a-1 = a-1*(a*x)* a-1 = (a-1*a)*x* a-1 = x* a-1
故 a-1∈C;因此C是G的子群。 （习题-25与之类似）
阿贝尔群 设<G，*>是一个群，若*是可交换的, 则称 群 <G，*>为可交换群或阿贝尔群。
例 <R，×>不是群；而 <R-{0}，×>是群。
例 7.2.1 <I，+>是阿贝尔群。
例 7.2.2 G={α，β，γ，δ}，验证<G，*>是群。
可验证运算*是可结合的， * α β γ
δ

离散数学

离散数学

代数运算
定义： 是三个任意的非空集。 定义：设 A、B、D是三个任意的非空集。 、 、 是三个任意的非空集 一个A 一个 ×B到D 的函数 * ， 到 叫做一个A 叫做一个 ×B到D的代数运算。 到 的代数运算。 给了A中的任意一个元素 和B中任意一个元素 ，存 中任意一个元素b， 给了 中的任意一个元素a和 中任意一个元素 中的任意一个元素 在唯一的d∊D， 在唯一的 ∊ ，使得 * ((a，b))=d ， 由于代数运算是一种特殊的函数，描写它的符号， 由于代数运算是一种特殊的函数，描写它的符号，也 可以特殊一点。 可以特殊一点。我们记 *((a，b))=d 为 ， a*b =d
伽罗瓦
Galois, Evariste
法国数学家。 日生于巴黎附近的小镇。 法国数学家。1811年10月25日生于巴黎附近的小镇。 年 月 日生于巴黎附近的小镇 1827年开始自学勒让德、拉格朗日、高斯和柯西等人的 年开始自学勒让德、 年开始自学勒让德 拉格朗日、 论著。 论著。1828-1830年，得到许多后来称为「伽罗瓦理论」 年 得到许多后来称为「伽罗瓦理论」 的重要结果。 的重要结果。 1830年进入高等师范学校 年进入高等师范学校 (Ecole Normale)学习， 学习， 学习 1832年5月31日，死于一次 年 月 日 决斗中。 决斗中。 直到1846年，伽罗瓦的手稿 年 直到 才公开发表。 才公开发表。1870年，伽罗 年 瓦的工作才被完全理解。 瓦的工作才被完全理解。
例4ቤተ መጻሕፍቲ ባይዱ
Z是整数集，* 是Z上一个二元运算， 是整数集， 上一个二元运算， 是整数集 上一个二元运算 对于任意的m， ∊ ， 对于任意的 ，n∊Z，m*n=m+n-5。 。 是可交换的吗？ 是可结合的吗？ 问：* 是可交换的吗？ * 是可结合的吗？ 对于任意的m， ∊ ， 解：对于任意的 ，n∊Z， ， ∵m*n=m+n-5， n*m=n+m-5, 是可交换的。 ∴m*n=n*m，故 * 是可交换的。 ， 对于任意的m， ， ∊ ， 对于任意的 ，n，k∊Z， ∵(m*n)*k =(m+n-5)*k=m+n+k-10, 又 m*(n*k)=m+n+k-10, 是可结合的。 ∴(m*n)*k=m*(n*k)，故 * 是可结合的。 ，

离散数学形考任务3代数结构部分概念及性质

离散数学形考任务3代数结构部分概念及性质

离散数学形考任务3代数结构部分概念及性质一、概念介绍代数结构是离散数学中的一个重要概念。

它描述了在特定集合上定义的运算规则和性质。

常见的代数结构主要包括：1. 群（Group）：群是一种具有封闭性、结合律、单位元和逆元的代数结构。

它是一种基本的抽象代数结构，并具有丰富的性质和应用。

2. 环（Ring）：环是一种具有加法和乘法两种运算的代数结构。

它具有封闭性、结合律、单位元、交换律和分配律等性质。

3. 域（Field）：域是一种具有加法、乘法、减法和除法四种运算的代数结构。

它是一种高级的代数结构，并满足多种性质，如交换性、维数等。

二、性质探讨不同的代数结构具有不同的性质，下面我们分别探讨一下群、环和域的性质：1. 群的性质：- 封闭性：对于群G中的任意元素a和b，它们的运算结果ab 也属于G。

- 结合律：对于群G中的任意元素a、b和c，(ab)c = a(bc)，即运算顺序不影响结果。

- 单位元：群G中存在一个元素e，使得对于任意元素a，ae = ea = a。

- 逆元：对于群G中的任意元素a，存在一个元素b，使得ab = ba = e。

2. 环的性质：- 封闭性：对于环R中的任意元素a和b，它们的加法运算结果a+b和乘法运算结果ab都属于R。

- 结合律：对于环R中的任意元素a、b和c，(a+b)+c = a+(b+c)和(ab)c = a(bc)，即运算顺序不影响结果。

- 单位元：环R中存在一个元素0，使得对于任意元素a，a+0 = 0+a = a。

- 交换律：对于环R中的任意元素a和b，a+b = b+a和ab = ba。

- 分配律：对于环R中的任意元素a、b和c，a(b+c) = ab+ac和(a+b)c = ac+bc。

3. 域的性质：- 封闭性：对于域F中的任意非零元素a和b，它们的加法运算结果a+b和乘法运算结果ab都属于F。

- 结合律、单位元和逆元：与群和环的性质类似，域也具有结合律、单位元和逆元的性质。

离散数学第七讲群、环、域

离散数学第七讲群、环、域

17
三、子群
定义7: 设〈G , *〉是一个群, S是G的非空子集, 并满足以 下条件: (1) 对任意a、b∈S有a * b∈S ; (2) 对任意a∈S有a-1 ∈S; (3) e∈S, e是〈G ,*〉的么元, 则称〈S ,*〉是〈G ,*〉的子群。 如 〈I ,+〉是〈R ,+〉的子群， 〈N ,+〉不是。
的群同态如果g一个子集k的每一元素都被映入h再没有其它元素映入e的同态h的核kerh形成群g如果abkerh那么habkerh即kerh对运算1kerh四群同态24定义10的子群我们称集合ah为元素ag所确定的子群称为左陪集ah的表示元素
6.7
一、群的定义和性质
群
定义1：群〈G , * 〉是一代数系统, 其中二元运算* 满足: (1) 运算*是可结合的； (2) 存在么元e (3) 对每一a∈G, 存在一个元素a-1 , 使 a-1 * a = a * a-1 = e 如 〈Q, ×, 1〉 不是群（0无逆元） 〈Q+, ×, 1〉 是群
16
二、置换群和循环群
定理11：设〈G, *〉是由g∈G生成的有限循环群, 如果 |G|=n,则gn =e, G = {g, g2, g3, …, gn = e} 且n是使gn =e 证: (2) 再证{g, g2, g3, …, gn}中的元素全不相同。 若有gi= gj, 不妨设i＜j, 于是gj-i=e。 但j-i＜n, 这与n是使gn =e 由于〈G , *〉是群, 所以G= {g, g2, g3, …, gn}, 又由(1)得gn =e。 证毕。
如 〈I, +〉是阿贝尔群。
2
一、群的定义和性质
例1：①〈Q+, ×, 1〉

离散数学部分概念和公式总结(考试专用)

离散数学部分概念和公式总结(考试专用)

命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。

命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。

给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。

若指定的一组值使A的值为真，则称成真赋值。

真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。

将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。

命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。

（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。

（3）若A至少存在一组赋值是成真赋值，则A是可满足式。

主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

命题的等值式：设A、B为两命题公式，若等价式A↔B是重言式，则称A与B是等值的，记作A<=>B。

约束变元和自由变元：在合式公式∀x A和∃x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。

一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A↔B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。

前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。

集合的基本运算：并、交、差、相对补和对称差运算。

笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。

二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。

群(离散数学)(1)

群(离散数学)(1)
2013-7-16
所以“5”是<6, +6>的生成元。
24
例13.2.8（续）
因此，含幺半群<6, +6>有两个生成元“1”、 “5”，则<6, +6>是循环含幺半群。
另解 不妨设a∈6是生成元，则 x∈6，m∈N，有x = am = ma (mod 6)， 特别地，当x = 1时，有1 = ma (mod 6)，即 k∈Z，使得ma = 6k + 1，即 ma + (k)6 = 1。
因此，(a, 6) = 1，即a与6的最大共因子为1。
2013-7-16
25
例13.2.8（续）
反之，对 a∈6，如果(a, 6) = 1，则
k∈Z，使得1 = ma + 6k，
因此，对x∈6，有
x = (xm)a + 6(xk)，xm，xk∈Z，
根据“+6”的定义，则 x = axm，xm∈Z， 因此，a是生成元。
2013-7-16
29
13.3 群及其性质
定义13.3.1 质： 设<G, >为二元代数系统，满足如下性
（1）“”在G中满足结合律，即a, b, c∈G，有 (ab) c = a (bc)； （2）G中存在关于“”的幺元e，即e∈G，使得 a∈G，ea = ae = a； （3）G中每个元素a都有逆元a1，即a∈G，都
2013-7-16
23
例13.2.8（续）
②、2º = 0, 2¹ = 2, 2² = 0, 2³ = 2,„„，
所以“2”不是<6, +6>的生成元；
③、3º = 0, 3¹ = 3, 3² = 0, 3³ = 3,„„，

离散数学代数结构部分

离散数学代数结构部分

离散数学代数结构部分离散数学是数学的一个分支，主要研究离散的、分离的、离散化的对象和结构。

其中代数结构是离散数学的一个重要部分，涉及到一些常见的代数结构，如群、环和域等。

下面将从群、环和域三个方面展开，对离散数学中的代数结构进行详细介绍。

一、群群是离散数学中的一个基本代数结构，它由三个主要部分组成：集合、运算和满足一定性质的公理。

具体地，一个群G是一个非空集合，也即G={a,b,c,...}，其中的元素a、b、c等叫做群的元素。

除此之外，群还具有一个二元运算，记作"·"，满足以下四个公理：1.封闭性公理：对于群的任意两个元素a、b，它们的乘积c=a·b仍然属于G，即c∈G。

2.结合律公理：对于群的任意三个元素a、b、c，(a·b)·c=a·(b·c)。

3.单位元公理：群中存在一个特殊的元素e，称为单位元，满足对于任意元素a，有a·e=e·a=a。

4.逆元公理：对于群中任意元素a，存在一个元素b，使得a·b=b·a=e，其中e是群的单位元。

群结构的研究对于解决各类数学问题具有重要意义。

例如，在密码学中，通信双方使用群的运算来实现加密和解密的功能。

二、环环是另一个重要的代数结构，在离散数学中有广泛的应用。

一个环R由一个非空集合以及两个满足一定条件的二元运算分别组成。

对于一个环R={G,+,·}，其中G是一个非空集合，"+"和"·"分别是R上的两个二元运算，满足以下四个公理：1.集合G关于"+"构成一个阿贝尔群，即对于任意的a、b、c∈G，满足以下性质：(a+b)+c=a+(b+c)，存在单位元0，对于任意元素a，有a+0=0+a=a，对于任意元素a，存在一个元素-b，使得a+(-b)=-b+a=0，且满足交换律性质：a+b=b+a。

离散数学各章要点16

离散数学各章要点16

主要内容1.无向树的定义及其性质.2.生成树的定义及存在定理.3.基本回路及基本回路系统.4.基本割集及基本割集系统.5.最小生成树.6.根树及其分类.7.最优树、Huffman算法.8.最佳前缀码.9.波兰符号法与逆波兰符号法.学习要求1.深刻理解树的定义和性质.2.熟练地求解无向树.3.准确地求解最小生成树（见例题）.4.深刻理解基本回路、基本割集、基本回路系统、基本割集系统等概念.5.深刻理解根树、分类、家族树等诸多概念.6.会画阶数n较小的非同构的根树.7.熟练掌握用Huffman算法求最优树的方法.8.熟练掌握求最佳前缀码的方法.9.会用二叉树表示算式.10会求算式的波兰符号法和逆波兰符号法表示的算式.典型习题1.无向树T有n i个i度顶点, i=2,3,…,k, 其余顶点都是树叶, 求T的树叶数t.2.设T为非平凡的无向树, 最大度△(T)≥k（k≥1）, 证明T至少有k片树叶.3.设G'是无向连通图G的无圈子图, 证明G中存在生成树T, 使得E(G')E(T).4.设C为无向图G中一个圈, 边e1与e2在C中, 证明G中存在割集S, 使得e1,e2∈S.5.设G为n阶无向简单图, n≥5, 证明G或必含圈.6.关于顶点和度数选择题.7.画出5阶所有非同构的根树, 并分析它们都是几叉树.8.设T是正则二叉树, 有t片树叶. 证明T的阶数n=2t-1.9.设7个字母在通信中出现的频率如下：a：35% b：20%c：15% d：10%e：10% f：5%g：5%用Huffman算法求传输它们的前缀码. 要求画出最优树, 指出每个字母对应的编码. 并指出传输10n个按上述频率出现的字母, 需要多少个二进制数字.10下图所示的2叉树表达一个算式.（1）用中序行遍法还原算式.（2）用前序行遍法写出该算式的波兰符号法表示式.（3）用后序行遍法写出该算式的逆波兰符号法表示式.。

离散数学——群论

离散数学——群论
18
群的性质
其中Z 【例3】设有群〈Z6，⊕6〉,其中 6={0,1,2,3,4,5}, 】设有群〈 其中 ⊕6是模 加法 试求出群〈Z6，⊕6〉中每一元素 是模6加法 试求出群〈 加法,试求出群 的阶。 的阶。
19
群的性质
【练习3】求群<Z,+>, <Zn， ⊕n>及<P(S), ⊕>中 练习 】求群 及 中 各元素的阶。 各元素的阶。
8
群的基本概念
4) 每个元素存在逆元： 每个元素存在逆元： 对于任意a∈ 设 存在且a 对于任意 ∈S,设a-1存在且 -1 ∈S ，则
a ∗ a −1 = 0 −1 * a = 0 a
a + a −1 + a a −1 = 0 即 a −1 + a + a −1a = 0
17
群的性质
6.群中元素的阶 群中元素的阶 定义】元素的阶(Order)： 【定义】元素的阶 ： 是群， ∈ ， 设<G, >是群，a∈G， 是群 的最小正整数k称 的阶 记作|a| 的阶， 使ak=e的最小正整数 称为a的阶，记作 。 的最小正整数 如果这样的 不存在，则称a的阶是无限的 这样的k不存在 的阶是无限的。 如果这样的 不存在，则称 的阶是无限的。 注: (1) |a| = |a-1| (2) |e| = 1
6
群的基本概念
2) 运算 满足结合律： 运算*满足结合律 满足结合律： 任意a， ， ∈ ， 任意 ，b，c∈S，有 (a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c =a+b+c+ab+ac+bc+abc,且 且 a*(b*c)=a*(b+c+bc)=a+b+c+bc+a(b+c+bc) =a+b+c+ab+ac+bc+abc, 所以， 满足结合律。 所以，(a*b)*c=a*(b*c)，即*满足结合律。 ， 满足结合律

离散数学代数系统中的群与域知识梳理

离散数学代数系统中的群与域知识梳理

离散数学代数系统中的群与域知识梳理离散数学是研究不连续量的数学分支，而代数系统是离散数学的基础概念之一。

在代数系统中，群与域是两个重要的概念。

本文将对离散数学代数系统中的群与域的相关知识进行梳理。

一、群的定义及性质群是代数系统中一种基本的代数结构，它是一个集合与一个二元运算的组合，满足四个条件：封闭性、结合律、单位元和逆元。

1.1 封闭性在群中的任意两个元素进行运算后，结果仍然属于这个群。

即对于群 G 中任意的 a、b，有 a * b ∈ G。

1.2 结合律在群中进行运算的结果不受运算元素的顺序影响。

即对于群 G 中任意的 a、b、c，有 (a * b) * c = a * (b * c)。

1.3 单位元群中存在一个特殊元素，称为单位元，它与群中的任意元素进行运算后得到这个元素本身。

即对于群 G 中任意的 a，有 a * e = e * a = a，其中 e 是群 G 的单位元。

1.4 逆元对于群 G 中的每个元素 a，群中存在一个元素 b，使得 a * b = b * a = e，其中 e 是群 G 的单位元，并且称元素 b 是元素 a 的逆元，记作 b = a^(-1)。

二、群的例子2.1 整数环（Z，+）整数环是一个群，其中的运算为加法。

整数环满足群的四个条件：封闭性、结合律、单位元和逆元。

例如，对于整数环中的任意两个整数 a、b，其和仍然为整数，满足封闭性；整数的加法满足结合律；0 是整数环的单位元，对于任意整数 a，有 a + 0 = 0 + a = a；对于任意整数 a，存在一个整数 -a，使得 a + (-a) = (-a) + a = 0。

2.2 二进制群（Zn，⊕）二进制群是一个有限集合，其中的运算为模 n 的加法（⊕）。

二进制群也满足群的四个条件：封闭性、结合律、单位元和逆元。

例如，对于二进制群中的任意两个元素 a、b，其模 n 的和仍然在这个群中，满足封闭性；模 n 的加法满足结合律；0 是二进制群的单位元，对于任意元素 a，有 a ⊕ 0 = 0 ⊕ a = a；对于任意元素 a，存在一个元素 b，使得 a ⊕ b = b ⊕ a = 0。

离散数学教学图论【共58张PPT】

离散数学教学图论【共58张PPT】

一 、图的基本概念
• 邻接和关联 • 无向图和有向图 • 零图和平凡图 • 简单图 • 完全图（无向完全图和有向完全图） • 有环图
一 、图的基本概念
• 有限图和无限图 设图G为< V，E，Ψ>
（l）当V和E为有限集时，称G为有限图，否则称G为无限图。 （2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足
二、生成树
1、生成树定义：
若无向图的一个生成子图T是树，则称T 为G的生 成树，T中的边称为树枝，E（G）-E（T）称为树T 的补，其中的每一边称为树T 的弦。
在任何图中，结点v的度（degree）d(v)是v所关联边的数目。
第三节 生成树、最短路径和关键路径 由结点a和它所有的后代导的子图，称为T的子树.
∴ T连通且具有m=n-1的图
{e5,e4,e8} ， {e7，e6，e5，e2，e4} 第四节 欧拉图和哈密顿图
第四节 特殊图（欧拉图和哈密顿图等）
第五节 树、二叉树和哈夫曼树
离散数学教学图论
（优选 欧拉图和哈密顿图
(3)2=>3 ∴W(T)≤W(T1) ∴W(ei+1)≥W(f) 二. 哈密顿图的由来—周游世界问题：
第二节 图的矩阵表示 第四节 欧拉图和哈密顿图
证明：若G中一个边割集和一生成 树无公共边，则表示该边割集所分离的结点不在生成树中，这导致与生成树的定义矛盾。 哈密顿图的由来—周游世界问题： c)对新图向下旋转45度。 ei之后将取f而不是ei+1
为该顶点的度,列之和一定为2. • 有向图的关联矩阵 ----- 以节点数为行,边数为列.节点与边无关系,为0,有关系,则起点为1,
终点为-1;列之和一定为0,每行绝对值之和等于该节点的度数;其 中1的个数为该节点的出度,-1的个数为对应节点的入度;所有元 素的和为0,1的个数等于-1的个数,都等于边数m.

离散数学-群

离散数学-群

例1 代数系统 < N; + > 和 < N; ·>、< I; + > 和 < I; ·>、< R; +
> 和 < R; ·> 都是半群，且都是可交换半群。但 < I; – > 和 < R – {0}; / > 不是半群。
例2 代数系统 < 2U; > 和 < 2U; > 都是可交换半群。
例3 设 S 是非空集合，对于任意 a, b S，定义 a b = b，则代
证：对任意的 b S，因为 < S; > 是半群，所以由 的封闭性 可知，b2 = b b S，b3 = b2 b = b b2 S，…。
因为 S 是有限集，所以必存在 j > i，使得 bi = bj。 令 p = j – i，便有 bi (= bj = bp + i) = bp bi。
例8 对于半群 < N; + >， N 的子集
N2 = {2n | n N}，N3 = {3n | n N}，N4 = {4n | n N}，… 都是 < N; + > 的子半群。
例9 对于半群 < S; > 的任一元素 a S，令集合
T = {a, a2, a3, …}， 则 < T; > 是 < S; > 的子半群。
10
例10 对于独异点 < Z; + > , 子集 N2，N3，N4，… （见例8）均
不能形成 < Z; + > 的子独异点； 而 Z2 = {2n | n Z}，Z3 = {3n | n Z}，Z4 = {4n | n Z}，… 都 能形成 < Z; + > 的子独异点。 注： 子半群也是一个半群；子独异点也是一个独异点。 定理 5-5 设 < S; > 是一个可交换的独异点，则 S 的所有幂等 元的集合形成 < S; > 的一个子独异点。

离散数学课件17

离散数学课件17
子群，群的分解
离散数学教学组
回顾
运算及其封闭性 运算的性质 运算表 代数系统 代数系统的同构与同态
提要
子群定义 子群判定定理 有限子群判定定理 元素的阶 陪集，集合的划分 拉格朗日定理
子群
子群
子群的判定定理
子群的判定定理
子群的判定定理
有限子群的判定定理
有限子群的判定定理
群中元素的阶
群中元素的阶
群中元素的阶
群中元素的阶
群中元素的阶
群中元素的阶
陪集
陪集
陪集
陪集
陪集
陪集
陪集
Lagrange定理
Lagrange定理
Lagrange定理Lagrnge定理Lagrange定理
Lagrange定理
教材和练习
伽罗瓦（1811-1832）

离散数学---群环域格

离散数学---群环域格
10
11.1 格的定义与性质
定义11.1 设<S, ≼>是偏序集，如果x,yS，{x,y}都有最小上 界和最大下界，则称S关于偏序≼作成一个格. 求{x,y} 最小上界和最大下界看成 x 与 y 的二元运算∨和∧， 例1 设n是正整数，Sn是n的正因子的集合. D为整除关系，则 偏序集<Sn,D>构成格. x,y∈Sn，x∨y是lcm(x,y)，即x与y的 最小公倍数. x∧y是gcd(x,y)，即x与y的最大公约数.
11
实例
例2 判断下列偏序集是否构成格，并说明理由. (1) <P(B), >，其中P(B)是集合B的幂集. (2) <Z, ≤>，其中Z是整数集，≤为小于或等于关系. (3) 偏序集的哈斯图分别在下图给出.
(1) 幂集格. x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y. (2) 是格. x,y∈Z，x∨y = max(x,y)，x∧y = min(x,y)， 图2 (3) 都不是格. 可以找到两个结点缺少最大下界或最小上界12
14
实例
定义11.10 如果一个格是有补分配格, 则称它为布尔格或布 尔代数. 布尔代数标记为<B,∧,∨,, 0, 1>, 为求补运算. 例9 设B为任意集合, 证明B的幂集格<P(B), ∩,∪, ~, , B> 构成布尔代数, 称为集合代数.
证 (1) P(B)关于∩和∪构成格, 因为∩和∪运算满足交换律, 结合律和吸收律. (2) 由于∩和∪互相可分配, 因此P(B)是分配格. (3) 全下界是空集, 全上界是B. (4) 根据绝对补的定义, 取全集为B, x∈P(B), ~x是x的补元. 从而证明P(B)是有补分配格, 即布尔代数.
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
整数加群<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
例－Klein四元群
设G＝{a,b,c,e}，•为G上的二元运算，见下表。
x,y ∈ R*，x∘y=y
为半群，非独异点。
3
元素的幂运算性质
元素的幂运算定义 设V=<S, >为半群，对任意 x∈S，规定：
x1 = x xn+1 = xn x, n∈Z+
幂运算规则： xn xm = xn+m (xn)m= xnm ，m, n∈Z+
证明方法：数学归纳法
4
独异点的幂
独异点的幂运算定义 x0 = e x1 = x xn+1 = xn x, n∈N
幂运算规则 xn xm = xn+m (xn)m= xnm ， m, n∈N
5
第十七章 群
群的定义与性质
• 群的定义与实例 • 群中的术语
– 有限群、无限群与群的阶 – Abel群 – 群中元素的幂 – 元素的阶
• 群的性质
– 幂运算规则、 – 群方程的解 – 消去律 – 群的运算表的排列
7
群的定义
第十六章 半群
半群与独异点
定义 (1)设V＝<S,>是代数系统，为二元运算，如
果运算是可结合的，则称V为半群 （semigroup）。 (2)设V＝<S,>是半群,若e∈S是关于运算的单 位元,则称V是含幺半群，也叫做独异点 （monoid）。 (P240 定义16.1)
2
实例
(1) <Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>, <C,+>（+是普通加法） 都是半群，除了<Z+,+>外都是独异点，
定义 (P258)设S＝{1,2,…,n}，S上的任何双射函 数σ：S→S称为S上的n元置换。
恒等置换(1)表示无置换
1
(1)
2
(2)
(nn)
29
n元置换的乘法与求逆
两个 n 元置换的乘法就是函数的复合运算 n 元置换的求逆就是求反函数.
例设
15
2 3
3 2
4 1
5 4
,
14
2 3
26
循环群的子群求法
定理(P256 定理17.13) (1) 设G＝<a>是循环群，则G的子群仍是循环
群。 (2) 若G＝<a>是无限循环群，则G的子群除{e}
以外都是无限循环群。 (3) 若G＝<a>是n阶循环群，则对n的每个正
因子d，G恰好含有一个d阶子群。
27
定理说明
• 求循环群的所有子群的方法: • 如果G＝<a>是无限循环群，那么<am>是G的子
3 1
4 2
5 5
1
5
2 1
3 3
4 4
5
2
,
1 1
2 2
3 5
4 3
5
43
1 4
4 1
5
4
2 3
3 2
4 5
5 1
30
n元置换群及其实例
考虑所有的 n 元置换构成的集合 Sn Sn关于置换的乘法是封闭的；置换的乘法满足结合 律；恒等置换(1)是 Sn 中的单位元；对于任何 n元置
17
子群的定义
定义(P253 定义17.6) 设G是群，H是G的非空子 集，如果H关于G中的运算构成群，则称H是G 的子群，记作 H≤G。
若H是G的子群，且HG，则称H是G的真子群， 记作 H＜G。
G和{e}都是G的子群，称为G的平凡子群 。 例：
nZ（n是自然数）是整数加群〈Z,+〉的子群。 当n≠1时,nZ是Z的真子群。
18
子群的判定定理一
定理（判定定理一）设G为群，H是G的非空子集。 H是G的子群当且仅当下面的条件成立： (1) a,b∈H，有 ab∈H。 (2) a∈H，有 a-1∈H。 P253 定理17.9
定理（判定定理二） 设G为群，H是G的非空子集。 H是G的子群当且仅当a,b∈H有ab-1∈H。 定理 17.10
37
陪集
定义(P263 定义17.16) 设H是G的子群，a∈G。令 Ha＝{ha|h∈H}
对于阿贝尔群G，因为G中所有的元素互相都 可交换，G的中心为G。
如果中心是{e}，那么G是无中心的。
22
例
例 设H是群G的子群,x∈G,证明： xHx-1={xhx-1|h∈H}是G的子群,称为H的共轭 子群。
例设G是群，H,K是G的子群。证明 (1) H∩K也是G的子群。 (2) H∪K是G的子群当且仅当 HK 或 KH。
例 在<Z6,>中 2 和 4 是 ? 阶元，3 是 ? 阶元，1
和 5 是 ? 阶元，0 是 ? 阶元
在<Z,+>中0 是 ? 阶元，其它元素是? 阶元
13
群的性质—群的幂运算规则
定理(P250 定理17.2) 设G为群,则G中的幂运算 满足：
(1) a∈G,(a-1)-1＝a。 (2) a,b∈G，(ab)-1＝b-1a-1。 (3) a∈G，anam＝an+m，n,m∈Z。 (4) a∈G，(an)m＝anm，n,m∈Z。 (5) 若G为交换群，则(ab)n＝anbn。
G是所有码字的集合，定义G上的运算*： x*y=z1z2...z7， zi=xiyi
则<G,*>是群。
另外，所有长度为7位的二进制数全体关于构成 群，也称为{0,1}上的n维线性空间。
10
群论中常用的概念或术语
定义(P250 定义17.2 17.3) (1)若群G是有穷集,则称G是有限群，否则称为无
• 回顾关于n元置换的轮换表示,任何n元置 换都可以唯一地表示成不相交的轮换之积, 而任何轮换又可以进一步表示成对换之积, 所以任何n元置换都可以表成对换之积。
36
对换分解式的特征
• 尽管n元置换的对换表示式是不唯一的,但可以 证明表示式中所含对换个数的奇偶性是不变 的。例4元置换τ=（1 2 3 4）只能表示成奇数 个对换之积。如果n元置换σ可以表示成奇数 个对换之积,则称σ为奇置换,否则称为偶置换, 不难证明奇置换和偶置换各有n!/2个。 P262 定义17.15
14
消去律
定理 (P251 定理17.5) G为群,则G中适合消去律， 即对任意a,b,c∈G 有
(1)若ab＝ac，则b＝c。 (2)若ba＝ca，则b＝c。
15
群的性质---运算表排列规则
定理 设 G 为有限群，则 G 的运算表中每行每列 都是 G 中元素的一个置换，且不同的行（或列） 的置换都不相同. 注意：必要条件，用于判断一个运算表不是群.
19
子群的判定定理三
定理(判定定理三) 设G为群，H是G的非空子集。 如果H是有穷集，则H是G的子群当且仅当 a,b∈H有ab∈H。 P254 定理17.11
20
特殊子群1
例 设G为群，a∈G，令H＝{ak|k∈Z}， 即a的所有的幂构成的集合，则H是G 的子群，称为由a生成的子群，记作 <a>。
n0 n0 n0
在 <Z,+> 中有 (2)3=23=2+2+2=6 在<Z3,3 >中有 23=(21)3=13=13131=0
12
群论中常用的概念－元素的阶
定义 设G是群，a∈G，使得等式ak＝e成立的最 小正整数k称为a的阶，记作|a|＝k，这时也称 a为k阶元。 若不存在这样的正整数k,则称a为无限阶元。
G＝{a0＝e,a±1,a±2,…} 这时称G为无限循环群。 (P255)
25
循环群的生成元求法
定理(P255 定理17.12) 设G＝<a>是循环群。 (1)若G是无限循环群，则G只有两个生成元，即a
和a-1。 (2)若G是n阶循环群，则G含有(n)个生成元。