[离散数学复习提纲.doc

第一章 TRUTH TABLES, LOGIC, AND PROOFS 　命题的概念、命题的真值：T，F 　，析取联结词，蕴含联结词→，等值(双条件)联结词 　　　　永假式，可满足式　　　　　　　…而且…”、“既…又…以”；用于表示条件联结词的“若…则…”，“PQ”表示Q是P的必要条件，P是Q的充分条件。在自然语言表达中，要根据前提和结论的语义来判断条件语句的前件和后件，否则会出现将必要条件当成充分条件，以至于将真命题变成假命题，或将假命题变成真命题。在构造命题公式时，应概念清楚，按命题公式的定义准确书写公式； （2）判断哪些语句是命题？判断给定的公式是否是永真式？关于是否是命题的判定主要根据命题的概念：即能惟一判断其真假的陈述句。简单命题是不能再进一步分解的命题，不含联结词；而复合命题是可以进一步分解的命题，其中至少包含一个联结词。 （3）判断一个公式是否是一个永真式，可以利用真值表法、等价取代和写出其相应的主范式等方法； （4）析（合）取范式的求解方法，一般可采用公式推导（等价取代）的形式，先将公式中的条件和双条件联结词转化掉，化为只含，，～的式子，然后利用德摩根律将“～”放到每个变元的前面，利用结合律、分配律将公式化成析（合）取范式的形式； 而主析（合）取范式的求解则可用：真值表法、公式推导法；或者可从主析（合）取范式直接转换成主合（析）取范式； （5）证明结论有效性（蕴涵式）的方法：真值表法、利用蕴涵式的定义（前件真推出后件也真法、后件假推出前件也假法）、直接证明法、间接证明法（反证法）。 第二章　SET THEORY 　　子集的概念、集合之间的包含、真包含关系 　集合的基数，有限集和无限集，空集，全集 　　基本集合恒等式 　布尔代数及其基本性质 　有序对、集合的笛卡尔积 　关系定义与表示：集合表示法、关系图表示法 　关系的性质：自反性、反自反性、对称性、反对称性和传递性 　关系的运算：并、交、差、对称差、逆关系和合成运算 　等价关系、等价类与划分 　序关系：偏序关系、全序关系和良序关系 　偏序关系的覆盖哈斯图B，BA；二是已知的集合恒等式，即等价取代的方法，对A利用有关的集合恒等式，得到B；或证明A＝C且B＝C，从而A＝B。 （4）A和B的笛卡尔积就是由所有第一个元素属于集合A，第二个元素属于集合B的序偶构成的集合。 （5）二元关系是笛卡尔积的任意一个子集。二元关系有三种表示方法：集合表示法、关系矩阵表示法和关系图表示方法。 （6）二元关系性质（自反性、反自反性、对称性、反对称性、传递性）的判断，取决于关系的表示方式。关系的这五个性质是非常重要且常用的内容，也是解决证明题的关键。对于各种不同性质的证明，一般地，总是这样开始证明的： 自反性：xX,……, （x,x）R，即R是自反的； 反自反性：xX,……, （x,x）R，即R是反自反的； 对称性：x,yX,若（x,y）R……, （y,x）R，即R是对称的； 反对称性：x,yX,若（x,y）R且（y,x）R……, y＝x，即R是反对称的； 传递性：x,y,zX,若（x,y）R且（y,z）R……, （x,z）R，即R是传递的； （7）等价关系和划分、偏序关系、全序关系和良序关系所具有的性质，无非就是上述某些性质的组合； （8）偏序关系与哈斯图LOGIC, INTEGERS, AND PROOFS 　　　　　全称量词全称量词量词量词　　　下取整函数上取整函数　　　图的基本概念：顶点、边、度、无向图、有向图、出度、入度 　关联、端点、邻接顶点、孤立点、自回路 　多图、伪图、简单图、有限图 　Euler握手定理 　子图、生成子图 　无向完全图Kn，完全二部图　通路（回路）、基本通路（基本回路） 　顶点间的可达性、连通性、连通分支 　有向图的强连通、弱连通 　树，叶结点，分支结点 　底图 　二元树 　欧拉图：欧拉路径，欧拉回路 　图的矩阵表示：邻接矩阵 主要知识点、重点和难点： （1）无向图连通性的判断比较容易，但有向图的连通性的判断则比较复杂，要特别注意有向连通图的分类及它们之间的关系：强连通和弱连通； （2）应掌握图中通路、回路的概念及其分类，它们之间的关系； （3）掌握图中顶点的度数与边数的关系（欧拉握手定理）； （4）掌握欧拉通路（回路）是否存在的判断条件，证明给定的图是欧拉图。 第十二章 GRAPHS REVISITED 　补图 　生成子图，割集，割边，割点 　平面图 　欧拉公式，面，deg (f)=2|E| 　哈密尔顿图：哈密尔顿路径，哈密尔顿回路 　赋树图 　Dijkstra算法，最短路径 主要知识点、重点和难点： （1）掌握哈密尔顿通路（回路）是否存在的直观判断条件（充分条件或必要条件），证明给定的图是或不是哈密尔顿图； （2）平面图的