26-27-1-离散数学(下)-期中

一、

设 R={(x,y)∣x−y+2>0, x−y−2<0}R=\{(x,y)\mid x-y+2>0,\ x-y-2<0\} 是实数集上的二元关系。判断关系 RR 是否具有自反性、对称性、反对称性和传递性,并说明理由。

二、

设集合 A={1,2,3}A=\{1,2,3\}。

  1. 写出集合 AA 上的所有等价关系。
  2. 在集合 A×AA\times A 上定义二元关系 RR:对任意 (u,v),(x,y)∈A×A(u,v),(x,y)\in A\times A,(u,v)R(x,y)(u,v)R(x,y) 当且仅当 u+y=v+xu+y=v+x。证明 RR 是 A×AA\times A 上的等价关系。
  3. 确定关系 RR 在集合 A×AA\times A 上的划分。

三、

题图3

题图3

下图为关系 RR 的有向图。

  1. 计算 R2R^2。
  2. 求 RR 的对称闭包。
  3. 用 Warshall 算法求 RR 的传递闭包。

四、

  1. 设集合 S={a,b,c}S=\{a,b,c\},在 SS 的幂集上定义偏序关系 {(A,B)∣A⊆B}\{(A,B)\mid A\subseteq B\},求该偏序的覆盖关系。 (注:设 (P,⪯)(P,\preceq) 是偏序集。若 x≺yx \prec y,且不存在元素 z∈Sz\in S 满足 x≺z≺yx \prec z \prec y,则称元素 yy 覆盖元素 xx。所有满足“yy 覆盖 xx”的有序对 (x,y)(x,y) 构成的集合,称为 (P,⪯)(P,\preceq) 的覆盖关系)

  2. 画出幂集 P(S)\mathcal{P}(S) 的 Hasse 图。设 W={∅,{a},{b},{c}}W=\{\emptyset,\{a\},\{b\},\{c\}\}(其中 W⊆P(S)W\subseteq \mathcal{P}(S)),求集合 WW 的极大元、极小元、最小上界和最大下界。

五、

设集合 G={1,2,3,4}G=\{1,2,3,4\},定义二元运算 ⊙\odot: a⊙b=(a⋅b) mod 5,∀a,b∈Ga\odot b=(a\cdot b)\bmod 5,\quad \forall a,b\in G,⋅\cdot 为普通乘法。证明 (G,⊙)(G,\odot) 是阿贝尔群。

六、

设 S={a,b}S=\{a,b\} 和 T={u,v}T=\{u,v\} 是两个半群,各自的二元运算如下:

∗abaabbba\begin{array}{c|cc} * & a & b \\ \hline a & a & b \\ b & b & a \end{array} ⋅uvuuuvuv\begin{array}{c|cc} \cdot & u & v \\ \hline u & u & u \\ v & u & v \end{array}
  1. 写出积半群 (S×T,⊙)(S\times T,\odot) 的运算表。
  2. 判断 S×TS\times T 是否与 Z4\mathbb{Z}_4(模 4 加法群)同构,并证明你的结论。

七、

设 G=(Z6,+6)G=(\mathbb{Z}_6,+_6),即模 6 整数加法群。在 GG 上定义二元关系 RR:x R y  ⟺  2x≡2y(mod6)x\,R\,y \iff 2x\equiv 2y \pmod{6}。

  1. 证明 RR 是 GG 上的同余关系。
  2. 构造商群 G/RG/R。
  3. 找出 Z6\mathbb{Z}_6 的所有子群。

八、

  1. 设集合 S=ZS=\mathbb{Z},二元运算定义为 x∗y=xx*y=x,则 (S,∗)(S,*) 是 【暂无答案】(半群 / 含幺半群 / 群)。
  2. 设 NN 是群 GG 的正规子群,则商群 G/NG/N 上的群运算为 (gN)(hN)=(gN)(hN)= 【暂无答案】
  3. 设 (S,∗)(S,*) 是半群,子集 T⊆ST\subseteq S 是 SS 的子半群,当且仅当对任意 t1,t2∈Tt_1,t_2\in T,【暂无答案】
  4. 在模 8 加法群 G=Z8G=\mathbb{Z}_8 中,设 H={0,4}H=\{0,4\},则左陪集 3+H=3+H= 【暂无答案】
  5. 设集合 S={1,2,3}S=\{1,2,3\},运算为 x∗y=max⁡{x,y}x*y=\max\{x,y\},则子集 T={2,3}T=\{2,3\} 【暂无答案】(是 / 不是)子半群。

九、

设

H=[101110011100010001]H=\begin{bmatrix} 1 & 0 & 1\\ 1 & 1 & 0\\ 0 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}
  1. 确定该 (3,6)(3,6) 群码的编码函数 eH:B3→B6e_H:B^3\to B^6。
  2. 求该编码的最小距离;该编码可以检测多少位错误?设 dd 是对应的最大似然译码函数,则该编码-译码系统 (e,d)(e,d) 可以纠正多少位错误?
  3. 借助译码表,使用最大似然译码函数对下列码字进行译码: (a) 011101011101 (b) 101001101001 (c) 110010110010

十、

设

H=[110011100010001]H=\begin{bmatrix} 1 & 1 & 0\\ 0 & 1 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}
  1. 找出 eH(B2)e_H(B^2) 在 B5B^5 中的所有左陪集。
  2. 对每个陪集,找出一个陪集首,并计算每个陪集首的伴随式。
  3. 利用伴随式,使用最大似然译码函数对码字 0101001010 进行译码。