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

Introduction to Predicate Logic: Beyond Propositions

Created: December 19, 2025 9 min read

Introduction

Predicate logic (also called first-order logic) extends propositional logic to handle statements about properties and relationships. While propositional logic can express “It is raining,” predicate logic can express “All humans are mortal” and “There exists a prime number greater than 100.”

Understanding predicate logic is essential for:

  • Mathematics: Expressing mathematical theorems and proofs
  • Computer Science: Database queries, logic programming, formal verification
  • Artificial Intelligence: Knowledge representation and reasoning
  • Philosophy: Analyzing complex philosophical arguments
  • Formal Verification: Proving software and hardware correctness

This comprehensive guide introduces predicate logic, its syntax, semantics, and applications.

Limitations of Propositional Logic

What Propositional Logic Can Express

Propositional logic can express:

  • “It is raining” (p)
  • “It is raining AND the ground is wet” (p ∧ q)
  • “If it rains, the ground gets wet” (p → q)

What Propositional Logic Cannot Express

Propositional logic cannot express:

  • “All humans are mortal”
  • “Some birds can fly”
  • “There exists a prime number greater than 100”
  • “For every x, if x is human, then x is mortal”

Why? Propositional logic treats propositions as atomic units. It cannot express:

  • Quantification: “all,” “some,” “there exists”
  • Properties: “is human,” “is mortal”
  • Relationships: “is parent of,” “is greater than”
  • Variables: Statements about arbitrary objects

Example: The Socratic Argument

In Propositional Logic:

p: All humans are mortal
q: Socrates is human
r: Socrates is mortal

Premises: p, q
Conclusion: r

This doesn’t capture the logical structure. The conclusion doesn’t follow from the premises in propositional logic.

In Predicate Logic:

∀x (Human(x) → Mortal(x))    "All humans are mortal"
Human(Socrates)               "Socrates is human"
─────────────────────────────
Mortal(Socrates)              "Therefore, Socrates is mortal"

The logical structure is clear, and the conclusion follows necessarily from the premises.

Predicates

Definition

A predicate is a function that takes one or more arguments and returns true or false.

Notation: P(x), Q(x, y), R(x, y, z), …

Examples of Predicates

Unary Predicates (one argument):

  • Human(x) = “x is human”
  • Prime(x) = “x is prime”
  • Red(x) = “x is red”

Binary Predicates (two arguments):

  • Parent(x, y) = “x is the parent of y”
  • Greater(x, y) = “x is greater than y”
  • Loves(x, y) = “x loves y”

Ternary Predicates (three arguments):

  • Between(x, y, z) = “y is between x and z”
  • Gives(x, y, z) = “x gives y to z”

Predicate Variables

A predicate variable is a variable that can be replaced with different values.

Example: Human(x)

  • Human(Socrates) = true
  • Human(Plato) = true
  • Human(2) = false

Evaluating Predicates

A predicate becomes a proposition when all variables are replaced with specific values.

Example: Prime(x)

  • Prime(2) = true (proposition)
  • Prime(4) = false (proposition)
  • Prime(x) = neither true nor false (predicate, not a proposition)

Quantifiers

Universal Quantifier (∀)

Symbol: ∀ (for all, for every)

Meaning: “For all x, P(x)” or “Every x has property P”

Notation: ∀x P(x)

Truth Condition: ∀x P(x) is true if P(x) is true for every value of x in the domain.

Examples of Universal Quantification

Example 1: “All humans are mortal”

∀x (Human(x) → Mortal(x))

Example 2: “Every prime number greater than 2 is odd”

∀x ((Prime(x) ∧ x > 2) → Odd(x))

Example 3: “For all real numbers x, x² ≥ 0”

∀x (x ∈ ℝ → x² ≥ 0)

Existential Quantifier (∃)

Symbol: ∃ (there exists, there is at least one)

Meaning: “There exists an x such that P(x)” or “At least one x has property P”

Notation: ∃x P(x)

Truth Condition: ∃x P(x) is true if P(x) is true for at least one value of x in the domain.

Examples of Existential Quantification

