命題と証明

正しいか、正しくないかが明確に決まる文や式を命題という。
命題が正しいことを真、正しくないことを偽という。
命題は2つの条件p, qを用いて
「p ならば q」
の形に表されるものが多い。 これを記号で
p q
と表し、pを仮定、qを結論という。
さらに「pならばq かつ qならばp」を
p qと表す。

条件pを満たす要素全体の集合をP, 条件qを満たす要素全体の集合をQとすると
p qが真ならばP⊂Qが成り立ち、
P⊂Qが成り立つならばp qは真である。
「p qが真」 「P⊂Qが成り立つ」
またp qとP=Qには次の関係が成り立つ
「p qが真」 「P=Qが成り立つ」

条件pにたいして「pではない」という条件を「pの否定」といい、pとあらわす。

条件pを満たす要素全体の集合をP, 条件qを満たす要素全体の集合をQとすると
pは補集合 Pとなり、
「pかつq」は共通部分　P∩Q、
「pまたはq」は和集合　P∪Qとなる。

ド・モルガンの法則から
P∩Q = P∪Q , P∪Q = P∩Q なので
p かつ q p または q
p または q p かつ q

命題p q が真であるとき
qはpであるための必要条件、
pはqであるための十分条件 という。
pq十分　　必要
また、p q と q pがともに真のとき、つまり p qが真のとき
p は q (q は p) であるための 必要十分条件という。
このとき 「pとqは同値である」 という。

命題　p q に対して
q p を逆
p q を裏
q p を対偶
という。

条件pを満たす要素全体の集合をQ, 条件qを満たす要素全体の集合をQとする。
「p q が真」のとき、P⊂Qなので、次の図のようになる。

図からわかるようにQの要素であってPの要素でないものもあるので
命題の逆 q p が真とは限らない。
ところが　Qの補集合QはPの補集合Pに含まれる。 Q ⊂ P
よって q p は真である。
つまり
「命題の真偽とその対偶の真偽は一致する。」
このため命題を証明するにはその対偶を証明してもよい。

命題が成り立たないと仮定すると矛盾することを導き、それによって命題が成り立つことを示す。
この証明法を背理法という。