形式邏輯/命題邏輯/形式語法

← 命題語言

↑ 命題邏輯

非正式約定 →

形式語法

在命題語言中，我們非正式地描述了我們的命題語言。在這裡，我們給出它的形式語法或文法。我們將我們的語言稱為${\mathcal {L_{S}}}\,\!$.

詞彙

• 命題字母：大寫字母 'A' – 'Z'，每個字母都有 (1) 上標 '0' 和 (2) 自然數下標。（自然數 是正整數和零的集合。）因此，命題字母是

$\mathrm {A_{0}^{0}} ,\ \mathrm {A_{1}^{0}} ,\ ...,\ \mathrm {B_{0}^{0}} ,\ \mathrm {B_{1}^{0}} ,\ ...,\ ...,\ \mathrm {Z_{0}^{0}} ,\ \mathrm {Z_{1}^{0}} ,\ ...\,\!$

• 命題聯結詞:

$\land ,\ \lor ,\ \lnot ,\ \rightarrow ,\ \leftrightarrow \,\!$

• 分組符號

$(,\ )\,\!$

命題字母上的上標直到我們學習謂詞邏輯才重要，所以在這裡我們不會太在意它們。命題字母的下標是為了確保命題字母有無限個。在下一頁，我們將縮寫掉大多數上標和下標。

表示式

來自${\mathcal {L_{S}}}\,\!$詞彙的任何字元序列都是${\mathcal {L_{S}}}\,\!$的表示式。有些表示式在語法上是正確的。有些表示式在${\mathcal {L_{S}}}\,\!$中與 'Over talks David Mary the' 在英語中的錯誤一樣。其他一些表示式在${\mathcal {L_{S}}}\,\!$中與 'jmr.ovn asgj as;lnre' 在英語中的錯誤一樣。

我們將語法上正確的${\mathcal {L_{S}}}\,\!$表示式稱為合式公式。當我們開始學習謂詞邏輯時，我們會發現只有部分合式公式才是句子。不過現在，我們將所有合式公式都視為句子。

構造規則

${\mathcal {L_{S}}}\,\!$中的表示式，如果它是根據以下規則構造的，則被稱為${\mathcal {L_{S}}}\,\!$的合式公式。

${\mbox{i.}}$ 該表示式由一個句子字母組成

${\mbox{ii.}}$ 該表示式是透過以下幾種方式之一，由其他合式公式$\varphi \,\!$和$\psi \,\!$構造的

${\mbox{ii-a.}}\ \ \lnot \varphi \,\!$

${\mbox{ii-b.}}\ \ (\varphi \land \psi )\,\!$

${\mbox{ii-c.}}\ \ (\varphi \lor \psi )\,\!$

${\mbox{ii-d.}}\ \ (\varphi \rightarrow \psi )\,\!$

${\mbox{ii-e.}}\ \ (\varphi \leftrightarrow \psi )\,\!$

一般來說，我們將使用 'formula' 來簡化 'well-formed formula'。由於${\mathcal {L_{S}}}\,\!$ 中的所有公式都是句子，我們將交替使用 'formula' 和 'sentence'。

引用約定

我們將把${\mathcal {L_{S}}}\,\!$中的表示式視為自我引用，並因此將其視為

$(\mathrm {P_{0}^{0}} \rightarrow \mathrm {Q_{0}^{0}} )\,\!$

包含隱式引號。但是，類似

$(1)\quad (\varphi \rightarrow \psi )\,\!$

需要特別考慮。它本身不是 ${\mathcal {L_{S}}}\,\!$ 的表示式，因為 $\varphi \,\!$ 和 $\psi \,\!$ 不在 ${\mathcal {L_{S}}}\,\!$ 的詞彙表中。相反，它們在英語中用作變數，這些變數在 ${\mathcal {L_{S}}}\,\!$ 的表示式上取值。這樣的變數稱為 *元變數*，使用來自 ${\mathcal {L_{S}}}\,\!$ 和元變數的詞彙的表示式稱為 *元邏輯表示式*。假設我們讓 $\varphi \,\!$ 為 $\mathrm {P_{0}^{0}} \,\!$，並且 $\psi \,\!$ 為 $(\mathrm {Q_{0}^{0}} \lor \mathrm {R_{0}^{0}} )\ .\,\!$ 那麼 (1) 變成

$(\,\!$'$\mathrm {P_{0}^{0}} \,\!$' $\rightarrow (\,\!$'$\mathrm {Q_{0}^{0}} \,\!$' $\lor \,\!$'$\mathrm {R_{0}^{0}} \,\!$'$))\,\!$

這與我們想要的不同。相反，我們將（1）理解為（使用明確的引號）

由 '$(\,\!$' 接著 $\varphi \,\!$ 接著 '$\rightarrow \,\!$' 接著 $\psi \,\!$ 接著 '$)\,\!$' 組成的表示式。

遵循這種約定的明確引號被稱為 *Quine 引號* 或 *角引號*。我們的角引號將是隱式的。

其他術語

我們介紹（或在某些情況下，重複）一些有用的語法術語。

