Gourt Home::Gourt :: 証明
証明（一般）
証明（しょうめい）とは、ある事柄が間違いないことを明らかにすること。
関連項目
証明（数学、記号論理学）
ある命題が、事前に認められた仮定(公理という)から、事前に認められた推論規則のみを用いて有限ステップで導くことができるとき、その命題は証明可能であるといい、公理から命題を導くためのステップの有限列を証明と呼ぶ。
より正確には次の通り。
- 言語を一つ固定し、その言語に属する語を命題という。
- 命題の集合を一つ固定し、その集合に属する命題を事前に認められた仮定として採用し、それを公理と呼ぶ。
- 命題の有限個の組がどのような条件を満たせば、それらの命題から別の命題が導けるのかを決めたルールの組を決め、それらのルールを推論規則という。
- 公理の集合と推論規則の集合の組を公理系と呼ぶ。
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は定理であるという。
証明の例（背理法）
- 素数の個数は有限であると仮定する。すべての素数を掛け合わせた数に1を足したものはどの素数で割っても1余り、割り切れない。すなわちそれ自体が素数であるか、ここで想定した最大の素数よりも大きい素数でしか割り切れないことを意味する。いずれにしても、すべての素数以外に素数が存在することになり仮定と矛盾する。よって仮定は間違っており、素数は無限に存在することが示された。(QED)
健全性と完全性
Aを公理系とする。 Aが性質1を満たすときAは健全であるといい、Aが性質2を満たすときAは完全であるという：
正しくない事が推論されてしまう公理系は無意味なので、記号論理学では原則として、健全性を満たす公理系のみをあつかう。
命題論理と述語論理が完全性を満たす事はクルト・ゲーデルによって証明された。 それに対し、自然数論を含む無矛盾な公理系は完全性を満たさない(ゲーデルの第一不完全性定理)。 すなわちこのような公理系では、正しいのに証明できない命題が存在する。
(注：「ゲーデルの第一不完全性定理」という言葉の最後にある「定理」という単語はいわゆるメタ定理の事であり、通常の意味での定理ではない。「ゲーデルの第一不完全性メタ定理」といったほうがより正確であろうが、慣習的に「ゲーデルの第一不完全性定理」という)。
ゲーデルの不完全性定理ははじめ、自然数論を含むω無矛盾な公理系に対してクルト・ゲーデルによって証明されたが、その後条件が緩和され、単に無矛盾であれば不完全性定理が成立する事が証明された。
なお、自然数論を含む無矛盾な公理系は自己の無矛盾性を証明できない(ゲーデルの第二不完全性定理)。
アラン・チューリングは、任意のチューリング機械の停止性問題を解く事ができるアルゴリズムは存在しない事を示したが、ゲーデルの不完全性定理はこの定理の一般化である。
関連項目
証明（計算機科学）
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に関する所属の対話証明が存在し、そしてその逆も言える事が知られている。
証明（論理学）
命題P→Q(→は内含)が真であることを、個々の命題の内容と正しい推論をくり返すことによって明らかにすること。 以下に証明を分類する。
直接証明法
命題P→Qそのものが真であることを証明する方法である。間接証明法
命題P→Qが真であることを証明するために、これと同値なR→Sが真であることを証明する方法である。- 対偶法（￢は否定）
- 命題P→Qを証明する代わりに、これと同値な￢Q→￢Pを証明する方法。
- 背理法（∧は連言）
- 命題P→Qを証明する代わりに、P∧￢Q→O（矛盾）を証明する方法。つまりPが真でQが偽とすると矛盾することを示して、P→Qが真であることを示す方法である。
- 転換法
- 一群の証明された定理があり、その仮定が全ての場合をつくしていて、かつその結論が同時には成立しないとき、これらの定理の逆は全て成立するという方法である。
証明（法律学）
裁判官が、事実の存否につき確信を得た状態、または裁判官に確信を得させるための当事者の活動。疎明と対比される概念。
関連項目
প্রমাণ | Beweis | Proof | Preuve | Dokaz | Dimostrazione | Dowód | Prova | Доказательство | Proof | Bevis
"証明"