离散数学笔记（4）——谓词逻辑（续）和集合论

wzf2000
2019年10月10日

离散数学笔记（4）——谓词逻辑（续）和集合论

谓词演算的推理理论

推理方法

直接推理、条件论证、反证法

所用公式

等价式、蕴含式

推理规则

P，T，CP，US，ES，EG，UG

全称特质规则 US

形式：$\forall x A(x) \Rightarrow A(c)$（其中 $c$ 是论域内指定个体）

含义：如果 $\forall x A(x)$ 为真，则在论域内任何指定个体 $c$，都使得 $A(c)$ 为真。

作用：去掉全称量词。

要求：$c$ 不是 $A(x)$ 中的符号。

存在特制规则 ES

形式：$\exists x A(x) \Rightarrow A(c)$（其中 $c$ 是论域内指定个体）

含义：如果 $\exists x A(x)$ 为真，则在论域内指定个体 $c$，都使得 $A(c)$ 为真。

作用：去掉存在量词。

要求：

1. $c$ 不是 $A(x)$ 中的符号。
2. 用 ES 指定的客体 $c$ 不应该是在此之前用 US 规则或者用 ES 规则所指定的个体 $c$。
3. $A(x)$ 中除 $x$ 外还有其他自由出现的个体变元时，不能用此规则。

存在推广规则 EG

形式：$A(c) \Rightarrow \exists x A(x)$（其中 $c$ 是论域内指定个体）

含义：如果在论域内指定个体 $c$ 使得 $A(c)$ 为真，则 $\exists x A(x)$ 为真。

作用：添加存在量词。

要求：$x$ 不是 $A(c)$ 中的符号。

全程推广规则 UG

形式：$A(c) \Rightarrow \forall x A(x)$（其中 $c$ 是论域内任何指定个体）

含义：如果在论域内任何指定个体 $c$ 使得 $A(c)$ 为真，则 $\forall x A(x)$ 为真。

作用：添加全称量词。

要求：

1. $x$ 不是 $A(c)$ 中的符号。
2. $c$ 一定是任意的个体，否则不可全称推广。

量词有关的重要等价式与蕴含式

\langle img src="http://101.43.216.60/wp-content/uploads/------------/------------------/19-1.png" alt="19" style="zoom: 67%;" / \rangle

\langle img src="http://101.43.216.60/wp-content/uploads/2019/10/------------/20.png" alt="20" style="zoom: 50%;" / \rangle

注意点

• 使用 US、UG、ES、EG 规则应对前束范式。

• 在推理过程中，谓词公式只能应用前面给出的蕴含式与等价式。

• 在含有多个量词的谓词推理中，使用指定规则应该按照从左到右的顺序，而推广规则的使用应该按照从右到左的顺序。

集合论

基本定义

集合

是一些确定的、可以区分的事物汇集在一起组成的一个整体。用大写的英文字母表示。

元素

集合中的每个事物，称之为元素。用小写英文字母表示 $\in$ 表示元素与集合的属于关系。

有限集合与无限集合

有限集合：元素是有限个的集合。

如果A是有限集合，用 $|A|$ 表示 $A$ 中元素个数。

无限集合：元素是无限个的集合

集合的表示方法

列举法（外延表示法）

将集合中的元素一一列出，写在大括号内。

描述法（谓词法）

用句子（或谓词公式）描述元素的属性。

$A=\{x|P(x)\}$，其中 $P(x)$ 是谓词公式，如果论域内个体 $a$ 使得 $P(a)$ 为真，则 $a \in A$，否则 $a \not \in A $。

特别说明

1. 集合中的元素间次序是无关紧要的，但是必须是可以区分的。
2. 对集合中的元素无任何限制。
3. 常用的几个集合符号的约定：
   1. 自然数集合 $\mathbb{N} = \{0,1,2,3,……\}$。
   2. 整数集合 $\mathbb{Z}$。
   3. 实数集合 $\mathbb{R}$。
   4. 有理数集合 $\mathbb{Q}$。
