同値式
記号論理入門(前原)より引用
冪等律
$ A \land A \leftrightarrow A $ A \lor A \leftrightarrow A
交換律
$ A \land B \leftrightarrow B \land A $ A \lor B \leftrightarrow B \lor A
結合律
$ A \land (B \land C) \leftrightarrow (A \land B) \land C
$ A \lor (B \lor C) \leftrightarrow (A \lor B) \lor C
分配律
$ A \land (B \lor C) \leftrightarrow (A \land B) \lor (A \land C)
$ A \lor (B \land C) \leftrightarrow (A \lor B) \land (A \lor C)
ここまで最小論理の範囲内で証明可能(だと思う)．
以下は直観主義論理の世界
矛盾律
$ A \land \lnot A \leftrightarrow \bot
以下は古典論理の世界．
無矛盾律と排中律つまり二重否定の除去がないと証明できない．
排中律
$ A \lor \lnot A \leftrightarrow \top
同一律
$ (A \to A) \leftrightarrow \top
対偶
$ (A \to B) \leftrightarrow (\lnot A \to \lnot B)
ド・モルガンの法則
$ \lnot \lnot A \leftrightarrow A
$ \lnot (A \land B) \leftrightarrow \lnot A \lor \lnot B
$ \lnot (A \lor B) \leftrightarrow \lnot A \land \lnot B
吸収律
$ A \land (A \lor B) \leftrightarrow A, A \lor (A \land B) \leftrightarrow A
$ (\top \to A) \leftrightarrow A
$ (A \to \top) \leftrightarrow \top
$ (A \leftrightarrow \top) \leftrightarrow \top
$ (\bot \to A) \leftrightarrow \bot
$ (A \to \bot) \leftrightarrow \lnot A
$ (A \leftrightarrow \bot) \leftrightarrow \lnot A
ここまで命題論理の世界．
以下は述語論理の世界
束縛変数の文字について
$ \forall x F(x) \leftrightarrow \forall y F(y)
同種類の限量子について
$ \forall x \forall y F(x,y) \leftrightarrow \forall y \forall x F(x, y)
$ \exists x \exists y F(x,y) \leftrightarrow \exists y \exists x F(x, y)
異なる種類の限量子については同値式が成立しない．
$ \forall x \exists yと書くと$ \exists y \forall xと同値にはならない
口語的にいうと「すべてのxにおいて任意のy」と「任意のyにおいてすべてのx」は異なる
yという集合がxに包含されていれば成り立つのだが，それは証明できない
$ \forall xA \leftrightarrow A
$ \exists x A \leftrightarrow A
前者は直感的．後者は任意のxを仮定してAが真なのでAは真．
束縛変数$ xが対象式$ Aにおいて用いられておらず，(他の変数もしくは定数によって)常にAであるため，恒真式．
$ \forall x (A \land F(x)) \leftrightarrow A \land \forall xF(x)
$ \forall x (A \lor F(x)) \leftrightarrow A \lor \exists xF(x)
後者は双対の原理より．
$ \forall x (A \to F(x)) \leftrightarrow (A \to \forall x F(x))
ド・モルガンの法則その2
$ \lnot \forall x F(x) \leftrightarrow \exists x \lnot F(x)
$ \lnot \exists x F(x) \leftrightarrow \forall x \lnot F(x)