含意の言い換え
論理式\(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 \)に置き換えることができます。
\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 \)が含まれません。
&\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 \)に置き換えることができます。
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 \)が含まれません。
&\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\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 \)に置き換えることができます。
\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 \)が含まれません。
\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 \)が含まれません。
論理式の定義：再論
論理演算子として\(\lnot,\wedge ,\vee ,\rightarrow ,\leftrightarrow ,\veebar \)を定義しましたが、先に示したように\(\rightarrow,\leftrightarrow ,\veebar \)はいずれも\(\lnot,\wedge ,\vee \)によって言い換え可能であるため、結局、論理演算子として\(\lnot ,\wedge ,\vee \)だけ与えられれば任意の論理式を表現することができます。具体的には、論理式\(A,B\)がそれぞれ任意に与えられたとき、\begin{eqnarray*}&&\left( a\right) \ A\rightarrow B\Leftrightarrow \lnot A\vee B \\
&&\left( b\right) \ A\leftrightarrow B\Leftrightarrow \left( A\rightarrow
B\right) \wedge \left( B\rightarrow A\right) \\
&&\left( c\right) \ A\veebar B\Leftrightarrow \left( A\wedge \lnot B\right)
\vee \left( \lnot A\wedge B\right)
\end{eqnarray*}などの関係が成り立つため、これらの関係を適用することにより、論理式中の\(\rightarrow,\leftrightarrow ,\veebar \)を\(\lnot ,\wedge ,\vee \)に置き換えることができます。以上の事実を踏まえると、論理式を以下のように定義しなおしても一般性は失われません。
- 命題変数\(P,Q,\cdots \)は論理式である。
- 命題定数\(T,F\)は論理式である。
- \(A\)が論理式ならば、\(\left( \lnot A\right) \)は論理式である。
- \(A,B\)が論理式ならば、\(\left( A\wedge B\right) \)は論理式である。
- \(A,B\)が論理式ならば、\(\left( A\vee B\right) \)は論理式である。
- 以上から論理式と判定されるものだけが論理式である。
演習問題
\Leftrightarrow A
\end{equation*}が成り立つことを証明してください。
\Leftrightarrow A
\end{equation*}が成り立つことを証明してください。
A\wedge B\right) \vee C
\end{equation*}が成り立つことを証明してください。
B\Leftrightarrow A\rightarrow B
\end{equation*}が成り立つことを証明してください。
\Leftrightarrow A\rightarrow B
\end{equation*}が成り立つことを証明してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】