Example 1: “There exists a prime number greater than 100”

∃x (Prime(x) ∧ x > 100)

Example 2: “Someone loves everyone”

∃x ∀y Loves(x, y)

Example 3: “There exists a real number x such that x² = 2”

∃x (x ∈ ℝ ∧ x² = 2)

Scope of Quantifiers

The scope of a quantifier is the part of the formula to which it applies.

Example: ∀x (Human(x) → Mortal(x))

  • Scope of ∀x: (Human(x) → Mortal(x))

Example: ∀x Human(x) → Mortal(Socrates)

  • Scope of ∀x: Human(x)
  • Mortal(Socrates) is outside the scope

Free and Bound Variables

A bound variable is a variable within the scope of a quantifier.

A free variable is a variable not within the scope of any quantifier.

Example: ∀x (Human(x) → Mortal(y))

  • x is bound (within scope of ∀x)
  • y is free (not within scope of any quantifier)

Combining Quantifiers

Multiple Quantifiers

When multiple quantifiers appear, their order matters.

Example 1: ∀x ∃y Loves(x, y)

  • “For all x, there exists a y such that x loves y”
  • “Everyone loves someone”

Example 2: ∃y ∀x Loves(x, y)

  • “There exists a y such that for all x, x loves y”
  • “Someone is loved by everyone”

These have different meanings!

Nested Quantifiers

Example: ∀x ∀y (Parent(x, y) → Ancestor(x, y))

  • “For all x and y, if x is the parent of y, then x is an ancestor of y”

Example: ∃x ∃y (Siblings(x, y) ∧ Loves(x, y))

  • “There exist x and y such that x and y are siblings and x loves y”

Quantifier Equivalences

Swapping Universal Quantifiers:

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

Swapping Existential Quantifiers:

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

Cannot Swap Different Quantifiers:

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

Negation of Quantified Statements

Negating Universal Quantifiers

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

Intuition: “Not all x have property P” is equivalent to “There exists an x that doesn’t have property P”

Example:

  • Original: “All humans are mortal”
  • Negation: “There exists a human that is not mortal”

Negating Existential Quantifiers

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

Intuition: “There doesn’t exist an x with property P” is equivalent to “For all x, x doesn’t have property P”

Example:

  • Original: “There exists a prime number greater than 100”
  • Negation: “For all numbers, they are not prime or not greater than 100”

Negating Complex Statements

Example 1: Negate ∀x (Human(x) → Mortal(x))

¬∀x (Human(x) → Mortal(x))
≡ ∃x ¬(Human(x) → Mortal(x))        [Negation of ∀]
≡ ∃x (Human(x) ∧ ¬Mortal(x))        [Negation of →]

Interpretation: “There exists a human that is not mortal”

Example 2: Negate ∃x ∀y Loves(x, y)

¬∃x ∀y Loves(x, y)
≡ ∀x ¬∀y Loves(x, y)                [Negation of ∃]
≡ ∀x ∃y ¬Loves(x, y)                [Negation of ∀]

Interpretation: “For all x, there exists a y such that x doesn’t love y”

Translating English to Predicate Logic

Basic Translation

Example 1: “All dogs are animals”

∀x (Dog(x) → Animal(x))

Example 2: “Some cats are black”

∃x (Cat(x) ∧ Black(x))

Example 3: “No birds are reptiles”

¬∃x (Bird(x) ∧ Reptile(x))
or equivalently
∀x (Bird(x) → ¬Reptile(x))

Complex Translations

Example 1: “Everyone loves someone”

∀x ∃y Loves(x, y)

Example 2: “Someone is loved by everyone”

∃x ∀y Loves(y, x)

Example 3: “If someone is a parent, they have a child”

∀x (∃y Parent(x, y) → ∃z Child(x, z))

Example 4: “All students who study hard pass the exam”

∀x ((Student(x) ∧ StudiesHard(x)) → Passes(x))

Interpretations and Models

Domain of Discourse

The domain of discourse is the set of objects that variables can refer to.

