笔记离散数学

离散数学复习笔记数理逻辑逻辑：以研究人的思维形式及思维规律为目的的一门学科数理逻辑：利用数学符号来协助推理的一门形式逻辑学命题：能表达判断并具有确定真值的陈述句真值：每个命题都具有的一个值，要么为真，要么为假，不能随着环境变化原子命题：不能再分解的命题复合命题：由原子命题符号及联结词组成的有意义的命题表达式否定非P合取P而且Q 析取P可兼或Q排斥析取P不可兼或Q单条件若P则Q双条件P当且仅当Q命题公式：满足特定条件的合法的命题表达式分量：命题公式中的原子命题翻译：将自然语言转化为数理逻辑语言真值表：对一个命题公式而言，将对于其分量的各种可能的真值指派汇聚成的表A,B,A\BP1\P2..A，BAB等价定律：交换律，结合律，分配律，摩根律，否定律，同一律重言式：永真式，无论对命题变元作何种真值指派，它都等价于T的命题公式F用一个命题公式代替重言式中同一个分量，依然为重言式蕴含式：若A->B永真则称A蕴含B，记做A=>B原命题等价于它的逆否命题三个性质：传递性，A=>BA=>CA=>(B^C)，A=>BC=>BAvC=>B有效结论：H1，H2、、、、Hn，C为一组命题公式，若H1^H2^...^Hn=>C,称C是一组条件下的有效结论三种方法：真值表法，直接证法，间接证法其他连接词：条件否定，与非，或非规范命题表达式：只含非且或A1^A2^...^An，A1，A2...An否定组成的析取式A1vA2v...vAn，A1，A2...An否定组成的合取式一个命题公式的合取范氏或析取范氏并不是唯一的n时存在，但两者必须出现且仅出现一次P^QP^Q一般n个命题变元共有2^n个小项n时存在，但两者必须出现且仅出现一次PvQPvQ组成，则称该等价式为原式的主析取范式组成，则称该等价式为原式的主合取范式集合论集合：满足一定特征的对象的全体扩张原则：两个集合相等，当且仅当他们有相同的元素UP，A，AUP集合表示：列举法，特征法幂集：对给定的集合A，称以A的全体子集为元素的集合为A的幂集集合的基数：|A|元素的个数无限集合：元素个数能与某个真子集一一对应的集合序偶：有序的二元数组<x,y>A*B={<x,y>|xAyB}xRy，x，y，关系域是前域和值域的并集。两集合ABAA=BA关系表示：集合表示法，关系矩阵法，关系图表示法关系性质：自反关系（xX，<x,x>R），反自反关系（xX，<x,xR）【存在既不反自反也不自反的关系】x，yX，且<x,y>R，则<y,x>R，xX，yX，<x,y>R，则在既不对称又不反对称的关系】传递性x,y,z属于X，且<x,y><y,z>都属于R，则<x,z>属于R复合关系:<x,y>属于R,<y,z>属于S，则<x,z>属于R复合S逆关系:{<y,x>|<x,y>属于R,x属于X,y属于Y}闭包运算：通过往已知关系中添加序偶让它达到某种要求的运算，叫闭包运算S={s1,s2...smSiA，且SA，则SASAA交叉划分是原两划分的加细等价关系：同时具备自反，对称和传递三个性质的关系即等价关系A，<x,a>R，为元素aRRAAA关于R的商集，为A/R定理：ARAAAAR1，R2，则成立A/R1=A/R2A相容关系：给定集合Ar，若rrrA在相容关系图中，最大完全多边形的顶点集合，就是最大相容类定理：设rACr，CCrAACr(A)偏序关系：AR，R序关系链与反链：一个元素构成的子集，既是链，又是反链Ax,yA，x*yy*xAB必然唯一A，BA，BA良序集一定是全序集，有限元素的全序集一定是良序集函数性质：入射（单射）x1x2yY，xX，yx双射：既是入射又是满射的函数逆函数：若fx->y的双射,则逆函数是y->x的双射g*f<x,yf<y,z>ggfg*fgfg*fgfg*f是入射，都是双射，g*f是双射图论图的定义：平面上由一些点和连接两点之间的连线构成的图形有向图-每条边都有方向的图，无向图-每条边都没有方向的图，混合图-既有有向边又有无向边的图点边关联，点点（边边）邻接（相邻）结点v-v（时，规定按两次计），x2空图：没有边的图，平凡图：一个点的空图，有向图的出入度，奇偶点：度为奇偶数的点图的基本定理1、无向图的度为边数的两倍2Gn有向完全图：完全图每条边上任意添加一个方向同构：两个图若存在一个映射，点到点，边和边也映射，则两个图同构必要条件：结点数目相同，边数相等，度数相同的结点数目相等，与同度点相邻的点的度数应对应相同补图：两个图点和边相互补充子图：点和边都属于另一个图的子集，真子图：点或边不全包含路与回路路的长度：路经过的边的次数，路，迹，通路，回路，闭迹，圈lGn-1路VG点和边N-1欧拉图1、欧拉回路：经过G中每条边一次且仅一次的回路2、欧拉图：含有欧拉回路的图3、欧拉图充要条件：G无孤立点，那么G是欧拉图【G连通且无奇点】汉密尔顿图1、汉密尔顿圈：经过图G中每个点一次且仅一次的圈2、汉密尔顿图：含有汉密尔顿圈的图，至今无充分必要条件3、闭包：简单图G是汉密尔顿图等价于它的闭包是也是汉密尔顿图树1、树：连通的无圈回路的无向图2、森林：无圈图3、生成树：作为图G的支撑子图的一棵树，任一连通图都至少有一棵生成树4、带权图：每条边上都带有一个给定权值的图、最小生成树：边权和最小的生成树，不唯一6、有向树：在不考虑边上方向时为一棵树的有向图7、根树：一棵恰有一个结点的入度为0，其余结点的入度为1的有向树8、有序树：结点间拥有顺序的根树，任意一棵有序树都可以改写成一棵对应的二叉树9、m叉树，完全m叉树：同二叉树10路长度11、带权二叉树：每片树叶i都带权值wi的二叉树12、最优二叉树必是完全二叉树代数系统代数系统1、n：A，B，A^n->BAn2AAA3、幺元：e*a=aea*e=aA则必存在幺元4、零元：q*a=qa*q=q左右零元同时存在左零元和右零元，则存在零元5、逆元：a*b=eba，b*a=ebaa*b=b*a=eba逆元半群1、广群：代数系统<A,*>称为广群，若*在A上满足封闭性2、半群：<S,*>为半群，若满足封闭性和可结合性3、子半群：<S,*>是半群，<B,*>是半群，B属于S，称<B,*>是<S,*>的子半群4<s,*>表中任何两行或任何两列都是不相同的，设<S,*Sab，aba*b群与子群1<G,*>G*GG群2G<G,*>G<G,*>是一个无限群3、子群：<G,*>是一个群，BG，<B,*>也作成一个群，称<B，*><G,*>的子群4、群的性质：每个元素的逆元唯一若|G|>1，G群中满足消去律子群与原群具有相同的幺元5、非空子集成为子群的两个充分条件-设群<G,*>,BGBB<B,*>必为<G,*>的子群-设<G,*>GSa*b逆属于S，那么<S,*>必为<G,*>的子群阿贝尔群1、定义：<G,*>是一个群，如果群中的运算*还满足交换律，即对任何两个元素x,y属于G，都有x*y=y*x,则称为一个阿贝尔群2、定理：<G,*>(a*b)*(a*b)=(a*a)*(b*b)循环群1Ga，使得Ga<G,*>a2、性质：任何循环群必为阿贝尔群，一般说来，阿贝尔群未必是循环群3、群的元素的阶：设<G,*>是一个群，aGa^r=erm，a^m=ear北航离散复习笔记第二章谓词逻辑1、项：用于表达个体的符号串，相当于汉语中的名词2、公式：用于表达命题的符号串，相当于汉语中的句子3、使用符号：个体变元【变元】，个体常元【常元】，函数符号，谓词符号，量词符号，联结词符号，圆括号和逗号4BABA式是它自己5、不出现变元的项称为基项，也称为闭项，没有自由变元的公式称为语句，也称为闭公式。没有约束变元的公式称为开公式6、论域也称为个体域7、永真式：A在每个解释中为真，永假式类似(矛盾式，不可满足式)8A到的谓词逻辑公式。命题逻辑永真式的替换实例称为重言式9式未必是永真式1、定义：指从事先给定的公里出发，根据推理规则推导出一系列定理，由此而形成的演绎系统2、组成：符号集，公式集，公理集，推理规则集，定理集3、性质：可靠性【只要公设都真，每个定理就真】，完备性【公设集的每个逻辑推论都是公理系统的定理】，协调性，独立性第四章归结法原理1、文字的有穷集合称为子句，不包含任何文字的子句称为空子句2vSvS，S，SS3、如果一个文字恰为另一个文字的否定，则称它们为相反的文字是反的文字，C1，C2是子句，称C11-{L1}U C2-{L2}为C1和C2的归结子句4CC1，C2CC1，C25、子句集S是不可满足的当且仅当存在S的反驳6Q1v1...QvnB,Q1v1...QnvnB的母式7、不出现存在量词存在的前束范式称为无存在前束范式8BAAB9、不出现变元的文字称为基文字，基文字的有穷集合称为基子句10、如果解释ISIS，S，SS第五章集合的基本概念和运算1、集合：人们直观上或思想上能够明确区分的一些对象所构成的一个整体，通过枚举法和抽象法展示2、基数：有穷集A的元素个数称为A的基数3、如果集合A中的每个元素都是集合，则称A为集合的聚合，或者集合族4、集合归纳定义的三个组成部分：基础语句【直接规定某些对象是该集合的元素】，归纳语句【规定由已知元素得到新元素的办法】，权限语句【限定集合的范围，保证定义集合的唯一性】5、字母表：符号的有穷非空集合称为字母表，也称为符号集6xyx,y序偶的第一元，第二元7AB构成有序偶1、关系：任何有序偶的集合称为二元关系，简称关系2R3、值域：关系R中所有有序偶的第二元组成的集合4XY，m*n5、R：R1，R自环【对应反自反】6R（或者两条相反方向的弧）【对应反对称】7Rxy1x到y的有向边8xyyzxzR,S9R阵转置，关系图中每条有向边反向10、闭包：RRBAB反、对称、传递的，AB，XCABC11、若RPR偏序12RPR偏序13xyyx14、<A,≤>是偏序集，BA，bB，xB，x<=b,bBb<=x】，b<xbBx<b】15、<A,≤>是偏序集，BA，bA，xB，x<=b,bBb<=x】，BBBB16、良序集：<P,<=>偏序,P<P,<=>17ASUA=S，AS18、ASAB,C，BCAS的元素为划分块，AA，S在一个块中，任何两不同块都没有公共元素】19、等价关系：R是非空集合X上自反的、对称的、传递的关系20等，或者不相交。所有等价类的并集是集合X，等价类的聚合确定了集合X个划分21、商集：RXXR22、每个等价关系确定一个划分，每个划分确定一个等价关系第七章函数1、设fXYxXyf，fXYXY2、fXYAX，AYfA3xyY，使得<x,y>f，fXY数4、满射：对于每个y属于Y，都存在x属于X，使得f(x)=y，称f为满射5x不等f(y)6、双射：既是单射，也是满射7、fXYgYZ，fg射；双射->双射】8、常值函数：设函数f:X->YxX，存在某一个yY，f(x)=yf9、设f：X->Y是双射函数，则其逆关系是双射函数Y->X10、双射集合构成群：封闭性；结合律；有单位元；有逆元第八章自然数1、集合A是无穷集当且仅当A与它的某些真子集等势2AA3、与某个自然数等势的集合称为有穷集，否则称为无穷集4、任何有穷集只与一个自然数等势5、任何与自然数集合等势的集合称为可数无穷集6、有穷集和可数无穷集统称为可数集，不是可数集的无穷集称为不可数集7、任何无穷集必有可数无穷子集8、可数集合删去或者合并一个有穷集合仍然是可数集合9、两个可数集合的并，笛卡尔积仍然是可数集第九章图的基本概念1、带权图：为每条弧或边指定了权的图称为带权图2、关联、相邻、邻接，自环，平行弧，平行边，多重弧图，多重边图，简单图，引出弧，引入弧，引出次数，引入次数，孤立点（次数0），悬挂点（次数1），悬挂边，零图（每个顶点都是孤立点），平凡图3、次数为奇数的顶点称为奇顶点，次数为偶数的顶点为偶顶点，在任何图中奇顶点的个数必为偶数4、正则图：所有顶点次数都是同一个数；完全图：任何两个顶点之间都有一条边的简单无向图；有向完全图：任何两顶点恰有一条弧的简单有向图5K，k数一样多，有同样多的环6/单回路，基本回路，无回路图，半通路，强连通，单向连通，弱连通，不连通7uv，uv8、有向图D是单向连通的当且仅当D有完备通路9、链，简单链，基本链，闭合链，圈，割点（去掉不连通），割边（去掉不连通），强连通分图，弱连通分图，压缩（把每个强连通分图作为一个点）第十章树1、定义：连通且无圈的无向图为树，非平凡树中至少有两片树叶2、称为顶点或弧指定了次序的根数是有序树3m0m4、在所有带权为p1...pn的二元树中，权最小的带权二元树称为最优二元树5、生成树，破圈法，最小生成树，割集（G中分离出E后成为两个连通分支，E是最小要分离的量）；基本割集（只包含一个树枝的割集）6、每个圈与任何生成树的补至少有一条公共