阅读数:205 评论数:0

一、数理逻辑

1、命题逻辑的基本概述

（1）命题与联结词

在离散数学中，命题是一个陈述句，它要么是真（真值为 T），要么是假（真值为 F）。命题逻辑是研究命题及其组合的规则和技术。

命题可以通过使用逻辑联结词（逻辑运算符）组合成更复杂的命题。以下是一些基本的逻辑联结词：

• **否定（NOT，¬）**:
• **合取（AND，∧）**:
• **析取（OR，∨）**:
• **蕴含（IMPLIES，→）**:
• **双条件（IFF，↔）**:
• 还有一些其他的联结词，如异或（XOR，⊕）

（2）命题公式及其赋值

在离散数学中，命题公式是由原子命题、逻辑联结词和括号构成的表达式。原子命题是不可再分的命题，它们是命题公式的基本构建块。通过对原子命题进行逻辑运算，可以构建更复杂的命题公式。

命题公式的赋值是指给每个原子命题指定一个真值（真或假）。通过对原子命题的不同赋值，我们可以确定整个命题公式的真值。

如果两个命题公式在所有可能的真值赋值下都有相同的真值结果，那么这两个命题公式被认为是逻辑等价的。例如，命题公式 p → q 和 ¬p ∨ q 在逻辑上是等价的，因为它们有相同的真值表。

2、命题逻辑等值演算

（1）等值式

• **交换律 (Commutative Laws)**
  $$ p \land q \equiv q \land p $$
  $$ p \lor q \equiv q \lor p $$
• **结合律 (Associative Laws)**
  $$ (p \land q) \land r \equiv p \land (q \land r) $$
  $$ (p \lor q) \lor r \equiv p \lor (q \lor r) $$
• **分配律 (Distributive Laws)**
  $$ p \land (q \lor r) \equiv (p \land q) \lor (p \land r) $$
  $$ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) $$
• **同一律 (Identity Laws)**
  $$ p \land \text{true} \equiv p $$
  $$ p \lor \text{false} \equiv p $$
• **支配律 (Domination Laws)**
  $$ p \land \text{false} \equiv \text{false} $$
  $$ p \lor \text{true} \equiv \text{true} $$
• **幂等律 (Idempotent Laws)**
  $$ p \land p \equiv p $$
  $$ p \lor p \equiv p $$
• **否定律 (Negation Laws)**
  $$ p \land \neg p \equiv \text{false} $$
  $$ p \lor \neg p \equiv \text{true} $$
• *双重否定律 (Double Negation Law)**
  $$ \neg (\neg p) \equiv p $$
• **德摩根定律 (De Morgan's Laws)**
  $$ \neg (p \land q) \equiv \neg p \lor \neg q $$
  $$ \neg (p \lor q) \equiv \neg p \land \neg q $$
• **吸收律 (Absorption Laws)**
  $$ p \lor (p \land q) \equiv p $$
  $$ p \land (p \lor q) \equiv p $$
• **条件等值式**
  $$ p \rightarrow q \equiv \neg p \lor q $$
  $$ p \rightarrow q \equiv \neg q \rightarrow \neg p $$
• **双条件等值式**
  $$ p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p) $$
  $$ p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q) $$
  $$ p \leftrightarrow q \equiv \neg (p \oplus q) $$

（2）析取范式与合取范式

析取范式是一个逻辑表达式的标准形式，它由一个或多个合取子句的析取组成。每个合取子句是一个或多个文字的合取（一个文字是一个命题变量或其否定）。简单来说，DNF是一个"或"表达式，其中每个操作数都是一个"与"表达式。例如：

$$ (A \land B) \lor (C \land \neg D) \lor E $$

合取范式是一个逻辑表达式的另一种标准形式，它由一个或多个析取子句的合取组成。每个析取子句是一个或多个文字的析取。简单来说，CNF是一个"与"表达式，其中每个操作数都是一个"或"表达式。例如：

