Skip to main content
⚡ Calmops
🤖 AI 🏗️ Architecture 🌐 Web 🗃️ Database ⚙️ DevOps 🌍 Network 💻 Programming 🧮 Algorithms 📐 Software Eng. ☁️ Cloud 🔒 Security 📈 Finance More →

Predicate Logic Equivalences

Created: December 20, 2025 9 min read

Introduction

Predicate logic equivalences are fundamental transformations that allow us to rewrite formulas in different forms while preserving their logical meaning. These equivalences are essential for:

  • Simplifying complex formulas
  • Converting formulas to normal forms
  • Proving logical theorems
  • Understanding logical relationships
  • Optimizing logical queries

In this article, we’ll explore the major equivalences in predicate logic and learn how to apply them.

Basic Equivalences

Definition of Equivalence

Two formulas are logically equivalent if they have the same truth value under all possible interpretations.

Notation: P ≡ Q (P is equivalent to Q)

Example:

∀x P(x) ≡ ∀x P(x)  (reflexivity)
∀x P(x) ≡ ∀y P(y)  (variable renaming)
¬∀x P(x) ≡ ∃x ¬P(x)  (De Morgan's law)

Quantifier Equivalences

De Morgan’s Laws for Quantifiers

De Morgan’s laws show how negation interacts with quantifiers.

Law 1: Negation of Universal Quantifier

¬∀x P(x) ≡ ∃x ¬P(x)

English: "It's not the case that all x satisfy P"
is equivalent to
"There exists an x that does not satisfy P"

Example:
¬∀x (student(x) → studies(x))
≡ ∃x ¬(student(x) → studies(x))
≡ ∃x (student(x) ∧ ¬studies(x))
"It's not the case that all students study"
≡ "There exists a student who doesn't study"

Law 2: Negation of Existential Quantifier

¬∃x P(x) ≡ ∀x ¬P(x)

English: "It's not the case that some x satisfies P"
is equivalent to
"All x do not satisfy P"

Example:
¬∃x (student(x) ∧ studies(x, logic))
≡ ∀x ¬(student(x) ∧ studies(x, logic))
≡ ∀x (¬student(x) ∨ ¬studies(x, logic))
"It's not the case that some student studies logic"
≡ "No student studies logic"

Quantifier Distribution

Quantifiers distribute over certain logical connectives.

Distribution over Conjunction (Universal)

∀x (P(x) ∧ Q(x)) ≡ ∀x P(x) ∧ ∀x Q(x)

English: "All x satisfy both P and Q"
is equivalent to
"All x satisfy P, and all x satisfy Q"

Example:
∀x (student(x) ∧ studies(x))
≡ ∀x student(x) ∧ ∀x studies(x)
"All are students and all study"
≡ "All are students, and all study"

Distribution over Disjunction (Existential)

∃x (P(x) ∨ Q(x)) ≡ ∃x P(x) ∨ ∃x Q(x)

English: "There exists an x that satisfies P or Q"
is equivalent to
"There exists an x that satisfies P, or there exists an x that satisfies Q"

Example:
∃x (student(x) ∨ teacher(x))
≡ ∃x student(x) ∨ ∃x teacher(x)
"Someone is a student or a teacher"
≡ "Someone is a student, or someone is a teacher"

Non-Distribution Cases

∀x (P(x) ∨ Q(x)) ≢ ∀x P(x) ∨ ∀x Q(x)

Example:
∀x (student(x) ∨ teacher(x))
"Everyone is either a student or a teacher"
≢ ∀x student(x) ∨ ∀x teacher(x)
"Everyone is a student, or everyone is a teacher"

The first is true if each person is one or the other.
The second is true only if everyone is the same role.

∃x (P(x) ∧ Q(x)) ≢ ∃x P(x) ∧ ∃x Q(x)

Example:
∃x (student(x) ∧ studies(x, logic))
"Someone is a student and studies logic"
≢ ∃x student(x) ∧ ∃x studies(x, logic)
"Someone is a student, and someone studies logic"

The first requires one person to be both.
The second allows different people.

Quantifier Commutativity

Multiple quantifiers of the same type commute.

Universal Commutativity

∀x ∀y P(x, y) ≡ ∀y ∀x P(x, y)

English: "For all x and for all y, P(x, y)"
is equivalent to
"For all y and for all x, P(x, y)"

Example:
∀x ∀y (parent(x, y) → ancestor(x, y))
≡ ∀y ∀x (parent(x, y) → ancestor(x, y))

Existential Commutativity

∃x ∃y P(x, y) ≡ ∃y ∃x P(x, y)

English: "There exist x and y such that P(x, y)"
is equivalent to
"There exist y and x such that P(x, y)"

Example:
∃x ∃y (parent(x, y) ∧ sibling(x, y))
≡ ∃y ∃x (parent(x, y) ∧ sibling(x, y))

Mixed Quantifiers Do NOT Commute

∀x ∃y P(x, y) ≢ ∃y ∀x P(x, y)

Example:
∀x ∃y (parent(x, y))
"Everyone has a parent"
≢ ∃y ∀x (parent(x, y))
"There is someone who is everyone's parent"

The first is true (each person has parents).
The second is false (no one is everyone's parent).

Logical Connective Equivalences

Implication Equivalences

Implication as Disjunction

P → Q ≡ ¬P ∨ Q

Example:
student(x) → studies(x)
≡ ¬student(x) ∨ studies(x)
"If x is a student, then x studies"
≡ "x is not a student, or x studies"

Contrapositive

P → Q ≡ ¬Q → ¬P

Example:
student(x) → studies(x)
≡ ¬studies(x) → ¬student(x)
"If x is a student, then x studies"
≡ "If x doesn't study, then x is not a student"

Implication with Quantifiers

∀x (P(x) → Q(x)) ≡ ∀x (¬P(x) ∨ Q(x))

Example:
∀x (student(x) → studies(x))
≡ ∀x (¬student(x) ∨ studies(x))
"All students study"
≡ "For all x, x is not a student or x studies"

Biconditional Equivalences

Biconditional as Conjunction of Implications

P ↔ Q ≡ (P → Q) ∧ (Q → P)

Example:
student(x) ↔ studies(x)
≡ (student(x) → studies(x)) ∧ (studies(x) → student(x))
"x is a student if and only if x studies"
≡ "If x is a student then x studies, and if x studies then x is a student"

Biconditional as Equivalence of Truth Values

P ↔ Q ≡ (P ∧ Q) ∨ (¬P ∧ ¬Q)

Example:
student(x) ↔ studies(x)
≡ (student(x) ∧ studies(x)) ∨ (¬student(x) ∧ ¬studies(x))
"x is a student if and only if x studies"
≡ "Either x is a student and studies, or x is not a student and doesn't study"

Scope and Binding Equivalences

Variable Renaming (Alpha-Conversion)

Renaming bound variables doesn’t change meaning.

∀x P(x) ≡ ∀y P(y)
∃x Q(x) ≡ ∃z Q(z)

Example:
∀x (student(x) → studies(x))
≡ ∀y (student(y) → studies(y))
≡ ∀z (student(z) → studies(z))

Important: Only bound variables can be renamed. Free variables cannot be renamed.

∀x P(x, y) ≢ ∀x P(x, z)
(y and z are free, so renaming changes meaning)

Scope Equivalences

Quantifier Scope Extension

∀x (P(x) ∧ Q) ≡ (∀x P(x)) ∧ Q  (if Q has no free x)

Example:
∀x (student(x) ∧ important(logic))
≡ (∀x student(x)) ∧ important(logic)
"All are students and logic is important"
≡ "All are students, and logic is important"

Quantifier Scope Contraction

(∀x P(x)) ∧ Q ≡ ∀x (P(x) ∧ Q)  (if Q has no free x)

Example:
(∀x studies(x)) ∧ important(logic)
≡ ∀x (studies(x) ∧ important(logic))
"All study, and logic is important"
≡ "For all x, x studies and logic is important"

Prenex Normal Form

Prenex normal form is a standard form where all quantifiers appear at the beginning of a formula.

Definition: A formula is in prenex normal form if it has the form:

Q₁x₁ Q₂x₂ ... Qₙxₙ P(x₁, x₂, ..., xₙ)

where each Qᵢ is either ∀ or ∃, and P is a formula with no quantifiers.

Converting to Prenex Normal Form

Step 1: Eliminate Implications

P → Q ≡ ¬P ∨ Q

Step 2: Move Negations Inward

¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
¬(P ∨ Q) ≡ ¬P ∧ ¬Q

Step 3: Move Quantifiers Outward

∀x P(x) ∨ Q ≡ ∀x (P(x) ∨ Q)  (if Q has no free x)
∃x P(x) ∧ Q ≡ ∃x (P(x) ∧ Q)  (if Q has no free x)

Step 4: Rename Variables if Needed

∀x P(x) ∨ ∃x Q(x) ≡ ∀x (P(x) ∨ ∃y Q(y))
(Rename to avoid variable capture)

Example: Converting to Prenex Normal Form

Original: ∀x (P(x) → ∃y Q(x, y))

Step 1: Eliminate implication
∀x (¬P(x) ∨ ∃y Q(x, y))

Step 2: Move negation inward (already done)

Step 3: Move quantifiers outward
∀x ∃y (¬P(x) ∨ Q(x, y))

Result: ∀x ∃y (¬P(x) ∨ Q(x, y))
(Already in prenex normal form)

Example: Complex Conversion

Original: (∀x P(x)) ∨ (∃y Q(y))

Step 1: Eliminate implication (none)

Step 2: Move negation inward (none)

Step 3: Move quantifiers outward
∀x (P(x) ∨ ∃y Q(y))
∀x ∃y (P(x) ∨ Q(y))

Result: ∀x ∃y (P(x) ∨ Q(y))

Practical Applications

Simplifying Formulas

Use equivalences to simplify complex formulas.

Example 1:

¬∀x (student(x) → studies(x))
≡ ∃x ¬(student(x) → studies(x))  (De Morgan)
≡ ∃x (student(x) ∧ ¬studies(x))  (Implication)
"There exists a student who doesn't study"

Example 2:

∀x (P(x) ∨ Q(x)) ∧ ∀x (¬P(x) ∨ R(x))
≡ ∀x ((P(x) ∨ Q(x)) ∧ (¬P(x) ∨ R(x)))  (Scope)
≡ ∀x ((P(x) ∧ ¬P(x)) ∨ (P(x) ∧ R(x)) ∨ (Q(x) ∧ ¬P(x)) ∨ (Q(x) ∧ R(x)))  (Distribution)
≡ ∀x (⊥ ∨ (P(x) ∧ R(x)) ∨ (Q(x) ∧ ¬P(x)) ∨ (Q(x) ∧ R(x)))  (Contradiction)
≡ ∀x ((P(x) ∧ R(x)) ∨ (Q(x) ∧ ¬P(x)) ∨ (Q(x) ∧ R(x)))  (Identity)

Converting Between Equivalent Forms

Use equivalences to convert between different representations.

Example:

"All students study"
∀x (student(x) → studies(x))

Equivalent forms:
≡ ∀x (¬student(x) ∨ studies(x))  (Implication)
≡ ¬∃x (student(x) ∧ ¬studies(x))  (De Morgan)
"It's not the case that some student doesn't study"

Glossary

  • Logical equivalence: Two formulas have the same truth value under all interpretations
  • De Morgan’s laws: Laws relating negation and quantifiers
  • Distribution: Spreading a connective over another connective
  • Commutativity: Order doesn’t matter for certain operations
  • Contrapositive: P → Q is equivalent to ¬Q → ¬P
  • Biconditional: P ↔ Q means P and Q have the same truth value
  • Prenex normal form: All quantifiers at the beginning of a formula
  • Variable renaming: Renaming bound variables (alpha-conversion)
  • Scope: The range over which a quantifier applies

Practice Problems

Problem 1: De Morgan’s Laws

Apply De Morgan’s laws to negate:

  1. ∀x P(x)
  2. ∃x Q(x)
  3. ∀x (student(x) → studies(x))

Solution:

  1. ¬∀x P(x) ≡ ∃x ¬P(x)
  2. ¬∃x Q(x) ≡ ∀x ¬Q(x)
  3. ¬∀x (student(x) → studies(x)) ≡ ∃x (student(x) ∧ ¬studies(x))

Problem 2: Quantifier Distribution

Determine if these are equivalent:

  1. ∀x (P(x) ∧ Q(x)) and ∀x P(x) ∧ ∀x Q(x)
  2. ∃x (P(x) ∨ Q(x)) and ∃x P(x) ∨ ∃x Q(x)
  3. ∀x (P(x) ∨ Q(x)) and ∀x P(x) ∨ ∀x Q(x)

Solution:

  1. ✓ Equivalent
  2. ✓ Equivalent
  3. ✗ Not equivalent

Problem 3: Prenex Normal Form

Convert to prenex normal form:

  1. ∀x P(x) ∨ ∃y Q(y)
  2. (∃x P(x)) → (∀y Q(y))

Solution:

  1. ∀x ∃y (P(x) ∨ Q(y))
  2. ∀x ∃y (¬P(x) ∨ Q(y))

Problem 4: Simplification

Simplify:

  1. ¬∃x (student(x) ∧ studies(x, logic))
  2. ∀x (P(x) → Q(x)) ≡ ?

Solution:

  1. ∀x (¬student(x) ∨ ¬studies(x, logic)) “No student studies logic”
  2. ∀x (¬P(x) ∨ Q(x))

Online Platforms

Interactive Tools

  • “Language, Proof, and Logic” by Barwise & Etchemendy - Equivalences
  • “Introduction to Logic” by Hurley - Comprehensive coverage
  • “Symbolic Logic” by Lewis & Langford - Classic text
  • “Logic: The Basics” by Priest - Accessible introduction
  • “Formal Semantics” by Heim & Kratzer - Advanced topics

Academic Journals

Software Tools

Conclusion

Predicate logic equivalences are powerful tools for:

  • Transforming formulas into equivalent forms
  • Simplifying complex expressions
  • Converting to standard forms like prenex normal form
  • Understanding logical relationships
  • Proving logical theorems

Mastering these equivalences enables you to work effectively with predicate logic and understand the deep structure of logical formulas.

Previous Article: Scope and Variable Binding

Comments