计算机科学/应用逻辑

在下面，我们简要地考虑一些应用问题，其中语言的可表达性很重要。很容易发现，FO 对于许多情况是不够的。为了克服 FO 的限制，存在许多扩展，例如不动点逻辑、计数逻辑、二阶逻辑的各种变体等，这些扩展在本~~chaper~~ [章节 | 论文] 中没有涵盖。

数据库理论：SQL

关系具有名为属性的命名列。

   frequents |  drinker  bar
   ----------|---------------
             |

   serves    |  bar  beer
   ----------|---------------
             |

   likes     |  drinker  beer
   ----------|---------------
             |

标准查询语言

关系代数变体，在关系词汇表上使用 FO（没有函数，只有关系）。

这里，常量具有固定的解释，这与 FO 逻辑略有不同。

关系查询示例

(i) 查找所有供应 Bud 的酒吧

$\{b:bar|serves(b,Bud)\}$

b 是一个自由变量，Bud 是一个常量。

(ii) 查找光顾供应 Bud 的酒吧的~~drunkers~~ [drinkers | drunkards]
$\{d:drinker|\exists b(frequents(d,b)\wedge serves(b,Bud))\}$

(iii) 查找只光顾供应 Bud 的酒吧的饮酒者
$\{d:drinker|\forall b[frequents(d,b)\longrightarrow serves(b,Bud)]\}$

(iv) 查找只光顾供应他们喜欢的某些啤酒的酒吧的饮酒者
$\{d:drinker|\forall b(freq(d,b)\longrightarrow \exists c(serves(b,c)\wedge likes(d,c)))\}$

这些查询的 SQL 表示

   SELECT s.bar
   FROM serves s
   WHERE s.beer = 'Bud'

   SELECT f.drinker
   FROM freq f, serves s
   WHERE f.bar = s.bar and s.beer = 'Bud'

   SELECT drinker
   FROM freq
   WHERE dr NOT IN
   (
       SELECT f.drinker
       FROM frequents f
       WHERE f.bar NOT IN
           (SELECT bar
            FROM serves
            WHERE beer = 'Bud')
   )

关系代数

是在 SQL 中使用的另一种表示语言。您可以使用关系代数表示的内容与您可以在 FO 逻辑中表示的内容完全相同。它由对关系的简单运算构成，这些运算允许您指定查询。

主要运算

$\Pi$ 投影 : 将关系投影到其列（属性）的子集上。

$\sigma$ 选择 : 根据指定的选定条件，从特定关系中选择元组的子集。

$\cup$ , $-$ 联合、差 : 与集合运算类似。

|><| 连接 : 允许您组合来自两个关系的元组。

重命名 : 将 A 重命名为 B。

从这些表达式构建的表达式称为关系代数查询。无论您可以在代数中表达什么，我们都可以在 FO 中表示。

示例

(i) $\Pi _{bar}(\Sigma _{beer=Bud}(serves))$

(ii) $\Pi _{dr}(freq|><|\sigma _{beer=Bud}(serves))$

(iii) $\Pi _{d}(freq)-\Pi _{d}[freq|><|(\Pi _{bar}(freq)-\Pi _{bar}(\Sigma _{beer=Bud}(serves)))]$

表达能力

图的属性对应于关系数据库中数据结构的属性（参见关于数据库查询的章节），例如：

考虑一个包含所有经理及其之间“是上级”关系的公司数据库。在一个适当的层次结构中，数据库不应该包含循环，即经理不能成为其上级的上级。查询此对应于检查图是否有循环。如上所述，这在 FO 中是无法完成的。
假设两位经理想弄清楚他们俩中谁更有权势。所以他们想要查询数据库，看看他们的下属人数是否相等，即下属集（例如直接和间接下属）的基数是否相等。这在 FO 中是无法完成的（“FO 不能计数”）。这就是为什么 SQL 通过计数函数进行扩展的原因。
考虑一个包含机场及其之间连接航班的数据库。为了查询从机场 a 到机场 b 的直接可达性，我们可以编写

$q_{0}(a,b)=F(a,b)$ .

现在，为了查询经过一次转机的连接，我们编写

$q_{1}(a,b)=\exists _{c}F(a,c)\land F(c,b)$ 并且得到 $Q_{1}(a,b)=q_{1}(a,b)\lor q_{1}(a,b)$

对于零次或一次转机的连接。因此，为了将此扩展到可达性（无论经过多少次转机），我们必须编写

$\bigvee _{k\in \mathbb {N} }q_{k}$

这不是 FO 表达式。因此，对于最多为某个 k 的受限可达性，我们可以使用 FO，但对于图论中出现的那样，我们无法使用 FO 进行可达性查询。事实上，可以证明，可达性在 FO 中是无法查询的。

描述性复杂性理论

如上所述，Hamiltonicity 无法用 FO 表达。因此，现在我们可以考虑对 FO 进行扩展，以便表达此属性。这可以像这样完成

$\exists L\exists S(isLinOrd(L)\land isSucRelOf(S,L)\land \forall _{x}\exists _{y}(L(x,y)L\lor L(y,x))\land \forall _{x}\forall _{y}(S(x,y)\implies E(x,y)))$

其中左侧的量词表示存在满足右侧公式的二元关系 L 和 S。关系 isLinOrd 表示 L 是一个线性序，而 isSucRelOf 意味着 S 是 L 的后继关系。这两者都可以用 FO 表示。如上所示的模式，即存在量词之后是一个一阶公式，被称为存在二阶逻辑。

众所周知，Hamiltonicity 是一个 NP 完备问题，我们可以问：NP 和二阶逻辑之间是否存在自然联系？确实，它们之间存在非常惊人的联系：存在二阶逻辑完全对应于 NP 完备问题的类别！这个结果被称为 Fagin 定理，它导致了**描述性复杂性**这个新领域，在这个领域中，复杂性类别是用逻辑形式来描述的。