PS

矛盾と否定

記号論理

矛盾

矛盾 $\bot$ を

$\forall A(\bot \Rightarrow A)$

を満たす何らかの命題と定義する。

否定

命題Aの否定を

$\neg A \equiv (A \Rightarrow \bot)$

と定義する。

vacuously true

矛盾の定義より、前提が矛盾している命題は結論がどうあれ真である。こういう命題をvacuously trueという(らしい)。証明で便利な用語。

背理法

否定の定義より、「Aではない」と仮定して、矛盾が生じれば「Aでないことはない」となる。

命題

$(A \Rightarrow B) \Leftrightarrow (\neg A \vee B)$
- 最も重要な命題かもしれない
$(\neg \exists x F(x)) \Leftrightarrow (\forall x \neg F(x))$
$(\neg \forall x F(x)) \Leftrightarrow (\exists x \neg F(x))$
- ド･モルガンの法則の一種でよく使う

参考文献