离散数学 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上的一个二元运算。

运算及其性质

二元运算的性质

封闭性

• Premise：\(*\)是定义在集合A上的二元运算， \(\forall\ x,y\in A\)
• Condition：\(\ x*y\in A\)
• Summary：\(*\)在A上是封闭的

可交换性

• Premise：\(*\)是定义在集合A上的二元运算， \(\forall\ x,y\in A\)
• Condition：\(x*y=y*x\)
• Summary：\(*\)在A上是可交换的

可结合性

• Premise：\(*\)是定义在集合A上的二元运算， \(\forall\ x,y,z\in A\)
• Condition：\((x*y)*z=x*(y*z)\)
• Summary：\(*\)在A上是可结合的

可分配性

• Premise：\(*,\triangle\)是定义在集合A上的二元运算， \(\forall\ x,y,z\in A\)
• Condition：\(x*(y\triangle z)=(x*y)\triangle (x*z)\)、\((y\triangle z)*x=(y*x)\triangle (z*x)\)
• Summary：在A上，\(*\)对于$\triangle $是可分配的

吸收律

• Premise：\(*,\triangle\)是定义在集合A上的二元运算， \(\forall\ x,y\in A\)
• Condition：\(x*(x\triangle y)=x\)、\(x\triangle (x*y)=x\)
• Summary：\(*\)和$\triangle $在A上满足吸收律

等幂性

• Premise：设\(*\)是定义在集合A上的二元运算， \(\forall\ x\in A\)
• Condition：\(x*x=x\)
• Summary：\(*\)在A上是等幂的

消去律

• Premise：设\(*\)是定义在集合A上的二元运算， \(\forall\ x,y,z \in A\)
• Condition：（左消去律）\(x*y=x*z\Rightarrow y=z\)、（右消去律）\(y*x=z*x\Rightarrow y=z\)
• Summary：\(*\)在A上是满足消去律的

特殊的元素性质

\(*\)是定义在集合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^-1
  • 此时有a与b互为逆元

证明逆元且唯一定理

• Premise：\(\forall\ a\in A\)，e为A的逆元，\(*\)为A的二元运算
• Condition：a都有左逆元，\(*\)可结合
• Summary：a的左逆元为a的逆元且唯一

二元运算表中性质的体现

\(*\)是定义在集合A上的二元运算

• 封闭性\(\Leftrightarrow\)运算表中所有元素\(\in A\)
• 可交换性\(\Leftrightarrow\)运算表中所有元素沿对角线对称
• 等幂性\(\Leftrightarrow\)运算表中主对角线元素等于本身
• 零元\(\Leftrightarrow\)该元素运算行列元素与其本身相同
• 幺元\(\Leftrightarrow\)该元素运算行列元素与其对应的行列元素一致
• 逆元\(\Leftrightarrow\)两元素行列相交处都是幺元

半群

广群

成立条件

• \(*\)运算封闭

半群

定义

• \(*\)运算封闭
• \(*\)运算可结合

特性

• A元素有限，则必有等幂元

证：

∵ <S, *>是半群，∴对于\(\forall\)b \(\in\)S，由运算*封闭可知:
b²=b*b\(\in\)S，b² *b=b*b²=b³\(\in\)S ，b⁴，b⁵… \(\in\)S
∵ S有限，∴必定\(\exists\)i,j，j>ｉ，有bⁱ=b^j（第一轮）
∴ bⁱ =b^j =b^j-i * bⁱ
令p=j-i ，则有 bⁱ =b^p * bⁱ
∴ 对任意q≥i, 有b^q= b^p *b^q （第二轮）
又∵p≥1 ∴$\exists $k,有kp≥i，则有b^kp=b^p *b^kp （第三轮）
由b^kp=b^p *b^kp得： b^kp=b^p *b^kp=b^p *(b^p *b^kp)=…=b^kp *b^kp
∴令a=b^kp \(\in\)S 则a*a=a，∴b^kp是等幂元。

子半群

• \(B\subseteq A\)
• \(*\)在B上运算封闭

独异点

成立条件

• 为半群
• 含幺元

特性

• 运算表任意两行两列都不相同

证：

设独异点中幺元为e，对于任意 a,b?S且a≠b，总有
（1）∵a*e=a ≠ b=b*e
由a，b任意性， 有<S, *>运算表中任两行不同；
（2）∵e*a = a ≠ b = e*b
由a，b任意性，有<S, *>运算表中任两列不同。

• 若a，b均有逆元，则
  • \((a^{-1})^{-1}=a\)
  • \(a*b\)有逆元，且\((a*b)^{-1}=b^{-1}*a^{-1}\)

