Introduction
In propositional logic, different expressions can have the same truth value in all interpretations. These logically equivalent expressions can be transformed into each other using logical laws.
Understanding logical equivalence and normal forms is essential for:
- Simplifying Complex Expressions: Reducing formulas to simpler, equivalent forms
- Automated Reasoning: SAT solvers and theorem provers use normal forms
- Circuit Design: Boolean algebra simplification for hardware design
- Database Queries: Optimizing logical conditions in SQL
- Software Verification: Proving program correctness
This comprehensive guide explores logical equivalence, normal forms, and practical techniques for transforming logical expressions.
Logical Equivalence
Definition
Two formulas are logically equivalent if they have the same truth value in every possible interpretation.
Notation: A ≡ B or A ⇔ B
Formal Definition:
Formulas A and B are logically equivalent if and only if for every interpretation I:
truth_value(A, I) = truth_value(B, I)
Verifying Equivalence with Truth Tables
Method: Create truth tables for both formulas and compare the final columns.
Example: Verify that p → q ≡ ¬p ∨ q
Truth Table:
| p | q | p → q | ¬p | ¬p ∨ q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
The columns for p → q and ¬p ∨ q are identical, confirming equivalence.
Why Equivalence Matters
Simplification: Replace complex expressions with simpler equivalent ones.
Optimization: Reduce the number of operations needed.
Verification: Prove that different formulations are equivalent.
Transformation: Convert between different forms (e.g., CNF to DNF).
Fundamental Logical Laws
Identity Laws
Definition: Identity laws describe how formulas interact with true and false.
p ∧ T ≡ p (true is the identity for AND)
p ∨ F ≡ p (false is the identity for OR)
Intuition:
- “p AND true” is true exactly when p is true
- “p OR false” is true exactly when p is true
Example:
(x > 5) ∧ T ≡ (x > 5)
(x > 5) ∨ F ≡ (x > 5)
Domination Laws
Definition: Domination laws describe how true and false dominate operations.
p ∨ T ≡ T (true dominates OR)
p ∧ F ≡ F (false dominates AND)
Intuition:
- “p OR true” is always true
- “p AND false” is always false
Example:
(x > 5) ∨ T ≡ T
(x > 5) ∧ F ≡ F
Idempotent Laws
Definition: Idempotent laws describe how formulas combine with themselves.
p ∨ p ≡ p
p ∧ p ≡ p
Intuition:
- “p OR p” is true exactly when p is true
- “p AND p” is true exactly when p is true
Example:
(x > 5) ∨ (x > 5) ≡ (x > 5)
(x > 5) ∧ (x > 5) ≡ (x > 5)
Double Negation Law
Definition: Negating a negation returns to the original.
¬(¬p) ≡ p
Intuition: “Not not p” is the same as “p”
Example:
¬(¬(x > 5)) ≡ (x > 5)
Commutative Laws
Definition: Commutative laws state that order doesn’t matter.
p ∨ q ≡ q ∨ p (OR is commutative)
p ∧ q ≡ q ∧ p (AND is commutative)
Intuition: “p OR q” is the same as “q OR p”
Example:
(x > 5) ∨ (y < 3) ≡ (y < 3) ∨ (x > 5)
(x > 5) ∧ (y < 3) ≡ (y < 3) ∧ (x > 5)
Associative Laws
Definition: Associative laws state that grouping doesn’t matter.
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (OR is associative)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (AND is associative)
Intuition: “p OR q OR r” is the same regardless of how we group them
Example:
((x > 5) ∨ (y < 3)) ∨ (z = 0) ≡ (x > 5) ∨ ((y < 3) ∨ (z = 0))
Distributive Laws
Definition: Distributive laws describe how AND and OR distribute over each other.
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (AND distributes over OR)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (OR distributes over AND)
Intuition: “p AND (q OR r)” is the same as “(p AND q) OR (p AND r)”
Example:
(x > 5) ∧ ((y < 3) ∨ (z = 0))
≡ ((x > 5) ∧ (y < 3)) ∨ ((x > 5) ∧ (z = 0))
De Morgan’s Laws
Definition: De Morgan’s laws describe how negation distributes over AND and OR.
¬(p ∧ q) ≡ ¬p ∨ ¬q (negation of AND is OR of negations)
¬(p ∨ q) ≡ ¬p ∧ ¬q (negation of OR is AND of negations)
Intuition:
- “Not (p AND q)” is the same as “not p OR not q”
- “Not (p OR q)” is the same as “not p AND not q”
Examples:
¬((x > 5) ∧ (y < 3)) ≡ ¬(x > 5) ∨ ¬(y < 3)
≡ (x ≤ 5) ∨ (y ≥ 3)
¬((x > 5) ∨ (y < 3)) ≡ ¬(x > 5) ∧ ¬(y < 3)
≡ (x ≤ 5) ∧ (y ≥ 3)
Practical Application: De Morgan’s laws are crucial for simplifying negated expressions.
Absorption Laws
Definition: Absorption laws describe how formulas can absorb others.
p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p
Intuition:
- “p OR (p AND q)” is true exactly when p is true
- “p AND (p OR q)” is true exactly when p is true
Example:
(x > 5) ∨ ((x > 5) ∧ (y < 3)) ≡ (x > 5)
Negation Laws
Definition: Negation laws describe how formulas interact with their negations.
p ∨ ¬p ≡ T (Law of Excluded Middle)
p ∧ ¬p ≡ F (Law of Non-Contradiction)
Intuition:
- “p OR not p” is always true
- “p AND not p” is always false
Example:
(x > 5) ∨ ¬(x > 5) ≡ T
(x > 5) ∧ ¬(x > 5) ≡ F
Implication Laws
Definition: Implication laws describe how implications relate to other operators.
p → q ≡ ¬p ∨ q (implication as disjunction)
p → q ≡ ¬q → ¬p (contrapositive equivalence)
¬(p → q) ≡ p ∧ ¬q (negation of implication)
Intuition:
- “If p then q” is the same as “not p OR q”
- “If p then q” is the same as “if not q then not p”
Example:
(x > 5) → (y < 3) ≡ ¬(x > 5) ∨ (y < 3)
≡ (x ≤ 5) ∨ (y < 3)
Biconditional Laws
Definition: Biconditional laws describe how biconditionals relate to other operators.
p ↔ q ≡ (p → q) ∧ (q → p) (biconditional as two implications)
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) (biconditional as same truth values)
Intuition:
- “p if and only if q” means “if p then q” AND “if q then p”
- “p if and only if q” means “both true or both false”
Example:
(x > 5) ↔ (y < 3) ≡ ((x > 5) → (y < 3)) ∧ ((y < 3) → (x > 5))
Simplifying Expressions
Step-by-Step Simplification
Strategy: Apply logical laws to reduce complexity.
Example 1: Simplify ¬(p ∨ ¬q) ∨ (¬p ∧ ¬q)
¬(p ∨ ¬q) ∨ (¬p ∧ ¬q)
≡ (¬p ∧ ¬(¬q)) ∨ (¬p ∧ ¬q) [De Morgan's Law]
≡ (¬p ∧ q) ∨ (¬p ∧ ¬q) [Double Negation]
≡ ¬p ∧ (q ∨ ¬q) [Distributive Law]
≡ ¬p ∧ T [Excluded Middle]
≡ ¬p [Identity Law]
Example 2: Simplify (p ∧ q) ∨ (p ∧ ¬q)
(p ∧ q) ∨ (p ∧ ¬q)
≡ p ∧ (q ∨ ¬q) [Distributive Law]
≡ p ∧ T [Excluded Middle]
≡ p [Identity Law]
Example 3: Simplify ¬(¬p ∧ q) ∧ (p ∨ ¬q)
¬(¬p ∧ q) ∧ (p ∨ ¬q)
≡ (¬(¬p) ∨ ¬q) ∧ (p ∨ ¬q) [De Morgan's Law]
≡ (p ∨ ¬q) ∧ (p ∨ ¬q) [Double Negation]
≡ p ∨ ¬q [Idempotent Law]
Normal Forms
Conjunctive Normal Form (CNF)
Definition: A formula is in CNF if it is a conjunction (AND) of disjunctions (OR).
General Form:
(L₁ ∨ L₂ ∨ ... ∨ Lₙ) ∧ (M₁ ∨ M₂ ∨ ... ∨ Mₘ) ∧ ...
where each L, M, etc. is a literal (a variable or its negation).
Examples:
(p ∨ q ∨ r) ∧ (¬p ∨ s) ∧ (q ∨ ¬s ∨ t)
(p ∨ ¬q) ∧ (¬p ∨ q)
p ∧ q ∧ r
Advantages:
- Used by SAT solvers
- Useful for automated reasoning
- Can be converted from any formula
Conversion to CNF:
Step 1: Eliminate implications using p → q ≡ ¬p ∨ q
Step 2: Apply De Morgan’s laws to move negations inward
Step 3: Apply distributive laws to move ORs inside ANDs
Example Conversion:
Original: (p → q) ∧ (r → s)
Step 1: (¬p ∨ q) ∧ (¬r ∨ s) [Eliminate implications]
Result: Already in CNF
More Complex Example:
Original: p → (q ∧ r)
Step 1: ¬p ∨ (q ∧ r) [Eliminate implication]
Result: Already in CNF (disjunction of literals and a conjunction)
Disjunctive Normal Form (DNF)
Definition: A formula is in DNF if it is a disjunction (OR) of conjunctions (AND).
General Form:
(L₁ ∧ L₂ ∧ ... ∧ Lₙ) ∨ (M₁ ∧ M₂ ∧ ... ∧ Mₘ) ∨ ...
where each L, M, etc. is a literal.
Examples:
(p ∧ q ∧ r) ∨ (¬p ∧ s) ∨ (q ∧ ¬s ∧ t)
(p ∧ ¬q) ∨ (¬p ∧ q)
p ∨ q ∨ r
Advantages:
- Can be read directly from truth tables
- Useful for understanding when a formula is true
- Each disjunct represents a row where the formula is true
Conversion to DNF:
Step 1: Eliminate implications
Step 2: Apply De Morgan’s laws to move negations inward
Step 3: Apply distributive laws to move ANDs inside ORs
Example Conversion:
Original: (p ∨ q) ∧ r
Step 1: (p ∧ r) ∨ (q ∧ r) [Distributive law]
Result: Already in DNF
Converting Between CNF and DNF
From Truth Table to DNF:
- Identify all rows where the formula is true
- For each true row, create a conjunction of literals
- Combine all conjunctions with OR
Example:
Truth table for (p ∧ q) ∨ r:
| p | q | r | (p ∧ q) ∨ r |
|---|---|---|---|
| T | T | T | T |
| T | T | F | T |
| T | F | T | T |
| T | F | F | F |
| F | T | T | T |
| F | T | F | F |
| F | F | T | T |
| F | F | F | F |
True rows: 1, 2, 3, 5, 7
DNF:
(p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ r)
This can be simplified to: (p ∧ q) ∨ r
Applications of Equivalence and Normal Forms
Circuit Design
Boolean algebra simplification is used to design efficient circuits.
Example: Simplify (A ∧ B) ∨ (A ∧ ¬B)
(A ∧ B) ∨ (A ∧ ¬B)
≡ A ∧ (B ∨ ¬B) [Distributive Law]
≡ A ∧ T [Excluded Middle]
≡ A [Identity Law]
This reduces a two-input circuit to a single wire.
Database Query Optimization
SQL queries use logical conditions that can be optimized.
Example: Optimize WHERE clause
Original: WHERE (age > 18 AND status = 'active') OR (age > 18 AND status = 'pending')
Simplified: WHERE age > 18 AND (status = 'active' OR status = 'pending')
SAT Solving
SAT solvers convert formulas to CNF and use algorithms to find satisfying assignments.
Example: Convert to CNF for SAT solver
Original: (p → q) ∧ (q → r) ∧ (r → s)
CNF: (¬p ∨ q) ∧ (¬q ∨ r) ∧ (¬r ∨ s)
Practice Problems
Problem 1: Verify Equivalence
Verify that (p ∧ q) ∨ (¬p ∧ ¬q) ≡ p ↔ q
Solution: Create truth tables for both sides and compare.
| p | q | p ∧ q | ¬p | ¬q | ¬p ∧ ¬q | (p ∧ q) ∨ (¬p ∧ ¬q) | p ↔ q |
|---|---|---|---|---|---|---|---|
| T | T | T | F | F | F | T | T |
| T | F | F | F | T | F | F | F |
| F | T | F | T | F | F | F | F |
| F | F | F | T | T | T | T | T |
Both columns are identical, confirming equivalence.
Problem 2: Simplify Expression
Simplify: ¬(p ∧ ¬q) ∨ (¬p ∧ q)
Solution:
¬(p ∧ ¬q) ∨ (¬p ∧ q)
≡ (¬p ∨ ¬(¬q)) ∨ (¬p ∧ q) [De Morgan's Law]
≡ (¬p ∨ q) ∨ (¬p ∧ q) [Double Negation]
≡ ¬p ∨ q [Absorption Law]
Problem 3: Convert to CNF
Convert (p ∨ q) → r to CNF
Solution:
(p ∨ q) → r
≡ ¬(p ∨ q) ∨ r [Implication law]
≡ (¬p ∧ ¬q) ∨ r [De Morgan's Law]
≡ (¬p ∨ r) ∧ (¬q ∨ r) [Distributive Law]
Result: (¬p ∨ r) ∧ (¬q ∨ r)
Problem 4: Convert to DNF
Convert (p → q) ∧ (q → r) to DNF
Solution:
(p → q) ∧ (q → r)
≡ (¬p ∨ q) ∧ (¬q ∨ r) [Implication law]
≡ ((¬p ∨ q) ∧ ¬q) ∨ ((¬p ∨ q) ∧ r) [Distributive Law]
≡ ((¬p ∧ ¬q) ∨ (q ∧ ¬q)) ∨ ((¬p ∧ r) ∨ (q ∧ r)) [Distributive Law]
≡ ((¬p ∧ ¬q) ∨ F) ∨ ((¬p ∧ r) ∨ (q ∧ r)) [Negation Law]
≡ (¬p ∧ ¬q) ∨ (¬p ∧ r) ∨ (q ∧ r) [Identity Law]
Result: (¬p ∧ ¬q) ∨ (¬p ∧ r) ∨ (q ∧ r)
Related Resources and Tools
Online Learning Platforms
- Stanford Encyclopedia of Philosophy - Logical Equivalence - Academic treatment
- Khan Academy - Boolean Algebra - Video tutorials
- Coursera - Mathematical Logic - University course
- MIT OpenCourseWare - Mathematics for Computer Science - Free materials
Interactive Tools
- Boolean Algebra Simplifier - Boolean Algebra Calculator - Simplify expressions
- Truth Table Generator - Stanford Tool - Create truth tables
- CNF/DNF Converter - Logic Converter - Convert between forms
- Logic Simulator - LogicSim - Visual circuit design
Recommended Books
- “Introduction to Logic” by Irving M. Copi and Carl Cohen - Classic textbook
- “A Concise Introduction to Logic” by Patrick J. Hurley - Accessible introduction
- “Logic: The Laws of Truth” by Nicholas J.J. Smith - Modern treatment
- “forall x: An Introduction to Formal Logic” by P.D. Magnus - Free online textbook
Academic Journals
- Journal of Symbolic Logic - Leading journal on mathematical logic
- Studia Logica - International journal on logic and philosophy
- Logic and Logical Philosophy - Open access journal
Software Tools
- Prolog - Logic programming language
- Z3 - SMT solver
- Python - For implementing simplification algorithms
Glossary of Key Terms
- Absorption: Law where p ∨ (p ∧ q) ≡ p
- Biconditional: “If and only if” operator (↔)
- CNF: Conjunction of disjunctions
- Conjunction: “And” operator (∧)
- De Morgan’s Laws: Laws for distributing negation
- Disjunction: “Or” operator (∨)
- DNF: Disjunction of conjunctions
- Distributive Law: Law for distributing operators
- Equivalence: Two formulas with identical truth values
- Literal: A variable or its negation
- Normal Form: Standardized form of a formula
- Simplification: Reducing formula complexity
Conclusion
Logical equivalence and normal forms are powerful tools for:
- Simplifying complex expressions
- Transforming formulas between different representations
- Optimizing circuits and queries
- Automating reasoning processes
By mastering the fundamental logical laws and normal forms, you develop the ability to:
- Recognize equivalent expressions
- Simplify formulas systematically
- Convert between CNF and DNF
- Optimize logical conditions
- Understand automated reasoning systems
The next article in this series will explore Inference Rules and Modus Ponens, diving into the rules for deriving new conclusions from premises.
Which logical law do you find most useful? Have you used normal forms in your work? Share your experiences in the comments below!
Comments