代数结构

第 8 章 代数结构

前面各章研究的都是具体对象：命题、集合、排列、整数取模。这一章做一件更抽象的事：把这些对象上反复出现的运算律（结合律、单位元、逆元、分配律）抽出来当公理，一类公理定义一类代数结构，然后一次性证明关于这一类结构的全部定理。学完之后，你能判断一个”集合 + 运算”到底是不是群、环、域或格，会用子群判定定理和 Lagrange 定理做结构分析，并理解布尔代数为什么是命题逻辑与集合运算的统一骨架——这也是数字电路和布尔检索的形式化基础。

8.1 公理方法的动机

为什么要抽象？因为同一个定理会被重新证明几十次。模 $n$ 加法、复数单位根的乘法、图顶点置换的复合，表面上完全不同，但它们都满足”结合律 + 单位元 + 每个元素有逆元”。把这三条抽出来定义群，那么关于群证出的一切结论（如 Lagrange 定理）立即对全部实例生效。公理方法的另一个好处是反向使用：当一个问题不满足某条公理时，你知道哪些工具会失效——比如不满足交换律的运算，就不能照搬整数的消去习惯而不加验证。

抽象代数里一张反复出现的”谱系”是本章的主线：

$$\text{半群}\subset \text{幺半群}\subset \text{群}\subset \text{环}\subset \text{域},$$

每向右一步，就多要求几条公理，结构就越具体、可用的定理越多。

8.2 半群、幺半群与群

半群（semigroup）：非空集合 $S$ 配上一个二元运算 $\cdot$，满足封闭性（$a\cdot b\in S$）与结合律 $(a\cdot b)\cdot c=a\cdot (b\cdot c)$。

幺半群（monoid）：半群 plus 一个单位元 $e$，使得对任意 $a$ 有 $e\cdot a=a\cdot e=a$。例子：$(\mathbb{N},+)$ 是幺半群（单位元 $0$）但不是群；$({\mathbb{Z}}^{+},\max )$ 是幺半群（单位元 $1$）；字符串在拼接运算下是幺半群（单位元是空串），这是形式语言理论的基础。

群（group）：幺半群 plus 逆元公理：对每个 $a$ 存在 $a^{-1}$ 使 $a\cdot a^{-1}=a^{-1}\cdot a=e$。若还满足交换律 $a\cdot b=b\cdot a$，称为阿贝尔群。运算通常写成加法（阿贝尔群）或乘法。

群的等价刻画中两条最常用（$G$ 为非空集合上的结合运算）：

• 消去律刻画：若 $G$ 有限，且左右消去律成立（$ab=ac\Rightarrow b=c$，$ba=ca\Rightarrow b=c$），则 $G$ 是群。思路：固定 $a$，映射 $x\mapsto ax$ 由消去律是单射，有限集上的单射必是满射，于是存在 $e_a$ 使 $a{e}_a=a$，再证这个 $e_a$ 就是全局单位元、每个元素有逆。
• 除法刻画：$G$ 是群当且仅当对任意 $a,b$，方程 $ax=b$ 与 $ya=b$ 都有解。这比逐条验证单位元、逆元快得多。

元素的阶：使 $a^n=e$ 的最小正整数 $n$ 称为 $a$ 的阶，记 $|a|$；不存在这样的 $n$ 则称无限阶。有限群中每个元素的阶都整除群的阶（这是 Lagrange 定理的直接推论）。

子群判定

$H\subseteq G$ 是子群（记 $H\le G$），指 $H$ 在 $G$ 的运算下自身成群。逐条验四条公理太啰嗦，判定定理把它压成一步：

定理（子群判定） 设 $G$ 是群，$H$ 非空。$H\le G$ 当且仅当对任意 $a,b\in H$ 有 $a{b}^{-1}\in H$。

思路： 取 $a=b$ 得 $e\in H$；取 $a=e$ 得 $b^{-1}\in H$；再由 $a(b^{-1}{)}^{-1}=ab\in H$ 得封闭性；结合律从 $G$ 继承。若 $H$ 有限，判据还可弱化为”封闭性”一条——有限子集只要运算封闭就成群（消去律在 $G$ 中成立，限制到封闭的 $H$ 上仍成立，用上面的消去刻画即得）。

循环群与生成元

