代数结构

参考资料

• 抽象代数 - 维基百科
• 群论 - 维基百科
• 格 (序理论) - 维基百科
• 布尔代数 - 维基百科

引入

代数结构（Algebraic Structure）$=$ 集合 $+$ 运算。当我们把整数加法、矩阵乘法、置换合成、字符串拼接这些看似无关的东西放在一起，会发现它们遵循同一套法则（结合、有单位元、可逆……）。抽象出这些 共性、不管元素究竟是什么，就得到了代数结构。

这套「只看运算规律、不看具体对象」的思路，正是计算机科学反复用到的：编码理论、密码学、形式语言、纠错码、哈希，背后都站着群、环、域。本章是 线性代数 的延伸，也是它的一般化。

二元运算

集合 $A$ 上的 二元运算（Binary Operation）是函数：

$$*:A\times A\to A$$

也就是「输入两个元素、输出一个元素」。最关键的隐含要求是 封闭性——结果 仍在 $A$ 中。比如自然数对减法不封闭（$3-5\notin\mathbb{N}$），所以 $(\mathbb{N},-)$ 不是一个合格的代数系统。

运算的性质

名称	定义	直觉
封闭性	$\forall a,b\in A,\ a*b\in A$	不会「算出去」
结合律	$(a*b)*c=a*(b*c)$	不必管加括号的顺序
交换律	$a*b=b*a$	左右可以对调
单位元 $e$	$\forall a,\ a*e=e*a=a$	「什么都不做」的元素
零元 $\theta$	$\forall a,\ a*\theta=\theta*a=\theta$	「一票否决」的元素
逆元 $a^{-1}$	$a*a^{-1}=a^{-1}*a=e$	把 $a$ 撤销回 $e$

单位元、零元若存在则 唯一；在满足结合律时，逆元若存在也 唯一。这些唯一性证明都用同一招——假设有两个，让它们互相作用，立刻推出相等。

tip

结合律是默默无闻的主角。有了它，$a*b*c*\dots$ 才能随便去括号、连乘有意义，逆元才唯一。没有结合律的运算（如向量叉积、减法）会非常难处理，这也是为什么半群、群都把结合律放在第一条。

半群与独异点

按「要求逐渐增多」排成一条链：

• 广群：只要求 封闭。
• 半群（Semigroup）：封闭 $+$ 结合律。
• 独异点 / 含幺半群（Monoid）：半群 $+$ 单位元。
• 群（Group）：独异点 $+$ 每个元素可逆。

例：非空字符串集合在 拼接 运算下是半群；加上空串作单位元就成了独异点。程序里「可结合、有空值」的折叠（fold）操作，数学上就是独异点——这也是为什么 MapReduce 能并行：结合律允许任意分组求和。

群

定义

$(G,*)$ 是 群，当且仅当满足四条：

1. 封闭性。
2. 结合律。
3. 存在单位元 $e$。
4. 每个元素都有逆元。

若还满足 交换律，称 交换群 / 阿贝尔群（Abelian Group）。群抽象的是「可逆的对称操作」——魔方的每一步转动、平面的每一次旋转，都能撤销，合起来就是群。

群里有两条好用的 消去律：$a*b=a*c\Rightarrow b=c$。因为可以两边左乘 $a^{-1}$。

判定是否为群算例

例：判断 $(\mathbb{Z}_4,+)$ 是否为群。运算表（模 $4$ 加法）：

$+$	$0$	$1$	$2$	$3$
$0$	$0$	$1$	$2$	$3$
$1$	$1$	$2$	$3$	$0$
$2$	$2$	$3$	$0$	$1$
$3$	$3$	$0$	$1$	$2$

逐条核对：表内全是 $\set{0,1,2,3}$ 中元素（封闭）；加法 结合；$0$ 是 单位元（$0$ 那行那列原样复制）；每行每列都出现 $0$，故 每个元素有逆（$1$ 与 $3$ 互逆、$2$ 自逆）。四条全满足，是群，且交换，是阿贝尔群。

例：判断 $(\mathbb{Z}_4\setminus\set 0,\times)=(\set{1,2,3},\times)$（模 $4$ 乘法）是否为群。看 $2\times2=4\equiv0\notin\set{1,2,3}$，不封闭，第一条就崩了——根源是 $2$ 与 $4$ 不互素、没有乘法逆。把模数换成素数 $5$，则 $(\set{1,2,3,4},\times)$ 封闭且每个非零元可逆，是群。这解释了为什么 $\mathbb{Z}_p^*$ 要求 $p$ 素。

