集合论
一、基本概念
集合(set)：做为整体识别的、确定的、互相区别的一些对象的总体。 规定集合的三种方式：列举法、描述法、归纳法
集合论的三大基本原理
外延公理：两个集合A和B相等当且仅当它们具有相同的元素（无序性） 概括公理：对于任意个体域U，任一谓词公式P都确定一个以该域中的对象为元素的集合S（确定性）
正规公理：不存在集合A1,A2,A3,…使得…∈A3∈A2∈A1（有限可分，集合不能是自己的元素）
注意：隶属、包含的判断（有时两者兼有）
定理1：对于任意集合A和B，A=B当且仅当A ? B且B ? A ?传递性，对全集、空集的?关系等 定理5：空集是唯一的
子集、真子集、子集个数等
运算：并、交、补、差、幂集，及一些运算性质、公式
幂集：对任意集合A，ρ(A)称作A的幂集，定义为：ρ(A)={x|x?A}，所有子集的集合 设A,B为任意集合， A?B当且仅当ρ(A) ?ρ(B)
集合族：如果集合C中的每个元素都是集合，称C为集合族
集合族的标志集：如果集合族C可以表示为某种下标的形，C={Sd|d∈D}，那么这些下标组成的集合称作集合族C的标志集
广义并、广义交，及相关运算性质、公式
归纳定义：
基础条款：规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定
归纳条款：规定由已确定的集合元素去进一步确定其它元素的规则 终极条款：规定待定义集合只含有基础条款和归纳条款所确定的成员
基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生集合中所有成员 终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象
例：自然数的归纳定义、数学归纳法等……（建议看一下课件例子了解一下思路）
二、关系
有序组（二元）：设a,b为任意对象，称集合族{{a},{a,b}}为二元有序组，简记为 称a为的第一分量，b为第二分量 递归定义：n=2时，={{a1},{a1,a2}}
n>2时，=<< a1,…,an-1>, an>
集合的笛卡儿积：对任意集合A,A2,…,A，A1×A2称作集合A1，A2的笛卡儿积，定义如下：A1×A2 = {
A1×A2×… ×An =(A1×A2×… ×An-1) ×An
定理：对于任意有限集合A1,…,An，有|A1×…×An|=|A1|*…*|An|
一些运算性质
关系是各个对象之间的联系和对应
R称为集合A1,A2,…,An-1到An的n元关系，如果R是A1×A2×…×An的一个子集。当A1=A2=…=An-1=An时，也称R为A上的n元关系 几个特殊二元关系：空关系、全关系、相等关系 定义：设R为A到B的二元关系(R?A×B)
xRy表示
定义域domain：Dom(R)={x|x∈A∧?y(
注意：前域与定义域，陪域与值域的差别。尤其是定义域与前域，与函数的差别
关系表示法：
集合表示法
关系图表示法（有向箭头，主要是前域陪域相同的关系图） 关系矩阵（mij=1当且仅当aiRbj；mij=0当且仅当?aiRbj） 关系相等：相同前域陪域，且?x?y(xRy?xSy)
运算：要有相同前域、陪域。但总可以对关系的前域和陪域做适当的扩充，使之满足条件
并（矩阵分量析取） 交（矩阵分量合取）
差（前一个关系和后一个关系的补矩阵做合取） 补（矩阵做否定） 逆运算：R~={
合成：R?A×B，S?B×C，R和S的合成关系R?S定义为：
R?S={
幂运算：定义为自身的n次合成Rn=R?…?R（n个R合成），R0=EA
幂关系有限定理：设集合A的基数为n，R是A上的二元关系，则存在自然数i,j使得0 ≤i＜j≤2n2，有Ri=Rj（鸽笼原理，A×A有n2个元素，子集个数为2n^2个）
自反关系：（就是每个元素都和自己有关系）
?x(x∈A→xRx)
关系图：每个节点都有环 关系矩阵：对角线全为1 反自反关系：（每个元素都和自己没关系）
?x(x∈A→ ?xRx)
关系图：每个节点都没有环 关系矩阵：对角线全为0 对称关系：（每对关系都是相互的）
?x?y(x,y∈A∧xRy→yRx)
关系图：两个节点之间有边的就有反向边 关系矩阵：对称矩阵 反对称关系：（若有相互关系则只能是同一个元素，不同元素间不能有相互关系）
?x?y(x,y∈A∧xRy∧yRx→x=y)
关系图：两个节点之间只能有一条单向边 关系矩阵：ci,j=1(i≠j)时cj,i=0 传递关系：
?x?y?z(x,y,z∈A∧xRy∧yRz→xRz)
关系图：如果有边v1v2,…,vn-1vn，则有边v1vn
注意：A上的空关系?是反自反的，不是自反的（此外是对称的、反对称的、传递的）
如果A=?，那么A上的空关系就是自反的，同时也是反自反的，因为注意定义谓词的前件x∈A始终为假
A上的相等关系EA既是对称的，又是反对称的 即对于特殊集合、关系的判断要从定义式出发，注意前件的真假 R自反当且仅当EA?R
R反自反当且仅当EA∩R?? R对称当且仅当R?R~
R反对称当且仅当R∩R~?EA R传递当且仅当R2?R
运算的封闭性：如果关系R的某个性质经过关系运算后仍然保持，则称该性质对这个运算封闭（以上5个特性对交和求逆运算都封闭，自反对合成封闭）
等价关系：等价关系R为A上的自反、对称、传递的二元关系
等价类：设R为A上的等价关系，对于每个a∈A，a的等价类记做[a]R(简记[a])，定义为：[a]R={x|x∈A ∧xRa}，a称作[a]R的代表元素 划分：满足下列条件的集合A的子集族π
?B(B∈π → B≠?) （划分单元里没有空集） ∪π=A （所有划分单元合起来是全集）
?B ?B’(B∈π∧B’∈π∧B≠B’ → B ∩B’=?) （划分单元两两不相交） π中的元素称为划分的单元 特别约定A=?时只有划分?
A上的等价关系R的所有等价类的集合，构成A的一个划分，称作等价关系R对应的划分 反过来，集合A的一个划分π，也对应A上的一个等价关系R，称作划分π对应的等价关系
等价关系和划分的一一对应
划分的“粗细”概念：如果π1的每一个单元都包含于π2的某个单元，称π1细于π2，表示为π1≤π2；如果π1≤π2而且π1≠π2 ，则表示为π1＜π2，称作“真细于” 定理：π1，π2分别是等价关系R1，R2对应的划分，那么R1?R2 ? π1≤π2
定理说明，越“小”（包含二元组较少）的等价关系对应越细的划分；最小的等价关系是相等关系EA；最大的等价关系是全关系 划分的运算：（结合图来很好理解）
积划分运算：划分π1和π2的积划分π1?π2是满足如下条件的划分：π1?π2细于π1和π2；如果某个划分π细于π1和π2，则π一定细于π1?π2；也就是说， π1?π2是细于π1和π2的最粗划分（”最小公倍数”）
积划分对应于等价关系交运算
和划分运算：划分π1和π2的和划分π1+π2是满足如下条件的划分：π1和π2均细于π1+π2；如果有划分π， π1和π2均细于π，则π1+π2细于π。也就是说， π1+
π2是粗于π1和π2的最细划分（“最大公约数”）
和划分不对应于等价关系的并运算，而是对应于等价关系并运算结果的传递闭包
二元关系R的传递闭包t(R)：t(R) 是传递的，R?t(R)，对于A上的任意一个具有传递性质且包含R的关系R’，t(R)?R’
商集：R是A上的等价关系，称A的划分{[a]R|a∈A}为A的R商集，记做A/R
A/(R1∩R2 )=A/R1?A/R2 A/t(R1∪R2)=A/R1+A/R2
序关系：R为集合A上的自反、反对称、传递的二元关系 存在序关系R的集合A称作有序集（ordered set），用二元有序组表示，一般的有序集表示成
哈斯图：对序关系关系图的一种简化画法
由于序关系自反，各结点都有环，省去； 由于序关系反对称且传递，所以关系图中任何两个不同的结点直接不会有双向的边或通路，所以省去边的箭头，把向上的方向定为箭头方向
由于序关系传递，所以省去所有推定的边，即a≤b,b≤c有a≤c，省去ac边 元素排序：a≤b，称a先于或等于b；a小于或等于b；如果?(a≤b)，则称a,b不可比较或者不可排序
最大（小）元、极大（小）元（必须是B中元素）：为有序集，B?A B的最小元b：b∈B∧?x(x∈B→b≤x) （必须比每个B的元素都小于或等于） B的最大元b：b∈B∧?x(x∈B→x≤b) （必须每个B的元素都比它小于或等于） B的极小元b：b∈B∧??x(x∈B∧x≠b∧x≤b) （比B中每个可比元都小于或等于） B的极大元b：b∈B∧??x(x∈B∧x≠b∧b≤x) （B中每个可比元都比它小于或等于） 极大和最大的差别在于B中是否包含不可比较的元素
最大（小）元必为极大（小）元；最大（小）元若有则唯一；极大（小）元恒存在未必唯一 上（下）界，上（下）确界（只要是A中元素）：为有序集，B?A B的上界a：a∈A∧?x(x∈B→x≤a) （必须每个B的元素都比它小于或等于） B的下界a：a∈A∧?x(x∈B→a≤x) （必须比每个B的元素都小于或等于） B的上确界a：a是B的所有上界的集合最小元 B的下确界a：a是B的所有下界的集合最大元
最大（小）元是上（下）确界；属于B的上（下）界为最大（小）元；都未必存在 链、反链
半序关系：R为集合A上的反自反、反对称、传递的二元关系（即序关系除去每个元素与自己的关系）
三、函数
定义：如果X到Y的二元关系f?X×Y，对于每个x∈X，都有唯一的y∈Y，使得
前域和定义域重合；单值性：
y=f(x)，称x为自变元，y为函数在x处的值，y为x的像点，x为y的源点（基于映射） X≠?时，空关系?不是函数，当X＝?时，空关系?是函数，称作空函数 函数的规定方法：列表法、图标法、解析法、递归定义 函数相等与包含
函数个数：如果|X|=m，|Y|=n，则{f|f:X→Y}的基数为nm，共有nm个X到Y的函数。X到
Y的全体函数集合表示为YX
定义域子集的映象：f’(A)={y|?x(x∈A∧y=f(x))}（即定义域的一个子集A的值域） 函数合成（恩，不写了。。。）
单射：如果任意x1≠x2有f(x1)≠f(x2)。如果f和g都是单射函数，则其合成g?f也是单射函数。如果g?f是单射函数，则f是单射函数
满射：如果任意y都有x使得y=f(x)，即Ran(f)=Y。如果f和g都是满射函数，则其合成g?f也是满射函数。如果g?f是满射函数，则g是满射函数
双射函数：如果f既是单射函数又是满射函数，称作双射函数。如果f和g都是双射函数，则其合成g?f也是双射函数。如果g?f是双射函数，则f是单射函数，g是满射函数 逆函数：只有双射函数存在逆函数
左逆函数：如果g ?f=EX，则称g为f的左逆函数 右逆函数：如果f ?g=EY，则称g为f的右逆函数
f可逆当且仅当f既有左逆函数，又有右逆函数，而且左逆函数和右逆函数相等
图论
图：由结点和联结结点的边所构成的离散结构G=
有重边的为重图，否则为单图 简单图：无环无重边的无向图
完全图：任意两个不同结点间都有边，Kn 孤立结点、零图（只有孤立结点）
赋权图：G=
度的总和为偶数，边数目的两倍；有向图出度等于入度 悬挂点：一度的顶点 正则图：所有顶点的度均相同的图称为正则图，按照顶点的度数k称作k-正则图，Kn是n-1正则图
子图、真子图：边集结点集都必须为子集 生成子图：结点集相同的子图
补图：结点集相同，边集交集为空，并集为完全图
图的同构：可以将V1中所有的结点一一对应地置换为V2中的结点名后得到的图等于G2 （同分异构体）
拟路径：v1,e1,v2,e2,v3,…,vl-1,el-1,vl，其中ei=
路径：拟路径中的边各不相同 闭路径：v1=vl的路径