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