子群

非空子集 $H\subseteq G$ 在 $G$ 的运算下自身也是群，记 $H\le G$。

判定定理：$H\ne\varnothing$ 且 $\forall a,b\in H,\ a*b^{-1}\in H$，则 $H\le G$。一条式子同时保证了封闭和有逆，很省事。

任何群都有 平凡子群 $\set{e}$ 和 $G$ 本身。

陪集与拉格朗日定理

取定子群 $H\le G$ 和元素 $a\in G$，左陪集 是 $aH=\set{a*h\mid h\in H}$。所有左陪集 大小相同（都等于 $|H|$）、互不相交、并起来 铺满 $G$——也就是说，陪集是 $G$ 的一个划分，背后正是一个等价关系。

由此立得 拉格朗日定理（Lagrange's Theorem）：有限群 $G$ 的任意子群 $H$ 满足

$$|H|\,\big|\,|G|$$

即 子群的阶整除群的阶。陪集个数 $|G|/|H|$ 称 $H$ 在 $G$ 中的 指数。

例：在 $(\mathbb{Z}_6,+)$ 里取子群 $H=\set{0,3}$（$|H|=2$），求全部左陪集。逐个元素算 $a+H$：

$$\begin{aligned} 0+H&=\set{0,3}, & 1+H&=\set{1,4}, & 2+H&=\set{2,5},\\ 3+H&=\set{3,0}, & 4+H&=\set{4,1}, & 5+H&=\set{5,2}. \end{aligned}$$

不同的陪集只有 $\set{0,3},\set{1,4},\set{2,5}$ 三个（$3+H$ 与 $0+H$ 重合，依此类推）。它们大小都是 $2$、互不相交、并起来铺满 $\mathbb{Z}_6$。验证拉格朗日：$|H|=2$ 整除 $|G|=6$，指数为 $6/2=3$，正是陪集个数。

tip

拉格朗日定理威力很大：它直接推出「元素的阶整除群的阶」，进而推出 费马小定理 和 欧拉定理——RSA 加密的数学基石。素数阶的群因为没有非平凡因子，只能是循环群，结构被完全锁死。

例：用群论「秒杀」费马小定理 $a^{p-1}\equiv1\pmod p$（$p$ 素，$p\nmid a$）。乘法群 $\mathbb{Z}_p^*$ 的阶是 $p-1$。由拉格朗日定理，任一元素 $a$ 的阶 $d$ 整除群的阶 $p-1$，写 $p-1=dk$。又 $a^d\equiv1$（阶的定义），于是

$$a^{p-1}=a^{dk}=(a^d)^k\equiv1^k=1\pmod p$$

整个证明不碰任何数论技巧，纯靠「元素的阶整除群的阶」。把 $\mathbb{Z}_p^*$ 换成一般的 $\mathbb{Z}_n^*$（阶为 $\varphi(n)$），同一论证立刻给出 欧拉定理 $a^{\varphi(n)}\equiv1\pmod n$。

循环群

由 单个元素 反复运算生成的群称 循环群（Cyclic Group）：

$$G=\langle a\rangle=\set{a^k\mid k\in\mathbb{Z}}$$

$a$ 称 生成元。元素 $a$ 的 阶 是最小的 $n>0$ 使 $a^n=e$（不存在则阶为无穷）。

• 有限循环群 $\langle a\rangle$（阶 $n$）同构于 $(\mathbb{Z}_n,+)$——「在钟面上转」。
• 无限循环群同构于 $(\mathbb{Z},+)$。

循环群是最简单的群：交换、结构完全由阶决定。

例：求 $(\mathbb{Z}_6,+)$ 的生成元与子群。元素 $a$ 是生成元 $\iff\gcd(a,6)=1$，故生成元是 $1$ 和 $5$。验证 $\langle1\rangle$：$1,2,3,4,5,0$ 跑遍全群；而 $\langle2\rangle=\set{0,2,4}$ 只生成一个 $3$ 阶子群（$\gcd(2,6)=2$）。各元素的阶为 $6/\gcd(a,6)$：$1,5$ 阶 $6$，$2,4$ 阶 $3$，$3$ 阶 $2$，$0$ 阶 $1$。

循环群的子群也都是循环的，且每个阶 $d\mid 6$ 恰有一个 $d$ 阶子群：

$$\langle0\rangle=\set 0,\quad\langle3\rangle=\set{0,3},\quad\langle2\rangle=\set{0,2,4},\quad\langle1\rangle=\mathbb{Z}_6$$

