Lec2 Logic and Proof, Sets, and Function

由于离散数学PPT过于杂乱，这里只取重点的进行记录，如果是比较细枝末节的，本篇不会记录。

集合的幂集（Power Set）及其性质

定义：

集合 $ S $ 的幂集 $ P(S) $ 是集合 $ S $ 的所有子集的集合。即，$ P(S) $ 是包含所有 $ S $ 的子集的集合。
符号表示：$ P(S) { x x S } $，其中 $ x $ 是集合 $ S $ 的一个子集。

例子：

对于集合 $ S = {a, b} $，其幂集为：$ P({a, b}) = {, {a}, {b}, {a, b}} $ 其中包含了 $ S $ 的所有子集，空集 $ $，以及包含单一元素和所有元素的子集。

幂集的大小：

幂集 $ P(S) $ 的元素个数是集合 $ S $ 的子集的数量。对于一个有限集合 $ S $，如果 $ |S| = n $，那么 $ |P(S)| = 2^n $，即幂集的大小是集合 $ S $ 元素个数的 2 的幂。
举例：
- 如果 $ |S| = 2 $，即 $ S = {a, b} $，则 $ |P(S)| = 2^2 = 4 $，对应的子集是 $ , {a}, {b}, {a, b} $。
- 对于 $ S = {a, b, c} $，则 $ |P(S)| = 2^3 = 8 $。

幂集的大小与原集合的关系：

对于任何集合 $ S $，有以下关系：$ |P(S)| = 2^{|S|} $，即幂集的大小是原集合大小的 2 的幂。
幂集的元素个数永远大于原集合的元素个数，即 $ |P(S)| > |S| $。

无限集合的幂集：

对于无限集合 $ S $，其幂集的大小大于原集合本身的大小。
- 例如，集合 $ $（自然数集合）的幂集 $ P() $ 的大小严格大于 $ $ 的大小。
- 这意味着，不同的无限集合可能有不同的大小。例如，实数集合 $ $ 的大小大于自然数集合 $ $ 的大小，这表明存在不同大小的无限集合。

总结：

有限集合的幂集大小： 对于有限集合 $ S $，幂集的大小为 $ 2^{|S|} $。
无限集合的幂集： 对于无限集合 $ S $，其幂集的大小总是大于 $ S $ 的大小。不同的无限集合可能具有不同的大小。

容斥原理：

某个研究所共有 170 名职工，其中：

120 人会英语
80 人会法语
60 人会日语
50 人会英语和法语
25 人会英语和日语
30 人会法语和日语
10 人会英语、日语和法语

问：有多少人不会这三种语言？

解题步骤：

1. 设置集合：

设全集为 $ U $，其中包含所有 170 名职工。
设 $ E $ 为会英语的人集合，$ F $ 为会法语的人集合，$ J $ 为会日语的人集合。

根据题意，有以下已知条件：

$ |U| = 170 $
$ |E| = 120 $（会英语的人数）
$ |F| = 80 $（会法语的人数）
$ |J| = 60 $（会日语的人数）
$ |E F| = 50 $（会英语和法语的人数）
$ |E J| = 25 $（会英语和日语的人数）
$ |F J| = 30 $（会法语和日语的人数）
$ |E F J| = 10 $（会英语、法语和日语的人数）

2. 求至少会一种语言的人数：

我们要求至少会英语、法语或日语的职工数量，使用集合的并集公式： $ |E F J| = |E| + |F| + |J| - |E F| - |E J| - |F J| + |E F J| $ 代入已知数值： $ |E F J| = 120 + 80 + 60 - 50 - 25 - 30 + 10 $ 计算过程： $ 120 + 80 + 60 = 260 $ $ 50 + 25 + 30 = 105 $ $ 260 - 105 = 155 $ $ 155 + 10 = 165 $ 所以，至少会英语、法语或日语的职工数量是 165 人。

3. 求不会三种语言的人数：

所有职工总数为 170 人，至少会一种语言的职工为 165 人，因此不会这三种语言的职工数量为： $ |U - (E F J)| = |U| - |E F J| = 170 - 165 = 5 $

结论：

因此，有 5 人不会这三种语言。

