一、一阶谓词逻辑

• 个体：可以独立存在的客体称为个体。

  • 个体常项：一般记为 $a, b, c$ ……
  • 个体变项：一般记为 $x, y, z$……
  • 个体域：个体的取值范围，记为 $D$。如果不特别规范，为全总个体域。

• 谓词：用来刻画个体性质或个体之间关系的词称为谓词。一般记为 $F, G, H$……

  • 一元谓词：一般指 $x$ 具有性质 $F$，表示为 $F(x)$。
  • 二元谓词：一般指 $x, y$ 具有关系 $F$，表示为 $F(x,y)$。eg. 小李比小赵高 2 厘米。
  • 当所有的个体变量没有得到指定时，谓词并不能判断真假。
    • 零元谓词：就是命题，能直接判断真假的陈述句。

• 量词：

  • 有全称量词 $\forall$ 和存在量词 $\exists$。

    比如：

    • D 为人类集合。F(x)：x是要死的。G(x)：能活到百岁以上。于是有命题公式：

      • $\forall (x\in D)F(x)$：所有人都是要死的。
      • $\exists (x \in D)G(x)$：有的人能活到百岁以上。

    • 如果用全总个体域，则必须引入特性谓词，如 M(x)：x是人。

      对应的命题是 $\forall x (M(x) \rightarrow F(x))$，$\exists x (M(x) \wedge G(x))$。

      • 这说明受限的全称量化和一个蕴含式的全称量化相等价。受限的存在量化和一个合取式的存在量化等价。
      • 关于为什么「有的人能活到百岁以上」不是 $\exists x (M(x) \to G(x))$，因为如果这么表述的话，哪怕所有的人都不能活到百岁以上，只要 D 中有任意不是人的东西 $c$ 存在，$M(c)$ 为假，$M(c) \to G(c)$ 就为真，$\exists x (M(x) \to G(x))$ 就为真；这显然与初衷「有的人能活到百岁以上」不符。

    拓展：唯一性量词 $\exists!$

    存在唯一的，有且仅有一个。但可以通过已有量词进行定义：

    $\exists ! x P(x) \Leftrightarrow \exist x (P(x) \wedge \forall u((u \neq x) \to \neg P(u)))$

  • $\forall xA, \exist xA$ 这类东西，称 $x$ 为指导变项，$A$ 为量词的辖域（作用域）。作用域中 $x$ 的所有出现称为约束出现的（约束变项），其他非受量词约束的变项为自由出现的（自由变项）。

    e.g. $(\forall x)(F(x) \rightarrow G(x, y)) \wedge H(x, y)$，有约束 x、自由 x、自由 y 三个变项。

  • 如约束变项和自由变项命名冲突，为了看起来方便，要么换掉约束项名字（换名规则），要么换掉自由项名字（代替规则）。

• 合式公式（一阶谓词命题公式）：谓词通过 $\neg, \vee, \wedge, \rightarrow, \leftrightarrow , (), \forall x, \exists x$ 所构成的公式。

  • 量词的优先级比所有逻辑运算符都要高。
    • 比如 $\forall xP(x) \vee Q(x)$ 表示 $(\forall xP(x)) \vee Q(x)$ 而非 $\forall x(P(x) \vee Q(x))$。
  • 合式公式中若无自由变项，则称为闭式，其是可被判断真假的命题。

  拓展：高阶谓词（广义的谓词逻辑）

  一阶逻辑，谓词变元的主目（对象）目前只用于个体变元，如果它能用于命题变元和谓词变元，那么便构成高阶逻辑。

  e.g. 数学归纳法： 对于任何公式F(x)：头符合、可递推，便搞起来。

  $\forall F((F(0) \wedge \forall x(F(x)\rightarrow F(x+1)))\rightarrow \forall x (F(x)))$

• 谓词公式的解释（赋值）

  • 一个解释要用非空个体域 $D$ 范畴下，一些特定的元素、函数、谓词来描述。

    解释的一个例子

    命题公式 $A$ 为：$\forall x(F(x) \wedge G(x, a))$

    赋予如下解释 $I$（注意0, 1是在表示真假哦）：$D=\{2, 3\}, \ \ a = 2, \ \ F:F(2)=0, F(3)=1, \ \ G:G(i, j)\equiv 1, \ \ i=2, \ \ j=3$。

    这样有：$A \Leftrightarrow \forall x(F(x) \wedge G(x, 2)) \Leftrightarrow (F(2) \wedge G(2, 2)) \wedge (F(3) \wedge G(3, 2)) \Leftrightarrow (0\wedge1)\wedge(1\wedge1) \Leftrightarrow 0$

    结果是假的，也就是式子 $A$ 在解释 $I$ 下是假的。

  • 谓词公式在任意解释下的永真、永假、可满足性，其判断相当于解决宇宙问题。不过仍然，特殊情况下可以有一些规律。

    e.g. $\forall x(F(x)) \rightarrow (\exists x\exists y(G(x, y)) \rightarrow \forall x(F(x)))$ 即 $p \rightarrow (q \rightarrow p)$ ，它永真。

