数理論理学/命題論理

概要

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

用語の定義

テンプレート:定義 　命題を記号で表したものを命題変数という。以下より$T,F$を除く大文字のアルファベット（およびそれに添え字を付けたもの）は命題変数であり、その文字を単体で原子論理式（単に原子式とも）という。テンプレート:定義終わり 　命題論理では一般化された命題について考える分野であるため、命題変数は命題を一般化したものであると思って良い。 テンプレート:定義 　全て命題は真(TRUE)であるか偽(FALSE)であるかのいずれかである。よって、真でない命題は全て偽である。 テンプレート:定義終わり 　詳しくは前ページを参考すること。

真理関数　

　定義1.2では全て命題が真か偽かの2種類に分けられることを述べた。よって、命題に対し真、偽という2種類の値を定義することができる。 テンプレート:定義 　$P$を任意の命題とする、$P$の真理値を以下のように定義する。
$P=\{\begin{array}{cc}T& \text{if }P\text{ is TRUE}\\ F& \text{otherwise}\end{array}$ テンプレート:定義終わり 　真理値は、任意の命題$P$が真であったら$T$を持ち、そうでなければ(偽であれば)$F$を持つ値である、という解釈で間違いない。 テンプレート:定義 　集合$l=\{T,F\}$及び自然数$n$に対して、直積$l^n$から$l$への写像を（$n$変数の）真理関数という。 テンプレート:定義終わり 　直感的には、命題にいくつか（間に関係項のもった）連なりがあり、そこに真理関数を作用させていけば最終的にその連なり全体が真か偽いずれかになる、ということを示している。以下の具体例を見ればそれが分かりやすくなるだろう。その前に一つ定理を導いておく。 テンプレート:定理 　任意の命題$P$及び、先ほど定義された集合$l$に対し$P\in l$である。 テンプレート:定理終わり 　これは$P$が$T,F$いずれかの真理値を持つことから明らかである。 テンプレート:定義 　否定$\mathrm{\neg }$は一変数の真理関数であり、以下のように定義する。
$\mathrm{\neg }P=\{\begin{array}{cc}F& \text{if }P=T\\ T& \text{otherwise}\end{array}$ テンプレート:定義終わり 　真と偽をひっくり返す真理関数である。 テンプレート:定義 　理論和$\vee$は二変数の真理関数であり、以下のように定義する。
$P\vee Q=\{\begin{array}{cc}F& \text{if }P=Q=F\\ T& \text{otherwise}\end{array}$ テンプレート:定義終わり 　$P,Q$共に偽であるときでのみ$P\vee Q$も偽であるということを示す。つまり、$P$または$Q$を表している。 テンプレート:定義 　理論積$\wedge$は二変数の真理関数であり、以下のように定義する。
$P\wedge Q=\{\begin{array}{cc}T& \text{if }P=Q=T\\ F& \text{otherwise}\end{array}$ テンプレート:定義終わり 　$P,Q$共に真であるときでのみ$P\wedge Q$も真であるということを示す。つまり、$P$かつ$Q$を表している。 テンプレート:定義 　含意$\to$は二変数の真理関数であり、以下のように定義する。
$P\to Q=\{\begin{array}{cc}F& \text{if }P=T\wedge Q=F\\ T& \text{otherwise}\end{array}$
　そして以上で述べた真理関数$\mathrm{\neg },\vee ,\wedge ,\to$を論理結合子という。 テンプレート:定義終わり 　$P$が真であり、$Q$が偽であるときでのみ$P\to Q$が偽であるということを示す。つまり、$P$ならば$Q$を表している。
　以下より論理結合子を中心に議論していく。上の定義では真、偽の関係が分かりづらいため、真理値表を参考にすること。 テンプレート:Stub