4. 集合中的元素也可以是集合。
5. 对一个集合来说，任一事物或者是它的元素或者不是它的元素，二者必居其一而不可兼而有之，且结论是确定的。

集合间的关系

被包含关系（子集）

$A$、$B$ 是集合，如果 $A$ 中元素都是 $B$ 中元素，则称 $B$ 包含 $A$，$A$ 包含于 $B$， 也称 $A$ 是 $B$ 的子集。

记作 $A \subseteq B$。

谓词定义：$A \subseteq B \Leftrightarrow \forall x (x \in A \rightarrow x \in B)$

性质：

1. 自反性，$A \subseteq A$
2. 传递性，$A \subseteq B,B \subseteq C$，则 $A \subseteq C$
3. 反对称性，$A \subseteq B,B \subseteq A$，则 $A = B$

相等关系

$A$、$B$ 是集合，如果它们的元素完全相同，则称 $A$ 与 $B$ 相等。

记作 $A = B$。

谓词定义：$A = B \Leftrightarrow \forall x (x \in A \leftrightarrow x \in B)$

定理：$A = B$ 当且仅当 $A \subseteq B$ 且 $B \subseteq A$

性质：

1. 自反性，$A = A$
2. 传递性，$A = B,B = C$，则 $A = C$
3. 对称性，$A = B$，则 $B = A$

真被包含关系（真子集）

$A$、$B$ 是集合，如果 $A\subseteq B$ 且 $A \not = B$，则称 $B$ 真包含 $A$，$A$真包含于 $B$，也称 $A$ 是 $B$ 的真子集。

记作 $A \subset B$。

谓词定义：

性质：

对任何集合 $A$、$B$、$C$，如果有 $A \subset B$ 且 $B \subset C$ ，则 $A \subset C$。

特殊集合

全集：$E$

包含所讨论的所有集合的集合，称之为全集，记作 $E$。

性质：对于任何集合 $A$，都有 $A \subseteq E$。

空集：$\varnothing$

不含任何元素的集合，称之为空集，记作 $\varnothing$。

性质：

1. 对于如何集合 $A$，都有 $\varnothing \subseteq A$。 因为 $\forall x (x \in \varnothing \rightarrow x \in A)$为永真式，所以 $\varnothing \subseteq A$。
2. 空集是唯一的。

集合的幂集

$A$ 是集合，由 $A$ 的所有子集构成的集 合，称之为 $A$ 的幂集。记作 $P(A)$ 或 $2^A$。

$P(A) = \{B | B \subseteq A\}$

结论：

对任意集合 $A$，因为 $\varnothing \subseteq A$，$A \subseteq A$，所以有 $\varnothing \in P(A), A \in P(A)$ 。

集合的运算

交运算 $\cap$

$A$、$B$ 是集合，由既属于 $A$，也属于 $B$ 的元素构成的集合，称之为 $A$ 与 $B$ 的交集，记作 $A \cap B$。

谓词定义：

$A \cap B = \{x | x \in A \land x \in B\}$

$x \in A \cap B \Leftrightarrow x \in A \land x \in B$

性质：

1. 幂等律，$A \cap A = A$
2. 交换律，$A \cap B = B \cap A$
3. 结合律，$(A \cap B) \cap C = A \cap (B \cap C)$
4. 同一律，$A \cap E = A$
5. 零律，$A \cap \varnothing = \varnothing$
6. $A \subseteq B \Leftrightarrow A \cap B = A$

并运算 $\cup$

$A$、$B$ 是集合，由或属于 $A$，或属于 $B$ 的元素构成的集合，称之为 $A$ 与 $B$ 的并集，记作 $A \cup B$。

谓词定义：

$A \cup B = \{x | x \in A \lor x \in B\}$

$x \in A \cup B \Leftrightarrow x \in A \lor x \in B$

性质：

