注：本文以陈莉、刘晓霞编著的《离散数学》(第三版) 这本书为教材。

速通

第一章 命题逻辑

命题逻辑注重 演算+推理（详见1.8）

异或、当且仅当

a⊕b <=> (¬a ∧ b) ∨ (a ∧¬b)

9种联结词

第一章下面有详细介绍

真值表

会画就行，下面有例子

已知 主析取范式 求 主合取范式

求主析取范式：

1. 列真值表
2. 找出真值为 T 的项用 m_n 表示并 V 起来

求主合取范式：
可以将主析取范式里没有的项用M_n表示然后∧起来

第五章 关系

等价关系

设R是集合X中的二元关系，若R是自反的、对称的、传递的，则R是等价关系。
在5.3

偏序关系

设R是集合X的二元关系，如果R是自反的、反对称的和可传递的，则称R是X中的偏序关系，通常用符号“≤”记偏序关系R。
在5.6

第八章 代数系统

同态概念、证明同态
同余关系

代数系统 概念

幺元

若 e∈U, ∀x∈U,
有 e*x=x(此时e为左幺元)
还有 x*e=x(此时e为右幺元)
则 e为幺元

逆元

若 ∃x^-1∈U
使 x^-1 * x = e(此时x^-1为左逆元)
还使 x * x^-1 = e(此时x^-1为右逆元)
则 x^-1 为逆元

代数系统

非空集合A和若干运算f_n组成的U
U = <A,f₁, f₂ ……>

代数系统的 同态

代数系统的 同余关系

代数系统的 商代数

第九章 半群与群

半群

群

有逆元、含幺元、满足结合律

子群

第十章 环与域

环

子环

环的同态

第十一章 格与布尔代数

偏序(书151页) ：自反、反对称、可传递

用偏序集定义的格

用代数系统定义的格

第十二章 图的基本概念

度和顶点

有向图中
任意顶点v，以v为起点的边的条数称为v的出度
任意顶点v，以v为终点的边的条数称为v的入度
v的出度与入度之和为度（PS:个人理解就是这个点连了几条边）

度为奇数的顶点为奇顶点，为偶数则偶顶点。

图

G=<点,边,映射>

G = <V, E, φ>称为无（有）向图

1. V是一个非空有限集合，它的元素称为顶点或者结点。
2. E是一个与V不相交的有限集合，它的元素称为无（有）向边。
3. φ: E->V&V (E->VxV) 是映射

子图

简单图

不含自环和重边的图称为简单图

完全图

每对顶点之间都有一条无向边的简单图，称为无向完全图
每对顶点之间都有一对方向相反的有向边的简单图，称为有向完全图

路径与循环

第十三章 欧拉图与哈密顿图

欧拉图与哈密顿图的判定

欧拉图

哈密顿图

第十四章 树、二分图与平面图

树

无向树：不含 基本循环(书297页) 的无向连通图
有向树：无向树的边带箭头就成有向树了

生成树

避圈法、破圈法

最优树

二分图

偶循环长度就是二分图
(PS:好像点能分成上下两部分，每条边分别连一个上面的点和一个下面的点，但不是连在同一面的点)
下图(a)是无向二分图，(b)是无向完全二分图

平面图

可嵌入平面 —> 可平面图 --无相交边–> 平面图

欧拉公式

设G是含n个顶点、m条边和k个面的连通平面图
则有 n-m+k=2

第一章 命题逻辑

1.1命题及联结词

1.命题的概念

所谓命题，就是指具有真假意义的陈述句，且真或假二者必居其一，也只居其一。约定用大写英文字母表示命题。

2.命题的真值及命题的表示

命题是能够分辨真假的陈述句，把命题的“真”或“假”称为命题的 “真值”，分别用T(True)和F(False)表示。

3.联结词

下面介绍常用的五种联结词：

(1)合取 联结词(∧)

合取联结词，记作"∧"，也称为“与”。

(2)析取 联结词(V)

析取联结词，记作“V”，也称为“或”。

(3)否定 联结词(¬)

否定联结词，记作“¬”，也称为“非”。

