东北大学离散数学复习总结满分版.docx

第 1 页
方法、知识点总结
〔知识重点与考题重点〕
前三章重点内容〔知识重点〕：
蕴含〔条件〕“→〞的真值
→的真值为假，当且仅当为真，为 假。
重言(永真)蕴涵式证明方法
<>假设前件为真，推出后件也为真。
<>假结点(全是射入的边及之 相连)。(采用抓两头，带中间的方法 )
重要元素定义〔极大小元、最大小元、上下界、最大下界及最小上界〕
如何求映射是入〔单〕、满、双射？
第一步：分别求出定义域与值域
第二步：比拟就出来了，就那么简单
但是要证明的话：
两者结合得：双射成立
复合函数中的重要性质〔常考〕：
→, →是两个函数, 那么
⑴如果与是满射的，那么 。 也是满射的；
⑵如果与是入射的，那么 。 也是入射的；
⑶如果与是双射的，那么 。 也是双射的
⑴如果 。 是满射的，那么是 满射的；
第 9 页
⑵如果。 是入射的，那么 是入射的；
⑶如果 。 是双射的，那么是入射的与是满射的
函数种类个数的求法
逆函数〔性质〕
设→是双射的函数，® 也是函数, 称 之为 的逆函数。
设→是双射的函数，那么有
第六章根底知识重点
幂等元、幺元、零元、逆元的概念
同态同构：()满射、并且满足
*不是双射就一定复合同构的条件：
必须具有 幺元对幺元、零元对零元......
代数系统〔重点〕
半群：封闭、可逆 独异点：有幺元
群：可逆 交换群：可交换
群的特征：.消去律 .无零元 .除幺元外无其他幂等元
运算表中：每个元素在每一行、列必须出现仅出现一次！
第七章根底知识重点
第 10 页
格：<,≤>是偏序集，如果任何∈,使得{}都有最大下界与最小上界，那么称<,≤>是格
平凡格：所有全序都是格，称之为平凡格。
分配格：〔判定定理〕
所有链均为分配格。
设<, ≤>是分配格，对任何∈, 如果有 ∧∧及 ∨∨那么必有 .
有界格：〔判定定理〕
有界格定义：如果一个格存在全上界及全下界，那么 称此格为有界格。
从格的图形看：全上界，就是图的最上边元素(只一个)。 全下界，就是图的最下边元素(只一个)。
有补格：〔判定定理：根据定义看是不是每个中间元素都有补元〕
补元：设<,≤>是个有界格，∈, 如果存在 ∈, 使得∨ ∧ 那么称及互为补元〔其中∨是求最小上界，∧求最大下界〕
有补格的定义：一个有界格中，如果每个元素都有补元，那么称之为有补格
布尔格：如果一个格既是分配格又是有补格，那么称之为布尔格。
*重要定理：
第 11 页
在有界分配格中，如果元素有补元，那么补元 是唯一的。
格的同构条件〔特别〕需同时满足：
钻石定律：
一个布尔代数的所有原子〔直接覆盖最小元的元素〕构成的布尔代数一定及元代数同构
布尔代数表达式与布尔函数
<,∨,∧,¯> 是布尔代数的形式
含有变元 ,… 的布尔 表达式记作(,…),也可以看成是一个函数→, 称之为布尔函数
布尔表达式的范式的写法〔很重要，及第一第二章的方法类似〕
第八章图论的重要知识点〔好多好多的定义自己记吧〕
图的同构：
两个图同构的必要条件:
结点个数相等.
边数相等.
度数一样的结点数相等.
对应的结点的度数相等.
第 12 页
图的连通：强连通、单侧连通与弱连通〔一般不考〕
如果任何两个结点间相互可达, 那么称 是强连通. 如果任何一对结点间, 至少有一个结点到另 一个结点可达, 那么称是单侧连通. 如果将看成无向图后 (即把有向边看成无向边)是连通的,那么称是弱连通
强分图、单侧分图与弱分图
在简单有向图中,具有强连通的最大子图,称为强分图.
具 有单侧连通的最大子图,称为单侧分图.
具有弱连通的最 大子图,称为弱分图.
图的矩阵表示与写法〔前两个有点重要〕：
邻接矩阵
每一行的：在无向图中代表一条线
有向图中代表—>出线
列中的代表<—入线
可达性矩阵
完全关系矩阵
图中结点的度及个数、边的关系：
第 13 页
考试需要两那么结合
欧拉图及〔汉密尔〕图〔重点〕
定义：
在无孤立结点的图中,假设存在一条回路,它 经过图中每条边一次且仅一次,称此回路为欧拉回路. 称此图为欧拉图
汉密尔顿回路(回路):通过中每个结点恰好一次的回 (回路)的图.
欧拉回路的判定：〔充要条件〕
无向图具有欧拉路,当且仅当是连通的,且有零个或两个奇数度的结点.
汉密尔顿图的判定: 〔只有充分条件〕
(充分条件)设是有个结点的简单图,假设中每