前面我們說過 “不是所有的鳥都會飛”用謂詞邏輯表示有兩種方式：
B（x）：x是一隻鳥
F（x）：x可以飛翔
這個語句就可以編碼為：﹁(∀xB(x)→ F(x))
換而言之“隻要是鳥就會飛，這種情況是不成立的”，上句話也可以編碼為：∃ x(B(x) ∧﹁F(x) )
是以可知，在某些量詞形式之間存在着語義的等價。本節就對其中的一些最常見和最常用的量詞等價給出證明。
定理： 設Φ和Ψ是謂詞邏輯公式，則具有下面的等價關系：
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Φ
這裡出現了一個概念：自由變量。這是一個和謂詞邏輯公式文法樹相關聯的概念，還記得文法樹的概念嗎？
引入量詞後，文法樹變化并不大。下面是(∀x(P(x) ∧ Q(x))) -> (┐P(x) ∨ Q(y))的文法樹：
如果x是Φ的文法分析樹中的一個葉結點，而且不存在從結點x到∀x或∃x的向上路徑就稱x的出現是自由的。否則，稱x的出現是限制的。對∀xΦ或∃xΦ，我們稱除去Φ的任何形如∀x或∃x的子公式的Φ分别是∀x或∃x的作用範圍。那麼你能說出上面這個文法樹中哪個變量是自由的哪個是限制的嗎？
3.(a)∀xΦ∧∀xΨ⇔∀x(Φ∧Ψ)
(b)∃xΦ∨∃xΨ⇔∃x(Φ∨Ψ)
4.(a)∀x∀yΦ⇔∀y∀xΦ
(b)∃x∃yΦ⇔∃y∃xΦ
看完這些等價公式，有沒有感覺很自然。不過即使這樣，我們也需要證明它們。
證明就需要用到量詞的演算規則：
（1）等價關系規則
等價引入規則，不需要前提，一個變量總是和它自身相等
等價消去規則，使用了代換。說一下代換的概念：
給定變量x、項t和公式Φ，定義Φ[t/x]為用t代替Φ中的變量x的每個自由出現而得到的公式。
變量隻是占位符，我們需用更具體的資訊代替它，使其具有某種含義。從文法角度來講，我們常用一個完全項t的文法分析樹去代換葉結點x。由公式的定義，對x的代換隻能是項，不會是謂詞表達式，或者更複雜的公式，因為x隻作為謂詞符号的變量出現。切記在用t代換x時，必須避開那些受限制的變量x，因為它們處在某個∀x或∃x的作用範圍，分别表示某些非特指的或所有的值。
此種變量代換也會産生意外副作用，如果t包含變量y，x在Φ中的自由出現處于Φ中∀x 或∃x的作用範圍内。這種預料之外的變量捕捉是無論如何要避免的。
比如：考慮下圖分析樹公式Φ，并令t是f(y,y)。x在Φ中的兩次出現全是自由的，出現在最左端的x可以被代換，因為它不在任何量詞的作用範圍之内。但是最右端葉結點x會引入一個t中的新變量y，它被∀y限制，是以f(y,y)對Φ中的x不是自由的。
（2）全稱量詞消去規則
全稱量詞引入規則
（3）存在量詞引入規則
存在量詞消去規則
這一篇說到這，其中概念很多，了解上也比較難。
下一篇需要用到剛說的量詞證明規則和前面的命題演算規則對等價關系進行證明。