数理論理学/命題論理

概要[編集]

　命題論理とは、命題を記号（命題変数という）に置き換え、命題どおしの関係の規則について考える。（よって、命題一つ一つにおける構造についての構成は述語論理のページを参照されたい）そして、それらの命題変数を組み合わせである論理式について考察していく。

用語の定義[編集]

定義1.1

　命題を記号で表したものを命題変数という。以下より

T,F

を除く大文字のアルファベット（およびそれに添え字を付けたもの）は命題変数であり、その文字を単体で原子論理式（単に原子式とも）という。

　命題論理では一般化された命題について考える分野であるため、命題変数は命題を一般化したものであると思って良い。

定義1.2

　全て命題は真(TRUE)であるか偽(FALSE)であるかのいずれかである。よって、真でない命題は全て偽である。

　詳しくは前ページを参考すること。

真理関数　[編集]

　定義1.2では全て命題が真か偽かの2種類に分けられることを述べた。よって、命題に対し真、偽という2種類の値を定義することができる。

定義2.1

　 $P$ を任意の命題とする、 $P$ の真理値を以下のように定義する。
$P={\begin{cases}T&{\mbox{if }}P{\mbox{ is TRUE}}\\F&{\mbox{otherwise}}\end{cases}}$

　真理値は、任意の命題 $P$ が真であったら $T$ を持ち、そうでなければ(偽であれば) $F$ を持つ値である、という解釈で間違いない。

定義2.2

　集合 $l=\{T,F}\$ 及び自然数 $n$ に対して、直積 $l^{n}$ から $l$ への写像を（ $n$ 変数の）真理関数という。

　直感的には、命題にいくつか（間に関係項のもった）連なりがあり、そこに真理関数を作用させていけば最終的にその連なり全体が真か偽いずれかになる、ということを示している。以下の具体例を見ればそれが分かりやすくなるだろう。その前に一つ定理を導いておく。

定理2.1

　任意の命題 $P$ 及び、先ほど定義された集合 $l$ に対し $P\in l$ である。

　これは $P$ が $T,F$ いずれかの真理値を持つことから明らかである。

定義2.3

　否定 $\lnot$ は一変数の真理関数であり、以下のように定義する。
$\lnot P={\begin{cases}F&{\mbox{if }}P=T\\T&{\mbox{otherwise}}\end{cases}}$

　真と偽をひっくり返す真理関数である。

定義2.4

　理論和 $\lor$ は二変数の真理関数であり、以下のように定義する。
$P\lor Q={\begin{cases}F&{\mbox{if }}P=Q=F\\T&{\mbox{otherwise}}\end{cases}}$

　 $P,Q$ 共に偽であるときでのみ $P\lor Q$ も偽であるということを示す。つまり、 $P$ または $Q$ を表している。

定義2.5

　理論積 $\land$ は二変数の真理関数であり、以下のように定義する。
$P\land Q={\begin{cases}T&{\mbox{if }}P=Q=T\\F&{\mbox{otherwise}}\end{cases}}$

　 $P,Q$ 共に真であるときでのみ $P\land Q$ も真であるということを示す。つまり、 $P$ かつ $Q$ を表している。

定義2.6

　含意 $\rightarrow$ は二変数の真理関数であり、以下のように定義する。
$P\rightarrow Q={\begin{cases}F&{\mbox{if }}P=T\land Q=F\\T&{\mbox{otherwise}}\end{cases}}$
　そして以上で述べた真理関数 $\lnot ,\lor ,\land ,\rightarrow$ を論理結合子という。