若群 $G$ 中存在 $g$ 使得 $G=\{g^n:n\in \mathbb{Z}\}$，称 $G$ 为循环群，$g$ 是一个生成元，记 $G=⟨g⟩$。循环群被其阶完全分类：无限循环群同构于 $(\mathbb{Z},+)$；$n$ 阶循环群同构于 $({\mathbb{Z}}_n,{+}_n)$。

例题 1（验证 $\{1,-1,i,-i\}$ 在复数乘法下成群）

解：记 $G=\{1,-1,i,-i\}$。逐条验证：

1. 封闭性：$1$ 与 $-1$ 相乘不出 $G$；$i\cdot i=-1$，$i\cdot (-i)=1$，$(-i)(-i)=-1$，$(-i)i=1$。所有乘积仍在 $G$ 内。
2. 结合律：复数乘法本身满足结合律，继承自 $\mathbb{C}$。
3. 单位元：$1\in G$，$1\cdot z=z$。
4. 逆元：$1^{-1}=1$，$(-1{)}^{-1}=-1$，$i^{-1}=-i$，$(-i{)}^{-1}=i$，全部落在 $G$ 中。

故 $G$ 是群。进一步，$i^1=i,i^2=-1,i^3=-i,i^4=1$，所以 $G=⟨i⟩$ 是 4 阶循环群。事实上 $G$ 就是 4 次单位根的乘法群。

例题 2（${\mathbb{Z}}_{12}$ 的生成元与子群）

解：${\mathbb{Z}}_{12}=\{0,1,\dots ,11\}$，运算为模 12 加法。元素 $a$ 是生成元当且仅当反复加 $a$ 能遍历全部 12 个元素，当且仅当 $\gcd (a,12)=1$（$a$ 与 $12$ 互素时，存在整数 $x,y$ 使 $ax+12y=1$，于是 $ax\equiv 1(\mathrm{mod}12)$，$1$ 可达则一切可达）。故生成元为

$$\{1,5,7,11\},\text{共 }\phi (12)=4\text{ 个},$$

其中 $\phi$ 是欧拉函数：$\phi (m)$ 等于不超过 $m$ 且与 $m$ 互素的正整数个数。

子群由”每 $d$ 步取一个”给出：对每个整除 $12$ 的 $d$，存在唯一 $d$ 阶子群 $⟨12/d⟩$。全部子群为

$$\begin{array}{rlrlrl}⟨0⟩& =\{0\},& ⟨6⟩& =\{0,6\},& ⟨4⟩& =\{0,4,8\},\\ ⟨3⟩& =\{0,3,6,9\},& ⟨2⟩& =\{0,2,4,6,8,10\},& ⟨1⟩& ={\mathbb{Z}}_{12}.\end{array}$$

恰好对应 $12$ 的全部因子 $1,2,3,4,6,12$——这不是巧合，循环群的子群结构与整除格同构， Lagrange 定理的推论保证了不漏。

置换群与对称群 $S_n$

$n$ 个元素的一一映射称为置换，全体置换在映射复合下构成的群叫对称群 $S_n$，有 $n!$ 个元素；$S_n$ 的任何子群叫置换群。

轮换记号：把置换写成不相交轮换的乘积，例如

$$\sigma =\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 3& 5& 4& 1& 2\end{array}\right)=(134)(25),$$

读作”1 送到 3，3 送到 4，4 送回 1”。每个轮换可继续分解为对换（两元轮换）之积，因此每个置换都是若干对换的积；虽然分解不唯一，但对换个数的奇偶性是唯一确定的，由此每个置换有良定义的奇偶性，偶置换全体构成 $S_n$ 的指数为 2 的子群 $A_n$（交错群）。

一个典型例子：等边三角形的 6 个对称变换（3 个旋转、3 个翻转）在复合下成群，同构于 $S_3$。这也是”群 = 对称的语言”这句话的来源：群元素是保持某结构不变的操作。

8.3 Lagrange 定理

定理（Lagrange） 设 $G$ 是有限群，$H\le G$，则 $|H|$ 整除 $|G|$，且 $|G|=[G:H]\cdot |H|$，其中指数 $[G:H]$ 是 $H$ 在 $G$ 中不同左陪集的个数。

证明思路： 对 $a\in G$，左陪集 $aH=\{ah:h\in H\}$ 满足两条：(1) 任意两个左陪集要么相等要么不相交——若 $aH\cap bH\ne \varnothing$，取公共元 $a{h}_1=b{h}_2$，则 $a=b{h}_2{h}_1^{-1}\in bH$，从而 $aH\subseteq bH$，反向同理；(2) 每个陪集与 $H$ 等势——映射 $h\mapsto ah$ 是双射。于是 $G$ 被划分成 $[G:H]$ 个互不相交、每个大小为 $|H|$ 的陪集，元素总数相乘即得。