$$ (A \lor \neg B) \land (C \lor D) \land (\neg E \lor F) $$

任何逻辑表达式都可以转换为等价的DNF或CNF。

（3）联结词的完备集

在逻辑中，一组联结词被称为完备的（或者功能完备的），如果能够使用这组联结词来表达逻辑中的任何表达式。

对于命题逻辑，以下是几个知名的完备集：

• 单一联结词的完备集：
  • NOR（或非）：任何逻辑函数都可以只用 NOR 运算来表达。
  • NAND（与非）：任何逻辑函数都可以只用 NAND 运算来表达。
• 包含两个联结词的完备集：
  • {AND, NOT}（合取和否定）：可以通过合取和否定组合来表达所有逻辑函数。
  • {OR, NOT}（析取和否定）：可以通过析取和否定组合来表达所有逻辑函数。
• 包含三个联结词的完备集：
  • {AND, OR, NOT}：虽然 NOT 可以由 AND 或 OR 单独配合 NAND 或 NOR 表达，但这三个联结词通常一起使用，因为它们在直观上更容易理解。

在逻辑电路设计中，NAND 和 NOR 特别重要，因为它们可以单独构成电路系统的基础，这就是为什么它们被称为"通用门"。

（4）可满足性问题与消解法

对于布尔表达式，如果存在一种对变量的赋值方式使得整个表达式求值为真（即满足表达式），则称该表达式是可满足的（satisfiable）。如果无论如何赋值，表达式都不可能为真，则称该表达式是不可满足的（unsatisfiable）。

消解法是一个用于命题逻辑和一阶逻辑的自动定理证明方法，尤其适用于判定公式集的不可满足性。它是基于反证法的原理，即假设我们要证明的公式是错误的，然后通过一系列逻辑推理步骤推导出矛盾，从而证明原始公式必须是正确的。

在命题逻辑中，消解法通常应用于以合取范式（CNF）表示的公式。消解规则允许我们从两个包含互补文字（一个变量的正面和负面形式）的子句中推导出一个新子句。这个过程反复进行，直到：

• 生成一个空子句，表示原公式是不可满足的（因为空子句不能为真）；
• 或者无法进一步应用消解规则，这可能意味着原公式是可满足的，或者我们的推理尚未找到证明。

消解法的一个关键优点是它的决策过程是有限的，因为任何给定的有限公式集合在应用消解规则的次数上都有一个上限。然而，实际上，对于复杂的公式，消解过程可能会非常耗时，并且生成的中间子句数量可能会非常巨大，这就是为什么在实践中人们会使用更高效的SAT求解器来处理可满足性问题。

3、命题逻辑的推理理论

（1）推理的形式结构

推理的形式结构是指用形式逻辑的语言来表示推理过程的结构。在形式逻辑中，推理是通过从一组前提出发，根据逻辑规则得出结论的过程。

在形式逻辑中，推理的形式结构可以是演绎的、归纳的或是溯因的：

• 演绎推理（Deductive Reasoning）：如果前提为真，则结论必然为真。演绎推理关注于保证结论的必然性。经典的例子包括所有人类都是凡人（前提1），苏格拉底是人类（前提2），因此苏格拉底是凡人（结论）。
• 归纳推理（Inductive Reasoning）：从特殊到一般的推理，即从个别实例出发，推广到一般规律。归纳推理不保证结论的必然性，只是提供结论为真的概率。例如，观察到的所有天鹅都是白色的，因此推断所有天鹅都是白色的。
• 溯因推理（Abductive Reasoning）：从结果推测最可能的原因。它通常用于形成假设，作为科学研究的起点。例如，草地上有湿迹（结果），推断可能是因为下过雨（原因）。

（2）自然推理系统

自然推理系统（Natural Deduction System）是一种模拟日常推理过程的形式逻辑系统。它由一系列推理规则组成，这些规则描述了如何从一组前提中合理地推导出结论。自然推理系统的目的是尽可能贴近人类的自然思维习惯，使得推导的过程直观易懂。

