Definition 2.1.1. Tautologies and Contradictions.
An expression involving logical variables that is true for all values is called a tautology.
An expression involving logical variables that is false for all values is called a contradiction.
Section 2.1 Logical Equivalences
What does it mean for two logical statements to be the same? In this section, we’ll meet the idea of logical equivalence and visit two methods to show two statements are equivalent.
Subsection
Statements that are not tautologies or contradictions are called contingencies.
Aside
Definition 2.1.2. Logical Equivalence.
We say two propositions \(p\) and \(q\) are logically equivalent if \(p \leftrightarrow q\) is a tautology. We denote this by \(p \equiv q\text{.}\)
The first method to show that two statements \(p \and q\) are equivalent is to build a truth table to to find the truth values of \(p \leftrightarrow q\text{.}\)
Aside
Example 2.1.3.
Prove the following are equivalent using a truth table.
-
\(\displaystyle ( \neg p \to (q \wedge \neg q) ) \equiv p\)
-
\(\displaystyle p \vee (p \wedge q) \equiv p \)
-
\(\displaystyle p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)\)
-
\(\displaystyle \neg(p \to q) \equiv p \wedge \neg q\)
-
\(\displaystyle p \to q \equiv \neg p \vee q\)
We use \(p \to q \equiv \neg p \vee q\) often enough that this has a name. We’ll call it implication
Video / Answer.
Solution.
Here’s the solution for \((\neg p \to (q \wedge \neg q)) \equiv p\text{:}\)
| \(p\) | \(q\) | \(\neg p\) | \(q \wedge \neg q\) | \(\neg p \to (q \wedge \neg q)\) | \((\neg p \to (q \wedge \neg q)) \leftrightarrow p\) |
|---|---|---|---|---|---|
| T | T | F | F | T | T |
| T | F | F | F | T | T |
| F | T | T | F | F | T |
| F | F | T | F | F | T |
The following table is a set of core tautologies we will be using for the rest of the course. In the example that follows them, we will show how we can use these existing tautologies (which we’ll call laws) to make conclusions about more complex statements.
Aside
Let \(p, q\) and \(r\) be logical propositions.
- Commutative Laws
-
\(p \lor q\equiv q\lor p\)
\(p \land q\equiv q \land p\) - Associative Laws
-
\((p \lor q) \lor r \equiv p \lor (q \lor r)\)
\((p \land q) \land r\equiv p \land (q \land r)\) - Distributive Laws
-
\(p \land (q \lor r) \equiv (p \land q ) \lor (p \land r)\)
\(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\) - Identity Laws
-
\(p \lor F\equiv p\)
\(p \land T \equiv p\) - Negation Laws
-
\(p\land \neg p\equiv F\)
\(p\lor \neg p\equiv T\) - Idempotent Laws
-
\(p \lor p \equiv p\)
\(p\land p \equiv p\) - Domination Laws
-
\(p \land F \equiv F\)
\(p \lor T \equiv T\) - Absorption Laws
-
\(p \land (p\lor q)\equiv p\)
\(p \lor (p \land q) \equiv p\) - DeMorgan’s Laws
-
\(\neg (p \lor q) \equiv (\neg p) \land (\neg q)\)
\(\neg (p \land q) \equiv (\neg p) \lor (\neg q)\) - Double Negation Law
-
\(\displaystyle \neg (\neg p)\equiv p\)
- Implication
-
\(\displaystyle p \to q \equiv \neg p \lor q\)
You’ll notice that for those laws which have two different forms they look very similar, just with different operations and true and false swapped. Not only does this mean you actually have half as much to memorize, there’s a neat reason for this that we’ll get into when we discuss Boolean Algebras in Discrete 2!
Example 2.1.6.
Use the logical laws from List 2.1.5 to show the following are equivalent.
-
\(\displaystyle p \wedge q \equiv \neg(p \to \neg q)\)
-
\(\displaystyle (p \to r) \vee (q \to r) \equiv (p \wedge q) \to r\)
-
\(\displaystyle q \to p \equiv \neg p \to \neg q\)
-
\(\displaystyle ( \neg p \to (q \wedge \neg q) ) \equiv p\)
Video / Answer.
This is your first experience with logical proof! It won’t be your last. Much of this class is about learning to understand and argue rigorously.
Exercises Exercises
1.
Show that the following are true:
-
The conditional is logically equivalent to its contrapositive: \(p\to q \equiv \neg q \to \neg p\text{.}\)
-
The converse is logically equivalent to the inverse: \(q\to p \equiv \neg p \to \neg q\text{.}\)
Solution.
Make a truth table for these statements.
2.
Determine whether the following two statements are logically equivalent: \(\neg(p \to q)\) and \(p \wedge \neg q\text{.}\) Explain how you know you are correct.
Solution.
Make a truth table for each and compare. The statements are logically equivalent.
3.
Are the statements \(p \to (q\vee r)\) and \((p \to q) \vee (p \to r)\) logically equivalent?
Solution.
Let’s start with the left-hand side and work towards the right to find out.
\begin{align*}
p \to (q \lor r) \amp\equiv \neg p \lor (q \lor r) \amp \text{implication} \\
\amp\equiv \neg p \lor q \lor r \amp \text{associative; drop parens}\\
\amp\equiv \neg p \lor \neg p \lor q \lor r \amp \text{idempotent}\\
\amp\equiv \neg p \lor q \lor \neg p \lor r \amp \text{communitive}\\
\amp\equiv (\neg p \lor q) \lor (\neg p \lor r) \amp \text{associative}\\
\amp\equiv (p \to q) \lor (p \to r) \amp \text{implication}
\end{align*}
which was what we wanted to show.
4.
Use a truth table to show that \((p \to q) \land (p \to r)\) and \(p \to (q \land r)\) are logically equivalent.
Solution.
Here’s an alternative solution using previous equivalences (not a truth table):
\begin{align*}
(p \to q) \land (p \to r) & \equiv (\neg p \lor q) \land (\neg p \lor r) \\
&\equiv \neg p \lor (q \land r)\\
&\equiv p \to (q \land r)
\end{align*}
5.
Simplify the following statements (so that negation only appears right before variables).
-
\(\neg(p \to \neg q)\text{.}\)
-
\((\neg p \vee \neg q) \to \neg (\neg q \wedge r)\text{.}\)
-
\(\neg((p \to \neg q) \vee \neg (r \wedge \neg r))\text{.}\)
Video / Answer.
-
\(p \wedge q\text{.}\)
-
\((\neg p \vee \neg r) \to (q \vee \neg r)\) or, replacing the implication with a disjunction first: \((p \wedge q) \vee (q \vee \neg r)\text{.}\)
-
\((p \wedge q) \wedge (r \wedge \neg r)\text{.}\) This is necessarily false, so it is also equivalent to \(p \wedge \neg p\text{.}\)
6.
Use DeMorgan’s Laws, and any other logical equivalence facts you know to simplify the following statements. Show all your steps. Your final statements should have negations only appear directly next to the sentence variables or predicates (\(p\text{,}\) \(q\text{,}\) etc.), and no double negations. It would be a good idea to use only conjunctions, disjunctions, and negations.
-
\(\neg((\neg p \wedge q) \vee \neg(r \vee \neg s))\text{.}\)
-
\(\neg((\neg p \to \neg q) \wedge (\neg q \to k))\) (careful with the implications).
-
\(\displaystyle (p\land q) \to (p \lor q)\)
Solution.
-
\begin{align*} \neg((\neg p \wedge q) \vee \neg(r \vee \neg s)) \amp\equiv \neg(\neg p \wedge q) \land \neg \neg(r \vee \neg s) \\ \amp\equiv \neg(\neg p \wedge q) \land (r \vee \neg s)\\ \amp\equiv (\neg\neg p \lor \neg q) \land (r \lor \neg s)\\ \amp\equiv (p \lor \neg q) \land (r \lor \neg s) \end{align*}
-
\begin{align*} \neg((\neg p \to \neg q) \wedge (\neg q \to k)) \amp \equiv \neg((\neg \neg p \lor \neg q) \wedge (\neg \neg q \lor k))\\ \amp\equiv \neg((p \lor \neg q) \wedge (q \lor k))\\ \amp \equiv \neg(p \lor \neg q) \lor \neg (q \lor k)\\ \amp \equiv (\neg p \land \neg \neg q) \lor (\neg q \land \neg k)\\ \amp \equiv (\neg p \land q) \lor (\neg q \land \neg k) \end{align*}
-
\begin{align*} (p\land q) \to (p \lor q) \amp \equiv \neg (p\land q) \lor (p \lor q) \\ \amp \equiv (\neg p \lor \neg q) \lor (p \lor q)\\ \amp \equiv \neg p \lor \neg q \lor p \lor q\\ \amp \equiv \neg p \lor p \lor \neg q \lor q\\ \amp \equiv (\neg p \lor p) \lor ( \neg q \lor q )\\ \amp \equiv (T) \lor (T)\\ \amp \equiv T \end{align*}... it’s a tautology!