推论 1：元素阶整除群阶（元素 $a$ 生成循环子群 $⟨a⟩$，其阶即 $|a|$）。

推论 2（素数阶群必循环）：设 $|G|=p$ 为素数。任取 $a\ne e$，则 $|a|>1$ 且 $|a|\mid p$，只能 $|a|=p$，故 $G=⟨a⟩$。注意这不需要 $G$ 阿贝尔——素数阶群自动是循环群。

例题 3 设 $G$ 是 6 阶群，证明 $G$ 中每个非单位元的阶只能是 2、3 或 6，并由此说明若 $G$ 含有一个 3 阶元 $a$ 和一个 2 阶元 $b$，则 $ab$ 的阶整除 6。

解：对任意 $a\in G$，$⟨a⟩\le G$，由 Lagrange 定理 $|a|=⟨a⟩$ 的阶整除 $6$，即 $|a|\in \{1,2,3,6\}$；$a\ne e$ 时排除 1。$ab\in G$ 当然满足 $(ab{)}^6=e$（因为任何元素的阶都整除 6），故 $ab$ 的阶是 6 的因子。这个”阶只可能是群阶的因子”的推理是 Lagrange 定理最日常的用法。

8.4 环与域

环（ring）：集合 $R$ 配两个二元运算 $+$ 与 $\cdot$，使得 $(R,+)$ 是阿贝尔群，$\cdot$ 满足结合律与封闭性，且分配律把两者联系起来：

$$a(b+c)=ab+ac,(b+c)a=ba+ca.$$

乘法不要求交换、不要求有单位元、不要求有逆。若乘法交换且存在乘法单位元 $1$，称为含幺交换环；若还满足”无零因子”（$ab=0\Rightarrow a=0$ 或 $b=0$），称为整环。注意环里 $ab=0$ 推不出 $a=0$ 或 $b=0$：在 ${\mathbb{Z}}_6$ 中 $2\cdot 3=0$，两个都不是 $0$。

例子的层级值得记住：

• $(\mathbb{Z},+,\cdot )$ 是整环，不是域（$2$ 没有乘法逆元）；
• $({\mathbb{Z}}_n,{+}_n,{\times }_n)$ 是含幺交换环；它是域当且仅当 $n$ 是素数；
• 多项式环 $R[x]$：系数取自环 $R$ 的多项式按通常法则运算，是计算机代数与编码理论的基本对象。

定理 ${\mathbb{Z}}_p$ 是域当且仅当 $p$ 是素数。

证明思路： 若 $p$ 素数，任取 $a\ne 0$，有 $\gcd (a,p)=1$，Bézout 定理给出 $x,y$ 使 $ax+py=1$，模 $p$ 得 $ax\equiv 1(\mathrm{mod}p)$，即 $x$ 是 $a$ 的逆元，故每个非零元可逆。若 $p$ 合数，写 $p=ab$（$1<a,b<p$），则 $a,b$ 在 ${\mathbb{Z}}_p$ 中均非零但 $ab=0$，零因子不可能是可逆元（$a$ 可逆则 $b=a^{-1}ab=0$，矛盾），故非域。$■$

域（field）：每个非零元都有乘法逆元的含幺交换环。域上可以做”加减乘除（除数非零）“全套四则运算，这使它成为线性代数与有限域计算的舞台——${\mathbb{Z}}_2$ 是计算机里一切位运算的算术，$\mathrm{GF}(2^m)$ 是 AES 与 Reed–Solomon 码的底层。

8.5 格

格（lattice） 从序的角度定义：偏序集 $(L,⪯)$ 中任意两元 $a,b$ 都有最小上界（lub，又称并，记 $a\vee b$）与最大下界（glb，又称交，记 $a\wedge b$），就称 $L$ 为格。

格与序的关系是一一对应：给定格，$a⪯b⟺a\wedge b=a⟺a\vee b=b$；反过来，给定一个带两个满足吸收律（$a\vee (a\wedge b)=a$，$a\wedge (a\vee b)=a$）的二元运算 $\vee ,\wedge$ 的代数系统，定义 $a⪯b⟺a\wedge b=a$ 便得到一个偏序，且 $\vee ,\wedge$ 恰是其 lub 与 glb。一句话：“任意两元可比较出上下确界”这个序性质，与吸收律这组代数公理，是同一件事的两种表述。

