一、谓词公式等价

若 $A \leftrightarrow B$ 为永真式（或者称为逻辑有效式），则 $A$与$B$ 等价 ，记为 $A \Leftrightarrow B$ 。

二、常见的谓词公式等价

1. 置换规则

置换规则：使用命题逻辑中的等值式，将谓词公式代入。

2. 量词取反规则

$\neg \exists x(F(x)) \Leftrightarrow \forall x(\neg F(x)), \ \ \neg \forall x(F(x)) \Leftrightarrow \exists x(\neg F(x))$

$\neg \exists x(M(x) \wedge F(x)) \Leftrightarrow \forall x(\neg M(x) \vee \neg F(x)) \Leftrightarrow \forall x(M(x) \rightarrow \neg F(x))$

$\neg \forall x(M(x) \rightarrow F(x)) \Leftrightarrow \neg \forall x(\neg M(x) \vee F(x)) \Leftrightarrow \exists x(M(x) \wedge \neg F(x))$

并不是所有兔子都比乌龟跑得快。

$\neg \forall x \forall y ((R(x) \wedge T(y))\to F(x, y)) \Leftrightarrow \exists x \exists y (R(x) \wedge T(y) \wedge \neg F(x, y))$

3. 量词的辖域收缩/扩张

$\forall x (F(x) \wedge G) \Leftrightarrow \forall xF(x) \wedge G$,

$\forall x (F(x) \vee G) \Leftrightarrow \forall xF(x) \vee G$

$\forall x (F(x) \rightarrow G) \Leftrightarrow \exists xF(x) \to G$

$\forall x (G \rightarrow F(x)) \Leftrightarrow G \to \forall x F(x)$

<aside> 📌 证明：

1. $\forall x (F(x) \wedge G) \xLeftrightarrow{x \in \{a, b\}} (F(a) \wedge G) \wedge (F(b) \wedge G) \Leftrightarrow ((F(a) \wedge F(b)) \wedge G) \Leftrightarrow \forall xF(x) \wedge G$
2. ..
3. $\forall x (F(x) \rightarrow G) \Leftrightarrow \forall x (\neg F(x) \vee G) \Leftrightarrow \forall x \neg F(x) \vee G \Leftrightarrow \neg \exists x F(x) \vee G \Leftrightarrow \exists xF(x) \to G$ </aside>

对称性很好，上面各式 $\exists, \forall$ 反过来也一样。

4. 量词分配等值式

$\forall x (A(x) \wedge B(x)) \Leftrightarrow \forall x A(x) \wedge \forall x B(x) \Leftrightarrow \forall x A(x) \wedge \forall y B(y)$