離散數學 - 謂詞邏輯

謂詞邏輯處理謂詞，謂詞是包含變數的命題。

謂詞邏輯 – 定義

謂詞是在某個特定域上定義的一個或多個變數的表示式。透過為變數賦值或對變數進行量化，可以將包含變數的謂詞變成命題。

以下是謂詞的一些示例：

• 設 E(x, y) 表示 "x = y"
• 設 X(a, b, c) 表示 "a + b + c = 0"
• 設 M(x, y) 表示 "x 與 y 結婚"

良構公式

良構公式 (wff) 是滿足以下任何條件的謂詞：

• 所有命題常量和命題變數都是良構公式

• 如果 x 是一個變數，Y 是一個良構公式，則 $\forall x Y$ 和 $\exists x Y$ 也是良構公式

• 真值和假值是良構公式

• 每個原子公式都是良構公式

• 連線良構公式的所有連線詞都是良構公式

量詞

謂詞的變數由量詞量化。謂詞邏輯中有兩種型別的量詞：全稱量詞和存在量詞。

全稱量詞

全稱量詞指出其作用域內的語句對於特定變數的每個值都為真。它用符號 $\forall$ 表示。

$\forall x P(x)$ 讀作對於 x 的每一個值，P(x) 為真。

示例：“人是凡人”可以轉化為命題形式 $\forall x P(x)$，其中 P(x) 是表示 x 是凡人的謂詞，論域是所有的人。

存在量詞

存在量詞指出其作用域內的語句對於特定變數的某些值成立。它用符號 $\exists$ 表示。

$\exists x P(x)$ 讀作對於 x 的某些值，P(x) 為真。

示例：“有些人是不誠實的”可以轉化為命題形式 $\exists x P(x)$，其中 P(x) 是表示 x 不誠實的謂詞，論域是某些人。

巢狀量詞

如果我們使用一個出現在另一個量詞作用域內的量詞，則稱之為巢狀量詞。

示例

• $\forall\ a\: \exists b\: P (x, y)$，其中 $P (a, b)$ 表示 $a + b = 0$

• $\forall\ a\: \forall\: b\: \forall\: c\: P (a, b, c)$，其中 $P (a, b, c)$ 表示 $a + (b + c) = (a + b) + c$

注意 – $\forall\: a\: \exists b\: P (x, y) \ne \exists a\: \forall b\: P (x, y)$