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
Definition2.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.
Statements that are not tautologies or contradictions are called contingencies.
Definition2.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{.}\)
Example2.1.3.
Prove the following are equivalent using a truth table.
Here’s the solution for \((\neg p \to (q \wedge \neg q)) \equiv p\text{:}\)
Table2.1.4.Showing \(( \neg p \to (q \wedge \neg q) )\leftrightarrow p\) is a tautology
\(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.
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!
Example2.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)\)
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.
\((\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).