离散数学1

集合的定义

集合是由指定范围内的满足给定条件的所有对象聚集在一起构成，每一个对象称为这个集合的元素。

什么是集合呢？生活中到处都是，例如所有英文字母，中国所有的美食，某个广场的所有建筑

集合的数学符号：

用带或不带下标的大写英文字母表示集合:

A,B,C, A1,B1,C1....

用带或不带下标的小写英文字母表示元素:

a,b,c a1,b1,c1

常见的几大数集：

N:自然数集

Z:整数集

Q:有理数集

R:实数集

若 a 是集合 A 中的元素，则称 a属于A，记为 a ∈ A

若 a 不是集合 A 中的元素，则称 a不属于A，记为 a /∈A

集合的表示

常见的有这几种方法

枚举法：列出集合中的全部元素或者仅列出一部分元素，其余用省略号(...)表示

例如

A={a,b,c,d}

B={2,4,6,8,10,.....}

当然用的比较多的还是叙述法

通过刻画集合中元素所具备的某种性质或特性来表示一个集合

P={x|P(x)}

例如A={x|x是鱼类中的热带鱼类}

B = {x|x ∈ Z, x < 10}

文氏图

文氏图是利用平面上的点来做成对集合的图解方法。一般使用平面上的方形或圆

形表示一个集合，而使用平面上的一个小圆点来表示集合的元素。

集合的基数

集合 A 中的元素个数称为集合的基数(base number)，记为|A|

有限集和无限集的区分就在这里

空集、全集

不含任何元素的集合叫做空集(empty set)，记作 ∅.

空集可以符号化为 ∅ = {x|x /= x}

因为这样的集合是不存在的

要记住空集是绝对唯一的。

针对一个具体范围，我们考虑的所有对象的集合叫做全集(universal set)，记作 U 或 E.

在文氏图一般使用方形表示全集。

在我国的人口普查中，全集是由我国所有人组成的。

全集是相对唯一的。会根据你的需求来变化

集合之间的关系

元素的基本特征:无序和不同

相等关系：如果A和B具有相同的元素，那么称两个集合相等。

外延性：两个集合 A 和 B 相等，当且仅当它们的元素完全相同，记为 A = B, 否则 A 和 B不相等，记为A /= B

包含关系： A 中含有 B 中所有的元素，这种情况称为A 包含 B.

包含也有两种：包含和真包含

与之同时也会出现子集和真子集

已知 A = {1, 2, 3, 4}, B = {1, 2, 4}, C = {2, 3}, D = {3, 2}，可见

A ⊆ A,B⊆A, C ⊆ A,D ⊆ A

如何证明集合是否相等？

设 A,B为任意两个集合，则 A = B ⇔ A ⊆ B 并且 B ⊆ A

首先证明 A ⊆ B：∀x∈ A, · · · , x ∈ B. ∴ A ⊆ B

其次证明B⊆ A:∀x∈ B, · · · , x ∈A. ∴ B⊆A

结合以上两点，可得A=B

来看个实列

设 A = {a,b,c}，求出 A 的所有子集。

由于 |A|=3，因而 A 的子集可能包含的元素个数 m = 0, 1, 2, 3

很容易得出8个集合

推广下去对于任意 n 元集合 A，他的m元子集个数为Cmn

累加后根据二项式定理也就得出总和为2**n

二项式定理：

因为我们这里a和b的值是1，所以可以推广出来

幂集：设 A 为任意集合，把 A 的所有不同子集构成的集合叫做 A 的幂集(power set)，记作 P(A)

集合的运算以及运算定理

并集:设 A, B 是两个集合，则集合 A 与 B 的并集定义为A ∪ B = {x|x ∈ A 或 x ∈ B}

交集:设 A, B 是两个集合，则集合 A 与 B 的交集定义为A ∩ B = {x|x ∈ A 且 x ∈ B}

补集:设 U 是全集，则集合 A 的补集定义为：—A={x|x/∈A}

差集:设 A,B 是两个集合，则集合 A 与 B 的差集定义为A-B={x|x∈A并且x/∈B}

对称差集：设 A,B 是两个集合，则集合 A 与 B 的对称差集定义为A ⊕ B={x|(x∈A并且x/∈B)或者(x∈B并且x/∈A)}

并集和交集的扩展:

设 A1,A2, · · · , An 是任意 n 个集合，则这 n 个集合的并集是包含那些至少是这组集合中一个集合成员的元素的集合

设 A1,A2, · · · , An 是任意 n 个集合，则这 n 个集合的交集是包含那些至少是这组集合中一个集合成员的元素的集合 \[ 幂等律： A ∪ A = A ; A ∩ A = A \]

\[ 交换律： A ∪ B = B ∪ A ; A ∩ B = B ∩ A \]

\[ 结合律： A ∪ ( B ∪ C ) = ( A ∪ B ) ∪ C , A ∩ ( B ∩ C ) = ( A ∩ B ) ∩ C A \]

\[ 同一律： A ∪ ∅ = A , A ∩ U = A \]

\[ 零律： A ∪ U = U , A ∩ ∅ = ∅ A \]

\[ 分配律： A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C ) , A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C ) \]

\[ 吸收律： A ∪ ( A ∩ B ) = A , A ∩ ( A ∪ B ) = A \]

\[ 矛盾律和排空律： A ˉ ∩ A = ∅ , A ˉ ∪ A = U \]

\[ 双重否定律： A ‾ ‾ = A \]

\[ 德摩根律： A ∪ B ‾ = A ˉ ∩ B ‾ , A ∩ B ‾ = A ‾ ∪ B ‾ \]

自然数集以及其相关分类和定律

皮亚诺公理：基于序数的自然数定义公理。定理包括：

0是自然数
每个自然数n都有一个后继，这个后继也是一个自然数，记为 S ( n ) 
两个自然数相等，当且仅当他们有相同的后继，即 m = n ，当且仅当 S ( m ) = S ( n ) S(m)=S(n)
没有任何自然数的后继是0
（归纳公理）若 φ是一个自然数的预测
    如果  φ(0)为真
    当 φ(n)为真，则有 φ(S(n))为真
    则 φ(n)对任何自然数成立