一、集合的概念 集合由指定范围内的某些特定对象聚集在一起构成。指定范围内的每一个对象称为这个集合的元素. 二、集合的记法 通常用带(不带)标号的大写字母A、B、C、…、A1、 B1 、C1 、…、X、Y、Z、…表示集合； 通常用带（不带）标号的小写字母a、b、c、…、a1、 b1 、c1 、…、x、y、z、…表示元素。

三、集合的表示方法 集合是由它包含的元素完全确定的，为了表示一个集合，通常有： 枚举法: 如：A＝{a，b，c，d} 描述法： 如：Z = {x|x是一个整数}； 归纳法： 如：P={xi|xi=xi-1+2, i是1到100的整数，x0=2} 文氏图 四、 集合与元素的关系 五、集合的特征 1、互异性：集合中的元素都是不同的，凡是相同的元素，均视为同一个元素； {1,1,2}={1,2} 2、无序性：集合中的元素是没有顺序的。 {2,1}={1,2} 3、确定性 ： 任何一个对象，或者是这个集合的元素，或者不是，二者必居其一； 4、多样性：集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征。 例如：A={a,{a},{{a},b},{{a}}, 1}； 六、集合与集合的关系 相等,包含,真包含 相等: 包含: 4、空集: 6 有限集和无限集:集合A中元素的个数称为集合A的基数，记为|A|。 如|A|是有限的，则称集合A为有限集， 如|A|是无限的，则称集合A为无限集。 7 m元子集:如果一个集合A含有n个元素，则称集合A为n元集，称A的含有m个(0≤m≤n)元素的子集为A的m元子集 子集总数: 8 幂集 设A为任意集合，把A的所有不同子集构成的集合叫做A的幂集，记为ρ(A)或2^A 。

证明集合包含的方法： 任取x属于A, 能够推出x属于B,则可得A包含于B 证明集合相等的方法： a)证明A包含于B且B包含于A b)利用已有的等价公式证明

1.定义　 由两个元素x,y按照一定的次序组成的二元组称为有序偶对(序偶),记作,其中x为第一个元素，y为第二个元素。 2.序偶的特点 1)序偶可以看作是具有两个元素的集合， 2)但是序偶中的两个元素具有确定的次序。即≠,但是{a,b}={b,a}. 3)给定序偶和，如果a=c，b=d，则=。 3. 有序N元组：是个有序对，其中第一个元素是一个有序n-1元组。 例：有序三元组=≠ 二、笛卡尔乘积 1 定义 设A，B是两个集合，称集合：A×B＝{|(x∈A)∧(y∈B)}为集合A与B的笛卡尔积。 注意： （1）集合A与B的笛卡尔积A×B仍然是集合； （2）集合A×B中的元素是序偶，序偶中的第一个元素取自A，第二个元素取自B。 2 性质 （1）笛卡尔积不满足交换律； （2）A×B=Φ当且仅当A=Φ或者B=Φ； （3）笛卡尔积不满足结合律； （4）对有限集A,B，有|A×B|=|B×A|=|A|×|B|。 （5）设A,B,C是任意三个集合，则 A×(B∪C)=(A×B)∪(A×C)； (B∪C)×A=(B×A)∪(C×A)； A×(B∩C)=(A×B)∩(A×C)； (B∩C)×A=(B×A)∩(C×A)。 6）设A，B，C，D是集合，若AC且BD，则AB  CD。

1.定义 设A,B为两个非空集合，称A×B的任何子集R为从A到B的二元关系，简称关系。 如果 A＝B，则称R为A上的二元关系。

2 关系的表示法 （1）集合表示法 例:a)设A={a},B={b,c}，写出从A到B的不同关系； b)写出定义在实数集合R上的“相等”关系。 解:a) A到B的不同关系有：R1=Ф,R2={},R3={},R4={,}； b）设实数集合R上的“相等”关系为S，则S={|(x,y∈R)∧(x=y)}。 （2）关系图法 a）A≠B 设A＝{a1,a2,…,an},B＝{b1,b2,…,bm}，R是 从A到B的一个二元关系，则规定R的关系图如下： 　①.设a1,a2,…,an和b1,b2,…,bm分别为图中的结点，用“。”表示；　 　②.如属于R,则从ai到bj可用有向边ai。 。bj相连。为对应图中的有向边。 　b)A=B 设A＝B=，R是A上的关系，则R的关系图规定如下： ①.设a1,a2,…,an为图中节点，用“。”表示 ②.如属于R,则从ai到aj可用有向边ai。 。aj相连。为对应图中的有向边。 ③.如属于R,则从ai到ai用一带箭头的小圆环表示，即：ai (3).关系矩阵 设A＝{a1,a2,…,an},B＝{b1,b2,…,bm},R是从A到B的一个二元关系，称矩阵MR＝（rij)n×m为关系R的关系矩阵，其中: 若属于R，则rij=1；若属于R，则rij=0又称MR为R的邻接矩阵。 注意：A中元素序号对应矩阵元素的行下标， B中元素序号对应矩阵元素的列下标；关系矩阵是0-1矩阵，称为布尔矩阵。 3.前域和值域 令R为二元关系,由∈R的所有x组成的集合domR称为R的前域，即 domR={x|(存在y)(∈R)} 使∈R的所有y组成的集合ranR称作R的值域，即 ranR={y|(存在x)(∈R)} R的前域和值域一起称作R的域，记作 FLDR，即 FLDR =domR∪ranR 4.三种特殊关系 规定：把X×Y的两个平凡子集X×Y和Φ，分别称为X到Y上的全域关系和空关系。 当X=Y时，集合X上： 全域关系： EX=X×X 空关系： ΦX=Φ 恒等关系： IX={|x属于X}

