前面說到了謂詞邏輯的一些等價關系:
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(Φ∨Ψ)
其餘等價關系類似,有興趣可以自己嘗試一下。