下载掌阅APP，畅读海量书库
立即打开
定义2.4.1 设 A 和 B 是任意两个谓词公式，如果 A ←→ B 是永真式，则称谓词公式 A 和 B 等价 或 等值 ，记为 A ⇔ B 。
由定义显然可以看出，谓词公式 A 和 B 等价的充要条件是：在任意解释下，谓词公式 A 和 B 的真值都相同。
由于命题逻辑中的永真式的代换实例都是谓词逻辑中的永真式，所以命题逻辑中的等价式的代换实例是谓词逻辑中的等价式。
例如，
的代换实例
，
的代换实例
都是谓词逻辑中的等价式。
除了由命题逻辑中的等价式的代换实例得到的谓词逻辑等价式外，还有许多谓词逻辑中特有的等价式。下面给出一些常用的基本谓词公式等价式。
定理2.4.1（量词否定转换律） 设 A （ x ）是任意谓词公式，则有
1）
2）
证明
1）
为真⇔∀
xA
（
x
）为假⇔∃
a
使
A
（
a
）为假⇔∃
a
使
为真⇔
为真，所以
。
2）
为假⇔∃
a
使
为假⇔∃
a
使
A
（
a
）为真⇔∃
xA
（
x
）为真
为假，所以
。
◀
定理2.4.2 （ 量词辖域扩张和收缩律 ）设 A （ x ）是包含 x 为自由变元的公式， B 是不包含 x 的公式，则有
1）∀ x （ A （ x ）∧ B ）⇔∀ xA （ x ）∧ B
2）∀ x （ A （ x ）∨ B ）⇔∀ xA （ x ）∨ B
3）∃ x （ A （ x ）∧ B ）⇔∃ xA （ x ）∧ B
4）∃ x （ A （ x ）∨ B ）⇔∃ xA （ x ）∨ B
5）∀ xA （ x ）→ B ⇔∃ x （ A （ x ）→ B ）
6）∃ xA （ x ）→ B ⇔∀ x （ A （ x ）→ B ）
7） B →∀ xA （ x ）⇔∀ x （ B → A （ x ））
8） B →∃ xA （ x ）⇔∃ x （ B → A （ x ））
证明 仅证5），其余证明留给读者。
5）
定理2.4.3 （ 量词分配律 ）设 A （ x ）， B （ x ）是包含自由变元 x 的公式，则有
1）∀ xA （ x ）∧∀ xB （ x ）⇔∀ x （ A （ x ）∧ B （ x ））
2）∃ xA （ x ）∨∃ xB （ x ）⇔∃ x （ A （ x ）∨ B （ x ））
证明 1）设 I 为任意解释。
如果∀ xA （ x ）∧∀ xB （ x ）在 I 下为真，则∀ xA （ x ）和∀ xB （ x ）都为真，于是对于任意一个个体 a 都有 A （ a ）∧ B （ a ）为真，所以∀ x （ A （ x ）∧ B （ x ））为真，因此∀ xA （ x ）∧∀ xB （ x ）⇒∀ x （ A （ x ）∧ B （ x ））。
如果∀ x （ A （ x ）∧ B （ x ））在 I 下为真，则对于任意一个个体 a 都有 A （ a ）和 B （ a ）为真，从而∀ xA （ x ）和∀ xB （ x ）都为真，于是∀ xA （ x ）∧∀ xB （ x ）为真，因此∀ x （ A （ x ）∧ B （ x ））⇒∀ xA （ x ）∧∀ xB （ x ）。
故∀ xA （ x ）∧∀ xB （ x ）⇔∀ x （ A （ x ）∧ B （ x ））。
2）证明与1）类似。
◀
这个定理说明，全称量词对合取满足分配律，存在量词对析取满足分配律。
定理2.4.4 设 A （ x , y ）是包含自由变元 x 、 y 的二元谓词公式，则有
1）∀ x ∀ yA （ x ， y ）⇔∀ y ∀ xA （ x ， y ）
2）∃ x ∃ yA （ x ， y ）⇔∃ y ∃ xA （ x ， y ）
下面通过例子来说明定理2.4.4是成立的。
设 A （ x ， y ）表示 x 回答了问题 y ， x 的个体域是学生集合， y 的个体域是问题集合。则∀ x ∀ yA （ x ， y ）表示所有学生回答了所有问题；∀ y ∀ xA （ x ， y ）表示所有的问题所有学生回答了。显然这两个句子的含义是相同的，故∀ x ∀ yA （ x ， y ）⇔∀ y ∀ xA （ x ， y ）。
同理，∃ x ∃ yA （ x ， y ）表示一些学生回答了一些问题，∃ y ∃ xA （ x ， y ）表示一些问题有一些学生回答了。显然，这两句的含义也是相同的，故∃ x ∃ yA （ x ， y ）⇔∃ y ∃ xA （ x ， y ）。
利用上面的等价关系式可以进行谓词公式的等价推演。在进行等价推演时，可以利用置换规则，将公式中的一个子公式用和它等价的公式代替；还可以利用换名规则或代入规则更改变元名，使得谓词公式不含既是约束出现又是自由出现的变元。
例2.4.1 证明下面的等价式成立。
1）
2）∃ xA （ x ）→ B （ x ）⇔∀ y （ A （ y ）→ B （ x ））
3）∀ xA （ x ）→∃ xB （ x ）⇔∃ x （ A （ x ）→ B （ x ））
证明
在谓词逻辑中有一些蕴含式，蕴含式的定义如下。
定义2.4.2 设 A 和 B 是任意两个谓词公式，如果 A → B 是永真式，则称谓词公式 A 蕴含 B ，记为 A ⇒ B ，称 A ⇒ B 为 蕴含式 。
定理2.4.5 设 A （ x ）、 B （ x ）是包含自由变元 x 的公式，则有
1）∀ xA （ x ）∨∀ xB （ x ）⇒∀ x （ A （ x ）∨ B （ x ））
2）∃ x （ A （ x ）∧ B （ x ））⇒∃ xA （ x ）∧∃ xB （ x ）
3）∀ x （ A （ x ）→ B （ x ））⇒∀ xA （ x ）→∀ xB （ x ）
4）∃ x （ A （ x ）→ B （ x ））⇒∀ xA （ x ）→∃ xB （ x ）
证明 仅证1）和3），2）、4）留给读者证明。
1）若∀ x （ A （ x ）∨ B （ x ））为假，则存在个体 a 使 A （ a ）∨ B （ a ）为假，于是 A （ a ）和 B （ a ）都为假，因而∀ xA （ x ）和∀ xB （ x ）都为假，从而∀ xA （ x ）∨∀ xB （ x ）为假。所以∀ xA （ x ）∨∀ xB （ x ）⇒∀ x （ A （ x ）∨ B （ x ））。
3）利用推理的CP规则，∀
x
（
A
（
x
）→
B
（
x
））∧∀
xA
（
x
）⇔∀
x
（
A
（
x
）→
B
（
x
））∧
A
（
x
））⇔
，所以∀
x
（
A
（
x
）→
B
（
x
））⇒∀
xA
（
x
）→∀
xB
（
x
）。
◀
例2.4.2 证明下面的蕴含式成立。
1）∀ xA （ x ）→∃ xB （ x ）⇒∃ x （ A （ x ）→ B （ x ））
2）∃ xA （ x ）→∀ xB （ x ）⇒∀ x （ A （ x ）→ B （ x ））
解
多个量词同时使用时，有下面的蕴含式。
◀
定理2.4.6 设 A （ x , y ）是包含自由变元 x , y 的二元谓词公式，则有
1）∀ x ∀ yA （ x ， y ）⇒∀ xA （ x ， x ）
2）∃ xA （ x ， x ）⇒∃ x ∃ yA （ x ， y ）
3）∀ x ∀ yA （ x ， y ）⇒∃ y ∀ xA （ x ， y ）
4）∀ y ∀ xA （ x ， y ）⇒∃ x ∀ yA （ x ， y ）
5）∃ y ∀ xA （ x ， y ）⇒∀ x ∃ yA （ x ， y ）
6）∀ x ∃ yA （ x ， y ）⇒∃ y ∃ xA （ x ， y ）
7）∃ x ∀ yA （ x ， y ）⇒∀ y ∃ xA （ x ， y ）
8）∀ y ∃ xA （ x ， y ）⇒∃ x ∃ yA （ x ， y ）
证明 1）设 I 为任意解释，如果∀ xA （ x ， x ）在解释 I 下为假，则存在一个个体 a ，使得 A （ a ， a ）为假，于是∀ yA （ a ， y ）为假，因而∀ x ∀ yA （ x ， y ）为假，所以∀ x ∀ yA （ x ， y ）⇒∀ xA （ x ， x ）。
◀
其余留给读者证明。