証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』
証明（しょうめい）とは、ある事柄が真理もしくは事実であることを立証すること。また、その内容。
目次 |
[編集] 証明（数学、記号論理学）
ある命題が、事前に認められた仮定から、事前に認められた推論規則のみを用いて有限ステップで導くことができるとき、その命題は証明可能であるといい、公理から命題を導くためのステップの有限列を証明と呼ぶ。
[編集] 代表的な証明方法
P⇒Q を証明したいとき、P⇒Q を直に証明することを直接証明と言う。それに対して P⇒Q が真であることを直接証明する代わりに、P⇒Q と同値な別の命題が真であることを証明する方法を間接証明と言う（これらはあくまで直観的な分類に過ぎず、数学的な定義があるわけではない）。
証明の代表的なテクニックを以下に示す。
- 対偶法 - 命題 P⇒Q を証明する代わりに、これと同値な ￢Q⇒￢P を証明する方法（￢は否定）。
- 背理法 - 命題 P⇒Q を証明する代わりに、P∧￢Q を仮定して矛盾を導く方法（∧ は連言）。
- 転換法 - 全ての状況が P, Q, R のいずれかに分類でき、A, B, C が独立であるとする。今「P⇒A」「Q⇒B」「R⇒C」が証明できていたとする。このとき、それらの逆「A⇒P」「B⇒Q」「C⇒R」も成立する。
- ディリクレの箱入れ論法 - n+1 個以上のボールのそれぞれが n 個の箱のいずれかに入っているとする。このとき、少なくとも1個の箱には2個以上のボールが入っている。
- 数学的帰納法 - 自然数に関する命題 P(n) が全ての n に対して成立することを示す論法。まず P(1) が成立することを示し、次に P(n) が成立すれば P(n+1) が成立することを示す。
- 反例 - ある命題 P⇒Q が偽であることを示すには、「PであってQではない」という反例をあげればよい。
- 否定 - ある命題 p の否定が偽であると証明できれば、命題 p は真である。
[編集] その他の用語
- 存在証明 - 解が存在する事を示す行為
- 一意性証明 - （解がもし存在すれば）解の数は1つであることを示す行為
[編集] 証明の例（背理法）
- 素数の個数は有限であると仮定する。すべての素数を掛け合わせた数に1を足したものはどの素数で割っても1余り、割り切れない。すなわちそれ自体が素数であるか、ここで想定した最大の素数よりも大きい素数でしか割り切れないことを意味する。いずれにしても、すべての素数以外に素数が存在することになり仮定と矛盾する。よって仮定は間違っており、素数は無限に存在することが示された（QED）。
[編集] より厳密な定義
- 言語を1つ固定し、その言語に属する語を命題という。
- 命題の集合を1つ固定し、その集合に属する命題を事前に認められた仮定として採用し、それを公理と呼ぶ。
- 命題の有限個の組がどのような条件を満たせば、それらの命題から別の命題が導けるのかを決めたルールの組を決め、それらのルールを推論規則という。
- 公理の集合と推論規則の集合の組を公理系と呼ぶ。
Aを公理系とし、(P_1,...,P_n) を命題の列とする。
任意の i≦n に対し P_i が
- P_i は公理である
- P_i は、P_1,..., P_{i-1} から、許された推論規則によって導くことができる
のいずれかを満たすとき、(P_1,...,P_n) を P_n の（公理系 A における）証明と言う。
ある (P_1,...,P_n) があって、(P_1,...,P_n) が P_n の証明であるとき、P_n は（公理系 A において）証明可能である、もしくは P_n は定理であると言う。
[編集] 記述の習慣
証明を記述する際には、証明とそれ以外の部分をはっきりわけて可読性をあげるため、証明の始めと終わりを明確に示す習慣があり、特に高等学校などで初めて証明の記述を学ぶ者に対しては厳しく指導される。始めや終わりを示す記号は書く人の好みによりさまざまであるが、始めには「proof」「（証明）」「（証）」、丸で囲んだ「∵」などが、終わりには「Q.E.D.」「（証明終）」「（証終）」「（終）」「□」「//」などが用いられる。
[編集] 証明（計算機科学）
対話 (P,V) が
- Completeness - 任意の x∈L に対し、(P,V)(x) は、x のビット長に関して 1/2 + non negligible な確率で accept される
- Soundness - L に属さない任意の x、および任意の計算機 P^* に対し、(P^*,V)(x) は、x のビット長に関して 1/2 + non negligible な確率で reject される
を満たすとき、(P,V) は L に関する所属の対話証明あるいは単に証明と言い、P を証明者、V を検証者と言う。
L がPSPACEに属する言語であれば L に関する所属の対話証明が存在し、そしてその逆も言える事が知られている。
[編集] 証明（法律学）
裁判官が、事実の存否につき確信を得た状態、または裁判官に確信を得させるための当事者の活動。疎明と対比される概念。
[編集] 関連項目
 |
この項目「証明」は、自然科学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。 |