函数的一些概念：

定义回顾：
- 函数的定义： 如果我们有一个函数 $ f $，并且函数的定义是“$ f $ 是一个将这班的学生映射到成绩集合 $\{A, B, C, D, E\}$ 的函数”，则这表示每个学生在这个班级上都有一个对应的成绩（即函数值），而这些成绩从集合 $\{A, B, C, D, E\}$ 中选取。
- 值域（Range）： 函数的值域是指函数 $ f $ 的所有输出值（也就是所有学生可能得到的实际成绩）。如果某些成绩从未出现在实际结果中，则这些成绩不会出现在值域中。
- 定义域（Domain）： 函数的定义域是输入的集合。在这个问题中，定义域就是这班的所有学生。
- 余域（Codomain）： 函数的余域是函数值可能属于的集合，通常是函数声明时给定的目标集合。在这个问题中，余域是 $\{A, B, C, D, E\}$，因为这是成绩的集合。
第一部分： 你告诉我“$ f $ 是一个将这班的学生映射到成绩集合 $\{A, B, C, D, E\}$ 的函数”，因此：
- 余域（Codomain）： 根据声明，$ f $ 的余域就是你提供的成绩集合 $\{A, B, C, D, E\}$，即：
  Codomain = $\{A, B, C, D, E\}$
- 值域（Range）： 此时我们还不知道实际有哪些成绩被分配给学生，因此我们无法确定具体的值域，值域可以是一个函数可能输出的所有成绩的子集。因此，Range = 未知（尚未确定）。
第二部分： 现在假设成绩实际上全部是 A 和 B，那么：
- 值域（Range）： 实际上只有 A 和 B 出现在学生的成绩中，所以函数 $ f $ 的值域将仅包含这两种成绩。因此： Range = $\{A, B\}$
- 余域（Codomain）： 余域仍然是最初声明的成绩集合 $\{A, B, C, D, E\}$，即使只有 A 和 B 出现，余域依然不变。所以： Codomain = $\{A, B, C, D, E\}$

函数的单射、满射和双射

单射（Injection）：
- 定义： 一个函数 $ f: A B $ 被称为单射（或称为一一映射），如果对于 $ A $ 中的不同元素 $ a_1 $ 和 $ a_2 $，当且仅当 $ f(a_1) = f(a_2) $ 时，才有 $ a_1 = a_2 $。也就是说，不同的输入对应不同的输出。
- 数学符号表示： 对于任意 $ a_1, a_2 A $，如果 $ f(a_1) = f(a_2) $，则 $ a_1 = a_2 $。
- 通俗理解： 单射确保了没有两个不同的元素映射到同一个值。
满射（Surjection）：
- 定义： 一个函数 $ f: A B $ 被称为满射（或称为到射），如果对 $ B $ 中的每一个元素 $ b $，都存在至少一个 $ a A $，使得 $ f(a) = b $。换句话说，函数的值域覆盖了余域中的所有元素。
- 数学符号表示： 对于任意 $ b B $，存在至少一个 $ a A $，使得 $ f(a) = b $。
- 通俗理解： 满射保证了每个目标值都有对应的源值。
双射（Bijection）：
- 定义： 一个函数 $ f: A B $ 被称为双射（或称为一一对应），如果它是既单射又满射。即，函数在“映射”上既保证了不重复（单射），又保证了目标值的完全覆盖（满射）。
- 数学符号表示： 既是单射又是满射，形式上可以写为：
  $ f $ 是双射当且仅当 $ f $ 同时满足：
  - 对于任意 $ a_1, a_2 A $，如果 $ f(a_1) = f(a_2) $，则 $ a_1 = a_2 $（单射）。
  - 对于任意 $ b B $，存在至少一个 $ a A $，使得 $ f(a) = b $（满射）。
- 通俗理解： 双射意味着每个输入值都对应唯一的输出值，且每个输出值都有唯一的输入值。
总结：
- 单射（Injection） = 一一映射，确保不同的输入有不同的输出。
- 满射（Surjection） = 到射，确保每个输出值都有对应的输入值。
- 双射（Bijection） = 一一对应，既是单射又是满射，确保输入和输出之间存在一一对应关系。