<离散数学>DM1 逻辑关系

DM1 逻辑关系

DM1.1 联结词

具有唯一真值的陈述句称为 命题（语句）。真值为真的称为 真命题，真值为假的称为 假命题。

有的陈述句的真假是变化的，这些陈述句不是命题。有的命题的真假无法判断，但只要真值唯一就是命题。

命题为真时，其真值用 T 或 1 表示。假命题用 F 或 0 表示。

数理逻辑中常用的联结词有以下几种。下面的 $p$、$q$、$r$ 表示原子命题（简单命题、变元、常元）

• $¬p$：否定联结词（非运算）

  p	¬p
  1	0
  0	1

• $p∧ q$：合取联结词（与运算）

  p	q	p∧q
  0	0	0
  0	1	0
  1	0	0
  1	1	1

• $p∨ q$：析取联结词（或运算）

  p	q	p∨q
  0	0	0
  0	1	1
  1	0	1
  1	1	1

• $p→q$：蕴含联结词（$p$ 是 $q$ 的充分条件，$q$ 是 $p$ 的必要条件）

  p	q	p→q
  0	0	1
  0	1	1
  1	0	0
  1	1	1

  如果认为所有猫都爱睡觉，也就是说：如果有一只猫（$p$），那么这只猫喜欢睡觉（$p→ q$）。

  这样的话：

  如果不是一只猫（$p=0$），那么它可以不爱睡觉（$q=0$），也可以爱睡觉（$q=1$）

  如果是一只猫（$p=1$），那么它不可以不爱睡觉（$q=0$），只可以爱睡觉（$q=1$）

• $p↔q$：等价联结词（等于，充分必要条件）

  p	q	p↔q
  0	0	1
  0	1	0
  1	0	0
  1	1	1

另外，还有几个复合命题：

• $p↑ q$：与非联结词。即 $¬(p∧ q)$
• $p↓ q$：或非联结词。即 $¬(p∨ q)$

DM1.2 命题公式

单个命题变元（或常元）是命题公式。

若 $p$、$q$ 是命题公式，那么 $¬p$、$p∧ q$、$p∨ q$、$p→q$、$p↔q$ 都是命题公式。命题公式的长度是有限的。

联结词的优先级是： $¬$、$∧$、$∨$、$→$、$↔$

将值永远为 $0$ 的命题公式称为矛盾式（永假式），如 $p ∧ ¬p$

将值可能为 $1$ 的命题公式称为可满足式。

将值永远为 $1$ 的命题公式称为重言式（永真式），如 $p∧(p∨ q)↔p$。永真式是可满足式的一种

• 小项（布尔合取、极小项）：n 个命题变元的简单合取式。

  每个命题变元与其否定不能同时存在，并要出现且仅出现一次。

  n 个命题变元能产生 $2^n$ 个小项。可以字母 m 及下标二进制数表示命题变元。

  如：对于命题 $P_1,P_2,P_3$，其小项 $m_{101}=P_1∧\neg P_2∧ P_3$

  可见，每个小项有一个编码，且仅在唯一情况下为真。而且，不同小项的成真赋值（指派）不同。

• 大项（布尔析取、极大项）：n 个命题变元的简单析取式。

  每个命题变元与其否定不能同时存在，并要出现且仅出现一次。

  大项性质与小项类似，以字母 $M$ 及其二进制下标表示。每个大项有一个编码，且仅在唯一情况下为假。

• 主析取范式：仅由小项析取组成的，原命题公式的等价公式，称为主析取范式。

  在主式真值表中，所有真值为真的小项的析取，即构成主析取范式。

  任何命题公式都存在唯一的主析取范式。

• 主合取范式：仅由大项合取组成的，原命题公式的等价公式，称为主合取范式。

  在主式真值表中，所有真值为假的大项的合取，即构成主合取范式。

  任何命题公式都存在唯一的主合取范式。

• 完备集：对于联结词集合 $S$，若任何真值函数都能用 $S$ 中联结词表示，则称 $S$ 是一个完备集。

  可以证明，$\{∧,¬\}$ 与 $\{∨,¬\}$ 都是完备集。此外，$\{↑\}$ 和 $\{↓\}$ 也是完备集。

