[学习/自用]离散数学期末复习笔记

本文主要是介绍[学习/自用]离散数学期末复习笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

双重否定 ㄱ(ㄱ(p))⇔p
幂等 p ∧/∨ p ⇔ p
交换 p ∧/∨ q ⇔ q ∧/∨ p
分配 p ∧/∨ (s ∨/∧ t) ⇔ p ∧/∨ s ∨/∧ p ∧/∨ t
结合 r ∧/∨ s ∧/∨ t ⇔ (r ∧/∨ s) ∧/∨ t
吸收 p ∧/∨ (q ∨/∧ p) ⇔ p(里面的符号和外面相反)
德摩根 ㄱ (p ∧/∨ q) ⇔ ㄱ p ∨/∧ ㄱ q
零 p ∨ 1 ⇔ 1, q ∧ 0 ⇔ 0
同一 p ∧ 1 ⇔ p, q ∨ 0 ⇔ q(和零律区别关键在于结果)
排中 p ∨ ㄱ p ⇔ 1 （析取）
矛盾 p ∧ ㄱ p ⇔ 0（合取）
蕴含等值 p → q ⇔ ㄱ p ∨ q
等价等值 p ↔ q ⇔( p → q )∧( q → p )
假言易位 p → q ⇔ ㄱ q → ㄱ p (即充分/必要的转换)
等价否定等值 p ↔ q ⇔ ㄱ p ↔ ㄱ q
归谬 (p → q)∧(p → ㄱ q) ⇔ ㄱ p
附加 A⇒A∨B
化简 A∧B⇒A/B
假言推理 (A→B)∧A⇒B
拒取式 (A→B)∧┐B⇒┐A
析取三段论 (A∨B)∧┐B⇒A
假言三段论 (A→B)∧(B→C)⇒(A→C)
等价三段论 (A↔B)∧(B↔C)⇒(A↔C)
构造性二难 (A→B)∧(C→D)∧(A∨C)⇒(B∨D)
构造性二难 (A→B)∧(┐A→B)∧(A∨┐A)⇒B
破坏性二难 (A→B)∧(C→D)∧(┐B∨┐D)⇒(┐A∨┐C)
求范式：①消去箭头②移动否定③进行分配
10.
子群判定：
定理一：封闭(ab)逆元(a-1)
定理二：ab-1
定理三：H有穷并且ab
循环群：由元素a的k次幂生成的群
小于6阶的群都是循环群
无限循环群的生成元：a和a的逆
有限：φ(n): n的质因数个数，例如φ(12)=4 (1/5/7/11)，生成元为a的r次幂，r为fact(n)
环：<S,+,x>, ①S+交换群, ②Sx半群, ③x对+分配
交换环/含幺环：对乘法而言
无零因子环：无零因子
整环：交换&含幺&无零因子
域：除0外都含逆元的整环
环的直积：有序对的每个元素自然运算,例如<ac,bd>
整环的直积不一定是整环
左右陪集数：[G:H]
11.
格：偏序集内任意两个元素都有最小上界和最大下界（第一定义）
符号说明：（也同时是运算）
∧最大下界（和符号指向相反）
∨最小上界（同上）
这两个运算满足交换/结合/幂等/吸收
对偶式/对偶原理（类比于代数系统/集合）将≥和≤替换，∧∨替换，真假不变。
格：<S,+,x>中+x满足交换/结合/吸收
分配格：∨∧满足分配律（普通格满足分配不等式）（就是等于关系）
L是分配格当且仅当L的子格没有五角格、钻石格（含同构）

有界格：存在全上界（记作1）和全下界（记作0）（即任意....)
补元：a∧b=0或者a∨b=1，b是a的补元。补元若存在即唯一。
有补格：所有元都存在补元
布尔代数：有补&分配格（证法：证两个性质或者证交换/分配/同一/补元）
任何有限布尔代数基数为2的幂次
等势有限布尔代数同构
12.13.组合数学
14.
（图的概念太多，懒得写了）
生成子图：子图的顶点集和母图相同，边不同
握手定理：（主要记推论）奇度定点个数为偶数
可图化条件：度数列之和为偶数
可简单图化：最大度数Δ≤n-1（n是阶数）
同构：不断线变换可以变成一个图
竞赛图：基图为完全图
割集：去掉任意几个边/点后连通分支数增加，少去掉一个连通分支数不变（可以考虑孤立点情况）
连通度：产生一个不连通图所要删去的点的最少数目
二部图：将G中所有顶点的两端各归属到两个顶点集中，记作Kr,s r,s是两个集合的基数（元素个数）
割点：如果去掉一个点以及与它连接的边，该点原来所在的图被分成两部分（不连通），则称该点为割点。
割边：如果去掉一条边，该边原来所在的图被分成两部分（不连通），则称该点为割边，又叫做桥。
k阶正则图：每个顶点的阶数都为k
15.
欧拉回路：一笔走完全部顶点和边，不重复，回路
欧拉图：具有欧拉回路；半欧拉图：只有欧拉通路
欧拉图判定：无奇度顶点&连通
半欧拉图：有且仅有两个奇度定点&连通
哈密顿图，一笔走完全部顶点
哈密顿图存在充分条件：n阶简单完全图，不相邻顶点度和≥n-1（构成通路）n（构成回路）
哈密顿图点子图V1: p(G-V1)≤|V1|
dijkstra算法：局部最右获得全局最优，一直找最小的最后就是最小的。
16.
树：无回路（n阶m条边时m=n-1)
树上的树枝：就是树的边
树上的弦：原图有的边树上没有
n阶m边无向树等价定义：
(1) G 是树。
(2) G 中任意两个顶点之间存在唯一的路径。
(3) G 中无回路且 m＝n-1。
(4) G 是连通的且 m＝n-1。
(5) G 是连通的且 G 中任何边均为桥。
(6) G 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。
破圈法：删掉圈的一个边，有圈继续删
基本回路：把弦连上能在树上构造一个圈
圈秩：ξ=m-n+1
18.
平面图：边不相交
面Ri的次数：面（用回路划分的区域）的边界个数，其和为边数之和的二倍
极大平面图：不能再往里加边
欧拉定理：连通平面图的顶点数V，边数E，面数S满足V-E+S=2
欧拉定理推论：每个面次数至少为L,V,E满足：E(L-2)≤L(V-2)
定理：n阶E边简单平面图：E≤3n-6（ps：提醒，所谓阶数就是顶点集个数）
简单平面图的最小度≤5
同胚：①同构②反复插入、消除2度定点仍同构
平面图⇔不含K5,K33的同胚子图


这篇关于[学习/自用]离散数学期末复习笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！