WonderU
离散数学

4.谓词逻辑

1.谓词逻辑中的基本概念与表示

  • 谓词逻辑命题符号化的3个基本要素：个体词、谓词、量词

个体词

  • 个体词：研究对象中可以独立存在的具体的或抽象的客体，如：小智，中国。
    • 个体常项：表示具体或特定的客体的个体词
    • 个体变项：表示抽象或泛指的个体词
    • 个体域(论域)：个体变项的取值范围
    • 全总个体域：由宇宙间一切事物组成的个体域

谓词

  • 刻画个体词性质及个体词之间的相互关系的词。

    例：

    1. 44 是有理数，“是有理数”是谓词，记为FF，表示为：
    2. xx 是有理数，“是有理数”是谓词，记为FF，表示为：
    3. 小霞和小智是同学，“和…是同学”是谓词，记为HH，aa表示小霞，bb表示小智，表示为 H(a,b)H(a, b)

量词

  • 个体之间数量关系的词。

    • 全称量词：∀\forall

      ∀x\forall x 表示个体域中所有的xx。对应汉语：一切的，所有的，每一个，任意的，凡，都 …

    • 存在量词：∃\exists

      ∃x\exists x 表示个体域中有一个个体xx。对应汉语：存在，有一个，有的，至少有一个 …

2.谓词合式公式与解释

  • 在公式 ∀xA\forall x A 和 ∃xA\exists x A 中，称 xx 为指导变元，AA 为量词的辖域。
  • 在 ∀x\forall x 和 ∃x\exists x 的辖域中，xx 的所有出现都称作约束出现； AA 中不是约束出现的其他变项均称作自由出现。
    • 例1：∀x(F(x,y)→G(x,z))\forall x(F(x, y) \to G(x, z))
      xx 是指导变元，∀\forall 的辖域 A=(F(x,y)→G(x,z))A=(F(x, y) \to G(x, z))。
      在 AA 中，xx 是约束出现，约束出现两次；yy 和 zz 均为自由出现，各自由出现一次。
    • 例2：∀x(F(x)→G(y))→∃y(H(x)∧L(x,y,z))\forall x(F(x) \to G(y)) \to \exists y(H(x) \land L(x, y, z))
      ∀\forall 的指导变元为 xx，∀\forall 的辖域为 (F(x)→G(y))(F(x) \to G(y))，xx 是约束出现，yy 是自由出现。
      ∃\exists 的指导变元为 yy，∃\exists 的辖域为 (H(x)∧L(x,y,z))(H(x) \land L(x, y, z))，yy 是约束出现，x,zx,z均为自由出现。 设 AA 为一公式：
    1. 若 AA 在任何情况下的任何赋值下均为真，则称 AA 为永真式（逻辑有效式）。
    2. 若 AA 在任何情况下的任何赋值下均为假，则称 AA 为矛盾式（永假式）。
    3. 若至少存在一个情况下的一个赋值使 AA 为真，则称 AA 是可满足式。

    注：当多个量词出现时，它们的顺序一般不能随意调换，如 ∀x∃y\forall x\exists y 与 ∃y∀x\exists y\forall x 含义不同。 设 AA , BB 是谓词逻辑中任意两个公式，若 A↔BA \leftrightarrow B 是永真式，则称 AA 与 BB 等值，记作 A⇔BA \Leftrightarrow B，称 A⇔BA \Leftrightarrow B 是等值式。

量词否定等值式

  1. ¬∀xA(x)⇔∃x¬A(x)\neg \forall x A(x) \Leftrightarrow \exists x \neg A(x) \
  2. ¬∃xA(x)⇔∀x¬A(x)\neg \exists x A(x) \Leftrightarrow \forall x \neg A(x)

量词辖域收缩与扩张等值式

  1. ∀x(A(x)∨B)⇔∀xA(x)∨B\forall x(A(x) \vee B) \Leftrightarrow \forall x A(x) \vee B
    ∀x(A(x)∧B)⇔∀xA(x)∧B\forall x(A(x)\land B)\Leftrightarrow \forall xA(x)\land B
    ∀x(A(x)→B)⇔∃xA(x)→B\forall x(A(x)\to B)\Leftrightarrow \exists xA(x)\to B
    ∀x(B→A(x))⇔B→∀xA(x)\forall x(B\to A(x))\Leftrightarrow B\to \forall xA(x)
  2. ∃x(A(x)∨B)⇔∃xA(x)∨B\exists x(A(x) \vee B) \Leftrightarrow \exists xA(x) \vee B
    ∃x(A(x)∧B)⇔∃xA(x)∧B\exists x(A(x) \land B) \Leftrightarrow \exists x A(x) \land B
    ∃x(A(x)→B)⇔∀xA(x)→B\exists x(A(x)\to B)\Leftrightarrow \forall xA(x)\to B
    ∃x(B→A(x))⇔B→∃xA(x)\exists x(B\to A(x))\Leftrightarrow B\to \exists xA(x)