证：

a) ∵a^-1是a的逆元

? ∴a^-1既是a的左逆元又是a的右逆元

? 即：a^-1 *a=a *a^-1=e

? ∴a既是a^-1的右逆元又是a^-1的左逆元，

? ∴ a是a^-1的逆元 即(a^-1)^-1=a

b) 要证(a *b)^-1=b^-1 *a^-1，即证b^-1 *a^-1为a*b的逆元。

∵(a*b) *(b^-1 *a^-1)=a* (b*b^-1) *a^-1=a*e*a^-1=e

∴b^-1 *a^-1是a*b的右逆元，

又∵（b^-1 *a^-1）*（a *b）=b^-1 *（a^-1 *a）*b＝e

∴b^-1 *a^-1是a*b的左逆元，

∴(a*b)^-1=b^-1 *a^-1

证明是半群或独异点

按定义证明

群和子群

群

定义

• 运算封闭
• 可结合
• 存在幺元e
• 对于每一个元素\(x\in G\)，存在逆元$x^{-1}

阶数、有限群、无限群

如果\(<G,*>\)为群且元素有限，则称为有限群，元素个数称为群的阶数，否则称为无限群

1阶、2阶、3阶、4阶群

1~4阶都有循环群，可以用mod运算推

4阶还有克莱因四元群，如下

特性

• 阶大于1的群中不可能有零元

证：

（1）当群的阶为1时，它的唯一元素视作幺元e；

（2）设|G|>1且群<G, *>中有零元q，那么群中

? ?x∈G，*都有q*x=x*q=q ≠ e

所以零元q不存在逆元，这与<G, *>是群矛盾。

• $\forall\ a,b\in G,\ \exists\ \(唯一的\)x,\ a*x=b$

证：

（1）存在性
设群<G, *>的单位元为e，令x=a^-1 *b， 则
a*x＝a*(a^-1 *b)＝(a*a^-1) *b＝e*b=b
所以x＝a^-1 *b是方程a*x＝b的解。
（2）唯一性
若还有x′∈G， 使得a*x′=b， 则
x′=e*x′
=(a^-1 *a)*x′=a^-1 *(a*x′)=a^-1 *b=x
故x＝a^-1 *b是方程a*x＝b的唯一解。

• 满足消去律

证：

a*b＝a*c

$\Rightarrow $ a^-1 *(a*b)＝a^-1 *(a*c)

$\Rightarrow $ (a^-1 *a) *b＝(a^-1 *a)*c

$\Rightarrow $ e*b＝e*c

$\Rightarrow $ b＝c

幂特性

• 除了幺元外，不存在其他等幂元
• 关于逆元,群中任一元素逆元唯一，且有：
  • \((a^{-1})^{-1}=a\)
  • \((a*b)^{-1}=b^{-1}*a^{-1}\)
  • \((a^{n})^{-1}=(a^{-1})^n=a^{-n}\)

证：

已学定理5-2.4：设代数系统<A, *> ， A中存在幺元e，且$\forall $x∈A，都存在左逆元，若*是可结合的运算，那么<A, *> 中任何一个元素的左逆元必定也是该元素的右逆元，且每个元素的逆元唯一。

证明：

∵群满足结合律，且群中每个元素都有逆元，

∴每个元素都有左逆元，

∴每个元素的逆元唯一。

运算表特性

• 每一行与每一列都是G元素的一个置换，没有相同元素
• 运算表中任意两行或者两列都不相同

运算

AB={ab|a∈A,b∈B}
A^-1={a^-1|a∈A}
gA={ga|a∈A}

子群

记为H\(\leq\)G，真子群记为H<G

定义

• 为一个群的非空子集
• 也为群

判定条件

