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