天天看點

謂詞邏輯之 等價關系證明

前面說到了謂詞邏輯的一些等價關系:

1.(a) ┐∀xΦ⇔∃x┐Φ

   (b) ┐∃xΦ⇔∀x┐Φ

2.假設x在Ψ中不是自由的,那麼:

(a)∀xΦ∧Ψ⇔∀x(Φ∧Ψ)

(b)∀xΦ∨Ψ⇔∀x(Φ∨Ψ)

(c)∃xΦ∧Ψ⇔∃x(Φ∧Ψ)

(d)∃xΦ∨Ψ⇔∃x(Φ∨Ψ)

(e)∀x(Ψ→Φ)⇔Ψ→∀xΦ

(f) ∃x(Φ→Ψ)⇔∀xΦ→Ψ

(g)∀x(Φ→Ψ)⇔∃xΦ→Ψ

(h)∃x(Ψ→Φ)⇔Ψ→∃xΦ 

3.(a)∀xΦ∧∀xΨ⇔∀x(Φ∧Ψ)

   (b)∃xΦ∨∃xΨ⇔∃x(Φ∨Ψ)

4.(a)∀x∀yΦ⇔∀y∀xΦ

   (b)∃x∃yΦ⇔∃y∃xΦ

現在來證明其中的一些,需要用到之前的命題邏輯演算規則和量詞證明規則。

先來看證明的思路:證明相繼式┐∀xP(x)├ ∃x┐p(x)的有效性

謂詞邏輯之 等價關系證明

 這個過程比較簡單:先假設相繼式右邊不成立(第2行),然後對一個任意變量x0假設p(x0)不成立,則得出存在一個x使得p(x)不成立(第5行,這個x起碼可以是x0),但和第2行的結論沖突了,是以第4行的假設不靠譜,必須有p(x0)成立(第7行)。既然x0是任意的,那麼對于所有x有P(x)成立(第8行)。但這和我們的前提沖突了,是以我們最初的假設是錯誤的。證明完畢。

 看明白了吧,接下來我們主要這樣進行證明。

要證明一個等價關系,需要分别證明左邊能推導出右邊和右邊能推導出左邊。

一、證明┐∀xΦ├ ∃x┐Φ的有效性,這個和上面的過程完全一緻

謂詞邏輯之 等價關系證明

 證明逆∃x┐Φ├ ┐∀xΦ的有效性

謂詞邏輯之 等價關系證明

 這個更簡單些。不過如果不熟悉全稱消去規則需要回到上一篇看看。

這樣我們證明了第一個等價規則:┐∀xΦ⇔∃x┐Φ。

二、證明∀xΦ∧Ψ├ ∀x(Φ∧Ψ)的有效性(注意條件:x在Ψ中不是自由的)

謂詞邏輯之 等價關系證明

 由于x在Ψ中不是自由的,進行代換時并不處理Ψ,是以第6行和第5行是一樣的。

證明∀x(Φ∧Ψ)├ ∀xΦ∧Ψ的有效性:

謂詞邏輯之 等價關系證明

三、證明矢列∃xΦ∨∃xΨ├∃x(Φ∨Ψ)

謂詞邏輯之 等價關系證明

 證明矢列∃xΦ∨∃xΨ-|∃x(Φ∨Ψ)

謂詞邏輯之 等價關系證明

其餘等價關系類似,有興趣可以自己嘗試一下。