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

1、学习必备欢迎下载离散数学及其应用重要名词中英对应以及重要概念解释与举例The Foundations: Logic and Proofs （逻辑与证明）Propositional Logic （命题逻辑）Propositions （命题）declarative sentence that is either true or false, but not both.判断性语句,正确性唯一。Truth Table （真值表）Conjunction （合取， 与“，and） , Disjunction （析取，or, 相容或“）,Exclusive （异或）, Negation （非，not） ,

2、Biconditional （双条件，双向，if and only if ）Translating English SentencesPropositional Equivalences （命题等价）Tautology （永真式、重言式）， Contradiction （永假式、矛盾式）， Contingency （偶然式）Logical Equivalences （逻辑等价）Compound propositions that have the same truth values inall possible cases are called logical equivalent.（真值表相

3、同的式子，pq 是重言式）Logical EquivalencesPage24Disjunctive normal form（DNF ,析取范式）Conjunctive normal form（CNF ,合取范式）见 Page2729Predicates and Quantifiers （谓词和量词）Predicates谓词，说明关系、特征的修饰词Quantifiers量词? Universal Quantified 全称量词）”学习必备欢迎下载全部满足? Existential Quantifier(存在量词)$至少有一个Binding Variables(变量绑定，量词作用域与重名的问题)

4、Logical Equivalence Involving QuantifiersNegating Quantified Expressions(量词否定表达：否定全称=存在否定，否定存在 =全程否定)Translating from English into Logical Expressions( 自然语句转化为逻辑表达)Using Quantifiers in System SpecificationsExamples from Lewis Carrol全称量词与条件式 (p-q)搭配. 存在量词与合取式搭配。Nested Quantifiers (量词嵌套)Page59 12、13xy

5、P(x,y) ? y x P(x,y)$x $yP(x,y) ? $y$xP(x,y)xyP(x,y) T $yxP(x,y)yxP(x,y) T $xyP(x,y)$xyP(x,y) T y$xP(x,y)$yxP(x,y) T x$yP(x,y)x$yP(x,y) T $y$xP(x,y)y$xP(x,y) T $x$yP(x,y)Prenex normal form(PNF前束范式):所有量词变换到最前面，否定变换到后面。学习必备欢迎下载Rules of Inference（推理规则）Valid Arguments in Propositionnal Logic（命题逻辑中的正确论点）P

6、remises（前提）all but the final proposition in the argumentConclusion（结论）R ules of Inference for Propositionnal LogicPage 6667,证明方法及过程示范Resolution（归结）:（p V q） A （n p V r） 一（q V r）合取，若两子句有互补文字，则可消去。Fallacies（谬论）R ules of Inference for Quantified StatementsUniversal instantiation（全称量词实例化）Universal genera

7、lization（全称量词一般化）Existential instantiation（存在量词实例化）Existential generalization（存在量词一般化）Page 70以上四点，其实就是一般和特殊之间的转换。名字是骗人的。Introduction to ProofsDirect proof:证明 p-qProof by Contraposition:对位证明，通过证明其逆反命题来证明原命题Vacuous and Trivial ProofsProof by Contradiction:反证法学习必备欢迎下载Proof Methods and StrategyBasic Str

8、uctures: Sets, Functions, Sequences and Sums(集合、函数、序列与和)Cardinality集合的势，即其中元素的个数。Power Set :the set of all subsets of the set S.原集合的所有子集组成的集合。Cartesian product:笛卡尔积、直积， AXB=(a,b)|a C A A b C BFunctionOnto:满射Injective=One-to-One :单射Bijection :双射=单射加满射37略8 Relations (关系)relations and Their PropertiesR

9、eflecxive 自反：if (a, a) C R for every element a A 者B有环Irreflexive 反自反：一个环也没有Symmetric 对称:if (b, a) CR whenever (a, b) C R, for all a,b.有从 a 至1Jb,必有从 b 到 a。Antisymmetric 反对称：除非 a=b,有从a到b,必无从 b到a。Asymmetric不对称：有从 a至1Jb,必无从b到a。Transitive 传递：a 至1J b, b 至1J c,贝U有 a 至U c。Combining Relations(复合关系):SR(空心圆圈)学

