离散数学
2021-06-23 01:03:21 80 举报AI智能生成
离散数学基础思维导图
作者其他创作
大纲/内容
6.代数系统的一般概念
代数系统
群与半群
群
半群
环与域
7.格与布尔代数
格的基本概念
分配格与有补格
布尔代数
8.图
无向图和有向图
无向图
端点
边
度
有向图
端点
入度、出度
空图
顶点集为空的图
零图
边集为空的图
平凡图
只有一个顶点没有边的图
通路、回路和图的连通性
通路定义
复杂通路
回路定义
复杂回路
连通定义
连通图
无向图中任意两点都是连通的
图的矩阵表示
无向图的关联矩阵
有向图的关联矩阵
有向图的临接矩阵
有向图的临接矩阵
最短路径、关键路径和着色
9.图的应用
二部图
极大匹配
最大匹配
完美匹配
欧卡图与哈密顿图
欧拉图
有欧拉回路的图
欧拉回路：当且仅当图是连通且每个顶点的入度等于出度
哈密顿图
半欧拉图
有欧拉通路的图
欧拉通路：当且仅当图是连通的且除两个顶点外其余顶点的入度等于出度
平面图
树及其遍历
- 命题和命题公式
命题和命题联结词
命题和命题的表示
命题：具有确切真值的陈述句
命题的表示
复合命题与联结词
简单命题
复合命题
联结词
否定
合取
析取
蕴含（条件）
等价式（双条件式）
命题公式的等值演算
命题公式
公式类型
重言式
矛盾式
满足式
常用命题定律
双重否定定律 A<=> ¬¬A
幂等定律A<=>A∨A,A<=>A∧A
结合定律（A∨B)∨C <=>A∨(B∨C),A∧(B∧C)<=>(A∧B)∧C
交换定律 A∨B<=>B∨A
分配律A∨(B∧C)<=>(A∨B)∧(A∨C),A∧(B∨C)<=>(A∧B)∨(A∧C)
吸收律A∨(A∨B)<=>A, A∧(A∨C)<=>A
德摩尔根定律 ¬(A∨B)<=>¬A∧¬B,¬(A∧B)<=>¬A∨¬B
同一律A∨F<=>A, A∧T<=>A
零律同一律 A∨T<=>T ,A∧F<=>F
排中律A∨¬A<=>T
否定律 A∧¬A<=>F
蕴含等值式 A→B<=>¬A∨B
等价等值式 A↔B<=>(A→B)∧(B→A)
假言易位 A→B<=>A→¬B
等价否定等值式 A↔B<=>¬A↔¬B
归谬论（A→B）∧（A→¬B）<=>¬A
等值运算和蕴含式
两命题公式之间的等值关系
推理定律
化简律 P∧Q+=>P
P∧Q=>Q
附加律P=>(P∨Q)
变形附加律¬P=>P→Q
变形附加律Q=>P→Q
变形简化律¬(P→Q)=>P
变形简化律¬(P→Q)=>¬Q
假言推理 P∧(P→Q)=>Q
拒收式(P→Q)∧¬Q=>¬P
析取三段论（P∨Q）∧¬Q=>P
条件三段论（P→Q）∧（Q→R）=>(P→R)
等价三段论（P→Q）∧（Q→R）=>(P↔R)
合取构造二难（P→Q）∧（R→S）∧(P∧R)=>Q∧S
析取构造二难（P→Q）∧（R→S）∧(P∨R)=>Q∨S
前后件附加P→Q =>(P∨R)→(Q∨R)
前后件附加P→Q =>(P∧R)→(Q∧R)
联结词完备集
S1={¬,∧,∨,→,↔}
S2={¬,∧,∨,→}
S5={¬,→}
最小联结词
S3={¬,∧}
S4={¬，∨}
P↑Q<=>¬(P∧Q)符号↑称为非与联结词
P↓Q<=>¬(P∨Q)符号↓称为非与联结词
2.命题逻辑的推理理论
范式
范式的概念
简单析取式
简单合取式
析取范式
合取范式
范式
小项和大项
小项
大项
主范式
主析取范式
主合取范式
自然推理系统
3.谓词逻辑
谓词的概念与表示
谓词
沦域
特性谓词
量词的合成公式
量词
量词与特性谓词的搭配
项
谓词演算的等价式与蕴含式
前束范式
谓词演算的推理理论
全程量词消去规则∀-
全程量词的引用规则∀+
存在量词的消去规则∃-
存在量词的引入规则∃+
4.集合
集合的基本概念
列举法E={1,2,...,N}
描述法S={x|P(x)}
图示法
集合的运算
交
并
补
差
有序的运算笛卡尔积
有序对
笛卡尔积
5.关系与函数
关系及关系的性质
关系的概念
关系的三种表示方式
表达式
关系矩阵
关系图
关系的性质
反关系
A上的全域关系Ea = A*A
恒等关系lA = {<x,x>|∀x∈A}
∈
小于等于关系LA
整除关系DA
自反关系
实数集上小于关系
幂集上的真包含关系
关系的性质的判断
自反性
反自反性
对称性
反对称性
传递性
关系的运算
并
交
补
差
逆运算R-1 Rc
复合运算 R o S
闭包运算
自反闭包
传递闭包
对称闭包
等价关系与偏序关系
等价关系
如果R是非空集合A上的关系，R是自反的，对称的和传递的，则称R是A上的等价关系
偏序关系
如果R是非空集合A上的关系，R是自反的，反对称的和传递的，则称R是A上的偏序关系
函数
定义
性质
单射
双射
满射
常函数
恒等函数
单调函数
特征函数
0 条评论
下一页
