論理式\(A_{1},\cdots ,A_{n}\)の論理和が前提であり、結論が論理式\(B\)で表される推論が与えられたとき、それぞれの\(i\ \left( =1,\cdots ,n\right) \)に対して推論\( A_{i}\ \therefore \ B \)が妥当であることを示すことができれば、もとの推論が妥当であることを示したことになります。これを場合分けと呼びます。また、場合分けを逆手にとった証明方法が総当たり法です。

2018年11月23日:公開

場合分け

まず、以下の命題が成り立ちます。

命題(場合分けの根拠)
任意の論理式\(A_{1},\cdots ,A_{n},B,C\)に対して以下が成り立つ。\begin{equation*}
\left( \bigvee_{i=1}^{n}A_{i}\right) \rightarrow B\Leftrightarrow \bigwedge_{i=1}^{n}\left( A_{i}\rightarrow B\right)
\end{equation*}
証明を見る(プレミアム会員限定)

論理式\(A_{1},\cdots ,A_{n}\)の論理和が前提であり、結論が論理式\(B\)で表される推論\begin{equation*}
\bigvee_{i=1}^{n}A_{i}\ \therefore \ B
\end{equation*}が与えられたとき、これを示す方法の 1 つは以下の論理式\begin{equation*}
\left( \bigvee_{i=1}^{n}A_{i}\right) \rightarrow B
\end{equation*}が恒真であることを示すというものですが、上の命題より、これは以下の論理式\begin{equation*}
\bigwedge_{i=1}^{n}\left( A_{i}\rightarrow B\right)
\end{equation*}と論理的に同値です。したがって、それぞれの\(i\ \left( =1,\cdots ,n\right) \)に対して以下の推論\begin{equation*}
A_{i}\ \therefore \ B
\end{equation*}が妥当であることを示すことができれば、もとの推論が妥当であることを示したことになります。これを場合分け(case analysis)と呼びます。

 

総当たり法

論理式\(A\)が前提であり、論理式\(B\)が結論であるような推論\begin{equation*}
A\ \therefore \ B
\end{equation*}が与えられたとき、前提に相当する論理式\(A\)に対して、\begin{eqnarray*}
&&\left( a\right) \ A=\bigvee_{i=1}^{n}A_{i} \\
&&\left( b\right) \ A_{1},A_{2},\cdots ,A_{n}\text{の中の2つが同時に真になることはない}
\end{eqnarray*}を満たすような有限\(n\)個の論理式\(A_{1},A_{2},\cdots ,A_{n}\)があるものとします。このとき、それぞれの\(i\ \left( =1,\cdots ,n\right) \)に対して以下の推論\begin{equation*}
A_{i}\ \therefore \ B
\end{equation*}が妥当であることを示すことができれば、先に示した場合分けにより、もとの推論が妥当であることを示したことになります。これを総当たり法(proof by exhaustion)と呼びます。

例(総当たり法)
正の整数\(n\)について\(n^{7}-n\)が\(7\)で割り切れることを証明します。\(n^{7}-n\)を因数分解すると、\begin{eqnarray*}
n^{7}-n &=&n\left( n^{6}-1\right) \\
&=&n\left( n^{3}+1\right) \left( n^{3}-1\right) \\
&=&n\left( n+1\right) \left( n^{2}-n+1\right) \left( n-1\right) \left( n^{2}+n+1\right)
\end{eqnarray*}となります。\(n\)を\(7\)で割ったときの余りで場合を分けます。\(m\)を\(1 \)以上の整数とします。\(n=7m\)の場合に\(n^{7}-n\)は\(7\)の倍数の因数\(n=7m\)を持つため、\(n^{7}-n\)は\(7\)で割り切れます。\(n=7m-1\)の場合に\(n^{7}-n\)は\(7\)の倍数の因数\(n+1=\left( 7m-1\right) +1=7m\)を持つため、\(n^{7}-n\)は\(7\)で割り切れます。\(n=7m-2\)の場合に\(n^{7}-n\)は\(7\)の倍数の因数\begin{eqnarray*}
n^{2}-n+1 &=&\left( 7m-2\right) ^{2}-\left( 7m-2\right) +1 \\
&=&49m^{2}-28m+4-7m+2+1 \\
&=&49m^{2}-35m+7 \\
&=&7\left( 7m^{2}-5m+1\right)
\end{eqnarray*}を持つため、\(n^{7}-n\)は\(7\)で割り切れます。\(n=7m-3\)の場合に\(n^{7}-n\)は\(7\)の倍数の因数\begin{eqnarray*}
n^{2}+n+1 &=&\left( 7m-3\right) ^{2}+\left( 7m-3\right) +1 \\
&=&49m^{2}-42m+9+7m-3+1 \\
&=&49m^{2}-35m+7 \\
&=&7\left( 7m^{2}-5m+1\right)
\end{eqnarray*}を持つため、\(n^{7}-n\)は\(7\)で割り切れます。\(n=7m-4\)の場合に\(n^{7}-n\)は\(7\)の倍数の因数\begin{eqnarray*}
n^{2}-n+1 &=&\left( 7m-4\right) ^{2}-\left( 7m-4\right) +1 \\
&=&49m^{2}-56m+16-7m+4+1 \\
&=&49m^{2}-63m+21 \\
&=&7\left( 7m^{2}-9m+3\right)
\end{eqnarray*}を持つため、\(n^{7}-n\)は\(7\)で割り切れます。\(n=7m-5\)の場合に\(n^{7}-n\)は\(7\)の倍数の因数\begin{eqnarray*}
n^{2}+n+1 &=&\left( 7m-5\right) ^{2}+\left( 7m-5\right) +1 \\
&=&49m^{2}-70m+25+7m-5+1 \\
&=&49m^{2}-63m+21 \\
&=&7\left( 7m^{2}-9m+3\right)
\end{eqnarray*}を持つため、\(n^{7}-n\)は\(7\)で割り切れます。\(n=7m-6\)の場合に\(n^{7}-n\)は\(7\)の倍数の因数\(n-1=\left( 7m-6\right) -1=7m-7\)を持つため、\(n^{7}-n\)は\(7\)で割り切れます。したがって、総当たり法により証明が完了しました。

次回から述語論理について学びます。
次へ進む 演習問題(プレミアム会員限定)