証明 (数学)
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2021年7月) |
数学における証明 (しょうめい、英語: Mathematical proof) とは、ある命題が正しいことを主張するための一連の演繹のこと。証明の各段階においては、前提（公理、定理等の認められた事実）や仮定から推論規則によって新たな命題を導くという形態をとる。ある証明の中で導入された仮定は、証明の別の部分で証明されるか、その証明の中で否定されなければならない（背理法）。
命題 P を証明したいとき、P をそのまま証明することを直接証明という。それに対して P が真であることを直接証明する代わりに、P と同値な別の命題が真であることを証明する方法を間接証明という（これらはあくまで直観的な分類に過ぎず、数学的な定義があるわけではない）。
代表的な方法
証明の代表的なテクニックを以下に示す。
- 対偶法
- 命題 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余り、割り切れない。すなわちそれ自体が素数であるか、ここで想定した最大の素数よりも大きい素数でしか割り切れないことを意味する。いずれにしても、すべての素数以外に素数が存在することになり仮定と矛盾する。よって仮定は間違っており、素数は無限に存在することが示された。
その他の用語
- 存在証明 - 解が存在することを示す行為
- 一意性証明 - （解がもし存在すれば）解の数は1つであることを示す行為
証明の形式的定義
数学における命題の証明においては、通常、その正しさの確認は証明の作成者と読者に委ねられている。証明の概念を形式化することによって、その正しさを機械的に判定したり、証明そのものを数学の研究対象とすることもできる。
- 有限集合を1つ固定し、その有限集合の元をアルファベットという。
- アルファベットの有限列を語という。
- 語の集合を言語という。
- 言語を1つ固定し、その言語に属する語を命題という。
- 命題の集合を1つ固定し、その集合に属する命題を事前に認められた仮定として採用し、それを公理と呼ぶ。
- 命題の有限個の組がどのような条件を満たせば、それらの命題から別の命題が導けるのかを決めたルールの組を決め、それらのルールを推論規則という。
- 公理の集合と推論規則の集合の組を公理系と呼ぶ。
Aを公理系とし、(P1,...,Pn) を命題の列とする。
任意の i≦n に対し Pi が
- Pi は公理である
- Pi は、P1,..., Pi-1 から、許された推論規則によって導くことができる
のいずれかを満たすとき、(P1,...,Pn) を Pn の（公理系 A における）証明と言う。
ある (P1,...,Pn) があって、(P1,...,Pn) が Pn の証明であるとき、Pn は（公理系 A において）証明可能である、もしくは Pn は定理であるという。
記述の習慣
証明を記述する際には、証明とそれ以外の部分をはっきりわけて可読性をあげるため、証明の始めと終わりを明確に示す習慣があり、特に初等中等教育などで初めて証明の記述を学ぶ者に対しては厳しく指導される。
始めや終わりを示す記号は書く人の好みによりさまざまであるが、証明の始めには「proof」「prf.」「pf.」「［証明］」「【証】」や、丸で囲んだ「∵」などが使われる。
証明の終わりには「Q.E.D.」「／証明終わり」「［証明終］」「【証終】」「（おわり）」「□」「■」「∥」や、スラッシュと重ねた「⌋」などが用いられる。学生のノートやレポートでは、中空の正方形をハッチングで塗ったものが使われることが多い。
一般に、一つの内容を一行に収め、上の行から順に下の行に移るに従って、論証が進むように書かれ、その理由や用いた定理を丸カッコ（）でくくって書き添えることが多い。複数の行に書かれた内容を使って次の行が得られるときは、複数の行を中カッコ｛、｝でくくるか、行末に....〇の丸の中に数字を入れたタグを付け、次の行頭に「①,②より」などと、説明の流れを明らかにする文言を添える。
脚注
出典
- ^ Heath, T.L. (1908). The Thirteen Books of Euclid's Elements. 1. p. 242
- ^ https://manabitimes.jp/math/1152
- ^ https://manabitimes.jp/math/1141
- ^ https://www.try-it.jp/chapters-5621/sections-5861/lessons-5914/
- ^ https://manabitimes.jp/math/692
- ^ https://www.nli-research.co.jp/report/detail/id=68448?site=nli#:~:text=%E3%80%8C%E6%95%B0%E5%AD%A6%E7%9A%84%E5%B8%B0%E7%B4%8D%E6%B3%95%E3%80%8D%E3%81%A8,%E3%81%AE%EF%BC%91%E3%81%A4%E3%81%A7%E3%81%82%E3%82%8B%E3%80%82
関連項目
外部リンク
 | この項目は、数理論理学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。 |
数学的証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 23:48 UTC 版)
「ビハム・ミドルトン・レヴィン交通モデル」の記事における「数学的証明」の解説
このモデルは単純だが、厳密な解析は非常に困難である。このモデルに対する数学的証明は、これまでのところ、パラメーターが極端な値の場合に限定されて行われている。 2005年4月、ブリティッシュコロンビア大学のエンジェルらは、密度が1に近い場合、常に渋滞が発生することを厳密に証明した。 2006年、カリフォルニア大学ロサンゼルス校のティム・オースティンらは、N×Nの正方格子の場合、車の数がN/2以下であれば、常に全ての車が停止することなく移動できる状態になることを発見した。
※この「数学的証明」の解説は、「ビハム・ミドルトン・レヴィン交通モデル」の解説の一部です。
「数学的証明」を含む「ビハム・ミドルトン・レヴィン交通モデル」の記事については、「ビハム・ミドルトン・レヴィン交通モデル」の概要を参照ください。
「数学的証明」の例文・使い方・用例・文例
- 数学的証明
- 数学的証明のページへのリンク