例题 4（判断一个小偏序集是否为格）

解：设 $P=\{1,2,3,4\}$，序关系为整除（$a⪯b$ 当且仅当 $a\mid b$）。列出可比关系：$1$ 整除一切；$2\mid 4$，$3$ 与 $2$、$3$ 与 $4$ 均不可比。考察 $\{2,3\}$：$P$ 中 $2$ 的倍数只有 $\{2,4\}$，$3$ 的倍数只有 $\{3\}$，两者交集为空——$\{2,3\}$ 连公倍数（上界）都没有，更谈不上最小上界。故 $P$ 不是格。

对比 $D_6=\{1,2,3,6\}$（$6$ 的正因子按整除）：任意两元 $\{2,3\}$ 的 lub 是 $6$、glb 是 $1$；$\{2,6\}$ 的 lub 是 $6$、glb 是 $2$；逐一检查可知任意两元都有 lub 与 glb，故 $D_6$ 是格，其 Hasse 图是一个菱形。事实上每个 $D_n$ 都是格，本章 ${\mathbb{Z}}_{12}$ 的子群按包含关系也构成格——“子对象按包含排序”几乎总是给出格。

特殊格：

• 分配格：$\vee$ 对 $\wedge$ 满足分配律且反之亦然，如 $D_6$；$D_8$（菱形上加一个点，含三元链 $1\prec 2\prec 4\prec 8$）其实分配，而 5 元菱形 $M_3$ 与 5 元链加两元的 $N_5$ 是仅有的两种极小非分配格（Dedekind–Birkhoff 判别）。
• 布尔格：有补的分配格——每个 $a$ 存在补元 $a^{\prime }$ 使 $a\wedge a^{\prime }=0$、$a\vee a^{\prime }=1$，且补元唯一。有限布尔格必同构于某个集合的幂集格 $(\mathcal{P}(S),\subseteq )$，即”元素就是子集、交并就对应集合交并”。

8.6 布尔代数

把布尔格的 $\vee ,\wedge {,}^{\prime }$ 连同最小元 $0$、最大元 $1$ 抽成公理系统，就是布尔代数：一个集合 $B$ 配上运算 $\vee ,\wedge {,}^{\prime }$ 与特异元 $0,1$，满足交换律、分配律（双向）、同一律（$a\vee 0=a$，$a\wedge 1=a$）与补律（$a\vee a^{\prime }=1$，$a\wedge a^{\prime }=0$）。由这四组公理可推出吸收律、幂等律与德摩根律 $(a\vee b{)}^{\prime }=a^{\prime }\wedge b^{\prime }$——布尔代数里所有”显然”的恒等式都能从公理机械推出，这正是公理方法想达到的状态。

布尔代数有三个同构的具体化身，彼此一一对应：

布尔代数	命题逻辑	集合运算
$a\vee b$	$p\vee q$（析取）	$A\cup B$（并）
$a\wedge b$	$p\wedge q$（合取）	$A\cap B$（交）
$a^{\prime }$	$\neg p$（否定）	$\complement A$（补）
$1$	永真式	全集 $U$
$0$	矛盾式	空集 $\varnothing$

以两元布尔代数 $B=\{0,1\}$ 为例，$\vee$ 的真值表就是析取的真值表、$\wedge$ 就是合取、${}^{\prime }$ 就是否定；把”元素”换成”子集”、运算换成并交补，每条恒等式逐字成立。这种三重复用意味着：在任何一个化身里证明的恒等式，其余两个里自动为真。

布尔函数是 $f:\{0,1{\}}^n\to \{0,1\}$，即 $n$ 个布尔输入到 1 个布尔输出的映射。$n$ 元布尔函数共 $2^{2^n}$ 个，每一个都能写成析取范式（选出使 $f=1$ 的全部输入组合，每个组合对应一项合取，再全部析取起来）。把 $\vee ,\wedge {,}^{\prime }$ 翻译成或门、与门、非门，布尔函数就是组合逻辑电路的功能规格——电路综合的任务，本质上是把一个布尔函数化简成门数更少的等价表达式，而布尔代数恒等式（分配律、吸收律、德摩根律）就是化简的合法变换规则。

8.7 常见错误

