Randy's Notes

集合与函数

前言

在学习程序静态分析的时候,经常会遇到“格(lattice)”这个词,上网搜都找不到什么解释,后来才知道这是离散数学中的知识,而大二的时候上离散数学并没有讲到这一节,先复习一下集合与函数。

集合

集合是对象的一个无序的聚集,对象也称为集合的元素(element)或成员(member)。

高中数学的概念,之所以要提一下就是要说明集合是无序的,因为有时候我们需要一种不同的结构来表示有序的聚集,就是有序 $n$ 元组

有序 $n$ 元组

有序 $n$ 元组(ordered n-tuple) ($a$$1$, $a$$2$, …, $a$$n$) 是以 $a$$1$ 为第一个元素,$a$$2$ 为第二个元素,…,$a$$n$ 为第 $n$ 个元素的有序聚类。

两个有序 $n$ 元组,当且仅当每一对对应的元素都相等时,这两个有序 $n$ 元组相等。

幂集

给定集合 $S$,$S$ 的幂集(power set)是集合 $S$ 所有子集的集合。$S$ 的幂集记作

例如:当 $S=${$0, 1, 2$} 时,幂集为

{∅, {$0$}, {$1$}, {$2$}, {$0, 1$}, {$0, 2$}, {$1, 2$}, {$0, 1, 2$}}

笛卡尔积

有序二元组称为序偶(ordered pair),两个集合的笛卡尔积(同理推广到多个集合):

令 $A$ 和 $B$ 为集合。$A$ 和 $B$ 的笛卡尔积(Cartesian product)用 $A × B$ 表示,是所有有序偶 ($a$, $b$) 的集合,其中 $a∈A$ 且 $b∈B$。于是

$A × B = $ {$(a, b) | a∈A ∧ b∈B$}

注意 $A × B ≠ B × A$,除非 $A = $∅ 或 $B = $∅ 或 $A = B$

例如:
$A = $ {$1, 2$} 和 $B = $ {$a, b, c$} 的笛卡尔积是

$A × B = $ {$(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)$}

笛卡尔积 $A × B$ 的一个子集 $R$ 称为是从集合 $A$ 到集合 $B$ 的一个关系(relation)。$R$ 的元素是序偶,其中第一个元素属于 $A$ 而第二个元素属于 $B$

函数

有时候需要为一个集合中的每个元素指派另一个集合(也可以是该集合本身)中的每一个特定元素。例如对每个学生指派一个从 {$A, B, C, D, F$} 中的字母作为他的成绩,这种指派就是函数的一个例子,也称为映射(mapping)或者变换(transformation)

令 $A$ 和 $B$ 为非空集合。从 $A$ 到 $B$ 的函数 $f$ 是对元素的一种指派,对 $A$ 的每个元素恰好指派 $B$ 的一个元素。如果 $B$ 中的元素 $b$ 是唯一由函数 $f$ 指派给 $A$ 中元素 $a$ 的,则我们就写成 $f(a) = b$。如果 $f$ 是 从 $A$ 到 $B$ 的函数,就写成 $f: A → B$

如果 $f$ 是从 $A$ 到 $B$ 的函数,则 $A$ 是 $f$ 的定义域(domain),而 $B$ 是 $f$ 的陪域(codomain)。如果 $f(a) = b$,则 $b$ 是 $a$ 的像(image),而 $a$ 是 $b$ 的原像(preimage)。$f$ 的值域(range)或像是 $A$ 中元素的所有像的集合。如果 $f$ 是 $A$ 到 $B$ 的函数,则说 $f$ 把 $A$ 映射(map)到 $B$

疏影横斜水清浅,暗香浮动月黄昏