場合分け
与えられた推論が複雑である場合には、それをいくつかの単純な推論に分割した上で、得られた個々の推論の妥当性を示す証明方法が有用です。まずは根拠となる命題を提示します。
\end{equation*}が成り立つことと、任意の\(j\in \left\{ 1,\cdots ,n\right\} \)について、\begin{equation*}A_{1},\cdots ,A_{m},B_{j}\ \models \ C
\end{equation*}が成り立つことは必要十分である。
上の命題はどのような意味において有用なのでしょうか。以下の推論規則\begin{equation}
A_{1},\cdots ,A_{m},\bigvee_{j=1}^{n}B_{j}\ \models \ C \quad \cdots (1)
\end{equation}が成り立つことを証明しようとしている状況を想定してください。先の命題より、この推論規則は以下の\(n\)個の推論規則\begin{eqnarray*}A_{1},\cdots ,A_{m},B_{1}\ &\models &\ C \\
A_{1},\cdots ,A_{m},B_{2}\ &\models &\ C \\
&&\vdots \\
A_{1},\cdots ,A_{m},B_{n}\ &\models &\ C
\end{eqnarray*}がすべて成り立つことと必要十分であるため、\(\left( 1\right) \)の代わりに以上の\(n\)個の推論規則が成り立つことを示しても構わないということになります。このような証明方法を場合分け（caseanalysis）や総当たり法（proof by exhaustion）などと呼びます。
D\ \therefore \ \lnot D
\end{equation*}の妥当性を示します。場合分けより、以下の2つの推論\begin{eqnarray*}
&&\left( a\right) \ A\rightarrow \left( B\wedge \lnot D\right) ,\
C\rightarrow A,\ C\ \therefore \ \lnot D \\
&&\left( b\right) \ A\rightarrow \left( B\wedge \lnot D\right) ,\
C\rightarrow A,\ \lnot D\ \therefore \ \lnot D
\end{eqnarray*}が妥当であることを示せば目標は達成されます。\(\left( b\right) \)に関しては、結論\(\lnot D\)が前提に含まれているため明らかに妥当です。一方、\(\left( a\right) \)の妥当性の証明は以下の通りです。$$\begin{array}{llll}\left( 1\right) & A\rightarrow \left( B\wedge \lnot D\right) & \quad & 前提 \\
\left( 2\right) & C\rightarrow A & \quad & 前提 \\
\left( 3\right) & C & \quad & 前提 \\
\left( 4\right) & A & \quad & \left( 2\right) ,\left( 3\right) と\rightarrow 除去 \\
\left( 5\right) & B\wedge \lnot D & \quad & \left( 1\right) ,\left( 4\right) と\rightarrow 除去 \\
\left( 6\right) & \lnot D & \quad & \left( 5\right) と \wedge 除去
\end{array}$$
\end{equation*}となりますが、場合分けより、以下の2つの推論\begin{eqnarray*}
&&\left( a\right) \ x>1\ \therefore \ \left\vert x\right\vert >1 \\
&&\left( b\right) \ x<-1\ \therefore \ \left\vert x\right\vert >1
\end{eqnarray*}がともに妥当であることを示せば目標を達成したことになります。まずは\(\left( a\right) \)を示します。\(x>1\)の場合、\begin{eqnarray*}\left\vert x\right\vert &=&x\quad \because x>1\text{および絶対値の定義} \\
&>&1\quad \because x>1
\end{eqnarray*}となるため証明が完了しました。続いて\(\left( b\right) \)です。\(x<-1\)の場合、\begin{eqnarray*}\left\vert x\right\vert &=&-x\quad \because x<-1\text{および絶対値の定義} \\
&>&1\quad \because x<-1
\end{eqnarray*}となるため証明が完了しました。
場合分けの応用
論理式\(A_{1},\cdots ,A_{m},B,C\)に関する以下の推論規則\begin{equation}A_{1},\cdots ,A_{m},B\ \models \ C \quad \cdots (1)
\end{equation}が成り立つことを証明しようとしている状況を想定してください。前提の1つである論理式\(B\)に対して、\begin{equation}B\Leftrightarrow \bigvee_{j=1}^{n}B_{j} \quad \cdots (2)
\end{equation}を満たす論理式\(B_{1},\cdots ,B_{n}\)が存在する場合には、\(\left( 1\right) \)と以下の推論規則\begin{equation}A_{1},\cdots ,A_{m},\bigvee_{j=1}^{n}B_{j}\ \models \ C \quad \cdots (3)
\end{equation}は必要十分であるため、\(\left( 1\right) \)の代わりに\(\left( 3\right) \)を示しても問題ありません。さらに、場合分けより、\(\left(3\right) \)を示す代わりに以下の\(n\)個の推論規則\begin{eqnarray*}A_{1},\cdots ,A_{m},B_{1}\ &\models &\ C \\
A_{1},\cdots ,A_{m},B_{2}\ &\models &\ C \\
&&\vdots \\
A_{1},\cdots ,A_{m},B_{n}\ &\models &\ C
\end{eqnarray*}を示しても問題ありません。つまり、もとの推論規則の前提\(B\)を\(\left( 2\right) \)を満たす論理式\(B_{1},\cdots ,B_{n}\)へ分割することにより場合分けに持ち込むということです。
\end{equation*}となります。ただし、すべての整数は\(3\)で割ったときの余りで場合分けが可能であるため、\begin{equation*}n\text{は整数}\Leftrightarrow n\text{を}3\text{で割った余りが}0\vee n\text{を}3\text{で割った余りが}1\vee n\text{を}3\text{で割った余りが}2
\end{equation*}という関係が成立します。したがって、場合分けより、以下の3つの推論\begin{eqnarray*}
&&\left( a\right) \ \text{整数}n\text{を}3\text{で割った余りが}0\ \therefore \ 2n^{2}+n+1\text{は}3\text{で割り切れない} \\
&&\left( b\right) \ \text{整数}n\text{を}3\text{で割った余りが}1\ \therefore \ 2n^{2}+n+1\text{は}3\text{で割り切れない} \\
&&\left( c\right) \ \text{整数}n\text{を}3\text{で割った余りが}2\ \therefore \ 2n^{2}+n+1\text{は}3\text{で割り切れない}
\end{eqnarray*}が妥当であることを示せば目標は達成されます。\(\left( a\right) \)を示します。整数\(n\)を\(3\)で割った余りが\(0\)であるものとします。つまり、何らかの整数\(m\)を用いて\(n=3m+0\)と表すことができるということです。このとき、\begin{eqnarray*}2n^{2}+n+1 &=&2\left( 3m+0\right) ^{2}+\left( 3m+0\right) +1\quad \because
n=3m+0 \\
&=&18m^{2}+3m+1 \\
&=&3\left( 6m^{2}+m\right) +1
\end{eqnarray*}となるため\(2n^{2}+n+1\)は\(3\)では割り切れません。したがって\(\left( a\right) \)が示されました。\(\left( b\right) ,\left(c\right) \)の証明も同様です。
演習問題
B\right)
\end{equation*}が成り立つことを証明してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】