当前位置:
文档之家› 离散数学总复习,西工大离散复习
离散数学总复习,西工大离散复习
31
The End
• 好好复习,考出好成绩! • 感谢大家一个学期的配合及努力 • 同学们辛苦了~ • PS:欢迎大家在四年后报考我的 研究生
32
14
函数的重点
• 单射函数、满射函数、双射函数的判断 • 函数的运算(合成、逆运算等) • f诱导的等价关系,规范映射
15
第六章 代数
知识点
• 代数系统、子代数系统的概念:封闭性; • 特殊的元素:幺元、零元、逆元、等幂元的识别(P172) • 主要的代数系统:广群、半群、独异点、群、子群;代数系 统之间的关系; • 置换群和循环群的定义(P202)
18
第八章 图论
知识点
1.图的基本概念、结点度数与边数的关系公式;
2. 路径、回路、通路、连通图与非连通图、强连通图与弱 连通图、有向图与无向图;强分图、点割集、边割集; 3. 赋权图的最短路径的计算。 4. 欧拉路、欧拉回路、欧拉图;哈密尔顿路、哈密尔顿回路、 哈密尔顿图; 5. 赋权图的最短哈密尔顿回路的(近似)计算-最邻近算法
第一章 数理逻辑-命题逻辑
知识点
1.命题的概念、表示方法 => 会将命题符号化
2. 联结词的逻辑意义 (含义及真值表定义).
3.命题公式的递归定义=> 会用真值表计算命题公式 4.真值表的构造、命题公式等价的概念(P6)。 5.重言式与蕴涵式的定义、逻辑意义(P8), 逻辑等价与逻辑蕴涵的意义和证明方法(P12)。 常用的逻辑等价公式和逻辑蕴涵公式(E和I)。
13
第四章 函数
知识点
1.函数的概念,定义域、值域、定义域与前域的 关系、值域与陪域的关系
2. 函数的类型:单射函数、满射函数、双射函数, 会判断,会证明(P140)
3.复合函数、逆函数的概念,复合函数与关系复合 的联系与区别,逆函数与逆关系的联系与区别。 合 成 函 数 fg 满 射 、 单 射 、 双 射 , f,g 分 别 是?(P141) 4. f诱导的等价关系,规范映射的定义 5. 置换的定义,置换的合成运算
4
命题逻辑重点
• 主析(合)取范式求取方法 • 命题逻辑推理方法: 直接证明方法 间接证明方法 反证法(逆反证明法) CP规则 归谬法
5
第一章 数理逻辑-谓词逻辑
知识点
1.谓词与量词的概念与表示方法(P35) 2.谓词逻辑的合式公式与自然语言的翻译(P36-37) 3.谓词中变元约束(P38) 4.谓词逻辑的等价式和蕴含式(P43) 带量词的公式在论域内展开式,量词否定,量词辖 域扩充, 量词分配公式. 5.推理理论(P49),参看下页
• 陪集、拉格朗日定理,与有限群相关的数量结果(P208)
• 正规子群,正规子群的陪集(G的同余类)(P210)
• 同态 /同构映射与同态 /同构(代数系统、半群、独异点、群)
• 同余关系(P183)
• 群同态诱导的等价关系是同余关系,核K是正规子群(P211)
16
第六章 代数—群
17
代数重点
• 代数结构中特殊元素的识别 • 半群、含幺半群、群、子群的证明方法 • 同态相关的证明
– – – – 极小元、极大元 最小元、最大元 上界、下界 上确界、下确界
6. 集合的等价关系与等价类,R诱导的等价关系(P123) 7. 集合的划分与覆盖,划分的大小与等价关系的大小(P127)
11
第三章 二元关系
关系的重点
• • • • 偏序集的特殊元素(极小元、极大元等) 关系的性质的证明与判别(P94) 关系闭包的计算,R诱导的等价关系(P124) 划分与等价关系(A/R)、划分是等价关 系的证明(P125)
3
第一章 数理逻辑-命题逻辑
知识点(续)
6.命题公式的对偶式(P12)、合取范式、析取范式、 主合取范式、主析取范式。逻辑小项、逻辑大项。 任给公式化为析取范式、任给公式化为主析取范 式、任给公式化为合取范式、任给公式化为主合 取范式(P16-P20)。
7.命题逻辑的证明:真值表、推理理论
常用推理规则:P规则、T规则(P26)。
19
图论重点
赋权图的最短路径的计算 哈密尔顿最短回路的计算 欧拉图、哈密尔顿图的判定 利用m=2n计算边与点的个数
20
考试题目主要来源
• 《离散数学》课本
– 作业题目 – 例题、定理
• 其他
29
题形
• • • • 选择 填空 计算 证明
30
考试时间、地点
• 时间:2012年1月4日-1月10日 • 地点:???
• 教学内容: 数理逻辑 集合 二元关系
函数 代数 图论
1
复 习 时 注 意
准确掌握每个概念 灵活应用所学定理 注意解题思路清晰(细节推不出来时,别 忘了写解题思路) 证明问题时,先用反向思维(从结论入手)分 析问题,再按正向思维写出证明过程. 如果是后面几章的证明,一般从定义入手。
2பைடு நூலகம்
9
集合的重点
• 集合相等、包含等关系的证明 • 幂集 • 归纳法的应用
10
第三章 二元关系
知识点
1. 关系的概念、表示方法 :关系矩阵、关系图(P93); 2.关系的特性:自反、对称、传递(P94),关系闭包 (P106) 3.关系的运算:合成关系、逆关系、闭包运算(P106); 合成关系的矩阵表示 4.次序关系(偏序、拟序(反自反)、线序、良序)、偏序集、 哈斯图(P112)。 5. 偏序集中特殊的元素(P113)
6
谓词逻辑的推理方法
• 规则:US、UG、ES、EG、命题逻辑的规则 • 可使用的公式表:命题逻辑的等价式、蕴含式; 谓词逻辑的常用等价式和蕴含式; • 推理方法: 同命题逻辑
7
谓词逻辑重点
• 自然语言的形式化(注意量词如何 加入和论述域) • 谓词逻辑推理方法
8
第二章 集合
知识点
1. 集合的基本概念与表示方法,全集与空集 2. 集合的运算:交并补差、环和(对称差)、环积、幂 集 3. 集合的三种关系(包含,相等,真包含)的定义及证明. 4. 归纳法的证明方法 5. 序偶与笛卡尔积;