离散数学

基本概念

数理逻辑

命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价↔）

析取∨ 类同于或
合取∧ 类同于且
蕴涵→ 如果就
等价充分必要条件

命题(非真既假的陈述句)

复合命题(由简单命题通过联结词联结而成的命题)

计算规律

双重否定律: A ⇔ ¬¬A
幂等律: A ∨ A ⇔ A, A ∧ A ⇔ A
交换律: A ∧ B ⇔ B ∧ A, A ∨ B ⇔ B ∨ A
结合律: (A ∨ B) ∨ C ⇔ A ∨ (B ∨ C), (A ∧ B) ∧ C ⇔ A ∧ (B ∧ C)
分配律: A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C), A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C)
德摩根律: ¬(A ∨ B) ⇔ ¬A ∧ ¬B, ¬(A ∧ B) ⇔ ¬A ∨ ¬B
吸收律: A ∨ (A ∧ B) ⇔ A, A ∧ (A ∨ B) ⇔ A
零律: A ∨ 1 ⇔ 1, A ∧ 0 ⇔ 0,
同一律: A ∧ 1 ⇔ A, A ∨ 0 ⇔ A
排中律: A ∨ ¬A ⇔ 1
矛盾律: A ∧ ¬A ⇔ 0
蕴涵等值式: A → B ⇔ ¬A ∨ B
等价等值式: A ↔ B ⇔ (A → B) ∧ (B → A)
假言易位: A → B ⇔ ¬B → ¬A
等价否定等值式: A ↔ B ⇔ ¬A ↔ ¬B
归谬论: (A → B) ∧ (A → ¬B) ⇔ ¬A

范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式

公式类型的判别方法：真值表法、等值演算法、主析取/合取范式法

命题逻辑的推理理论

有一些重要的重言蕴涵式，称作推理定律。下面给出9条推理定律，它们是：

$A \Rightarrow (A \lor B)$
附加律
$(A \land B) \Rightarrow A$
化简律
$(A \rightarrow B) \land A \Rightarrow B$
假言推理
$(A \rightarrow B) \land \neg B \Rightarrow \neg A$
拒取式
$(A \lor B) \land \neg B \Rightarrow A$
析取三段论
$(A \rightarrow B) \land (B \rightarrow C) \Rightarrow (A \rightarrow C)$
假言三段论
$(A \leftrightarrow B) \land (B \leftrightarrow C) \Rightarrow (A \leftrightarrow C)$
等价三段论
$(A \rightarrow B) \land (C \rightarrow D) \land (A \lor C) \Rightarrow (B \lor D)$
构造性二难
$(A \rightarrow B) \land (\neg A \rightarrow B) \Rightarrow B$
构造性二难（特殊形式）
$(A \rightarrow B) \land (C \rightarrow D) \land (\neg B \lor \neg D) \Rightarrow (\neg A \lor \neg C)$
破坏性二难

其中 $A, B, C, D$ 等是元语言符号，表示任意的命题公式。

集合

集合、元素、集合的表示方法（列元素法、谓词表示法）、子集、空集、全集、集合的包含、相等、幂集

定义幂集

设 $A$ 为集合，把 $A$ 的全体子集构成的集合叫做 $A$ 的幂集，记作 $P(A)$（或 $2^A$），符号化表示为

$$P(A) = \{ x \mid x \subseteq A \}。$$

若 $A$ 是 $n$ 元集，则 $P(A)$ 有 $2^n$ 个元素。
例如：$A = \{ a, b, c \}$，$A$ 的幂集：

$$P(A) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}。$$

集合的交、并、差、补以及对称差等运算及有穷集的计数（文氏（Venn）图、包含排斥原理）

集合恒等式（幂等律、交换律、结合律、分配律、吸收律、矛盾律、德摩根律等）及应用

集合恒等式

