discrete-mathematics-note

离散数学保研笔记

命题逻辑的公理系统

命题逻辑主要研究命题的真假值及其组合，通过逻辑连接词构造复杂命题，并利用公理和推理规则进行证明，这就形成了命题逻辑的公理系统。

公理系统满足三条性质，即可靠性，完备性和独立性

三条公理模式

A->(B->A)

(A->(B->C))->((A->B)->(A->C))

(~A->~B)->(B->A)

命题逻辑的三段论

分为假言三段论和选言三段论

A->B,B->C==>A->C

A|B,~B==>A

公理系统的可靠性、完备性和独立性

可靠性：公理系统中的每条定理都是永真式

完备性：通过公理系统能推出一切永真式，即每个永真式都是公理系统的定理

独立性：如果一个公理系统没有多余的公理模式和推理规则。即去掉任何一个公理模式或推理规则，定理都会减少。

数理逻辑表达范式

主合取范式是指如果命题公式A的合取范式中的简单析取式均为极大项，则为主合区范式

主析取范式是指如果命题公式A的析取范式中的简单合取式均为极小项，则为主析区范式

关系的定义

X到Y的关系：若R是XxY的子集，则称R为X到Y的二元关系，简称关系

什么是集合的划分

设A是非空集合，若某个集合是A的幂集的子集，且该集合的各个子集部分并在一起等于完整集合A，且各个子集之间没有交集，各个子集非空，则是A的一个划分

自反，对称，传递，闭包的概念

自反性指的是对于集合中的每个元素 a ，都有 (a, a) 在关系中；即每个元素与自身相关。

对称性表示如果 (a, b) 在关系中，则 (b, a) 也在关系中；即元素之间的关系是相互的。

传递性则意味着如果 (a, b) 和 (b, c) 都在关系中，则 (a, c) 也在关系中；即元素之间的关系能够“传递”。

闭包是指将关系扩展到满足特定性质的最小关系。例如，自反闭包是给定关系的最小自反关系，而传递闭包是使关系满足传递性的最小扩展。

st®是不成立的，即传递闭包的对称闭包不是传递的

偏序、全序、良序关系的定义

集合P上的关系R是偏序关系当且仅当R是自反的、反对称的和传递的，严格偏序是反自反、反对称、传递的

任意两个元素都可以比较的偏序集叫全序关系

对于一个偏序，如果P每个非空自己都有最小元，则是良序关系

每一个良序结构都是全序结构，有穷的全序结构一定是良序结构，无穷的则不一定

等价关系的定义、整除是等价关系吗

等价关系是自反，对称，传递的关系

对于每个A中的x而言，A中有关系R的元素组成的集合称为x关于R的等价类，所有集合中元素等价类组成的集合称为商集

整除关系不满足对称性，因此整除关系不是等价关系

单射、满射和双射的定义

单射是指如果存在f(x1)=f(x2)则x1=x2，满射是指对任意值域里的值y有对应的x满足y=f(x)

若f既满足单射也满足满射，则满足是双射的

集合的递归定义

集合的递归定义是一种通过基础情况（初始集）和递归规则来构建集合的定义方法

笛卡尔积的定义

令A和B是任意两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样的序偶集

合，称为集合A和B的笛卡尔乘积或直积

集合的势

集合的势是指集合中元素的数量。设A和B为二集合，若存在从A到B的双射，则称A和B对等。或称A和B等势

常考问题，证明自然数和有理数等势

欧拉图和哈密顿图的定义

经过每条边一次且仅一次的闭合链叫欧拉图，经过每一个点一次且仅一次的叫哈密顿图

欧拉图判定方式是每个节点都有偶数个度（无向）或每个节点出入度相同（有向）

哈密顿图常用动态规划去寻找解法

可数集的概念

如果该集合可以与自然数集建立双射则是可数集

有穷集的概念

如果该集合可以与某个自然数双射则是有穷集

生成子图和导出子图

生成子图包含原图中所有节点，而导出子图是包含选定点集形成的所有边的子图

简单路径，基本路径

简单路径是边不重复的路径，基本路径是点不重复的路径

强联通、弱连通和单向连通图

强连通图是任意两结点均相互可达

单向连通图是任意两结点至少有一结点到另一结点可达

弱连通图是把有向图看成是无向图是连通的