离散数学复习.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、有序对与笛卡尔集
有序对与笛卡尔集的概念、会求集合的笛卡尔集A×B
2、二元关系
（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循环群的定义，会求循环群的生成元及子群
③置换群中相关概念：要掌握元置换的概念；书上关于此知识点的例题14.23要理解掌握。
（3）了解环与域的相关概念
（4）格的定义及判断
书后习题：14.12 14.22 14.30 14.32 14.33