离散数学期末复习笔记
一、命题的基本概念
命题的定义:
陈述客观世界事情的陈述句叫命题,其特征性质是非真即假。
命题的“真值”有两种：
真（true,T,1）、假(false,F,0)，常用p,q,r……等命题变元表示命题
命题联结词：
由简单命题造复杂命题
如果……则……，如果（如果（如果……则……）则……）则……，
用文字不好表述，所以用符号：((p → q) → r) → s
| 命题联结词 | 表示 |
|---|---|
| 否定词 | ¬ p ( 非 p ) |
| 析取词 | p ∨ q |
| 合取词 | p ∧ q |
| 蕴含词 | p → q |
| 等价词 | p ↔ q |
蕴含词：
p → q 成立时，称 p 为 q 的充分条件，q 为 p的必要条件.
p ↔ q 成立时，称 p 为 q 的充分必要条件. p ↔ q 相当于 p → q 且 q → p.
p → q 的逆命题指的时 q → p,逆否命题是 ¬ q → ¬ p.
题：用命题联结词表示“ p 与 q 恰好有一个成立 ”.
两种情况：
- p = 1 且 q = 0
- p = 0 且 q = 0
命题联结词：**( p ∧ ¬ q ) ∨ ( ( ¬ p ) ∧ q )**
二、命题的等价与永真公式
基础概念
- 命题变元：
设命题 φ 中共有 n 个命题变元 p1, …, pn。 - 赋值：
对 p1, …, pn 分别指定真值 δ1, …, δn (δi ∈ {0, 1})，则称 φ 有一个赋值 (p1, …, pn) = (δ1, …, δn)。 - 成真赋值：
如果此赋值使得 φ 真，则称它为 φ 的成真赋值。 - 成假赋值：
如果此赋值使得 φ 假，则称它为 φ 的成假赋值。 - 永真公式（重言式）：
如果在任何赋值下 φ 都真，则称 φ 为永真公式（重言式）。 - 同真同假（等价）：
对于命题公式 α 与 β，如果在任何赋值下，α, β 同真同假，则称 α 与 β 等价，记为 α ≡ β，相当于 α ↔ β 是永真公式。
易错点： α ≡ β 表示的是两个命题之间的关系，而 α ↔ β 只是一个命题。
1、否定：
| p | ¬p |
|---|---|
| 1 | 0 |
| 0 | 1 |
2、合取：
| p | q | p ∧ q |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
3、析取：
| p | q | p ∨ q |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
4、条件：
| p | q | p → q |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
5、双条件：
| p | q | p ↔ q |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
例题：
| p | q | r | ¬p | ¬p ∧ q | ¬(¬p ∧ q) | ¬r | ¬(¬p ∧ q) ∨ ¬r |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
三、命题演算的基本逻辑规律
八条必须牢记的等价关系式：
1、排中律：α ∨ ¬α ≡ 1.
2、“→” 的定义：α → β ≡ ¬α ∨ β.
3、“↔” 的定义：α ↔ β ≡ (α → β) ∧ (β → α).
4、幂等律：α ∨ α ≡ α ∧ α ≡ α.
5、交换律：α ∨ β ≡ β ∨ α, α ∧ β ≡ β ∧ α.
6、结合律：(α ∨ β) ∨ γ ≡ α ∨ (β ∨ γ), (α ∧ β) ∧ γ ≡ α ∧ (β ∧ γ).
7、分配律：α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ), α ∧ (β ∨ γ) ≡ (α ∧ β) ∨ (α ∧ γ).
8、德摩根律：¬(α ∨ β) ≡ ¬α ∧ ¬β, ¬(α ∧ β) ≡ ¬α ∨ ¬β.
证明 (α → γ) ∨ (β → γ) ≡ (α ∧ β) → γ：
利用条件运算的定义，将 α → γ 和 β → γ 进行展开：
α → γ ≡ ¬α ∨ γ
β → γ ≡ ¬β ∨ γ将原式
(α → γ) ∨ (β → γ)代入条件运算的定义：(α → γ) ∨ (β → γ) ≡ (¬α ∨ γ) ∨ (¬β ∨ γ)根据析取的结合律，将上式重新排列：
(¬α ∨ γ) ∨ (¬β ∨ γ) ≡ ¬α ∨ ¬β ∨ γ根据析取的结合律，上式等价于：
¬α ∨ ¬β ∨ γ ≡ ¬(α ∧ β) ∨ γ利用条件运算的定义，将
¬(α ∧ β) ∨ γ重新表示：¬(α ∧ β) ∨ γ ≡ (α ∧ β) → γ
四、析取范式与合取范式
- 命题变元或其否定叫准变元
- 由有限个准变元作析取而得的析取式叫析基
- 由有限个准变元作合取而得的合取式叫合基
- 有限个合基的析取式叫析取范式，有限个析基的合取式叫合取范式
1、填空题：（选填：析取、合取）
(p ∧ ¬q) ∨ (¬p ∧ ¬q ∧ ¬s) ∨ (¬q ∧ ¬r) 是析取范式。(p ∨ ¬q) ∧ (¬p ∨ ¬q ∨ ¬s) ∧ (¬q ∨ ¬r) 是合取范式。
2、将公式 φ = (p → q) ↔ r 化成等价于它的析取范式
- 首先，利用条件和双条件的定义，将公式展开：
p → q ≡ ¬p ∨ q
(p → q) ↔ r ≡ ((¬p ∨ q) ∧ r) ∨ ((p ∧ ¬q) ∧ ¬r) - 将双条件的定义展开：
(¬p ∨ q) ↔ r ≡ ((¬p ∨ q) → r) ∧ (r → (¬p ∨ q))
- 利用条件运算的定义，将公式进一步展开：
((¬p ∨ q) → r) ≡ ¬(¬p ∨ q) ∨ r ≡ (p ∧ ¬q) ∨ r
(r → (¬p ∨ q)) ≡ ¬r ∨ (¬p ∨ q) - 将以上结果结合起来：
(¬p ∨ q) ↔ r ≡ ((p ∧ ¬q) ∨ r) ∧ (¬r ∨ (¬p ∨ q))
- 最后，使用分配律将公式转化为析取范式：
((p ∧ ¬q) ∨ r) ∧ (¬r ∨ (¬p ∨ q))
五、主析取范式与主合取范式
设 ( p_1, \ldots, p_n ) 是 ( n ) 个不同的命题符号，( p_i’ ) 是 ( p_i ) 或 ( \neg p_i )。设 ( \delta_i ) 为：
[
\delta_i = \begin{cases}
1, & \text{如果 } p_i’ \text{ 为 } p_i \
0, & \text{如果 } p_i’ \text{ 为 } \neg p_i
\end{cases}
]
且 ( \delta_i’ = 1 - \delta_i )。
[
m = p_1’ \land p_2’ \land \cdots \land p_n’ \text{ 是一个极小项，它唯一的成真赋值是 } (p_1, \ldots, p_n) = (\delta_1, \ldots, \delta_n)。
]
[
M = p_1’ \lor p_2’ \lor \cdots \lor p_n’ \text{ 是一个极大项，它唯一的成假赋值是 } (p_1, \ldots, p_n) = (\delta_1’, \ldots, \delta_n’)。
]
设二进制的 ( \delta_1, \ldots, \delta_n ) 表示数 ( i )，则把上述极小项记为 ( m_i )，把上述极大项记为 ( M_i )（ ( 0 \leq i \leq 2^n - 1 ) ）
由主析取范式可知成真赋值，由主合取范式可知成假赋值。
- 永真公式无主合取范式
- 永假公式无主析取范式
例题：把 φ = (p ∧ (q → r)) → s 化为主合取范式，求成假赋值。
将公式转换为合取范式：
1.1. 化简 φ：
[
φ = (p ∧ (¬q ∨ r)) → s
]
1.2. 使用 → 的定义：
[
φ = ¬(p ∧ (¬q ∨ r)) ∨ s
]
1.3. 使用德摩根律：
[
φ = (¬p ∨ ¬(¬q ∨ r)) ∨ s
]
1.4. 再次使用德摩根律：
[
φ = (¬p ∨ (q ∧ ¬r)) ∨ s
]
1.5. 分配律：
[
φ = (¬p ∨ q ∨ s) ∧ (¬p ∨ ¬r ∨ s)
]求成假赋值：
对于合取范式为假的情况，必须每个子句都为假：
[
¬p ∨ q ∨ s = 假
]
[
¬p ∨ ¬r ∨ s = 假
]因此，需要：
[
¬p = 假 ⇒ p = 真
]
[
q ∨ s = 假 ⇒ q = 假 且 s = 假
]
[
¬r ∨ s = 假 ⇒ r = 真 且 s = 假
]所以，成假赋值为：
[
p = 真, q = 假, r = 真, s = 假
]
例题：某科研所要从A, B, C三名骨干中选取1至2人出国进修，选派满足：
(1) A去则C去；
(2) B去则C不去；
(3) C不去则A或B可去。
问：如何选派？
解题步骤：
用 ( p, q, r ) 分别表示 A, B, C 去：
[
\phi = (p \rightarrow r) \land (q \rightarrow \neg r) \land (\neg r \rightarrow (p \lor q))
]将条件用逻辑符号表示：
[
\phi = (\neg p \lor r) \land (\neg q \lor \neg r) \land (r \lor p \lor q)
]化简公式：
[
\phi = (\neg p + r) \land (\neg q + \neg r) \land (r + p + q)
]
[
\phi = \neg p \neg q r + \neg p q r + p \neg q r + \neg q r + p \neg q \neg r + \neg p q \neg r + p q \neg r + q r
]主析取范式（DNF）：
[
\phi = (\neg p \land \neg q \land r) \lor (\neg p \land q \land r) \lor (p \land \neg q \land r) \lor (\neg q \land r) \lor (p \land \neg q \land \neg r) \lor (\neg p \land q \land \neg r) \lor (p \land q \land \neg r) \lor (q \land r)
]
计算成真赋值：
[
(p, q, r) = (0, 0, 1) 或 (0, 1, 0) 或 (1, 0, 1)
]
结论：
符合上述条件的选派方式有三种：
- 选派B去： ( (0, 1, 0) )
- 选派C去： ( (0, 0, 1) )
- 选派A和C一起去： ( (1, 0, 1) )
六、全称量词与存在量词的基本概念
存在量词
∃𝑥𝜑(𝑥) 指存在𝑥使公式𝜑(𝑥)成立.
全称量词
∀𝑥𝜑(𝑥), 指对任意𝑥, 公式𝜑(𝑥)都成立.
有下列关系:
¬∃𝑥𝜑(𝑥) ≡ ∀𝑥¬𝜑(𝑥)
∀𝑥¬𝜑(𝑥) ≡ ¬∃𝑥𝜑(𝑥)
¬∀𝑥𝜑(𝑥) ≡ ∃𝑥¬𝜑(𝑥)
∃𝑥𝜑(𝑥) ≡ ¬∀𝑥¬𝜑(𝑥)
∀𝑥(𝜑(𝑥)∧ψ(𝑥)) ≡ ∀𝑥𝜑(𝑥) ∧ ∀𝑥ψ(𝑥)
∃𝑥(𝜑(𝑥)∨ψ(𝑥)) ≡ ∃𝑥𝜑(𝑥) ∨ ∃𝑥ψ(𝑥)
对应关系:
- “任意” 对应 “且”
- “存在” 对应 “或”
证明：
为了证明：
$$ \exists x (\varphi(x) \rightarrow \psi(x)) \equiv (\forall x \varphi(x) \rightarrow \exists x \psi(x)) $$
证明
$$
\exists x (\varphi(x) \rightarrow \psi(x))
$$
等价于
$$
\exists x (\neg \varphi(x) \lor \psi(x))
$$
等价于
$$
\exists x (\neg \varphi(x)) \lor \exists x (\psi(x))
$$
等价于
$$
\neg \forall x (\varphi(x)) \lor \exists x (\psi(x))
$$
等价于
$$
\forall x (\varphi(x)) \rightarrow \exists x (\psi(x))
$$
七、集合论
集合 R 为关系 (relation) 指满足
[
\forall z (z \in R \rightarrow \exists x \exists y (\langle x, y \rangle = z))
]
的有序对 (\langle x, y \rangle) 构成的集合，对于关系 (R)，(\langle x, y \rangle \in R) 也写作 (xRy)，此时说 (x) 与 (y) 有关系 (R)。
把 (x \in \bigcup \bigcup R : \exists y(xRy))（所有 (xRy) 中的 (x) 构成的集合）叫 (R) 的 定义域，记为 (Dom(R))
把 (y \in \bigcup \bigcup R : \exists x(xRy))（所有 (xRy) 中的 (y) 构成的集合）叫 (R) 的 值域，记为 (Ran(R))
把 (R^{-1} = { \langle y, x \rangle \in Ran(R) \times Dom(R) : xRy }) 叫 (R) 的 逆关系，显然 (xRy \Leftrightarrow yR^{-1}x)
一个 函数 或 映射 (F) 指的是一个关系，且对于 (x \in Dom(F))，(\exists! y (xFy))（即定义域中的每个元素只能对应值域中的唯一元素）。我们把这唯一的 (y) 记为 (F(x))。
关系的定义
- 若 (R \subseteq A \times A)，称 (R) 为 A 上的关系。
- 若 (R, S) 为关系，定义关系的 复合 为
[
R \circ S = { \langle x, z \rangle \in Dom(S) \times Ran(R) : \exists y (xSy \land yRz) }
]
- 可以用函数来理解：若 (f : X \rightarrow Y)，(g : Y \rightarrow Z)，则 ((g \circ f)(x) = g(f(x)))。
注意
- 不同的书对复合的定义不太一样，这里采用的是 “左复合” 定义，有的书可能定义为 “右复合”：
[
R \circ S = { \langle x, z \rangle : \exists y (xRy \land ySz) }
]
题目
设 (A = {a, b, c, d})，(R_1, R_2) 为 (A) 上的关系，其中
[
R_1 = {\langle a, a \rangle, \langle a, b \rangle, \langle b, d \rangle}
]
[
R_2 = {\langle a, d \rangle, \langle b, c \rangle, \langle b, d \rangle, \langle c, b \rangle}
]
则 (R_1 \circ R_2) 为
[
R_1 \circ R_2 = {\langle x, z \rangle \in Dom(S) \times Ran(R) : \exists y (xR_1y \land yR_2z)}
]
使用左复合定义：
- (\langle a, a \rangle \in R_1) 且 (\langle a, d \rangle \in R_2)，因此 (\langle a, d \rangle \in R_1 \circ R_2)
- (\langle a, b \rangle \in R_1) 且 (\langle b, c \rangle \in R_2)，因此 (\langle a, c \rangle \in R_1 \circ R_2)
- (\langle a, b \rangle \in R_1) 且 (\langle b, d \rangle \in R_2)，因此 (\langle a, d \rangle \in R_1 \circ R_2)（重复，已在集合中）
- (\langle b, d \rangle \in R_1) 无法满足复合关系，因为 (d) 不是 (R_2) 的定义域中的元素
综上，(R_1 \circ R_2) 为
[
R_1 \circ R_2 = {\langle a, d \rangle, \langle a, c \rangle}
]
关系的性质
自反
对 (A) 上关系 (R)，称 (R) 在 (A) 上自反，指
[
\forall x \in A (xRx)
]
等价于
[
I_A = {\langle x, x \rangle : x \in A} \subseteq R
]
对称
对 (A) 上关系 (R)，称 (R) 在 (A) 上对称，指
[
\forall x \in A \forall y \in A (xRy \rightarrow yRx)
]
传递
对 (A) 上关系 (R)，称 (R) 在 (A) 上传递，指
[
\forall x \in A \forall y \in A \forall z \in A ((xRy \land yRz) \rightarrow xRz)
]
等价关系
(R) 是 (A) 上等价关系指 (R) 同时满足自反性、对称性、传递性。
| 性质 | 定义 |
|---|---|
| (R) 自反 | (R) 在 (A = Dom(R) \cup Ran(R)) 上自反。 |
| (R) 对称 | (\forall x \forall y (xRy \rightarrow yRx))。 |
| (R) 传递 | (\forall x \forall y \forall z ((xRy \land yRz) \rightarrow xRz))。 |
等价关系的关系满足以下性质：
- (R \subseteq R \circ R)
- (R = R^{-1})
- (R \circ R \subseteq R)
题1
设 (R) 为 (A) 上的自反和传递的关系，证明 (R \cap R^{-1}) 是 (A) 上的等价关系。
证明过程
自反性：
- 因为 (R) 是自反的，所以对任意 (x \in A)，有 (xRx)。
- 因为 (R^{-1}) 也是自反的，所以对任意 (x \in A)，有 (xR^{-1}x)。
- 因此，对任意 (x \in A)，有 (x (R \cap R^{-1}) x)，即 (R \cap R^{-1}) 是自反的。
对称性：
- 如果 ((x, y) \in R \cap R^{-1})，则 (xRy) 且 (yRx)。
- 由于 (xRy) 且 (yRx)，交换顺序仍然成立，因此 ((y, x) \in R \cap R^{-1})。
- 因此，(R \cap R^{-1}) 是对称的。
传递性：
- 如果 ((x, y) \in R \cap R^{-1}) 且 ((y, z) \in R \cap R^{-1})，则 (xRy)、(yRx)、(yRz) 和 (zRy) 都成立。
- 因为 (R) 是传递的，所以 (xRz) 和 (zRx)。
- 因此，((x, z) \in R \cap R^{-1})。
- 因此，(R \cap R^{-1}) 是传递的。
综上所述，(R \cap R^{-1}) 是自反的、对称的和传递的，因此 (R \cap R^{-1}) 是 (A) 上的等价关系。
八、图论基础概念
#### 1、假设我们有一个有限的非空集合 \( V \)，和一个与 \( V \) 不重叠的集合 \( E \)。有一个关联函数 \( \psi: E \rightarrow \{\{x, y\} : x, y \in V\} \)（无序对）或 \( \langle x, y \rangle : x, y \in V \)（有序对）。我们把 \( G = (V, E) \) 称为一个图，把 \( V \) 中的元素叫做 **顶点**， \( E \) 中的元素叫做 **边**。 - **端点**：如果 \( e \in E \) 并且 \( \psi(e) = \{x, y\} \) 或 \( \langle x, y \rangle \)，我们就说 \( x, y \) 是 \( e \) 的 **端点**，\( e \) 连接顶点 \( x, y \)。 - **表示**：通常我们用平面上的点表示 \( V \) 中的元素，当边 \( e \) 连接顶点 \( x, y \) 时，用一条连接 \( x \) 和 \( y \) 的线表示。如果 \( \psi(e) \) 是有序对 \( \langle x, y \rangle \)，则用从 \( x \) 指向 \( y \) 的箭头表示这样的边 \( e \)，这种边叫做 **有向边/弧**。 - **无向边**：没有方向的边叫做 **无向边**，所有边都是无向边的图叫做 **无向图**，所有边都是有向边的图叫做 **有向图**。 - **环**：图 \( G \) 中，如果一条边的两个端点是同一个顶点，这样的边叫做 **环**。 - **平行边或多重边**：如果连接同一对顶点的边不止一条，这些边叫做 **平行边或多重边**。有平行边的图叫做 **多重图**，没有环和平行边的无向图叫做 **简单图**。 - **相邻**：如果图 \( G \) 中有边 \( e \) 连接顶点 \( x, y \)，我们说 \( x, y \) **相邻**。在无向图中，有共同顶点的两条边叫做 **相邻的边**；在有向图中，若边 \( e_1 \) 的终点和边 \( e_2 \) 的起点是同一个顶点，我们称 \( e_1 \) 和 \( e_2 \) **相邻**。 #### 2、 对于图 \( G \)，用 \( V(G) \) 表示 \( G \) 的顶点集，用 \( E(G) \) 表示 \( G \) 的边集。把 \( v \in V(G) \) 的**邻域**定义为 \[ N_G(v) = \{ u \in V(G) \setminus \{ v \} : u \text{与} v \text{相邻} \} \] 把 \( N_G(v) \cup \{v\} \) 叫做 \( v \) 的**闭邻域**。 对于无向图 \( G \)，若 \( v \in V(G) \)，记 \( d_G(v) \)（或简记为 \( d(v) \)）表示 \( v \) 关联的边的条数，称为 \( v \) 的**度（次数）**。 下图中，\( N_G(v_1) = \{ v_2, v_3, v_5 \} \)。 图同构的定义
设 \( G \) 与 \( H \) 是两个图，如果存在 \( V(G) \) 与 \( V(H) \) 的一一对应 \( f \) 以及 \( E(G) \) 到 \( E(H) \) 的一一对应 \( g \)，使得 \( G \) 中边 \( e \) 连接顶点 \( u, v \) 当且仅当 \( H \) 中 \( g(e) \) 连接 \( f(u), f(v) \)，则称 \( G \) 与 \( H \) **同构**，记为 \( G \cong H \)。两个同构的例子
其中 ( u_i ) 与 ( v_i ) 一一对应。
- 图1： ( u_2 ), ( u_3 ), ( u_4 ), ( u_1 ) 形成一个正方形。
- 图2： ( v_1 ), ( v_2 ), ( v_3 ), ( v_4 ), ( v_5 ) 形成一个五边形。
两图中的顶点如下对应：
- ( u_1 ) 对应 ( v_1 )
- ( u_2 ) 对应 ( v_2 )
- ( u_3 ) 对应 ( v_3 )
- ( u_4 ) 对应 ( v_4 )
- ( u_5 ) 对应 ( v_5 )
