謂詞邏輯(Predicate Logic)


謂詞(predicate)

表示一「特性」或「關係」的敘述,範例如下:

  1. x < 5
  2. (a+π)/11 ≥ e²

在上述兩個範例中,分別存在一未知數 x 及 a,在沒有設定 x 與 a 的範圍下,無從判斷其真假值,因此不能稱為「命題」,而是「謂詞」。


量詞(quantifier)

「謂詞」經過「量詞」設定範圍、並以「邏輯連接詞」連接後,即形成「謂詞合式公式(predicate wff)」,量詞定義的謂詞又稱為「轄域(scope)」。設定範圍的方式共有兩種:

全稱量化(universal quantification)

即「對於所有(for all)」,符號記為「∀」。

存在量化(existential quantification)

即「存在(there exists)」,也就是「至少有一個」,符號記為「∃」。

有了「量詞」與「謂詞」,就能有像下面的敘述:

藍色「量詞」制定藍色「轄域」;綠色「量詞」制定綠色「轄域」;邏輯連接詞「且(∧)」的兩側各自為紅色「謂詞」。

只要再定義變數的定義域(domain)與謂詞,就可以判斷這個敘述的真假,例如:

  1. 定義變數「x」、「y」的定義域為整數(Z)。
  2. 定義謂詞「A(x)」為 x>0。
  3. 定義謂詞「B(x,y)」為 x>y。
  4. 定義謂詞「C(x,y)」為 y≤0。

上述的一連串符號即可解讀為「至少有一個 x,此 x>0,且對於所有的 y 而言, 若 x>y,則 y≤0」。

再白話一點可以這樣理解:

  1. 至少有一個大於 0 的整數 x,x 可為 1、2、3… 等等的正整數。
  2. 「如果 x 大於 y 成立,則y可能為0或所有負整數」是否為真?
  3. 在 x 為 1 時,敘述 2. 即成立,因此敘述為「真」。

在 x 為 2 時,若 x>y,則 y 除了 0 與所有負整數外也包含 1,敘述 2. 並不成立,x 為 3 以上的整數時亦然,但因為我們設定的是「至少有一個 x」,只要 x=1 時成立就算正確,因此該敘述為真。

若最前面的量詞改為「∀」,變成 x 用 1 以上任何一個整數代入時,都要符合 x>y 時,y≤0,但因為 x 為 2 以上的正整數皆不正確,因此「(∀x)(A(x) ∧ (∀y) [B(x,y) → C(y)])」為假。

量詞的「否定(negation)」

現在來試想以下兩種敘述的否定,其中 x 為整數:

  1. (∀x)(x>0)
  2. (∃x)(x>0)

要找出這兩個敘述的否定,代表要說明這兩個敘述是錯的!

  1. [(∀x)(x>0)]',即「所有的 x 都大於 0」是錯的。
  2. [(∃x)(x>0)]',即「至少有一個 x 大於 0」是錯的。

要說明「所有的 x 都大於 0」是錯的,就是要說明「存在一個 x 小於等於 0」;要說明「至少存在一個 x 大於 0」是錯的,就是要說明「所有的 x 都 ≤0」,用符號表示如下:

  1. 「[(∀x)(x>0)]'」即「(∃x)(x≤0)」。
  2. 「[(∃x)(x>0)]'」即「(∀x)(x≤0)」。

比較一下左右兩側符號可以發現,除了「>」改為「≤」外,只是把「∃」與「∀」互換,此即為量詞的否定,有點類似笛摩根定律中,將「∧」與「∨」互換的過程。


小結

  1. 謂詞:若無量詞設定範圍,則無從判斷真假值的敘述。
  2. 量詞:包含「∀(對於所有)」與「∃(存在)」,可使其轄域(即謂詞)有真假值。
#離散數學 #謂詞邏輯







你可能感興趣的文章

Day 86

Day 86

[MTR04] W2 D15 練習五:判斷大小寫

[MTR04] W2 D15 練習五:判斷大小寫

[PySide6]介面與邏輯

[PySide6]介面與邏輯






留言討論