- 离散数学资源
- 离散数学 - 快速指南
- 离散数学 - 资源
- 离散数学 - 讨论
离散数学 - 群论
半群
一个具有二元运算“ο”（复合）的有限或无限集合“S”称为半群，如果它同时满足以下两个条件：-
封闭性 - 对于每个对 (a, b) ∈ S，(a ο b) 必须存在于集合 S 中。
结合律 - 对于每个元素 a, b, c ∈ S，(a ο b) ο c = a ο (b ο c) 必须成立。
示例
正整数集（不包括零）在加法运算下构成一个半群。例如，S = {1, 2, 3, …}
这里封闭性成立，因为对于每个对 (a, b) ∈ S，(a + b) 都存在于集合 S 中。例如，1 + 2 = 3 ∈ S]
结合律也适用于每个元素 a, b, c ∈ S，(a + b) + c = a + (b + c)。例如，(1 + 2) + 3 = 1 + (2 + 3) = 5
幺半群
幺半群是一个具有单位元的半群。集合 S 的单位元（用 e 或 E 表示）是一个元素，使得对于每个元素 a ∈ S，(a ο e) = a。单位元也称为单位元素。因此，幺半群同时满足三个性质：封闭性、结合律、单位元。
示例
正整数集（不包括零）在乘法运算下构成一个幺半群。S = {1, 2, 3, …}
这里封闭性成立，因为对于每个对 (a, b) ∈ S，(a × b) 都存在于集合 S 中。[例如，1 × 2 = 2 ∈ S，依此类推]
结合律也适用于每个元素 a, b, c ∈ S，(a × b) × c = a × (b × c) [例如，(1 × 2) × 3 = 1 × (2 × 3) = 6，依此类推]
单位元性质也适用于每个元素 a ∈ S，(a × e) = a [例如，(2 × 1) = 2，(3 × 1) = 3，依此类推]。这里的单位元是 1。
群
群是一个具有逆元的幺半群。集合 S 的逆元（用 I 表示）是一个元素，使得对于每个元素 a ∈ S，(a ο I) = (I ο a) = a。因此，群同时满足四个性质：i) 封闭性，ii) 结合律，iii) 单位元，iv) 逆元。群 G 的阶是 G 中元素的数量，群中元素的阶是最小的正整数 n，使得 an 是该群 G 的单位元。
示例
N × N 非奇异矩阵集在矩阵乘法运算下构成一个群。
两个 N × N 非奇异矩阵的乘积也是一个 N × N 非奇异矩阵，满足封闭性。
矩阵乘法本身是结合的。因此，结合律成立。
N × N 非奇异矩阵集包含单位矩阵，满足单位元性质。
由于所有矩阵都是非奇异的，因此它们都具有逆元，这些逆元也是非奇异矩阵。因此，逆元性质也成立。
阿贝尔群
阿贝尔群 G 是一个群，对于其中每个元素对 (a,b) ∈ G 都满足交换律。因此，群同时满足五个性质：i) 封闭性，ii) 结合律，iii) 单位元，iv) 逆元，v) 交换律。
示例
正整数集（包括零）在加法运算下构成一个阿贝尔群。G = {0, 1, 2, 3, …}
这里封闭性成立，因为对于每个对 (a, b) ∈ S，(a + b) 都存在于集合 S 中。[例如，1 + 2 = 2 ∈ S，依此类推]
结合律也适用于每个元素 a, b, c ∈ S，(a + b) + c = a + (b + c) [例如，(1 +2) + 3 = 1 + (2 + 3) = 6，依此类推]
单位元性质也适用于每个元素 a ∈ S，(a × e) = a [例如，(2 × 1) = 2，(3 × 1) = 3，依此类推]。这里的单位元是 1。
交换律也适用于每个元素 a ∈ S，(a × b) = (b × a) [例如，(2 × 3) = (3 × 2) = 3，依此类推]
循环群与子群
循环群是一个可以由单个元素生成的群。循环群的每个元素都是某个特定元素的幂，该元素称为生成元。循环群可以由生成元“g”生成，使得该群的每个其他元素都可以写成生成元“g”的幂。
示例
复数集 {1,-1, i, -i} 在乘法运算下构成一个循环群。
有两个生成元：i 和 -i，因为 i1 = i，i2 = -1，i3 = -i，i4 = 1，以及 (-i)1 = -i，(-i)2 = -1，(-i)3 = i，(-i)4 = 1，涵盖了群的所有元素。因此，它是一个循环群。
注意 - 循环群始终是阿贝尔群，但并非每个阿贝尔群都是循环群。有理数在加法运算下不是循环群，但它是阿贝尔群。
子群 H 是群 G 的子集（用 H ≤ G 表示），如果它同时满足四个性质：封闭性、结合律、单位元和逆元。
群 G 的子群 H 不包含整个群 G 称为真子群（用 H < G 表示）。循环群的子群是循环群，阿贝尔子群也是阿贝尔群。
示例
令群 G = {1, i, -1, -i}
则一些子群是 H1 = {1}，H2 = {1,-1}，
这不是子群：H3 = {1, i}，因为 (i)-1 = -i 不在 H3 中
偏序集 (POSET)
偏序集由一个集合和一个二元关系组成，该关系是自反的、反对称的和传递的。“偏序集”缩写为 POSET。
示例
实数集在小于或等于 (≤) 的二元运算下构成一个偏序集。
令集合 S = {1, 2, 3}，运算为 ≤
关系将是 {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3)}
此关系 R 是自反的，因为 {(1, 1), (2, 2), (3, 3)} ∈ R
此关系 R 是反对称的，因为
{(1, 2), (1, 3), (2, 3)} ∈ R 和 {(1, 2), (1, 3), (2, 3)} ∉ R
此关系 R 也是传递的，因为 {(1,2), (2,3), (1,3)} ∈ R。
因此，它是一个偏序集。
有向无环图的顶点集在“可达性”运算下构成一个偏序集。
哈斯图
偏序集的哈斯图是有向图，其顶点是该偏序集的元素，弧覆盖偏序集中的对 (x, y)。如果在偏序集中 x < y，则点 x 在哈斯图中出现在点 y 的下方。如果在偏序集中 x {1, 2, 3} 的子集的偏序集 = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} 由以下哈斯图表示：- 线性序集或全序集是偏序集，其中每对元素都是可比较的。如果元素 a, b ∈ S 满足 a ≤ b 或 b ≤ a，则称元素 a, b ∈ S 是可比较的。三等分律定义了这个全序集。全序集可以定义为一个分配格，它具有属性 {a ∨ b, a ∧ b} = {a, b}，对于集合 S 中的所有 a 和 b 值。 {a, b} 的幂集按 ⊆ 排序是一个全序集，因为幂集 P = {∅, {a}, {b}, {a, b}} 的所有元素都是可比较的。 集合 S = {1, 2, 3, 4, 5, 6} 在运算 x 整除 y 下不是一个全序集。 这里，对于所有 (x, y) ∈ S，x | y 必须成立，但 2 | 3 不成立，因为 2 不整除 3 或 3 不整除 2。因此，它不是一个全序集。 格是一个偏序集 (L, ≤)，对于其中每对 {a, b} ∈ L 都有一个最小上界（用 a ∨ b 表示）和一个最大下界（用 a ∧ b 表示）。LUB ({a,b}) 称为 a 和 b 的并。GLB ({a,b}) 称为 a 和 b 的交。 上图是一个格，因为对于每对 {a, b} ∈ L，都存在 GLB 和 LUB。 上图不是一个格，因为 GLB (a, b) 和 LUB (e, f) 不存在。 下面讨论其他一些格：- 如果格 L 具有最大元素 1 和最小元素 0，则它成为有界格。 如果格 L 是有界格，并且如果格中的每个元素都有一个补元，则它成为补格。如果存在 x(x ∧ x'=0 且 x ∨ x' = 1)，则元素 x 具有补元 x' 如果格满足以下两个分配性质，则称为分配格。 a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) 如果格满足以下性质，则称为模格。 a ∧( b ∨ (a ∧ d)) = (a ∧ b) ∨ (a ∧ d) a ∨ a = a a ∧ a = a a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a示例
线性序集
示例
非全序集的示例
格
示例
有界格
补格
分配格
模格
格的性质
幂等律
吸收律
交换律
$a \lor b = b \lor a$
$a \land b = b \land a$
结合律（Associative Properties）
$a \lor (b \lor c) = (a \lor b) \lor c$
$a \land (b \land c) = (a \land b) \land c$
格的对偶（Dual of a Lattice）
格的对偶是通过交换“$\lor$”和“$\land$”运算得到的。
示例
$\lbrack a \lor (b \land c) \rbrack$ 的对偶是 $\lbrack a \land (b \lor c) \rbrack$