論理的同値関係
論理式\(A,B\)が与えられたとき、解釈を任意に選んだ上で、その場合に\(A,B\)から得られる命題を\(\overline{A},\overline{B}\)で表記します。任意の解釈において、\begin{equation*}\overline{A}\leftrightarrow \overline{B}
\end{equation*}が真である場合には、すなわち、任意の解釈において\(\overline{A}\)の真理値と\(\overline{B}\)の真理値が一致する場合には、\(A\)は\(B\)と論理的に同値（logically equivalent）であるとか、\(A\)と\(B\)はお互いに必要十分条件（necessary and sufficient condition）であるなどと言い、そのことを、\begin{equation*}A\Leftrightarrow B
\end{equation*}で表記します。その上で、記号\(\Leftrightarrow \)を論理的同値関係（logical equivalence relation）と呼ぶこととします。
P\left( x\right)
\end{equation*}について考えます。これは開論理式であるため、値を確定するためには変数\(x\)の定義域\(X\)と命題関数\(P\left( x\right) \)の形状および変数\(x\)に代入する値を指定する必要があります。そこで、\(x\)の定義域\(\overline{X}\)と命題関数の形状\(\overline{P}\left( x\right) \)および変数に代入する値\(\overline{x}\in \overline{X}\)をそれぞれ任意に選ぶと、以下の命題\begin{equation*}\left( \overline{P}\left( \overline{x}\right) \wedge \overline{P}\left(
\overline{x}\right) \right) \leftrightarrow \overline{P}\left( \overline{x}\right)
\end{equation*}が得られます。
$$\begin{array}{ccc}
\hline
\overline{P}\left( \overline{x}\right) & \overline{P}\left( \overline{x} \right) \wedge \overline{P}\left( \overline{x}\right) & \left( \overline{P }\left( \overline{x}\right) \wedge \overline{P}\left( \overline{x}\right) \right) \leftrightarrow \overline{P}\left( \overline{x}\right) \\ \hline
1 & 1 & 1 \\ \hline
0 & 0 & 1 \\ \hline
\end{array}$$
以上の真理値表から明らかであるように先の命題は常に真であるため、\begin{equation*}
P\left( x\right) \wedge P\left( x\right) \Leftrightarrow P\left( x\right)
\end{equation*}が成り立ちます。つまり、\(P\left( x\right) \wedge P\left( x\right) \)と\(P\left( x\right) \)は論理的に同値です。
\right) \right) \leftrightarrow \bot
\end{equation*}について考えます。これは閉論理式であるため、値を確定するためには変数\(x\)の定義域\(X\)と命題関数\(P\left( x\right) \)の形状を指定する必要があります。そこで、\(x\)の定義域\(\overline{X}\)と命題関数の形状\(\overline{P}\left(x\right) \)をそれぞれ任意に選ぶと、以下の命題\begin{equation*}\left( \forall x\in \overline{X}:\left( \overline{P}\left( x\right) \wedge
\lnot \overline{P}\left( x\right) \right) \right) \leftrightarrow \bot
\end{equation*}が得られます。全称命題の定義より、以下の命題\begin{equation*}
\forall x\in \overline{X}:\left( \overline{P}\left( x\right) \wedge \lnot
\overline{P}\left( x\right) \right)
\end{equation*}は以下の命題\begin{equation*}
\bigwedge_{x\in \overline{X}}\left( \overline{P}\left( x\right) \wedge
\lnot \overline{P}\left( x\right) \right)
\end{equation*}と同一視されます。論理積の定義より\(\overline{P}\left( x\right) \wedge \lnot \overline{P}\left( x\right) \)は偽であり、したがってやはり論理積の定義より上の命題は偽です。以上より、\begin{equation*}\left( \forall x\in X:\left( P\left( x\right) \wedge \lnot P\left( x\right)
\right) \right) \Leftrightarrow \bot
\end{equation*}であることが明らかになりました。つまり、\(\forall x\in X:\left( P\left( x\right) \wedge \lnot P\left(x\right) \right) \)と\(\bot \)は論理的に同値です。
同値変形
論理式\(A,B\)が論理的に同値である場合には、任意の解釈のもとで\(A\)から生成される命題\(\overline{A}\)と\(B\)から生成される命題\(\overline{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*}が成り立ちます。
\right) \quad \cdots (1)
\end{equation}に注目します。先に示したように、\begin{equation}
P\left( x\right) \wedge P\left( x\right) \Leftrightarrow P\left( x\right)
\quad \cdots (2)
\end{equation}が成り立ちます。\(\left(2\right) \)を用いて\(\left( 1\right) \)を同値変形することにより、\begin{equation*}Q\left( x\right) \vee \left( P\left( x\right) \wedge P\left( x\right)
\right) \Leftrightarrow Q\left( x\right) \vee P\left( x\right)
\end{equation*}を得ます。
論理的同値関係の反射律
論理式\(A\)を任意に選んだとき、\begin{equation*}A\Leftrightarrow A
\end{equation*}が成り立つことが保証されます。つまり、任意の論理式は自身と論理的に同値であるということです。論理的同値関係\(\Leftrightarrow \)が満たす以上の性質を反射律（reflexive law）と呼びます。
\end{equation*}が成り立つ。
以上の命題は、任意の論理式は自身へ同値変形可能であることを保証します。
\end{equation*}が成り立ちます。
\wedge Q\left( x\right)
\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\left( x\right) \Leftrightarrow P\left( x\right) \wedge P\left( x\right)
\end{equation*}もまた成り立ちます。
\right) \right) \Leftrightarrow \bot
\end{equation*}が成り立つことは先に示した通りです。したがって、対称律より、\begin{equation*}
\bot \Leftrightarrow \left( \forall x\in X:\left( P\left( x\right) \wedge
\lnot P\left( x\right) \right) \right)
\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\left( x\right) &\Leftrightarrow &R\left( x\right)
\end{eqnarray*}がともに成り立つ場合には、\(\Leftrightarrow \)の推移律より、\begin{equation*}P\left( x\right) \Leftrightarrow R\left( x\right)
\end{equation*}が成り立つことが保証されます。
R\left( x\right) &\Leftrightarrow &Q\left( x\right) \quad \cdots (2)
\end{eqnarray}がともに成り立つものとします。\(\left( 2\right) \)および\(\Leftrightarrow \)の対称律より、\begin{equation*}Q\left( x\right) \Leftrightarrow R\left( x\right)
\end{equation*}を得ます。これと\(\left(1\right) \)および\(\Leftrightarrow \)の推移律より、このとき、\begin{equation*}P\left( x\right) \Leftrightarrow R\left( x\right)
\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) \)が成り立つことが保証されるからです。
演習問題
\vee P\left( x\right)
\end{equation*}が成り立つことを示してください。
\Leftrightarrow P\left( x\right) \vee Q\left( x\right)
\end{equation*}が成り立つことを示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】