1. 非空\(S\subseteq G\)，且S也是群
2. 非空\(S\subseteq G\)，G为有限群，S中运算封闭
3. 非空\(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

平凡子群

\(S=\{e\}\quad OR\quad S=G\)

中心

对于\(C=\{y|y*a=a*y,y\in G\}\)，则<C, *>为子群，称为G的中心

共轭子群

若H为G子群，则xHx^-1={x*h*x^-1|h ∈H}也是G的子群，称xHx^-1是H的共轭子群

阿贝尔群和循环群

阿贝尔群 / 交换群

定义

• 是群
• \(*\)可交换

判定

• 是群，且\(\forall\ a,b\in G,\ (a*b)*(a*b)=(a*a)*(b*b)\)

证：

充分性 即证a*b=b*a。
∵ (a*b)*(a*b)=(a*a)*(b*b) 且<G,*>是群，*可结合
∴ a*(b*a)*b=a*(a*b)*b
∴ a^-1 *(a*(a*b)*b)*b^-1=a^-1 *(a*(b*a)*b)*b^-1
即有：a*b=b*a， ∴ <G,*>是阿贝尔群。
必要性 ∵ <G,*>是阿贝尔群，
∴对?a,b∈G，有：a*b=b*a
∴ (a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b=(a*a)*(b*b)

循环群

定义

\(\exists\ a\in G,\ \forall\ b\in G\)，b都能表示成a的幂，a称为生成元

特性

• 是阿贝尔群
• 如果是有限群，阶数为n，则
  • 幺元为aⁿ
  • 有\(\psi(n)\)个生成元,（欧拉函数，表示小于n且与n互质的正整数个数）
  • G的其他生成元即\(a^k\)，k与n互质
• 若阶数无限，则只有两个生成元e和e^-1

元素的阶

定义

最小正整数k使某一元素\(a^k=e\)，则k为a的阶（周期）

性质

• a^k=e \(\iff\) r | k

  （k是r的整数倍，即存在整数m，使得k=rm ）

证：

充分性：r | k \(\Rightarrow\) a^k=e

设 r | k，则存在整数m，使得k=rm，

? a^k= a^rm=(a^r)^m=e^m=e

必要性：a^k=e \(\Rightarrow\) r | k

若a^k=e，由带余除法，一定存在整数p,q，使得

k=pr+q(0≤q<r)，于是a^k=a^pr+q=a^pr *a^q=(a^r)^p *a^q =(e)^p *a^q =e*a^q =a^q =e （a^k=e）

∵ r是a的阶,即使得a^r=e的最小正整数

∴只有q=0才可能有a^q =e， ∴ k=pr 即r | k。

• O(a)= O(a^-1)（元素与其逆元的阶相同）

证：

O(a)= O(a^-1)（元素与其逆元的阶相同）

证：?a∈G，a的阶为r, a^-1的阶为r’,

则 (a^-1)^r’=e ，a^r=e

∵ (a^r)^-1 *a^r=e 且a^r=e，
∴ (a^r)^-1=e（ (a^r)^-1与e做运算=e，则(a^r)^-1必=e）
由红色部分可得(a^r)^-1=(a^-1)^r’=e－－－－－①
∵ <G,*>是群，即(aⁿ)^-1=(a^-1)ⁿ成立，则
(a^r)^-1=(a^-1)^r 成立－－－－－②
由①②可得，(a^-1)^r =(a^-1)^r’=e
∵ 已知r’是a^-1的阶，即r’是使得(a^-1)^k =e的最小正整数，
∴ r=mr’（m为正整数),即r’|r。 (定理中的(1)刚证明过)
同理可证r|r’。
(a^-1)^r’= (a^r’)^-1=e
∵ (a^r’)^-1 * a^r’=e
∴ a^r’=e
∵ 已知r是a的阶，即r是使得(a)^r =e的最小正整数，
∴ r’=mr (m为正整数),即r|r’ .由r’|r与 r|r’即可证得r=r’。

• r ≤ |G|（元素的阶一定小于等于群的阶）

证：

一个元素a, a的阶是r,且r>|G|,则由a可生成一个集合S={a,a²,a³,…,a^r-1,a^r}，因为运算*封闭，所以S$\subseteq \(G, 则S的元素个数小于|G|. 然后证明a,a^2^,a^3^,…,a^r-1^,a^r^各不相同。 若不然，假设S中存在两个元素相同： a^i^=a^j^,其中1≤i<j≤r，就有e=a^j-i^ (1≤ j-i<r,a^i^=a^j^右侧同\*a-i)，而已知r是使得a^r^=e的最小整数。 a,a^2^,a^3^,…,a^r-1^,a^r^都各不相同，即集合S的元素个数大于|G|，与S\)\subseteq $G矛盾。综上，r≤|G|

子群性质

• 循环群的子群也是循环群
• 循环群是无限阶的，则其子群除了{e}也是无限阶的
• 循环群是n阶的，对于每个n的因子，有且只有一个循环子群

置换群和伯恩赛德定理

置换

成立条件

• 对于非空集合S，\(S\rightarrow S\)的双射称为S的置换

运算

先运用\(\pi_2\)，再运用\(\pi_1\)

• 左复合 $\circ \(：\)\pi_1\circ\pi_2$
• 右复合 $\diamond \(：\)\pi_2\diamond\pi_1$

置换群

定义

• 具有n个元素的集合S中所有的置换组成的群\(<S_n,\circ>\)，其中元素个数有 n! 个
• 任意\(<S_n,\circ>\)的子群都是S上的置换群

对称群

\(S_n\)称为S的对称群

交错群

\(S_n\)中所有偶置换组成的群，记为\(A_n\)，\(|A_n|=n!/2\)

轮换

定义

设s是S={1,2,…,n}上的n元置换，且：

\[s(i_1)=i_2, s(i_2)=i_3, …, s(i_k-1)=i_k, s(i_k)=i_1 \]

且\(\forall\ x\in S,\ x\ne i_j (j=1,2,…,k)\)，有 s(x)=x（即s 不改变其余元素），称s是S上的一个k阶轮换, 当k=2, s也称为对换。

记法

\((i_1,i_2,...,i_k)\)

对换

定义

k=2时

性质

• 任意轮换可以写成对换的乘积。即

  (a1 a2…ar)＝(a1 ar)(a1 ar-１)…(a1 a3)(a1 a2)

诱导的二元关系

定义

设\(<G,\circ>\)为S的一个置换群，则其诱导的二元关系有

\[R=\{<a,b>|\pi(a)=b,\ \pi\in G\} \]

性质

• 是一个等价关系（条件：自反性、对称性、传递性）

三元素集的置换群

对称群

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)\)指置换中不变元个数

