Important propositional equivalences

Subsection 1.2.2 Important propositional equivalences

The following theorem can be thought of as telling us how to distribute a “not” across an “and” or an “or”.

Theorem 1.2.2.1. De Morgan’s laws for propositions.

Let \(p\) and \(q\) be propositions.

\(\displaystyle \lnot(p\land q)\equiv\lnot p\lor\lnot q\)
🔗

🔗
\(\displaystyle \lnot (p\lor q) \equiv\lnot p\land\lnot q\)
🔗

🔗

Proof.

We prove \(\lnot (p\lor q) \equiv\lnot p\land\lnot q\) and leave the other as an exercise. First compute the truth table.

\begin{equation*} \begin{array}{|*{2}{c|}|*{5}{c|}} \hline p\amp q\amp \lnot p\amp \lnot q\amp p\lor q\amp \lnot(p\lor q)\amp \lnot p \land\lnot q\\ \hline \true\amp \true\amp \false \amp \false \amp \true\amp \false \amp \false \\ \true\amp \false \amp \false \amp \true\amp \true\amp \false \amp \false \\ \false \amp \true\amp \true\amp \false \amp \true\amp \false \amp \false \\ \false \amp \false \amp \true\amp \true\amp \false \amp \true\amp \true\\ \hline \end{array} \end{equation*}

Since the last two columns are the same, we have \(\lnot (p\lor q) \equiv\lnot p\land\lnot q\) as desired.

🔗

Example 1.2.2.2. Jake is wearing khakis.

Let’s negate the statement “Jake is wearing khakis and sounds hideous.”

🔗

Let \(j\) be “Jake is wearing khakis,” and let \(h\) be “Jake sounds hideous.” Then the original statement is \(j\land h\) . By De Morgan’s law, the negation is

\begin{equation*} \lnot(j\land h) =\lnot j\lor\lnot h. \end{equation*}

This is, “Jake is not wearing khakis, or he does not sound hideous.”

🔗

There are several other important propositional equivalences that we should know.

🔗

Theorem 1.2.2.3. Proposition Identities I.

Let \(p\) be a proposition.

Identity laws 🔗: \(p\land \true \equiv p\) and \(p \lor \false \equiv p\text{.}\)
🔗
Domination laws 🔗: \(p\lor \true \equiv \true\) and \(p \land \false \equiv \false\text{.}\)
🔗
Idempotent laws 🔗: \(p\lor p \equiv p\) and \(p\land p \equiv p\text{.}\)
🔗
Double negation law 🔗: \(\displaystyle \lnot(\lnot p) \equiv p\)
🔗
Negation law 🔗: \(p\lor\lnot p \equiv \true\) and \(p \land\lnot p \equiv \false\text{.}\)
🔗

🔗

Proof.

Exercise. Just compute the truth tables and verify the corresponding columns are the same.

🔗

Theorem 1.2.2.4. Proposition Identities II.

Let \(p\) and \(q\) be propositions.

Commutative laws 🔗: \(p\lor q \equiv q\lor p\) and \(p\land q \equiv q\land p\text{.}\)
🔗
Absorption laws 🔗: \(p\lor (p\land q) \equiv p\) and \(p\land (p\lor q) \equiv p\text{.}\)
🔗
Contrapositive law 🔗: \(\displaystyle p \implies q \equiv\lnot q \implies\lnot p\)
🔗

🔗

Proof.

Exercise. Just compute the truth tables and verify the corresponding columns are the same.

🔗

Theorem 1.2.2.5. Proposition Identities III.

Let \(p\) , \(q\text{,}\) and \(r\) be propositions.

Associative laws 🔗: \(p\lor (q\lor r) \equiv (p\lor q) \lor r\text{;}\) \(p\land (q\land r) \equiv (p\land q)\land r.\)
🔗
Distributive laws 🔗: \(p\lor(q\land r) \equiv (p\lor q) \land (p\lor r)\text{;}\) \(p\land (q\lor r) \equiv (p\land q)\lor (p\land r).\)
🔗

🔗

Proof.

Exercise. Just compute the truth tables and verify the corresponding columns are the same.

🔗

We can also use logical equivalences to turn conditionals into disjunctions.

🔗

Theorem 1.2.2.6.

Let \(p\) and \(q\) be propositions. Then

\begin{equation*} p \implies q \equiv\lnot p\lor q. \end{equation*}

🔗

Proof.

We compute the relevant truth table.

\begin{equation*} \begin{array}{|*{2}{c|}|*{3}{c|}} \hline p\amp q\amp \lnot p\amp \lnot p\lor q\amp p \implies q\\ \hline \true\amp \true\amp \false \amp \true\amp \true\\ \true\amp \false \amp \false \amp \false \amp \false \\ \false \amp \true\amp \true\amp \true\amp \true\\ \false \amp \false \amp \true\amp \true\amp \true\\ \hline \end{array} \end{equation*}

Since the last two columns are equal, we have \(p \implies q \equiv \lnot p\lor q\) .

🔗

Once we have proven all of these important logical equivalences, we can use them to prove additional equivalences and simplify compound propositions without resorting to truth tables.

🔗

Example 1.2.2.7. Roller coaster (continued).

Recall Example 1.1.6.7, where we translated “You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.” Let

\(r \) be “You can ride the roller coaster,”
🔗

🔗
\(f \) be “You are under 4 feet tall,”
🔗

🔗
\(s \) be “You are older than 16 years old.”
🔗

🔗

Then we had two seemingly correct translations

\begin{equation*} \lnot s \implies (f \implies\lnot r) \end{equation*}

and

\begin{equation*} (f\land\lnot s) \implies\lnot r. \end{equation*}

Let’s see that these statements are logically equivalent by simplifying each one. We change each conditional to a disjunction and simplify.

\begin{align*} \lnot s \implies (f \implies\lnot r) \amp \equiv s\lor (f \implies\lnot r) \\ \amp \equiv s\lor (\lnot f\lor\lnot r) \end{align*}

🔗

\begin{align*} (f\land\lnot s) \implies\lnot r \amp \equiv \lnot (f\land\lnot s) \lor\lnot r \\ \amp \equiv (\lnot f\lor s) \lor\lnot r \\ \amp \equiv (s\lor \lnot f) \lor\lnot r \\ \amp \equiv s\lor (\lnot f \lor\lnot r) \end{align*}

Since both statements are equivalent to \(s\lor (\lnot f \lor\lnot r)\) , the statements are equivalent to each other.

🔗

Prev Top Next