証明 (数学)

ウィキペディア

索引トップランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/14 02:25 UTC 版)

代表的な方法

証明の代表的なテクニックを以下に示す。

対偶法: 命題 P⇒Q を証明する代わりに、これと同値な￢Q⇒￢P を証明する方法（￢は否定）。^[2]
背理法（帰謬法）: 命題 P を証明する代わりに、￢P が偽であることを証明する方法（￢P が偽であることを証明するには、￢P を仮定して矛盾を導けばよい）。^[3]
反例: 命題「全てのxがP(x)を満たす」が偽であることを示すには、 P(x) を満たさない x を一つあげればよいというもの。￢∀x, P(x) と ∃x, ￢P(x) が同値であることを利用する（∀は「全ての」、∃は「存在する」）。^[4]
転換法: 全ての状況が P, Q, R のいずれかに分類でき、A, B, C が独立であるとする。今「P⇒A」「Q⇒B」「R⇒C」が証明できていたとする。このとき、それらの逆「A⇒P」「B⇒Q」「C⇒R」も成立する。
同一法: A ⇒ B が成り立ち、B を満たすものがただひとつであれば、B ⇒ A が成り立つ。
ディリクレの箱入れ論法（鳩の巣原理）: n+1 個以上のボールのそれぞれが n 個の箱のいずれかに入っているとする。このとき、少なくとも1個の箱には2個以上のボールが入っている。^[5]
数学的帰納法: 自然数に関する命題 P(n) が全ての n に対して成立することを示す論法。まず P(1) が成立することを示し、次に P(n) が成立すれば P(n+1) が成立することを示す。^[6]

背理法による例

「素数は無限個存在する」という命題の証明は以下のようになされる。

証明 : 素数の個数は有限であると仮定する。すべての素数を掛け合わせた数に1を足したものはどの素数で割っても1余り、割り切れない。すなわちそれ自体が素数であるか、ここで想定した最大の素数よりも大きい素数でしか割り切れないことを意味する。いずれにしても、すべての素数以外に素数が存在することになり仮定と矛盾する。よって仮定は間違っており、素数は無限に存在することが示された。

脚注