（3）消解证明法

消解证明法（Resolution Proof Method）是一种在命题逻辑和谓词逻辑中用于自动证明定理的方法。它是由John Alan Robinson在1965年提出的，并且它是许多自动定理证明和逻辑编程语言的基础。

消解证明法特别适用于命题逻辑中的可满足性问题（SAT问题）和谓词逻辑中的一阶逻辑问题。其核心思想是将所有的命题转换成子句集合（通常是合取范式，即CNF），然后通过重复应用消解规则来简化这个集合。

**消解规则**：

在命题逻辑中，消解规则可以描述为：如果有两个子句，一个包含某个文字（即一个命题变量或其否定），另一个包含这个文字的否定，那么我们可以推导出一个新的子句，这个子句包含所有原来两个子句中的其他文字，但不包含这对互相冲突的文字。这个过程被称为消解。

例如，考虑以下两个子句：

1. $( P \vee Q )$
2. $( \neg P \vee R )$

我们可以应用消解规则来消去$( P )$和$( \neg P )$，得到新的子句：

$( Q \vee R )$

4、一阶逻辑基本概念

（1）一阶逻辑命题符号化

一阶逻辑的基础构建块包括：

• **个体常量**（例如：`a`, `b`, `c`），代表特定的对象。
• **个体变量**（例如：`x`, `y`, `z`），代表任意的对象。
• **谓词**（例如：`P(x)`, `Q(x, y)`），代表对象的属性或对象间的关系。
• **函数符号**（例如：`f(x)`, `g(x, y)`），代表从对象到对象的映射。
• **逻辑连接词**：合取（`∧`，且）、析取（`∨`，或）、否定（`¬`）、蕴含（`→`，如果...则）、等价（`↔`，当且仅当）。
• **量词**：存在量词（`∃`，存在）和全称量词（`∀`，对所有）。

（2）一阶逻辑公式及其解释

5、一阶逻辑等值演算与推理

（1）一阶逻辑等值式与置换规则

（2）一阶逻辑前束范式

在一阶逻辑中，前束范式（Prenex Normal Form，简称PNF）是一种特殊形式的公式，其中所有的量词都被移到了公式最前面，不再分散在公式的各个部分。

前束范式的一般形式是：

$$
Q_1x_1Q_2x_2...Q_nx_n M
$$

其中，$Q_i$ 是量词（全称量词 $\forall$ 或存在量词 $\exists$），$x_i$ 是变量，而 $M$ 是不含有量词的公式部分，称为矩阵。在这种形式中，所有的逻辑操作（如合取、析取、蕴含等）都在量词的作用域之外。

（3）一阶逻辑的推理理论

二、集合论

1、集合代数

（1）集合的基本概念

（2）集合的运算

• 并集（Union）

两个集合的并集包含属于第一个集合或属于第二个集合的所有元素（包括两者共有的元素）。并集通常用符号 $\cup$ 表示。如果有两个集合 $A$ 和 $B$，它们的并集写作 $A \cup B$，定义为：

$$
A \cup B = \{ x | x \in A \text{ 或 } x \in B \}
$$

• 交集（Intersection）

两个集合的交集包含同时属于第一个集合和第二个集合的所有元素。交集用符号 $\cap$ 表示。如果有两个集合 $A$ 和 $B$，它们的交集写作 $A \cap B$，定义为：

$$
A \cap B = \{ x | x \in A \text{ 且 } x \in B \}
$$

• 差集（Set Difference）

一个集合与另一个集合的差集包含属于第一个集合但不属于第二个集合的所有元素。差集用符号 $-$ 或 $\setminus$ 表示。如果有两个集合 $A$ 和 $B$，$A$ 对 $B$ 的差集写作 $A - B$ 或 $A \setminus B$，定义为：

