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

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

Contents

谓词演算的推理理论

推理方法

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

所用公式

等价式、蕴含式

推理规则

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$。

谓词定义

21

性质

对任何集合 $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$

优先权

22

关系及其表示法

关系

设 $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$ 的关系矩阵。

 

点赞 0

No Comments

Add your comment