离散数学 II(最全面的知识点汇总)

时间:2021-03-23 00:01:17

离散数学 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,由运算*封闭可知:

b2=b*b\(\in\)S,b2 *b=b*b2=b3\(\in\)S ,b4,b5… \(\in\)S

∵ S有限,∴必定\(\exists\)i,j,j>i,有bi=bj(第一轮)

∴ bi =bj =bj-i * bi

令p=j-i ,则有 bi =bp * bi

∴ 对任意q≥i, 有bq= bp *bq (第二轮)

又∵p≥1 ∴$\exists $k,有kp≥i,则有bkp=bp *bkp (第三轮)

由bkp=bp *bkp得: bkp=bp *bkp=bp *(bp *bkp)=…=bkp *bkp

∴令a=bkp \(\in\)S 则a*a=a,∴bkp是等幂元。

子半群

  • \(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阶还有克莱因四元群,如下

* e a b c
e e a b c
a a e c b
b b c e a
c c b a e

特性

  • 阶大于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,则
    • 幺元为an
    • 有\(\psi(n)\)个生成元,(欧拉函数,表示小于n且与n互质的正整数个数)
    • G的其他生成元即\(a^k\),k与n互质
  • 若阶数无限,则只有两个生成元e和e-1

元素的阶

定义

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

性质
  • ak=e \(\iff\) r | k

    (k是r的整数倍,即存在整数m,使得k=rm )

证:

充分性:r | k \(\Rightarrow\) ak=e

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

​ ak= arm=(ar)m=em=e

必要性:ak=e \(\Rightarrow\) r | k

若ak=e,由带余除法,一定存在整数p,q,使得

k=pr+q(0≤q<r),于是ak=apr+q=apr *aq=(ar)p *aq =(e)p *aq =e*aq =aq =e (ak=e)

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

∴只有q=0才可能有aq =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 ,ar=e

∵ (ar)-1 *ar=e 且ar=e,

∴ (ar)-1=e( (ar)-1与e做运算=e,则(ar)-1必=e)

由红色部分可得(ar)-1=(a-1)r’=e-----①

∵ <G,*>是群,即(an)-1=(a-1)n成立,则

(ar)-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’= (ar’)-1=e

∵ (ar’)-1 * ar’=e

∴ ar’=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,a2,a3,…,ar-1,ar},因为运算*封闭,所以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-1)…(a1 a3)(a1 a2)

诱导的二元关系

定义

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

\[R=\{<a,b>|\pi(a)=b,\ \pi\in G\}
\]
性质
  • 是一个等价关系(条件:自反性、对称性、传递性)

三元素集的置换群

对称群

S3={ (1), (1 2), (1 3), (2 3), (1 2 3), (1 3 2) }

交错群

A3={ (1), (1 2 3), (1 3 2) }

伯恩赛德定理

\(\pi\)是划分S的置换群的一个置换,\(\phi(\pi)\)指置换中不变元个数

