Logical Equivalence Relation
Suppose that formulas \(A,B\) are given. If the biconditional \[
A\leftrightarrow B
\]is a tautology, that is, if \(A\leftrightarrow B\) is true under every interpretation, then \(A\) and \(B\) are said to be logically equivalent, or each is said to be a necessary and sufficient condition for the other. We write \[
A\Leftrightarrow B
\]to express this fact. We call the symbol \(\Leftrightarrow\) the logical equivalence relation.
\left( P\left( x\right) \wedge P\left( x\right) \right) \leftrightarrow P\left( x\right) \quad \cdots (1)\end{equation}Since this is an open formula, in order to determine its truth value, choose arbitrarily the domain \(\overline{X}\) of the variable \(x\), the condition \(\overline{P}\left( x\right) \) specified by the propositional function, and a value \(\overline{x}\) assigned to the variable. Under this interpretation, we obtain the proposition \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}and can therefore determine its truth value using propositional logic. By the idempotent law of propositional logic, \(\left( 2\right) \) is true. Since the same argument applies under every interpretation, \(\left( 1\right) \) is a tautology. Therefore, \[
\left( P\left( x\right) \wedge P\left( x\right) \right) \Leftrightarrow P\left( x\right)
\]holds.
\left( \forall x\in X:\left( P\left( x\right) \wedge\lnot P\left(
x\right) \right) \right) \leftrightarrow\bot\quad \cdots (1)\end{equation}Since this is a closed formula, in order to determine its truth value, choose arbitrarily the domain \(\overline{X}\) of the variable \(x\) and the condition \(\overline{P}\left( x\right) \) specified by the propositional function. Consider the following proposition obtained under that interpretation: \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}By the law of contradiction, \(\overline{P}\left( x\right) \wedge \lnot\overline{P}\left( x\right) \) is false, so there is no \(x\in \overline{X}\) that satisfies \(\overline{P}\left( x\right) \wedge \lnot\overline{P}\left( x\right) \). Hence, \(\left( 2\right) \) is false. Since the same argument applies under every interpretation, \(\left( 1\right) \) is a tautology. Therefore, \[
\left( \forall x\in X:\left( P\left( x\right) \wedge\lnot P\left(
x\right) \right) \right) \Leftrightarrow\bot
\]holds.
Equivalence Transformations
If formulas \(A,B\) are logically equivalent, then their truth values always coincide under every interpretation, so they may be interchanged. Replacing a given formula with another formula logically equivalent to it is called an equivalence transformation.
Suppose that \(B\) is a subformula of a formula \(A\), and that there exists a formula \(B^{\prime}\) logically equivalent to \(B\). Let \(A^{\prime}\) denote the formula obtained by replacing \(B\) in \(A\) with \(B^{\prime}\). Since \(B\) and \(B^{\prime}\) have the same truth value under every interpretation, in this case, \[
A\Leftrightarrow A^{\prime}\]holds.
Q\left( x\right) \vee\left( P\left( x\right) \wedge P\left( x\right)
\right) \quad \cdots (1)\end{equation}As shown above,
\begin{equation}
P\left( x\right) \wedge P\left( x\right) \Leftrightarrow P\left( x\right)
\quad \cdots (2)\end{equation}holds. Using \(\left( 2\right) \) to perform an equivalence transformation on \(\left( 1\right) \), we obtain \[
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) .
\]
Reflexive Law of the Logical Equivalence Relation
For any formula \(A\), \[
A\Leftrightarrow A
\]always holds. In other words, every formula is logically equivalent to itself. This property of the logical equivalence relation \(\Leftrightarrow\) is called the reflexive law.
A\Leftrightarrow A
\]holds.
The proposition above guarantees that every formula can be transformed equivalently into itself.
P\left( x\right) \Leftrightarrow P\left( x\right) .
\]
P\left( x\right) \wedge Q\left( x\right) \Leftrightarrow P\left(
x\right) \wedge Q\left( x\right) .
\]
Symmetric Law of the Logical Equivalence Relation
For any formulas \(A,B\), if \[
A\Leftrightarrow B
\]holds, then
\[
B\Leftrightarrow A
\]also holds. In other words, if \(A\) is logically equivalent to \(B\), then \(B\) is also logically equivalent to \(A\). This property of the logical equivalence relation \(\Leftrightarrow\) is called the symmetric law.
A\Leftrightarrow B
\]holds, then
\[
B\Leftrightarrow A
\]also holds.
The proposition above guarantees that, if a formula \(A\) can be transformed equivalently into a formula \(B\), then conversely \(B\) can be transformed equivalently into \(A\).
P\left( x\right) \wedge P\left( x\right) \Leftrightarrow P\left( x\right)
.
\]Therefore, by the symmetric law,
\[
P\left( x\right) \Leftrightarrow P\left( x\right) \wedge P\left(
x\right)
\]also holds.
\left( \forall x\in X:\left( P\left( x\right) \wedge\lnot P\left(
x\right) \right) \right) \Leftrightarrow\bot
\]holds. Therefore, by the symmetric law,
\[
\bot\Leftrightarrow\left( \forall x\in X:\left( P\left( x\right)
\wedge\lnot P\left( x\right) \right) \right)
\]also holds.
Transitive Law of the Logical Equivalence Relation
For any formulas \(A,B,C\), if \begin{align*}
A & \Leftrightarrow B\\
B & \Leftrightarrow C
\end{align*}both hold, then
\[
A\Leftrightarrow C
\]also holds. In other words, if \(A\) is logically equivalent to \(B\) and \(B\) is logically equivalent to \(C\), then \(A\) is logically equivalent to \(C\). This property of the logical equivalence relation \(\Leftrightarrow\) is called the transitive law.
A & \Leftrightarrow B\\
B & \Leftrightarrow C
\end{align*}both hold, then
\[
A\Leftrightarrow C
\]also holds.
P\left( x\right) & \Leftrightarrow Q\left( x\right) \\
Q\left( x\right) & \Leftrightarrow R\left( x\right)
\end{align*}both hold, then by the transitive law of \(\Leftrightarrow\), \[
P\left( x\right) \Leftrightarrow R\left( x\right)
\]holds.
P\left( x\right) & \Leftrightarrow Q\left( x\right) \quad \cdots (1)\\
R\left( x\right) & \Leftrightarrow Q\left( x\right) \quad \cdots (2)\end{align}both hold. From \(\left( 2\right) \) and the symmetric law of \(\Leftrightarrow \), \[
Q\left( x\right) \Leftrightarrow R\left( x\right)
\]follows. Combining this with \(\left( 1\right) \) and applying the transitive law of \(\Leftrightarrow\), we obtain \[
P\left( x\right) \Leftrightarrow R\left( x\right) .
\]
Suppose that formulas \(A,B,C\) are given and, starting from \(A\), repeated equivalence transformations lead eventually to \(C\) in the form \[
A\Leftrightarrow B\Leftrightarrow C.
\]By the transitive law of \(\Leftrightarrow\), the initial formula \(A\) and the final formula \(C\) are guaranteed to be logically equivalent.
The same applies to three or more formulas \(A_{1},A_{2},\cdots,A_{n}\). If repeated equivalence transformations starting from \(A_{1}\) eventually lead to \(A_{n}\) in the form \[
A_{1}\Leftrightarrow A_{2}\Leftrightarrow\cdots\Leftrightarrow A_{n},
\]then repeated application of the transitive law of \(\Leftrightarrow\) guarantees that the initial formula \(A_{1}\) and the final formula \(A_{n}\) are logically equivalent.
Suppose that we wish to prove that two formulas \(A,B\) are logically equivalent, that is, \begin{equation}
A\Leftrightarrow B\quad \cdots (1)\end{equation}holds. If it is difficult to prove this directly, we may introduce another formula \(C\) and prove both \begin{align}
A & \Leftrightarrow C\quad \cdots (2)\\
C & \Leftrightarrow B\quad \cdots (3)\end{align}instead. This is because, if \(\left( 2\right) \) and \(\left( 3\right) \) both hold, then \(\left( 1\right) \) follows from the transitive law of \(\Leftrightarrow\).
Exercises
P\left( x\right) \wedge P\left( x\right) \Leftrightarrow P\left(
x\right) \vee P\left( x\right)
\]holds.
\lnot\lnot P\left( x\right) \vee\lnot\lnot Q\left( x\right)
\Leftrightarrow P\left( x\right) \vee Q\left( x\right)
\]holds.
A & \Leftrightarrow B\\
C & \Leftrightarrow B\\
C & \Leftrightarrow D
\end{align*}Show, using the symmetric and transitive laws of the logical equivalence relation, that
\[
A\Leftrightarrow D
\]holds.
\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)
\]holds.
\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) .
\]Give one interpretation showing that this relation does not hold.
B\Leftrightarrow B^{\prime}.
\]Show that, for any formula \(C\), \[
C\wedge B\Leftrightarrow C\wedge B^{\prime}\]holds.
\[
A\Leftrightarrow B
\]and that \(A\) is a tautology. Prove that \(B\) is also a tautology.
