命題論理の例題

この記事では、いくつかの論理式について、考えられる真理値の割り当てを真理値表を使って調べます。

例題1

論理式 ϕ = (p ∧ q) ∨ ¬q が真になるのはどんなときかを調べてみましょう。まず、命題変数 p と q を表に書きます。

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

次に、論理式の前半部分 (p ∧ q)、否定 ¬q、そして論理式全体を表に書き加えます。

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

ここで、3列目の値を求めます。これは単純な論理積です。同時に否定の列も求めます。否定の列には、2列目と反対の値を入れるだけです。

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

最後に、いちばん右の列の値を求めます。これが論理式全体です。この表でいえば、「3列目と4列目の論理和」を求めることになります。結果は次のとおりです。

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

例題2

問題は同じで、今度の論理式は ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q) です。この論理式には、命題変数 p と q、およびその否定が出てきます。そこでまず、二つの命題変数とその否定の表を作ります。

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

次に、論理式 p ∧ ¬q と ¬p ⇒ q を加えます。表にはそれぞれの命題の割り当ても、その否定の割り当てもあるので、これらはすぐに求められます。表は次のようになります。

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

最後に残るのは論理式全体の値で、これは最後の二つの列の同値です。

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

例題3

3番目の例題は少し難しくなります。命題変数を三つにするので、表の計算が複雑になります。論理式は ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)) です。

命題変数が三つあるので、真理値の割り当ては全部で8通りです。

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

あとは前の例題と同じように進め、それぞれの列の値を8行すべてについて求めます。表全体は次のようになります。

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

例題4

この例題は、ふつうの論理式ではなく文章題として出します。マイク、ジャック、ポールの3人の留学生が、にぎやかなパーティーに行こうとしています。ただ、3人はあまり仲がよくないので、パーティーに行くための条件をそれぞれつけています。条件は次のとおりです。

1. マイクが行くならば、ジャックも行く。
2. ポールがパーティーに来る、または「マイクが来るならば、ジャックは来ない」。
3. ポールが来るのは、マイクが来ないかジャックが来ないとき、かつそのときに限る。

3人全員がパーティーに行くことはできるでしょうか。できないなら、だれがどの条件も破らずにパーティーに行けるでしょうか。

まず、文章で書かれた命題を命題変数と論理式に書き直す必要があります。命題変数を M、J、P（マイク、ジャック、ポール）とし、それぞれ「マイクはパーティーに行く」のような命題を表すことにします。一つ目の条件は M ⇒ J と書き直せます。「M ならば J」、つまり「マイクがパーティーに行くならば、ジャックもパーティーに行く」です。

二つ目の条件は次のように書き直します。この条件は「ポールがパーティーに来る、または…」で始まるので、論理和が必要なことは明らかです。そこで、ひとまず P ∨ … と書いておきます。文の残りは「マイクが来るならば、ジャックは来ない」です。これは含意で、右側にはさらに否定を使う必要があります。「ジャックは来ない」は ¬J です。含意全体は M ⇒ ¬J になります。これを先ほどの論理和につなげると、P ∨ (M ⇒ ¬J) になります。

三つ目の条件は次のように書き直します。まず「ポールが来るのは…とき、かつそのときに限る」は同値を表すので、P ⇔ … と書きます。続く「マイクが来ないかジャックが来ない」は ¬M ∨ ¬J と書き直せます。合わせると (P ⇔ (¬M ∨ ¬J)) になります。

これらの論理式をすべて表に入れて、値を求めます。

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

3人全員がパーティーに行けるかどうかは、1行目を見ればわかります。1行目は3人全員が行く場合で、最初の三つの列がすべて1になっていることからわかります。すべての条件が満たされているでしょうか。一つ目の条件は満たされています（4列目）。二つ目も満たされています（5列目）。しかし、最後の条件は満たされていません（最後の列）。ここは0です。つまり、3人全員が行くと、三つ目の条件が満たされません。

そこで、条件を表す位置（最後の三つの列）がすべて1になっている行を探します。1は条件が満たされていることを表します。そうなる場合は二つあることがわかります。ジャックとポールが行き、マイクは行かない場合と、ポールだけが行く場合です。

三つの条件すべての論理積となる論理式 ϕ を表に加えて求めることもできます。この論理式は ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))) です。これは、すべての論理式（すべての条件）が満たされるという、求めたい状態をそのまま表しています。表は次のようになります。

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

真理値表を使う方法の例題

与えられた論理式から表全体を自動で作るプログラムを書いたので、せっかくですからしっかり使ってみます。解いた論理式をさらにいくつか挙げます。

論理式 ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))) の真理値表は次のとおりです。

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

論理式 (a ∨ ¬a) ⇔ (b ∧ ¬b) の真理値表は次のとおりです。

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

論理式 ¬(a ∨ b) ⇔ (¬b ∧ ¬a) の真理値表は次のとおりです。

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

論理式 ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)) の真理値表は次のとおりです。

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

論理式 ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r) の真理値表は次のとおりです。

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$