陪集和拉格朗日定理

陪集

定义

设H是G的子群，\(a\in G\)，则

• aH={a*h|h∈H} H关于a的左陪集
• Ha={h*a|h∈H} H关于a的右陪集

a称为陪集的代表元素

性质

元素\(\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^-1 *b∈H \(\iff\) b∈aH \(\iff\) aH=bH

所有左陪集的集合∑刚好是G的一个划分

特殊关系

划分

• 每个元素非空。不存在空块
• 所有元素并集为G
• 任两个元素交集为空

等价关系

关系R满足自反、对称、传递

• 若<x,y>\(\in\)R，称x等价于y，记作x~y

等价类

有等价关系的元素组成的一个集合，记为[a]_R

• a称为[a]_R的代表元素

商集 A/R

以R的所有等价类作为元素的集合称为A关于R的商集

子群的指数

G对H的陪集的集合的基数，即陪集的数目，记为[G:H ]

拉格朗日定理

H为G的子群，则：

• R={<a,b>|a∈G,b∈G且a^-1 *b∈H}是G上的一个等价关系。对于a∈G，若记[a]_R={x|x∈G且<a,x>∈R}，则[a]_R=aH
• 如果G是有限群，|G|=n，|H|=m，则m|n。

推论

• 素数阶群的子群一定是平凡群。（素数阶的群不存在非平凡子群）
• 设<G,*>是n阶群，则对任意a∈G，有aⁿ=e
• 有限群中，元素的阶能整除群的阶
• 素数阶群一定是循环群，且每个非幺元均为生成元

正规子群和商群

正规子群 / 不变子群

定义

H\(\leq\)G，\(\forall g\in G\)，gH=Hg，记为H\(\unlhd\)G

判别

\(\forall a\in G\)，

• aH=Ha，（即H\(\unlhd\)G）
• \(\forall h\in H\)，aha^-1\(\in\)H
• aHa^-1\(\subseteq\)H
• aHa^-1=H

如果G是交换群，则G的任何子群都是正规子群

[G:H]=2 ， 则H是G的正规子群

单群

G除了平凡子群外无其他正规子群

性质

• 正规子群与子群的乘积是子群
• 正规子群与正规子群的乘积是正规子群
• 无传递性

商群

运算

在G/H上定义陪集乘法运算?，对于任意aH,bH∈G/H, 有

定义

设G为群，H为正规子群，则G/H关于运算?构成一个群，称为G的商群

性质

• 商群G/H的单位元是eH（=H）
• 在G/H中aH的逆元是a^-1H

推论

• 若G是交换群，G/H也是交换群
• 商群的阶是G阶数的因子

同态与同构

同态映射 / 同态 ~

定义

<A,\(\star\)>与<B,*>满足\(f(a_1\star a_2)=f(a_1)*f(a_2)\)

称 f 为同态映射 / 同态，<A,\(\star\)>同态于<B,*>

记为 A~B

同态象

<f(A), *>为<A,\(\star\)>的一个同态象

自然同态

群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 $>的所有性质

同态核

定义

A中元素映射 f 后为幺元。记为 Ker(f)，称为 f 的同态核

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, +, ·>有两种二元运算的代数系统

• <A, +>是阿贝尔群

• <A, ·>是半群

• 运算 · 对于 + 是可分配的，即\(\forall a,b,c\in A\)：

  a·(b+c)=(a·b)+(a·c)

  (b+c)·a=(b·a)+(c·a)

为了区别环中的两个运算，通常称＋运算为环中的加法，?运算为环中的乘法。

零元

加法单位元，记为0(\(\theta\))

单位元

乘法单位元，记为1

负元

加法逆元，记为-x

逆元

乘法逆元，记为x^-1

例子

• <R,＋,?> 实数环
• <Q,＋,?> 有理数环
• <I,＋,?> 整数环
• <M_n(I),＋, ?> n阶整数矩阵环
• <N_k , ＋_k , ×_k> 模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)