1. 幂等律，$A \cup A = A$
2. 交换律，$A \cup B = B \cup A$
3. 结合律，$(A \cup B) \cup C = A \cup (B \cup C)$
4. 同一律，$A \cup \varnothing = A$
5. 零律，$A \cup E = E$
6. 分配率，$A \cap (B \cup C) = (A \cap B) \cup (A \cap C),A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
7. 吸收律，$A \cup (A \cap B) = A,A \cap (A \cup B) = A$
8. $A \subseteq B \Leftrightarrow A \cup B = B$
9. $A \subseteq B \Rightarrow A \cup C \subseteq B \cup C,A \cap C \subseteq B \cap C$
10. $A \subseteq B \land C \subseteq D \Rightarrow A \cup C \subseteq B \cup D,A \cap C \subseteq B \cap D$

差运算 $-$

$A$、$B$ 是集合，由属于 $A$，而不属于 $B$的元素构成的集合，称之为 $A$ 与 $B$ 的差集，或 $B$ 对 $A$ 的相对补集，记作 $A-B$。

谓词定义：

$A - B = \{x | x \in A \land x \not \in B\}$

$x \in A - B \Leftrightarrow x \in A \land x \not \in B$

性质：

1. $A - \varnothing = A$
2. $\varnothing - A = \varnothing$
3. $A - A = \varnothing$
4. $A - B \subseteq A$
5. $A \subseteq B \Leftrightarrow A - B =\varnothing$
6. $A - B = A \Leftrightarrow A \cap B =\varnothing$

绝对补集 $\sim$

$A$ 是集合,由不属于 $A$ 的元素构成的集合，称之为 $A$ 的绝对补集，记作 $\sim A$。实际上 $\sim A = E - A$。

谓词定义：

$\sim A = E - A = \{x | x \in E \land x \not \in A\} = \{x | x\not \in A\}$

$x \in \sim A \Leftrightarrow x \not \in A$

性质：

1. $\sim E = \varnothing$
2. $\sim \varnothing = E$
3. $\sim (\sim A) = A$
4. $A \cap \sim A = \varnothing$
5. $A \cup \sim A = E$
6. $A - B = A \cap \sim B$
7. $\sim (A \cap B) = \sim A \cup \sim B$
8. $\sim (A \cup B) = \sim A \cap \sim B$

对称差 $\oplus$

$A$、$B$ 是集合,由属于 $A$ 而不属于 $B$，或者属于 $B$ 而不属于 $A$ 的元素构成的集合，称之为 $A$ 与 $B$ 的对称差，记作 $A \oplus B$。

谓词定义：

$A \oplus B = (A - B) \cup (B - A) = \{x | (x \in A \land x \not \in B) \lor (x \in B \land x \not \in A)\}$

$A \oplus B = (A \cup B) - (A \cap B)$

性质：

1. 交换律，$A \oplus B = B \oplus A$
2. 结合律，$(A \oplus B) \oplus C = A \oplus (B \oplus C)$
3. 同一律，$A \oplus \varnothing = A$
4. $A \oplus A = \varnothing$

序偶与集合的笛卡尔积

序偶与有序 $n$ 元组

由两个对象 $x$、$y$ 组成的序列称为有序二元组，也称之为序偶，记作 $\langle x,y \rangle$；称 $x$、$y$ 分别为序偶 $\langle x,y \rangle$ 的第一，第二元素。

注意，序偶 $\langle x,y \rangle$ 与集合 $\{x,y\}$不同：

序偶 $\langle x,y \rangle$：元素 $x$ 和 $y$ 有次序；

集合 $\{x,y\}$：元素 $x$ 和 $y$ 的次序是无关紧要的。

设 $\langle x,y \rangle$，$\langle u,v \rangle$ 是两个序偶，如果 $x = u$ 和 $y = v$，则称 $\langle x,y \rangle$ 和 $\langle u,v \rangle$ 相等， 记作 $\langle x,y \rangle = \langle u,v \rangle$。

有序 $n$ 元组是一个序偶，其第一个元素本身是个有序 $n-1$ 元组,记作 $\langle $。且可 以简记成 $\langle x_1 , x_2 ,\cdots, x_{n-1}, x_n \rangle$。

