Course contentsShow
← Computer Science
Lesson 40 of 2,8722. Discrete Mathematics for CSFree lesson

Logical Equivalence

Master the concept of equivalent propositions and learn to prove equivalence using truth tables.

Logical Equivalence

What you'll learn: You'll discover how to recognize when two different-looking logical statements always produce identical truth values, making them logically equivalent.

What Is Logical Equivalence?

Two propositions are logically equivalent if they have the same truth value in every possible situation. Think of them as different routes to the same destination—no matter what inputs you start with, both propositions end up at the same true/false conclusion.

We write this using the symbol ≡. For example, if proposition p ≡ q, then p and q are logically equivalent.

Why Does This Matter?

Just like in algebra where 2(x + 3) equals 2x + 6, logical statements can look different but mean the same thing. Recognizing equivalence lets you:

  • Simplify complex logical expressions
  • Verify that different circuits or programs produce identical results
  • Prove mathematical statements in multiple ways

Proving Equivalence with Truth Tables

The most straightforward way to prove two propositions are equivalent is to build truth tables for both and compare their final columns. If every row matches, they're equivalent.

Example: Are ¬(p ∧ q) and ¬p ∨ ¬q equivalent? (This is De Morgan's Law!)

pqp ∧ q¬(p ∧ q)¬p¬q¬p ∨ ¬q
TTTFFFF
TFFTFTT
FTFTTFT
FFFTTTT

The columns for ¬(p ∧ q) and ¬p ∨ ¬q match perfectly—they're equivalent!

Key Takeaway: Two propositions are logically equivalent if their truth tables produce identical results for all possible combinations of truth values.