本节涉及到的关系，如无特别声明，都是假定其前域和值域相同。即都为定义在集合A上的关系，且A是非空集合。对于前域、值域不相同的关系，其性质无法加以定义。 结论：（1）关系R是自反的，则R一定不是反自反的；关系R是反自反的，则R一定不是自反的； （2）存在既不是自反的也不是反自反的关系； （3）关系R是自反的等价于关系图中每个结点都有自环，关系R是反自反的等价于关系图中每个结点都无自环； （4）关系R是自反的等价于关系矩阵的主对角线上全为1，关系R是反自反的等价于关系矩阵的主对角线上全为0。

一、复合运算

二.关系图求闭包 利用关系图求关系R闭包的方法： （1）检查R的关系图，在没有自环的结点处加上自环，可得r®的关系图； （2）检查R的关系图，将每条单向边全部改成双向边，可得s®的关系图； （3）检查R的关系图，从每个结点出发，找到长度不超过n（n为图中结点的个数）的路径的终点，如果该结点到其终点没有边相连，就加上此边，可得t®的关系图。 利用关系图求关系R闭包的方法： （1）检查R的关系图，在没有自环的结点处加上自环，可得r®的关系图； （2）检查R的关系图，将每条单向边全部改成双向边，可得s®的关系图； （3）检查R的关系图，从每个结点出发，找到长度不超过n（n为图中结点的个数）的路径的终点，如果该结点到其终点没有边相连，就加上此边，可得t®的关系图。 根据R的关系矩阵求r®的关系矩阵：把R的关系矩阵主对角线都标为1 根据R的关系矩阵求s®的关系矩阵：把R的关系矩阵和R-1的关系矩阵或运算

一、等价关系定义 设R是定义在非空集合A上的关系，如果R是自反的、对称的、传递的，则称R为A上的等价关系。 二、等价类 如果R是一个等价关系，∈R，则称a等价于b，记作a~b。 设R是非空集合A上的等价关系，对任意a∈A，称集合 [a]R＝{x|x∈A∧∈R} 称[a]R 为a关于R的等价类, 简称为a的等价类 二、等价类 设R是非空集合A上的等价关系，对任意a∈A，称集合 [a]R＝{x|x∈A∧∈R} 称[a]R 为a关于R的等价类, 简称为a的等价类 三、商 集设R是非空集合A上的等价关系，由R确定的一切等价类的集合，称为集合A上关于R的商集，记为A/R，即A/R＝{[x]R|x∈A} 四、等价关系与划分

定义： 设R是给定集合X上的一个二元关系，若R是自反的和对称的，则称R是相容的，即R是相容关系。 对相容关系而言，在它的图形表示中，每个元素的环不必画出，两个元素之间的相反方向弧也不必画出，可代之以一条无向弧，这样得到的图称为相容关系图。 在相容关系的关系矩阵中，只需写出该关系矩阵对角线下方的部分就够了，称为相容关系矩阵 最大相容类：定义： 设X是一个集合， R是X上的相容关系，如果AX，若对于A中任意两个元素a1，a2有a1Ra2，称A是由相容关系R产生的相容类。不能真包含在其它相容类中的相容类称为最大相容类。 完全覆盖：最大相容类组成的集合 求最大相容类的方法： 在关系图中确定最大完全多边形的顶点 每个顶点都与其他所有顶点相联结的多边形 1）孤立结点是最大的完全多边形； 2）两个相互联结的结点是最大完全多边形； 3) 三角形是三个结点的最大完全多边形； 求最大相容类的方法： 在关系图中确定最大完全多边形的顶点 （4）四个结点 （5）五个结点 画出简化相容关系的关系图后， 先找结点最多的完全多边形，以后逐次减少。

哈斯图的特点：（1）每个结点没有环。 （2）两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前。 （3）具有盖住关系的两个结点之间连边。 哈斯图: 利用偏序关系的自反、反对称、传递性进行简化的关系图。 性质： (1) 对于有穷集，极小元和极大元一定存在，可能存在多个. (2) 最小元和最大元不一定存在，如果存在一定惟一. (3) 最小元一定是极小元；最大元一定是极大元. (4) 孤立结点既是极小元，也是极大元.