《离散数学》PPT课件 常州工学院 何中胜

 
课件内容： 
命题逻辑 
（1）掌握命题、命题联结词的概念，理解命题公式的递归定义，熟练掌握命题符号化的方法，掌握命题公式真值表的求法。（2） 熟练掌握运用常用等价式进行等值演算的过程，掌握蕴含式的证明方法。（3）了解范式的概念，掌握求命题公式的析取范式、合取范式和主范式的方法。（4）掌握常用的推理规则和证明方法。 
（1）命题及联结词 
（2）命题公式及类型 
（3）等价式与蕴含式 
（4）范式与对偶式 
（5）推理规则与证明方法 
谓词逻辑 
（1）理解谓词、量词、谓词公式、自由变元和约束变元的概念（2）掌握谓词公式在给定解释下的真值计算（3）掌握谓词演算基本的等价式与蕴含式（4）会计算谓词公式的前束范式（5）会利用谓词演算的推理规则进行简单的推理 
（1）谓词与量词 
（2）谓词公式及其解释 
（3）谓词公式的等价与蕴含 
（4）谓词公式的前束范式 
（5）谓词演算的推理规则 
集合与关系 
（1）理解集合的基本概念及表示法，掌握集合的交、并、差和补等概念及交律、合律、分配律和 De Morgan 律等运算律，证明集合等式。（2）掌集合的笛卡尔乘积的运算（3）理解关系及有关概念，掌握关系图、关系矩阵及关系的特性（自反性、反自反性、对称性、反对称性和传递性）（4）掌握关系的复合、关系的逆及其有关性质（5）了解关系的闭包运算（自反闭包、对称闭包和传进闭包）的性质及求法。（6）掌握偏序集合及特殊元素的概念及性质。（7）理解等价关系、覆盖及划分的概念，掌握求集合的等价类方法。 
（1）集合概念与基本运算 
（2）集合的笛卡尔乘积 
（3）关系的概念与表示 
（4）关系的运算与性质 
（5）等价关系与偏序关系 
函数 
（1）理解函数的基本概念（2）会判断和证明函数的单射、满射、双射的性质（3）了解从 A 到 B 的双射函数构造方法；（4）掌握复合函数、双射函数的反函数计算。 
（1）函数的概念与性质 
（2）函数的复合与新型逆函数 
（3）函数的类型与集合的基数 
代数系统 
（1）理解运算与函数间的联系与区别（2）掌握判断和证明二元运算的性质（3）掌握关于给定运算下的特殊元计算（单位元、零元，逆元、等幂元）；（4）理解各个典型二元代数系统之间的联系。 
（1）运算的概念与代数系统的定义 
（2）二元运算的性质及特殊元 
（3）典型代数系统的概述（半群、独异点、群） 
（4）元素的阶与生成元 
图论 
（1）了解无向图与有向图的定义、结点的度数等概念；理解零图、平凡图、简单图、完全图、正则图、子图、补图、图的同构等概念；熟练掌握握手定理及应用（2）理解通路与回路、简单通路、简单回路、基本通路、基本回路、无向图结点间的连通、有向图结点间的可达及距离等概念；（3）熟练掌握利用邻接矩阵求结点间长度为 k 的通路数、回路数以及长度为 k 的通路数、回路数的方法（4）理解欧拉通路、回路及欧拉图的概念，熟练掌握欧拉图的判别方法（5）理解汉密尔顿通路、回路及汉密尔顿图的概念，会判断某些图是或不是汉密尔顿图（6）理解平面图的概念与性质，熟练掌握欧拉公式及其推论（7）理解树、生成树、有向树、根树、最优树的概念（8）掌握最小生成树构造算法、最优树的 Huffman 算法、前缀码的求法 
（1）图的概念及表示、有向图、无向图、度，图同构，子图、补图 
（2）路与回路的概念及性质 
（3）图的连通性，点割集与割点，边割集与割边 
（4）图的矩阵表示及计算 
（5）欧拉图与汉密尔顿图念、性质、判定 
（6）平面图的概念、性质、判定 
（7）对偶图及着色的概念 
(8）树的定义及性质 
（9）生成树与最小生成树的概念与求解算法（Kruskal 算法） 
（10）根树的概念及性质 
（11）最优树的概念与求解算法（Huffman 算法） 
（12）最优树的应用（前缀码的求法）