特殊环

交换环

<A, · >可交换

含幺环

<A, · >含幺元

无零因子环

（等价于乘法消去律）

\(\forall a,b\in A, a\neq\theta, b\neq \theta\)，则必有\(a·b\neq\theta\)

零因子

若\(a,b\in A, a\neq\theta, b\neq \theta\)，有\(a·b=\theta\)，则a或b为零因子

整环

定义

（基于乘法运算的性质）

交换、无零因子 OR 含幺、无零因子

即同时满足交换环、含幺环和无零因子环的条件

子环

定义

环的子集，也是环

判定定理

\(\forall a,b\in S,a-b\in S,a·b\in S\)

域

定义

满足如下：

• <A, +>是阿贝尔群
• <A - {\(\theta\)}, ·>是阿贝尔群
• 运算 ? 对运算＋是可分配的

例子

• 实数域
• 有理数域
• 〈Z_n,+_n, ? _n 〉是域的充要条件是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,+, ? >同构。

证明：

首先证明<R, ⊕, ⊙ >是环。

（1） <R, ⊕ >是阿贝尔群。

（2） <R, ⊙ >是含幺半群。

（3） ⊙对⊕可分配，再证明同构。

（4）构造双射f: f(a)=a-1,验证同构性。

（1） <R, ⊕ >是阿贝尔群。

显然R关于⊕是封闭的且⊕运算是可交换的。

结合性：对于任意的x,y,z\(\in\)R,有

(x⊕y)⊕z=(x+y+1)⊕z=x+y+z+2,而

x⊕(y⊕z )= x⊕ (y+z+1)=x+y+z+2, 即⊕运算满足结合律。

幺元：对于任意x\(\in\)R， x⊕-1= x+(-1)+1=x,-1是R关于⊕运算的幺元。

逆元：对于任意x\(\in\)R， x⊕（-x-2)= x+(-x-2)+1=-1, +(-x-2)是x关于⊕运算的逆元。

所以<R, ⊕ >是阿贝尔群。

（2） <R, ⊙ >是含幺半群。

显然R关于⊙是封闭的、可交换的。

结合性：对于任意的x,y,z ?R,有

(x ⊙ y) ⊙ z=(xy+x+y) ⊙ z=xyz+xz+yz+xy+x+y+z,而

x ⊙(y ⊙ z )= x ⊙ (yz+y+z)=xyz+xy+xz+yz+x+y+z, 即⊙运算满足结合律。

幺元：对于任意x?R， x ⊙ 0=0+ x+0=x，0是R关于⊙运算的幺元。

所以<R, ⊙ >是含幺半群.

（3） ⊙对⊕可分配

对于任意的x,y,z\(\in\)R,有

x⊙(y⊕z )= x⊙(y+z+1)=xy+xz+x+x+y+z+1=xy+xz+2x+y+z+1

(x⊙y)⊕(x⊙z)=(xy+x+y)⊕(xz+x+z)=xy+xz+2x+y+z+1

同理可以证明右可分配性。

综上所述， <R, ⊕, ⊙ >也是含幺环

再证明同构。

构造双射f: f(a)=a-1,验证同构性。

（4）证明同构。构造函数f: f(x)=x-1

双射：对于任意x\(\in\)R,则有x+1\(\in\)R，使得f(x+1)=x，所以f是满射

x，y\(\in\)R,若f(x)=f(y),则有x-1=y-1,即x=y,所以f是单射。

同态： f(x+y)=x+y-1

f(x)⊕f(y)=(x-1)⊕(y-1)=x-1+y-1+1=x+y-1

所以f(x+y)= f(x)⊕f(y)

又因为 f(x?y)=x?y-1

f(x)⊙f(y)=(x-1) ⊙(y-1)=(x-1)? (y-1)+x-1+y-1

? =x?y-x-y+1+x-1+y-1=x?y-1

所以f(x?y)= f(x)⊙f(y)

? 综上，<R, ⊕, ⊙ >与<R,+, ° >同构。

离散数学 II（最全面的知识点汇总）

原文：https://www.cnblogs.com/rsmx/p/12993902.html