离散基础及数学 13

1离散数学第七章群与环主要内容7.1半群7.2群7.3子群与群的陪集分解7.4循环群与置换群7.5群的同态与同构7.6环与域7.7应用与拓展7.8历史人物与思政27.1半群

34

有幺元e5

6

7

8

9

1011

12

abcdadcbabbbbbcccccdabcd表7.113

abcdadcbabbbbbcccccdabcd表7.114

15

16

17

7.1半群·同态与同构

1819与前面定义类似，根据半群同态映射f是单射(一对一)、满射、双射，把半群同态映射f分别定义半群单一同态映射、半群满同态映射和半群同构映射。如果两个半群，存在一个同构映射，则称一个半群同构于另一个半群。由于代数结构之间的满同态具有保持运算的各种性质，对于半群满同态当然完全适用。20

21

g

h

22

23

24

25

bcaabcbbcaccab表7.1a26上面介绍半群同态及有关定理。接着讨论独异点之间的同态及其有关定理。

27

28

e01ee0100001101表7.1b29

30

3132

337.1半群·积半群把积代数方法应用于特殊一类代数结构——半群，便产生积半群。定义7.6

给定两个半群<S，⊙>和<T，*>。称<S×T，⊗>为<S，⊙>和<T，*>的积半群，其中S×T为集合S与T的笛卡儿积，运算⊗定义如下：<s1，t1>⊗<s2，t2>=<s1⊙s2，t1*t2>，其中s1，s2∈S，t1，t2∈T由于运算⊗是经⊙和*定义的，易知，积半群是个半群。34不难证明下列定理：定理7.2

若半群<S，⊙>和<T，*>是可交换的，则<S×T，⊗>也是可交换的。定理7.3

给定半群<S，⊙>和<T，*>，且e1和e2分别是它们的幺元，则积半群<S×T，>含有幺元<e1，e2>。换言之，若<S，⊙，e1>和<T，*，e2>是独异点，则<S×T，⊗，<e1，e2>>是独异点。35定理7.4

给定半群<S，⊙>和<T，*>，且θ1和θ2分别为它们的零元，则积半群<S×T，⊗>含有零元<θ1，θ2>。定理7.5

给定半群<S，⊙>和<T，*>，且s∈Ｓ的逆元s-1，t∈T的逆元t-1，则积半群<S×T，⊗>中<s，t>的逆元是<s-1，t-1>。7.2.1 群的概念定义7.10

给定代数系统Ｖ＝<G，⊙>，若<G，⊙>是独异点并且每个元素均存在逆元，或满足⊙是可结合的并且关于⊙存在幺元并且G中每个元素关于⊙是可逆的，则称<G，⊙>是群，记为G。群比独异点具有更强的条件。36在半群、独异点、群这些概念中，由于只含有一个二元运算，所以在不发生混淆的情况下，可以将算符省去。例如将x*y写成xy。37

有幺元e

或例7.8<Z，+>，整数加群，<Q，+>，有理数加群，<R，+>，

实数加群，<C，+>，复数加群，他们都是群。38例7.9给定<Z，+>和<Q，*>，其中Z和Q分别为整数集和有理数集，+和*分别是一般意义下的加法和乘法。可知<Z，+>是群，0是幺元，每个元素I∈Z的逆元为–I；<Q，*>不是群，1是幺元，0无逆元。但<Q-{0}，*>是群。39例7.10设G={e，a，b，c}，G上的运算由下表表示，不难验证G是一个群。特征：1.满足交换律2.每个元素都是自己的逆元3.a,b,c中任何两个元素运算结果都等于剩下的第三个元素。这个群为Klein四元群，简称四元群。eabceabceabcaecbbceacbae

40

41

42

7.2.2 群的性质群的基本性质：43（1）封闭性：若a,b∈G，则存在唯一确定的c∈G,使得a*b=c；（2）结合律成立：任意a,b,c∈G，有(a*b)*c=a*(b*c)；（3）单位元存在：存在e∈G,对任意a∈G，满足a*e=e*a=a，称e为单位元，也称幺元；（4）逆元存在：任意a∈G，存在唯一确定的b∈G，a*b=b*a=e（单位元），则称a与b互为逆元素，简称逆元，记作a-1=b。群中元素的幂44定义7.11

设G是群，a∈G，n∈Z，则a的n次幂。

群的性质：幂运算规则

45

群的性质：方程存在唯一解定理7.15

G为群，∀a,b∈G，方程ax=b和ya=b在G中有解且仅有惟一解.46

