離散數(shù)學(xué)及其應(yīng)用重要名詞中英對(duì)應(yīng)以及重要概念解釋與舉例

1、學(xué)習(xí)必備歡迎下載離散數(shù)學(xué)及其應(yīng)用重要名詞中英對(duì)應(yīng)以及重要概念解釋與舉例The Foundations: Logic and Proofs （邏輯與證明）Propositional Logic （命題邏輯）Propositions （命題）declarative sentence that is either true or false, but not both.判斷性語(yǔ)句,正確性唯一。Truth Table （真值表）Conjunction （合取， 與“，and） , Disjunction （析取，or, 相容或“）,Exclusive （異或）, Negation （非，not） ,

2、Biconditional （雙條件，雙向，if and only if ）Translating English SentencesPropositional Equivalences （命題等價(jià)）Tautology （永真式、重言式）， Contradiction （永假式、矛盾式）， Contingency （偶然式）Logical Equivalences （邏輯等價(jià)）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 ,合取范式）見(jiàn) Page2729Predicates and Quantifiers （謂詞和量詞）Predicates謂詞，說(shuō)明關(guān)系、特征的修飾詞Quantifiers量詞? Universal Quantified 全稱量詞）”學(xué)習(xí)必備歡迎下載全部滿足? Existential Quantifier(存在量詞)$至少有一個(gè)Binding Variables(變量綁定，量詞作用域與重名的問(wèn)題)

4、Logical Equivalence Involving QuantifiersNegating Quantified Expressions(量詞否定表達(dá)：否定全稱=存在否定，否定存在 =全程否定)Translating from English into Logical Expressions( 自然語(yǔ)句轉(zhuǎn)化為邏輯表達(dá))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前束范式):所有量詞變換到最前面，否定變換到后面。學(xué)習(xí)必備歡迎下載Rules of Inference（推理規(guī)則）Valid Arguments in Propositionnal Logic（命題邏輯中的正確論點(diǎn)）P

6、remises（前提）all but the final proposition in the argumentConclusion（結(jié)論）R ules of Inference for Propositionnal LogicPage 6667,證明方法及過(guò)程示范Resolution（歸結(jié)）:（p V q） A （n p V r） 一（q V r）合取，若兩子句有互補(bǔ)文字，則可消去。Fallacies（謬論）R ules of Inference for Quantified StatementsUniversal instantiation（全稱量詞實(shí)例化）Universal genera

7、lization（全稱量詞一般化）Existential instantiation（存在量詞實(shí)例化）Existential generalization（存在量詞一般化）Page 70以上四點(diǎn)，其實(shí)就是一般和特殊之間的轉(zhuǎn)換。名字是騙人的。Introduction to ProofsDirect proof:證明 p-qProof by Contraposition:對(duì)位證明，通過(guò)證明其逆反命題來(lái)證明原命題Vacuous and Trivial ProofsProof by Contradiction:反證法學(xué)習(xí)必備歡迎下載Proof Methods and StrategyBasic Str

8、uctures: Sets, Functions, Sequences and Sums(集合、函數(shù)、序列與和)Cardinality集合的勢(shì)，即其中元素的個(gè)數(shù)。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 (關(guān)系)relations and Their PropertiesR

9、eflecxive 自反：if (a, a) C R for every element a A 者B有環(huán)Irreflexive 反自反：一個(gè)環(huán)也沒(méi)有Symmetric 對(duì)稱:if (b, a) CR whenever (a, b) C R, for all a,b.有從 a 至1Jb,必有從 b 到 a。Antisymmetric 反對(duì)稱：除非 a=b,有從a到b,必?zé)o從 b到a。Asymmetric不對(duì)稱：有從 a至1Jb,必?zé)o從b到a。Transitive 傳遞：a 至1J b, b 至1J c,貝U有 a 至U c。Combining Relations(復(fù)合關(guān)系):SR(空心圓圈)學(xué)