• 只验结合律就宣布成群。 结合律只保证是半群；单位元和逆元缺一不可。检验清单：封闭 → 结合 → 单位元 → 逆元，四步都要落笔。反过来，在有限集上若已验证运算封闭且结合，再验一条消去律即可推出群（8.2 的刻画），可以省一半力气。
• 把”每个元素有限阶”误当成循环。 有限群中每个元素阶都有限，但生成元未必存在。例如 Klein 四元群 ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$：每个非单位元阶都是 2，但没有任何单个元素能生成整个群。判断循环要找一个元素遍历全群，或用”阶为 $\phi (n)$ 的生成元恰是与 $n$ 互素的元素”。
• 在 ${\mathbb{Z}}_n$ 上直接拿乘法当群运算。 ${\mathbb{Z}}_n$ 对模乘是含幺半群（单位元 $1$），但 $0$ 与非互素元素没有逆元。要成群必须割成 $U(n)=\{a:\gcd (a,n)=1\}$，此时阶为 $\phi (n)$。
• 看到 $ab=0$ 就断言 $a=0$ 或 $b=0$。 这只在整环（包括域）里成立；在 ${\mathbb{Z}}_6$、矩阵环里零因子无处不在。
• 检验格时漏掉”不可比对”。 逐对检查 lub/glb 时要重点盯不相容的元素对：例题 4 里 $P$ 恰败在 $\{2,3\}$ 无上界。另外记得 lub 与 glb 必须落在集合内部。

8.8 练习

1. 判断 $\{-1,0,1\}$ 在普通乘法下是否成群；若不是，指出缺哪条公理。
2. 求 ${\mathbb{Z}}_{10}$ 的全部生成元，并求 $U(9)$ 的全部元素；判断 $U(9)$ 是否循环，若是则给出一个生成元。
3. 设 $G$ 是 10 阶群，$H\le G$。证明 $H$ 的阶只能是 $1,2,5,10$，并证明若 $a\in G$ 且 $a\ne e$，则 $a^5=e$ 或 $a^2=e$ 或 $|a|=10$。
4. 设 $S=\{1,2,3,4,6,12\}$（12 的正因子），序为整除。验证 $(S,\mid )$ 是格，并求 $2\vee 3$、$4\wedge 6$；再判断它是否分配格。

答案：

1. 不是群。封闭性、结合律、单位元（$1$）都满足，但 $0$ 没有逆元：不存在 $x$ 使 $0\cdot x=1$。缺逆元公理（它是含幺半群，不是群）。
2. ${\mathbb{Z}}_{10}$ 的生成元是与 $10$ 互素的元素：$\{1,3,7,9\}$，恰 $\phi (10)=4$ 个。$U(9)=\{1,2,4,5,7,8\}$（与 9 互素的剩余类），阶为 $\phi (9)=6$。它是循环群：$2^1=2,2^2=4,2^3=8,2^4=7,2^5=5,2^6=1(\mathrm{mod}9)$，$2$ 遍历全部 6 个元素，故 $⟨2⟩=U(9)$，生成元为 $2$ 与 $2^5=5$。
3. $H$ 的阶整除 $|G|=10$（Lagrange 定理），故 $|H|\in \{1,2,5,10\}$。对 $a\ne e$，$|a|>1$ 且 $|a|\mid 10$，所以 $|a|\in \{2,5,10\}$，分别对应 $a^2=e$、$a^5=e$、$|a|=10$ 三种情形。
4. 逐对验证：任意 $a,b\in S$，最小公倍数 $\mathrm{lcm}(a,b)\in S$ 正是 $a\vee b$，最大公因数 $\gcd (a,b)\in S$ 正是 $a\wedge b$（例如 $\mathrm{lcm}(3,4)=12\in S$，$\gcd (4,6)=2\in S$），故 $(S,\mid )$ 是格。$2\vee 3=\mathrm{lcm}(2,3)=6$，$4\wedge 6=\gcd (4,6)=2$。它是分配格：$S$ 与 ${\mathbb{Z}}_{12}$ 的子群格同构（$d\leftrightarrow ⟨12/d⟩$），而任何形如 $D_n$ 的因子格都满足分配律——也可直接验证对任意三元的 $\vee$ 对 $\wedge$ 分配。

学习路径

• 返回 离散数学总览
• 返回 数学基础专题首页
• PREV：生成函数
• NEXT：本章是离散数学的最后一章。接下来可以继续学习 图学习，或在总览中回顾全书脉络。