Example: If the domain is {Socrates, Plato, Aristotle}, then:

  • ∀x Human(x) means “Socrates, Plato, and Aristotle are all human”

Example: If the domain is all real numbers, then:

  • ∃x (x² = 2) means “There exists a real number whose square is 2”

Interpretations

An interpretation assigns:

  • A domain of discourse
  • A meaning to each predicate
  • A meaning to each constant

Example: Interpret ∀x (Human(x) → Mortal(x))

  • Domain: {Socrates, Plato, Aristotle}
  • Human(x): x is human
  • Mortal(x): x is mortal

Under this interpretation, the statement is true if all humans in the domain are mortal.

Models

A model is an interpretation that makes a formula true.

Example: The formula ∃x Prime(x) has a model where:

  • Domain: {2, 3, 4, 5}
  • Prime(x): x is prime
  • The formula is true because 2, 3, and 5 are prime

Validity and Satisfiability

Valid Formulas

A formula is valid if it is true in every interpretation.

Example: ∀x (P(x) ∨ ¬P(x))

  • This is valid (law of excluded middle)

Satisfiable Formulas

A formula is satisfiable if it is true in at least one interpretation.

Example: ∃x Prime(x)

  • This is satisfiable (true when domain includes primes)

Unsatisfiable Formulas

A formula is unsatisfiable if it is false in every interpretation.

Example: ∃x (P(x) ∧ ¬P(x))

  • This is unsatisfiable (contradiction)

Practice Problems

Problem 1: Translate to Predicate Logic

Translate: “All students who pass the exam are happy”

Solution:

∀x ((Student(x) ∧ Passes(x, exam)) → Happy(x))

Problem 2: Negate a Statement

Negate: “There exists a student who doesn’t study”

Solution:

Original: ∃x (Student(x) ∧ ¬Studies(x))
Negation: ¬∃x (Student(x) ∧ ¬Studies(x))
        ≡ ∀x ¬(Student(x) ∧ ¬Studies(x))
        ≡ ∀x (¬Student(x) ∨ Studies(x))
        ≡ ∀x (Student(x) → Studies(x))

Interpretation: “All students study”

Problem 3: Interpret Quantifier Order

What’s the difference between:

  • ∀x ∃y Likes(x, y)
  • ∃y ∀x Likes(x, y)

Solution:

  • ∀x ∃y Likes(x, y): “For each person, there is someone they like” (everyone likes someone)
  • ∃y ∀x Likes(x, y): “There is someone who is liked by everyone” (someone is liked by all)

Problem 4: Evaluate Truth

Given domain {1, 2, 3} and Prime(x) = “x is prime”:

Evaluate: ∀x Prime(x)

Solution: False (1 is not prime)

Online Learning Platforms

Interactive Tools

  • “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
  • Coq - Interactive theorem prover
  • Isabelle - Generic proof assistant
  • Z3 - SMT solver

Glossary of Key Terms

  • Bound Variable: Variable within scope of a quantifier
  • Domain of Discourse: Set of objects variables can refer to
  • Existential Quantifier: “There exists” operator (∃)
  • Free Variable: Variable not within scope of any quantifier
  • Interpretation: Assignment of meanings to predicates and constants
  • Model: Interpretation that makes a formula true
  • Predicate: Function mapping objects to true/false
  • Quantifier: Operator expressing “all” or “some”
  • Scope: Part of formula to which quantifier applies
  • Universal Quantifier: “For all” operator (∀)

Conclusion

Predicate logic extends propositional logic to handle:

  • Quantification: Expressing “all” and “some”
  • Properties: Describing characteristics of objects
  • Relationships: Expressing connections between objects
  • Variables: Making statements about arbitrary objects

By mastering predicate logic, you develop the ability to:

  • Express complex mathematical and logical statements
  • Reason about properties and relationships
  • Understand formal specifications
  • Work with databases and logic programming
  • Apply logic to real-world problems

The next article in this series will explore Quantifiers: Universal and Existential, diving deeper into quantifier semantics and applications.

What aspect of predicate logic interests you most? Have you used quantifiers in mathematics or programming? Share your thoughts in the comments below!

Comments