論理演算の言い換え

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

含意の言い換え

論理式\(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
< 前のページ
次のページ >

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

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

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