离散数学知识点总结

注意/技巧：析取符号为V,大写字母Vx+y=3不是命题前件为假时，命题恒为真运用吸收律命题符号化过程中要注意命题间的逻辑关系认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。也就是说，在不改变原意的基础上，按照最简单的方式翻译通用的方法：真值表法VxP（x）蕴含存在xP（x）利用维恩图解题证明两个集合相等：证明这两个集合互为子集常用的证明方法：任取待证集合中的元素<,>构造相应的图论模型第一章命题逻辑命题和联结词命题的条件：表达判断的陈述句、具有确定的真假值。选择题中的送分题原子命题也叫简单命题，与复合命题相对简单联结词的真值表要记住非（简单）合取（当且仅当P，Q都为真时，命题为真）析取（当且仅当P，Q都为假时，命题为假），P，Q可以同时成立，是可兼的或条件（f）（当且仅当P为真，Q为假时，命题为假）P是前件，Q是后件只要P，就Q等价于P-Q只有P，才Q等价于非P-非Q，也就是Q-PP-Q特殊的表达形式：P仅当Q、Q每当P双条件（一）（当且仅当P与Q具有相同的真假值时，命题为真，与异或相反）命题公式优先级由高到低：非、合取和析取、条件和双条件括号省略条件：①不改变先后次序的括号可省去②最外层的括号可省去重言式（永真式入矛盾式（永假式入偶然式可满足式：包括重言式和偶然式逻辑等价和蕴含（逻辑）等价:这是两个命题公式之间的关系，写作“Q”，要与作为联结词的一区分开来。如果命题公式A为重言式，那么AqT常见的命题等价公式：需要背过被标出的，尽量去理解。关键是掌握公式是将哪个符号转换为了哪个符号，这对于解证明题有很大的帮助！验证两个命题公式是否等价：当命题变元较少时，用真值表法。当命题变元较多时，用等价变换的方法，如代入规则、替换规则和传递规则定理：设A、B是命题公式，当且仅当A-B是一个重言式时，有A和B逻辑等价。蕴含:若A-B是一个重言式，就称作A蕴含B,记作AnB常见的蕴含公式的运用方法同上面的命题等价公式证明AoB:①肯定前件，推出后件为真②否定后件，推出前件为假当且仅当AoB且BoA时，AqB，也就是说，要证明两个命题公式等价，可以证明它们相互蕴含联结词的完备集新的联结词：条件否定、异或（不可兼或、或非（析取的否定、与非（合取的否定）任意命题公式都可由仅含｛非，析取｝或｛非，合取｝的命题公式来等价地表示全功能联结词集合极小全功能联结词集合对偶式对偶式：将仅含有联结词非、析取、合取（若不满足，需先做转换）的命题公式A中的析取变合取，合取变析取，T变F，F变T得到的命题公式A*称为A的对偶式范式析取式：否定+析取合取式：否定+合取析取范式：（合取式）析取（合取式）……析取（合取式。内合外析合取范式：（析取式）合取（析取式）……合取（析取式。内析外合对于任何一个命题公式，都可以求得它的合取范式或者析取范式方法一：（1）将公式中的联结词都归约成非、析取和合取（2）利用德摩根定律将否定联结词直接移到各命题变元之前（3）利用分配律、结合律将公式归约成合取范式或析取范式极小项：一个含n个命题变元的合取式，如果其中每个变元与其否定不同时存在，但两者之一必须出现且仅出现一次性质：任意两个不同极小项的合取式永假，所有极小项的析取式永真主析取范式：定义在课本的第28页相关例题在第29页一个命题的主析取范式是唯一的构造真值表是求主析取/合取范式的重要方法等价推演法是另一个方法：（1）将原命题公式转化为析取范式（2）将每个合取式等价变换为若干极小项的析取（对每个合取式填补没有出现的变元，如缺P和非P，则合取非P析取P，再应用分配律展开）（3）重复的极小项只保留一个极大项：析取式，其余定义与极小项相同，举一反三性质：两个不同极大项的析取式永真；所有极大项的合取式永假极大项对应的是主合取范式!这与析取范式和合取范式的道理是相同的注意极大项的编码与极小项恰好相反在一个命题公式的真值表里，使A的真值为F的所有赋值所对应的极大项构成的合取范式即为A的主合取范式一个命题公式的主合取范式是唯一的等价推演法就不再详细说了，需要注意的是应该析取一个F（析取一个F,相当于不析取）一些逻辑推断的问题：可以通过命题的主范式来解决命题逻辑的推理理论H1，H2，……，HnC，前提为真时，结论C为真；前提为假时，结论C可能为真，也可能为假推理证明时，主要用到的公式是等价公式和蕴含公式，还有P规则和T规则推理方法有无义证明法（少用、平凡证明法（少用），直接证明法（基础）反证法：为了推出结论C，将C加以否定，并将非C加入结论，利用直接证明法推出矛盾，比如R合取非R，即可得证。否定的步骤写作P（假设前提）CP规则法：结论必须是条件式，若不是，需要作出转换，将前件加入前提的步骤写作P（附加前提）以上用到的命题等价公式、蕴含公式只需写E、I即可第二章谓词逻辑谓词和量词谓词将简单命题进一步分析，找出所描述的对象及对象间的关系，抽象出同类命题描述的一般模式，谓词刻画了单个个体的的特性或者多个个体间关系的模式个体常元、个体变元论域（个体域）：个体变元的取值范围量词分为全称量词和存在量词。量化分为全称量化和存在量化。量化后所得命题的真值与变元的论域有关。引入一个统一的个体论域——全总个体域它包括所有个体变元所能代表的所有可能的个体。以后除非特别说明，否则论域都默认是全总个体域。此时，对个体变元的变化范围，可以用特性谓词（如H（x）:x是人）来加以限制将特性谓词加入命题公式时，有以下两条重要的规则：①对于全称量词，特性谓词作为条件式的前件加入②对于存在量词，特性谓词作为合取式的合取项加入谓词公式谓词公式的定义与命题公式的定义基本上相同在辖域内x的一切出现称为约束出现，约束出现的个体变元x称为约束变元。个体变元的非约束出现称为自由出现，自由出现的个体变元称为自由变元约束变元的换名（防止引起混淆）规则：对某个约束变元换名时，需对量词的作用变元以及该量词辖域内所有受该量词约束的约束变元一起换名。自由变元的换名规则：自由变元代入时，谓词公式中该变元自由出现的每一处都要同时代入谓词演算的永真公式谓词公式有永真、永假和可满足三种情况，而这都是针对特定论域而言的等价：给定任意两个谓词公式A和B，若对于任何赋值，A和B的真值均相同，则称谓词公式A和B等价，记为AB蕴含：给定任意两个谓词公式A和B，若A-B是永真式，则称A蕴含B，记为AB命题逻辑中的代入规则、替换规则在谓词逻辑中同样适用量词的否定律①不是对于任意的x都有P（x）成立等价于存在一个x使得P（x）不成立②不存在一个x使得P（x）成立等价于对于任意的xP（x）都不成立以上两个公式说明了全称量词和存在量词可以相互表达量词的辖域可以扩张与收缩量词的分配律①全称量词对合取可分配②存在量词对析取可分配课本第51页有关于分配律的若干重要公式全称量词和存在量词在谓词公式中出现的次序不能随意改变课本第53页有若干等价公式和蕴含公式谓词逻辑的推理理论命题逻辑的推理规则，如P规则、T规则和CP规则以及证明方法在谓词逻辑中同样适用。消去量词和引入量词的四种常用推理规则（1）存在指定规则存在xP（x）,有P（a）,其中a是论域中使得P（a）的真值为真的个体（2）全称指定规则VxP（x）,有p（y）（y在P（y）中是自由变元）和P（a）注意：当对谓词公式存在xP（x）和VxQ（x）均应用指定规则指定为同一个体时，应先进行存在指定，再进行全称指定(3)存在推广规则P(a),有存在xP(x)(4)全称推广规则ToP(x)，有ToVxP(x)。如果能够从已知的公理和前提证明对于论域中的任一个体都使(x)为真，则可以得到VxP(x)为真第三章集合与关系集合的概念与表示符号：子集U，真子集u或空集是任意集合的子集且是任何非空集合的真子集。因为空集不是空集的真子集重要的概念还有幕集集合的基本运算基础：交、并、补、差(也叫做相对补)对称差(环和)，环积的定义及运算需要背过课本69页有若干集合运算律课本70页有三条重要的公式容斥原理两个集合的容斥原理非常重要必须掌握若干个集合的容斥原理也要了解归纳证明需要掌握的有数学归纳法第一原理和数学归纳法第二原理数学归纳法第一原理在证明n+1规模成立时，为了尽量避免分解中的错误通常采用“从n+1个元素集合中取出1个元素让问题变成n规模，应用归纳假设后再放回去”的策略集合的笛卡尔积笛卡尔积也叫做叉集，其中的元素为序偶或n元组（序偶为n=2的特例方集合A的n次方A^n的概念便出于此。注意做笛卡尔积的顺序不能随意改变笛卡尔积运算对交、并运算可分配。同时注意先后顺序二元关系定义：两个集合A和B的笛卡尔积AxB的任意子集R，称为集合A到B上的二元关系。二元二元，说明了R是由序偶组成的集合若x与y有R关系，则序偶＜x,y＞应属于集合R，并与＜丫不＞属于集合R无任何关系。n元关系是二元关系的推广。空关系是指关系集合R为空，全域关系是指关系集合R为A1A2……An的笛卡尔积关系可以用集合来表示，还可以用关系矩阵和关系图来表示关系矩阵与有向无权图的邻接矩阵非常相似画关系图时要注意连线上带着箭头。关系的运算有交、并、补（全集为全域关系）和环和对于二元关系，有两种特殊的运算复合运算：运算符号用空心圆圈表示。称RoS为R与S的复合关系。例如R={<a,b>},S={<b,c>},那么RoS={<a,c>}除了暴力运算，求复合关系还可以通过关系矩阵的布尔乘法来实现Mros=Mr©Ms结合律:(RoS)oT=Ro(SoT)逆关系：记作R的-1次方。也就是将R中的所有序偶反向。体现在关系矩阵上就是R与其逆关系的关系矩阵互为转置矩阵逆运算对交、并、差运算可分配(RoS)-1=S-1oR-1(即位置互换)集合上的二元关系及其特性A上的二元关系(注意这个说法)：集合A与A的笛卡尔积AxA的子集。A上的二元关系是AxA的子集！集合A的相等关系：记作IAO{<a,a>|aeA}关系的幕次与复合运算执行的次数有关。即设R是集合A上的二元关系，称RoRoRoRo……oR为R的n次幕注意之前的A是普通集合，而这里的R是关系集合规定R的0次幕为集合A上的相等关系运算与代数的幕次运算无差别。注意一个技巧：R的多次复合运算(即幕次)容易出现周期性循环二元关系的特性（1）自反性设R是集合A上的二元关系，如果对于A中的每一元素x都有xRx，则称R在A上是自反的。关系图中的元素;表现为一个小圆圈）是A中的所有元素。比如A={a,b,c,d}。只有当<a,a>,<b,b>,<c,c>,<d,d>都属于R时，才能称R在A上是自反的反自反的要求也很高，要求**每一元素**x都没有xRx只有空集上的空关系既是自反的又是反自反的课本第94页上的表3.7.1总结地很好（2）对称性如果R的关系图上仅含有0个或多个自回路，那么R既是对称的，又是反对称的。如果R的关系图上，仅存在两个不同的结点，其间有单向弧，又存在两个不同的结点，其间有方向相反的一对弧，那么R既不是对称的，又不是反对称的（3）传递性空集是反自反、对称、反对称和传递的。关系的闭包运算R的自反闭包r（R）是包含R的最小的、自反的关系集合R的对称闭包s（R）是包含R的最小的、对称的关系集合R的传递闭包t（R）是包含R的最小的、传递的关系集合R是自反的当且仅当r（R）=RR是对称的当且仅当s（R）=RR是传递的当且仅当t(R)=R求关系R的闭包：①r(R)=RUIA(集合A上的相等关系)②s(R)=RUR-1(R的逆关系)③t(R)=R的一次方UR的二次方U……UR的无穷次方(一般只需做几次复合运算，找出循环)或者利用“史蒂芬・沃舍尔”方法求传递闭包。再或者利用定理设R是有限集合A上的二元关系且|A|二n，那么有t(R尸RURA2URA3U...URAn设R是集合A上的二元关系，则有①如果R是自反的，那么s(R)和t(R)也是自反的。②如果R是对称的，那么r(R)和t(R)也是对称的。③如果R是传递的，那么r(R)也是传递的。注意这里的s(R)不是传递的。①②的道理很简单，利用闭包的运算中有并运算便可以解释明白。注意③中的s(R)闭包运算的复合运算：①sr(R)=s(r(R))=rs(R)②tr(R)=rt(R)③st(R)ts(R)以上说明了，自反闭包运算与对称或传递闭包运算的先后顺序互换后不影响运算的结果，但是对称闭包运算与传递闭包运算的先后顺序不能随意转换等价关系集合的划分和覆盖注意小集合不能为空集，n=p(A)-为集合A的覆盖一个集合A的划分n中的元素Ai称为该划分的块划分的块数|n|为划分的秩设R是集合A上的一个二元关系，若R是自反、对称和传递的，则称R为等价关系•验证自反性：IAUR验证对称性：R-1UR验证传递性：RoRuR等价类：基于等价关系，所以要先求等价关系定义在课本第105页商集：设R是集合A上的等价关系，由R确定的所有等价类组成的集合，称为集合A上关于R的商集，记为A/R商集的元素的集合(等价类)，这两种写法都可以。A上关于R的商集A/R就是集合A的一个划分，通常称为由R诱导的A的划分任意集合A上的等价关系与该集合的划分之间的一一对应的，相互可诱导的。由划分诱导等价关系：将每个块做笛卡尔积然后并起来。因为A上的等价关系与A的划分是一一对应的，因此可以先求A上的所有划分，然后再求由这些划分分别诱导的等价关系。第七章图论图的基本概念如下：图的定义无向边：端点，｛｝，无箭头连线有向边：始点、终点，＜＞，带箭头连线删点必删边，删边不删点有限图、无限图无向图、有向图、混合图底图邻接点、邻接边、孤立顶点零图、平凡图平行边、自回路（或环）含有平行边的图称为多重图不含平行边的图称为线图不含自回路的线图称为简单图赋权图与结点v关联的边数称为结点v的度数。有向图中还将度分为入度和出度握手定理：在任何图中，所有结点的度数之和等于边数的两倍推论：任何图中，奇数度的结点必为偶数个在任何有向图中，所有结点的入度之和等于所有结点的出度之和等于图中的边数无向完全图：Kn有向完全图：Dn具有n个结点的无向完全图共有n（n-2）/2条边，有向完全图有n〃2条边二部图二部图必无自回路，但可以有平行边简单判定一个图是否是二部图的方法设G=<X,E,Y,>是一个二部图，若G是一个简单图，并且X中的每个结点与Y中的每个结点均邻接，则称G为完全二部图。如果|X|二m，|Y|=n，则在同构的意义下，这样的完全二部图只有一个子图、生成子图补图图的同构：相互同构的图只是画法不同或结点与边的命名不同而已图的连通性路一条路中所含的边数称为该路的长度若一条路中经过的所有结点均不相同，则称该路为通路若一条路中经过的所有边均不相同，则称该路为迹始点与终点不同的迹称为开迹通路一定是迹，但是迹不一定是通路始点与终点相同的路称为回路经过的每条边均不相同的回路称为闭迹除始点与终点外其余结点均不相同的闭迹称为圈设G是一个无向图，若G中每个结点的度数大于等于2，则G中必有圈设G是无向图，且|E|>0，G是二部图当且仅当G中不含奇圈无向图的连通性、连通分支如果一个简单无向图不是连通的，则它的补图一定连通割集若某一个结点构成一个点割集，则称该结点为割点连通无向图G中的一个结点w是割点，当且仅当G中存在两个不同于w的结点间的每条路都要通过该结点边割集若某条边构成边割集，则称该边为割边或桥无向图G中的一条边是割边，当且仅当它不包含在G的任一圈中有向图的连通性、强连通、单侧连通、弱连通若图G是强连通的，则它必是单侧连通的；若图G是单侧连通的，则它必是弱连通的一个有向图是强连通的，当且仅当图中存在一条回路，它至少包含图中每个结点一次在有向图中，G1是G是子图，若G1是强连通（单侧连通、弱连通）的，且不存在G的子图G2G1，并且G2也是强连通（单侧连通、弱连通）的，则称G1为G的强（单侧、弱）分图迪杰斯特拉算法基于这样一个事实：从s到t的最短路如果通过结点v，那么s到v的部分必然也是从s到v的最短路这样就可以按照距离递增的顺序依次寻找s到其他结点的最短路图的矩阵表示邻接矩阵A（A^T）的元素的意义（AAT）A的元素的意义AxA的元素的意义可达矩阵可达矩阵用于描述一个线图中从任意结点到另一结点之间是否存在路由于在图中两个结点之间有路，则必存在长度小于等于n-1的通路，另外认为同一个结点到自身可达可达矩阵P(G)的计算方法利用邻接矩阵A和可达矩阵P，可以判断图的连通性利用可达矩阵P,可以求得有向图的强分图设r是集合V上的二元关系，nw正整数，对于任意a,beV,<a,b>wRAn当且仅当R的关系图G=<V,£>中存在从a到b的长度为n的有向路欧拉图与汉密尔顿图包含图中所有边的开迹称为该图中的一条欧拉迹或欧拉路包含图中所有边的闭迹称为欧拉回路含欧拉回路的图称为欧拉图无向图G是欧拉图当且仅当G是连通的并且每个结点的度均为偶数无向图G中存在一条欧拉迹，当且仅当G是连通的，并且图中恰有两个奇数度的结点有向图G是欧拉图，当且仅当它是连通的，并且每个结点的入度等于其出度一个有向图G中具有单向欧拉路，当且仅当它是连通的，而且除了2个结点外，每个结点的入度等于出度。但是在这2个结点中，一个结点的入度比出度小1，一个结点的入度比出度大1汉密尔顿图包含图中每个结点一次且仅一次的通路称为汉密尔顿路包含图中所有结点一次且仅一次的圈称为汉密尔顿圈含汉密尔顿圈的图称为汉密尔顿图目前为止还没有找到一个简单的判定汉密尔顿路或回路的存在性的充