述語論理は、命題論理に加えて、「任意の（all）」と「適当な（some）」という対象の範囲を表す語により推論を行います。尚、「述語」とは対照の性質や関係を表します。
論理記号
以下に、述語論理で使われる論理記号について説明します。
任意の（$\forall$）
任意の（全ての）対象（自由変数）を表す場合、全称記号 $\forall$ を用います。任意の変数 $x$ について論理式 $F(x)$ が成り立つ場合、以下のように表します。
$$\forall xF(x) -①$$
論理式 $A$ が自由変数 $x$ を含まなければ、以下は自明です。
$$\forall xA\rightleftarrows A$$
適当な（$\exists$）
適当な（特定の）対象（束縛変数）を表す場合、存在記号 $\exists$ を用います。適当な変数 $x$ について論理式 $F(x)$ が成り立つ場合、以下のように表します。
$$\exists xF(x) -②$$
論理式 $A$ が自由変数 $x$ を含まなければ、以下は自明です。
$$\exists xA\rightleftarrows A$$
否定記号を使った表現
①の全称記号は、存在記号と否定記号を使って以下のように書き換えることができます。
$$\forall xF(x)\rightleftarrows\neg\exists x\neg F(x) -③$$
この右辺は「$F$ が成り立たない $x$ は存在しない」という意味なので、左辺の「全ての $x$ で $F$ が成り立つ」と言い換えることができます。
また、②の存在記号は、全称記号と否定記号を使って以下のように書き換えることができます。
$$\exists xF(x)\rightleftarrows\neg\forall x\neg F(x) -④$$
この右辺は「$F$ が成り立たないのは全ての $x$ ではない」という意味なので、左辺の「特定の $x$ で $F$ が成り立つ」と言い換えることができます。
公理系
述語論理では以下の公理系が採用されています。
- $\forall xF(x)\to F(t)$
- $\forall x(A\to F(x))\to(A\to\forall xF(x))$
最初の式は、右辺の「全ての $x$ で $F$ が成り立つ」ならば、左辺の「特定の $t$ で $F$ が成り立つ」ことを表しており、これを書き換えると以下のように表すことができます。
$$\forall xF(x)\to \exists xF(x)$$
ド・モルガンの法則
ド・モルガンの法則は以下のように表されます。
$$\neg\exists xF(x)\rightleftarrows\forall x\neg F(X) -⑤$$$$\neg\forall xF(x)\rightleftarrows\exists x\neg F(X) -⑥$$
⑤の左辺は「$F$ が成り立つ $x$ は存在しない」という意味なので、右辺の「全ての $x$ で $F$ は成り立たない」と言い換えることができます。
また、⑥の左辺は「$F$ が成り立つのは全ての $x$ ではない」という意味なので、左辺の「特定の $x$ で $F$ が成り立たない」と言い換えることができます。
⑤と⑥の証明
⑤の左辺に④を代入すると、
$$\neg\exists xF(x)\rightleftarrows\neg\neg\forall x\neg F(x)\rightleftarrows\forall x\neg F(x)$$
また、⑥の左辺に③を代入すると、
$$\neg\forall xF(x)\rightleftarrows\neg\neg\exists x\neg F(x)\rightleftarrows\exists x\neg F(x)$$
