証明 Proofs
命題P(p、q、r、…)が真の時、命題Q（p、q、r、…)が真である事が論理的に導ける時、その論理的推論過程を証明(Proof)という。
定理(theorem)は真であることが証明できる命題であり、公理(axiom)は証明の際に真として使うことができる命題である。
定理よりも重要性は低いが他の結果の証明に役立つ補題(lemma)、ある命題から導き出せる結論をcorollaryという。
推論(conjecture)は証明をする際に真と仮定したりする命題のことで、度々偽になることがあるので定理ではない。
<直接証明(Direct Proof)>
pが真である時、必ずqが真でなければならない事を示す事によって、含意(logically imply)p→qが真である事を確立する方法である。
例：
直接証明を使って、「２つの奇数の積は奇数である」事を証明する。
ある奇数を２k＋１とし、もう１つの奇数を２m＋１とする。２つの奇数の積は、
（２k＋１）（２m＋１）＝４km＋２k＋２m＋１＝２（２km＋k＋m）＋１
∴２つの奇数の積は奇数である。
<矛盾を使う証明(Proof by Contradiction)>
もし命題pが真であることが、矛盾qおよび含意¬p→qが真である事によって証明されれば命題pは矛盾を使って証明されるとする。
例：
矛盾を使って「０でない有理数と無理数の積は無理数である」事を証明する。
xを有理数、yを無理数とすると、xはx＝a/bと表すことができる。
ここで、有理数と無理数の積を有理数であると仮定すると、xy＝p/qと表すことが出来るので、xy＝p/q＝(a/b)y
yについて解くと、y＝pb/qa
yは無理数であるが、pb/qaは有理数であるため矛盾が生じる。
ある命題が偽である事を証明するには、反例(counterexample)を挙げれば良い。
例：
「もしaとbが有理数なら、a^bも有理数であるかどうか」を証明する。
a＝２、b＝1/2とすると、a^b＝２^(1/2)＝√２
√２は無理数であるため、この命題の反例である。
