KATUBLO
2019年02月03日

【命題論理】3つの証明方法、直接法、対偶法、背理法をわかりやすく解説するよ!

ゴール

証明手法である、直接法、対偶法、背理法を理解する。

 

証明の形式

数学の定義というのは以下の表現を持つ。

 

 

ある仮定(pが使われることが多い)のもとで、

ある結論(qが使われることが多い)が成り立つ。

 

これを記号を用いて表すと

 

$$
p \rightarrow q
$$

 

この命題が真であることを証明できれば、

 

$$
p \Rightarrow q
$$

 

となる。

([math]p \Rightarrow q[/math]というのは[math]p \rightarrow q[/math]の真理値が1であることを表す)

 

 

3つの証明方法

[math]p \Rightarrow q[/math]を示す為に、3つの証明方法が存在するので紹介する。

 

  1. 1.直接法
  2. 2.対偶法
  3. 3.背理法

 

これら3つに関して解説していく。

 

 

今回扱う命題

以下の命題をそれぞれの方法で証明する。

 

$$x = y ならば  x^2-2xy+y^2 =0  である$$

 

直接法

直接法というのは

$$pが真であると仮定して、qが真であることを示す$$

方法です。[math]p[/math]が偽であれば[math]p \rightarrow q[/math]は全て真である為。真理表を見ればこれがわかる。

 

 

 

直接法を用いて例題を証明する

[math]x = y [/math]が真であると仮定する。

[math]x^2-2xy+y^2 =0 [/math]の式に代入すると

 

$$ x^2-2x^2+x^2 = 0$$

$$ 0 = 0$$

 

となり、命題が真であることが証明された。

 

 

対偶法

対偶は高校でもならったと思うが、これを用いて証明する。

対偶について忘れてしまった人ように説明が載っているリンクを貼っておきます。

 

 

対偶法というのは

 

$$p \rightarrow q $$

$$
\overline { q } \rightarrow \overline { p }
$$

 

は同値であることを利用して、

 

$$
\overline { q } \rightarrow \overline { p } が真であること
$$

 

を示す。証明方法です。

 

対偶法を用いて例題を証明する

対偶法なので、

$$
x ^ { 2 } – 2 x y + y ^ { 2 } \neq 0  ならば
$$

$$
x \neq y
$$

 

を証明すればいい。

 

$$
x ^ { 2 } – 2 x y + y ^ { 2 } \neq 0
$$

$$
\begin{array} { c } { ( x – y ) ^ { 2 } \neq 0 } \end{array}
$$

 

よって

 

$$
x – y \neq 0
$$

 

であるので、命題は真である。

 

背理法

最後に背理法を紹介する。背理法というのは「仮定pを真と仮定して、結論qを否定すると矛盾がでる」ということ、すなわち

 

$$ p \wedge \overline { q }  $$

を示せばいい。

 

背理法を用いて例題を証明する

$$
x = y
$$

として、結論を否定すると

$$
x ^ { 2 } – 2 x y + y ^ { 2 } \neq 0
$$

 

となる。

 

$$
x ^ { 2 } – 2 x y + y ^ { 2 } \neq 0
$$

$$
\begin{array} { c } { ( x – y ) ^ { 2 } \neq 0 } \end{array}
$$

 

となり、[math]x = y[/math] であるため、矛盾が生じる。よって命題は真となる。

 

 

 

感想・気づき

割と曖昧にしていた、大御所の証明方法を復習することができました。ビジネスの場面でロジカルシンキングというのが大事になってきますが、このような基礎知識があるのとないのでは雲泥の差がでるのかなって思います。

 

最後まで読んで頂き、ありがとうございました。
SNS等でのシェアが頂ければ幸いです。

関連記事

プロフィール

@KATUO

現在都内私立大学に通う大学4年生。大学では電気電子工学を専攻。大学2年の夏頃に、プログラマーの長期インターン募集の広告が目に止まり、独学でプログラミングの学習をスタート。この時期からプログラミングにどハマりし、現在までに「AIスタートアップ」「Webマーケティング会社」でエンジニアとしての業務に没頭してきた。

過去の投稿