証明
![]() | この記事はただいま大幅な改稿を行っています。 申し訳ございませんが編集の競合を避けるため、分割などの作業(ノート参照)が完了するまで編集を控えてくださるとありがたく存じます。ご迷惑をおかけしますが、ご協力お願いいたします。 設定期限もしくは貼付後72時間経っても工事が完了していない場合は、このテンプレートを除去しても構いません。 |
![]() |
![]() |
証明(しょうめい)とは、ある事柄が真理もしくは事実であることを明らかにすること。また、その内容。
一般用法
社会生活で、一般的に使用される用法としては、ある事柄に対する論説や理論・解答・判断・推理などの根拠・理由などを明らかにし、その事柄が真実であることなどを明らかにすることである[1]。 立証(りっしょう)とも呼ばれることもある。
証明されたものを、より確実にするための、あるいはその正当性を示す証拠や保証となるもの、およびそれを求める行為のことを裏付け(うらづけ)、裏書き(うらがき)と呼ぶ[1]。
![]() | この節の加筆が望まれています。 |
数学、記号論理学における証明
ある命題が正しいことを主張するための一連の演繹を証明 (英: Mathematical proof) と呼ぶ。証明の各段階においては、前提(公理、定理等の認められた事実)や仮定から推論規則によって新たな命題を導くという形態をとる。ある証明の中で導入された仮定は、証明の別の部分で証明されるか、その証明の中で否定され(背理法)なければならない。
命題 P を証明したいとき、P を直に証明することを直接証明と言う。それに対して P が真であることを直接証明する代わりに、P と同値な別の命題が真であることを証明する方法を間接証明と言う(これらはあくまで直観的な分類に過ぎず、数学的な定義があるわけではない)。
![]() | この節の加筆が望まれています。 |
代表的な証明方法
証明の代表的なテクニックを以下に示す。
- 対偶法 - 命題 P⇒Q を証明する代わりに、これと同値な ¬Q⇒¬P を証明する方法(¬は否定)。
- 背理法 - 命題 P を証明する代わりに、¬P が偽であることを証明する方法(¬P が偽であることを証明するには、¬P を仮定して矛盾を導けばよい)。
- 反例 - 命題「全てのxがP(x)を満たす」 が偽であることを示すには、 P(x) を満たさない x を一つあげればよい(¬∀xPx と ∃x¬Px が同値であることを利用する)。
- 転換法 - 全ての状況が 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個以上のボールが入っている。
- 数学的帰納法 - 自然数に関する命題 P(n) が全ての n に対して成立することを示す論法。まず P(1) が成立することを示し、次に P(n) が成立すれば P(n+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.」「(証明終わり)」「(証明終)」「(証終)」「(終)」「□」「■」「//」などが用いられる。
証明の例(背理法)
「素数は無限個存在する」という命題の証明は以下のようになされる。
pf. 素数の個数は有限であると仮定する。すべての素数を掛け合わせた数に1を足したものはどの素数で割っても1余り、割り切れない。すなわちそれ自体が素数であるか、ここで想定した最大の素数よりも大きい素数でしか割り切れないことを意味する。いずれにしても、すべての素数以外に素数が存在することになり仮定と矛盾する。よって仮定は間違っており、素数は無限に存在することが示された。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 に関する所属の対話証明が存在し、そしてその逆も言える事が知られている。
証明(法律学)
裁判官が、事実の存否につき確信を得た状態、または裁判官に確信を得させるための当事者の活動。疎明と対比される概念。