一阶谓词逻辑

所有人都会死，苏格拉底是人，所以苏格拉底会死。 人被杀,就会死(误)

在命题逻辑中无法判断推理的正确性。

为了解决个体和总体之间的联系，引入量词。

一阶逻辑是 在命题逻辑基础上的扩展。

命题逻辑只能处理“整个命题”的真假，推理粒度更粗。

而一阶逻辑推理更细 ，能描述命题内部的结构，即’对象+属性+关系’。

一阶逻辑符号化

个题词 ：所研究对象中可以独立存在的具体或抽象的客体，个体常项，具体的用abc表示，个体变项，抽象的用xyz表示

谓词：表示个体词质或相互之间关系的词

  • 谓词常项：\(F(a)\) ：a是人
  • 谓词变项：\(F(x)\) : x具有性质F
  • 根据个体变项的个数，称n元谓词
  • 0元谓词就是命题常项或命题变项 量词分
  • 存在，\(\exists\) ,exists，存在，有的，至少一个
  • 任意\(\forall\)，for all，对所有的，任意一个，每一个都 命题符号化
  • “D中所有 x 都有性质 F ” ，符号化为： \[ \forall xF(x) \]
  • “D中存在 x 有性质 F ” ，符号化为： \[ \exists xF(x) \]
  • “对D中的所有 x，如果 x 有性质 F，x 就有性质 G ” ，符号化为： \[ \forall x(F(x) \rightarrow G(X)) \]
  • “D中存在 x， 既有性质 F、又有性质 G ” ，符号化为： \[ \exists x(F(x)\land G(x)) \]
  • “D中的所有 x、y, 如果x有性质 F、y 有性质 G ,则 x、y 就有关系H” ，符号化为： \[ \forall x\forall y(F(x)\land G(y)\rightarrow H(x,y)) \]
  • “D中的所有 x, 如果x有性质 F,就存在y 有性质 G ,使得 x、y 有关系H” ，符号化：

\[ \forall x(F(x)\rightarrow \exists y(G(y)\land H(x,y))) \]

  • “D中存在 x有性质 F,且对所有的 y 而言,如果 y 有性质 G ,则 x、y 就有关系 H ”： \[ \exists x(F(x)\land \forall y(G(y)\rightarrow H(x,y))) \]

量词的辖域 在公式\(\exists xA\)和\(\forall xA\)中x为指导变元，A为相应量词的辖域。

在\(\exists xA\)和\(\forall xA\)的辖域中，x的所有出现为约束出现，A中不是约束出现的所有其他变项称为是自由出现

若公式A中不包含自由出现的个体变项，则称A为封闭的公式，简称闭式

一阶逻辑公式

一阶语言L包括:

非逻辑符号:

  1. 个体常项符号：a, b, c, …
  2. 函数符号：f, g, h, …
  3. 谓词符号：F, G, H, …

逻辑符号:

  1. 个体变项符号：x, y, z, …
  2. 量词符号：\(\exists ,\forall\)
  3. 联结词符号：\(\land \lor \lnot \rightarrow\leftrightarrow\)
  4. 括号与逗号：(,),,

L的项的定义如下：

  1. 个体常项和个体变项是项。
  2. 若\(\phi(x_{1}, x_{2},\dots, x_{n})\)是n元函数符号，\(t_{1}, t_{2},\dots, t_{n}\)是 n个项，则\(\phi(t_{2}, t_{2}, \dots, t_{n})\) 是项。
  3. 所有的项都是有限次使用(1),(2)得到的。如, a, x, x+y, f(x), g(x,y)等都是项。

原子公式

设\(R(x_{1}, x_{2}, \dots, x_{n})\)是L 的n元谓词符号，\(t_{1}, t_{2},\dots, t_{n}\) 是L 的n个项，则称\(R(t_{1}, t_{2},\dots, t_{n})\)是L的原子公式。

如，F(x, y), F(f(x1, x2), g(x3, x4))等均为原子公式

合式公式

  1. 原子公式是合式公式.
  2. 若A是合式公式，则 \((¬A)\)也是合式公式
  3. 若A, B是合式公式，则\((A\land B), (A\lor B), (A\rightarrow B), (A\leftrightarrow B)\)也是合式公式
  4. 若A是合式公式，则\(\forall xA, \exists xA\)也是合式公式
  5. 只有有限次地应用(1)—(4)形成的符号串才是合式公式

