Non-Equivalence
Contents |
Theorem
- $\neg \left ({p \iff q}\right) \dashv \vdash \left({\neg p \land q}\right) \lor \left({p \land \neg q}\right)$
- $\neg \left ({p \iff q}\right) \dashv \vdash \neg \left({p \implies q}\right) \lor \neg \left({q \implies p}\right)$
- $\neg \left ({p \iff q}\right) \dashv \vdash \left({p \lor q} \right) \land \neg \left({p \land q}\right)$
- $\neg \left ({p \iff q}\right) \dashv \vdash \left({p \lor q} \right) \land \left({\neg p \lor \neg q}\right)$
Thus we see that negation of equivalence means the same thing as either-or but not both, that is, exclusive or.
Proof
Proof by Natural Deduction
By the tableau method:
| Line | Pool | Formula | Rule | Depends upon | |
|---|---|---|---|---|---|
| 1 | 1 | $\neg \left ({p \iff q}\right)$ | P | (None) | |
| 2 | 1 | $\neg \left({\left ({p \implies q}\right) \land \left ({q \implies p}\right)}\right)$ | Material Equivalence | 1 | |
| 3 | 1 | $\neg \left({\left ({\neg p \lor q}\right) \land \left ({\neg q \lor p}\right)}\right)$ | Rule of Material Implication | 2 | |
| 4 | 1 | $\neg \left({\neg p \lor q}\right) \lor \neg \left ({\neg q \lor p}\right)$ | DM | 3 | |
| 5 | 1 | $\left ({\neg \neg p \land \neg q}\right) \lor \left ({\neg \neg q \land \neg p}\right)$ | DM | 4 | |
| 6 | 1 | $\left ({p \land \neg q}\right) \lor \left ({q \land \neg p}\right)$ | $\neg \neg \mathcal{E}$ | 5 | |
| 7 | 1 | $\left ({p \land \neg q}\right) \lor \left ({\neg p \land q}\right)$ | Comm | 6 | |
| 8 | 1 | $\left ({\neg p \land q}\right) \lor \left ({p \land \neg q}\right)$ | Comm | 7 |
$\blacksquare$
The argument is reversible:
| Line | Pool | Formula | Rule | Depends upon | |
|---|---|---|---|---|---|
| 1 | 1 | $\left ({\neg p \land q}\right) \lor \left ({p \land \neg q}\right)$ | P | (None) | |
| 2 | 1 | $\left ({p \land \neg q}\right) \lor \left ({\neg p \land q}\right)$ | Comm | 1 | |
| 3 | 1 | $\left ({p \land \neg q}\right) \lor \left ({q \land \neg p}\right)$ | Comm | 2 | |
| 4 | 1 | $\left ({\neg \neg p \land \neg q}\right) \lor \left ({\neg \neg q \land \neg p}\right)$ | $\neg \neg \mathcal{E}$ | 3 | |
| 5 | 1 | $\neg \left({\neg p \lor q}\right) \lor \neg \left ({\neg q \lor p}\right)$ | DM | 4 | |
| 6 | 1 | $\neg \left({\left ({\neg p \lor q}\right) \land \left ({\neg q \lor p}\right)}\right)$ | DM | 5 | |
| 7 | 1 | $\neg \left({\left ({p \implies q}\right) \land \left ({q \implies p}\right)}\right)$ | Rule of Material Implication | 6 | |
| 8 | 1 | $\neg \left ({p \iff q}\right)$ | Material Equivalence | 7 |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | |
|---|---|---|---|---|---|
| 1 | 1 | $\neg \left ({p \iff q}\right)$ | P | (None) | |
| 2 | 1 | $\neg \left({\left ({p \implies q}\right) \land \left ({q \implies p}\right)}\right)$ | Material Equivalence | 1 | |
| 3 | 1 | $\neg \left({p \implies q}\right) \lor \neg \left({q \implies p}\right)$ | DM | 2 |
$\blacksquare$
The above reasoning is completely reversible.
| Line | Pool | Formula | Rule | Depends upon | |
|---|---|---|---|---|---|
| 1 | 1 | $\neg \left({p \implies q}\right) \lor \neg \left({q \implies p}\right)$ | P | (None) | |
| 2 | 1 | $\neg \left({\left ({p \implies q}\right) \land \left ({q \implies p}\right)}\right)$ | DM | 1 | |
| 3 | 1 | $\neg \left ({p \iff q}\right)$ | Material Equivalence | 2 |
$\blacksquare$
- $\neg \left ({p \iff q}\right) \dashv \vdash \left({p \lor q} \right) \land \neg \left({p \land q}\right)$:
First, get this simple result:
| Line | Pool | Formula | Rule | Depends upon | |
|---|---|---|---|---|---|
| 1 | 1 | $p \land \neg q$ | P | (None) | |
| 2 | 1 | $p$ | $\land \mathcal{E}_1$ | 1 | |
| 3 | 1 | $p \lor q$ | $\lor \mathcal{I}_1$ | 2 | |
| 4 | 1 | $\neg q$ | $\land \mathcal{E}_2$ | 1 | |
| 5 | 1 | $\left({p \lor q}\right) \land \neg q$ | $\land \mathcal{I}$ | 1 |
$\blacksquare$
... and its converse:
| Line | Pool | Formula | Rule | Depends upon | |
|---|---|---|---|---|---|
| 1 | 1 | $\left({p \lor q}\right) \land \neg q$ | P | (None) | |
| 2 | 1 | $\left({p \land \neg q}\right) \lor \left({q \land \neg q}\right)$ | Dist | 1 | |
| 3 | 3 | $q \land \neg q$ | A | (None) | |
| 4 | 3 | $\bot$ | $\neg \mathcal{E}$ | 3 | |
| 5 | $\neg \left ({q \land \neg q}\right)$ | $\neg \mathcal{I}$ | 4 | ||
| 6 | 1 | $p \land \neg q$ | Disjunctive Syllogism | 2, 5 |
$\blacksquare$
Now the main part of the proof:
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg \left ({p \iff q}\right)$ | P | (None) | ||
| 2 | 1 | $\left({\neg p \land q}\right) \lor \left({p \land \neg q}\right)$ | SI | 1 | Non-Equivalence: from above | |
| 3 | 1 | $\left({p \land \neg q}\right) \lor \left({q \land \neg p}\right)$ | Comm | 2 | ||
| 4 | 1 | $\left ({\left({p \lor q}\right) \land \neg q}\right) \lor \left({\left({q \lor p}\right) \land \neg p}\right)$ | SI | 3 | From above | |
| 5 | 1 | $\left ({\left({p \lor q}\right) \land \neg q}\right) \lor \left({\left({p \lor q}\right) \land \neg p}\right)$ | Comm | 4 | ||
| 6 | 1 | $\left({p \lor q}\right) \land \left({\neg q \lor \neg p}\right)$ | Dist | 5 | ||
| 7 | 1 | $\left({p \lor q}\right) \land \left({\neg p \lor \neg q}\right)$ | Comm | 6 | ||
| 8 | 1 | $\left({p \lor q}\right) \land \neg \left({\neg \neg p \land \neg \neg q}\right)$ | DM | 7 | ||
| 9 | 1 | $\left({p \lor q}\right) \land \neg \left({p \land q}\right)$ | $\neg \neg \mathcal{E}$ | 8 |
The above argument is reversible:
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\left({p \lor q}\right) \land \neg \left({p \land q}\right)$ | P | (None) | ||
| 2 | 1 | $\left({p \lor q}\right) \land \left({\neg p \lor \neg q}\right)$ | DM | 1 | ||
| 3 | 1 | $\left({p \lor q}\right) \land \left({\neg q \lor \neg p}\right)$ | Comm | 2 | ||
| 4 | 1 | $\left ({\left({p \lor q}\right) \land \neg q}\right) \lor \left({\left({p \lor q}\right) \land \neg p}\right)$ | Dist | 3 | ||
| 5 | 1 | $\left({p \land \neg q}\right) \lor \left({q \land \neg p}\right)$ | SI | 4 | From above | |
| 6 | 1 | $\left({\neg p \land q}\right) \lor \left({p \land \neg q}\right)$ | Comm | 5 | ||
| 7 | 1 | $\neg \left ({p \iff q}\right)$ | SI | 6 | Non-Equivalence: from above |
$\blacksquare$
- $\neg \left ({p \iff q}\right) \dashv \vdash \left({p \lor q} \right) \land \left({\neg p \lor \neg q}\right)$
Follows directly from the above and De Morgan's Laws.
Proof by Truth Table
We apply the Method of Truth Tables to the propositions in turn.
As can be seen by inspection, in all cases the truth values under the main connectives match for all models.
$\begin{array}{|cccc||ccccccccc|} \hline
\neg & (p & \iff & q) & (\neg & p & \land & q) & \lor & (p & \land & \neg & q) \\
\hline
F & F & T & F & T & F & F & F & F & F & F & T & F \\
T & F & F & T & T & F & T & T & T & F & F & F & T \\
T & T & F & F & F & T & F & F & T & T & T & T & F \\
F & T & T & T & F & T & F & T & F & T & F & F & T \\
\hline
\end{array}$
$\blacksquare$
$\begin{array}{|cccc||ccccccccc|} \hline
\neg & (p & \iff & q) & \neg & (p & \implies & q) & \lor & \neg & (q & \implies & p) \\
\hline
F & F & T & F & F & F & T & F & F & F & F & T & F \\
T & F & F & T & F & F & T & T & T & T & T & F & F \\
T & T & F & F & T & T & F & F & T & F & F & T & T \\
F & T & T & T & F & T & T & T & F & F & T & T & T \\
\hline
\end{array}$
$\blacksquare$
$\begin{array}{|cccc||cccccccc|} \hline
\neg & (p & \iff & q) & (p & \lor & q) & \land & \neg & (p & \land & q) \\
\hline
F & F & T & F & F & F & F & F & T & F & F & F \\
T & F & F & T & F & T & T & T & T & F & F & T \\
T & T & F & F & T & T & F & T & T & T & F & F \\
F & T & T & T & T & T & T & F & F & T & T & T \\
\hline
\end{array}$
$\blacksquare$
$\begin{array}{|cccc||ccccccccc|} \hline
\neg & (p & \iff & q) & (p & \lor & q) & \land & (\neg & p & \lor & \neg & q) \\
\hline
F & F & T & F & F & F & F & F & T & F & T & T & F \\
T & F & F & T & F & T & T & T & T & F & T & F & T \\
T & T & F & F & T & T & F & T & F & T & T & T & F \\
F & T & T & T & T & T & T & F & F & T & F & F & T \\
\hline
\end{array}$
$\blacksquare$
Sources
- Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (1993): $\S 1.1$: Exercise $1.1.1$
- D.J. O'Connor and Betty Powell: Elementary Logic (1980): $\S 1.12$
