論理演算の言い換え

含意、同等、排他的論理和はいずれも否定、論理積、論理和を用いて間接的に定義可能です。
含意 同等 排他的論理和
< 前のページ
次のページ >

含意の言い換え

論理式\(A,B\)をそれぞれ任意に選んだとき、以下の真理値表が得られます。

$$\begin{array}{ccccc}
\hline
A & B & \lnot A & \lnot A\vee B & A\rightarrow B \\ \hline
1 & 1 & 0 & 1 & 1 \\ \hline
1 & 0 & 0 & 0 & 0 \\ \hline
0 & 1 & 1 & 1 & 1 \\ \hline
0 & 0 & 1 & 1 & 1 \\ \hline
\end{array}$$

表:含意の言い換え

つまり、任意の解釈のもとで\(A\rightarrow B\)の値は\(\lnot A\vee B\)の値と一致するため、\begin{equation*}
A\rightarrow B\Leftrightarrow \lnot A\vee B
\end{equation*}という関係が成り立ちます。

命題(含意の言い換え)
任意の論理式\(A,B\)に対して以下が成り立つ。\begin{equation*}
A\rightarrow B\Leftrightarrow \lnot A\vee B
\end{equation*}
証明を見る(プレミアム会員限定)

論理式\(A\)が部分論理式\(B\rightarrow C\)を持つとき、\(A\)中の\(B\rightarrow C\)を\(\lnot B\vee C\)に置き換えて得られる論理式を\(A^{\prime }\)で表します。上の命題より\(B\rightarrow C\)と\(\lnot B\vee C\)の真理値は任意の解釈のもとで一致するため、\(A\)と\(A^{\prime }\)の真理値もまた任意の解釈のもとで一致します。したがって、論理式の中に\(\rightarrow \)が含まれる場合には、それを\(\lnot \)と\(\vee \)に置き換えることができます。

例(含意の言い換え)
命題変数\(P,Q,R\)に関する論理式\(\left( P\wedge \lnot Q\right) \rightarrow \lnot R\)を同値変形すると、\begin{eqnarray*}
\left( P\wedge \lnot Q\right) \rightarrow \lnot R &\Leftrightarrow &\lnot
\left( P\wedge \lnot Q\right) \vee \lnot R\quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\vee \lnot \lnot Q\right) \vee \lnot R\quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot P\vee Q\vee \lnot R\quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(\lnot P\vee Q\vee \lnot R\)には\(\rightarrow \)が含まれません。
例(含意の言い換え)
命題変数\(P,Q,R\)に関する論理式\(\lnot P\rightarrow \lnot \left( Q\rightarrow \lnot R\right) \)を同値変形すると、\begin{eqnarray*}
\lnot P\rightarrow \lnot \left( Q\rightarrow \lnot R\right)
&\Leftrightarrow &\lnot \lnot P\vee \lnot \left( \lnot Q\vee \lnot R\right)
\quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\lnot \lnot P\vee \left( \lnot \lnot Q\wedge \lnot \lnot
R\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &P\vee \left( Q\wedge R\right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(P\vee \left( Q\wedge R\right) \)には\(\rightarrow \)が含まれません。

 

同等の言い換え

論理式\(A,B\)をそれぞれ任意に選んだとき、以下の真理値表が得られます。

$$\begin{array}{cccccc}
\hline
A & B & A\rightarrow B & B\rightarrow A & \left( A\rightarrow B\right) \wedge \left( B\rightarrow A\right) & A\leftrightarrow B \\ \hline
1 & 1 & 1 & 1 & 1 & 1 \\ \hline
1 & 0 & 0 & 1 & 0 & 0 \\ \hline
0 & 1 & 1 & 0 & 0 & 0 \\ \hline
0 & 0 & 1 & 1 & 1 & 1 \\ \hline
\end{array}$$

表:同等の言い換え

つまり、任意の解釈のもとで\(A\leftrightarrow B\)の値は\(\left( A\rightarrow B\right) \wedge \left( B\rightarrow A\right) \)の値と一致するため、\begin{equation*}
A\leftrightarrow B\Leftrightarrow \left( A\rightarrow B\right) \wedge \left(
B\rightarrow A\right)
\end{equation*}という関係が成り立ちます。

命題(同等の言い換え)

任意の論理式\(A,B\)に対して以下が成り立つ。\begin{equation*}
A\leftrightarrow B\Leftrightarrow \left( A\rightarrow B\right) \wedge \left(
B\rightarrow A\right)
\end{equation*}

証明を見る(プレミアム会員限定)

論理式\(A\)が部分論理式\(B\leftrightarrow C\)を持つとき、\begin{eqnarray*}
B\leftrightarrow C &\Leftrightarrow &\left( B\rightarrow C\right) \wedge
\left( C\rightarrow B\right) \\
&\Leftrightarrow &\left( \lnot B\vee C\right) \wedge \left( \lnot C\vee
B\right)
\end{eqnarray*}という関係が成り立つため、\(A\)中の\(B\leftrightarrow C\)を\(\left( \lnot B\vee C\right) \wedge \left( \lnot C\vee B\right) \)に置き換えて得られる論理式を\(A^{\prime }\)で表すのであれば、\(A\)と\(A^{\prime }\)の真理値は任意の解釈のもとで一致します。したがって、論理式の中に\(\leftrightarrow \)が含まれる場合には、それを\(\lnot \)と\(\vee \)に置き換えることができます。

例(同等の言い換え)
命題変数\(P,Q\)に関する論理式\(P\leftrightarrow \lnot Q\)を同値変形すると、\begin{eqnarray*}
P\leftrightarrow \lnot Q &\Leftrightarrow &\left( P\rightarrow \lnot
Q\right) \wedge \left( \lnot Q\rightarrow P\right) \quad \because
\leftrightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\vee \lnot Q\right) \wedge \left( \lnot
\lnot Q\vee P\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\vee \lnot Q\right) \wedge \left( Q\vee
P\right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(\left( \lnot P\vee \lnot Q\right) \wedge \left( Q\vee P\right) \)には\(\leftrightarrow \)や\(\rightarrow \)が含まれません。
例(同等の言い換え)
命題変数\(P,Q,R\)に関する論理式\(\left( P\wedge \lnot Q\right) \leftrightarrow \lnot R\)を同値変形すると、\begin{eqnarray*}
\left( P\wedge \lnot Q\right) \leftrightarrow \lnot R &\Leftrightarrow
&\left( \left( P\wedge \lnot Q\right) \rightarrow \lnot R\right) \wedge
\left( \lnot R\rightarrow \left( P\wedge \lnot Q\right) \right) \quad
\because \leftrightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot \left( P\wedge \lnot Q\right) \vee \lnot
R\right) \wedge \left( \lnot \lnot R\vee \left( P\wedge \lnot Q\right)
\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \left( \lnot P\vee \lnot \lnot Q\right) \vee \lnot
R\right) \wedge \left( \lnot \lnot R\vee \left( P\wedge \lnot Q\right)
\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \lnot P\vee Q\vee \lnot R\right) \wedge \left(
R\vee \left( P\wedge \lnot Q\right) \right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(\left( \lnot P\vee Q\vee \lnot R\right) \wedge \left( R\vee \left( P\wedge \lnot Q\right) \right) \)には\(\leftrightarrow \)や\(\rightarrow \)が含まれません。

 

排他的論理和の言い換え

論理式\(A,B\)をそれぞれ任意に選んだとき、以下の真理値表が得られます。

$$\begin{array}{cccccccc}
\hline
A & B & \lnot A & \lnot B & A\wedge \lnot B & \lnot A\wedge B & \left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) & A\veebar B \\ \hline
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ \hline
0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$

表:排他的論理和の言い換え

つまり、任意の解釈のもとで\(A\veebar B\)の値は\(\left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) \)の値と一致するため、\begin{equation*}
A\veebar B\Leftrightarrow \left( A\wedge \lnot B\right) \vee \left( \lnot
A\wedge B\right)
\end{equation*}という関係が成り立ちます。

