Let $p$, $q$, $r$, and $s$ be any propositions. Then does the following logical equivalence hold?
$$ \big( p \rightarrow q \big) \rightarrow \big( r\rightarrow s \big) \ \equiv \ \big( p \rightarrow r \big) \rightarrow \big( q \rightarrow s \big). \tag{1} $$
My Attempt:
We note that the left-hand-side of (1) is False if and only if $p \rightarrow q$ is True and $r \rightarrow s$ is False, which in turn holds if and only if
$$
\overline{ \left( p \equiv T \ \land \ q \equiv F \right) } \ \land \ \bigl( r \equiv T \ \land \ s \equiv F \bigr),
$$
which is the same as
$$
\bigl( p \equiv F \ \lor \ q \equiv T \bigr) \ \land \ \bigl( r \equiv T \ \land \ s \equiv F \bigr),
$$
that is,
$$
\begin{align}
& \bigl( p \equiv F \ \land \ r \equiv T \ \land \ s \equiv F \bigr) \\ & \ \ \ \lor \big( q \equiv T \ \land \ r \equiv T \ \land \ s \equiv F \bigr), \end{align} \tag{2}
$$
where $T$ stands for True and $F$ stands for False. Thus the left-hand-side of (1) above is False if and only if (2) holds.
On the other hand, the right-hand-side of (1) is False if and only if $p \rightarrow r$ is True and $q \rightarrow s$ is False, which in turn holds if and only if
$$
\overline{ \left( p \equiv T \ \land \ r \equiv F \right) } \ \land \ \bigl( q \equiv T \ \land \ s \equiv F \bigr),
$$
which is the same as
$$
\begin{align}
& \bigl( p \equiv F \ \lor \ r \equiv T \bigr) \\
& \ \ \ \land \ \bigl( q \equiv T \ \land \ s \equiv F \bigr),
\end{align}
$$
that is,
$$
\begin{align}
& \bigl( p \equiv F \ \land \ q \equiv T \ \land \ s \equiv F \bigr) \\
& \ \ \ \lor \ \bigl( r \equiv T \ \land \ q \equiv T \ \land \ s \equiv F \bigr),
\end{align}
$$
or in other words,
$$
\begin{align}
& \bigl( p \equiv F \ \land \ q \equiv T \ \land \ s \equiv F \bigr) \\
& \ \ \ \lor \ \bigl( q \equiv T \ \land \ r \equiv T \ \land \ s \equiv F \bigr). \end{align} \tag{3}
$$
Thus the right-hand-side of \label{1} is False if and only if (3) holds.
Now from (2) we find that the left-hand-side of (1) is True if $r \equiv F$ whatever the truth values of $p$, $q$, and $s$ may be, because in that case both the conjunctions that form the components of the disjunction in (2) are False thus making the disjunction in (2) False too. On the other hand, the right-hand-side of (1) is False if
$$ p \equiv F, \qquad q \equiv T, \qquad r \equiv F, \qquad s \equiv F, \tag{4} $$
because for this combination of truth values (3) above holds.
Alternatively, from (3) above we find that the right-hand-side of (1) is True if $q \equiv F$ whatever the truth values of $p$, $r$, and $s$ may be, because in that case both the conjunctions that form the components of the disjunction in (2) are False thus making the disjunction in (2) False too. On the other hand, the left-hand-side of (1) is False if
$$ p \equiv F, \qquad q \equiv F, \qquad r \equiv T, \qquad s \equiv F, \tag{5} $$
because for this combination of truth values (2) above holds.
Hence the combinations of truth values in (4) and in (5) show that the logical equivalence in (1) above fails to hold.
Am I right?
Is my proof correct, clear, and complete enough? Or, are there any issues of accuracy, clarity, or completeness in this proof?
Best Answer
Here’s another approach, using conjunctive normal form.
We note that $$ \begin{align} \big(p \rightarrow q \big) \rightarrow \big(r \rightarrow s \big) &\equiv \left( \overline{ p \rightarrow q } \right) \lor \big( r \rightarrow s \big) \\ & \equiv \left( \overline{ \overline{p} \lor q } \right) \lor \left( \overline{r} \lor s \right) \\ &\equiv \left( \overline{\overline{p}} \land \overline{q} \right) \lor \left( \overline{r} \lor s \right) \\ &\equiv \left( p \land \overline{q} \right) \lor \left( \overline{r} \lor s \right) \\ &\equiv \left( p \lor \left( \overline{r} \lor s \right) \right) \ \land \ \left( \overline{q} \lor \left( \overline{r} \lor s \right) \right) \\ &\equiv \left( p \lor \overline{r} \lor s \right) \ \land \ \left( \overline{q} \lor \overline{r} \lor s \right). \end{align} $$ Thus we have $$ \big(p \rightarrow q \big) \rightarrow \big(r \rightarrow s \big) \ \equiv \ \left( p \lor \overline{r} \lor s \right) \ \land \ \left( \overline{q} \lor \overline{r} \lor s \right). \tag{1} \label1 $$ Interchanging the roles of $q$ and $r$ in \eqref{1} yields $$ \begin{align} \big(p \rightarrow r \big) \rightarrow \big( q \rightarrow s \big) & \equiv \left( p \lor \overline{q} \lor s \right) \ \land \ \left( \overline{r} \lor \overline{q} \lor s \right) \\ &\equiv \left( p \lor \overline{q} \lor s \right) \ \land \ \left( \overline{q} \lor \overline{r} \lor s \right). \end{align} $$ Thus we have $$ \big(p \rightarrow r \big) \rightarrow \big( q \rightarrow s \big) \ \equiv \ \left( p \lor \overline{q} \lor s \right) \ \land \ \left( \overline{q} \lor \overline{r} \lor s \right). \tag{2}\label{2} $$
From \eqref{1} and \eqref{2}, we note that these two conjunctive normal forms are clearly equivalent when $q$ and $r$ take the same truth values, so a natural next step is to instead test opposite truth values, thus leading to a counterexample.