論理的同値関係
論理式\(A,B\)が与えられたとき、それらに関する同等\begin{equation*}A\leftrightarrow B
\end{equation*}が恒真式である場合には、すなわち、任意の解釈のもとで\(A\leftrightarrow B\)が真になる場合には、\(A\)は\(B\)と論理的に同値（logically equivalent）であるとか、\(A\)と\(B\)はお互いに必要十分条件（necessary and sufficient condition）であるなどと言い、そのことを、\begin{equation*}A\Leftrightarrow B
\end{equation*}で表記します。その上で、記号\(\Leftrightarrow \)を論理的同値関係（logical equivalence relation）と呼ぶこととします。
\end{equation*}に関して、以下の真理値表が得られます。
$$\begin{array}{ccc}
\hline
P & P\wedge P & P\wedge P\leftrightarrow P \\ \hline
1 & 1 & 1 \\ \hline
0 & 0 & 1 \\ \hline
\end{array}$$
つまり、\(P\wedge P\leftrightarrow P\)は2通りの解釈が可能ですが、いずれの解釈においても\(P\wedge P\leftrightarrow P\)の値は\(1\)であるため、\begin{equation*}P\wedge P\Leftrightarrow P
\end{equation*}が成り立ちます。つまり、\(P\wedge P\)は\(P\)と論理的に同値です。
\end{equation*}に関して、以下の真理値表が得られます。
$$\begin{array}{cccc}
\hline
P & P\wedge P & P\vee P & P\wedge P\leftrightarrow P\vee P \\ \hline
1 & 1 & 1 & 1 \\ \hline
0 & 0 & 0 & 1 \\ \hline
\end{array}$$
つまり、\(P\wedge P\leftrightarrow P\vee P\)は2通りの解釈が可能ですが、いずれの解釈においても\(P\wedge P\leftrightarrow P\vee P\)の値は\(1\)であるため、\begin{equation*}P\wedge P\Leftrightarrow P\vee P
\end{equation*}が成り立ちます。つまり、\(P\wedge P\)は\(P\vee P\)と論理的に同値です。
同値変形
論理式\(A,B\)が論理的に同値である場合には、任意の解釈のもとで\(A\)と\(B\)の真理値は常に一致するため、両者は交換可能です。そこで、与えられた論理式をそれと論理的に同値な論理式に交換することを同値変形（equivalence transformation）と呼びます。
論理式\(A\)の部分論理式\(B\)に注目したとき、\(B\)と論理的に同値であるような論理式\(B^{\prime }\)が存在するものとします。さらに、\(A\)中の\(B\)を\(B^{\prime }\)に同値変形することにより得られる論理式を\(A^{\prime }\)で表します。\(B\)と\(B^{\prime }\)の真理値は任意の解釈のもとで一致するため、この場合、\begin{equation*}A\Leftrightarrow A^{\prime }
\end{equation*}が成り立ちます。
\end{equation}に注目します。先に示したように、\begin{equation}
P\wedge P\Leftrightarrow P \quad \cdots (2)
\end{equation}が成り立ちます。\(\left(2\right) \)を用いて\(\left( 1\right) \)を同値変形することにより、\begin{equation*}Q\vee \left( P\wedge P\right) \Leftrightarrow Q\vee P
\end{equation*}を得ます。
論理的同値関係の反射律
論理式\(A\)を任意に選んだとき、\begin{equation*}A\Leftrightarrow A
\end{equation*}が成り立つことが保証されます。つまり、任意の論理式は自身と論理的に同値であるということです。論理的同値関係\(\Leftrightarrow \)が満たす以上の性質を反射律（reflexive law）と呼びます。
\end{equation*}が成り立つ。
以上の命題は、任意の論理式は自身へ同値変形可能であることを保証します。
\end{equation*}が成り立ちます。
\end{equation*}が成り立ちます。
論理的同値関係の対称律
論理式\(A,B\)を任意に選んだとき、\begin{equation*}A\Leftrightarrow B
\end{equation*}が成り立つ場合には、\begin{equation*}
B\Leftrightarrow A
\end{equation*}もまた成り立つことが保証されます。つまり、\(A\)が\(B\)と論理的に同値である場合には、逆に、\(B\)が\(A\)と論理的に同値であることも保証されるということです。論理的同値関係\(\Leftrightarrow \)が満たす以上の性質を対称律（symmetric law）と呼びます。
\end{equation*}が成り立つ場合には、\begin{equation*}
B\Leftrightarrow A
\end{equation*}もまた成り立つ。
以上の命題は、論理式\(A,B\)が与えられたとき、\(A\)が\(B\)へ同値変形可能である場合には、逆に、\(B\)が\(A\)へ同値変形可能であることを保証します。
\end{equation*}が成り立つことは先に示した通りです。したがって、対称律より、\begin{equation*}
P\Leftrightarrow P\wedge P
\end{equation*}もまた成り立ちます。
\end{equation*}が成り立つことは先に示した通りです。したがって、対称律より、\begin{equation*}
P\vee P\Leftrightarrow P\wedge P
\end{equation*}もまた成り立ちます。
論理的同値関係の推移律
論理式\(A,B,C\)を任意に選んだとき、\begin{eqnarray*}A &\Leftrightarrow &B \\
B &\Leftrightarrow &C
\end{eqnarray*}がともに成り立つ場合には、\begin{equation*}
A\Leftrightarrow C
\end{equation*}もまた成り立つことが保証されます。つまり、\(A\)が\(B\)と論理的に同値であり、\(B\)が\(C\)と論理的に同値である場合には、\(A\)が\(C\)と論理的に同値であることが保証されるということです。論理的同値関係\(\Leftrightarrow \)が満たす以上の性質を推移律（transitive law）と呼びます。
B &\Leftrightarrow &C
\end{eqnarray*}がともに成り立つ場合には、\begin{equation*}
A\Leftrightarrow C
\end{equation*}もまた成り立つ。
Q &\Leftrightarrow &R
\end{eqnarray*}がともに成り立つ場合には、\(\Leftrightarrow \)の推移律より、\begin{equation*}P\Leftrightarrow R
\end{equation*}が成り立つことが保証されます。
R &\Leftrightarrow &Q \quad \cdots (2)
\end{eqnarray}がともに成り立つものとします。\(\left( 2\right) \)および\(\Leftrightarrow \)の対称律より、\begin{equation*}Q\Leftrightarrow R
\end{equation*}を得ます。これと\(\left(1\right) \)および\(\Leftrightarrow \)の推移律より、このとき、\begin{equation*}P\Leftrightarrow R
\end{equation*}が成り立ちます。
論理式\(A,B,C\)が与えられたとき、\begin{equation*}A\Leftrightarrow B\Leftrightarrow C
\end{equation*}という形で\(A\)から出発して同値変形を繰り返して最終的に\(C\)へ至った場合、\(\Leftrightarrow \)の推移律より、出発点\(A\)と終着点\(C\)は論理的に同値であることが保証されます。
3個以上の論理式\(A_{1},A_{2},\cdots,A_{n}\)についても、\begin{equation*}A_{1}\Leftrightarrow A_{2}\Leftrightarrow \cdots \Leftrightarrow A_{n}
\end{equation*}という形で\(A_{1}\)から出発して同値変形を繰り返して最終的に\(A_{n}\)へ至った場合、\(\Leftrightarrow \)の推移律を繰り返し適用することにより、出発点\(A_{1}\)と終着点\(A_{n}\)は論理的に同値であることが保証されます。
2つの論理式\(A,B\)が論理的に同値であること、すなわち、\begin{equation}A\Leftrightarrow B \quad \cdots (1)
\end{equation}が成り立つことを示そうとしている状況を想定します。これを直接示すことが困難である場合、別の論理式\(C\)を仲介させて、\begin{eqnarray}A &\Leftrightarrow &C \quad \cdots (2) \\
C &\Leftrightarrow &B \quad \cdots (3)
\end{eqnarray}をともに示しても構いません。なぜなら、\(\left( 2\right) \)と\(\left( 3\right) \)がともに成り立つ場合、\(\Leftrightarrow \)の推移律より\(\left(1\right) \)が成り立つことが保証されるからです。
演習問題
B &\Leftrightarrow &C \\
C &\Leftrightarrow &D
\end{eqnarray*}がいずれも成り立つものとします。このとき、\begin{equation*}
D\Leftrightarrow A
\end{equation*}が成り立つことを同値変形で示してください。
B &\Leftrightarrow &C
\end{eqnarray*}がいずれも成り立つものとします。このとき、\begin{equation*}
\lnot A\Leftrightarrow \lnot C
\end{equation*}が成り立つことを同値変形で示してください。
\end{equation*}が成り立つことを同値変形で示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】