Java教程

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

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

双重否定 ㄱ(ㄱ(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的同胚子图

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