离散数学及其应用重要名词中英对应以及重要概念解释与举例.docx

离散数学及其应用 重要名词中英对应以及重要概念解释与举例1 The Foundations: Logic and Proofs （逻辑与证明）1.1 Propositional Logic（命题逻辑）Propositions（命题）declarative sentence that is either true or false, but not both.判断性语句，正确性唯一。Truth Table（真值表）Conjunction（合取，“与”，and），Disjunction（析取，or，“相容或”），Exclusive（异或），Negation（非，not），Biconditional（双条件，双向，if and only if）Translating English Sentences1.2 Propositional Equivalences（命题等价）Tautology（永真式、重言式），Contradiction（永假式、矛盾式），Contingency（偶然式）Logical Equivalences（逻辑等价）Compound propositions that have the same truth values in all possible cases are called logical equivalent.（真值表相同的式子，pq是重言式）Logical EquivalencesPage24Disjunctive normal form(DNF，析取范式)Conjunctive normal form(CNF，合取范式) 见Page27291.3 Predicates and Quantifiers（谓词和量词）Predicates谓词，说明关系、特征的修饰词Quantifiers量词 Universal Quantifier(全称量词) 全部满足 Existential Quantifier(存在量词) $至少有一个Binding Variables(变量绑定，量词作用域与重名的问题)Logical Equivalence Involving QuantifiersNegating Quantified Expressions(量词否定表达：否定全称=存在否定，否定存在=全程否定)Translating from English into Logical Expressions(自然语句转化为逻辑表达)Using Quantifiers in System SpecificationsExamples from Lewis Carrol全称量词与条件式(p-q)搭配，存在量词与合取式搭配。1.4 Nested Quantifiers（量词嵌套）Page59 12、13xyP(x,y) y x P(x,y)$x $yP(x,y) $y$xP(x,y)xyP(x,y) $yxP(x,y)yxP(x,y) $xyP(x,y)$xyP(x,y) y$xP(x,y)$yxP(x,y) x$yP(x,y)x$yP(x,y) $y$xP(x,y)y$xP(x,y) $x$yP(x,y)Prenex normal form(PNF 前束范式)：所有量词变换到最前面，否定变换到后面。1.5 Rules of Inference(推理规则)Valid Arguments in Propositionnal Logic(命题逻辑中的正确论点)Premises(前提)all but the final proposition in the argumentConclusion(结论)Rules of Inference for Propositionnal LogicPage 6667，证明方法及过程示范Resolution(归结): (pq) (p r) (q r) 合取，若两子句有互补文字，则可消去。Fallacies(谬论)Rules of Inference for Quantified StatementsUniversal instantiation(全称量词实例化)Universal generalization(全称量词一般化)Existential instantiation(存在量词实例化)Existential generalization(存在量词一般化) Page 70以上四点，其实就是一般和特殊之间的转换。名字是骗人的。1.6 Introduction to ProofsDirect proof:证明p-qProof by Contraposition:对位证明，通过证明其逆反命题来证明原命题Vacuous and Trivial ProofsProof by Contradiction:反证法1.7 Proof Methods and Strategy2 Basic Structures: Sets, Functions, Sequences and Sums（集合、函数、序列与和）Cardinality 集合的势，即其中元素的个数。Power Set :the set of all subsets of the set S.原集合的所有子集组成的集合。Cartesian product:笛卡尔积、直积，AB=(a,b)|aAbBFunctionOnto:满射Injective=One-to-One：单射Bijection：双射=单射加满射37 略8 Relations（关系）8.1 relations and Their PropertiesReflecxive自反：if (a, a)R for every element aA 都有环Irreflexive 反自反：一个环也没有Symmetric 对称：if (b, a)R whenever (a, b)R, for all a,b.有从a到b，必有从b到a。Antisymmetric 反对称：除非a=b，有从a到b，必无从b到a。Asymmetric 不对称：有从a到b，必无从b到a。Transitive 传递：a到b，b到c，则有a到c。Combining Relations(复合关系)：SR(空心圆圈)分配率：并集满足等价，交集满足包含(1) Fo(GH)= FoG FoH(2) Fo(GH) FoG FoH(3) (GH) oF = (GoF ) (HoF)(4) (GH) oF GoF HoFRn + 1= Rn oRThe relation R on a set A is transitive if and only if Rn属于R for n=1,2,38.2 n-ary Relations and Their Applications8.3 Representing Relations(表示关系) Representing Relations Using MatricesZero-One MatrixReflexive自反：主对角线上的数都为1。Symmetric对称：以主对角线为轴对称。 Representing Relations Using Digraphs(有向图)8.4 Closures of Relations(关系的闭包)闭包是指在原关系的基础上添加最少的有序对，构成满足一种特性的新的关系。自反闭包、对称闭包和传递闭包。Reflexive closure(自反闭包)：在所有元素上加环。Symmetric closure(对称闭包)：对于所有的(a, b)，添加(b, a)。Transitive Closure(传递闭包)：先合取再析取M(R*)=M(R)(M (R)M(R)(M(R)M(R)M(R)直到第n项*Warshalls Algorithm沃舍尔算法8.5 Equivalence RelationsA relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.等价=自反+对称+传递A的全域关系和恒等关系都是等价关系，空关系不具自反性。 全域关系：全部有序偶。 恒等关系：对称且反对称，有且只能有环。Equivalent等价量Equivalence Classes等价类集合中具有等价关系的一个子集。集合中与一个元素具有等价关系的全部元素构成的子集。Partitions分割 非空、无交集、其并集为全集。 Let R be an equivalence relation on a set S. Then the equivalence classes of R form a partition of S. Conversely, given a partition Ai | i I of the set S, there is an equivalence relation R that has the sets Ai, iI, as its equivalence classes.8.6 Partial Orderings偏序关系A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R).自反+反对称+传递Comparable可比：The elements a and b of a poset (S, *)are called comparable if either a*b or b*a.Totally ordered or linearly ordered(全序或线序)：没两个元素都是可比的。这样的集合又称作链(chain)Lexicographic Order(字典序) Page 569Well-ordered(良序)：A chain (A, R) is well-ordered良序 iff every nonempty subset of A has a least element.Hasse Diagrams(哈斯图)To construct a Hasse diagram:1) Construct a digraph representation of the poset (A, R) so that all arcs point up (except the loops).(所有的弧指向上)2) Eliminate all loops(删除环)3) Eliminate all arcs that are redundant because of transitivity(删除由于传递而多余的弧)4) Eliminate the arrows at the ends of arcs since everything points up.(删除箭头)Maximal and Minimal ElementsGreat and Least Element(唯一)Upper and Lower BoundsLeast Upper and Greatest Lower Bound(唯一) Page 572574Lattices格对于一个偏序集A，若其中任意两个元素a、b，都有最大下界和最小上界，则称这样的偏序集为格。Topological Sorting拓扑排序Not only one possible order.可能有多种排序方式。9 Graphs（图论）9.1 Graphs and Graph ModelsTypeEdgesMultiple Edges AllowedLoops AllowedSimple graph简单图UndirectedNoNoMultigraph多重图UndirectedYesNoPseudograph伪图UndirectedYesYesSimple directed graph简单有向图DirectedNoNoDirected multigraph多重有向图DirectedYesYesMixed graph混合图BothYesYes简单图+多重边重图，重图+环伪图Graph ModelsPage 5925959.2 Graph Terminology and Special Types of Graphs(图论术语和特殊图)Adjacent and Incident(连接和关联)：一条边相连的两点为连接，该边与这两点关联。这两点称作端点(endpoints).Degree:度，与一个点相关联的边数，deg(v).Isolated Vertex:孤立点，dev(v)=0.Pendant Vertex:悬挂点，dev(v)=1.The Handshaking Theorem(握手定理)Let G=(V，E) be an undirected graph with e edges. Then 2e=deg(v).度数是边数的两倍。An undirected graph has an even number of vertices of odd degree.奇数度顶点有偶数个。In-degree(入度): deg-(v),the number of edges with v as their terminal vertex(终点).Out-degree(出度):deg+(v), the number of edges with v as their initial vertex(起点).Let G=(V, E) be a graph with directed edges. Thendeg-(v)=deg+(v)=|E|.Some Special Simple GraphsComplete Graphs(全图) is the Simple graph that contains exactly one edge between each pair of distinct vertices. Kn 顶点数：n，边数：n(n+1)/2.Cycles(圈图),Cn 顶点数n，边数n.Wheels(轮图),Wn 顶点数n+1, 边数2n.Cube(方图)，Qn 顶点数2n, 边数2n-1*nBipartite Graphs(偶图，二分图)可通过着色法判断，有边相连的两点颜色不同，总共只有两种颜色。Complete Bipartite Graphs(完全二分图)New Graphs from OldSubgraph(子图) 生成子图Spanning Subgraph:与原图顶点相同，边是真子集。 导出子图：顶点是原图顶点的子集，而边为与它们相连的原图的所有边。The union of the simple graphs:所有简单图的边与顶点的并集所得到的简单图。9.3 Representing Graphs and Graph Isomorphism(图的表示与同构)Adjacency Lists and Matrices(邻接表与邻接矩阵) Page 612 点与点的关系对于有向图的邻接矩阵，行数字相加为该点出度，列数字相加为该点入度，所有数字相加为度数的一半，即边数。Incidence Matrices(关联矩阵) 点与边的关系。Isomorphism of Graphs(图的同构)必要条件：1，相同顶点数2，相同的边数3，对应顶点的度数相同4，子图相同5，路径相同使用矩阵判断两图是否同构： 邻接矩阵：任意交换行列，调整至两矩阵相同，即为同构。 关联矩阵：行与对应列同时做相同变动，调整至两矩阵相同，为同构。9.4 Connectivity连通Paths(路径)有向图路径和无向图路径Circuit(回路)，Traverse(遍历)简单路径：每条边只出现一次。初级路径：每个点只出现一次。Connectedness in Undirected Graphs(无向图的连通)An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph.Connected component 连通分支:Maximal connected subgraph of G.Cut vertices(割点)/cut edge(割边、或bridge桥)：扔掉它们就会产生更多连通分支的东西。Connectedness in Directed GraphsStrongly connected强连通路径a到b和b到a同时存在。Weakly connected弱连通两点之间有线存在(underlying undirected graph看作无向图路径即可)。强连通一定是弱连通。Counting Paths between Vertices使用该图的邻接矩阵A，长度为n，就计算An。对应行乘以对应列。The (i, j)th entry of Ar+1 equals: bi1a1j+bi2a2j+bi3a3j+binanj.9.5 Euler and Hamilton Paths Euler Paths and Circuits:欧拉路径、回路，周游原图的每一条边。 Hamilton Paths and Circuits:哈密顿路径、回路，周游每个顶点。 一个连通重图具有欧拉回路，当且仅当它的每个顶点都是偶数度。 一个连通重图具有欧拉路径(称为半欧拉图)，当且仅当它有且只有两个奇度数顶点。对于一个有向图而言：欧拉回路的条件：1，每个顶点都有偶数度。2，出度等于入度。欧拉路径的条件：1，仅有两个顶点有奇数度。2，对于偶度数顶点，出度等于入度。3，对于奇数度顶点，出度和等于入度和。Hamilton Paths and Circuits充分条件：Ores Theorem: If G is a simple graph with n vertices with n3 such that deg(u)+deg(v)n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit.任意两顶点度数之和不小于总的顶点数。Diracs Theorem: If G is a simple graph with n vertices with n3 such that the degree of every vertex is at least n/2, then G has a Hamilton circuit.每一点的度数都不小于总顶点数的一半。必要条件：If G is a Hamiltonian graph, then for every nonempty proper set S of vertices of G, K(G-S)|S|.删去任意顶点后的连通分支数不大于删去的顶点数。9.6 Shortest-Path ProblemsWeighted graphs(带权图)边带权和顶点带权。A Shortest-Path AlgorithmThe Traveling Salesman Problem9.7 Planar Graphs定义：可以画在一个平面内，而没有任意两条边交叉的图。最小非平面图：删去一条边可以变成平面图的非平面图。最大平面图：任意加一条边都会变成非平面图的平面图。Eulers Formula 平面图欧拉公式Region=edge-vertice+2 (connected planar simple graph平面连通简单图)所有面的度数之和等于边数的两倍。区域度数计算：围成该区域的边数，悬挂边记作两度。Corollary 1:If G is a connected planar simple graph with e edges and v vertices, where v3, then e3v-6.Corollary 2:If G is a connected planar simple graph, then G has a vertex of degree not exceeding five.Kuratowskis Theorem(库拉图斯基/苦辣兔斯基定理)Elementary subdivision(初等分割)&Homeomorphic(同胚)增加新的点只能是有两度的点，删点也只能删两度的点。K Theorem: A graph is nonplanar if and only if it contains a subgraph homoeomorphic to K3,3 or K5.9.8 Graph ColoringDual Graph对偶图：指原图中的每个封闭区域对应一个点，每条边对应一条边(连接两顶点，与原来的边相交)而形成的新图。环对应悬挂边。同构的图，对偶图不一定同构。Chromatic Number(色数)：为一个图上色所需的最少颜色数。The Four Color Theorem: The chromatic number of a planar graph is no greater than four.10 Trees（树）10.1 Introduction to TreesDefinition: a tree is a connected undirected graph with no simple circuits.An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices. (任意