离散数学之集合论
1.基本概念
定义：集合是包含不同对象的一个无序的聚集。集合元素在集合里面叫做A包含a，记作a E A（打不出来），否则记作a !E A。
集合的描述有：列举法：一一列举几个里面的元素，还有采用集合构造器，叙述法。
区间：有疑问请回顾高中知识。
集合相等：两个集合当且仅当它们拥有相同的元素。就是说：A与B是集合，则A与B相等的条件是当且仅当（AX）(XEA & XEB)，若A与B相等，则A=B
空集：一个集合不包含任何元素叫做空集。用{}表示
子集：集合A是集合B的子集并且B是A的超集（意思是B集合大一些），当且仅当A的元素是B的元素（B元素里面包括A元素）就表示A是B的子集。
推广：对于集合A，有 {} E A ，A E A
真子集：集合A是集合B的子集并且A != B。
要证明两个集合相等，就证明A是B的子集，B是A的子集。
幂集：集合A里面所有子集的集合幂集元素的个数：2^n个。
2.集合的运算
并集：A与B的并集，记作：A∪B，它同时包含集合A或者集合B里面的元素：A∪B={x|xEA | xEB}
交集：A与B的交集，记作：A∩B，他包含A与B里面的公共元素：A∩B = {x| xEA & xEB}
如果两个集合不相交，他们的交集是空集。
A∪B = A + B - A∩B
补集：有两种：绝对补与相对补。
相对补：也叫做差集，记作A - B(意思是A集合里面减去包含在B里面的A元素)，即：A-B = A - A∩B
A - B = {x| xEA & x !E B}
绝对补：全集是E，有一个集合是A，那么A的补集是：A。A = E-A
所以有性质：(A) = A ~E = 空集 ~空集 = E A∩~A = 空集 A∪~A = E
~(A ∩ B) = ~A ∪ ~B ~（A ∪ B）= ~A ∩ ~B
对称差：A与B对称差包括属于A的部分加上属于B的部分减去属于A与B的公共部分。
[email protected] = (A-B) ∪ (B-A) == A + B - A∩B
所以我们可以得到以下公式：[email protected][email protected] [email protected]=A [email protected]=K [email protected]=(A∩B)∪(B∩A) ([email protected])@[email protected]([email protected])
3.序偶与笛卡尔积
序偶：有序二元组的称呼，可以看作一个有顺序的集合，记作<A,B>
序偶不同于集合的是序偶是有顺序的，<A,B> != <B,A>，相当于键值对。
笛卡尔积：A与B是集合，那么A与B的笛卡尔积相当于A*B，表示<a,b>,其中：aEA ,bEB
即：A*B = {<a,b>| aEA & bEB}请注意：AB != BA
笛卡尔积不满足交换律与结合律：即AB != BA (AB)C != A(BC)
如果A, B, C是三个集合，则有：
A(B∩C) = (AB)∩(AC)
A(B∪C) = (AB)∪(AC)
(A∩B)C = (AC)∩(BC)
(A∪B)C = (AC)∪(BC)
性质：对于集合A, B, C, D如果满足AB 属于 CD ，其充要条件是 A属于C，B属于D。
4.关系
集合A与B的关系可以记作 AB里面的子集属于一个关系，也就是说，一个从A到B的二元关系就是AB的子集。
我们可以这么记：对于一个二元关系R，R里面的任意一个序偶<x,y>可以记作<x,y>ER 或者<x,y> !E R
要么是xRy 或者 x !R y
相关概念：
前域：在二元关系<x,y> E R里面，由所有x组成的集合叫做前域。
值域：在二元关系<x,y> E R里面，由所有y组成的集合叫做值域。
域：由前域与值域最初 相当于前域与值域的并集。
有集合A和B，直积AB的子集叫做A到B的关系。
恒等关系：Ix是X上面的二元关系，并且满足Ix={<x,x>|x EX}，叫做恒等关系。
关系矩阵：我们有两个有限集合：X = {x1,x2,x3,……,xm}，Y={y1,y2,y3,……,yn}，R是X到Y上的一个二元关系，那么就有相应的关系矩阵：M = [rij]m*n
其中Mij = 1，即<xi,yi> E R，0，即<xi,ji> !E R iE[1,m] jE[1,n]
我们还可以画有向图来表示关系：
5.关系的性质
自反的关系：R是集合X上面的二元关系，如果对于每一个x EX,有xRx，就称R是自反的。
对称关系：对于关系里面x,y E X，每当xRy，就有yRx，就X上面关系R是对称的。
传递关系：对于x, y, z E X，每当xRy, yRz时就有xRz,就称R在X上是传递的。
反自反关系：我们在自反的基础上面不能出现xRx的情况。
反对称关系：大概地说，集合 X 上的二元关系 R 是反对称的，当且仅当不存在X里的一对相异元素a, b，它们相互 R-关系于彼此
用数学符号可写成：
看了这么多，我们可以总结一下：
关系的性质
该有序偶不能没有
自反性：应该含有所有**<x, x>**
对称性：如果有**<x, y>就应该有<y, x>**
传递性：如果有**<x, y>和<y, z>就应该有<x, z>**
该有的序偶没有就不满足
不该有的序偶不能有
反自反性：不应该含有任何**<x, x>**
反对称性：如果有**<x, y>就不应该有<y, x>**
不该有的序偶有了就不满足
从关系矩阵、关系图来判断五个性质:
1、自反的:
关系矩阵的对角线上元素全为1,关系图中每个结点均有自回路。
2、对称的:
关系矩阵是对称矩阵，关系图中若两个结点之间有有向弧，则必成对出现
3、反自反的:
关系矩阵中对角线元素全为0,关系图中每个结点都没有自回路。
4、反对称的:
关系矩阵以对角线对称的元素不能同时为1，(但可为对称阵，同时为0)
关系图中如果两个结点之间有有向弧，则不能成对出现。
5、传递性:
不能明确判断，只能用定义。
6.复合关系与逆关系
1、
复合关系:为了明确地表示复合关系，给出定义:
定义:
R是X到Y的关系，S是Y到Z的关系，则R和S的复合关系R°S称为R和S的复合关系，表示为:
RoS= {<x,z>|x∈Xz∈Z@y)(y∈Y ^(x, y>∈R^<y,z> ES)}
如: R={<1,2>,❤️,4>,<2,2)}
S= {<4,2>,<2,5)>,❤️,1>,<1,3>}
则: RoS={(1,5),<(3,2>,(2,5)}
从左至右复合。
如: S’ =SU{<4,1>},
则:
RoS’ ={(1,5),❤️,2>,❤️,1)>,<2,5)}
实际上复合关系相当于一个个元素进行传递，看是否满足传递关系。
关系矩阵的复合：
其实有点像矩阵相乘方法。
其实，计算方法原理如下：
逆关系：
2、
逆关系:
R是X到y的二元关系，把R中每一序偶的元素次序颠倒，得到的关系称为R的逆关系，记作R c:
R^ ={<y,x><x,y>E R}。
如:“>”逆“<”，3>2, 2 ❤️,(3,2>∈>,<2,3>∈<
如: X= {xy,xX2,x}Y = {JV,V2,V;3}
R={<x,V2>,<x2,V3>,<xs,y>}
R° ={<V2,X>,< V;,X2 >,< Jy,X3>}
逆关系的性质：
7.关系的闭包运算
闭包相关定义：
我们可以这么总结：算自反闭包就是把对角线元素全部变成1，对称闭包：我们就是把它的逆关系找出来再加以合并，传递闭包，关系矩阵相乘再合并。
至于传递闭包，我们有以下方法：
所以有几个元素我们最多算几次就可以了。
我们引入了warshall算法进行计算：
我们通过一系列图进行看：
总结一下：warshall算法实际上就是我们看列有没有真值，有的话就是把相关行加到我们目前在列数的行上面。
8.等价关系与等价类
1、定义:若R为集合A上一个关系，满足R是自反的、对称的、传递的，则R称为等价关系。
同余模K的关系：
商集：
9.序关系
盖住关系：
我们总结以下盖住关系：
我们不能有相等的元素，也不能有可以传递出来的元素。
偏序集：
极大元极小元与最大元与最小元的关系：
