slide 14: 函数 Functions

基本定义

函数是一种特殊的关系。若二元关系 满足当 且 ，必定有 ，则这个二元关系 是一个函数。

更广泛的来讲，当多元关系 满足 且 ，必定有 ，则这个二元关系 是一个函数。

由于函数是比较特殊的关系，通常把 写作 ，即多元组前边是自变量，最后是因变量。

因此，关系是一种特殊的集合，而函数又是一种特殊的关系。所以

• 所有的关系运算（求逆、组合等），都可以用函数解决。
• 所有的与集合论有关的运算（并集交集等），也都可以用函数解决

lambda 记号

lambda 记号是用来更简洁的定义函数的一种工具。例如 ，表示的是， 是一个函数，参数是一个整数 ，返回值是 。即： 后面写的是参数（自变量），圆点 后面写的是返回值（因变量）。

函数的定义域，值域，像，到达域（domain，range，image，codomain）

• 定义域：略
• 值域：略
• 像：是值域的一个子集，这个子集包含由函数 映射来的一些元素。注意像并不是函数的值。函数的值是值域当中的某个元素，而函数的像是至于当中的某个子集。
• 到达域，又称对应域，与值域不同。值域是到达域的一个子集。满射函数的值域与到达域是相等的。

函数的单射，满射，双射（injective，surjective，bijective）

• 单射，是指，像中的每一个元素，都是由定义域中唯一的一个元素映射来的：
• 满射，是指，像中的每一个元素，都能被定义域中的元素映射得到：
• 双射，是指，既是单射，又是满射。即双射的两个集合，元素个数一定相等。

偏函数（partial function）

大概就是，定义域当中有的元素没有映射出去。

如果进一步限制约束偏函数的定义域，那么就会变成 total function（翻译过来可能是全函数）

比如，阶乘函数 fact(x) 的定义域如果是整数集，那么它就是一个偏函数，因为 fact(-1) 不知道。

多重集 multiset（bag）

顾名思义，是指元素可以出现多次的集合。其中，元素出现的次数叫做重数，multiplicity。

与 C++ 当中的 std::multiset 不同的是，数学概念上的多重集，是无序的。

一般来讲，可以用一种特殊的双方括号，，来表示多重集，虽然这种表示方法并不是正规的。

也可以把多重集理解为一个函数。

多重集的并比较特殊，有两种。第一种，符号与常规集合是一致的，运算示例：

第二种，符号里面多了个加号，运算示例：

其中， 的定义是：。而 指 bag 当中的元素 的重数。

序列 sequence

序列，保存了每个元素出现的位置（position）。类似于 std::map<T, std::vector<int>> pos;。

一般来讲，可以用特殊的尖括号 来表示序列，虽然这种表示方法也不是特别正规的。

例如， 是一个序列，其中 出现在 三个位置， 出现在 两个位置， 仅出现在 一次。

类似于多重集，序列也可以理解成一个函数。对于序列 ， 表示序列 的第 个位置上的元素。

可以写成集合的形式：。因此，序列的并运算，示例如下：

序列还有一个特殊的运算：，作用是返回一个有限集合的元素个数。若 是一个有限集合， 就是对应的 。如：。

不仅如此，序列还可以按照顺序连接起来，这个运算名叫 。例如，。由于这个弧线写起来有点麻烦，有时候直接用点 来表示连接，即 。

关于集合的用处的一些补充

• 在这门课当中，集合是用来辅助学习逻辑的。
• 数据库理论中，关系是基本的概念（Codd’s relational algebra）
• 计算理论当中，函数是基本的概念（Church’s λ-calculus）
• 语言理论当中，序列是基本的概念（Kleene’s regular expressions，Chomsky’s grammars 等）