导图社区 离散数学
这是大学课程《离散数学》其中的一章,是我在复习过程中整理出来的其中一章,希望对大家有帮助!
编辑于2021-01-17 17:04:30集合论
集合
基本概念
集合的概念
集合就是人们直观上或思想上能够明确区分的一些确定的、彼此不同的事物所构成的整体。把组成这个集合的个别事物称为集合的元素。通常用大写英文字母A,B,…表示集合的名称,用小写英文字母a,b,…表示集合的元素.
集合的性质
.集合元素所表示的事物可以是具体的,也可以是抽象的.集合的元素既是任意的,又必须是确认的和可区分的
一个集合,若其组成的元素的个数是有限的,则称该集合为有限集;否则,称其为无限集
有限集S 中所含元素的数目称为集合S 的元数或基数,记作|S|.若|S|=0,则称S 为空集,记为Ø
集合的表示
列举法
列举法就是将集合的元素按某一次序逐一列在花括号内,并用逗号分开的方法.例如 A={a,b,c},B={1,2,3,…},C={2,4,6,…}.
描述法
用谓词描述出集合元素的公共特征,其形式为S={x|P(x)},即S 是使P(x)为真的x 的 全体.例如A={x|∃y(y∈Z∧x=2y)}
归纳定义法
定义
归纳定义法通常包括以下3步: (1)基本步:S0 非空且S0 中的任意元素均是A 的元素; (2)归纳步:给出一组规则,从A 的元素出发,依据这些规则所得到的仍是A 的元素; (3)极小化:若S 的任意元素均是A 的元素,并且S 满足(1)和(2),则S 与A 含有相同的元素
应用
自然数N的归纳定义
归纳法
第一归纳法
第二归纳法
集合的符号
子集
设有集合A 和B.若∀x(x∈A→x∈B),则称 A 是B 的子集,也称 A 包含于 B,或者B 包含A,记为AÍB 或BÊA;否则,称A 不是B 的子集
相等
设有集合A,B.若AÍB,且BÍA,则称 A 与B 相等,记为 A=B;否则,称 A与B不等
真子集
设有集合A,B.若 AÍB,且 A不等于B,则称 A 是B 的真子集,也称 A 真包含于B,或B 真包含A,记为AÌB 或BÉA
全集
若集合E 包含我们讨论的每一个集合,则称 E 是所讨论问题的完全集,简称 全集(或论述域).
全集是一个相对的概念,它根据所讨论的问题的不同而有所不同。
定理1:设A,B,C 是任意集合,则 (1)FÍA; (2)AÍA; (3)AÍE; (4)若AÍB 且BÍC,则AÍC; (5)若AÌB 且BÌC,则AÌC
空集
空集是存在的并且是唯一的,记为F
幂集
设A 是集合,则称{x|xÍA}为A 的幂集,记为r(A),有时记为2^A ,即 A 的幂 集是由A 的所有子集组成的集合
定理2:如果有限集A 的元数为n,则 |r(A)|=2Ùn =2Ù|A|.
集合的运算
基本运算符
文氏图(韦恩图)
文氏图是用点的集合作为集合的示意表示.通常用一个矩形区域表示全集E,矩形中的点表示全集E 中的元素.E 的子集用矩形内的圆形区域表示
包含排斥定理
设A,B 是两个有限集合,则 |AÈB|=|A|+|B|-|AÇB|.
定理5:设A1,A2,…,An 为有限集合,其元数分别为|A1|,|A2|,…|A2|,则
基本定律
环和、环积
集合的分类
有限集与无限集
等势
判定
可数集(可列集)与不可数集
可数集(可列集)
定义一
定义二
性质
不可数集
无限集关系
集合基数的比较
集合基数的关系
由|A|=|B|的定义可知,要证明A 和B 有相同基数,则要找一个从 A 到B 的双射,只要找一个从A 到B 的单射和一个从B 到A 的单射即可
集合基数的比较
二元关系
关系的基础
笛卡尔积
有序n元组
对于自然数n,n个客体a1,a2,…,an,按一定的次序排列成的一个序列,称为有序n元组,简称n元组,记为(a1,a2,…,an).ai 称为n 元组的第i个元素.
(a1,a2,…,an)=(b1,b2,…,bn)当且仅当ai=bi(i=1,2,…,n). 当n=2时的有序二元组称为序偶.
笛卡尔积概念及例子
笛卡尔积的性质
关系的基本概念
关系的概念
关系的表示法
集合表示法
关系图
关系矩阵
关系的性质
自反与反自反
1、在R里面,如果全部在X中的元素都有自己跟自己的关系,那他就是自反的 2、在R里面,如果全部在X中的元素都没有自己跟自己的关系,那他就是反自反 3、若两者都不是,那就是既不是自反的又不是反自反的
对称与反对称
1、在R里,若同时存在(x,y)和(y,x),则R是对称的 【x,y可以相等也可以不相等】 2、在R里,若只有(x,y)而没有(y,x)【x不等于y】, 那么R就是反对称的,不是对称的 特殊地,若直接没有(x,y)【x不等于y】,即恒等关系和 空关系,那么R还是反对称的
传递
1、在R里面,如果有(x,y)和(y,z)【首尾相接】的前提下同时有(x,z)那就是传递的 2、如果在R里面直接没有首尾相接的两个序偶 ,那还是传递的 【有首尾相接却不接起来就不是传递的,其余为传递的】
概要
关系的合成
关系的交、并、补、差
复合关系
定义
定理
满足结合律,不满足交换律
关系的幂
定义
定理
逆关系
定义
定理
闭包
闭包概念
r取自reverse 使次序颠倒的 s取自symmetry 对称 t取自transmit 传递
闭包性质
如果R是自反(对称或者传递)的,那么R的自反(对称或者传递)闭包是它自己
(1)中原因是当一个集合是自反时,任意添加其他序偶(闭包的原则就是向原集合中添加序偶),这个集合还是自反的 (2)中原因是(a,a)是对称的,当一个集合是对称是,它的自反和传递闭包必是在原集合的基础上添加若干(a,a) (3)中若R同时是传递和对称的,则r(R)也是传递的,若R只是传递的,则r(R)不是传递的
关系的划分
特殊的关系
次序关系
概念
次序关系是满足反对称的、传递的关系,根据其是自反的还是反自反的,可以把次序分为偏序关系和拟序关系
偏序关系
概念
分类
偏序集
偏序集的概念
偏序集中的特殊元素
注意: 1、y在Y之中 2、在确定各元之前先画出哈斯图 3、若存在极大元(同时存在多个最大值),那么就不会存在最大元
注意: 1、y在X或者Y中都有可能 2、在确定各界之前先画出哈斯图 3、留意确定上(下)界时,y必须是小于(大于)或等于所有Y中的元素,不满足此条件就是无上(下)界 4、上(下)界可以有多个,但是上(下)确界只能有一个或者没有 5、若没有上(下)界,那么就不会有上(下)确界
哈斯图
拟序关系
等价关系
概念
等价类
概念
重要举例
性质
根据等价类的性质,集合 X 上的等价关系R 所构成的类,它们两两互不相交而且覆盖整个集合 X.由它们构成一个新的集合———商集.
商集
函数关系
函数的概念
相等函数的判定
函数的集合
Y中元素数目是X中元素可以做选择的数目,X中元素数目表示可选择的次数
当A 或B 中至少有一个集合是空集时,可以分成左边的3种情况
特殊函数
常函数
恒等函数
单调函数
特征函数
自然映射
复合函数
逆函数
概念
性质