3.3: Equivalence and Validity

Last updated
Save as PDF

Page ID: 48307

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Implications and Contrapositives

Do these two sentences say the same thing?

If I am hungry, then I am grumpy.

If I am not grumpy, then I am not hungry.

We can settle the issue by recasting both sentences in terms of propositional logic. Let \(P\) be the proposition “I am hungry” and \(Q\) be “I am grumpy.” The first sentence says “\(P \text{ IMPLIES } Q\)” and the second says “\(\text{NOT} (Q) \text{ IMPLIES NOT} (P)\).” Once more, we can compare these two statements in a truth table:

\[\nonumber \begin{array}{c|c|c|ccc}
P & Q & (P \text{ IMPLIES } Q) & (\text{NOT}(Q) & \text{ IMPLIES } & \text{NOT}(P))\\
\hline \mathbf{T} & \mathbf{T} & \mathbf{\large T} & \mathbf{F} & \mathbf{\large T} & \mathbf{F} \\
\mathbf{T} & \mathbf{F} & \mathbf{\large F} & \mathbf{T} & \mathbf{\large F} & \mathbf{F} \\
\mathbf{F} & \mathbf{T} & \mathbf{\large T} & \mathbf{F} & \mathbf{\large T} & \mathbf{T} \\
\mathbf{F} & \mathbf{F} & \mathbf{\large T} & \mathbf{T} & \mathbf{\large T} & \mathbf{T}
\end{array}\]

Sure enough, the highlighted columns showing the truth values of these two statements are the same. A statement of the form “\(\text{NOT} (Q) \text{ IMPLIES } \text{NOT} (P)\)” is called the contrapositive of the implication “\(P \text{ IMPLIES } Q\).” The truth table shows that an implication and its contrapositive are equivalent—they are just different ways of saying the same thing.

In contrast, the converse of “\(P \text{ IMPLIES } Q\)” is the statement “\(Q \text{ IMPLIES } P\).” The converse to our example is:

If I am grumpy, then I am hungry.

This sounds like a rather different contention, and a truth table confirms this suspicion:

\[\nonumber \begin{array}{c|c|c|c}
P & Q & P \text{ IMPLIES } Q & Q \text{ IMPLIES } P \\
\hline \mathbf{T} & \mathbf{T} & \mathbf{\large T} & \mathbf{\large T} \\
\mathbf{T} & \mathbf{F} & \mathbf{\large F} & \mathbf{\large T} \\
\mathbf{F} & \mathbf{T} & \mathbf{\large T} & \mathbf{\large F} \\
\mathbf{F} & \mathbf{F} & \mathbf{\large T} & \mathbf{\large T}
\end{array}\]

Now the highlighted columns differ in the second and third row, confirming that an implication is generally not equivalent to its converse.

One final relationship: an implication and its converse together are equivalent to an iff statement, specifically, to these two statements together. For example,

If I am grumpy then I am hungry, and if I am hungry then I am grumpy.

are equivalent to the single statement:

I am grumpy iff I am hungry.

Once again, we can verify this with a truth table.

\[\nonumber \begin{array}{c|c|ccc|c}
P & Q & (P \text{ IMPLIES } Q) & \text{AND} & (Q \text{ IMPLIES } P) & (P \text{ IFF } Q)\\
\hline \mathbf{T} & \mathbf{T} & \mathbf{T} & \mathbf{\large T} & \mathbf{T} & \mathbf{\large T} \\
\mathbf{T} & \mathbf{F} & \mathbf{F} & \mathbf{\large F} & \mathbf{T} & \mathbf{\large F} \\
\mathbf{F} & \mathbf{T} & \mathbf{T} & \mathbf{\large F} & \mathbf{F} & \mathbf{\large F} \\
\mathbf{F} & \mathbf{F} & \mathbf{T} & \mathbf{\large T} & \mathbf{T} & \mathbf{\large T}
\end{array}\]

The fourth column giving the truth values of

\[\nonumber (P \text{ IMPLIES } Q) \text{ AND } (Q \text{ IMPLIES } P)\]

is the same as the sixth column giving the truth values of \(P \text{ IFF } Q\), which confirms that the \(\text{ AND }\) of the implications is equivalent to the \(\text{ IFF }\) statement.

Validity and Satisfiability

A valid formula is one which is always true, no matter what truth values its variables may have. The simplest example is

\[\nonumber P \text{ OR NOT } (P).\]

You can think about valid formulas as capturing fundamental logical truths. For example, a property of implication that we take for granted is that if one statement implies a second one, and the second one implies a third, then the first implies the third. The following valid formula confirms the truth of this property of implication.

\[\nonumber [(P \text{ IMPLIES } Q) \text{ AND } (Q \text{ IMPLIES } R)] \text{ IMPLIES } (P \text{ IMPLIES } R).\]

Equivalence of formulas is really a special case of validity. Namely, statements \(F\) and \(G\) are equivalent precisely when the statement (\(F \text{ IFF } G\)) is valid. For example, the equivalence of the expressions (3.2.1) and (3.2.2) means that

\[\nonumber (A \text{ OR } B) \text{ IFF } (A \text{ OR} \text{ NOT } (A) \text{ AND } B))\]

is valid. Of course, validity can also be viewed as an aspect of equivalence. Namely, a formula is valid iff it is equivalent to \(\textbf{T}\).

A satisfiable formula is one which can sometimes be true—that is, there is some assignment of truth values to its variables that makes it true. One way satisfiability comes up is when there are a collection of system specifications. The job of the system designer is to come up with a system that follows all the specs. This means that the \(\text{AND}\) of all the specs must be satisfiable or the designer’s job will be impossible (see Problem 3.12).

There is also a close relationship between validity and satisfiability: a statement \(P\) is satisfiable iff its negation \(\text{NOT} (P)\) is not valid.