(4)如果则 联结词(→)

也可称为条件联结词。将P和Q联结起来，记作“P→Q”，读作“如果P，则Q”。

(5)当且仅当 联结词(↔)

由真值表可知，当且仅当P和Q真值相同，“P↔Q”的真值才是T。双条件联结词也称为同或。

1.2命题公式及命题公式的翻译

1.命题变元

前面我们约定用大写英文字母表示命题，如果用P表示一个抽象的命题，而不是一个具体的命题时，就称它为命题变元。
由于命题变元可以表示任何命题，故其真值无法确定。

2.命题公式

若A和B是命题变元，则其为命题公式，那么(A∧B)、(AVB)、(A→B)、(A↔B)都是命题公式，且为二元命题公式。由此可以推广出三元…n元命题公式的定义。

3.命题公式的符号化

例1.2.1：(1)他既聪明又用功 (2)他虽然聪明但不用功
解    P：他聪明。 Q：他用功。
		则有：(1) P∧Q  (2) P∧¬Q

1.3公式的等价性

若对命题公式A和B，所有真值组合都相同，则称公式A等价于公式B，记作A⇔B
例如：B→A与¬A→¬B，列出其真值表

A	B	B→A	¬A→¬B
T	T	T	T
T	F	T	T
F	T	F	F
F	F	T	T

可以看到他们在任意A与B的真值组合中，得到的真值都是相同的，则B→A与¬A→¬B是等价的。

基本等价公式

公式	名称
¬¬P⇔P	双重否定律
PVP⇔P, P∧P⇔P	等幂律
(PVQ)VR ⇔ PV(QVR)
(P∧Q)∧R ⇔ P∧(Q∧R)	结合律
PVQ ⇔ QVP, P∧Q ⇔ Q∧P	交换律
PV(Q∧R) ⇔ (PVQ)∧(PVR)
P∧(QVR) ⇔ (P∧Q)V(P∧R)	分配律
PV(P∧Q) ⇔ P
P∧(PVQ) ⇔ P	吸收律
¬(PVQ) ⇔ ¬P∧¬Q
¬(P∧Q) ⇔ ¬PV¬Q	德·摩根律
PVF ⇔ P, P∧T ⇔ P	同一律
PVT ⇔ T, P∧F ⇔ F	零律
PV¬P ⇔ T, P∧¬P ⇔ F	补余律

1.4蕴含式

当且仅当A→B是一个永真式时，称A蕴含B，记作A⇒B。

基本蕴含公式

公式	名称
P∧Q ⇒ P, P∧Q ⇒ Q	化简式
P ⇒ PVQ, Q ⇒ PVQ	附加式
¬P ⇒ P→Q
Q ⇒ P→Q
¬(P→Q) ⇒ P
¬(P→Q) ⇒ ¬Q
P∧(P→Q) ⇒ Q	假言推论
¬Q∧(P→Q) ⇒ ¬P	拒取式
¬P∧(PVQ) ⇒ Q	析取三段论
(P→Q)∧(Q→R) ⇒ P→R	假言三段论
(PVQ)∧(P→R)∧(Q→R) ⇒ R	两难推论

1.6对偶

设A是只含有与或非的公式，如果将A中的∧换成V，V换成∧，T换成F，F换成T，得到公式A*，称为A的对偶公式。
定理：如果A等价于B，则A* 等价于 B*

1.7范式

概括:
T - 极小项(∧) - 主析取范式(极小项V极小项)
F - 极大项(V) - 主合取范式(极大项∧极大项)

极小项

P∧Q, P∧¬Q, ¬P∧Q, ¬P∧¬Q

极大项

PVQ, PV¬Q, ¬PVQ, ¬PV¬Q

1.8命题演算的推理理论

直接推理

P规则：使用题目中给的一个条件
T规则：由上面推理过程的某几个步骤由基本等价式或基本蕴含式推出

CP规则

比直接推理多出P（假设前提），即题目目标要推出P→Q时可将P作为条件引入推理，最终推出Q，最后一步推出的Q为CP规则。