合式公式的解释

设公式 A, 取个体域\(Di\) , 把A中的个体常项符号a、函数符号f、谓词符号F分别替换成它们在I中的解释\(\bar{a},\bar{f},\bar{F}\)， 称所得到的公式A’为A在I下的解释, 或A在I下被解释成A’。

口诀：除了约束变元，由外往内全部替换！

闭式在任何解释下都是命题。

注意: 不是闭式的公式在解释下可能是命题, 也可能不是命题.

永真式、矛盾式、可满足式

  • 若公式A在所有解释下均为真, 则称A为 永真式 (逻辑有效式).
  • 若公式A在所有解释下均为假, 则称A为 矛盾式 (永假式).
  • 若至少有一个解释使公式A为真, 则称A为 可满足式.

几点说明：

永真式为可满足式，但反之不真

判断公式是否是可满足的(永真式, 矛盾式)是不可判定的

一阶逻辑等值式与运算

等值式

设A，B是两个谓词公式，如果A\(\leftrightarrow\)B是永真式，则称A与B等值，记作A\(\Leftrightarrow\)B,并称其为等值式

基本等值式

  1. 逻辑命题中16组24个基本等值式的代换实例
  2. 谓词专有 量词否定等值式 \[ \begin{align*} \neg \forall xA(X)\Leftrightarrow \exists x\neg A(x) \\ \neg \exists xA(x)\Leftrightarrow \forall x \neg A(X) \end{align*} \]

量词收缩与扩张

全称量词
  1. \[\forall x(A(x)\lor B)\Leftrightarrow \forall xA(x)\lor B \]
  2. \[ \forall x(A(x)\land B)\Leftrightarrow \forall xA(x)\land B \]
  3. \[ \textcolor{red}{\forall} x(A(x)\rightarrow b)\Leftrightarrow \textcolor{red}{\exists}xA(x)\rightarrow B \]
  4. \[ \forall x(B\to A(x))\Leftrightarrow B\to \forall xA(x) \]
存在量词
  1. \[ \exists x(A(x)\lor B)\Leftrightarrow \forall xA(x)\lor B\]
  2. \[ \exists x(A(x)\land B)\Leftrightarrow \exists xA(x)\land B \]
  3. \[\textcolor{red}{\exists}x(A(x)\to B)\Leftrightarrow \textcolor{red}{\forall} xA(x)\to B \]
  4. \[ \exists x(B\to A(x))\Leftrightarrow B\to \exists xA(x) \]
量词分配

\[ \begin{align*} \forall x(A(x)\land B(x))\Leftrightarrow \forall xA(x)\land \forall xB(x) \\ \exists x(A(x)\lor B(x))\Leftrightarrow \exists xA(x)\lor \exists xB(x) \end{align*} \]

常用重要推理定律
  1. \[ \forall x A(x)\lor \forall xB(x)\Rightarrow \forall x(A(x)\lor B(x)) \]
  2. \[ \exists x(A(x)\land B(x))\Rightarrow \exists xA(x)\land \exists xB(x) \]
  3. \[ \forall x(A(x)\to B(x))\Rightarrow \forall xA(x)\rightarrow \forall xB(x) \]
  4. \[ x\exists(A(x)\to B(x))\Rightarrow \exists xA(x)\to \exists xB(x)\]

置换

\[ 若A \Leftrightarrow B,设\phi(A),\phi(B)分别是包含A，B的公式，那么\phi(A)\Leftrightarrow \phi(B) \]

换名

设A为一公式，将A中某量词辖域中个体变项的所有约束出现及相应的指导变元换成该量词辖域中未曾出现过的个体变项符号，其余部分不变，设所得公式为A’，则A’\(\Leftrightarrow\)A.

也就是把约束出现的指导变元换名字，公式谓词公式等值

消去量词

设论域\(D=\{a_{1},a_{2},\dots,a_{n}\}\)是有限集合，则 \[ \begin{align} \forall x A(X) \Leftrightarrow A(a_{1})\land A(a_{2})\land\dots \land A(a_{n}) \\ \exists xA(X)\Leftrightarrow A(a_{1})\lor A(a_{2})\lor\dots \lor A(a_{n}) \end{align} \]