含意の言い換え
論理式\(A,B\)を任意に選んだとき、以下の同値関係\begin{equation*}A\rightarrow B\Leftrightarrow \lnot A\vee B
\end{equation*}が成り立ちます。つまり、含意\(\rightarrow \)は否定\(\lnot \)と論理和\(\vee \)を用いて表現できます。
任意の論理式\(A,B\)に対して、\begin{equation*}A\rightarrow B\Leftrightarrow \lnot A\vee B
\end{equation*}が成り立つ。
\end{equation*}を得ます。
&&R\vee S
\end{eqnarray*}はともに論理式であるため、先の命題より、\begin{equation*}
\left( P\wedge Q\right) \rightarrow \left( R\vee S\right) \Leftrightarrow
\lnot \left( P\wedge Q\right) \vee \left( R\vee S\right)
\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 \)に置き換えることができます。
\end{equation*}を同値変形すると、\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*}となります。同値変形後の論理式\begin{equation*}
\lnot P\vee Q\vee \lnot R
\end{equation*}には\(\rightarrow \)が含まれません。
同等の言い換え
論理式\(A,B\)を任意に選んだとき、以下の同値関係\begin{equation*}A\leftrightarrow B\Leftrightarrow \left( A\rightarrow B\right) \wedge \left(
B\rightarrow A\right)
\end{equation*}が成り立ちます。つまり、同等\(\leftrightarrow \)は含意\(\rightarrow \)と論理積\(\wedge \)を用いて表現できます。
任意の論理式\(A,B\)に対して、\begin{equation*}A\leftrightarrow B\Leftrightarrow \left( A\rightarrow B\right) \wedge \left(
B\rightarrow A\right)
\end{equation*}が成り立つ。
Q\rightarrow P\right)
\end{equation*}が成り立ちます。
&&R\vee S
\end{eqnarray*}はともに論理式であるため、先の命題より、\begin{equation*}
\left( P\wedge Q\right) \leftrightarrow \left( R\vee S\right)
\Leftrightarrow \left( \left( P\wedge Q\right) \rightarrow \left( R\vee
S\right) \right) \wedge \left( \left( R\vee S\right) \rightarrow \left(
P\wedge Q\right) \right)
\end{equation*}が成り立ちます。
これまで示した命題を踏まえると以下を得ます。
任意の論理式\(A,B\)に対して、\begin{equation*}A\leftrightarrow B\Leftrightarrow \left( \lnot A\vee B\right) \wedge \left(
\lnot B\vee A\right)
\end{equation*}が成り立つ。
以上の命題より、同等\(\leftrightarrow \)は否定\(\lnot \)と論理積\(\wedge \)と論理和\(\vee \)を用いて表現できることが明らかになりました。
\lnot Q\vee P\right)
\end{equation*}が成り立ちます。
&&R\vee S
\end{eqnarray*}はともに論理式であるため、先の命題より、\begin{equation*}
\left( P\wedge Q\right) \leftrightarrow \left( R\vee S\right)
\Leftrightarrow \left( \lnot \left( P\wedge Q\right) \vee \left( R\vee
S\right) \right) \wedge \left( \lnot \left( R\vee S\right) \vee \left(
P\wedge Q\right) \right)
\end{equation*}が成り立ちます。
論理式\(A\)が部分論理式\(B\leftrightarrow C\)を持つ場合、\(A\)中の\(B\leftrightarrow C\)を\(\left( \lnot B\vee C\right)\wedge \left( \lnot C\vee B\right) \)に置き換えることにより得られる論理式を\(A^{\prime }\)で表します。先の命題より\(B\leftrightarrow C\)と\(\left( \lnot B\vee C\right) \wedge \left( \lnot C\vee B\right) \)の真理値は任意の解釈のもとで一致するため、\(A\)と\(A^{\prime }\)の真理値もまた任意の解釈のもとで一致します。したがって、論理式の中に\(\leftrightarrow \)が含まれる場合には、それを\(\lnot \)と\(\wedge \)と\(\vee \)に置き換えることができます。
\end{equation*}を同値変形すると、\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*}となります。同値変形後の論理式\begin{equation*}
\left( \lnot P\vee \lnot Q\right) \wedge \left( Q\vee P\right)
\end{equation*}には\(\leftrightarrow \)や\(\rightarrow \)が含まれません。
排他的論理和の言い換え
論理式\(A,B\)を任意に選んだとき、以下の同値関係\begin{equation*}A\veebar B\Leftrightarrow \left( A\wedge \lnot B\right) \vee \left( \lnot
A\wedge B\right)
\end{equation*}が成り立ちます。つまり、排他的論理和\(\veebar \)は否定\(\lnot \)と論理積\(\wedge \)と論理和\(\vee \)を用いて表現できます。
A\wedge B\right)
\end{equation*}が成り立つ。
P\wedge Q\right)
\end{equation*}が成り立ちます。
&&R\vee S
\end{eqnarray*}はともに論理式であるため、先の命題より、\begin{equation*}
\left( P\wedge Q\right) \veebar \left( R\vee S\right) \Leftrightarrow \left(
\left( P\wedge Q\right) \wedge \lnot \left( R\vee S\right) \right) \vee
\left( \lnot \left( P\wedge Q\right) \wedge \left( R\vee S\right) \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 \)に置き換えることができます。
\end{equation*}を同値変形すると、\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*}となります。同値変形後の論理式\begin{equation*}
\left( P\wedge Q\right) \vee \left( \lnot P\wedge \lnot Q\right)
\end{equation*}には\(\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) \)は論理式である。
- 以上から論理式と判定されるものだけが論理式である。
演習問題
\end{equation*}を含意\(\rightarrow \)を用いずに表現してください。
\end{equation*}を含意\(\rightarrow \)や同等\(\leftrightarrow \)を用いずに表現してください。
\end{equation*}を排他的論理和\(\veebar \)を用いずに表現してください。
\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*}が成り立つことを証明してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】