离散数学：集合与关系

离散数学知识点介绍：集合与关系

离散数学是计算机科学和数学的基础学科之一，其中集合与关系是非常重要的内容。本文将介绍集合、关系以及函数的基础知识，并结合公式与例题帮助理解这些概念。

一、集合

**集合（Set）**是离散数学的基本概念，用于表示对象的集合。一个集合中的元素是唯一且无序的。常见的集合运算包括子集、并集、交集、差集、补集、笛卡尔积等。

1.1 集合的定义

一个集合可以定义为一组不同对象的无序集合，通常用大写字母表示集合，用花括号表示集合内的元素，例如：

A = \{1, 2, 3, 4\}, \quad B = \{3, 4, 5, 6\}

集合 $A$ 和 $B$ 包含一些整数元素。

1.2 子集

如果集合 $A$ 的所有元素都属于集合 $B$ ，则称 $A$ 是 $B$ 的子集，记作：

A \subseteq B

例如，如果 $A = \{1, 2\}$ ， $B = \{1, 2, 3, 4\}$ ，则 $A \subseteq B$ 。

1.3 并集

两个集合的并集是由两个集合的所有元素组成的集合，记作：

A \cup B = \{x \mid x \in A \text{ 或 } x \in B\}

例如， $A = \{1, 2, 3\}$ ， $B = \{3, 4, 5\}$ ，则 $A \cup B = \{1, 2, 3, 4, 5\}$ 。

1.4 交集

两个集合的交集是同时属于两个集合的元素的集合，记作：

A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}

例如， $A = \{1, 2, 3\}$ ， $B = \{3, 4, 5\}$ ，则 $A \cap B = \{3\}$ 。

1.5 差集

差集表示集合 $A$ 中的元素但不属于 $B$ 的元素集合，记作：

A - B = \{x \mid x \in A \text{ 且 } x \notin B\}

例如， $A = \{1, 2, 3\}$ ， $B = \{3, 4, 5\}$ ，则 $A - B = \{1, 2\}$ 。

1.6 笛卡尔积

集合 $A$ 和 $B$ 的笛卡尔积是由所有可能的有序对 $(a, b)$ 组成的集合，记作：

A \times B = \{(a, b) \mid a \in A, b \in B\}

例如， $A = \{1, 2\}$ ， $B = \{x, y\}$ ，则 $A \times B = \{(1, x), (1, y), (2, x), (2, y)\}$ 。

1.7 幂集

集合 $A$ 的幂集是所有 $A$ 的子集构成的集合，记作 $\mathcal{P}(A)$ 。如果 $A = \{1, 2\}$ ，则 $A$ 的幂集为：

\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}

二、关系

**关系（Relation）**是集合与集合之间的联系。关系可以用集合的笛卡尔积的一部分来表示。例如，如果 $A$ 和 $B$ 是两个集合， $R$ 是从 $A$ 到 $B$ 的关系，则 $R$ 是 $A \times B$ 的一个子集。

2.1 关系的定义

如果 $R$ 是集合 $A$ 上的一个二元关系，则 $R \subseteq A \times A$ 。我们可以说两个元素 $a, b \in A$ 存在关系 $R$ ，记作 $aRb$ ，如果 $(a, b) \in R$ 。

2.2 关系的性质

自反性：对所有 $a \in A$ ， $aRa$ 。例如，集合 $\{1, 2\}$ 上的关系 $\{(1, 1), (2, 2)\}$ 是自反的。
对称性：对所有 $a, b \in A$ ，如果 $aRb$ ，则 $bRa$ 。例如，关系 $\{(1, 2), (2, 1)\}$ 是对称的。
传递性：对所有 $a, b, c \in A$ ，如果 $aRb$ 且 $bRc$ ，则 $aRc$ 。例如，关系 $\{(1, 2), (2, 3), (1, 3)\}$ 是传递的。
反自反性：对所有 $a \in A$ ， $aRa$ 不成立。也就是说， $aRa$ 永远为假。

2.3 等价关系与偏序关系

等价关系：同时满足自反性、对称性和传递性的关系。例如，集合 $\{1, 2, 3\}$ 上的关系 $\{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ 是等价关系。
偏序关系：同时满足自反性、传递性和反对称性的关系。偏序关系可以用哈斯图表示。

2.4 哈斯图

**哈斯图（Hasse Diagram）**是一种用于表示偏序集的图形。哈斯图通过省略自反关系和冗余的传递关系，简化了偏序集的表示。

三、函数

**函数（Function）**是从一个集合到另一个集合的映射，常用来描述输入与输出之间的确定关系。

3.1 函数的定义

如果 $A$ 和 $B$ 是两个集合，函数 $f: A \to B$ 表示集合 $A$ 中的每一个元素通过 $f$ 都唯一地映射到集合 $B$ 中的一个元素。例如：

f(x) = x^2

是一个从实数集合映射到非负实数集合的函数。

3.2 单射、满射和双射

单射（Injective）：如果不同的输入有不同的输出，即对于所有 $a_1 \neq a_2$ ， $f(a_1) \neq f(a_2)$ 。
满射（Surjective）：如果每个 $B$ 中的元素都有对应的 $A$ 中的元素，即对于每个 $b \in B$ ，都存在 $a \in A$ 使得 $f(a) = b$ 。
双射（Bijective）：如果函数既是单射又是满射，则称为双射。双射函数是可逆的，即存在反函数 $f^{-1}$ 使得 $f^{-1}(f(a)) = a$ 。

3.3 复合函数

如果 $f: A \to B$ 和 $g: B \to C$ 是两个函数，那么可以定义复合函数 $g \circ f: A \to C$ ，表示先应用 $f$ ，然后应用 $g$ ，即：

(g \circ f)(x) = g(f(x))

例题

例 1：给定集合 $A = \{1, 2, 3\}$ ， $B = \{x, y\}$ ，求 $A \times B$ 的笛卡尔积。

解答：

A \times B = \{(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)\}

例 2：判断集合 $R = \{(1, 1), (2, 2), (1, 2), (2, 1)\}$ 是否为等价关系。

解答：

自反性： $R$ 包含 $(1, 1)$ 和 $(2, 2)$ ，故满足自反性。
对称性： $R$ 包含 $(1, 2)$ ，且包含 $(2, 1)$ ，故满足对称性。
传递性

：没有需要传递的情况，故满足传递性。

因此， $R$ 是等价关系。

结论

通过这篇博客，我们介绍了离散数学中集合、关系和函数的基础概念，并结合公式与例题帮助理解这些内容。集合与关系是离散数学中的基础知识，对于理解更复杂的数学结构和算法具有重要意义。

目录