中科院计算机专业各科考试要点（1）
《离散数学》考试要点以下是偶整理的《离散数学》考查要点，
希望对大家的复习备考有所帮助。
参考书：《离散数学》左孝凌等编著，上海科学技术文献出版社出版
数理逻辑
考查要点：公式推演，谓词演算，符号化推理。
第一章：命题逻辑
符号化命题，命题定律;
重言式、蕴含式及其性质;
主合取范式、主析取范式，二者的关系(必考题，一般运算较繁，应力求熟练);
推理理论，基本蕴含式和等价式(p43);
1-9节略过。
第二章：谓词逻辑
基本概念;
用谓词公式符号化命题;
了解变元的约束;
谓词演算的等价式与蕴含式，
熟悉表2-5.1中的等价式和蕴含式，理解p70页的例子;
了解前束范式;
谓词演算的推理理论，熟悉基本规则，
注意存在量词和全称量词的消去顺序，
关于UG规则的使用，请参考往年试题中方法。
集合论
考查要点：基本概念;关系及其性质，等价关系与等价类，序关系。
第三章：集合与关系
集合运算;
关系、关系矩阵、关系图;
关系的性质;
复合关系、逆关系，复合关系矩阵的构造;
了解关系的闭包运算，Warshall算法;
划分与覆盖的概念;
等价关系、等价类，商集，相关性质;(重点)
命题：集合A上的等价关系个数，等于A的划分种数;(常用于辅助计算)
了解相容关系、相容类、最大相容类;
偏序关系、偏序集，哈斯图;
链和反链的概念;
了解全序集合、全序关系;
了解概念极大元、极小元，最大元、最小元，上确界、下确界;
了解良序集。
第四章：函数
函数概念，函数相等;
满射(即到上映射);
入射(即单射、一对一映射);
双射(即一一对应);
其它略过。
代数系统
考查要点：运算及性质，群理论，拉格朗日定理及推论。
第五章：代数结构
运算及性质，运算表;
群，有限群的阶，群中元素的幂;
群的几个定理;
子群，交换群，循环群;
命题：循环群中，若a为生成元，则a的逆元也是生成元;
生成元阶与有限循环群的阶的关系;
5-6节略过;
陪集与拉格朗日定理，定理推论;
了解同态与同构中的几个概念;
5-9节略过。
第六章：格和布尔代数
格与子格的概念，对偶原理;
格的基本性质;
分配格及其性质;
略过模格;
有补格一节中的概念;
布尔代数;
原子;
Stone表示定理及推论;
了解布尔表达式。
考查要点：图论基本概念，性质。
第七章：图论
基本概念;
完全图的性质，补图，图的同构;
补充：鸽巢原理;
路与回路;
连通分支和连通图;
点/边割集，连通度;
有向图的可达性;
单侧连通、强连通、弱连通;
强分图、弱分图、单侧分图;
邻接矩阵、可达性矩阵、完全关联矩阵;
Warshall算法;
了解关联矩阵的秩;