$$
A - B = A \setminus B = \{ x | x \in A \text{ 且 } x \notin B \}
$$

• 补集（Complement）

一个集合的补集包含不属于该集合但属于一个基准全集的所有元素。补集通常用上标 $^C$ 或者符号 $\complement$ 表示。如果有集合 $A$ 和全集 $U$，$A$ 的补集写作 $A^C$ 或 $\complement_U A$，定义为：

$$
A^C = \complement_U A = \{ x | x \in U \text{ 且 } x \notin A \}
$$

• 笛卡尔积（Cartesian Product）

两个集合的笛卡尔积是所有可能的有序对组合，其中第一个元素来自第一个集合，第二个元素来自第二个集合。笛卡尔积用符号 $\times$ 表示。如果有两个集合 $A$ 和 $B$，它们的笛卡尔积写作 $A \times B$，定义为：

$$
A \times B = \{ (a, b) | a \in A \text{ 且 } b \in B \}
$$

• 幂集（Power Set）

一个集合的幂集是其所有子集的集合，包括空集和集合本身。幂集通常用符号 $\mathcal{P}$ 或 $2^A$ 表示。如果有集合 $A$，它的幂集写作 $\mathcal{P}(A)$ 或 $2^A$，定义为：

$$
\mathcal{P}(A) = 2^A = \{ X | X \subseteq A \}
$$

（3）有穷集的计数

有穷集（或称有限集）的计数涉及确定集合中元素的个数。对于有穷集，我们可以通过直接计数的方法来确定集合的势（大小）。以下是一些与有穷集计数相关的基本概念和原理：

• 基数（Cardinality）

一个集合的基数是指集合中元素的数量。对于有穷集合 $A$，基数通常用符号 $|A|$ 或 $\#A$ 表示。例如，如果 $A = \{2, 4, 6\}$，则 $|A| = 3$。

• 加法原理（Sum Rule）

如果集合 $A$ 和集合 $B$ 是不相交的（即 $A \cap B = \emptyset$），那么它们的并集 $A \cup B$ 的基数是它们基数的和：

$$
|A \cup B| = |A| + |B|
$$

• 乘法原理（Product Rule）

如果要对两个集合的笛卡尔积进行计数，集合 $A$ 和集合 $B$ 的笛卡尔积 $A \times B$ 的基数等于两个集合基数的乘积：

$$
|A \times B| = |A| \cdot |B|
$$

• 幂集的基数

对于任何有穷集合 $A$，其幂集 $2^A$ 或 $\mathcal{P}(A)$ 的基数是 $2$ 的 $|A|$ 次方：

$$
|\mathcal{P}(A)| = 2^{|A|}
$$

• 排列（Permutations）

从集合中选取 $n$ 个元素进行排列的方式的数量，如果集合有 $n$ 个不同的元素，那么排列的总数是 $n!$（$n$ 的阶乘）。如果是从 $n$ 个元素中选取 $r$ 个元素进行排列，则排列数为：

$$
P(n, r) = \frac{n!}{(n-r)!}
$$

• 组合（Combinations）

从集合中选取 $n$ 个元素进行组合的方式的数量，不考虑元素的顺序。如果集合有 $n$ 个不同的元素，从中选取 $r$ 个元素的组合数为：

$$
C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}
$$

• 重复组合（Combinations with Repetition）

当从集合中选取元素时，允许重复选取同一个元素，从 $n$ 个不同的元素中选取 $r$ 个（允许重复）的组合数为：

$$
\binom{n+r-1}{r}
$$

（4）集合恒等式

• 交换律（Commutative Laws）

对于任何集合 $A$ 和 $B$：
$$
A \cup B = B \cup A
$$
$$
A \cap B = B \cap A
$$

• 结合律（Associative Laws）

对于任何集合 $A$、$B$ 和 $C$：
$$
(A \cup B) \cup C = A \cup (B \cup C)
$$
$$
(A \cap B) \cap C = A \cap (B \cap C)
$$