量词分配等值式

  1. ∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)\forall x(A(x) \land B(x)) \Leftrightarrow \forall x A(x) \land \forall x B(x)
  2. ∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)\exists x(A(x) \vee B(x)) \Leftrightarrow \exists xA(x) \vee \exists x B(x)
  3. ∀xA(x)∨∀xB(x)⇒∀x(A(x)∨B(x))\forall x A(x) \vee \forall x B(x) \Rightarrow \forall x(A(x) \vee B(x))
  4. ∃x(A(x)∧B(x))⇒∃xA(x)∧∃xB(x)\exists x(A(x) \land B(x)) \Rightarrow \exists x A(x) \land \exists x B(x)

命题逻辑中的重言式的代换实例 都是谓词逻辑中的永真式

  1. ∀xF(x)⇔¬¬∀xF(x)\forall x F(x) \Leftrightarrow \neg \neg \forall x F(x)
  2. ∀x∃y(F(x,y)→G(x,y))⇔¬¬∀x∃y(f(x,y)→G(x,y))\forall x \exists y(F(x,y) \rightarrow G(x,y) ) \Leftrightarrow \neg \neg \forall x \exists y(f(x,y) \rightarrow G(x,y))
  3. F(x)→G(y)⇔¬F(x)∨G(y)F(x)\to G(y)\Leftrightarrow \neg F(x)\lor G(y)
  4. ∀x(F(y)→G(y))→∃zH(z)⇔¬∀x(F(x)→G(y))∨∃zH(z)\forall x(F(y) \to G(y)) \to \exists z H(z) \Leftrightarrow \neg \forall x(F(x) \to G(y)) \vee \exists z H(z)

3.公式的标准型‑范式

前束范式

  • 具有形如 Q1x1Q2x2...QkxkBQ_{1} x_{1} Q_{2} x_{2} ... Q_{k} x_{k} B 的谓词逻辑公式。 其中 Qi(1≤i≤k)Q_{i}(1 ≤i ≤k) 为量词 ∀\forall 或 ∃\exists，辖域 BB 中不含量词。
    • 例：
      1. ∀x∀y(F(x)∧G(y)→H(x,y))\forall x \forall y(F(x) \land G(y) \to H(x, y)) 是前束范式。
      2. ∀x(F(y)→∃y(G(y)∧H(x,y)))\forall x(F(y) \to \exists y(G(y) \land H(x, y))) 不是前束范式。

前束范式存在定理：

  • 谓词逻辑中的任何公式都存在等值的前束范式。

转为前束范式的步骤

  1. 把条件或双条件联结词转化
  2. 利用量词否定公式，把否定深入到命题变元和谓词公式的前面
  3. 换名
  4. 利用量词作用域的扩张和收缩等价式，把量词提到前面
  • 例1：∀xF(x)∧¬∃xG(x)\forall x F(x) \land \neg \exists x G(x)
    ∀xF(x)∧¬∃xG(x)⇔ ∀xF(x)∧∀x¬G(x)⇔ ∀xF(x)∧∀y¬G(y)⇔ ∀x∀y(F(x)∧¬G(y)) \begin{align*} &\forall xF(x) \land\neg\exists xG(x) \\ \Leftrightarrow\ &\forall xF(x) \land\forall x\neg G(x) \\ \Leftrightarrow\ &\forall xF(x) \land\forall y\neg G(y) \\ \Leftrightarrow\ &\forall x\forall y\big(F(x) \land\neg G(y)\big) \end{align*}
  • 例2：∀x1F(x1,x2)→∃x2G(x2)\forall x_{1} F\left(x_{1}, x_{2}\right) \to \exists x_{2} G\left(x_{2}\right)
    ∀x1F(x1,x2)→∃x2G(x2)⇔ ¬∀x1F(x1,x2)∨∃x2G(x2)step1 联结词转化⇔ ∃x1¬F(x1,x2)∨∃x2G(x2)step2⇔ ∃x1¬F(x1,x2)∨∃x3G(x3)step3 换名⇔ ∃x1∃x3(¬F(x1,x2)∨G(x3))step4 量词作用域化 \begin{align*} &\forall x_{1}F(x_{1},x_{2})\to \exists x_{2}G(x_{2}) \\ \Leftrightarrow\ &\neg \forall x_{1}F(x_{1},x_{2})\lor \exists x_{2}G(x_{2}) \quad \text{step1 联结词转化}\\ \Leftrightarrow\ &\exists x_{1}\neg F(x_{1},x_{2})\lor \exists x_{2}G(x_{2}) \quad \text{step2}\\ \Leftrightarrow\ &\exists x_{1}\neg F(x_{1},x_{2})\lor \exists x_{3}G(x_{3}) \quad \text{step3 换名}\\ \Leftrightarrow\ &\exists x_{1}\exists x_{3}\big (\neg F(x_{1},x_{2})\lor G(x_{3})\big ) \quad \text{step4 量词作用域化} \end{align*}

4.谓词逻辑的推理理论

  • 在谓词逻辑中，从前提 A1,A2,...,AkA_{1}, A_{2}, ..., A_{k} 出发推出结论 BB 的推理的形式结构采用如下的蕴含式形式： A1∧A2∧⋯∧Ak→BA_{1} \land A_{2} \land \cdots \land A_{k} \to B
    • 缩写说明：
      • US：全称特指规则
      • ES：存在特指规则
      • UG：全称推广规则
      • EG：存在推广规则

