Section 11.3 命題と定理
「正しい」かどうか明確に定まる文を命題(proposition)という。 命題\(P\)が「正しい」とき「\(P\)は真(true)である」といい、そうでないとき「\(P\)は偽(false)である」という[107][108]。 真である命題を一般に定理(theorem)というが、一般的には、真である命題のうち特に重要なものを指して「定理」と呼ぶことが多い。
\(P, Q\)が命題のとき、「\(P\)ならば\(Q\)である」という形の命題を、「ならば」の意味を表す記号「\(⇒\)」を使って「\(P ⇒ Q\)」と表す。 例えば、「\(x\)がネコならば、\(x\)は動物である」という命題は「\(x \in \text{ネコ} ⇒ x \in \text{動物}\)」と表せる。
日常会話では、命題「\(x\)がネコならば、\(x\)は動物である」をより単純に「ネコは動物である」と表すことがある。 「ネコは動物である」も真偽が定まるので命題だが、「ネコ」「動物」は単なる集合で真偽が定まらないため、この命題を「\(\text{ネコ} ⇒ \text{動物}\)」と表すことはできない。 代わりに、部分集合を表す記号「\(\subset\)」を使うと、この命題は「\(\text{ネコ} \subset \text{動物}\)」と表せる。
注釈 11.1. 「ならば」の形式的定義と対偶.
\(P, Q\)が命題のとき、命題「\(P ⇒ Q\)」の厳密な定義は「命題\(P\)が真であれば命題\(Q\)が真である」である。 従って「\(P ⇒ Q\)」が真となるのは、「\(P\)かつ\(Q\)」が成り立つときか、「\(P\)ではない(\(P\)が偽である)」ときである。 定義記号「\(:=\)」で記せば、「\((P ⇒ Q) := (\bar{P} \vee (P \wedge Q)) = ((\bar{P} \vee P) \wedge (\bar{P} \vee Q)) = (\bar{P} \vee Q)\)」となる。
この定義に従えば、「命題「\(P ⇒ Q\)」とその対偶「\(\bar{Q} ⇒ \bar{P}\)」の真偽は等しい」という定理は、次の式変形で示せる。
注釈 11.2. 「すべて」「ある」の形式的定義とその否定.
「すべて」や「ある」を含む命題については、Aristotleの時代から議論されてきた[107][108]。 集合\(X\)のすべての(任意の)要素\(x\)について命題\(P_x\)が成り立つことを、全称記号と呼ばれる記号「\(\forall\)」を使って「\(\forall x \in X, P_x\)」と表す。 また、集合\(X\)のある要素\(x\)について命題\(P_x\)が成り立つ(\(P_x\)が成り立つ\(x\)が存在する)ことを、特称記号と呼ばれる記号「\(\exists\)」を使って「\(\exists x \in X, P_x\)」と表す。 \(\forall, \exists\)はそれぞれ、「All」と「Exists」の頭文字を逆さにした記号である。 これらを、前のコラムで使った「\(:=\)」で形式的に定義すると、次のようになる。 なお、\(X = \{x_1, \cdots, x_n\}\)のとき\(\bigwedge_{x \in X} P_x := P_{x_1} \wedge \cdots \wedge P_{x_n}\)とする。
この定義を使うと、「すべての\(x\)について\(P_x\)が成り立つ」の否定が「ある\(x\)について\(P_x\)が成り立たない」になることや、「ある\(x\)について\(P_x\)が成り立つ」の否定が「すべての\(x\)について\(P_x\)が成り立たない」になることは、次の式変形で示せる。変形の途中ではde Morganの公式(\(\overline{A \wedge B} = \bar{A} \vee \bar{B}, \overline{A \vee B} = \bar{A} \wedge \bar{B}\))を使っている。