10、習(xí)必備歡迎下載分配率：并集滿足等價(jià)，交集滿足包含F(xiàn)o(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(表示關(guān)系)? Representing Relations Using MatricesZero-One Mat

11、rixReflexive自反：主對(duì)角線上的數(shù)都為1。Symmetric對(duì)稱：以主對(duì)角線為軸對(duì)稱。? Representing Relations Using Digraphs( 有向圖)Closures of Relations(關(guān)系的閉包)閉包是指在原關(guān)系的基礎(chǔ)上添加最少的有序?qū)?，?gòu)成滿足一種特性的新的關(guān)系。自反閉包、 對(duì)稱閉包和傳遞閉包。Reflexive closure(自反閉包)：在所有元素上加環(huán)。Symmetric closure(對(duì)稱閉包):對(duì)于所有的(a, b),添加(b, a)。Transitive Closure（傳遞閉包）:。：先合取再析取學(xué)習(xí)必備歡迎下載M(R*)=M(R

12、) V (M (R) A M(R) V (M(R) A M(R) A M(R)直到第 n 項(xiàng)*Warshall s Algorithm舍爾算法Equivalence RelationsA relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.等價(jià)=自反+對(duì)稱+傳遞A的全域關(guān)系和恒等關(guān)系都是等價(jià)關(guān)系，空關(guān)系不具自反性。2全域關(guān)系：全部有序偶。2恒等關(guān)系：對(duì)稱且反對(duì)稱，有且只能有環(huán)。Equivalent 等價(jià)量Equivalence Classes 等價(jià)

13、類集合中具有等價(jià)關(guān)系的一個(gè)子集。集合中與一個(gè)元素具有等價(jià)關(guān)系的全部元素構(gòu)成的子集。Partitions 分害口2非空、無(wú)交集、其并集為全集。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 偏序關(guān)系A(chǔ) 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).學(xué)習(xí)必備歡迎下載自反+反對(duì)稱+傳遞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（全序或線序）:沒(méi)兩個(gè)元素都是可比的。這樣的集合又稱作 鏈（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（刪除環(huán)）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 格學(xué)習(xí)必備歡迎下載對(duì)于一個(gè)偏序集 A,若其中任意兩個(gè)元素a、b,都有最大下界和最小上界，則稱這樣的偏序集為格。Topological Sorting 拓?fù)渑判騈ot only one possible order.可能有多種排序方式。Graphs (圖論)9.1 Graphs and Graph

18、 ModelsTypeEdgesMultiple Edges AllowedLoops AllowedSimple graph 簡(jiǎn)單圖UndirectedNoNoMultigraph 多重圖UndirectedYesNoPseudograph 偽圖UndirectedYesYesSimple directed graph 簡(jiǎn)單圖DirectedNoNoDirected multigraph 多重有向圖DirectedYesYesMixed graph 混合圖BothYesYes簡(jiǎn)單圖+多重邊重圖，重圖+環(huán)偽圖Graph ModelsPage 592595Graph Terminology an

19、d Special Types of Graphs(圖論術(shù)語(yǔ)和特殊圖)Adjacent and Incident(連接和關(guān)聯(lián))：一條邊相連的兩點(diǎn)為連接，該邊與這兩點(diǎn)關(guān)聯(lián)。這兩點(diǎn) 稱作端點(diǎn)(endpoints).Degree:度，與一個(gè)點(diǎn)相關(guān)聯(lián)的邊數(shù)，deg(v).Isolated Vertex:孤立點(diǎn)，dev(v)=0.Pendant Vertex:懸掛點(diǎn)，dev(v)=1.學(xué)習(xí)必備歡迎下載The Handshaking Theorem（握手定理）Let G=（V , E） be an undirected graph with e edges. Then 2e= E deg（v）.度數(shù)是邊數(shù)

20、的兩倍。An undirected graph has an even number of vertices of odd degree.奇數(shù)度頂點(diǎn)有偶數(shù)個(gè)。In-degree（入度）:deg-（v）,the number of edges with v as their terminal vertex（ 終點(diǎn)）.Out-degree（出度）:deg+（v）, the number of edges with v as their initial vertex（ 起1點(diǎn)）.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 頂點(diǎn)數(shù)：n,邊數(shù)：n（n+1）/2.Cycles（圈圖）,Cn頂點(diǎn)數(shù)n,邊數(shù)n.Wheels（輪圖）,Wn頂點(diǎn)數(shù)n+1,邊數(shù)2n.Cube（方圖），Qn頂點(diǎn)數(shù)2n,邊數(shù)2n-1*nBipartite Graphs（偶圖，二分圖）可通過(guò)著色法判斷，有邊相連的兩點(diǎn)顏色不同，總共只有兩種顏色。Complete B

22、ipartite Graphs（完全二分圖）New Graphs from OldSubgraph（子圖）?生成子圖Spanning Subgraph:與原圖頂點(diǎn)相同，邊是真子集。?導(dǎo)出子圖：頂點(diǎn)是原圖頂點(diǎn)的子集，而邊為與它們相連的原圖的所有邊。學(xué)習(xí)必備歡迎下載The union of the simple graphs:所有簡(jiǎn)單圖的邊與頂點(diǎn)的并集所得到的簡(jiǎn)單圖。Representing Graphs and Graph Isomorphism（圖的表示與同構(gòu)）Adjacency Lists and Matrices（鄰接表與鄰接矩陣 ）Page 612點(diǎn)與點(diǎn)的關(guān)系對(duì)于有向圖的鄰接矩陣,行數(shù)字