命题逻辑推理定律的代换实例

1. ∀xF(x)∧∀yG(y)⇒∀xF(x)\forall x F(x) \land \forall y G(y) \Rightarrow \forall x F(x) A∧B⇒AA \land B \Rightarrow A
2. ∀xF(x)⇒∀xF(x)∨∃yG(y)\forall x F(x) \Rightarrow \forall x F(x) \vee \exists y G(y) A⇒A∨BA \Rightarrow A \vee B

由基本等值式生成的推理实例

1. ∀xF(x)⇒¬¬∀xF(x)\forall x F(x) \Rightarrow \neg \neg \forall x F(x) A⇔¬¬AA \Leftrightarrow \neg \neg A
2. ¬¬∀xF(x)⇒∀xF(x)\neg \neg \forall x F(x)\Rightarrow \forall x F(x) <br />
3. ¬∀xF(x)⇒∃x¬F(x)\neg \forall x F(x) \Rightarrow \exists x \neg F(x) ¬∀xA(x)⇔∃x¬A(x)\neg \forall x A(x) \Leftrightarrow \exists x \neg A(x)
4. ∃x¬F(x)⇒¬∀xF(x)\exists x \neg F(x) \Rightarrow \neg \forall x F(x) ¬∃xA(x)⇔∀x¬A(x)\neg \exists x A(x) \Leftrightarrow \forall x \neg A(x)

一些常用的重要推理定律

  1. ∀x(A(x)→B(x))⇒∀xA(x)→∀xB(x)\forall x(A(x) \to B(x)) \Rightarrow \forall x A(x) \to \forall x B(x) \
  2. ∀x(A(x)→B(x))⇒∃xA(x)→∃xB(x)\forall x(A(x) \to B(x)) \Rightarrow \exists x A(x) \to \exists x B(x)

4条消去量词和引入量词的规则

  1. 全称量词消去规则(US：∀−\forall-)：∀xG(x)⇒G(c)\forall x G(x) \Rightarrow G(c)
  2. 存在量词消去规则(ES：∃−\exists-)：∃xG(x)⇒G(c)\exists x G(x) \Rightarrow G(c)
  3. 全称量词引入规则(UG：∀+\forall+)：G(c)⇒∀xG(x)G(c) \Rightarrow \forall x G(x)
  4. 存在量词引入规则(EG：∃+\exists+)：G(c)⇒∃xG(x)G(c) \Rightarrow \exists x G(x)

注意：(∃−)(\exists-) 一定在 (∀−)(\forall-) 前面。

  • 例1：前提：∀x(F(x)→G(x)), ∃x(F(x)∧H(x))\forall x(F(x) \to G(x)),\ \exists x(F(x) \land H(x))
    结论：∃x(G(x)∧H(x))\exists x(G(x) \land H(x))
    证明：

    (1)∃x(F(x)∧H(x))前提引入(2)F(a)∧H(a)∃−(3)F(a)化简律(4)H(a)化简律(5)∀x(F(x)→G(x))前提引入(6)F(a)→G(a)∀−(7)G(a)假言推理(8)G(a)∧H(a)合取(9)∃x(G(x)∧H(x))∃+ \begin{array}{lll} (1) & \exists x(F(x) \land H(x)) & \text{前提引入} \\ (2) & F(a) \land H(a) & \exists- \\ (3) & F(a) & \text{化简律} \\ (4) & H(a) & \text{化简律} \\ (5) & \forall x(F(x) \to G(x)) & \text{前提引入} \\ (6) & F(a) \to G(a) & \forall- \\ (7) & G(a) & \text{假言推理} \\ (8) & G(a) \land H(a) & \text{合取} \\ (9) & \exists x(G(x) \land H(x)) & \exists+ \end{array}
    得证 ∃x(G(x)∧H(x))\exists x(G(x) \land H(x)) 是有效结论。

  • 例2：前提：∀x(F(x)∨G(x))\forall x(F(x) \vee G(x))
    结论：¬∀xF(x)→∃xG(x)\neg \forall x F(x) \to \exists x G(x)
    证明：

    (1)¬∀xF(x)附加前提引入(2)∃x¬F(x)置换(3)¬F(a)∃−(4)∀x(F(x)∨G(x))前提引入(5)F(a)∨G(a)∀−(6)G(a)析取三段论(7)∃xG(x)∃+ \begin{array}{lll} (1) & \neg \forall x F(x) & \text{附加前提引入} \\ (2) & \exists x \neg F(x) & \text{置换} \\ (3) & \neg F(a) & \exists- \\ (4) & \forall x(F(x) \vee G(x)) & \text{前提引入} \\ (5) & F(a) \vee G(a) & \forall- \\ (6) & G(a) & \text{析取三段论} \\ (7) & \exists x G(x) & \exists+ \end{array}

    得证 ¬∀xF(x)→∃xG(x)\neg \forall x F(x) \to \exists x G(x) 是有效结论。

← 返回 Note