离散数学复习提纲.pdf

《离散数学》复习提纲 第一章命题逻辑■命题符号化及联结词■命题公式及分类■等值演算会运用等值式(P9) 证明两个公式是否相等、判断公式的类型(P33:7-9) ■对偶与范式求命题公式的( 主) 析取范式及用途、( 主) 合取范式(P33 : 12 , 13) 第一章命题逻辑■联结词全功能集复合联结词、 N 个命题变项可构成的不等价的命题公式数■推理理论推理的形式结构、常用推理规则(P23) 构造证明法(直接证明法、附加前提证明法、反证法) (P34-35 : 18,19) ■本章的应用 P11 例 11 , P27 例 28 ,P34 : 15 第二章一阶逻辑■一阶逻辑基本概念、命题符号化■一阶逻辑公式、解释及分类公式的解释、代换实例(P53-54 : 5 , 13) ■一阶逻辑等值式、前束范式量词否定等值式( P46 ) 量词辖域收缩和扩张等值式(P47) 量词分配等值式(P47) 第二章一阶逻辑■一阶逻辑推理理论有关量词的推理规则(EI,EG,UI,UG ) 及运用■本章应用例: 证明: “金属都是导电体, 铜是金属,所以铜是导电体。”解: 令 F ( x ): x 是金属, G ( x ): x 是导电体, a : 铜前提: ? x ( F ( x ) → G ( x )) , F ( a ) 结论: G ( a ) 证明: ① F ( a) 前提引入②? x ( F ( x ) → G ( x)) 前提引入③ F ( a ) → G ( a) ② UI ④ G ( a) ①③假言推理涉及到?命题的符号表示?有关量词的推理规则?量词的等值式第三章集合的基本概念和运算■集合的基本概念集合之间的关系、?、 E 、幂集,文氏图■集合的基本运算会运用集合运算算律(P60-61) 证明有关集合运算的命题成立与否、进行化简■集合中元素的计数( 本章应用) 包含排斥原理( P63 例 9 , 10 ,P65-67 例11-13 ) 第四章二元关系与函数■集合的笛卡儿积与二元关系会计算和运用笛卡儿积的性质(P83) 证明命题成立与否重要关系( ?、 E 、 I 、 L 、 D 、?) ■关系的运算 dom 、 ran 、fld , R -1 和合成 R ° S 、关系上的幂运算■关系的性质( 判断、证明) 自反性、反自反性、对称性、反对称性、传递性关系运算与性质的关系(P87) 、关系性质的充要条件■关系的闭包对称闭包、自反闭包和传递闭包的定义和构造方法第四章二元关系与函数■等价关系和偏序关系等价类,商集、划分及其关系哈斯图,偏序集的特定元素及性质■函数的定义和性质满射、单射、双射的性质、判断双射函数的构造■函数的复合和反函数函数复合运算及性质,反函数的计算■本章应用等价类及划分, 构造双射函数第五章图的基本概念■无向图及有向图握手定理、推论及应用图的同构条件及判断完全图、正则图、生成子图、自补图■通路、回路、图的连通性无向图和有向图的连通性,点割集、边割集■图的矩阵表示关联矩阵、邻接矩阵及性质会计算图中指定长度的通路和回路的个数(P126) ■最短路径和关键路径(本章应用) P129 例 3 ,P130 例 4 ,P138 : 19 , 20 第六章特殊的图■二部图——完全二部图、匹配、 Hall 定理及应用。■欧拉图——( 半) 欧拉图的定义及判别方法。■哈密顿图( 半) 哈密顿图的定义及存在性的充分条件和必要条件。■平面图平面图的面、次数及它们之间的关系极大平面图、极小非平面图欧拉公式及推广( 定理 , ) 平面图判定定理( 定理 , ) 对偶图的构造和性质■本章应用二部图(P154:5 ) ,哈密顿回路(P154:15), 平面图