Ⅰ 离散数学 第二章 集合
一个 集合 是一些对象的整体
序列 和集合的不同之处是要考虑次序数字系统包括众所周知的十进制，二进制等等
关系 是序偶的集合
函数 是关系的一个特例
一个集合是一些对象的整体
可以用枚举法描述它:A={1,2,3,4}
也可以列出其元素的性质来描述:B={x│x是正偶数}
如果X是一个有限集合，令| X |=X中元素的个数，
没有元素的集合称为空集(或零集)用符号∅表示,∅={}，
两个集合X和Y有相同的元素,说两个集合相等，记为X=Y。
子集
设 X 和 Y 是集合。如果X的所有元素都是Y的元素，我们说X是Y的子集,写为X⊆Y。
真子集
如X是Y的子集但X不等于Y,则X是Y的一个真子集。记为：X⊊Y
空集是任何集合的子集。
集合X的所有子集的集合,称为X的幂集，用P(×)表示。
并集、交集、差集
并集XUY={x|x∈X or y ∈Y}
交集X∩Y= {x|x∈X and y∈ Y}
差集X-Y= {x|x∈X or x ∉ Y}
不相交 X∩Y=∅；
U：全集 X：子集
则U-X为X的补集
一个由集合X的非空子集的整体组成的S，如X的每个元素都只属于S的某一个元素，S就称为X的一个划分。
笛卡尔积
—个由两个元素组成的有序对(或序偶)，写为(a,b)
(a,b)=(c,d)当且仅当a=c,b=d. X,Y集合，X×Y称为X和Y的笛卡儿积
一个序列(或有序组)是一个表,要计及其元素出现的次序。
如果s是一个序列，一般的，s.表示序列的第n项。我们把n称为序列的下标。
序列3,5,5,7,8,8,13是增序列。对于所有的n, S n >S n+1 ,则称S n 为增序列。
对于n=m,m+1,..,令{S n }是一个序列，且令n1，n2,...是一个增序列，值在{m,m+1,..}中,满足n k <n k+1 ，称序列{S nk }是{S n }的一个子序列
X 集合
X* X上所有串的集合
α串,| α |串的长度。
如果α和β是两个串，由α后面跟着β所组成的串α β ,称为α和β的连接。
①比特bit ②二进制系统,16进制系统,8进制系统 ③系统的基数
这个就不多阐述了，计组中已经学过了！
关系可以想成一张表，其中列出了一些元素和其他元素之间的关系。
X到Y的关系R,是笛卡儿积X*Y的一个子集。如果(x, y)∈R，我们写为xRy且说x和y有关。当X=Y，我们称R是X上的(二元)关系。
定义 ：
令S是集合X的一个划分。 定义xRy:
对于S的某些集合干,x和y都属于T。则R是自反，对称和传递的。
X上的一个自反的，对称的和传递的关系称为X上的一个等价关系。
令R是集合×上的一个等价关系。对于每个a∈X，
令[a]={x∈X]xRa};则s={[a]la∈X}是X的一个划分。
令R是集合x上的一个等价关系集合[a]，称为由关系R确定的x的等价类。
令R表示一个有限集合x上的等价关系。如每个等价类有r个元素,则共有|X|/r个等价类。
一个表示从X到Y的关系的方法是使用矩阵。如果xRy，则×行y列的元素之值为1,否则，其值为0。这即是关系矩阵。
定理
R₁的关系(X到Y)矩阵A₁，R₂的关系(到Z)矩阵A₂。
R₁○R₂的关系矩阵:
在矩阵的积A₁A₂中，把非0项用1代替而得的矩阵。
函数是特殊的关系。
R的定义域=
{x∈X│|存在y ∈ Y,(×,y) ∈R}f 关系，f函数，f的定义域=X，且.(x,y')在f 中，y=y'。
Ⅱ 离散数学中fg(x)等不等于gf(x)
不同的教材关于合成函数f•g记法中的次序与关系可能不一样（可能刚好相反）为了迎合函数习惯，近自变元的函数先发生作用，作如下定义：
设f:X→Y和g:Y→Z是函数, 它们组成一个合成函数h=f•g: X→Z。即h= f•g={(x,z)| x∈X, z∈Z 且至少存在一个y∈Y，使y=f(x),z=g(y)}，那么对一切x∈X, (f•g)(x)=g(f(x)).
Ⅲ 简单的离散数学问题
1. S上的有序对有<1,1>,<1,2>，<2,1>,<2,2> 4个
偏序关系需要满足自反，反对称，传递
即<1,1>,<2,2>都属于偏序集，<1,2>,<2,1>不能同时属于偏序集
所以一共有2^2-1=3个偏序关系
因为S上有序对有4个，所以二元关系有2^4=16个
2 4个元素集合的满射，即是4个元素集合的双射个数
显然双射有4！=24个
3 x中有3个元素，设等价关系为R
等价关系是自反，对称，传递
所以对任意的a∈X,<a,a>都属于这个等价关系R
对称需要满足对于任意的a,b ,若<a,b>属于R,则<b,a>属于R
传递需要满足对于任意的a,b,c 若<a,b>,<b,c>属于R, 则<a,c>属于R
只需要计算R中出现不同的a,b <a,b>∈R一共有几种可能
1）一个<a,b>属于R都没有，这样的等价关系只有一种为恒等关系Ix
2)有一个<a,b>属于R，则根据对称<b，a>也属于R
这样的<a,b>一共有C(3,2)=3个
3）有2个不同的有序对<a,b><a,c>,因为对称和传递性可知，<b,a>,<c,a><b,c><c,b>都属于R,这样的等价关系也只有一种，即X上的全关系Ex
所以一共有5种