群的性质：消去律

47

群的性质：元素的阶

48

群的性质：元素的阶

49

群的性质：元素的阶

50群的性质：群的阶定义7.13

若群G是有穷集，则称G是有限群，否则称为无限群。群G的基数称为群G的阶。只含有单位元的群称为平凡群。51

⊙abcaabcbbcaccab群的性质：Abel群定义7.14

给定群G，若⊙是可交换的，则称G是可交换群或G是Abel群。52

群的性质：Abel群

53

547.3

子群与群的陪集分解例如nZ(n是自然数)是整数加群<Z,+>的子群.当n≠1时,nZ是Z的真子群.对任何群G都存在子群.G和{e}都是G的子群，称为G的平凡子群.

定义7.15

设G是群，H是G的非空子集，(1)如果H关于G中的运算构成群，则称H是G的子群,记作H≤G.(2)若H是G的子群，且H⊂G，则称H是G的真子群，记作H<G.如果G是一个群，H是G的一个子群，那么H也是关于G中运算的一个群，因为G中的结合性质在H中也成立。557.3.1

子群

567.3.2

子群的判定

577.3.2

子群的判定

证明：必要性显然.只证充分性.

因为H非空，必存在a∈H.

根据给定条件得aa−1∈H，即e∈H.

任取a∈H,由e、a∈H

得ea−1∈H，即a−1∈H.

任取a，b∈H，知b−1∈H.再利用给定条件得a(b−1)−1∈H，即ab∈H.综合上述，可知H是G的子群.587.3.2

子群的判定

597.3.2

子群的判定

607.3.3

子群的性质：生成子群

617.3.3

子群的性质：中心C

627.3.3

子群的性质：子群的交

637.3.3

子群的性质：子群的格

实例：Klein四元群的子群格如下：64主要内容7.3子群的陪集分解、拉格朗日定理7.4循环群与置换群生成元、n阶循环群、无限循环群置换群：对称群、S37.5群的同态与同构群同态映射：单一同态、满同态、群同构映射7.6.1环的概念与性质7.6.2域的概念7.7应用与拓展657.3.4

子群的陪集分解：陪集

7.3.4

子群的陪集分解：陪集

(证明在下一页)

7.3.4

子群的陪集分解：陪集

7.3.4

子群的陪集分解：陪集(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>}，f6={<1,3>,<2,1>,<3,2>}令G={f1,f2,…,f6}，则G关于函数的复合运算构成群.考虑G的子群H={f1,f2}.做出H的全体右陪集如下：

Hf1={f1∘f1,f2∘f1}=H,Hf2={f1∘f2,f2∘f2}=H

Hf3={f1∘f3,f2∘f3}={f3,f5},Hf5={f1∘f5,f2∘f5}={f5,f3}

Hf4={f1∘f4,f2∘f4}={f4,f6},Hf6={f1∘f6,f2∘f6}={f6,f4}结论：Hf1=Hf2，Hf3=Hf5，Hf4=Hf6.7.3.4

子群的陪集分解：陪集的性质

7.3.4

子群的陪集分解：陪集的性质

7.3.4

子群的陪集分解：陪集的性质

7.3.4

子群的陪集分解：推论

附：左陪集小结

7.3.5

拉格朗日定理

7.3.5

拉格朗日定理每一个G的子群的阶数（和每一个G内元素的阶数）都必须为|G|的因子。

7.3.5

拉格朗日定理例7.24

证明6阶群中必含有3阶元。

7.4循环群与置换群·集合的置换定义7.22

集合的置换：令X是非空有限集合，从X到X的双射函数，称为集合X中的置换，并称|X|为置换的阶。

集合上的所有置换（双射）与复合运算，构成的代数系统是一个群，称为对称群。

由n个元素的集合而构成的所有n!个n阶置换的集合Sn与复合置换运算

构成群<Sn，

>，它便是n次n!阶对称群。

若Q⊆Px=S|x|，则称由Q和

构成的群<Q，

>为置换群。807.4.2置换群

+01001110那么f是一个同态。817.4.2置换群

827.4.2置换群

837.4循环群与置换群

847.4.1循环群85

7.4.1循环群

定理7.27

（1）设G=<a>是循环群，则G的子群仍是循环群。

（2）若G=<a>是无限循环群，则G的子群除{e}以外都是无限循环群。

（3）若G=<a>是n阶循环群，则对于n的每个正因子d，G恰好含有一个d阶子群。867.4.1循环群

87

7.4.2置换群

定义7.29

