离散数学-代数系统

广义加乘

定义

广义的加法与乘法没有特定的运算形式，主要依赖于它的定义。可以定义它为实数运算，也可定义它为矩阵类运算。 如果不好定义或没有符号，只能使用运算表，限于有限情况。

广义加乘形式类似于 C++ 中的运算符重载。

运算符号由自己定义。

定律

广义加乘的封闭性

交换律

广义交换律是二元运算中存在 x*y=y*x 二元交换普遍存在。

结合律

任意 xyz 在集合 S 中，有 (x+y)+z=x+y+z=x+(y+z)，称该运算在 S 中满足结合律。 实数的加、乘； 集合的并、交； 逻辑的与、逻辑或； 矩阵的加、乘 可满足结合律。

幂等律

任意 x 在集合 S 中，有 x+x=x 称该运算在 S 中幂等。 有些不满足幂等律，但某些元素满足。如普通加法不满足幂等。

分配律

任意 xyz 在集合 S 中，有 x*(y+z)=(x*y)+(x*z), 称 * 对 + 可分配。 如实数加乘，逻辑的与、逻辑或。

吸收律

任意 xy 在集合 S 中，有 x*(x+y)=x,x+(x*y)=x, 则称 * 与 + 满足吸收率。 如 xyz 命题变元。

单位元与零元

实数乘法的 1，实数加法的 0：广义加乘为单位元。

在单位元和零元都存在的基础上，单位元和零元必然不会相同。 例如：

• 乘法中 1 为单位元，0 为零元
• 加法中 0 为单位元，没有零元。

逆元

实数乘的倒数，实数加相反数广义加乘的逆元。

并不是所有元素都一定有逆元。 逆元必须在代数系统集合内，满足运算但是不在系统集合内的，不算逆元。

---

代数系统的相似性

其实类比于 C++ 的类，集合 S 相当于数据成员，运算相当于函数成员。 代数系统中举例子，实数系统就由 <实数,+，*> 构成。

<集合,运算> 构成一个代数系统。

同构

注意：满足一个映射即可说两组代数系统同构。

同余

这个同余在之前的学习中也有提及，好像是关系里的，可以回去看看。

---

群

广群、半群、幺群、群

• 若代数系统封闭，称其为广群。
• 若代数系统封闭、可结合,则其为半群。
• 若V=封闭、可结合、有e，则为幺群(独异点)
• 若封闭，可结合，有 e，则为群。

我们做题，就是判断这个题是否为”群”。 判断这个代数系统是否为群，这个例题： 用运算分别判断封闭，结合，单位元，逆元，从而判断。

Klein 群

和周期挂钩。

Abel 群（交换群）

符合交换律的群即为交换群，又叫作 abel 群。

定理

• 已知 <G,*> 是群，G 是交换群 = 对于任意元素 a, b 有 (a*b)*(a*b)=(a*a)*(b*b) 这是一个充要条件。

群的性质

表表示

群是可以用运算表表示的，对于群，我们看运算表可以获得它的封闭，可结合，逆元，单位元。

群的幂

负数幂怎么操作？取逆元后再进行幂运算。 模运算 ：“模 p 加法意思就是（a+b）mod p 的值”。

元素的周期（元素的阶）

注意，对于群而言，群的阶表达的是群的元素个数，这里解释的是元素的阶。

周期与幂有关，对元素作 n 次幂，让元素转化为单位元，那么可以说该元素的周期为 n。 其实这样子在模运算里也比较难识别的。模运算转化为一种乘法运算也比较方便。

• 单位元的阶（周期）为 1。

这个“陌生”的运算，其实是大学抽象代数里最经典、最简单的群之一，叫做整数模n加法群，记作 (Zn​,+)。我们的 G 集合就是 Z8​ 的一个“二进制马甲”。

对于这种群，有一个求周期的黄金公式：

元素 k 的周期 = m/gcd(k,m)

这里的字母代表：

• m: 群里一共有多少个元素。在这道题里，G有8个元素，所以 m=8。
• k: 我们要计算的那个元素所代表的十进制数。比如 010 代表 2，110 代表 6。
• gcd(k,m): k 和 m 的最大公约数 (Greatest Common Divisor)。就是能同时整除 k 和 m 的最大正整数。

定理

• 1. 幂的普通运算
• 2. 幂与逆元

• 3.群无零元 有零元代表该代数系统无逆元，而群的基本性质就是有逆元，因此冲突，推出群无逆元。注意周期大于等于 2。

• 4. 一元一次群方程有解，且解唯一。
• 5. 群满足消去律
• 6. 群的阶，a^k=e 相当于阶 r|k

子群

类似于子集吧。子群，顾名思义就是一个群的一部分，一个代数系统的一部分。

子群依然符合群的各种性质：

• 封闭
• 可结合
• 单位元
• 每个元素有逆元

子群快捷判断定理

1.（1）任何 a, b 属于 H, 有 a*b 属于 H。 （2）所有 a 属于 H 都有 a^-1 属于 H。 2. 任何 a，b 属于 H 都有 a*b^-1 属于 H。（逆元混沌封闭） 3. 任意 a，b 属于 H 都有 a*b 属于 H。(只封闭)

循环子群

定义：由 a 的幂次方组成的子群称为循环子群或者生成子群，记为 <a,*> 或 <a>

---

陪集

陪集是一种集合而非群，它相当于是一种映射关系的集合。

定理

1.（1）与单位元建立映射的右陪集等于原来的子群。 （2）与常数项建立映射的右陪集等于原来的子群的倍。 2. 子群是对群的划分，是相同关系的集合。 3. 陪集与等价关系 对于等价类 [a], 对于一个子群 H，它的所有的左（或者右）陪集的集合，本质上就是一个子群 H 的等价类的集合。

• 核心都是划分： 等价关系的核心作用是划分 (Partition) 一个集合。陪集的作用也完全一样，它将一个大群 G 划分成若干个大小相等、互不相交的子集（陪集）。每个元素 g∈G 都属于且仅属于一个陪集。

---

拉格朗日定理

特指子群元素的拉格朗日定理。结合刚才的群定理，总结出群的四个定理，前三条回顾。

1. 2. 3. 定理 3 还有一个推论：

拉格朗日定理 或者说，子群的元素个数是母群的因数。

在一个有限群中，任何一个元素的阶，都必然能整除这个群的阶。

也有一种表达：

对于一个有限群 G 和它的任意一个子群 H，群 G 的阶（元素个数，记作 ∣G∣）必然是子群 H 的阶（∣H∣）的整数倍。

这是对于群 G 为有限群而言，子群 H 的陪集数目是有限的。 当群 G 为无限群，陪集数可能有限，可能无限，要依赖选取的子群来确定。拉格朗日定理只适用于有限群。

---

置换群

好像就是把洗牌的指令集合为群。

乘积/复合：σ ∘ τ （或写作 στ），先按 σ 的指令操作，然后按 τ 的指令操作，构成一个新的排列。

注意： 在数学上，运算顺序通常是从右往左的。但是这里 PPT 上这么处理，所以跟着 PPT 的来吧。

定理

就是把”洗牌顺序”，所有的方法集合，构成了一个置换群。

---

环与环域

群 → 环 → 域，是一个能力不断增强，限制越来越严格的过程。环是比群多了一个乘法运算的结构，域是比环多了一个除法运算的结构。