离散数学复习.doc

离散数学复习第1章 数学语言与证明方法1、常用数学符号（了解）2、集合及运算3、证明方法概述（不考）第2章 命题逻辑1、命题判断及符号化（1）简单命题，复合命题，联结词（2）命题的符号化（3）命题公式分类2、命题公式等值演算 （1）熟练掌握24个基本等值式，并能利用基本等值式进行等值演算（2）了解联结词完备集3、范式（1）会求公式的真值表及公式的成真赋值（2）一定掌握公式的主析取/主合取范式的求法，掌握极小项、极大项的性质。4、推理理论 根据推理规则和推理定律会做简单的推理证明。直接证明、附加前提证明、反证法书后习题：2.19 2.20 2.26 2.27 2.33 2.34第3章 一阶逻辑1、会用谓词符号化命题 注意特性谓词的正确使用2、一阶逻辑公式与分类理解对公式的解释的含义；永真式（逻辑有效式）、矛盾式（永假式）、可满足式3、一阶逻辑等值演算 量词消去等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式4、了解一阶逻辑前束范式5、了解一阶逻辑推理的形式结构书后习题：3.10 3.11 3.15第4章 关系1、有序对与笛卡尔集 有序对与笛卡尔集的概念、会求集合的笛卡尔集AB2、二元关系（1）二元关系的定义；会计算集合A上二元关系的数目；掌握集合上的3种基本关系（空关系、全域关系、恒等关系）（2）关系的表示:集合表达式、矩阵、关系图（3）关系的基本运算：了解关系的定义域、值域、域；会求关系的逆和合成（图示法、关系矩阵）。（4）了解关系的幂运算（5）掌握关系的性质（会判断） 自反、反自反、对称、反对称、传递（6）会求关系的自反、对称、传递闭包（7）等价关系 等价关系的定义；等价类的定义和性质，会求等价类；商集的定义 掌握集合上的等价关系和划分之间的对应关系。会根据集合上的划分求出对应的等价关系。（8）偏序关系偏序关系的定义（自反、反对称、传递）常见偏序：整除、包含、小于等于、大于等于会根据偏序关系中的覆盖关系画出哈斯图，并会求最大最小元、极大极小元、上（确）界下（确）界。书后习题：4.1 4.10 4.14 4.18 4.23 4.25 4.27 4.32 4.35 4.36第5章 函数1、掌握函数的定义及性质（1）函数的定义（2）常见函数：常函数、恒等函数、单调函数、自然映射（3）了解函数的像与完全原像（4）会判断函数性质：单射、满射、双射2、函数的运算 掌握函数的复合及求反函数第6章 图1、图的基本概念（1）无向、有向图的定义及基本术语（2）掌握度及握手定理（3）多重图与简单图；无向完全图、正则图、圈图、轮图的基本概念；（4）生成子图、导出子图（5）图的连通性 通路与回路概念；无向图的连通与非连通；点割集与边割集；点连通性和边连通性；有向图的连通性2、图的矩阵表示（1）无向图的关联矩阵；（2）有向图的关联矩阵、邻接矩阵、可达矩阵 掌握通过邻接矩阵求长度为n的通路数和回路数。2、特殊的图（1）了解二部图、欧拉图、哈密顿图、平面图的基本定义。重点是欧拉通路回路；哈密顿通路回路（2）对简单的二部图、欧拉图、哈密顿图、平面图能进行判断书后习题：6.1 6.2 6.3 6.20 6.24 6.38第14章代数系统1、掌握二元运算及性质（1）二元与一元运算定义（2）二元运算性质：交换律、结合律、幂等律、分配律、吸收律、消去律（3）代数常元：单位元、零元、逆元2、代数系统（1）了解代数系统定义（2）了解子代数、积代数系统定义（3）了解代数系统的同态与同构的定义3、典型的代数系统(会判断具体的代数系统是哪一个)（1）掌握半群与独异点的定义与判断（2）熟练掌握群的定义及相关知识子群及生成子群循环群：无限循环群与阶n循环群的定义，会求循环群的生成元及子群置换群中相关概念：要掌握元置换的