• 分配律（Distributive Laws）

对于任何集合 $A$、$B$ 和 $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)
$$

• 吸收律（Absorption Laws）

对于任何集合 $A$ 和 $B$：
$$
A \cup (A \cap B) = A
$$
$$
A \cap (A \cup B) = A
$$

• 德摩根定律（De Morgan's Laws）

对于任何集合 $A$ 和 $B$ 以及全集 $U$：
$$
(A \cup B)^C = A^C \cap B^C
$$
$$
(A \cap B)^C = A^C \cup B^C
$$

• 补集律（Complement Laws）

对于任何集合 $A$ 和全集 $U$：
$$
A \cup A^C = U
$$
$$
A \cap A^C = \emptyset
$$
$$
(A^C)^C = A
$$

• 幂集律（Power Set Laws）

对于任何集合 $A$：
$$
|\mathcal{P}(A)| = 2^{|A|}
$$

• 空集和全集律（Laws of the Empty Set and Universe）

对于任何集合 $A$ 和空集 $\emptyset$ 以及全集 $U$：
$$
A \cup \emptyset = A
$$
$$
A \cap \emptyset = \emptyset
$$
$$
A \cup U = U
$$
$$
A \cap U = A
$$

2、二元关系

（1）有序对与笛卡尔儿积

（2）二元关系

（3）关系的运算

（4）关系的性质

（5）关系的闭包

（6）等价关系与划分

（7）偏序关系

偏序关系（Partial Order Relation）是集合理论中的一个重要概念，用于描述集合内元素之间存在的一种顺序关系。一个偏序关系是关系的一种特殊类型，它具有以下性质：

• **自反性（Reflexivity）**：对于集合中的每个元素 $a$，都有 $a \leq a$。
• **反对称性（Antisymmetry）**：对于集合中的任意两个元素 $a$ 和 $b$，如果 $a \leq b$ 且 $b \leq a$，则 $a = b$。
• **传递性（Transitivity）**：对于集合中的任意三个元素 $a$、$b$ 和 $c$，如果 $a \leq b$ 且 $b \leq c$，则 $a \leq c$。

这里的 $\leq$ 符号是偏序关系的一种常见表示，但实际上可以用任何符号来表示。

3、函数

（1）函数的定义与性质

（2）函数的复合与反函数

（3）双射函数与集合的基数

三、代数结构

1、代数系统

（1）二元运算及其性质

（2）代数系统

（3）代数系统的同态与同构

• 同态（Homomorphism）

一个同态是从一个代数系统到另一个相同类型的代数系统的映射，它保持了代数结构的运算。确切地说，如果有两个代数结构 $(A, \ast)$ 和 $(B, \cdot)$，一个映射 $f: A \to B$ 被称为同态，如果对于所有 $a_1, a_2 \in A$，都有：
$$
f(a_1 \ast a_2) = f(a_1) \cdot f(a_2)
$$
这意味着通过 $f$ 映射后，$A$ 中的运算 $\ast$ 在 $B$ 中的像是运算 $\cdot$。

• 同构（Isomorphism）

同构是一种特殊的同态，它是双射的，即一一对应和到上的。如果存在一个同构 $f: A \to B$，那么我们可以说代数结构 $A$ 和 $B$ 是同构的，记作 $A \cong B$。同构的存在意味着两个代数结构在结构上是完全相同的，只是它们的元素可能有不同的标记或表示。

2、群与环

（1）群的定义及性质

（2）子群与群的陪集分解

（3）循环群与置换群

（4）环与域

3、格与布尔代数

（1）格的定义与性质

（2）分配格、有补格与布尔代数

四、组合数学

1、基本的组合计数公式

（1）加法法则与乘法法则

（2）排列与组合

（3）二项式定理与组合恒等式

（4）多项式定理

2、递推方程与生成函数