离散数学
标签
绩点/专业课
开发/基础
字数
746 字
阅读时间
4 分钟
速览
命题逻辑
代数结构与群
代数运算
二元运算
集合内运算结果唯一且封闭
性质：
- 满足交换律
- 满足结合律
- 满足分配律（左右）
- 满足
特殊元：
- 单位元：e * x = x（左单位元 e ），同时满足左右
- 零元：θ * x = θ（左零元 θ ），同时满足左右
- 逆元：y * x = e（ x 的左逆元 y），同时满足左右，记为 x^-1
群
有代数系统 < G, * >，* 为二元运算
- G中，* 满足结合律，< G, * > 为 半群
- 满足 1 的同时，G中，* 存在单位元，< G, * > 为 有幺半群
- 满足 2 的同时，G中，* 对所有 G 中元素 x 存在逆元，< G, * > 为 群
- 满足 3 的同时，G中，* 满足交换律，< G, * > 为 交换群（阿贝尔群）
幂运算：半群以上有幂，有幺半群以上有零次幂，群以上有负整数次幂
性质：e.g. < G, * >
定义
- 有限群：G 为有限集
- 有限群的阶数：G 中元素个数
- 平凡群：阶数为1，即只有单位元
- 无限群：G 为无限集
- x 的次数：使 x^n = e 成立的最小正整数 n，此时x被成为 n 次元
- 无限次元：不存在n次元
定理
- 方程的唯一可解性：半群为群的充分必要条件，是 a * x = b 和 a * x = b 在G中都有唯一解
- 消去律：群有消去律
- 有限群的运算表同一行（列）没有相同元素 群的简易判断
子群与陪集
子群是一个集合
- 子群：群< G, * >中，H为G的非空子集，且H对*构成群，则H为G子群
- 平凡子群：{e} 和 G
判定定理：
- ∀ a, b ∈ H, 有 a * b ^-1 ∈ H （充分必要条件）
陪集
设H为群< G, * >的子群，对 a ∈ G，称 aH = {a*h | h ∈ H }为 H 相应于元素 a 的左陪集，Ha 为右陪集
拉格朗日定理：设H为有限群< G, * >的子群，则 | G | = [G:H] x | H |，即子群的阶数一定是群阶数的因子
循环群
群< G, * >，若∃ a ∈ G，使∀ x ∈ G 有 x = a^k，则 a 为生成元，< G, * >为循环群，记为G = < a >
- 若a为无限次元，则只有 a 和 a^-1 两个生成元
- 若a为n次元，则 G 中只有 φ(n) 个生成元， φ(n) 为n的质数因子个数
Kiracoon