23、相加為該點(diǎn)出度，列數(shù)字相加為該點(diǎn)入度，所有數(shù)字相加為度數(shù)的一半，即邊數(shù)。Incidence Matrices（關(guān)聯(lián)矩陣）點(diǎn)與邊的關(guān)系。Isomorphism of Graphs（圖的同構(gòu)）必要條件：1,相同頂點(diǎn)數(shù)2,相同的邊數(shù)3,對(duì)應(yīng)頂點(diǎn)的度數(shù)相同4,子圖相同5,路徑相同使用矩陣判斷兩圖是否同構(gòu)：?鄰接矩陣：任意交換行列，調(diào)整至兩矩陣相同，即為同構(gòu)。?關(guān)聯(lián)矩陣：行與對(duì)應(yīng)列同時(shí)做相同變動(dòng)，調(diào)整至兩矩陣相同，為同構(gòu)。Connectivity 連通Paths（路徑）一一有向圖路徑和無(wú)向圖路徑Circuit（回路）,Traverse（遍歷）學(xué)習(xí)必備歡迎下載簡(jiǎn)單路徑：每條邊只出現(xiàn)一次。初級(jí)路徑：每個(gè)點(diǎn)只

24、出現(xiàn)一次。Connectedness in Undirected Graphs（無(wú)向圖的連通）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（割點(diǎn)）/cut edge（割邊、或bridge橋）：扔掉它們就會(huì)產(chǎn)生更多連通分支的東西。Connectedness in Directed G

25、raphsStrongly connected強(qiáng)連通路彳仝a至1J b和b至1J a同時(shí)存在。Weakly connected弱連通兩點(diǎn)之間有線存在 （underlying undirected graph看作無(wú)向圖路徑即可）。強(qiáng)連通一定是弱連通。Counting Paths between Vertices使用該圖的鄰接矩陣A,長(zhǎng)度為n,就計(jì)算Ano對(duì)應(yīng)行乘以對(duì)應(yīng)列。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:哈密頓路徑、回路，周游每個(gè)頂點(diǎn)。2 一個(gè)連通重圖具有歐拉回路，當(dāng)且僅當(dāng)它的每個(gè)頂點(diǎn)都是偶數(shù)度。學(xué)習(xí)必備歡迎下載2一個(gè)連通重圖具有歐拉路徑(稱為半歐拉圖)，當(dāng)且僅當(dāng)它有且只有兩個(gè)奇度數(shù)頂點(diǎn)。對(duì)于一個(gè)有向圖而言：歐拉回路的條件：1,每個(gè)頂點(diǎn)都有偶數(shù)度。2,出度等于入度。歐拉路徑的條件：1,僅有兩個(gè)頂點(diǎn)有奇數(shù)度。2,對(duì)于偶度數(shù)頂點(diǎn)，出度等于入度。3,對(duì)于奇數(shù)度頂點(diǎn)，出度和等于入度和。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. 任意兩頂,點(diǎn)度數(shù)之 和不小于總的頂點(diǎn)數(shù)。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、一點(diǎn)的度數(shù)都不小于總頂點(diǎn)數(shù)的一半。必要條件：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（同胚）增加新的點(diǎn)只能是有兩度的點(diǎn)，刪點(diǎn)也只能刪兩度的點(diǎn)。K TheoreiA graph is nonplanar if and only if it contains a subgraph homoeomorphic to K 3,3or K5.學(xué)習(xí)必備歡迎下載Graph ColoringDual Graph對(duì)偶圖：指原圖中的每個(gè)封閉區(qū)域?qū)?yīng)一個(gè)點(diǎn)，每條邊對(duì)應(yīng)一條邊（連接兩頂點(diǎn)，與原來(lái)的邊相交）而形成的新圖。環(huán)對(duì)應(yīng)懸掛邊。同構(gòu)的圖，對(duì)偶圖不一定同構(gòu)。Chromatic Number（色數(shù)）：為一個(gè)圖上色所需的最少顏色數(shù)。The Four Color Theorem : The chromatic number of a planar graph is no greater than four.Trees （樹(shù)）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.（任意兩點(diǎn)之間只有一條通路）A r