\[等价类数目=\frac{1}{|G|}\sum_{\pi\in G}\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,有an=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, 有

\[aH·bH=(ab)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,+,·> 整数环
  • <Mn(I),+, ·> n阶整数矩阵环
  • <Nk , +k , ×k> 模k整数环
  • <Z[i], +, ·>(Z[i]=a+bi,a,b\(\in\)Z,i2=-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\)}, ·>是阿贝尔群
  • 运算 · 对运算+是可分配的

例子

  • 实数域
  • 有理数域
  • 〈Zn,+n, · n 〉是域的充要条件是n是素数

域与整环的关系

  • 域一定是整环
  • 有限整环一定是域

环的同态定义

V1=<A,*,∘>和V2=<B,⊛,◎>是两环,其中*、∘、⊛和◎都是二元运算。f 是从AB的一个映射,使得对\(\forall\)a, b\(\in\)A有:

f(a*b)=f(a)⊛f(b)

f(ab)=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(最全面的知识点汇总)的更多相关文章

  1. nginx几个知识点汇总

    WHY? 为什么用Nginx而不用LVS? 7点理由足以说明一切:1 .高并发连接: 官方测试能够支撑 5 万并发连接,在实际生产环境中跑到 2 - 3 万并发连接数.?2 .内存消耗少: 在 3 万 ...

  2. python全栈开发 &ast; 10知识点汇总 &ast; 180612

    10 函数进阶 知识点汇总 一.动态参数 形参的第三种1.动态接收位置传参 表达:*args (在参数位置编写 * 表⽰接收任意内容) (1)动态位置参数def eat(*args): print(a ...

  3. 清华大学OS操作系统实验lab1练习知识点汇总

    lab1知识点汇总 还是有很多问题,但是我觉得我需要在查看更多资料后回来再理解,学这个也学了一周了,看了大量的资料...还是它们自己的80386手册和lab的指导手册觉得最准确,现在我就把这部分知识做 ...

  4. c&plus;&plus; 函数知识点汇总

    c++ 函数知识点汇总 swap函数 交换两个数组元素 比如 swap(a[i],a[j]); 就是交换a[i] 和 a[j] 的值 strcpy() 复制一个数组元素的值到另一个数组元素里 strc ...

  5. 前端开发 JavaScript 干货知识点汇总

    很多初学的朋友经常问我,前端JavaScript都需要学习哪些东西呀?哪些是JavaScript的重点知识啊? 其实做前端开发工程师,所有的知识点都是我们学习必备的东西,只有扎实的技术基础才是高薪的关 ...

  6. BBS项目知识点汇总

    目录 bbs项目知识点汇总 一. JavaScript 1 替换头像 2 form表单拿数据 3 form组件error信息渲染 4 添加html代码 5 聚焦操作 二 . html在线编辑器 三 . ...

  7. Java面试知识点汇总

    Java面试知识点汇总 置顶 2019年05月07日 15:36:18 温柔的谢世杰 阅读数 21623 文章标签: 面经java 更多 分类专栏: java 面试 Java面试知识汇总   版权声明 ...

  8. ECMAScript版本知识点汇总

    ECMAScript版本知识点汇总 ES5 btoa.atob 对参数进行base64格式编码.解码 /** * btoa() * base64编码 * @param {string} str * @ ...

  9. c&plus;&plus;常考算法知识点汇总

    前言:写这篇博客完全是给自己当做笔记用的,考虑到自己的c++基础不是很踏实,只在大一学了一学期,c++的面向对象等更深的知识也一直没去学.就是想当遇到一些比较小的知识,切不值得用一整篇 博客去记述的时 ...

随机推荐

  1. oc-16-set&comma;get方法

    S.h #import <Foundation/Foundation.h> /** 解决方案: 1.不用@public修饰 2.我们对象有访问和设置成员变量的两种操作 1>设置值 p ...

  2. 在C&plus;&plus;中调用DLL中的函数

    如何在C++中调用DLL中的函数 应用程序使用DLL可以采用两种方式:一种是隐式链接,另一种是显式链接.在使用DLL之前首先要知道DLL中函数的结构信息.Visual C++6.0在VC\bin目录下 ...

  3. 对于反射中的invoke&lpar;&rpar;方法的理解

    先讲一下java中的反射: 反射就是将类别的各个组成部分进行剖析,可以得到每个组成部分,就可以对每一部分进行操作 在比较复杂的程序或框架中来使用反射技术,可以简化代码提高程序的复用性. 讲的是Meth ...

  4. 关于throw、throws、try--catch的问题

    首先回顾概念 throws表示出现异常的一种可能性,并不一定会发生这些异常 throw则是抛出了异常,执行throw则一定抛出了某种异常 try--catch try语句用大括号{}指定了一段代码,该 ...

  5. Android动画模式

    在Android中,有两种动画模式:Tween Animation(渐变动画)和Frame Animation(帧动画).渐变动画是通过对场景里的对象不断做图像变换(平移.缩放.旋转等)来产生动画效果 ...

  6. EBS 请求输出Html报表集成Echarts

    百度开源的ECharts有样式丰富且美观的报表类型可供选用,可以将其集成至EBS请求输出的Html报表中,这其实就是一个生成Html数据的过程. 定义输出类型为HTML的请求我就不在此处赘述.   我 ...

  7. 如何提取app软件的apk格式中的字体?

    1.下载apk格式的指定app软件: 2.将apk格式的文件名更改为后缀名为zip格式: 3.用winrar解压软件解压,然后就找到其中的ttf格式的字体文件. 举例说明,我想找到airbnb的app ...

  8. 把CDLinux制作成U盘启动

    因为用下了CDlinux,本来想在虚拟机上运行的.发现虚拟机跑的时候无法识别集成的笔记本网卡,坑爹啊.后来想刻碟的,发现手头上还没有现成的东西,光驱是只读的,又要用到光驱,于是想到了了用U盘,正好手上 ...

  9. phpcms 留言板

    相信很多用phpcms v9的站长都不是程序员,而我也是一个网页设计师,所以对制作模板还是可以对付的.但是一设计到自己写程序,就一个头两个大啦.之前公司的网站是用找别人 用dede cms做的,后来我 ...

  10. GO语言(六)接口使用

    <music> |------<src> |-------<library> |-------manager.go |-------manager_test.go ...