前面说到了谓词逻辑的一些等价关系：
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(Φ∨Ψ)
其余等价关系类似，有兴趣可以自己尝试一下。
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