阶分别是 $1,2,3,6$——正好是 $6$ 的全部因子，每个因子对应唯一子群，这是循环群独有的整齐结构。

置换群

$n$ 个元素的所有 置换（双射 $\set{1,\dots,n}\to\set{1,\dots,n}$）在 复合 下构成 对称群 $S_n$，阶为 $n!$，$n\ge 3$ 时 非交换。

置换群极其重要，因为 凯莱定理 说：任何群都同构于某个置换群的子群。换句话说，置换群囊括了一切群的结构，洗牌、魔方、对称操作都是它的实例。

例：把置换 $\sigma=\begin{pmatrix}1&2&3&4&5\\2&3&1&5&4\end{pmatrix}$（即 $1\mapsto2,2\mapsto3,3\mapsto1,4\mapsto5,5\mapsto4$）作 轮换分解。从 $1$ 出发追踪：$1\to2\to3\to1$ 闭合，得轮换 $(1\,2\,3)$；再从 $4$：$4\to5\to4$，得 $(4\,5)$。于是 $\sigma=(1\,2\,3)(4\,5)$，是一个 $3$-轮换与一个对换之积。它的阶是各轮换长度的最小公倍数 $\operatorname{lcm}(3,2)=6$。

例：求两置换的乘法。设 $\tau=(1\,2)$，沿用上面的 $\sigma=(1\,2\,3)(4\,5)$，算复合 $\sigma\tau$（约定先作用右边的 $\tau$、再 $\sigma$）。逐点：$1\xrightarrow{\tau}2\xrightarrow{\sigma}3$，$2\xrightarrow{\tau}1\xrightarrow{\sigma}2$，$3\xrightarrow{\tau}3\xrightarrow{\sigma}1$，$4\mapsto5$，$5\mapsto4$。结果 $1\mapsto3,2\mapsto2,3\mapsto1$，即 $\sigma\tau=(1\,3)(4\,5)$。可见 $S_n$（$n\ge3$）非交换——换成 $\tau\sigma$ 会得到不同结果。

正规子群与商群

若子群 $N\le G$ 满足 左右陪集相等（$aN=Na$ 对所有 $a$），称 $N$ 为 正规子群（Normal Subgroup），记 $N\trianglelefteq G$。交换群的所有子群都正规。

正规性恰好保证陪集之间能良好地定义运算 $(aN)(bN)=(ab)N$，于是所有陪集本身又组成一个群——商群（Quotient Group）$G/N$。$\mathbb{Z}/n\mathbb{Z}=\mathbb{Z}_n$ 就是最熟悉的商群：把整数按模 $n$ 同余「打包」，每个同余类成了新群里的一个元素。

常见群

名称	结构
$(\mathbb{Z},+)$	整数加法群（无限循环）
$(\mathbb{Z}_n,+)$	模 $n$ 加法群（有限循环，阶 $n$）
$(\mathbb{Z}_p^*,\times)$	模素数 $p$ 乘法群（阶 $p-1$，循环）
$S_n$	$n$ 元对称群（阶 $n!$，$n\ge 3$ 非交换）
$D_n$	二面体群（正 $n$ 边形的旋转与翻转，阶 $2n$）

同态与同构

设 $(G,*)$ 与 $(H,\circ)$ 是两个代数系统，映射 $\varphi:G\to H$ 若 保持运算：

$$\varphi(a*b)=\varphi(a)\circ\varphi(b)$$

就称为 同态（Homomorphism）。它表达「先算后映 $=$ 先映后算」——结构在映射下被保留。按 $\varphi$ 是否单 / 满分类：

• 单同态：$\varphi$ 单射。
• 满同态：$\varphi$ 满射。
• 同构（Isomorphism）：$\varphi$ 双射。

同构 的两个结构在代数上 完全相同，只是给元素换了名字。识别同构是抽象代数的核心乐趣：指数函数 $\varphi(x)=e^x$ 是 $(\mathbb{R},+)\to(\mathbb{R}^+,\times)$ 的同构，于是「加法」和「乘法」在它眼里是同一回事——对数计算尺正是吃这碗饭的。

同态的 核 $\ker\varphi=\set{a\mid\varphi(a)=e_H}$ 总是正规子群，且 $G/\ker\varphi\cong\operatorname{im}\varphi$，这就是 同态基本定理。

例：验证 $\varphi:(\mathbb{Z},+)\to(\mathbb{Z}_3,+)$，$\varphi(n)=n\bmod3$ 是同态并求核。保运算：$\varphi(m+n)=(m+n)\bmod3=(m\bmod3)+(n\bmod3)=\varphi(m)+\varphi(n)$，成立。核是映到单位元 $0$ 的元素：

