离散数学 II（知识点汇总）
代数系统
代数系统定义
一个非空集合A，连同若干个定义在该集合上的运算f1,f2,…,fk，所组成的系统就称为一个代数系统，记作<A， f1,f2,…,fk >。
例子
例：<N,＋>,<Z,＋,·>,<R,＋,·>都是代数系统,其中+和·分别表示普通加法和乘法。
例：<Mn(R),＋,·>是代数系统,其中＋和·分别表示n阶(n≥2)实矩阵的加法和乘法。
例：<ρ(S),∪,∩,~ >也是代数系统，其中含有两个二元运算∪和∩以及一个一元运算 ~。
二元运算定义
S为非空集合，从S×S->S的映射： f: S×S->S称为集合S上的一个二元运算。
运算及其性质
二元运算的性质
封闭性
可交换性
可结合性
可分配性
吸收律
等幂性
消去律
特殊的元素性质
\(*\)是定义在集合A上的二元运算
幺元
- 左幺元：对于\(e_l\in A,\ \forall\ x\in A,\ e_l*x=x\)
- 右幺元：对于\(e_r\in A,\ \forall\ x\in A,\ x*e_r=x\)
- 幺元：对于\(e\in A\)，\(e\)既是左幺元又是右幺元
零元
- 左零元：对于\(\theta_l\in A,\ \forall\ x\in A,\ \theta_l*x=\theta_l\)
- 右零元：对于\(\theta_r\in A,\ \forall\ x\in A,\ x*\theta_r=\theta_r\)
- 零元：对于\(\theta\in A\)，\(e\)既是左零元又是右零元
逆元
设在代数系统\(<A,*>\)中，\(*\)为二元运算，e为A中关于\(*\)的幺元，\(a,b\in A\)
- 左逆元：\(b*a=e\)，则b为a的左逆元
- 右逆元：\(a*b=e\)，则b为a的右逆元
- 逆元：b既是a的左逆元又是右逆元，则b为a的逆元，记为a
- 此时有a与b互为逆元
证明逆元且唯一定理
二元运算表中性质的体现
\(*\)是定义在集合A上的二元运算
- 封闭性\(\Leftrightarrow\)运算表中所有元素\(\in A\)
- 可交换性\(\Leftrightarrow\)运算表中所有元素沿对角线对称
- 等幂性\(\Leftrightarrow\)运算表中主对角线元素等于本身
- 零元\(\Leftrightarrow\)该元素运算行列元素与其本身相同
- 幺元\(\Leftrightarrow\)该元素运算行列元素与其对应的行列元素一致
- 逆元\(\Leftrightarrow\)两元素行列相交处都是幺元
半群
广群
成立条件
半群
定义
特性
- A元素有限，则必有等幂元
子半群
独异点
成立条件
特性
- 运算表任意两行两列都不相同
- 若a，b均有逆元，则
- \((a^{-1})^{-1}=a\)
- \(a*b\)有逆元，且\((a*b)^{-1}=b^{-1}*a^{-1}\)
证明是半群或独异点
按定义证明
群和子群
群
定义
阶数、有限群、无限群
如果\(<G,*>\)为群且元素有限，则称为有限群，元素个数称为群的阶数，否则称为无限群
1阶、2阶、3阶、4阶群
1~4阶都有循环群，可以用mod运算推
4阶还有克莱因四元群，如下
特性
- 阶大于1的群中不可能有零元
- $\forall\ a,b\in G,\ \exists\ \(唯一的\)x,\ a*x=b$
- 满足消去律
幂特性
- 除了幺元外，不存在其他等幂元
- 关于逆元,群中任一元素逆元唯一，且有：
- \((a^{-1})^{-1}=a\)
- \((a*b)^{-1}=b^{-1}*a^{-1}\)
- \((a^{n})^{-1}=(a^{-1})^n=a^{-n}\)
运算表特性
- 每一行与每一列都是G元素的一个置换，没有相同元素
- 运算表中任意两行或者两列都不相同
运算
AB={ab|a∈A,b∈B}
A={a|a∈A}
gA={ga|a∈A}
子群
记为H\(\leq\)G，真子群记为H<G
定义
判定条件
- 非空\(S\subseteq G\)，且S也是群
- 非空\(S\subseteq G\)，G为有限群，S中运算封闭
- 非空\(S\subseteq G\)，有\(a*b^{-1}\in S\)
性质
若<H, *>和<K, *>为<G, *>子群，则
- <H\(\cap\)K, *>也是子群
- <H\(\cup\)K, *>是子群 当且仅当 H\(\subseteq\)K或K\(\subseteq\)H
- HK是子群 当且仅当 HK=KH
平凡子群
中心
共轭子群
阿贝尔群和循环群
阿贝尔群 / 交换群
定义
判定
- 是群，且\(\forall\ a,b\in G,\ (a*b)*(a*b)=(a*a)*(b*b)\)
循环群
定义
特性
- 是阿贝尔群
- 如果是有限群，阶数为n，则
- 幺元为a
- 有\(\psi(n)\)个生成元,（欧拉函数，表示小于n且与n互质的正整数个数）
- G的其他生成元即\(a^k\)，k与n互质
- 若阶数无限，则只有两个生成元e和e
元素的阶
定义
最小正整数k使某一元素\(a^k=e\)，则k为a的阶（周期）
性质
a=e \(\iff\) r | k
（k是r的整数倍，即存在整数m，使得k=rm ）
- O(a)= O(a)（元素与其逆元的阶相同）
- r ≤ |G|（元素的阶一定小于等于群的阶）
子群性质
- 循环群的子群也是循环群
- 循环群是无限阶的，则其子群除了{e}也是无限阶的
- 循环群是n阶的，对于每个n的因子，有且只有一个循环子群
置换群和伯恩赛德定理
置换
成立条件
运算
先运用\(\pi_2\)，再运用\(\pi_1\)
- 左复合 $\circ \(：\)\pi_1\circ\pi_2$
- 右复合 $\diamond \(：\)\pi_2\diamond\pi_1$
置换群
定义
对称群
\(S_n\)称为S的对称群
交错群
\(S_n\)中所有偶置换组成的群，记为\(A_n\)，\(|A_n|=n!/2\)
轮换
定义
记法
\((i_1,i_2,...,i_k)\)
对换
定义
性质
任意轮换可以写成对换的乘积。即
(a1 a2…ar)＝(a1 ar)(a1 ar-１)…(a1 a3)(a1 a2)
诱导的二元关系
定义
性质
- 是一个等价关系（条件：自反性、对称性、传递性）
三元素集的置换群
对称群
S={ (1), (1 2), (1 3), (2 3), (1 2 3), (1 3 2) }
交错群
A={ (1), (1 2 3), (1 3 2) }
伯恩赛德定理
\(\pi\)是划分S的置换群的一个置换，\(\phi(\pi)\)指置换中不变元个数
陪集和拉格朗日定理
陪集
定义
性质
元素\(\Rightarrow\)陪集
陪集元素个数相等，\(\forall a\in G\)，|aH|=|H|
a∈H$\iff $aH=H，Ha=H
a∈aH
b∈aH $\iff $ bH=aH
陪集与陪集
- aH和bH关系只有两种
- aH∩bH=\(\varnothing\)（Ha∩Hb=\(\varnothing\)）
- aH=bH（Ha=Hb）
陪集\(\Rightarrow\)元素，a/b属于同一陪集
- aRb \(\iff\) a *b∈H \(\iff\) b∈aH \(\iff\) aH=bH
所有左陪集的集合∑刚好是G的一个划分
特殊关系
划分
- 每个元素非空。不存在空块
- 所有元素并集为G
- 任两个元素交集为空
等价关系
关系R满足自反、对称、传递
- 若<x,y>\(\in\)R，称x等价于y，记作x~y
等价类
有等价关系的元素组成的一个集合，记为[a]
- a称为[a]的代表元素
商集 A/R
以R的所有等价类作为元素的集合称为A关于R的商集
子群的指数
G对H的陪集的集合的基数，即陪集的数目，记为[G:H ]
拉格朗日定理
H为G的子群，则：
- R={<a,b>|a∈G,b∈G且a *b∈H}是G上的一个等价关系。对于a∈G，若记[a]={x|x∈G且<a,x>∈R}，则[a]=aH
- 如果G是有限群，|G|=n，|H|=m，则m|n。
推论
- 素数阶群的子群一定是平凡群。（素数阶的群不存在非平凡子群）
- 设<G,*>是n阶群，则对任意a∈G，有a=e
- 有限群中，元素的阶能整除群的阶
- 素数阶群一定是循环群，且每个非幺元均为生成元
正规子群和商群
正规子群 / 不变子群
定义
判别
\(\forall a\in G\)，
- aH=Ha，（即H\(\unlhd\)G）
- \(\forall h\in H\)，aha\(\in\)H
- aHa\(\subseteq\)H
- aHa=H
如果G是交换群，则G的任何子群都是正规子群
[G:H]=2 ， 则H是G的正规子群
单群
性质
- 正规子群与子群的乘积是子群
- 正规子群与正规子群的乘积是正规子群
- 无传递性
商群
运算
在G/H上定义陪集乘法运算∙，对于任意aH,bH∈G/H, 有
定义
性质
- 商群G/H的单位元是eH（=H）
- 在G/H中aH的逆元是aH
推论
- 若G是交换群，G/H也是交换群
- 商群的阶是G阶数的因子
同态与同构
同态映射 / 同态 ~
定义
同态象
自然同态
群G到商群G/H的同态，为 a\(\rightarrow\)aH
分类
- f:A\(\rightarrow\)B 为满射，f 称为满同态
- f:A\(\rightarrow\)B 为入射，f 称为单一同态
- f:A\(\rightarrow\)B 为双射，f 称为同构映射
同构
f 为同构映射时，称<A,\(\star\)>与<B,*>同构，记为A\(\cong\)B
- 同构关系是等价关系
凯莱定理
任何一个有限群同构于一个置换群。
置换群即运算表中所有行 OR 所有列。
自同态 / 自同构
自身到自身的映射
同态映射性质
在 f 作用下
- <A, $\star $>的所有性质在同态象上保留
- 若同构，则<B, *>拥有<A, $\star $>的所有性质
同态核
定义
Ker(f) = {x|x∈G且f(x)=e’}
性质
- 同态核N为A的正规子群
- f 为单同态 \(\iff\) Ker(f)={e}
- 若Ker(f)=N ，则 f(a)=f(b) \(\iff\) aN=bN
同态基本定理
- 若 f 为A到B的满同态，Ker(f)=N，则A/N\(\cong\)B
- 若h为A自然同态，存在A/N到B的同构g，有f=gh
第一同构定理 / 商群同构定理
- 若 f 为A到B的满同态，Ker(f)=N，H\(\unlhd\)A 且 N\(\subseteq\)H
- 则 A/H \(\cong\) B/f(H)
- 若 H\(\unlhd\)A 且 K\(\unlhd\)A 且 K\(\subseteq\)H
- 则 A/H \(\cong\) (A/K) / (H/K)
环与域
定义
对于<A, +, ·>有两种二元运算的代数系统
为了区别环中的两个运算，通常称＋运算为环中的加法，·运算为环中的乘法。
零元
加法单位元，记为0(\(\theta\))
单位元
乘法单位元，记为1
负元
加法逆元，记为-x
逆元
乘法逆元，记为x
例子
- <R,＋,·> 实数环
- <Q,＋,·>有理数环
- <I,＋,·>整数环
- <M(I),＋, ·>n阶整数矩阵环
- <N , ＋ , ×>模k整数环
- <Z[i], ＋, ·>(Z[i]=a+bi,a,b\(\in\)Z,i=-1)高斯整数环 (复数)
- <R[x] ,＋, ·>R[x]为实数多项式
性质
与理解的加法乘法相同，消去律不一定
- a·\(\theta\)=\(\theta\)·a=\(\theta\)
- a·(–b)=(–a)·b = –(a·b)
- (–a)·(–b)=a·b
- a·(b–c)=(a·b)–(a·c)
- (b–c)·a=(b·a)– (c·a)
特殊环
交换环
含幺环
无零因子环
（等价于乘法消去律）
零因子
整环
定义
（基于乘法运算的性质）
子环
定义
判定定理
\(\forall a,b\in S,a-b\in S,a·b\in S\)
域
定义
例子
- 实数域
- 有理数域
- 〈Z,+, · 〉是域的充要条件是n是素数
域与整环的关系
- 域一定是整环
- 有限整环一定是域
环的同态定义
设V=<A,*,∘>和V=<B,⊛,◎>是两环，其中*、∘、⊛和◎都是二元运算。f 是从A到B的一个映射，使得对\(\forall\)a, b\(\in\)A有：
f(a*b)=f(a)⊛f(b)
f(a∘b)=f(a)◎f(b)
则称f是环V1到环V2的同态映射
分类
如果f是单射、满射和双射，分别称f是单同态、满同态和同构
同态像及其特性
<f(A),⊛,◎>是<A,*,∘>的同态像。
- 任何环的同态像是环
综合例题
设<R,+, · >是环，其乘法单位元记为1，加法单位元记为0，对于任意a,b\(\in\)R,定义
a⊕b=a+b+1,a⊙b=a·b+a+b。求证： <R, ⊕, ⊙ >也是含幺环，并与<R,+, · >同构。