间接证法

先令要推出的目标的非作为假设前提，最后推出一个矛盾式，则证明目标的非不成立，即推出目标。

第二章 谓词逻辑

2.1谓词、量词、个体域

用A表示“是个大学生”，A是谓词。
用c表示张华，用e表示李凯，则A©，A(e)表示他们是大学生。其中c和e是客体，A©是原子命题的谓词形式，它是命题。但若x代表任何一个人，A(x)则不是命题，因为我们无法判断其真假。

(∃x)A(x) 和 (∀x)A(x)是命题。

2.6谓词演算的推理理论

1.推理规则

(1)US规则（全称规定规则）（ES规则用完再用）

(∀x)A(x) ⇒ A(y)

(2)ES规则（存在规定规则）（做题时先用！！！）

(∃x)A(x) ⇒ A(y)

(3)EG规则（存在推广规则）（题目快做出来时用）

A(y) ⇒ (∃x)A(x)

(4)UG规则（全称推广规则）（题目快做出来时用）

A(y) ⇒ (∀x)A(x)

第五章 关系

5.1关系的概念

序偶

两个固定次序的个体组成的序列，记作<x,y>。
<x,x>也是一个序偶。

笛卡尔乘积

例：设A={a,b}, B={0,1}, C={∅}
解
A X B = {<a,0>,<a,1>,<b,0>,<b,1>};
B X A = {<0,a>,<0,b>,<1,a>,<1,b>};

5.2二元关系的表示及其性质

二元关系的性质

设R是集合X中的二元关系

自反

若对任一x∈X，都有xRx，即<x,x>∈R，则称R是自反的。

反自反

若对任一x∈X，都有xRx，即<x,x>∈R，则称R是反自反的。

对称

若对任一对x,y∈X，每当<x,y>∈R时都有<y,x>∈R，则称R是对称的。

反对称

若对任一对x,y∈X，若xRy且yRx，则必有x=y，则称R是反对称的。

传递

若对任意x,y,z∈X，每当xRy且yRz时，就有xRz，则称R是对称的。

5.3等价关系与划分

等价关系

设R是集合X中的二元关系，若R是自反的、对称的、传递的，则R是等价关系。

等价类

设R是集合X中的等价关系，对于任一确定的x∈X，均可作一个X的子集 ([x]_R) 称为由x生成的R等价类：
[x]_R = {y | (y∈X) ∧ (xRy)};

商集

设R是非空集合X中的等价关系。由X的各元素生成的R等价类构成的集合{[x]_R | x∈X}，称为X关于R的商集，记作X/R

覆盖(每个子集可相交)

设X是非空集合，A={A₁,A₂, … , A_m} 且令 A_i并起来等于X，则A是X的覆盖。

划分(每个子集不可相交)

在覆盖的基础上，每个A_i不相交。

5.4相容关系与覆盖

设R是X中的二元关系，如果R是自反的和对称的，则称R是相容关系。

5.5关系的运算

关系的合成运算

设R是从集合X到集合Y的关系，S是从集合Y到集合Z的关系，则R^。S称为R和S的合成关系。
定义为：
R^。S={<x,z>|(x∈X)∧(z∈Z)∧存在y使得(y∈Y∧<x,y>∈R∧<y,z>∈S)};

5.6偏序关系

偏序关系 定义

设R是集合X的二元关系，如果R是自反的、反对称的和可传递的，则称R是X中的偏序关系，通常用符号“≤”记偏序关系R。

例：设A={2,3,6,8,12,16,24,32}，R是A中的整除关系，R={<x,y>|x∈A ∧ y∈A ∧ x|y},其中|为整除符号。试证明R是偏序关系
解：
(1）对A中任意的x，因x|x，所以<x,x>∈R，即R是自反的。
(2）对A中任意的x，y，若<x,y>∈R，<y,x>∈R，即x|y且y|x，则有y=pqy，因y≠0，所以pq=1，即p=q=1，所以x=y。
(3）对A中任意x，y，z，若<x,y>∈R，<y,z>∈R，即x|y且y|z

Q.E.D.