一个置换群是一个群G，其元素是一个给定集M的置换，而其群作用是G中的置换（可以看作是从M到自身的双射）的复合；其关系经常写作(G,M)。注意所有置换的群是对称群；置换群通常是指对称群的一个子群。887.4.2置换群

897.4.2置换群

907.4.2置换群运算表（表7.5）917.4.2置换群92

7.5群的同态与同构

群同态保持幺元，逆元和子群。937.5群的同态与同构

根据g是单射、满射和双射，群同态分别称为群单一同态映射、群满同态映射和群同构映射。947.6环与域7.6.1环的概念与性质

为了区分环中的两个运算，通常称+为环中的加法，·为环中的乘法，把⟨R,+⟩称为加法群，⟨R,·⟩称为乘法半群。而且还规定，运算的顺序是先计算乘法再计算加法。2026/9/1495957.6.1环的概念与性质

2026/9/1496967.6.1环的概念与性质

2026/9/1497977.6.1环的概念与性质

2026/9/1498987.6.1环的概念与性质

2026/9/1499997.6.1环的概念与性质

2026/9/141001007.6.1环的概念与性质

2026/9/141011017.6.2域的概念

2026/9/141021027.6.2域的概念

2026/9/141031037.6.2域的概念

2026/9/141047.6.2域的概念

2026/9/141051057.7应用与拓展

2026/9/141061067.7.1

群与密码算法

给定一个素数p，元素个数为p的有限域GF(p)被定义为整数{0,1,…,n-1}的集合Zp，其运算为模p的算术运算。在整数{1,2,…,n-1}的集合Zn，在模n的算术运算下，构成一个交换环。Zn中的任一整数有乘法逆元当且仅当该整数与n互素。当n为素数，Zn中所有非零整数都与n互素，此时Zn中所有非零整数都有乘法逆元。2026/9/141071077.7.1

群与密码算法

下面介绍在GF(P)中求乘法逆元。如果gcd(m,b)=1（gcd：greatestcommondivisor最大公约数），那么b有模m的乘法逆元。对于正整数b<m，存在b-1<m使得bb-1=1modm。求出gcd（m,b）之后，当gcd(m,b)为1时，算法返回b的乘法逆元，即只有当

b

和

m

互质（即它们的最大公约数是

1）时，b

才存在乘法逆元。扩展欧几里得算法就是用来找到这个逆元的有效算法，其核心是通过一系列的除法和替换操作，逐步推进到最终的解。以下是算法的步骤：2026/9/141081087.7.1

群与密码算法

初始化：将A和B初始化为(1,0,m)和(0,1,b)。这里的A和B分别代表我们将要操作的数对。终止条件：如果B3

（数对B的第三个数，即b的当前值）为0，说明b和m不互质，乘法逆元不存在。如果B3

为1，说明我们已经找到解，此时的B2

就是b的逆元。逐步逼近：计算商Q=floor(A3/B3)。更新A和B的值，逐步缩小范围，最终逼近解。通过这些步骤，算法会不断地将问题简化，直到找到解或者确认解不存在。2026/9/141091097.7.1

群与密码算法

2026/9/141101107.7.1

群与密码算法

注意到，如果gcd(m,b)=1，在最后一步我们将得到B3=0和A3=1。因此，在上一步，B3=1。mB1+bB2=B3mB1+bB2=1bB2=1-mB1bB2=1(modm)此时B2为b的模m乘法逆元。利用上面介绍的方法，求550在有限域集合Zp=1759中的乘法逆元（即求解gcd(1759,550)=1）。2026/9/141111117.7.1

群与纠错编码

2026/9/141121127.7.1

群与纠错编码

数据通信的抽象数学模型可以表示成以下最基本的形式：2026/9/14113113图7.2

信道的抽象模型

7.7.1

群与纠错编码

2026/9/141141147.7.1

群与纠错编码

2026/9/141151157.7.1

群与纠错编码

2026/9/141161167.7.1

群与纠错编码

2026/9/141171177.7.1

群与纠错编码

2026/9/14118118位号001010011100101110111编码值校验位/信息位7.7.1

群与纠错编码

2026/9/141191197.7.1

群与纠错编码

2026/9/141201207.7.1

群与纠错编码

