計算機科學家邏輯/謂詞邏輯/語法

定義 1（謂詞邏輯的語法 - 項）

假設一個

• 可數的函式符號集 $\{f{_{i}}^{k}\mid i,k=1,2,3,\cdots \}$
• 一個可數的 $\{x_{i}\mid i=1,2,3,\cdots \}$

項的集合由以下歸納定義

• 變數 $x_{i}$ 是項。
• 如果 $t_{1},\cdots ,t_{k}$ 是項，而 $f_{i}^{k}$ 是一個函式符號，那麼 $f_{i}^{k}(t_{1},\cdots ,t_{k})$ 是一個項。

型別為 $f_{i}^{0}()$ 的項是特殊的項，它們被稱為常量。在這種情況下，我們省略括號並將其表示為 $f_{i}^{0}$。

項是上述物件的語法對應物。常量將表示域中的元素，而函式符號將表示引用這些物件的一種方式。

以下定義介紹了公式。

定義 2（謂詞邏輯的語法 - 公式）

假設一個可數的謂詞符號集 $\{p_{i}^{k}\mid i=1,2,3,\cdots \}$。公式（良構）的集合由以下歸納定義

• 如果 $t_{1},\cdots ,t_{k}$ 是項，而 $P_{i}^{k}$ 是一個謂詞符號，那麼 $P_{i}^{k}(t_{1},\cdots ,t_{k})$ 是一個公式。
• 如果 $F$ 和 $G$ 是公式，那麼 $(F\land G)$ 和 $(F\lor G)$ 都是公式。
• 如果 $F$ 是一個公式，那麼 $\lnot F$ 是一個公式。
• 如果 $x$ 是一個變數，而 $F$ 是一個公式，那麼 $\forall xF$ 和 $\exists xF$ 都是公式。

型別為 $P_{i}^{k}(t_{1},\cdots ,t_{k})$ 的公式被稱為原子或原子公式。

注意，子公式的概念與命題情況完全相同 (命題邏輯的語法 (Propositional Logic)).

我們引入以下縮寫，它們也將與索引一起使用

$u,v,w,x,z,$			代表變數
$a,b,c,\cdots$			代表常量
$f,g,h,\cdots$			代表函式符號
$p,q,r,\cdots$			代表謂詞符號

注意，在這些縮寫中，函式和謂詞符號的元數被省略；我們假設它將從上下文中清楚地顯現出來。

示例：假設我們想要表示以下等式，它對域中的任意元素成立

$x*(y+z)=x*y+x*z$

兩個運算子 $*$ 和 $+$ 在謂詞邏輯公式中表示為二元函式符號 $f_{1}^{2}$ 和 $f_{2}^{2}$，三個變數是 $x_{1},x_{2}$ 和 $x_{3}$，等價關係 $=$ 是二元謂詞符號 $P_{1}^{2}$。總的來說，我們有以下謂詞邏輯公式

$\forall x_{1}\forall x_{2}\forall x_{3}(P_{1}^{2}(f_{2}^{2}(x_{1},f_{1}^{2}(x_{2},x_{3})),f_{1}^{2}(f_{2}^{2}(x_{1},x_{2}),f_{2}^{2}(x_{1},x_{3}))))$

在下文中，我們將使用與命題情況相同顯而易見且更寬鬆的符號。

定義 3：變數的繫結和自由出現

在一個公式 $F$ 中，變數 $x$ 的出現被稱為繫結，如果它出現在 $F$ 的一個子公式中，該子公式的形式為 $\exists x\;G$ 或 $\forall x\;G$。否則我們稱這個出現為自由出現。

一個公式，如果它不包含一個變數的自由出現，就被稱為閉合的。

示例： 以下公式包含 $x$ 和 $y$ 的自由出現和綁定出現。

$\forall z(Q(z)\land \forall x(P(x,y))\lor \exists y(P(x,y)))$