DM1.3 等值式

等值式：如果 $p↔q$ 是永真式，则 $p⇔q$，表示 $p$ 与 $q$ 的取值完全相同，可以互相代替

p	q	p→q	¬p∨q	(p→q)↔(¬p∨q)
0	0	1	1	1
0	1	1	1	1
1	0	0	0	1
1	1	1	1	1

$∴p→q⇔¬p∨q$

基本的等值式

• 幂等率：$p⇔p∨ p{\qquad}p⇔p∧ p$

• 交换律：$p∨ q⇔p∨ q{\qquad}p∧ q⇔q∧ p$

• 结合律：$(p∨ q)∨ r⇔p∨(q∨ r){\qquad}(p∧ q)∧ r⇔p∧(q∧ r)$

• 分配律：$p∨(q∧ r)⇔(p∨ q)∧(p∨ r){\qquad}p∧(q∨ r)⇔(p∧ q)∨(p∧ r)$

• 德·摩根律：$¬(p∨ q)⇔¬p∧ ¬q{\qquad}¬(p∧ q)⇔¬p∨ ¬q$

• 吸收律：$p∨(p∧ q)⇔p{\qquad}p∧(p∨ q)⇔p$

• 零律：$p∨1⇔1{\qquad}p∧0⇔0$

• 同一律：$p∨0⇔p{\qquad}p∧1⇔p$

• 排中律：$p∨¬p⇔1$

• 矛盾律：$p∧¬p⇔0$

• 双重否定律：$¬¬p⇔p$

• 蕴含等值式：$p→q⇔¬p∨q$

• 等价等值式：$p↔q⇔(p→q)∧(q→p)$

• 等价否定等值式（否命题）：$p↔q⇔¬p↔¬q$

• 假言易位（逆否）：$p→q⇔¬q→¬p$

• 归谬论（反证法）：$(p→q)∧(p→¬q)⇔¬p$

DM1.4 命题逻辑推理

前提：$A_1，A_2，A_3,...，A_k$

结论：$B$

推理的形式结构：$(A_1∧ A_2∧ A_3∧ ... ∧ A_k)→B$

如果 $A→B$ 是永真式，则可以记为 $A⇒B$

重要的推理定律

• 附加律：$A⇒(A∨ B)$

• 化简律：$(A∧ B)⇒A{\qquad}(A∧ B)⇒B$

• 假言推理：$(A→B)∧ A⇒B$

• 拒取式：$(A→B)∧ ¬B⇒¬A$

• 析取三段论：$(A∨ B)∨¬A⇒B{\qquad}(A∨ B)∨¬B⇒A$

• 假言三段论：$(A→B)∧(B→C)⇒(A→C)$

• 等价三段论：$(A↔B)∧(B↔C)⇒(A↔C)$

• 构造性两难：$(A→B)∧(C→D)∧(A∨ C)⇒(B∨ D)$

DM1.5 谓词

基本概念

• 个体：表示客体的词。

  使用 $a,b,c,\ldots$ 表示 个体常元，使用 $x,y,z,\ldots$ 表示 个体变元。

  个体的函数仍是个体。将个体变元的取值范围称为 个体域。

• 谓词：表示个体间关系或性质的词。

  常用 $F,G,H,\ldots$ 表示 谓词常元 或 谓词变元。

  $F(x)$ 表示 $x$ 具有性质 $F$。如：$F(x)$ 表示 " 是黑色的"，而 $a$ 表示 “黑板”，则 $F(a)$ 表示 “黑板是黑色的”

  $F(x,y)$ 表示 $x$ 和 $y$ 具有关系 $F$。如：$F(x,y)$ 表示 “$x>y$”，则 $F(5,2)$ 表示 $5>2$

• 量词：表示数量的词

  全称量词：$∀$ 表示任意、全部。如：$∀x$ 表示个体域中的所有 $x$；$∀xF(x)$ 表示个体域中所有 $x$ 都有性质 $F$

  存在量词：$∃$ 表示存在、有一个。如：$∃x$ 表示存在个体域里的 $x$；$∃xF(x)$ 表示在个体域中存在 $x$ 有性质 $F$