$$\ker\varphi=\set{n\in\mathbb{Z}\mid n\equiv0\pmod3}=3\mathbb{Z}$$

它正是 $3$ 的倍数构成的正规子群。由同态基本定理 $\mathbb{Z}/3\mathbb{Z}\cong\mathbb{Z}_3$——把整数按模 $3$ 打包，商群恰好是 $\mathbb{Z}_3$。核越大，「被抹平」的信息越多：若核是 $\set 0$ 则 $\varphi$ 是单同态（无信息丢失）。

环与域

群只有一种运算，但整数同时有加法和乘法。把 两种运算 一起研究，就到了环与域。

环

$(R,+,\cdot)$ 是 环（Ring），当：

1. $(R,+)$ 是 交换群（加法）。
2. $(R,\cdot)$ 是 半群（乘法满足结合律）。
3. 乘法对加法满足 分配律。

例：$(\mathbb{Z},+,\cdot)$、$(\mathbb{Z}_n,+,\cdot)$、$(M_n(\mathbb{R}),+,\cdot)$（矩阵环，乘法不交换）、多项式环。

域

域（Field）是「最像有理数 / 实数」的环：

1. $(F,+,\cdot)$ 是 交换环。
2. 存在乘法单位元 $1\ne 0$。
3. 每个非零元都有乘法逆元——即非零元在乘法下构成群。

于是域里加减乘除（除 $0$ 外）全部畅通无阻。例：$\mathbb{Q}$、$\mathbb{R}$、$\mathbb{C}$，以及 有限域 $\mathbb{Z}_p$（$p$ 素数）。

tip

整环 是无零因子的交换环（$a\cdot b=0\Rightarrow a=0$ 或 $b=0$）。一条漂亮的定理：有限整环必为域。

这解释了为什么 $\mathbb{Z}_p$（$p$ 素数）是域，而 $\mathbb{Z}_6$ 不是——后者有零因子 $2\cdot 3\equiv 0$，做不到除法。有限域是纠错码（如 QR 码的里德–所罗门码）、AES 加密的运算舞台。

格与布尔代数

格

格（Lattice）是一种特殊的偏序集（参见 集合与关系）。它有两个等价的定义视角：

• 序定义：偏序集 $(L,\preceq)$，任意两元素都有 上确界（并 $\lor$，最小上界）与 下确界（交 $\land$，最大下界）。
• 代数定义：$(L,\lor,\land)$ 配两个运算，满足 交换、结合、吸收 三律。

两个视角等价：序里的「上 / 下确界」就是代数里的 $\lor/\land$。常见例子：

• $(\mathcal{P}(A),\subseteq)$：幂集偏序，$\lor=\cup$，$\land=\cap$。
• $(\mathbb{Z}^+,\,\mid\,)$：整除关系，$\lor=\operatorname{lcm}$，$\land=\gcd$。

若 $\lor,\land$ 互相满足分配律，称 分配格。

布尔代数

布尔代数（Boolean Algebra）是 有界分配格 $+$ 每个元素都有补元 $a'$（满足 $a\lor a'=1$、$a\land a'=0$）。

它是离散数学里「殊途同归」的最佳范例——三件看似无关的事，其实是同一个布尔代数：

• 命题逻辑（参见 数理逻辑）：$\lor,\land,\neg$、真 $1$、假 $0$。
• 集合代数：$\cup,\cap$、补、全集 $U$、空集 $\varnothing$。
• 数字电路：或门、与门、非门、高电平、低电平。

正因如此，逻辑化简、集合恒等、电路优化用的是同一套定律（德摩根、分配、吸收）。计算机的整个数字底层——加法器、控制逻辑、寄存器——都建立在这个布尔代数之上。

例：化简布尔表达式 $ab+a b'+a'b$（用 $b'$ 记补元 $\neg b$）。一步步套定律：

$$\begin{aligned} ab+ab'+a'b &=a(b+b')+a'b &&\text{分配律}\\ &=a\cdot1+a'b &&b+b'=1\\ &=a+a'b &&\text{同一律}\\ &=a+b &&\text{用 }a+a'b=a+b \end{aligned}$$

最后一步是布尔代数特有的化简（由 $a+a'b=(a+a')(a+b)=a+b$ 得来）。原来三项的电路化简成「一个或门」，门数从多个降到一个——这正是数字电路里 逻辑门优化 的日常，卡诺图就是把这套化简图形化。