Logical Equivalence: Proving Identities

1. What is Logical Equivalence?

In a previous lesson, we saw that two propositions are logically equivalent if they have identical truth tables. This is the semantic definition. Formally, we say that propositions $r$ and $s$ are logically equivalent if the biconditional statement $r\leftrightarrow s$ is a tautology (i.e., always true).

While we could prove equivalence by constructing a full truth table or by performing two separate natural deduction proofs (showing $r⊢s$ and $s⊢r$), a third, more direct method exists. We can use a pre-established set of equivalences, known as logical laws, to manipulate an expression step-by-step until it becomes the expression we are targeting. This syntactic manipulation is the focus of today's lesson.

Dr. Trefor Bazett gives a quick overview of these three methods. We have already covered truth tables, and today we will be focusing on his third method.

2. The Toolkit: Fundamental Logical Laws

To effectively manipulate logical expressions, we need a toolkit of established laws. These laws function like axioms or proven theorems in mathematics. We'll explore the most important ones, many of which will feel familiar from algebra and set theory.

The following video provides an excellent survey of these laws. We will go through it in sections.

Let's summarize the first set of laws:

• Identity Laws: $p\wedge T\equiv p$, $p\vee F\equiv p$. Adding a known truth or a known falsehood in specific ways doesn't change the original proposition's value.
• Domination Laws: $p\vee T\equiv T$, $p\wedge F\equiv F$. A known truth "dominates" a disjunction, and a known falsehood dominates a conjunction.

Now, let's continue with some of the most powerful and frequently used laws.

De Morgan's Laws are worth re-emphasizing, as they are fundamental to manipulating negated expressions. They essentially describe how to distribute a negation inward across a conjunction or disjunction:

1. $\neg (p\wedge q)\equiv \neg p\vee \neg q$
2. $\neg (p\vee q)\equiv \neg p\wedge \neg q$

In essence: to negate a conjunction/disjunction, you negate each component and flip the connective. Your experience with set theory may bring to mind the analogous rule for complements of unions and intersections: $(A\cup B{)}^c=A^c\cap B^c$.

For your reference, here is a complete table of the most important logical equivalences from a set of lecture notes. It is useful to have this open as you work through proofs.

3. Proofs by Transformation

Now, let's use this toolkit to prove equivalence. The process involves starting with one side of the equivalence and applying the laws sequentially, providing a justification for each step, until you have transformed it into the other side.

The TrevTutor video concludes with a clear, step-by-step example of this process.

Let's work through another example to solidify the method. We will prove that $\neg (p\vee (\neg p\wedge q))\equiv \neg p\wedge \neg q$. This is the kind of simplification that is common in logic design for digital circuits.

Proof:

Each step is a direct substitution based on a known law. This transforms the complex initial statement into a much simpler, equivalent form. You can find this exact proof laid out in the lecture notes from the University at Buffalo (resource LINK, page 28) for comparison.

4. The Equivalence of Contraposition

A particularly important equivalence in philosophical and mathematical arguments is contraposition. The contrapositive of an implication $p\to q$ is $\neg q\to \neg p$. Let's prove they are logically equivalent using our laws.

Proof of Contraposition: $p\to q\equiv \neg q\to \neg p$

We start with the left-hand side:

This elegant proof demonstrates how the fundamental laws interlock. By first converting the implication to a disjunction, we can manipulate it and then convert it back into a new, equivalent implication. Recognizing the contrapositive equivalence allows you to instantly rephrase a conditional statement into a potentially more useful form during an argument.

Another crucial equivalence relates to the negation of an implication:
$\neg (p\to q)\equiv p\wedge \neg q$
This shows that the only way for an "if-then" statement to be false is for the "if" part (antecedent) to be true and the "then" part (consequent) to be false. This is demonstrated in Example 2.4.1 in the Florida State University notes (LINK).

Conclusion

In this lesson, you have added a new method to your logical toolkit: proving logical equivalence by syntactic transformation. Rather than relying on cumbersome truth tables, you can now use a set of powerful logical laws to simplify and manipulate expressions, similar to how you would work with algebraic formulas.

Key Takeaways:

• Two propositions are logically equivalent if they are interchangeable, meaning their biconditional is a tautology.
• We can demonstrate equivalence by starting with one proposition and applying logical laws step-by-step to transform it into the other.
• De Morgan's Laws, the Distributive Laws, and the Conditional Law ($p\to q\equiv \neg p\vee q$) are among the most powerful tools for these transformations.
• Important equivalences like contraposition ($p\to q\equiv \neg q\to \neg p$) can be derived from more basic laws.

Preview of the Next Lesson:

We have now established a robust framework for reasoning about propositions. However, propositional logic has its limits. It treats sentences like "Socrates is human" as indivisible atoms (P) and cannot capture the internal structure of statements involving properties, objects, and quantities. For instance, we cannot express "All humans are mortal."

In our next lesson, we will move to first-order predicate logic. By introducing predicates, variables, and quantifiers (like "for all" $\forall$ and "there exists" $\exists$), we will unlock a much richer and more expressive logical language, capable of formalizing the vast majority of mathematical and philosophical arguments.