述語論理は、命題論理に加えて、「任意の(all)」と「適当な(some)」という対象の範囲を表す語により推論を行います。尚、「述語」とは対照の性質や関係を表します。
論理記号
以下に、述語論理で使われる論理記号について説明します。
全称記号
任意の(全ての)対象(自由変数)を表す場合、全称記号 $\forall$ を用います。任意の変数 $x$ について論理式 $F(x)$ が成り立つ場合、以下のように表します。
$$\forall xF(x) -①$$
論理式 $A$ が自由変数 $x$ を含まなければ、以下は自明です。
$$\forall xA\rightleftarrows A$$
①の全称記号は、存在記号と否定記号を使って以下のように書き換えることができます。
$$\forall xF(x)\rightleftarrows\neg\exists x\neg F(x) -②$$
この左辺は「全ての $x$ で $F$ が成り立つ」という意味なので、右辺の「特定の $x$ でも $F$ が成り立たなくなることはない」と言い換えることができます。
存在記号
適当な(特定の)対象(束縛変数)を表す場合、存在記号 $\exists$ を用います。適当な変数 $x$ について論理式 $F(x)$ が成り立つ場合、以下のように表します。
$$\exists xF(x) -③$$
論理式 $A$ が自由変数 $x$ を含まなければ、以下は自明です。
$$\exists xA\rightleftarrows A$$
②の存在記号は、全称記号と否定記号を使って以下のように書き換えることができます。
$$\exists xF(x)\rightleftarrows\neg\forall x\neg F(x) -④$$
この左辺は「特定の $x$ で $F$ が成り立つ」という意味なので、右辺の「全ての $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) -⑥$$
⑤の左辺は「特定の $x$ でも $F$ が成り立つことはない」という意味なので、右辺の「全ての $x$ で $F$ は成り立たない」と言い換えることができます。⑤は、⑤の左辺に④を代入することで得られます。
$$\neg\exists xF(x)\rightleftarrows\neg\neg\forall x\neg F(x)\rightleftarrows\forall x\neg F(x)$$
⑥の左辺は「全ての $x$ で $F$ が成り立つことはない」という意味なので、左辺の「特定の $x$ で $F$ が成り立たない」と言い換えることができます。⑥は、⑥の左辺に②を代入することで得られます。
$$\neg\forall xF(x)\rightleftarrows\neg\neg\exists x\neg F(x)\rightleftarrows\exists x\neg F(x)$$

