論理的同値関係
論理式\(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）と呼ぶこととします。
P\left( x\right) \quad \cdots (1)
\end{equation}について考えます。これは開論理式であるため、値を確定するために変数\(x\)の定義域\(\overline{X}\)と命題関数が表す条件\(\overline{P}\left( x\right) \)および変数に代入する値\(\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) \quad \cdots (2)
\end{equation}が得られるため、命題論理を用いて値を判定できます。実際、命題論理におけるベキ等律より\(\left( 2\right) \)は真です。任意の解釈のもとで同様の議論が成り立つため\(\left( 1\right) \)は恒真式であり、したがって、\begin{equation*} \left( P\left( x\right) \wedge P\left( x\right) \right) \Leftrightarrow
P\left( x\right)
\end{equation*}が成り立ちます。
\right) \right) \leftrightarrow \bot \quad \cdots (1)
\end{equation}について考えます。これは閉論理式であるため、値を確定するために変数\(x\)の定義域\(\overline{X}\)と命題関数が定める条件\(\overline{P}\left( x\right) \)を任意に選びます。その解釈のもとで得られる以下の命題\begin{equation} \forall x\in \overline{X}:\left( \overline{P}\left( x\right) \wedge \lnot
\overline{P}\left( x\right) \right) \quad \cdots (2)
\end{equation}に注目します。矛盾律より\(\overline{P}\left( x\right) \wedge \lnot \overline{P}\left( x\right) \)は偽であるため、\(\overline{P}\left( x\right) \wedge \lnot \overline{P}\left( x\right) \)を満たす\(x\in \overline{X}\)は存在せず、ゆえに\(\left( 2\right) \)は偽です。任意の解釈のもとで同様の議論が成り立つため\(\left( 1\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*}が成り立ちます。
同値変形
論理式\(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*}が成り立ちます。
\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*}が成り立つことを示してください。
A &\Leftrightarrow &B \\
C &\Leftrightarrow &B \\
C &\Leftrightarrow &D
\end{eqnarray*}が成り立つものとします。このとき、
\begin{equation*}
A\Leftrightarrow D
\end{equation*}が成り立つことを、論理的同値関係の対称律と推移律を用いて示してください。
\forall x\in X:\left( P\left( x\right) \rightarrow Q\left( x\right) \right)
\Leftrightarrow \lnot \left( \exists x\in X:P\left( x\right) \wedge \lnot
Q\left( x\right) \right)
\end{equation*}が成り立つことを示してください。
\forall x\in X:\left(P\left(x\right)\vee Q\left(x\right)\right)
\Leftrightarrow \left(\forall x\in X:P\left(x\right)\right) \vee
\left(\forall x\in X:Q\left(x\right)\right)
\end{equation*}これが成り立たないことを示す解釈を1つ与えてください。
B\Leftrightarrow B^{\prime}
\end{equation*}が成り立つものとします。このとき、任意の論理式\(C\)について、 \begin{equation*}
C\wedge B\Leftrightarrow C\wedge B^{\prime}
\end{equation*}が成り立つことを示してください。
A\Leftrightarrow B
\end{equation*}が成り立ち、\(A\)が恒真式であるものとします。このとき、\(B\)も恒真式であることを証明してください。
