nan2inf .cn
数学 旧 .com 迁移

离散数学：相关资料 / 第五次

从旧 .com 全量搬运的历史内容，来源路径：/math/课程/离散数学/resources/第五次/

约 3 分钟阅读
migrationlegacy-commathresourcecourse

迁移来源

第五次作业

习题六 1 #

note
  • (1) 是
  • (3) 是
  • (5) 不是
  • (7) 是
  • (9) 是

习题六 3 #

note
  • (1) 设 X={a,b},a∗b=a,a∗a=a,b∗b=a,b∗a=bX=\{a,b\},a*b=a,a*a=a,b*b=a,b*a=b.
  • (2) 设 X={a,b},a∗b=b,a∗a=a,b∗b=a,b∗a=aX=\{a,b\},a*b=b,a*a=a,b*b=a,b*a=a.
  • (3) 对于左幺元, el∗er=ere_l*e_r=e_r, 对于右幺元 el∗er=ele_l*e_r=e_l, 故 el=el∗er=ere_l=e_l*e_r=e_r.

习题六 7 #

note

满足结合律: x∗y∗k=x∗k=x,x∗(y∗k)=x∗y=xx*y*k=x*k=x,x*(y*k)=x*y=x.

不满足交换律: x∗y=x,y∗x=yx*y=x,y*x=y.

没有幺元, 但有右幺元, 且每个元素都是右幺元.

没有零元, 但有左零元, 且每个元素都是左零元.

没有逆元.

习题六 9 #

note

∀ x∈S, x∗x2=x2∗x⇒x=x\forall\ x\in S,\ x*x^2=x^2*x\Rightarrow x^=x

习题六 12 #

note

S1,S2S_1,S_2 是, S3S_3 不是.

习题六 17 #

note

