代数结构习题课-1
2023spring代数结构习题课讲义
代数结构 第一次习题课
2023.5.3
第三章 映射
内容回顾
- 映射的基本定义
- 概念：映射，原像，像，值域，映射相等
- 给定集合A，B，从A到B的映射有$|B|^{|A|}$个
- 特殊映射：对于$f:A\rightarrow B$:
- $B=A,\forall a,f(a)=a$：恒等映射
- $R_f=B$：满射
- 任给$a_1,a_2\in A,a_1\neq a_2\Rightarrow f(a_1)\neq f(a_2)$：单射
- 单射+满射：一一映射（双射） 相关性质：$f^{-1}$，$n!$个双射
- 映射的复合：$g\circ f(a)=g(f(a))$ 从右往左计算
- 结合律：$(h\circ g)\circ f=h\circ (g\circ f)$
- $f^{-1}\circ f=f\circ f^{-1}=I_A$
- 复合运算保持单射/满射/双射
- 置换：映射到自身的双射
- 恒等映射也可以称为恒等置换
- 求逆置换：交换两行并按照第一行排序
- 奇置换与偶置换：由逆序的个数奇偶决定
- 轮换：特殊的置换，$\sigma=(a_1a_2…a_r)$
- 不相交的轮换的乘积可以交换
- 任何置换都可以表示成若干不相交的轮换之乘积
- 置换的阶：将置换表示为不相交的轮换，阶为各轮换的因子长度的最小公倍数
- 对换：两个元素的轮换
- 任何轮换都可以表示成对换之积
- 对换是奇置换，n元置换中，奇置换和偶置换各占一半
- 开关函数：$F_2={0,1},f(x_1,…x_n)$为$F_2^n$到$F_2$的映射即为n元开关函数，共有$2^{2^n}$个
- 求补运算$\overline f$，逻辑加 $ +$，逻辑乘 $ \cdot$ （注意和算术运算的区别）
- 结合律，交换律，分配律，$f+0=f;f\cdot 1=f;f+\overline f=1;f\cdot \overline f=0$
- 小项表达式：唯一的表达$f(x_1,..x_n)=\sum_{a_i=0/1,1\leq i\leq n} f(a_1,..a_n)x_1^{a_1}…x_n^{a_n}$
作业题目
3.16 证明：任何n元置换都可以表示成(1 2),(2 3),…,(n-1,n)的乘积
方法1：用归纳法证明：
n=2时，2元置换即为(1 2);
n>2时，假设对于任何k，$k\le n$,满足任何k元置换都可以表示成(1 2),(2 3),…,(k-1,k)的乘积，考虑任何一个n元置换$\sigma$,设该置换对应的位置i的元素为n，令$\tau=(n-1\ n)…(i+1\ i+2)(i\ i+1)\sigma$，依次计算，即为将$\sigma$的第i个元素和第i+1个元素对换，第i+1个元素和第i+2个元素对换…最终可以将元素n换到第n个位置，即$\tau$为（n-1）元置换；将上式进行整理，原n元置换可以写为$\sigma=(i+1\ i+2)(i\ i+1)…(n-1\ n)\tau$，根据归纳假设，$\tau$可以写为(1 2),(2 3),…,(k-1,k)的乘积，因此$\sigma$可以写为(1 2),(2 3),…,(n-1,n)的乘积。
综上所述，任何n元置换都可以表示成(1 2),(2 3),…,(n-1,n)的乘积。
方法2：
任何置换都可以表示为成不相交的轮换之积，任何轮换都可以表示成对换之积，因此只需讨论将对换表示为(1 2),(2 3),…,(n-1,n)的乘积。对换$(a_i\ a_j),i>j$可表示为$(a_{i+1}\ a_{i+2})…(a_{j-2}\ a_{j-1})(a_{j-1}\ a_{j})…(a_{i+1}\ a_{i+2})(a_i\ a_{i+1})$从而得证。
3.17 求证下列恒等式
（1）$x_1=x_1x_2x_3+x_1\overline x_2x_3+x_1x_2\overline x_3+x_1\overline x_2\overline x_3$
$x_1=x_1(x_2+\overline x_2)(x_3+\overline x_3)=x_1x_2x_3+x_1\overline x_2x_3+x_1x_2\overline x_3+x_1\overline x_2\overline x_3$
（2）$x_1x_2+x_2x_3+x_3\overline x_1=x_1x_2+\overline x_1x_3$
$x_1x_2+x_2x_3+x_3\overline x_1=x_1x_2+x_2x_3(x_1+\overline x_1)+x_3\overline x_1 = x_1x_2(1+x_3)+\overline x_1x_3(x_2+1)=x_1x_2+\overline x_1x_3$
注意：开关函数的运算中$a+c=b+c$无法推出$a=b$
补充习题
注意，在置换/对换/轮换的计算中，乘积要从右往左计算，轮换的计算方式是将每个元素映射到右边的位置。
第四章 二元关系
内容回顾
关系
- 关系的定义：
- 相关概念：空关系（平凡关系），全关系
- 关系的性质：判断是否具有某种性质
- 自反性，反自反性，对称性，反对称性，传递性
- 关系的表示：
- 有序二元组：$xRy$
- 关系矩阵：$mij=\begin{cases}0,a_iR\mkern-10.5mu/ a_j\\1,a_iRa_j\end{cases} $
- 关系图：如果有$a_iRa_j$，则画一条由$a_i$指向$a_j$的有向弧（环）
- 关系的运算：
- 相等，$<,\leq,>,\geq$
- 并交补运算（交换律，结合律）
- 复合关系 ：结合律，幂运算$R^n=R^m\circ R1^{n-m}$
- 自反闭包：包含R且满足自反性质的最小关系
- 对称闭包，传递闭包
等价关系
- 满足自反，对称，传递
- 等价类$[a]_R$，代表元
- 集合的划分与集合上的等价关系一一对应（划分相同——等价关系本质相同）
- A/R：关于等价关系R的商集
序关系
- $\preceq$：自反，反对称，传递；偏序集$
- 可比较/不可比较
- 线序关系：任意两个元素都是可比较的（完全序关系）
- 序关系中的控制关系：y控制x，即$x\hat \preceq_\neq y$，且不存在$z,x\hat \preceq_\neq z ,z\hat\preceq_\neq y$
- 极大元，极小元
- 哈希图：最上方是极大元，最下方是极小元
- 最大元，最小元
- 最大元一定是极大元，最大元至多一个
- （子集的）上界/下界：不一定有，不一定唯一
- 最小上界/上确界；最大下界/下确界
集合的势
- 等势：$A \sim B$：存在双射
- $\mathscr P(E)$上的等价关系
- 有限集合
- 可数集合 ；可数无限集合：与自然数集合等势的集合
- 势的大小；支配：A和B的一个子集等势，则称B支配A，$A\preceq B$：偏序关系
- $A\prec \mathscr P(A) $
- 无限集合
- 每个无限集合都有一个可数无限子集
- 每个无限集合都和它的某个真子集集合等势
作业题目
4.7.设$A=\{1,2,3,4\},$在$\mathscr{P} (A)$上定义关系“$\sim$”。任给$S,T\in \mathscr{P}(A)$,
证明：“$\sim$”是$\mathscr{P}(A)$上的等价关系，并写出它的商集$\mathscr{P}(A)/\sim$。
- 自反性：$\forall S\in \mathscr P(A),|S|=|S|\Rightarrow S\sim S$
- 对称性：$\forall S,T\in \mathscr P(A),S\sim T\Rightarrow |S|=|T|\Rightarrow |T|=|S|\Rightarrow T\sim S$
- 传递性：$\forall S,T,V\in \mathscr P(A),S\sim T,T\sim V$
商集：$\{\{\empty\},\\\{\{1\},\{2\},\{3\},\{4\}\},\\\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\},\\\{\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\},\\\{\{1,2,3,4\}\}\}$
4.16.$A=\{a_1,a_2,…,a_n,…\}$是任意集合。在偏序集$<\mathscr{P}(A),\subseteq>$中取子集序列$\{a_1\},\{a_1,a_2\},\{a_1,a_2,a_3\},…,\{a_1,a_2,…,a_n,\},…$,它们的并集是否是$\mathscr{P}(A)$的一个极大元？为什么？
- 若A为有限集合，显然子集序列的并集为极大元（反证法）
- 若A是可数无限集合，则并集P可能是极大元，也可能不是极大元。举例：设A为自然数集合
- 是极大元： $a_i=i-1,\{a_1,a_2,…a_n,…\}=\{0,1,….n,..\}=A$
- 不是极大元：$a_i=i,\{a_1,a_2,…a_n,…\}=\{1,2,…n,…\}\subset A$
- 若A是不可数集合，则一定不是极大元，否则并集$P=A,{a_1,a_2,…a_n,…}$列举出了A的所有元素，与A是不可数集合矛盾。
