集合与关系

集合代数

• 证明集合相等：相互包含
• 并集 交集 补集 差集- 对称差集\oplus
• 幂集 所有子集的集合：$2^A or \rho(A), |\rho(A)| = 2^n$
• 笛卡尔积
  • A \times B
  • 所有序偶的集合：$\{(a,b) | a \in A \wedge b \in B \}$
  • 有分配律
  • 笛卡尔积包含 ⇒ 对应位置包含

二元关系

• $A \times B$ 的任意子集 R
• 空关系也是二元关系
• 一个 R 是一个集合，代表一个关系，里面是所有满足这个关系的序偶
• 解释 + 内容
• $xRy \ or \ x{\not R}y$ ⇒ 存在/不存在这种关系（表示 x 和 y 的关系）
• 前域 后域
• 空关系 全关系
• 恒等关系 $R = I_A = \{(x,x) | x \in A\}$ ⇒ R 在 A 上的恒等关系
• 关系的表示
  • 集合 枚举 or 叙述
  • 关系图 $a_i \to b_i$
  • 关系矩阵 满足R → 1
• 性质
  • 自反性 vs. 反自反性：对角线 全1 vs. 全0
  • 对称性 vs. 反对称性：全对称 vs. 没有任何一个对称
  • 传递性 $(x, y) \wedge (y, z) \Rightarrow (x, z)$
  • $\star$
    • $\{ (a, a), (b, b)\}$ 既对称又反对称
    • $\{(a, b)\}$ 有传递性
• 复合运算 \circ
  • 无交换律
  • 结合律
  • 对 $\cup$ 满足分配律，对 $\cap$ 不满足分配律
  • 同一律
  • 对关系矩阵 类似矩阵乘法 但加法变或 乘法变与 布尔运算
• 幂运算
• 逆运算 R^{-1} 矩阵转置
• 闭包
  • 往 R 中添加最少元素
  • 自反r(R) 对称s(R) 传递t(R)
  
• Warshall 算法 ⇒ 计算传递闭包 先找出 (j, i) 和 (i, k) 再令 (j, k) = 1

特殊关系

• 等价关系 ⇒ 解决分类
• 等价类 [a]_R
• 等价类无交集
• 划分 & 二元等价关系 → 一一对应
  • 划分 并起来覆盖全部A
  • 如模m
  • R = $(A_1 \times A_1) \cup (A_2 \times A_2) \cup \cdot \cdot \cdot \cup (A_m \times A_m)$
• 偏序 $\preceq$
  • 提供次序关系
  • 用 Hasse 图表示偏序关系
    • 正常关系图 → 去自环 → 去传递边 → 箭头向上
    • 覆盖法 找较小元 再一层层向上找覆盖
  • 拓扑排序 Hasse图每层都只留任意一个
  • 可比
    • 如2和3互相都不能整除 即不可比
    • Hasse 图同一层不可比
  • 覆盖 → “相邻的” ⇒ 不存在 z 使 x < z < y
  • 极大元 极小元 ⇒ 可多个
  • 最大元 最小元 ⇒ 可不存在
  • 对偏序集A的子集B 在A中有B的
    • 上界 下界
    • 上确界 下确界

函数

• X → Y 映射
• 定义域内任意都能取到
• I 代表整数集
• f 是一个集合，f(x) 是一个值
• X = Y ⇒ f 是 x 上的函数
• 单射 满射 双射
• 复合
  • 复合顺序 从右到左
  • 映射的传递 $Y \to Z \circ X \to Y = X \to Z$
  • $g \circ f = g(f(x))$
  • 有相同性质的函数复合后性质不变
• 置换
  • $\pi$ → A自身的双射函数
  • 第一行升序
  • 置换的复合 从后往前
  • 可由循环的积写出来 ⇒ ( … ) ( … ) 然后一个数循环不写 下面 $\pi_3 = (1), \pi_4 = (13652)$ 有多个循环就多个括号
• 双射 ⇒ 存在逆函数 $f^{-1}$

题型

• 求幂集 or 笛卡尔积 多重？
• 写关系的集合
• 关系表示
• 性质？
• 一些证明
• 复合运算 & 逆 写集合
• 证明等价关系 3个性质
• 画 Hasse 图
• 证明函数性质 按定义
• 函数的复合
• 函数置换表示成循环的积
• 函数置换的复合 其实就相当于映射
• 证明有关复合运算的结论：\forall(x,z) \implies \exists y,(x,y) \in S \wedge (y,z) \in T 再用逻辑推理证明