《离散数学》重点.pptVIP

《离散数学》重点 黄玉划 抓重点，把握线索 “离散数学”的特点是“散”，内容多，令人目不暇接，让人觉得难以全盘兼顾。但是，如果把握住重点内容，“离散数学”其实是比较简单的。“离散数学”重在对概念的理解。 1 命题逻辑 (5+3个)“联结词”是基础，是重中之重。 “等值”和“推理”的定义是重点。 重要概念：(主)范式。 通过理解联结词的物理含义，从而理解那些重要等值式和推理定律的物理含义，“命题逻辑”这一章就大体掌握了。了解概念：最小联结词组。 联结词与复合命题 2 谓词逻辑 谓词逻辑≈命题逻辑+量词。量词是关键。 “等值演算”和“逻辑推理” 是目标任务。 重要概念: 前束范式。了解概念: 闭式。 在掌握命题逻辑的基础上，理解两个量词的物理含义，从而理解那些重要等值式和推理规则的物理含义，“谓词逻辑”这一章就大体掌握了。 3 集合 重点: 元素与集合的关系, 集合与集合的关系; 集合的运算性质(结合联结词); 容斥原理。 重要概念：幂集P(A) = { x | x?A }；|P(A)| = 2n。 难点：集合与集合的关系证明。 通过理解集合的一些概念，掌握元素与集合的关系、集合与集合的关系；利用文氏图、结合联结词来理解集合中各种运算的物理含义，从而理解集合运算性质的物理含义。 解决证明题的方法一般是“见多识广” 。 4 关系与函数 “关系的性质”是基础，是重中之重。 “等价关系”“偏序关系”的定义是重点。 重要概念：笛卡积，闭包，BA (B上A)。 通过理解“关系”的一些概念，从“定义（表达式）、关系矩阵、关系图”三个方面来理解“关系”的五种性质，从而掌握“等价关系和偏序关系”。了解良序 关系性质判别 5 代数系统性质 “二元运算的性质”对前面两部分进行了总结。 重点：同构 = 同态?双射。 重要概念：积代数。 通过理解双射函数的概念，在理解运算和代数系统一些概念的基础上，理解同态的概念，从而掌握“同构”。 6 典型代数系统 (主要理解3个表) 重点：(1) 域 = 整环?除环； (2) 布尔代数 = 有补分配格 ? 幂集格。 (1)“(半)群、环”是“域”的基础，整环=交换环?含幺环?无零因子环。通过逐步理解“半群、含幺半群、群、交换群、环、整环与除环”这些代数系统的概念，从而掌握“域”。 (2) “格”是“布尔代数”的基础。通过理解“格、分配格、有补格”这些代数系统的概念，从而掌握“布尔代数”。掌握了“域”和“布尔代数”，“典型代数系统”这一章就大体掌握了。 (1) (半)群 (2) 环与域 (3) 格与布尔代数 * * p q ? p p∧q p∨q p?q p?q 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 基本复合命题的真值 如果顶点 xi 连通到xk , 则从 xi到 xk 有边 如果两点之间有边, 是一条有向边(无双向边) 如果两个顶点之间有边, 是一对方向相反的边(无单边) 每个顶点都没有环 每个顶点都有 环 关系图 对M2中1所在位置, M中相应位置都是1 若rij＝1, 且 i≠j, 则rji＝0 矩阵是对称矩阵 主对角线元素全是0 主对角线元素 全是1 关系 矩阵 R?R?R R∩R?1? IA R=R?1 R∩IA=? IA?R 表达式 传递 反对称 对称 反自反 自反  恒等关系IA既是等价关系, 又是篇序关系。 |S|≥2 × √ √ √ √ √ √ Abel群 × √ √ √ √ √ 群 √ √ √ 独异点 √ √ 半群 √ 代数 系统 含 零 消去 律 交换 律 所有元素 有逆元 含 幺 结合 律 封闭 性 S, o 重要概念：循环群，n元置换群。 √ √(θ除外) * √ * 无零 因子 环 除 环 √ *是 独异点 含 幺 环 √ *是交 换半群 交 换 环 整 环 域 √ √ √ √ +是 Abel群 √ *是半群 环 |S| ≥2 消去 律 分配 律 交换 律 所有元素 有逆元 含 幺 S, +, * n为素数?Zn