「証明」の版間の差分

削除された内容追加された内容

インライン

2008年1月7日 (月) 05:41時点における版

証明（しょうめい）とは、ある事柄が間違いないことを明らかにすること。また、その内容。

ある命題が、事前に認められた仮定(公理という)から、事前に認められた推論規則のみを用いて有限ステップで導くことができるとき、その命題は証明可能であるといい、公理から命題を導くためのステップの有限列を証明と呼ぶ。

「P⇒Q」を証明したいとき、「P⇒Q」を直接証明する事を直接証明という。それに対し、「P⇒Q」が真であることを直接証明する代わりに、「P⇒Q」と同値な別の命題が真であることを証明する方法を間接証明という。(これらはあくまで直観的な分類に過ぎず、数学的な定義があるわけではない)。

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

対偶法（￢は否定）：命題P⇒Qを証明する代わりに、これと同値な￢Q⇒￢Pを証明する方法。
背理法（∧は連言）：命題P⇒Qを証明する代わりに、P∧￢Qを仮定して矛盾を導く方法。
転換法：全ての状況がP、Q、Rのいずれかに分類できるとする。今「PならばA」、「QならばB」、「RならばC」が証明できていたとする。このときそれらの逆「AならばP」、「BならばQ」、「CならばR」も成立する。
ディリクレの箱入れ論法：n+1個以上のボールのそれぞれがn個の箱のいずれかに入っているとする。このとき、少なくとも一つの箱には2つ以上のボールが入っている。
数学的帰納法：自然数に関する命題P(n)が全てのnに対して成立する事を示す論法。まずP(1)が成立する事を示し、次にP(n)が成立すればP(n+1)が成立する事を示す。なお、数学的「帰納法」という名前だが、実際には帰納法ではなく演繹法である。
反例：ある命題P⇒Qが偽であることを示すには、「PであってQではない」という反例をあげればよい。
否定：ある命題pの否定が偽であることが証明できれば、命題pは真である。

素数の個数は有限であると仮定する。すべての素数を掛け合わせた数に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に関する所属の対話証明が存在し、そしてその逆も言える事が知られている。

裁判官が、事実の存否につき確信を得た状態、または裁判官に確信を得させるための当事者の活動。疎明と対比される概念。

@@ 15行目: / 15行目: @@
 *[[鳩の巣原理|ディリクレの箱入れ論法]]：n+1個以上のボールのそれぞれがn個の箱のいずれかに入っているとする。このとき、少なくとも一つの箱には2つ以上のボールが入っている。
 *[[数学的帰納法]]：自然数に関する命題P(n)が全てのnに対して成立する事を示す論法。まずP(1)が成立する事を示し、次にP(n)が成立すればP(n+1)が成立する事を示す。なお、数学的「帰納法」という名前だが、実際には帰納法ではなく演繹法である。
-*[[反例]]：ある命題P⇒Qが偽であることを示すには、「PであってQではない」という反例をあげればよい。
+*[[反例]]：ある命題P⇒Qが[[偽]]であることを示すには、「PであってQではない」という反例をあげればよい。
+*[[否定]]：ある命題pの否定が偽であることが証明できれば、命題pは真である。
 ===その他の用語===