$\langle x_1, x_2 ,\cdots, x_n \rangle = \langle y_1, y_2 ,\cdots, y_n \rangle \Leftrightarrow (x_1 = y_1) \land ( x_2 = y_2) \land \cdots \land ( x_n = y_n)$

集合的笛卡尔积

设 $A$、$B$ 是集合，由 $A$ 的元素为第一元素，$B$ 的元素为第二元素组成序偶的集合，称为 $A$ 和 $B$ 的笛卡尔积，记作 $A \times B$，即 $A \times B=\{\langle x,y \rangle | x \in A \land y \in B\}$

性质：

1. 如果 $A$、$B$ 都是有限集，且 $|A| = m, |B| = n$， 则 $|A \times B | = mn$.
2. $A \times \varnothing = \varnothing \times B = \varnothing$
3. 分配律：
   1. $A \times (B \cup C) = (A \times B) \cup (A \times C)$
   2. $A\times (B \cap C) = (A \times B) \cap (A \times C)$
   3. $(A \cup B) \times C = (A \times C) \cup (B \times C)$
   4. $(A \cap B) \times C = (A \times C) \cap (B \times C)$
4. 若 $C \not = \varnothing$，$A \subseteq B \Leftrightarrow (A \times C \subseteq B \times C) \Leftrightarrow (C \times A \subseteq C \times B)$
5. 设 $A$、$B$、$C$、$D$ 为非空集合，则 $A\times B \subseteq C \times D \Leftrightarrow A \subseteq C \land B\subseteq D$

优先权

关系及其表示法

关系

设 $A$、$B$ 是集合，如果 $R \subseteq A \times B$，则称 $R$ 是一 个从 $A$ 到 $B$ 的二元关系。

如果 $R\subseteq A \times A$，则称 $R$ 是 $A$ 上的二元关系。

二元关系简称为关系。

任何序偶的集合，都称之为一个二元关系。

列举法和描述法。

$xRy$ 表示有关系 $R$。

$x \not R y$ 表示无关系 $R$。

关系的定义域与值域

定义域：设 $R \subseteq A \times B$，称集合 $\rm{dom} R = \{x | \exists y (\langle x,y \rangle \in R)\}$ 为 $R$ 的定义域。

值域：设 $R \subseteq A \times B$，称集合 $\rm{ran} R = \{y | \exists x (\langle x,y \rangle \in R)\}$ 为 $R$ 的值域。

关系的域：$\rm{fid} R = \rm{dom} R \cup \rm{ran} R$

结论：$\rm{dom} R \subseteq A,\rm{ran} R \subseteq B$

关系的另两种表示法

1. 有向图法：

   $R \subseteq A \times B$（$A$、$B$ 非空、有限），用两组小圆圈（称为结点）分别表示 $A$ 和 $B$ 的元素，当 $\langle x,y \rangle \in R$ 时，从 $x$ 到 $y$ 引一条有向弧（边）（由 $x$ 指向 $y$）。这样得到的图形称为 $R$ 的关系图。 如 $R \subseteq A \times A$，即 $R$ 是集合 $A$ 中关系时，用一组小圆圈表示 $A$ 中的元素，若 $\langle x,x \rangle \in R$，则从 $x$ 到 $x$ 画一条有向环（自回路）。

2. 矩阵表示法：

   非空有限集合之间的关系也可以用矩阵来表示，这种表示法便于用计算机来处理关系。

   设 $A=\{a_1, a_2, \cdots , a_m\}$，$B=\{b_1, b_2, \cdots, b_n\}$ 是个有限集，$R \subseteq A \times B$，定义 $R$ 的 $m \times n$ 阶矩阵 $M_R=(r_{ij})_{m\times n}$，其中：

   $$
   r_{ij}=
   \left\lbrace
   \begin{array}{cc}
   1 & \langle a_i,b_j \rangle \in R\\
   0 & \langle a_i,b_j \rangle \not \in R
   \end{array}
   \right.
   (1 \le i \le m,1 \le j \le n)
   $$
   称 $M_R$ 为关系 $R$ 的关系矩阵。

 离散数学 笔记