二、一阶逻辑的等值

1. 一阶逻辑的基本等值式

i. 在有限个体域中消去量词

• 若个体域为有限集合 $D = \{a_1, a_2, \cdots a_n\}$ ，则：
  • $\forall (x\in D) F(x) \Leftrightarrow F(a_1) \wedge F(a_2) \wedge \cdots \wedge F(a_n)$；
  • $\exists (x \in D) F(x) \Leftrightarrow F(a_1) \vee F(a_2) \vee \cdots \vee F(a_n)$。

ii. 量词的否定（量词的德·摩根律）

• $\neg \forall x A(x) \Leftrightarrow \exists x (\neg A(x))$
• $\neg \exists x A(x) \Leftrightarrow \forall x (\neg A(x))$

iii. 量词辖域的收缩和扩张（空量化，受约束变量没有出现在某一部分时可以使用）

• 前 4 个式子：

  • $\forall x (F(x) \wedge G) \Leftrightarrow \forall xF(x) \wedge G$
  • $\forall x (F(x) \vee G) \Leftrightarrow \forall xF(x) \vee G$
  • $\forall x (F(x) \rightarrow G) \Leftrightarrow \exists xF(x) \to G$
  • $\forall x (G \rightarrow F(x)) \Leftrightarrow G \to \forall x F(x)$

  <aside> 📌 推导：

  1. $\forall x (F(x) \wedge G) \xLeftrightarrow{x \in \{a, b\}} (F(a) \wedge G) \wedge (F(b) \wedge G) \Leftrightarrow ((F(a) \wedge F(b)) \wedge G) \Leftrightarrow \forall xF(x) \wedge G$
  2. ..
  3. $\forall x (F(x) \rightarrow G) \Leftrightarrow \forall x (\neg F(x) \vee G) \Leftrightarrow \forall x \neg F(x) \vee G \Leftrightarrow \neg \exists x F(x) \vee G \Leftrightarrow \exists xF(x) \to G$ </aside>

• 把 $\exists, \forall$ 反过来得到后 4 个式子。

iv. 量词交换律

• $\forall x \forall y F(x, y) \Leftrightarrow \forall y \forall x F(x, y)$
• $\exists x \exists y F(x, y) \Leftrightarrow \exists y \exists x F(x, y)$
• 但是不一样的量词就不能交换。比如 $\forall x, \forall y, \exists z, x+y=z$ 是真命题，而 $\exists z, \forall x, \forall y, x+y=z$ 是假命题。

v. 量词分配律

• $\forall x (A(x) \wedge B(x)) \Leftrightarrow (\forall xA(x)) \wedge (\forall xB(x))$，即全称量词对 $\wedge$ 有分配律。
• $\exists x (A(x) \vee B(x)) \Leftrightarrow (\forall xA(x)) \vee (\exists xB(x))$，即存在量词对 $\vee$ 有分配律。

证明：认为论域是 $D = \{ a, b \}$。

例子

• e.g. 没有不吃饭的人===人都是要吃饭的。 M(x): x是人。 F(x): x需要吃饭。

  $\neg \exists x(M(x) \wedge \neg F(x)) \Leftrightarrow \forall x(M(x) \rightarrow F(x))$

• e.g. 素数不全是奇数===存在偶素数。 F(x): x是素数。G(x): x是奇数。

  $\neg \forall x(F(x) \rightarrow G(x)) \Leftrightarrow \exists x(F(x) \wedge \neg G(x))$

2. 前束范式

• 形如 $Q_1 x_1 (Q_2 x_2 (\cdots (Q_k x_k A(x_1, x_2, \cdots, x_k))\cdots))$ 形态的一阶公式。就是把量词全部放到最外面。通过基本等值式和换名规则可以得到前述范式。

例子

• e.g. 每个自然数都有后继自然数。M(x): x是自然数， F(x, y): y是x的后继数。

  $\forall x (M(x) \rightarrow \exists y (M(y) \wedge F(x, y)))$

  也可以写成 $\forall x \exists y (M(x) \rightarrow (M(y) \wedge F(x, y)))$

• 又一个例子，里面换名是因为 $\forall$ 对 $\vee$ 没有分配律。

  

三、一阶谓词的推理

1. 四个消去或引入量词的规则