离散数学（集合论）

您所在的位置：网站首页 › 可数集的交集必为可数集吗 › 离散数学（集合论）

离散数学（集合论）

2024-01-02 18:09| 来源: 网络整理| 查看: 265

集合的基本概念

集合的元素

属于$\in$

空集$\varnothing$ 全集

有限集、无限集

集合的元素数（基数）：特别的：| $\varnothing$ |=0，|{$\varnothing$}|=1

集合的特征：确定性、互异性、无序性、多样性

集合相等：两个集合A和B的元素完全一样

子集(subset) ：设A，B是两个集合，若A的元素都是B的元素，则称A是B的子集，也称B包含A，或A包含于B记以A $\subseteq$B

若A$\subseteq$B，且A$\ne$B，则称A是B的真子集(proper subset)，也称B真包含A，或A真包含于B，记以A$\subset$B

集合的运算及性质：

并集(Union)：

交集(Intersection)：

差集(Difference)：

余集(Complement)：

环和（对称差）：

环积：

集合的算律：

集合的证明题：

集合的幂与笛卡尔积：

幂集的性质：

有序n元组(ordered n-tuple)：(a1,a2 ,… ,an)

有序对(ordered pairs)：当n=2 时，将其称作有序对，也称作序偶，或有序二元组

有序对特点：

若a$\ne$b,则（a，b）$\ne$（b，a）两个有序对(a,b)和(c,d)相等当且仅当a=c，b=d

笛卡儿积(Cartesian product)：

笛卡儿积的性质：

|A$\times$B|=|A| $\times$|B|；

对任意集合A，有A$\times$$\varnothing$=$\varnothing$，$\varnothing$$\times$A=$\varnothing$；

笛卡儿积运算不满足交换律，即A$\times$B$\ne$B$\times$A；

笛卡儿积运算不满足结合律，即(A$\times$B)$\times$C$\ne$A$\times$(B$\times$C)

笛卡儿积运算对并和交运算满足分配律

设A，B，C，D是集合，若A$\subseteq$C且B$\subseteq$D，则A$\times$B $\subseteq$ C$\times$D。

证明集合的包含关系的常用方法：

利用定义：首先任取x$\in$A，再演绎地证出x$\in$B成立设法找到一个集合T,满足A$\subseteq$T且T$\subseteq$B,由包含关系的传递性有A$\subseteq$B. 利用A$\subseteq$B的等价定义,即A$\cup$B=B,A$\cap$B=A或A-B=$\varnothing$来证. 利用已知包含式的并、交等运算得到新的包含式反证法

证明集合相等的常用方法：

若A，B 是有限集，证明A=B可通过逐一比较两集合所有元素均一一对应相等，若A，B 是无限集，通过证明集合包含关系的方法证A $\subseteq$ B，B $\subseteq$ A即可

反证法

利用集合的基本算律以及已证明的集合等式，通过相等变换将待证明的等式左（右）边的集合化到右（左）边的集合，或者两边同时相等变换到同一集合

关系

非空集合中的空关系是反自反的、对称的、反对称的和传递的，但不是自反的；

空集合中的空关系则是自反的、反自反的、对称的、反对称的和传递的。

关系的定义：xRy

关系的特点：

A$\times$A的任一子集都是A上的一个关系

若|A|=n，则A上的关系有$2^{\mathrm{n}^2}$个

A上有三个特殊关系，即

空关系$\varnothing$；

全域关系EA=A$\times$A；

相等关系IA={(x,x)|x$\in$A}

关系的表示：

集合表示：

设A={1,2,3,4}， A上的关系R=

关系矩阵

关系图：

关系作为集合的运算：

关系的交：R ∩ S={(x,y)|x$\in$A, y$\in$A,xRy且xSy} 关系的并：R∪ S={(x,y)| x$\in$A, y$\in$A ,xRy或xSy} 关系的差：R - S={(x,y)| x$\in$A, y$\in$A ,xRy并且xS/y}

逆关系：$\mathrm{R}^{-1}$ ={(y, x)|x$\in$A, y$\in$A, 并且有xRy}

关系的乘积：称关系R•S为关系R和S的乘积或合成

关系的乘法的结论：

关系的乘法不满足交换律关系的乘法满足结合律

关系的幂

定理1.2.1 ：

$\mathrm{R}^{\mathrm{m}}\cdot \mathrm{R}^{\mathrm{n}}=\mathrm{R}^{\mathrm{m}+\mathrm{n}}$ $\left( \mathrm{R}^{\mathrm{m}} \right) ^{\mathrm{n}}=\mathrm{R}^{\mathrm{mn}}$

定理1.2.3：