命題(排他的論理和の言い換え)
任意の論理式\(A,B\)に対して以下が成り立つ。\begin{equation*}
A\veebar B\Leftrightarrow \left( A\wedge \lnot B\right) \vee \left( \lnot
A\wedge B\right)
\end{equation*}
証明を見る(プレミアム会員限定)

論理式\(A\)が部分論理式\(B\veebar C\)を持つとき、\(A\)中の\(B\veebar C\)を\(\left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) \)に置き換えて得られる論理式を\(A^{\prime }\)で表します。上の命題より\(B\veebar C\)と\(\left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) \)の真理値は任意の解釈のもとで一致するため、\(A\)と\(A^{\prime }\)の真理値もまた任意の解釈のもとで一致します。したがって、論理式の中に\(\veebar \)が含まれる場合には、それを\(\lnot ,\wedge ,\vee \)に置き換えることができます。

例(排他的論理和の言い換え)
命題変数\(P,Q\)に関する論理式\(P\veebar \lnot Q\)を同値変形すると、\begin{eqnarray*}
P\veebar \lnot Q &\Leftrightarrow &\left( P\wedge \lnot \lnot Q\right) \vee
\left( \lnot P\wedge \lnot Q\right) \quad \because \veebar \text{の言い換え} \\
&\Leftrightarrow &\left( P\wedge Q\right) \vee \left( \lnot P\wedge \lnot
Q\right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(\left( P\wedge Q\right) \vee \left( \lnot P\wedge \lnot Q\right) \)には\(\veebar \)が含まれません。
例(排他的論理和の言い換え)
命題変数\(P,Q,R\)に関する論理式\(\left( P\wedge \lnot Q\right) \veebar \lnot R\)を同値変形すると、\begin{eqnarray*}
\left( P\wedge \lnot Q\right) \veebar \lnot R &\Leftrightarrow &\left(
\left( P\wedge \lnot Q\right) \wedge \lnot \lnot R\right) \vee \left( \lnot
\left( P\wedge \lnot Q\right) \wedge \lnot R\right) \quad \because \veebar
\text{の言い換え} \\
&\Leftrightarrow &\left( \left( P\wedge \lnot Q\right) \wedge \lnot \lnot
R\right) \vee \left( \left( \lnot P\vee \lnot \lnot Q\right) \wedge \lnot
R\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( P\wedge \lnot Q\wedge R\right) \vee \left( \left(
\lnot P\vee Q\right) \wedge \lnot R\right) \quad \because \text{ド・モルガンの法則}
\end{eqnarray*}となります。同値変形後の論理式\(\left( P\wedge \lnot Q\wedge R\right) \vee \left( \left( \lnot P\vee Q\right) \wedge \lnot R\right) \)には\(\veebar \)が含まれません。

次回は対偶律について学びます。

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

ワイズをさらに活用するための会員サービス

ユーザー名とメールアドレスを入力して一般会員に無料登録すれば、質問やコメントを投稿できるようになります。さらに、有料(500円/月)のプレミアム会員へアップグレードすることにより、プレミアムコンテンツ(命題の証明や演習問題、解答など)にアクセスできます。
会員サービス

ディスカッションに参加しますか?

質問やコメントを投稿するためにはログインが必要です
ログイン

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