名称	等式
恒等律	$A \cup \emptyset = A, \, A \cap E = A$
支配律	$A \cup E = E, \, A \cap \emptyset = \emptyset$
幂等律	$A \cup A = A, \, A \cap A = A$
双重否定律	$\sim(\sim A) = A$
交换律	$A \cup B = B \cup A, \, A \cap B = B \cap A$
结合律	$A \cup (B \cup C) = (A \cup B) \cup C, \, A \cap (B \cap C) = (A \cap B) \cap C$
分配率	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C), \, A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
德摩根律	$\sim(A \cup B) = \sim B \cap \sim A, \, \sim(A \cap B) = \sim A \cup \sim B$
吸收律	$A \cup (A \cap B) = A, \, A \cap (A \cup B) = A$
补律	$A \cap \sim A = \emptyset, \, A \cup \sim A = E$

集合运算定律

幂等律：
- $A \cup A = A$
- $A \cap A = A$
结合律：
- $(A \cup B) \cup C = A \cup (B \cup C)$
交换律：
- $A \cup B = B \cup A$
- $A \cap B = B \cap A$
分配律：
- $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
- $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
同一律：
- $A \cup \emptyset = A$
- $A \cap U = A$
零律：
- $A \cup U = U$
- $A \cap \emptyset = \emptyset$
排中律：
- $A \cup \sim A = U$
矛盾律：
- $A \cap \sim A = \emptyset$
吸收律：
- $A \cup (A \cap B) = A$
- $A \cap (A \cup B) = A$
德摩根律：
- $A - (B \cup C) = (A - B) \cap (A - C)$
- $A - (B \cap C) = (A - B) \cup (A - C)$
- $\sim (B \cup C) = \sim B \cap \sim C$
- $\sim (B \cap C) = \sim B \cup \sim C$
- $\sim \emptyset = U$
- $\sim U = \emptyset$
双重否定律：
- $\sim (\sim A) = A$

‍

二元关系

了解序偶与笛卡尔积的概念，掌握笛卡尔积的运算。

理解关系的概念：二元关系、空关系、全域关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。

定义 7.3 二元关系

一个集合被称为二元关系（记作 RR），如果它满足以下条件之一：
1. 集合非空，且它的元素都是有序对；
2. 集合是空集。
对于二元关系 RR，如果 ⟨x,y⟩∈R⟨x,y⟩∈R，则记作 xRyxRy；如果 ⟨x,y⟩∉R⟨x,y⟩∈/R，则记作 xR̸yxRy。
示例：
- R1={⟨1,2⟩,⟨a,b⟩}R1={⟨1,2⟩,⟨a,b⟩} 是二元关系。
- R2={⟨1,2⟩,a,b}R2={⟨1,2⟩,a,b} 不是二元关系，除非将 aa 和 bb 定义为有序对。
定义 7.4 从 AA 到 BB 的二元关系

设 AA 和 BB 为集合，A×BA×B 的任何子集所定义的二元关系称为从 AA 到 BB 的二元关系。特别地，当 A=BA=B 时，称为 AA 上的二元关系。
示例：
- A={0,1}A={0,1}，B={1,2,3}B={1,2,3}。
- R1={⟨0,2⟩}R1={⟨0,2⟩}，R2=A×BR2=A×B，R3=∅R3=∅，R4={⟨0,1⟩}R4={⟨0,1⟩} 都是从 AA 到 BB 的二元关系。
- R3R3 和 R4R4 同时也是 AA 上的二元关系。
- 对于任何集合 AA，空集 ∅∅ 是 A×AA×A 的子集，称为 AA 上的空关系。此外，定义 AA 上的以下两种关系：
  1. 全域关系 EAEA：包含 A×AA×A 中的所有有序对，即 EA=A×AEA=A×A。
  2. 恒等关系 IAIA：包含所有形如 ⟨a,a⟩⟨a,a⟩ 的有序对，其中 a∈Aa∈A，即 IA={⟨a,a⟩∣a∈A}IA={⟨a,a⟩∣a∈A}。
  这些关系在集合论和离散数学中具有重要的应用，用于描述集合元素之间的特定联系。