場合分け・総当たり法

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

場合分け

論理式\(A_{1},\cdots ,A_{m},B_{1},\cdots ,B_{n},C\)に関する以下の推論\begin{equation*}
A_{1},\cdots ,A_{m},\bigvee_{j=1}^{n}B_{j}\ \therefore \ C
\end{equation*}が与えられたとき、この推論の妥当性を示す方法の1つは、以下の論理式\begin{equation*}
\left( \bigwedge_{i=1}^{m}A_{i}\right) \wedge \left(
\bigvee_{j=1}^{m}B_{j}\right) \rightarrow C
\end{equation*}が恒真式であることを示すというものです。ただ、これは以下の論理式\begin{equation*}
\bigwedge_{j=1}^{m}\left( \left( \left( \bigwedge_{i=1}^{m}A_{i}\right)
\wedge B_{j}\right) \rightarrow C\right)
\end{equation*}と論理的に同値です(演習問題にします)。したがって以下の命題を得ます。

命題(場合分け)
論理式\(A_{1},\cdots ,A_{m},B_{1},\cdots ,B_{n},C\)が与えられたとき、任意の\(j\in \left\{ 1,\cdots ,m\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
\end{equation*}が成り立つための必要十分条件である。
証明を見る(プレミアム会員限定)

つまり、前提が\(A_{1},\cdots ,A_{m},\bigvee_{j=1}^{n}B_{j}\)で結論が\(C\)であるような推論が与えられたとき、それぞれの\(i\)について、前提\(A_{1},\cdots ,A_{m}\)と仮定\(B_{i}\)から結論\(C\)を導けばよいと言うことです。このような証明方法を場合分け(case analysis)と呼びます。

例(場合分け)
命題変数\(P,Q,R\)に関する以下の推論規則\begin{equation*}
P\vee Q\ \models \ R
\end{equation*}が成り立つことを示すためには、場合分けより、以下の推論規則\begin{eqnarray*}
P\ &\models &\ R \\
Q\ &\models &\ R
\end{eqnarray*}がともに成り立つことを示せばよいということになります。
例(場合分け)
命題変数\(P,Q,R,S\)に関する以下の推論\begin{equation*}
P\rightarrow \left( Q\wedge \lnot S\right) ,\ R\rightarrow P,\ R\vee \lnot
S\ \therefore \ \lnot S
\end{equation*}の妥当性を示します。これは以下の証明により証明可能です。
$$\begin{array}{llll}
\left( 1\right) & P\rightarrow \left( Q\wedge \lnot S\right) & \quad & 前提 \\
\left( 2\right) & R\rightarrow P & \quad & 前提 \\
\left( 3\right) & R\vee \lnot S & \quad & 前提 \\
\left( 4\right) & R & \left[ 1\right] & 仮定 \\
\left( 5\right) & P & \left[ 1\right] & \left( 2\right) ,\left( 4\right) と\rightarrow 除去 \\
\left( 6\right) & Q\wedge \lnot S & \left[ 1\right] & \left( 1\right) ,\left( 5\right) と\rightarrow 除去 \\
\left( 7\right) & \lnot S & \left[ 1\right] & \left( 6\right) と\wedge 除去 \\
\left( 8\right) & R\rightarrow \lnot S & \quad & \left( 3\right) と\vee 除去 \\
\left( 9\right) & R & \quad & \left( 3\right) と\vee 除去 \\
\left( 10\right) & \lnot S & \quad & \left( 8\right) ,\left( 9\right)と\rightarrow 除去 \\
\left( 11\right) & \lnot S & \left[ 11\right] & 仮定 \\
\left( 12\right) & \lnot \lnot \lnot S & \left[ 11\right] & \left( 11\right) と\lnot \lnot 導入 \\
\left( 13\right) & \lnot S & \left[ 11\right] & \left( 12\right) と\lnot \lnot 除去 \\
\left( 14\right) & \lnot S\rightarrow \lnot S & \quad & \left( 11\right) ,\left( 12\right) と\rightarrow 導入 \\
\left( 15\right) & \lnot S & \quad & \left( 3\right) と\vee 除去 \\
\left( 16\right) & \lnot S & \quad & \left( 14\right) ,\left( 15\right) と\rightarrow 除去 \\
\left( 17\right) & \lnot S & \quad & \left( 10\right) ,\left( 16\right) と場合分け
\end{array}$$

ただし、前提の\(R\vee \lnot S\)を\(R\)と\(\lnot S\)の2つの場合に分けて考えており、\(\left( 4\right) \)から\(\left( 10\right) \)は\(R\)が成り立つ場合の議論であり、\(\left( 11\right) \)から\(\left( 16\right) \)は\(\lnot S\)が成り立つ場合の議論です。

 

総当たり法

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

例(総当たり法)
命題変数\(P,Q\)に関する以下の推論\begin{equation*}
P\ \therefore \ Q
\end{equation*}が与えられたとき、\(P=P_{1}\vee P_{2}\)かつ\(P_{1}\wedge P_{2}=\bot \)を満たす命題変数\(P_{1},P_{2}\)が存在するのであれば、総当たり法より、以下の推論\begin{eqnarray*}
P_{1}\ &\therefore &\ Q \\
P_{2}\ &\therefore &\ Q
\end{eqnarray*}がともに妥当であることを示しても問題ありません。
例(総当たり法)
正の整数\(n\)を任意に選んだとき、\(n^{7}-n\)が\(7\)で割り切れることを証明します。命題変数\(P,Q\)をそれぞれ、\begin{eqnarray*}
P &:&n\text{は整数である} \\
Q &:&n^{7}-n\text{は}7\text{で割り切れる}
\end{eqnarray*}とおくと、以下の推論\begin{equation*}
P\ \therefore \ Q
\end{equation*}の妥当性を示すことが目標になります。整数\(n\)は\(7\)で割った余りにより分類可能です。つまり、\(i\)は\(0\)以上\(6\)以下の整数を値としてとり得るとき、命題変数\(P_{i}\)を、\begin{equation*}
P_{i}:n\text{は}7\text{で割ったときの余りが}i\text{の整数である}
\end{equation*}とおくと、\begin{equation*}
P=P_{0}\vee P_{1}\vee P_{2}\vee P_{3}\vee P_{4}\vee P_{5}\vee P_{6}
\end{equation*}であるとともに、\(P_{0},\cdots ,P_{6}\)の中の2つが同時に真になることはありません。したがって、総当たり法より、もとの推論の妥当性を示す代わりに、それぞれの\(i\)について、以下の推論\begin{equation*}
P_{i}\ \therefore \ Q
\end{equation*}の妥当性を示しても問題ありません。そこでまずは、\begin{equation*}
P_{0}\ \therefore \ Q
\end{equation*}の妥当性を示します。\(P_{0}\)が真であることは\(n\)が\(7\)の倍数であることを意味するため、\(n\)は整数\(m\)を用いて\(n=7m\)と表すことができます。また、\(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*}となりますが、これは\(7\)の倍数である因数\(n=7m\)を持ちます。したがって\(n^{7}-n\)は\(7\)の倍数であり、\(Q\)が真であることが示されました。\(i\geq 1\)についても、\begin{equation*}
P_{i}\ \therefore \ Q
\end{equation*}が妥当であることを同様にして示すことができます(演習問題にします)。したがって、総当たり法より、もとの推論が妥当であることが示されました。

次回から述語論理について学びます。

次へ進む 質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
< 前のページ
次のページ >

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

有料のプレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

命題論理
アカウント
ログイン