NVIDIAGPU的纠错机制：以NVIDIAH100为例，它的HBM3/HBM2e显存子系统支持SECDEDECC（单比特纠错、双比特检测）来保护数据完整性，并且不只显存，连关键存储结构（如L2、L1Cache、SM内寄存器文件等）也会做ECC保护；同时H100还支持把ECC校验位放在独立区域的“SidebandECC”（相对InlineECC），并提供诸如内存行重映射（RowRemapping）等RAS功能：当某些内存行反复产生ECC错误时，可在启动/维护窗口把坏行替换为预留的“好行”，减少继续出错的概率。这样做的直接意义是：在长时间AI训练/推理中，把随机硬件噪声带来的数据破坏尽可能“纠正或隔离”，避免模型质量被悄悄拉偏。2026/9/141211217.7.1

群与纠错编码

这套纠错与RAS机制本质上是在保障AI计算的完整性（integrity）与可用性（availability）：即使出现不可纠正的ECC错误，也尽量做到错误隔离（ErrorContainment），把影响限制在触发错误的应用上，其它GPU工作负载继续运行；再配合动态页下线（DynamicPageOfflining）与行重映射等手段，把已知有问题的显存页/行标记为不可用或在硬件层替换，从而降低“一个硬件错误拖垮整卡/整机”的风险。这对多租户AI集群、长跑训练作业、以及对结果一致性要求高的推理服务都非常关键。我们仅给出了最简单的情况。包括海明码在内的整个编码学需要建立在十分复杂且严格的数学理论基础之上，尤其是抽象代数理论。2026/9/141221227.7.2

群与网络安全：GoogleGboardGoogleGboard是谷歌推出的手机输入法（支持Android与iOS），不仅提供基础输入功能，还集成了大量AI能力，如下一词预测、自动纠错和智能建议等。这些模型需要不断通过用户使用数据进行优化，但用户输入内容具有高度隐私性。为此，Gboard采用了“联邦学习（FederatedLearning）”机制：模型训练或更新在用户设备本地完成，只上传模型更新参数，而不上传原始文本数据，从而在提升模型效果的同时保护用户隐私。这一体系中，Gboard结合了安全聚合（SecureAggregation）机制来保障网络安全与数据隐私。2026/9/141231237.7.2

群与网络安全：GoogleGboard安全聚合的关键技术之一是迪菲–赫尔曼密钥交换（Diffie–Hellman,DH）及其椭圆曲线版本椭圆曲线迪菲–赫尔曼密钥交换（EllipticCurveDiffie–Hellman,ECDH）。DH/ECDH的数学基础是一个循环群（工程中常用椭圆曲线点群）：各客户端先在群上进行密钥协商，得到与其它客户端的共享秘密（共享随机性），再通过密钥派生函数把共享秘密扩展为伪随机序列，生成“成对掩码”（pairwisemasks）。随后，每个客户端将自己的本地模型更新（如梯度/权重增量向量）与若干掩码相加后上传，使服务器在传输链路被窃听或服务器本身不可信的情况下，仍无法从单个上传向量中还原该用户的更新信息。2026/9/141241247.7.2

群与网络安全：GoogleGboard

2026/9/141251257.7.2

群与网络安全：GoogleGboardrdGboard与“群”的关系是直接且关键的：群结构为DH/ECDH提供数学基础，使客户端能够在不安全网络环境下安全协商共享随机性，从而实现安全聚合。这种基于群的密码学机制保障了端侧AI训练过程中的隐私性与抗窃听能力，使服务器只能学习到整体统计信息，而无法获取单个用户的敏感输入数据，体现了群论在真实AI产品中的实际应用价值。2026/9/14126126历史人物与事件中国群表示论的奠基人——著名数学家段学复：段学复（1914—2005），陕西华县人。1936年毕业于清华大学算学系，1943年获美国普林斯顿大学博士学位，并成为普林斯顿高等研究院数学部研究人员。1946年回国，任清华大学数学系教授，1952年起任北京大学数学力学系教授。段学复在有限群的模表示论特别是指标块及其在有限单群和有限复线性群构造研究中的应用方面取得突出成果。指导学生用表示论和有限单群分类定理彻底解决了著名的Brauer第39问题、第40问题。在代数李群研究方面与国外学者合作完成了早期奠基性成果。在有限P群方面取得一系列研究成果。在数学应用于国防科研和国防建设方面作了大量工作。2026/9/14127127历史人物与事件段学复从小成绩优异，并对数学充满兴趣。段学复于1932年考入清华大学的数学系。当时，日本帝国主义正在不断扩大侵华战争。在民族生死存亡的紧要关头，原本不过问业务书外事的段学复也受到了爱国主义的洗礼，他参加了1935年12月9日和12月16日的两次示威游行，以及1936年2月29日