論理的同値

どんな真理値の割り当てでも同じ真偽になる関係。$A\equiv B$。

$A\leftrightarrow B$ が恒真式（トートロジー）であることと同じ。

主な同値則#

名前	式
ド・モルガン	$\neg (P\wedge Q)\equiv \neg P\vee \neg Q$
対偶	$P\to Q\equiv \neg Q\to \neg P$
含意の除去	$P\to Q\equiv \neg P\vee Q$
分配則	$P\wedge (Q\vee R)\equiv (P\wedge Q)\vee (P\wedge R)$
二重否定	$\neg \neg P\equiv P$

量化子の否定#

$$\neg \forall xP(x)\equiv \exists x\neg P(x)$$

「すべてがそうではない」＝「そうでないものがある」。 反例 1 つで全称命題を否定できる根拠がこれ。

$$\neg \exists xP(x)\equiv \forall x\neg P(x)$$

何に使うか#

• 論理式の簡約 — 回路の最適化、コンパイラの最適化
• 証明の言い換え — 対偶を示す、含意を分解する
• 標準形への変換 — SAT ソルバへの入力を作る

二重否定則は直観主義論理では成り立たない。 $\neg \neg P\to P$ を認めることが、 背理法を認めることと対応している。

参考文献#

• Herbert B. Enderton. A Mathematical Introduction to Logic, 2nd ed. Academic Press, 2001. https://doi.org/10.1016/b978-0-08-049646-7.50005-9
• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html