形式陈述

命题公式 $\varphi$$\phi$ 与 $\psi$$\psi$ 逻辑等价，记 $\varphi\equiv\psi$$\phi \equiv \psi$，当且仅当对每个真值赋值 $v$$v$ 都有 $v(\varphi)=v(\psi)$$v(\phi )=v(\psi )$。等价地，$\varphi\leftrightarrow\psi$$\phi \leftrightarrow \psi$ 是重言式；一阶公式则需相对于所有结构与变量赋值定义。

直觉

逻辑等价表示两个表达式在任何允许解释下都说同一件事，而不仅是在某个例子中同真或同假。它是语义层面的可替换性。

例子与边界

$P\Rightarrow Q\equiv\neg P\lor Q$$P\Rightarrow Q\equiv \mathrm{\neg }P\vee Q$，且 $\neg(P\land Q)\equiv\neg P\lor\neg Q$$\mathrm{\neg }(P\wedge Q)\equiv \mathrm{\neg }P\vee \mathrm{\neg }Q$。$P\Rightarrow Q$$P\Rightarrow Q$ 与 $Q\Rightarrow P$$Q\Rightarrow P$ 不等价；在某一行真值表上相同不足以证明逻辑等价。

推论与应用

等价变换用于化简公式、逆否证明、逻辑电路和查询规范化。语法相同、可证明等价与语义等价是不同层次。

参考资料

• Daniel J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019, Logic chapters。
• Herbert B. Enderton, A Mathematical Introduction to Logic, 2nd ed., Academic Press, 2001, Chapter 1。