命题符号化

一阶逻辑中命题逻辑化的两个基本公式：

• $∀x(F(x)→ G(x))$

  个体域中所有具有性质 $F$ 的个体都具有性质 $G$

• $∃x(F(x)∧ G(x))$

  个体域中存在同时具有性质 $F$ 和性质 $G$ 的个体

一阶谓词逻辑公式及其分类

一阶谓词逻辑公式，简称公式。其形成逻辑类似于命题逻辑公式。而且，$A$ 是公式时，$∀xA$ 及 $∃xA$ 也是公式

在公式 $∀xA$ 及 $∃xA$ 中，称 $x$ 为 指导变元，称 $A$ 为相应量词的 辖域。在该辖域中，$x$ 的所有出现都是 约束出现。所有非约束出现的变元都是 自由出现

解释

对于给定的公式 $A$，如果指定 $A$ 的个体域是已知的 $D$，使用特定的个体常元取代 $A$ 中的个体常元，用特定函数取代 $A$ 中的函数变元，用特定的谓词取代 $A$ 中的谓词变元，就构成了 $A$ 的一个解释。

一个公式 $A$ 可以有多种解释。当给出一种解释后，就能判断该解释的真假。

若 $A$ 在任何解释下都为真，称之为永真式。还有永假式、可满足式。

若 $A↔ B$ 是永真式，则称 $A$ 与 $B$ 等值，记为 $A⇔B$，并称之为等值式。

以下是一些基本的等值式

• 在有限个体域 $D=\lbrace a_1,a_2,\ldots,a_n\rbrace$ 中消去量词等值式

  $\quad ∀xA(x)⇔A(a_1)∧ A(a_2)∧ \ldots ∧ A(a_n)$

  $\quad ∃xA(x)⇔A(a_1)∨ A(a_2)∨ \ldots ∨ A(a_n)$

• 量词否定等值式

  $\quad ¬∀xA(x)⇔∃x¬A(x)$

  $\quad ¬∃xA(x)⇔∀x¬A(x)$

• 量词辖域收缩和扩张等值式（$B$ 中不含 $x$）

  $\quad ∀x(A(x)∨ B)⇔∀xA(x)∨ B$

  $\quad ∃x(A(x)∨ B)⇔∃xA(x)∨ B$

  $\quad ∀x(A(x)∧ B)⇔∀xA(x)∧ B$

  $\quad ∃x(A(x)∧ B)⇔∃xA(x)∧ B$

  $\quad ∀x(A(x)→ B)⇔∃xA(x)→ B$

  $\quad ∃x(A(x)→ B)⇔∀xA(x)→ B$

  $\quad ∀x(B→ A(x))⇔B→ ∀xA(x)$

  $\quad ∃x(B→ A(x))⇔B→ ∃xA(x)$

• 量词分配等值式

  $\quad ∀x(A(x)∧ B(x))⇔∀xA(x)∧ ∀B(x)$

  $\quad ∃x(A(x)∨ B(x))⇔∃xA(x)∨ ∃B(x)$

前束范式

若公式具有形式 $Q_1 x_1 Q_2 x_2\ldots Q_k x_k B$，则称其为 前束范式。其中 $Q_i(i\le i \le k)$ 为 $∃$ 或 $∀$，$B$ 中不含量词

换名规则：将公式 $A$ 中某量词辖域中出现的某个约束的个体变元及相应指导变元 $x_i$ 都改成公式中没有出现过的 $x_j$，所得公式 $A'⇔A$

一些重要的推理定律（注意：不是等值式）

• $∀xA(x)∨ ∀xB(x)⇒∀xA(x)∨ B(x)$
• $∃x(A(x)∧ B(x))⇒∃xA(x)∧ ∃xB(x)$
• $∀x(A(x)→ B(x))⇒∀xA(x)→ ∀xB(x)$
• $∀x(A(x)→ B(x))⇒∃xA(x)→ ∃xB(x)$