离散数学及其应用重要名词中英对应以及重要概念解释与举例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.（真值表相同的式子，p<->q是重言式）Logical Equivalences——Page24Disjunctive normal form(DNF，析取范式)Conjunctive normal form(CNF，合取范式) 见Page27～291.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、13"x"yP(x,y) Û "y "x P(x,y)$x $yP(x,y) Û $y$xP(x,y)"x"yP(x,y) Þ $y"xP(x,y)"y"xP(x,y) Þ $x"yP(x,y)$x"yP(x,y) Þ "y$xP(x,y)$y"xP(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(推理规则)V alid Arguments in Propositionnal Logic(命题逻辑中的正确论点)Premises(前提)——all but the final proposition in the argumentConclusion(结论)R ules of Inference for Propositionnal LogicPage 66～67，证明方法及过程示范Resolution(归结): ((p∨q) ∧(┐p ∨r)) →(q ∨r) 合取，若两子句有互补文字，则可消去。
Fallacies(谬论)R ules 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:笛卡尔积、直积，A×B={(a,b)|a∈A∧b∈B}FunctionOnto:满射Injective=One-to-One：单射Bijection：双射=单射加满射3～7 略8 Relations（关系）8.1 relations and Their PropertiesReflecxive自反：if (a, a)∈R for every element a∈A 都有环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(复合关系)：S·R(空心圆圈)分配率：并集满足等价，交集满足包含(1) Fo(GÈH)= FoG È FoH(2) Fo(GÇH)Í FoGÇ FoH(3) (GÈH) oF = (GoF ) È (HoF)(4) (GÇH) oFÍ GoFÇ HoFR n + 1= R n oRThe relation R on a set A is transitive if and only if R n属于R for n=1,2,3……8.2 n-ary Relations and Their Applications8.3 Representing Relations(表示关系)Ø Representing Relations Using Matrices——Zero-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项*Warshall’s 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, i∈I, 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(全序或线序)：没两个元素都是可比的。