离散数学及应用 -- 02 基本结构：集合、函数、序列、求和与矩阵-Toy模板网

这篇具有很好参考价值的文章主要介绍了离散数学及应用 -- 02 基本结构：集合、函数、序列、求和与矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

集合

集合运算

函数（映射、变换）

序列

求和

编辑集合的基数

矩阵

集合

集合是对象的一个无序的聚集，对象也称为集合的元素或成员。集合包含它的元素。

∈A：a是集合A中一个元素

∉A：a是集合A中一个元素

描述集合的方式：

花名册方法：在可能的情况下一一列出集合中的元素；有明显规律的就先列出集合的某些元素，然后用省略号代替。

集合构造器：通过描述作为集合的成员必须具备的性质来刻画集合中的那些元素

eg.O={x|x是小于10的正奇数}

= {0,1,2,3...}	自然数集
= {...,-2,-1,0,1,2,...}	整数集
$离散数学与矩阵,学习$ = {1,2,3,...}	正整数集
= {p/q \| p∈，q∈，且q≠0}	；有理数集
	实数集
$离散数学与矩阵,学习$	正实数集
	复数集

A和B是相同的集合：当且仅当A和B拥有相同的元素，即

空集：或者 { }表示，空集是一个特殊的不含任何元素的集合

单元素集：只有一个元素的集合

文氏图：全集+其他集合

离散数学与矩阵,学习

子集：当且仅当

对于任意集合S，(i) , (ii)

真子集：，当且仅当集合A是集合B的子集但A≠B

即

证明集合A和B相等，就证明和

集合的大小：令S为集合。如果S中恰有n个不同元素(n为非负整数)，我们就说S是有限集，而n是S的基数。S的基数记为 | S |。

一个集合称为是无限的如果它不是有限的。

幂集：给定集合S，S的幂集是集合S所有子集的集合。

如果一个集合有n个元素，那么它的幂集就有个元素

有序n元组：是以为第1个元素，为第2个元素 , ... , 为第n个元素的有序聚集

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

有序二元组称为序偶。序偶(a,b)和(c,d)相等当且仅当 a=c 和 b=d。

笛卡儿积：令A和B为集合。笛卡儿积用表示，是所有序偶 (a,b) 的集合，其中 a∈A 且 b∈B 。

笛卡儿积的个数 = 集合A中元素个数集合B中元素个数

笛卡儿积和并不相等，除非或或或

集合的笛卡儿积用表示，是有序n元组( , , ... , )的集合，其中属于 , 。

即

集合A和自身的笛卡儿积：

关系：笛卡儿积的一个子集 R 称为是从集合A到集合B的一个关系。R的元素是序偶，其中第一个元素属于A而第二个元素属于B。

使用带量词的集合符号：

是的简写，表示P(x)在集合S所有元素上的全称量化

是的简写，表示P(x)在集合S所有元素上的存在量化

真值集：给定谓词P和论域D，定义P的真值集为D中使P(x)为真的元素x组成的集合。

P(x)的真值集记为。

eg. 谓词P(x) 是 ''|x| = 1''，论域是整数集合。

这里P的真值集为{-1 , 1} 。

在论域上为真当且仅当P的真值集是集合。

在论域上为真当且仅当P的真值集非空。

集合运算

令A和B为集合：

两个集合称为是不相交的，如果它们的交集为空集。

容斥原理（包含排斥原理）： $离散数学与矩阵,学习$

差集：

补集：

集合恒等式：可以通过成员表（与真值表类似，0&1）或下列恒等式证明

离散数学与矩阵,学习

扩展的并集和交集

一组集合的并集是包含那些至少是这组集合中一个集合成员的元素的集合

一组集合的交集是包含那些属于这组集合中所有成员集合的元素的集合

函数（映射、变换）

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

如果 f 是从A到B的函数（f 把A映射到B），则A是 f 的定义域，B是 f 的陪域。

如果 f(a)=b，则b是a的像，a是b的原像。

f 的值域或像是A中元素的所有像的集合。

陪域就是集合B的所有元素，而值域是被指派到的元素。

函数相等：当且仅当两个函数有相同的定义域、陪域，且定义域中的每个元素映射到陪域中相同的元素。

实值函数：函数其陪域是实数集合。

整数集函数：函数其陪域是整数集合。

具有相同定义域的两个实值函数或两个整数集函数可以相加和相乘。

令和是从A到R的函数，那么 $离散数学与矩阵,学习$ 和也是从A到R的函数。

$离散数学与矩阵,学习$

令 f 为从A到B的函数，S为A的一个子集。S在函数 f 下的像是由S中元素的像组成的B 的子集。用 f(S)表示S的像，则

f(S)是一个集合

令A={a,b,c,d,e}，而B={1,2,3,4}，且 f(a)=2, f(b)=1, f(c)=4, f(d)=1及f(e)=1。子集S={b,c,d}的像是集合 f(S)={1,4}

一对一函数（单射函数）：这种函数不会把同样的值赋给定义域中两个不同元素。

即

或

在定义域内:

递增	当时，有
严格递增	当时，有
递减	当时，有
严格递减	当时，有

映上函数（满射函数）：函数值域与陪域相等，即陪域中每个成员都是定义域中某个元素的像

即当且仅当对每个有元素使得

或

双射函数：函数既是一对一的又是映上的

如果 f 时从集合A到自身的函数。如果A是有限的，那么 f 是一对一的当且仅当它是映上的。

假设 f：A→B

要证明 f 是单射的	证明对于任意,如果,则
要证明 f 不是单射的	找到特定的,使得且
要证明 f 是满射的	考虑任意元素,并找到一个元素使得
要证明 f 不是满射的	找到一个特定的,使得对于任意有