計算機科學/應用邏輯

在下面，我們簡要地考慮一些應用問題，其中語言的可表達性很重要。很容易發現，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 定理，它導致了**描述性複雜性**這個新領域，在這個領域中，複雜性類別是用邏輯形式來描述的。