取映射 φ(x)={0,x=01,x≠0\varphi(x)=\begin{cases} 0,\quad x=0\\ 1,\quad x\neq 0 \end{cases}

则有 φ(x)φ(y)=φ(xy)\varphi(x)\varphi(y)=\varphi(xy).

即 φ\varphi 是同态.

习题六 19 #

note

∀ a,b∈X, h(x)h(y)=f1(x)⊕f2(x)⊕f1(y)⊕f2(y)=f1(x)⊕f1(y)⊕(f2(x)⊕f2(y))=f1(xy)⊕f2(xy)=h(xy)\forall\ a,b\in X,\ h(x)h(y)=f_1(x)\oplus f_2(x)\oplus f_1(y)\oplus f_2(y)=f_1(x)\oplus f_1(y)\oplus (f_2(x)\oplus f_2(y))=f_1(xy)\oplus f_2(xy)=h(xy).

习题六 22 #

  • (1) $
∗012345000000010123452024024303030340420425054321\begin{aligned} * & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \end{aligned}

$

  • (2) ∀ x,y,z∈Nk\forall\ x,y,z\in N_k, 设 x∗y=p1k+r1,y∗z=p2k+r2,x∗y∗k=p3k+r3x*y=p_1k+r_1,y*z=p_2k+r_2,x*y*k=p_3k+r_3 则有 r1z≡r3( mod  k),xr2≡r3( mod  k),⇒x∗ky∗kz=r1∗kz=r3,x∗k(y∗kz)=x∗kr2=r3r_1z\equiv r_3(\bmod\ k),xr_2\equiv r_3(\bmod\ k),\Rightarrow x*_ky*_kz = r_1*_kz=r_3,x*_k(y*_kz)=x*_kr_2=r_3.

故满足结合律, 即 <Nk,∗k><N_k,*_k> 是半群.

习题六 25 #

note

∀x,y,z∈R,x∗y∗z=(x+y+xy)∗z=x+y+xy+z+(x+y+xy)z=x+y+z+xy+xz+yz, x∗(y∗z)=x∗(y+z+yz)=x+y+z+xy+xz+yz\forall x,y,z\in \mathbb R,x*y*z=(x+y+xy)*z=x+y+xy+z+(x+y+xy)z=x+y+z+xy+xz+yz,\ x*(y*z)=x*(y+z+yz)=x+y+z+xy+xz+yz.

幺元是 00. ∀x∈R,0∗x=0+x+0x=x,x∗0=x+0+x0=x\forall x\in \mathbb R,0*x=0+x+0x=x,x*0=x+0+x0=x.

故 <R,∗><\mathbb R,*> 是半群.

习题六 30 #

<S,∗><S,*> 是半群. 若有 a∈S, ∀ x∈S, ∃ u,v∈Sa\in S,\ \forall\ x\in S,\ \exists\ u,v\in S 使得

a∗u=v∗a=xa*u=v*a=x

证明: <S,∗><S,*> 是含幺半群.

note

先取 x=ax=a, 设 ab1=b2a=aab_1=b_2a=a.

再取 x=b1x=b_1, 设 b1=aub_1=au 同左乘 b2b_2 得 b2b1=b2au=au=b1b_2b_1=b_2au=au=b_1.

再取 x=b2x=b_2, 设 b2=vab_2=va 同右乘 b1b_1 得 b2b1=vab1=va=b2b_2b_1=vab_1=va=b_2.

故得到 b1=b2b_1=b_2 记作 bb, 即 ab=ba=aab=ba=a.

下面验证 bb 是幺元.

∀ x∈S,\forall\ x\in S, 设 x=au=vax=au=va 则有 bx=bau=au=x,xb=vab=va=xbx=bau=au=x,xb=vab=va=x.

故 bb 是幺元.

习题六 32 #

  • (1) {{< admonition note “证明” false >}} f1,f2∈SS,∀x∈S,f1∘f2(x)=f1(f2(x))f_1,f_2\in S^S, \forall x\in S,f_1\circ f_2 (x)=f_1(f_2(x)) 由 f2(x)∈S⇒f1(f2(x))∈S⇒f1∘f2∈SSf_2(x)\in S\Rightarrow f_1(f_2(x))\in S\Rightarrow f_1\circ f_2\in S^S.

又函数的复合具有结合律, <SS,∘><S^S,\circ> 是半群.

  • (2) {{< admonition note “答案” false >}} 对于给定 aa 设 σa:S→S,σa(x)=ax\sigma_a: S\to S,\sigma_a(x)=ax.

则有 σa∈SS\sigma_a\in S^S.

取 φ:S→SS,φ(a)=σa\varphi:S\to S^S,\varphi(a)=\sigma_a.

∀ a,b∈S,∀x∈S,φ(a)∘φ(b)(x)=σa(σb(x))=abx=σabx=φ(ab)(x)\forall\ a,b\in S,\forall x\in S,\varphi(a)\circ\varphi(b)(x)=\sigma_a(\sigma_b(x))=abx=\sigma_{ab}x=\varphi(ab)(x) 即 φ\varphi 是同态.

习题六 33 #

note

设 y=f(x)∈Yy=f(x)\in Y 则 y∗y=f(x)∗f(x)=f(x2)=f(x)=yy*y=f(x)*f(x)=f(x^2)=f(x)=y 故 yy 是 YY 的幂等元.

习题六 34 #

  • (1) 真
  • (2) 真
  • (2) 真

习题六 43 #

x∗x=ex*x=e 即 SS 中的元素均存在逆元. 故 <S,∗><S,*> 是群.

yx=yx∗e=yx∗y2=yx∗y∗e∗y=yx∗y∗x2∗y=(yx)2xy=e∗xy=xyyx=yx*e=yx*y^2=yx*y*e*y=yx*y*x^2*y=(yx)^2xy=e*xy=xy.

故 <S,∗><S,*> 是交换群.

习题六 47 #

note

先证必要性, H1H2H_1H_2 是 GG 的子群, ∀h1h2∈H1H2,(h1h2)−1∈H1H2,⇒∃h1′h2′=(h1h2)−1,⇒h1h2=(h1′h2′)−1=h2′−1h1′−1∈H2H1⇒H1H2⊆H2H1\forall h_1h_2\in H_1H_2,(h_1h_2)^{-1}\in H_1H_2,\Rightarrow\exists h_1'h_2'=(h_1h_2)^{-1},\Rightarrow h_1h_2=(h_1'h_2')^{-1}=h_2'^{-1}h_1'^{-1}\in H_2H_1\Rightarrow H_1H_2\subseteq H_2H_1.

又 ∀ h2h1∈H2H1,h1−1h2−1∈H1H2⇒(h1−1h2−1)−1∈H1H2⇒h2h1∈H1H2⇒H2H1⊆H1H2\forall\ h_2h_1\in H_2H_1,h_1^{-1}h_2^{-1}\in H_1H_2\Rightarrow (h_1^{-1}h_2^{-1})^{-1}\in H_1H_2\Rightarrow h_2h_1\in H_1H_2\Rightarrow H_2H_1\subseteq H_1H_2.

综上 H1H2=H2H1H_1H_2=H_2H_1.

下证充分性, ∀h1h2,h3h4∈H1H2\forall h_1h_2,h_3h_4\in H_1H_2 对于 (h3h4)−1=h4−1h3−1(h_3h_4)^{-1}=h_4^{-1}h_3^{-1} 存在 h3′h4′=(h3h4)−1,h3′∈H1,h4′∈H2h_3'h_4'=(h_3h_4)^{-1},h_3'\in H_1,h_4'\in H_2.

则 h1h2(h3h4)−1=h1h2h3′h4′h_1h_2(h_3h_4)^{-1}=h_1h_2h_3'h_4', 对于 h2h3h_2h_3 存在 h3′′∈H1,h2′′∈H2,h2h3=h3′′h2′′h_3''\in H_1,h_2''\in H_2,h_2h_3=h_3''h_2''.

即 h1h2h3′h4′=(h1h3′′)(h2′′h4′),h1h3′′∈H1,h2′′h4∈H2⇒h1h2(h3h4)−1∈H1H2h_1h_2h_3'h_4'=(h_1h_3'')(h_2''h_4'),h_1h_3''\in H_1,h_2''h_4\in H_2\Rightarrow h_1h_2(h_3h_4)^{-1}\in H_1H_2 故 H1H2H_1H_2 是 GG 的子群.

习题六 49 #

note

∀ x,y∈X, yH=Hy⇒H=y−1Hy⇒Hy−1=y−1H⇒y−1∈X\forall\ x,y\in X,\ yH=Hy\Rightarrow H=y^{-1}Hy\Rightarrow Hy^{-1}=y^{-1}H\Rightarrow y^{-1}\in X, 又 xy−1H=x(y−1H)=x(Hy−1)=(xH)y−1=H(xy−1)⇒xy−1∈Xxy^{-1}H=x(y^{-1}H)=x(Hy^{-1})=(xH)y^{-1}=H(xy^{-1})\Rightarrow xy^{-1}\in X

故 XX 是 GG 的子群.

习题六 50 #

  • (1) {{< admonition note “证明” false >}} 封闭性: f1=a1x+b1,f2=a2x+b2⇒f1∘f2=f1(a2x+b2)=a1a2x+a1b2+b1∈Gf_1=a_1x+b_1,f_2=a_2x+b_2\Rightarrow f_1\circ f_2=f_1(a_2x+b_2)=a_1a_2x+a_1b_2+b_1\in G.

函数的复合满足结合律.

逆元: f=ax+b,f−1=xa−baf=ax+b,f^{-1}=\dfrac{x}{a}-\dfrac b a.

幺元: fe=xf_e=x.

所以 <G,∘><G,\circ> 是群.

  • (2) {{< admonition note “证明” false >}} f1,f2∈S1f_1,f_2\in S_1 设 f1=x+b1,f2=x+b2,f2−1=x−b2f_1=x+b_1,f_2=x+b_2,f_2^{-1}=x-b_2, 则 f1∘f2−1=x+b1−b2∈S1f_1\circ f_2^{-1}=x+b_1-b_2\in S_1.

f1,f2∈S2f_1,f_2\in S_2 设 f1=a1x,f2=a2x,f2−1=xa2f_1=a_1x,f_2=a_2x,f_2^{-1}=\dfrac{x}{a_2}, 则 f1∘f2−1=a1xa2∈S2f_1\circ f_2^{-1}=\dfrac{a_1x}{a_2}\in S_2.

故 <S1,∘>,<S2,∘><S_1,\circ>,<S_2,\circ> 是 GG 的子群.

讨论

评论

正在加载评论...