Skip to main content

Section 3.7 証明

演繹による推論を続けて、命題の真偽を明らかにすることを証明(proof)という。 証明は「命題が真であること」を明らかにする場合が多いが、「命題が偽であること」を明らかにする場合もある。

Subsection 3.7.1 直接法

示したい命題を直接示す証明方法は、直接法と呼ばれることが多い。 直接法を用いる場合、前提に対して同値な変形や定理などの規則を繰り返し適用することにより、結論を示すことが多い。 場合によっては、結論から前提の側に向けて同値な変形を繰り返していくこともある。

Subsection 3.7.2 反例を用いた証明

命題\(x \in A \implies x \in B\)が偽である(\(\overline{x \in A \implies x \in B}\))ことを示すには、反例(counterexample)と呼ばれる命題が成り立たないような具体例を1つ挙げることも多い。 この場合、反例が1つ見つかりさえすれば、通常の証明に比べて簡単に示すことができる。

定義 3.40. 反例.
命題\(x \in A \implies x \in B\)に対して、「\(A\)の要素だが\(B\)の要素でない\(x\)(\(x \in A \land x \notin B\))」を、命題\(x \in A \implies x \in B\)の反例(counterexample)という。
\begin{gather*} \overline{x \in A \implies x \in B} = \overline{\overline{x \in A} \lor x \in B} = \overline{\overline{x \in A}} \land \overline{x \in B} = x \in A \land x \not\in B \end{gather*}

Subsection 3.7.3 対偶を用いた証明

命題\(p \implies q\)の真偽を直接示しにくい場合には、元の命題の対偶\(\overline{q} \implies \overline{p}\)をとり、対偶を示して元の命題を示せることがある。

Subsection 3.7.4 背理法

証明したい命題\(p\)を直接示すのが難しい場合には、命題\(p\)が成り立たない(偽である)と仮定して矛盾(contradiction)を導く背理法が用いられることがある。

定義 3.42. 矛盾.
\(p\)を命題とするとき、命題\(p \land \overline{p}\)を\(p\)についての矛盾(contradiction)という。 命題\(p \land \overline{p}\)は常に偽である。
\begin{gather*} [ \overline{p} \implies \text{F} ] = [ \overline{\overline{p}} \lor \text{F} ] = [ p \lor \text{F} ] = p \end{gather*}

実際の背理法の手順は、次のようになる。

背理法は、示したい命題が単純すぎて議論を始めにくいときや、示したい命題より、その否定の方が変形などを行いやすいときに用いる。

「和が1になる3数のうちには\(\frac{1}{3}\)以上のものがある」ことを、背理法で証明したい。 命題「和が1になる3数のいずれかは\(\frac{1}{3}\)以上である」の否定は「和が1になる3数はいずれも\(\frac{1}{3}\)より小さい」であり、これが成り立つと仮定する。 3数を\(a, b, c\)とすると、\(a < \frac{1}{3}, b < \frac{1}{3}, c < \frac{1}{3}\)となる。 このとき、\(a + b + c < \frac{1}{3} + \frac{1}{3} + \frac{1}{3} = 1\)となるが、これは\(a + b + c = 1\)であることと矛盾する。 従って、仮定した命題「和が1になる3数はいずれも\(\frac{1}{3}\)より小さい」は偽であることが分かり、「和が1になる3数のうちには\(\frac{1}{3}\)以上のものがある」ことが示された。
「素数が無数にある」ことを、背理法で証明したい。 命題「素数が無数にある」の否定は「素数は有限個しかない」であり、これが成り立つと仮定する。 すると、素数の個数は自然数\(n\)を用いて\(n\)個と表すことができ、\(n\)個の素数を\(p_1, \cdots, p_n\)と表すことができる。 このとき、数\(p = p_1 p_2 \cdots p_n + 1\)を考えると、\(p\)を\(p_1\)で割ると1余り、\(p\)を\(p_2\)で割っても1余る。 同様にすると、\(p\)を\(p_i (i = 1, \cdots, n)\)で割ると1余るので、\(p\)は\(p_1, \cdots, p_n\)のいずれとも互いに素になることが分かる。 そのため\(p\)は\(p_1, \cdots, p_n\)のいずれとも異なる素数であるが、これは素数が\(p_1, \cdots, p_n\)しかないことと矛盾する。 従って、仮定した命題「素数は有限個しかない」は偽であることが分かり、「素数が無数にある」ことが示された。
「\(\sqrt{2}\)が無理数である」ことを、背理法で証明したい。 命題「\(\sqrt{2}\)が無理数である」の否定は「\(\sqrt{2}\)が有理数である(\(\sqrt{2} \in \mathbb{Q}\))」であり、これが成り立つと仮定する。 すると、有理数は分数の形で表せる数なので、\(\sqrt{2}\)は整数\(m, n\)を用いて\(\sqrt{2} = \frac{m}{n}\)と表すことができる。 このとき、分数\(\frac{m}{n}\)が既約分数である、つまり互いに素であるような整数\(m, n\)をとることができる。 \(\sqrt{2} = \frac{m}{n}\)の両辺を2乗すると\(2 = \frac{m^2}{n^2}\)より\(m^2 = 2 n^2\)となり、\(n\)は整数\(n^2\)の2倍であるから\(m^2\)は偶数である。 ここで、対偶を用いると命題「\(m^2: \text{偶数} \implies m: \text{偶数}\)」が成り立つことがいえる。 \(m\)は偶数であるので、整数\(k\)を用いて\(m = 2k\)と表せる。 \(n^2 = \frac{m^2}{2} = \frac{(2k)^2}{2} = 2k^2\)となるので、\(n^2\)も偶数である。 先の命題を用いると、\(n\)は偶数であることが分かり、\(m, n\)はいずれも2で割り切れることが分かるが、これは\(m, n\)が互いに素であることと矛盾する。 従って、仮定した命題「\(\sqrt{2} \in \mathbb{Q}\)」は偽であることが分かり、「\(\sqrt{2}\)が無理数である」ことが示された。