- 集合定义：把一些事物汇集到一起组成一个整体就称作集合。
- 自然数集：在本书体系中，自然数集 N 包含 0。
- 表示方法：
- 列元素法：例如 A={a,b,c}。
- 谓词表示法：例如 B={x∣x∈R∧x2−1=0}。
- 包含关系：
- 子集 (Subset)：若 B 的每个元素都是 A 的元素，记作 B⊆A。
- 真子集 (Proper Subset)：若 B⊆A 且 B=A，记作 B⊂A。
- 相等：A=B⇔A⊆B∧B⊆A。
- 特殊集合：
- 空集：∅，是任何集合的子集。
- 幂集 (Power Set)：A 的全体子集构成的集合，记作 P(A) 或 2A。
- 若 ∣A∣=n，则 ∣P(A)∣=2n。
- 基本运算：
- 并集：A \cup B = \
- 交集：A \cap B = \
- 相对补集：A - B = \
- 对称差：A⊕B=(A−B)∪(B−A)
- 绝对补集：\sim A = E - A = \
- 广义运算：
- 广义并：\bigcup A = \
- 广义交：\bigcap A = \
- 分配律 (Distributive Laws)：
- A∪(B∩C)=(A∪B)∩(A∪C)
- A∩(B∪C)=(A∩B)∪(A∩C)
- 德·摩根律 (De Morgan's Laws)：
- ∼(A∪B)=∼A∩∼B
- ∼(A∩B)=∼A∪∼B
- 有序对：<x,y>，顺序重要。
- 笛卡儿积：A×B={<x,y>∣x∈A∧y∈B}。
- 大小：∣A×B∣=∣A∣⋅∣B∣。
- 域：domR (定义域), ranR (值域)。
- 逆关系：R−1={<y,x>∣<x,y>∈R}。
- 复合关系 (右复合)：
F∘G={<x,y>∣∃t(<x,t>∈F∧<t,y>∈G)}
- 幂运算：Rn+1=Rn∘R。
设 R 为 A 上的关系，矩阵为 M：
- 自反性 (Reflexive)：主对角线全为 1。
∀i,mii=1
- 反自反性 (Irreflexive)：主对角线全为 0。
- 对称性 (Symmetric)：矩阵关于主对角线对称。
M=MT
- 反对称性 (Antisymmetric)：对称位置不能同时为 1 (对角线除外)。
i=j⇒mij⋅mji=0
- 传递性 (Transitive)：
M2 的非零位置在 M 中也非零
- 自反闭包：r(R)=R∪IA
- 对称闭包：s(R) = R \cup R^
- 传递闭包：t(R)=R∪R2∪R3∪⋯ (使用沃舍尔算法计算)
- 定义：同时满足 自反、对称、传递 的关系。
- 等价类：[x]R={y∣xRy}。
- 商集：A/R={[x]R∣x∈A}。
- 定理：等价关系与集合的划分一一对应。
- 定义：同时满足 自反、反对称、传递 的关系 (记作 ≤)。
- 哈斯图 (Hasse Diagram)：简化偏序集的图形表示。
- 特殊元素：极小元、极大元、最小元、最大元、上界、下界。
这是基于 lsmath2.pdf 文件的核心概念总结，严格遵循你的 LaTeX 格式要求。
离散数学复习总结：集合论与二元关系
第6章 集合代数 (Set Algebra)
6.1 集合的基本概念
- 集合定义：把一些事物汇集到一起组成一个整体就称作集合，这些事物就是这个集合的元素或成员。
- 自然数集：在本书体系中，自然数集 N 包含 0。
- 表示方法：
- 列元素法：例如 A={a, b, c}。
- 谓词表示法：例如 B={x | x \in R \wedge x^2-1=0}。
- 包含关系：
- 子集 (Subset)：若 B 中的每个元素都是 A 中的元素，则称 B 是 A 的子集，记作 B \subseteq A。
- 真子集 (Proper Subset)：若 B \subseteq A 且 B \neq A，则称 B 是 A 的真子集，记作 B \subset A。
- 相等 (Equality)：A=B \Leftrightarrow A \subseteq B \wedge B \subseteq A。
- 特殊集合：
- 空集 (Empty Set)：不含任何元素的集合，记作 \emptyset，它是任何集合的子集。
- 全集 (Universal Set)：在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称该集合为全集 E。
- 幂集 (Power Set)：A 的全体子集构成的集合，记作 P(A) 或 2^A。
- 若 |A|=n，则 |P(A)|=2^n。
6.2 集合的运算
- 基本运算：
- 并集 (Union)：A \cup B = {x | x \in A \vee x \in B}。
- 交集 (Intersection)：A \cap B = {x | x \in A \wedge x \in B}。
- 相对补集 (Relative Complement)：A - B = {x | x \in A \wedge x \notin B}。
- 对称差集 (Symmetric Difference)：A \oplus B = (A - B) \cup (B - A) 或 A \oplus B = (A \cup B) - (A \cap B)。
- 绝对补集 (Absolute Complement)：\sim A = E - A = {x | x \in E \wedge x \notin A}。
- 广义运算：
- 广义并：\bigcup A = {x | \exists z (z \in A \wedge x \in z)}。
- 广义交：\bigcap A = {x | \forall z (z \in A \rightarrow x \in z)} (要求 A \neq \emptyset)。
6.3 有穷集的计数
- 文氏图 (Venn Diagram)：使用矩形表示全集，圆表示集合，阴影区域表示新组成的集合。
- 包含排斥原理 (Inclusion-Exclusion Principle)：
- 定理：设 A_i 是集合 S 中具有性质 P_i 的元素构成的子集。S 中不具有性质 P_1, \dots, P_n 的元素数为 |S| - \sum |A_i| + \sum |A_i \cap A_j| - span_16\dots + (-1)^n |A_1 \cap \dots \cap A_n|。
- 推论 (至少具有一条性质的元素数)：|\bigcup_{i=1}^n A_i| = \sum |A_i| - \sum |A_i \cap A_j| + span_17\dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|。
6.4 集合恒等式 (算律)
- 分配律 (Distributive Laws)：
-
-
- 德·摩根律 (De Morgan's Laws)：
- A - (B \cup C) = (A - B) \cap (A - C) (形式一)
- \sim (A \cup B) = \sim A \cap \sim B (形式二)
-
-
- 第7章 二元关系 (Binary Relations)
7.1 有序对与笛卡儿积
- 有序对 (Ordered Pair)：由两个元素 x, y 按一定顺序排列成的二元组 <x, y>。
- 性质：x \neq y \Rightarrow <x, y> \neq <y, x>。
- 笛卡儿积 (Cartesian Product)：A \times B = { <x, y> | x \in A \wedge y \in B }。
- 性质：如果不空且 A \neq B，则 A \times B \neq B \times A。
- 分配律：A \times (B \cup C) = (A \times B) \cup (A \times C)。
7.2 二元关系
- 定义：A \times B 的任何子集称作从 A 到 B 的二元关系 R。当 A=B 时称作 A 上的二元关系。
- 特殊关系：
- 全域关系 E_A = A \times A。
- 恒等关系 I_A = { <x, x> | x \in A }。
- 表示方法：
- 关系矩阵 (Relation Matrix)：M_R = (r_{ij})，若 x_i R x_j 则 r_{ij}=1，否则为 0。
- 关系图 (Relation Graph)：有向图，若 <x_i, x_j> \in R 则有一条从 x_i 到 x_j 的有向边。
7.3 关系的运算
- 域：
- 定义域：domR = {x | \exists y (<x, y> \in R)}。
- 值域：ranR = {y | \exists x (<x, y> \in R)}。
- 域：fldR = domR \cup ranR。
- 逆关系 (Inverse)：R^{-1} = { <y, x> | span_32<x, y> \in R }。
- 复合关系 (Composition)：教材采用右复合定义。F \circ G = { <x, y> | span_33\exists t (<x, t> \in F \wedge <t, y> \in G) }。
- 幂运算 (Powers)：R^0 = I_A, R^{n+1} = R^n \circ R。
7.4 关系的性质
设 R 是 A 上的关系：
- 自反性 (Reflexive)：\forall x (x \in A \rightarrow <x, x> \in R)。
- 反自反性 (Irreflexive)：\forall x (x \in A \rightarrow <x, x> \notin R)。
- 对称性 (Symmetric)：<x, y> \in R \rightarrow <y, x> \in R。
- 反对称性 (Antisymmetric)：<x, y> \in R \wedge <y, x> \in R \rightarrow x=y。
- 传递性 (Transitive)：<x, y> \in R \wedge <y, z> \in R \rightarrow <x, z> \in R。
- 矩阵特征：若 M^2 中某位置为1，则 M 中相应位置也为1。
7.5 关系的闭包 (Closures)
- 定义：包含 R 且具有特定性质的最小关系。
- 计算公式：
- 自反闭包：r(R) = R \cup R^0 = R \cup I_A。
- 对称闭包：s(R) = R \cup R^{-1}。
- 传递闭包：t(R) = R \cup R^2 \cup R^3 \cup \dots。
- 沃舍尔算法 (Warshall Algorithm)：用于在计算机上高效求解传递闭包。
7.6 等价关系与划分
- 等价关系 (Equivalence Relation)：满足自反性、对称性、传递性的关系。
- 等价类 (Equivalence Class)：[x]_R = {y | y \in A \wedge xRy}。
- 商集 (Quotient Set)：A/R = { [x]_R | x \in A }。
- 划分 (Partition)：等价关系与集合的划分是一一对应的。
7.7 偏序关系 (Partial Ordering)
- 偏序关系：满足自反性、反对称性、传递性的关系，记作 \leq。
- 偏序集：记作 <A, \leq>。
- 哈斯图 (Hasse Diagram)：简化偏序集的有向图（省略自环和传递边，方向隐含向上）。
- 特殊元素：
- 极小元 (Minimal) / 极大元 (Maximal)。
- 最小元 (Least) / 最大元 (Greatest)。
- 上界 (Upper Bound) / 下界 (Lower Bound)。
- 上确界 (Least Upper Bound) / 下确界 (Greatest Lower Bound)。