• 我們區分表示式（或公式）和表示式的 *出現*（或公式）。公式

$((\mathrm {P_{0}^{0}} \land \mathrm {P_{0}^{0}} )\land \lnot \mathrm {P_{0}^{0}} )\,\!$

無論寫多少次，都是同一個公式。但是，它包含三個句子字母 $\mathrm {P_{0}^{0}} \,\!$ 的出現，以及兩個句子連線詞 $\land \,\!$ 的出現。

• $\psi \,\!$ 是 $\varphi \,\!$ 的一個 子公式 當且僅當 $\varphi \,\!$ 和 $\psi \,\!$ 都是公式，並且 $\varphi \,\!$ 包含 $\psi \,\!$ 的一個出現。 $\psi \,\!$ 是 $\varphi \,\!$ 的一個 真子公式 當且僅當 (i) $\psi \,\!$ 是 $\varphi \,\!$ 的一個子公式，並且 (ii) $\psi \,\!$ 與 $\varphi \,\!$ 不是同一個公式。

• 一個 原子公式 或 原子句子 是一個僅包含一個句子字母的公式。或者換句話說，它是一個不包含任何句子連線詞的公式。一個 分子公式 或 分子句子 是一個包含至少一個句子連線詞的公式。

• 一個分子公式的 主連線詞 是在根據上述規則構造公式時最後新增的連線詞的最後一個出現。

• 一個 否定 是一個形式為 $\lnot \varphi \,\!$ 的公式，其中 $\varphi \,\!$ 是一個公式。

• 合取 是一個形如 $(\varphi \land \psi )\,\!$ 的公式，其中 $\varphi \,\!$ 和 $\psi \,\!$ 都是公式。在這種情況下，$\varphi \,\!$ 和 $\psi \,\!$ 都是 合取式。

• 析取 是一個形如 $(\varphi \lor \psi )\,\!$ 的公式，其中 $\varphi \,\!$ 和 $\psi \,\!$ 都是公式。在這種情況下，$\varphi \,\!$ 和 $\psi \,\!$ 都是 析取式。

• 條件式 是一個形如 $(\varphi \rightarrow \psi )\,\!$ 的公式，其中 $\varphi \,\!$ 和 $\psi \,\!$ 都是公式。在這種情況下，$\varphi \,\!$ 是 前件，$\psi \,\!$ 是 後件。 $(\varphi \rightarrow \psi )\,\!$ 的 逆命題 是 $(\psi \rightarrow \varphi )\,\!$。 $(\varphi \rightarrow \psi )\,\!$ 的 逆否命題 是 $(\lnot \psi \rightarrow \lnot \varphi )\,\!$.

• 雙條件式是一個形如$(\varphi \leftrightarrow \psi )\,\!$ 的公式，其中 $\varphi \,\!$ 和 $\psi \,\!$ 都是公式。

示例

$(1)\quad (\lnot (\mathrm {P_{0}^{0}} \lor \mathrm {Q_{0}^{0}} )\rightarrow (\mathrm {R_{0}^{0}} \land \lnot \mathrm {Q_{0}^{0}} ))\,\!$

根據規則 (i)，所有句子字母，包括

$\mathrm {P_{0}^{0}} ,\ \mathrm {Q_{0}^{0}} ,\ {\mbox{and}}\ \mathrm {R_{0}^{0}} \ ,\,\!$

都是公式。那麼，根據規則 (ii-a)，否定

$\lnot \mathrm {Q_{0}^{0}} \,\!$

也是公式。然後，根據規則 (ii-c) 和 (ii-b)，我們得到析取和合取

$(\mathrm {P_{0}^{0}} \lor \mathrm {Q_{0}^{0}} ),\ {\mbox{and}}\ (\mathrm {R_{0}^{0}} \land \lnot \mathrm {Q_{0}^{0}} )\,\!$

作為公式。再次應用規則 (ii-a)，我們得到否定

$\lnot (\mathrm {P_{0}^{0}} \lor \mathrm {Q_{0}^{0}} )\,\!$

作為公式。最後，規則 (ii-c) 生成 (1) 的條件式，所以它也是公式。

$(2)\quad ((\mathrm {P_{0}^{0}} \lnot \land \mathrm {Q_{0}^{0}} )\lor \mathrm {S_{0}^{0}} )\,\!$

這似乎是由規則 (ii-c) 從以下公式生成的

$(\mathrm {P_{0}^{0}} \lnot \land \mathrm {Q_{0}^{0}} ),\ {\mbox{and}}\ \mathrm {S_{0}^{0}} \ .\,\!$

其中第二個公式是根據規則 (i) 得出的。但第一個公式呢？它必須根據規則 (ii-b) 從

$\mathrm {P_{0}^{0}} \lnot \ {\mbox{and}}\ \mathrm {Q_{0}^{0}} \ .\,\!$

但是

$\mathrm {P_{0}^{0}} \lnot \,\!$

不能根據規則 (ii-a) 生成。因此 (2) 不是一個公式。

← 命題語言

↑ 命題邏輯

非正式約定 →