10、习必备欢迎下载分配率：并集满足等价，交集满足包含Fo(G H)= FoG 于oHFo(G?H) FoG? FoH(G 啕 oF = (GoF ) (HoF)(G?H) oF G oF? HoFRn + 1= Rn oRThe relation R on a set A is transitive if and only if R n 属于 Rfor n=1,2,3n-ary Relations and Their ApplicationsRepresenting Relations(表示关系)? Representing Relations Using MatricesZero-One Mat

11、rixReflexive自反：主对角线上的数都为1。Symmetric对称：以主对角线为轴对称。? Representing Relations Using Digraphs( 有向图)Closures of Relations(关系的闭包)闭包是指在原关系的基础上添加最少的有序对，构成满足一种特性的新的关系。自反闭包、 对称闭包和传递闭包。Reflexive closure(自反闭包)：在所有元素上加环。Symmetric closure(对称闭包):对于所有的(a, b),添加(b, a)。Transitive Closure（传递闭包）:。：先合取再析取学习必备欢迎下载M(R*)=M(R

12、) V (M (R) A M(R) V (M(R) A M(R) A M(R)直到第 n 项*Warshall s Algorithm舍尔算法Equivalence RelationsA relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.等价=自反+对称+传递A的全域关系和恒等关系都是等价关系，空关系不具自反性。2全域关系：全部有序偶。2恒等关系：对称且反对称，有且只能有环。Equivalent 等价量Equivalence Classes 等价

13、类集合中具有等价关系的一个子集。集合中与一个元素具有等价关系的全部元素构成的子集。Partitions 分害口2非空、无交集、其并集为全集。2 Let R be an equivalence relation on a set S. Then the equivalence classes of R form a partition ofConversely, given a partition Ai | i I of the set S, there is an equivalence relation R that has the sets Ai, i C I, as its equiva

14、lence 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).学习必备欢迎下载自反+反对称+传递Comparabl

15、e 可比: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 Dia

16、grams（哈斯图）To construct a Hasse diagram:Construct a digraph representation of the poset （A, R） so that all arcs point up （except the 100Ps）.（所有的弧指向上）Eliminate all loops（删除环）Eliminate all arcs that are redundant because of transitivity（ 删除由于传递而多余的弧 ）Eliminate the arrows at the ends of arcs since every

17、thing points up.（ 删除箭头）Maximal and Minimal ElementsGreat and Least Element（唯一）Upper and Lower BoundsLeast Upper and Greatest Lower Bound（唯一）574Lattices 格学习必备欢迎下载对于一个偏序集 A,若其中任意两个元素a、b,都有最大下界和最小上界，则称这样的偏序集为格。Topological Sorting 拓扑排序Not only one possible order.可能有多种排序方式。Graphs (图论)9.1 Graphs and Graph

18、 ModelsTypeEdgesMultiple Edges AllowedLoops AllowedSimple graph 简单图UndirectedNoNoMultigraph 多重图UndirectedYesNoPseudograph 伪图UndirectedYesYesSimple directed graph 简单图DirectedNoNoDirected multigraph 多重有向图DirectedYesYesMixed graph 混合图BothYesYes简单图+多重边重图，重图+环伪图Graph ModelsPage 592595Graph Terminology an

19、d 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= E deg（v）.度数是边数

20、的两倍。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（ 起1点）.Let G=（V, E） be a graph with directed edges. Then -（v）= oU+gv

21、）=|E|.Some Special Simple GraphsComplete Graphs（全图）is the Simple graph that contains exactly one edge between each pair of distinct vertices. K n 顶点数：n,边数：n（n+1）/2.Cycles（圈图）,Cn顶点数n,边数n.Wheels（轮图）,Wn顶点数n+1,边数2n.Cube（方图），Qn顶点数2n,边数2n-1*nBipartite Graphs（偶图，二分图）可通过着色法判断，有边相连的两点颜色不同，总共只有两种颜色。Complete B

22、ipartite Graphs（完全二分图）New Graphs from OldSubgraph（子图）?生成子图Spanning Subgraph:与原图顶点相同，边是真子集。?导出子图：顶点是原图顶点的子集，而边为与它们相连的原图的所有边。学习必备欢迎下载The union of the simple graphs:所有简单图的边与顶点的并集所得到的简单图。Representing Graphs and Graph Isomorphism（图的表示与同构）Adjacency Lists and Matrices（邻接表与邻接矩阵 ）Page 612点与点的关系对于有向图的邻接矩阵,行数字

23、相加为该点出度，列数字相加为该点入度，所有数字相加为度数的一半，即边数。Incidence Matrices（关联矩阵）点与边的关系。Isomorphism of Graphs（图的同构）必要条件：1,相同顶点数2,相同的边数3,对应顶点的度数相同4,子图相同5,路径相同使用矩阵判断两图是否同构：?邻接矩阵：任意交换行列，调整至两矩阵相同，即为同构。?关联矩阵：行与对应列同时做相同变动，调整至两矩阵相同，为同构。Connectivity 连通Paths（路径）一一有向图路径和无向图路径Circuit（回路）,Traverse（遍历）学习必备欢迎下载简单路径：每条边只出现一次。初级路径：每个点只

24、出现一次。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 G

25、raphsStrongly connected强连通路彳仝a至1J b和b至1J a同时存在。Weakly connected弱连通两点之间有线存在 （underlying undirected graph看作无向图路径即可）。强连通一定是弱连通。Counting Paths between Vertices使用该图的邻接矩阵A,长度为n,就计算Ano对应行乘以对应列。The （i, j）th entry of A r+1 equals: biiaij+bi2a2j+bi3a3j+binanj.Euler and Hamilton Paths? Euler Paths and Circuits

26、:欧拉路径、回路，周游原图的每一条边。? Hamilton Paths and Circuits:哈密顿路径、回路，周游每个顶点。2 一个连通重图具有欧拉回路，当且仅当它的每个顶点都是偶数度。学习必备欢迎下载2一个连通重图具有欧拉路径(称为半欧拉图)，当且仅当它有且只有两个奇度数顶点。对于一个有向图而言：欧拉回路的条件：1,每个顶点都有偶数度。2,出度等于入度。欧拉路径的条件：1,仅有两个顶点有奇数度。2,对于偶度数顶点，出度等于入度。3,对于奇数度顶点，出度和等于入度和。Hamilton Paths and Circuits充分条件：Ore s Theoremlf G is a simple

27、 graph with n vertices with ndeg(U)3cterp(Jv)that n forevery pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit. 任意两顶,点度数之 和不小于总的顶点数。Dirac s Theorem G is a simple graph with n vertices with n 3 such that the degree of everyvertex is at least n/2, then G has a Hamilton circuit.每

28、一点的度数都不小于总顶点数的一半。必要条件：If G is a Hamiltonian graph, then for every nonempty proper set S of vertices of G, K(G- S) 3, th（e 3-6.Corollary 2:If G is a connected planar simple graph, then G has a vertex of degree not exceeding five.Kuratowski s Theorem图斯基/苦辣兔斯基定理）Elementary subdivision（初等分害U ）&Homeomorp

29、hic（同胚）增加新的点只能是有两度的点，删点也只能删两度的点。K TheoreiA graph is nonplanar if and only if it contains a subgraph homoeomorphic to K 3,3or K5.学习必备欢迎下载Graph ColoringDual Graph对偶图：指原图中的每个封闭区域对应一个点，每条边对应一条边（连接两顶点，与原来的边相交）而形成的新图。环对应悬挂边。同构的图，对偶图不一定同构。Chromatic Number（色数）：为一个图上色所需的最少颜色数。The Four Color Theorem : The chromatic number of a planar graph is no greater than four.Trees （树）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.（任意两点之间只有一条通路）A r