Predicate Logic

←Back to Tech Tree

inventorycoverage

Predicate Logic #

Formal MethodsDifficulty: ★★★☆☆Depth: 3Unlocks: 0

First-order logic. Quantifiers, predicates, relations.

Interactive Visualization #

⏮◀◀▶▶STEP0.25x1xZOOM

t=0s

Core Concepts #

Key Symbols & Notation #

quantifier symbols: 'forall' and 'exists' (universal and existential quantifiers)

Essential Relationships #

Prerequisites (1) #

Propositional Logic9 atoms

Referenced by (1) #

Where this concept shows up in the operating-finance and personal-finance graphs.

From Business (1) #

[contract reviewBusiness

Contract clauses are conditional predicate structures ('If Party A fails to deliver within 30 days, then Party B may terminate') - formalizing review rules as quantified predicates is how you specify what each discrete check evaluates](/business/contract-review/)

Advanced Learning Details

Graph Position #

24

Depth Cost

0

Fan-Out (ROI)

0

Bottleneck Score

3

Chain Length

Cognitive Load #

5

Atomic Elements

52

Total Elements

L4

Percentile Level

L3

Atomic Level

All Concepts (23) #

Teaching Strategy #

Self-serve tutorial - low prerequisites, straightforward concepts.

Propositional logic can say “(P ∧ Q) → R”, but it can’t say “for every user, if they reset their password then they can log in” without inventing a separate proposition for each user. Predicate logic (first-order logic) is the upgrade that lets you talk about objects, their properties, and relationships—at scale—using variables and quantifiers.

TL;DR:

Predicate logic extends propositional logic with (1) a domain of discourse (objects), (2) terms that name objects (variables/constants/functions), (3) predicates/relations that make statements about objects, and (4) quantifiers ∀ and ∃ that range over the domain. You build formulas like ∀x (Human(x) → Mortal(x)) and reason by translating English carefully, tracking scope, and using sound inference patterns (e.g., universal instantiation, existential generalization) while avoiding common quantifier traps.

What Is Predicate Logic? #

Why we need more than propositional logic #

Propositional logic treats whole statements as indivisible atoms: P, Q, R. That’s great for reasoning about fixed, named facts, but it doesn’t let you open up a statement and talk about its internal structure.

Consider the English statement:

In propositional logic, you’d need one proposition per student (“Alice submitted”, “Bob submitted”, …) and then conjoin them all. That’s not scalable and it misses the structure that these are all instances of the same pattern.

Predicate logic (often called first-order logic, FOL) solves this by introducing:

  1. 1)A domain of discourse: a nonempty set of objects we’re talking about.
  2. 2)Variables that range over that domain.
  3. 3)Predicates (relations) that say something about objects.
  4. 4)Quantifiers to express “for all” (∀) and “there exists” (∃).

This is the language used by mathematics (“∀ε > 0 ∃N …”), by program specification (“∀i: 0 ≤ i < n → a[i] ≥ 0”), and by many formal methods tools.

The basic ingredients #

Predicate logic is built from a small set of syntactic building blocks.

Domain of discourse #

The domain (also called the universe) is the set over which variables range. It must be nonempty.

Examples:

The same formula can mean different things under different domains.

Terms (naming objects) #

A term denotes an element of the domain.

Terms come from:

Examples of terms:

Intuition: a term is like an expression that evaluates to “an object”.

Predicates / atomic formulas (stating facts) #

A predicate is an n-ary relation symbol, like:

When you apply a predicate to terms, you get an atomic formula:

An atomic formula evaluates to True/False once you know what the symbols mean in your domain.

Building complex formulas #

From atomic formulas, you build larger formulas using the same connectives as propositional logic:

And you add quantifiers:

Crucially, quantifiers bind variables (like how parentheses bind subexpressions). The part of the formula a quantifier controls is its scope.

Free vs bound variables #

A variable occurrence is:

Example:

A formula with no free variables is called a sentence. Sentences are what we typically evaluate as True/False in a model.

A quick semantics snapshot (what makes formulas “true”) #

To interpret a predicate-logic language, you need:

Then:

This “assignment of variables” idea is why quantifiers are powerful: they quantify over all objects in the domain, not just those you named.

Table: how predicate logic extends propositional logic #

FeaturePropositional LogicPredicate Logic (FOL)
Atomic unitsPropositions P, Q, RPredicates applied to terms, e.g., P(x), R(x,y)
Can talk about objects?NoYes (domain + terms)
Can express “all / some”?Only by enumeratingYes via ∀ and ∃
Typical useCircuit reasoning, SATMath, specs, verification, databases

Predicate logic keeps propositional logic’s connectives, but gives you a language to express structure and patterns over a domain.

Core Mechanic 1: Quantifiers and Scope #

Why quantifiers matter #

Most statements we care about in math and software are inherently quantified:

Quantifiers let you express these patterns directly. But they also introduce subtlety: the order and scope of quantifiers can change meaning dramatically.

Universal quantifier ∀ (for all) #

The formula:

means: “for every x in the domain, φ(x) is true.”

Example:

This does not claim that every object is a student. It says: if an object is a student, then it has an ID.

A common pattern:

reads as: “All A’s are B’s.”

Existential quantifier ∃ (there exists) #

The formula:

means: “there exists some x in the domain such that φ(x) is true.”

Example:

This asserts at least one student is late.

Scope: where a quantifier applies #

Scope is usually controlled by parentheses.

Compare:

  1. ∀x (P(x) → Q(x))

  2. (∀x P(x)) → Q(x)

These are not the same.

Quantifier order (∃∀ vs ∀∃) #

This is one of the biggest conceptual leaps from propositional logic.

Consider:

Assume the domain is people.

  1. ∀x ∃y Loves(x, y)
  1. ∃y ∀x Loves(x, y)

These are very different. The second is much stronger.

A careful translation pipeline (English → logic) #

When translating, go slowly:

  1. 1)Choose the domain explicitly.
  2. 2)Define predicates with clear meaning.
  3. 3)Identify quantifier words: “every”, “all”, “any” → ∀; “some”, “there exists” → ∃.
  4. 4)Attach conditions using → or ∧.

Example: “Every user who reset their password can log in.”

Translation:

Notice why it’s → and not ∧: we’re not claiming everyone reset their password.

Negating quantified statements (De Morgan’s for quantifiers) #

Negation interacts with quantifiers in a structured way:

Intuition:

Do the algebra carefully. For example:

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

Step-by-step:

  1. 1)¬∀x ψ(x) ≡ ∃x ¬ψ(x)

where ψ(x) = (P(x) → Q(x))

So:

  1. 2)¬(∀x (P(x) → Q(x)))

≡ ∃x ¬(P(x) → Q(x))

Now expand implication:

  1. 3)(P → Q) ≡ (¬P ∨ Q)

so ¬(P → Q) ≡ ¬(¬P ∨ Q)

Apply De Morgan:

  1. 4)¬(¬P ∨ Q) ≡ (P ∧ ¬Q)

Final:

  1. 5)¬(∀x (P(x) → Q(x)))

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

Reading: “It is not true that all P’s are Q’s” means “There exists a P that is not Q.”

Table: common English patterns #

EnglishTypical logic form
“All A are B”∀x (A(x) → B(x))
“Some A are B”∃x (A(x) ∧ B(x))
“No A are B”∀x (A(x) → ¬B(x)) (equiv. ¬∃x (A(x) ∧ B(x)))
“Not all A are B”∃x (A(x) ∧ ¬B(x))

Quantifiers are simple symbols with big consequences. Most real errors are scope/order errors, not symbol errors.

Core Mechanic 2: Predicates, Relations, and Terms (and why functions matter) #

Why terms and predicates are separate ideas #

Predicate logic splits the world into two roles:

Predicates are what turn objects into truth claims.

This separation is why you can’t, for example, treat a predicate like an object unless your logic explicitly supports that (standard first-order logic does not—this is a doorway to higher-order logic).

Arity: how many inputs a symbol takes #

Predicates and functions have an arity:

Similarly for functions:

Arity matters because it encodes what kind of relationship you’re expressing.

Relations as sets (a useful mental model) #

If your domain is D, then:

So the atomic formula R(a, b) is true exactly when (a, b) ∈ R.

This viewpoint connects predicate logic to:

Equality #

Most first-order settings include equality “=”.

Equality lets you state things like:

Be careful: equality is a logical symbol with its own meaning (identity), not just another predicate you can interpret arbitrarily (in standard FOL with equality).

Function symbols (building more complex terms) #

Function symbols let you talk about structured objects without introducing extra quantifiers.

Example domain: integers.

Then you can write:

Without functions, you’d need a relation Plus(x, 1, y) to express y = x + 1, and then quantify y.

Functions vs relations: two equivalent styles (often) #

You can encode a function f(x) using a relation F(x, y) meaning “y = f(x)” plus axioms:

But using function symbols is typically cleaner.

Binding and substitution (the safe way) #

A fundamental operation is substituting a term into a formula.

If φ(x) is a formula with x free, and t is a term, then φ(t) is the result of substituting t for x.

Example:

But you must avoid variable capture: substituting a term containing a variable that becomes accidentally bound.

Example of what can go wrong:

Naively you get ∀y Loves(y, y), where the y inside t became bound by ∀y.

The safe approach is:

So you’d rename:

Then substitute x := y:

Quantifiers as “big AND / big OR” (finite intuition) #

If the domain is finite D = {d₁, …, dₙ}, then:

This is not how we compute it in general (domains can be infinite), but it’s an excellent intuition-builder.

Summary of the “typing” discipline #

Keep these categories separate:

If you can reliably tell “object expressions” from “truth expressions”, you’ll write correct formulas much faster.

Application/Connection: Using Predicate Logic in CS and Formal Methods #

Why this matters in formal methods #

Formal methods is about specifying and proving properties of systems. Predicate logic is the backbone for:

Predicate logic is the first language where you can naturally express invariants like:

or existence claims like:

Typical CS domains and predicate meanings #

Predicate logic is flexible because you choose the domain and interpretation.

Examples:

  1. Data structures
  1. Security policies

Then a policy might be:

  1. Databases (relational model)

A table like Enrolled(student, course) is literally a binary predicate Enrolled(·,·).

Queries often correspond to existential formulas.

Example: “Find students enrolled in CS101” corresponds to:

Proof patterns you’ll reuse #

Even if you don’t do full theorem-prover work yet, you should recognize the standard moves.

Universal instantiation (UI) #

From ∀x φ(x), you may conclude φ(t) for any term t.

Example:

  1. 1)∀x (Human(x) → Mortal(x))
  2. 2)Human(socrates)

UI on (1) with t = socrates gives:

  1. 3)Human(socrates) → Mortal(socrates)

Then by modus ponens with (2):

  1. 4)Mortal(socrates)

Existential instantiation (EI) (with care) #

From ∃x φ(x), you can introduce a fresh symbol k such that φ(k) holds, but k must be new (it can’t carry hidden assumptions).

This is subtle: you don’t get to pick a specific known constant unless you can prove it works.

Existential generalization (EG) #

From φ(t), infer ∃x φ(x) (replace t by a variable).

Example:

Universal generalization (UG) (with care) #

From φ(x) for an arbitrary x (with no special assumptions about x), infer ∀x φ(x).

This “arbitrary” requirement is exactly where many informal proofs go wrong.

Satisfiability, validity, and models (a quick bridge from propositional logic) #

You already know satisfiability in propositional logic. In FOL:

Example (valid):

This is valid because if P holds for all x in a nonempty domain, then certainly there exists an x where P holds.

Non-valid (not always true):

True in some models, false in others.

Why tooling often restricts or extends FOL #

Pure FOL is expressive, but automated reasoning is harder than for propositional logic.

So real tools often:

The key takeaway: learning predicate logic is the gateway to reading specifications, understanding solver input languages, and following proofs about programs.

Worked Examples (3) #

Translate English to predicate logic (and see why → matters) #

Domain: all animals in a shelter.

Predicates:

Translate:

  1. “Every dog is vaccinated.”

  2. “Some dog is adoptable.”

  3. “Not every dog is adoptable.”

    1. “Every dog is vaccinated.”

    We want: for all x, if x is a dog then x is vaccinated.

    ∀x (Dog(x) → Vaccinated(x))

    1. “Some dog is adoptable.”

    We want: there exists an x that is a dog and is adoptable.

    ∃x (Dog(x) ∧ Adoptable(x))

    1. “Not every dog is adoptable.”

    Start from “Every dog is adoptable”: ∀x (Dog(x) → Adoptable(x))

    Negate it:

    ¬∀x (Dog(x) → Adoptable(x))

  2. Now push negation inward using ¬∀x φ ≡ ∃x ¬φ.

    Let φ(x) = (Dog(x) → Adoptable(x)).

    ¬∀x φ(x) ≡ ∃x ¬φ(x)

    So:

    ¬∀x (Dog(x) → Adoptable(x))

    ≡ ∃x ¬(Dog(x) → Adoptable(x))

  3. Eliminate implication:

    (Dog(x) → Adoptable(x)) ≡ (¬Dog(x) ∨ Adoptable(x))

    So:

    ¬(Dog(x) → Adoptable(x))

    ≡ ¬(¬Dog(x) ∨ Adoptable(x))

    ≡ Dog(x) ∧ ¬Adoptable(x)

    Final:

    ∃x (Dog(x) ∧ ¬Adoptable(x))

Insight: “All dogs are adoptable” is an implication because it’s conditional on being a dog. Negating a universal statement almost always turns into an existential counterexample: “there exists a dog that is not adoptable.”

Quantifier order changes meaning (everyone has a password vs one shared password) #

Domain: users.

Predicate Knows(u, p): user u knows password p.

We want to compare two statements:

A) ∀u ∃p Knows(u, p)

B) ∃p ∀u Knows(u, p)

  1. Statement A:

    ∀u ∃p Knows(u, p)

    Read carefully: for each user u, there exists some password p such that u knows p.

    Different users may have different passwords.

    This is typically true in a realistic system (each user knows at least one password).

  2. Statement B:

    ∃p ∀u Knows(u, p)

    Read carefully: there exists a single password p such that every user knows p.

    This is far stronger: it implies a shared universal password.

  3. Show non-equivalence by countermodel thinking.

    Suppose there are two users: alice and bob.

    Suppose alice knows password "a1" and bob knows password "b1".

    Then:

    • •A is True (alice has a password she knows; bob has a password he knows).
    • •B is False (there is no single password known by both).

Insight: Mentally underline which variables must be the same across all choices. In ∃p ∀u, the password is chosen once and reused for every user; in ∀u ∃p, each user gets their own choice.

A small proof using universal instantiation and modus ponens #

Given:

  1. ∀x (Student(x) → HasEmail(x))

  2. Student(alex)

Prove: HasEmail(alex)

  1. Start with the universal statement:

    1. ∀x (Student(x) → HasEmail(x))

  2. Apply universal instantiation with t = alex:

    From ∀x φ(x), infer φ(alex).

    So we get:

    1. Student(alex) → HasEmail(alex)

  3. Use the fact:

    1. Student(alex)

  4. Apply modus ponens to (3) and (2):

    If Student(alex) → HasEmail(alex) and Student(alex), then HasEmail(alex).

    Therefore:

    1. HasEmail(alex)

Insight: Universal facts are like templates. Instantiation turns the template into a concrete implication you can fire with propositional reasoning.

Key Takeaways #

Common Mistakes #

Practice #

easy

Translate into predicate logic. Domain: all integers ℤ. Predicates/relations: Even(x), Odd(x), Less(x,y). Use arithmetic terms like x+1 if you want.

A) “Every even integer is not odd.”

B) “There exists an integer that is less than every integer.”

Hint: A uses implication. B is about a single special integer that compares to all others; watch quantifier order.

Show solution

A) ∀x (Even(x) → ¬Odd(x))

B) ∃x ∀y Less(x, y)

medium

Negate the sentence and simplify:

∀x (P(x) → ∃y (Q(y) ∧ R(x, y)))

Hint: Push ¬ inward step by step: ¬∀ → ∃¬, ¬∃ → ∀¬, and ¬(A → B) ≡ A ∧ ¬B. Then use De Morgan on ¬(Q ∧ R).

Show solution

Start:

¬∀x (P(x) → ∃y (Q(y) ∧ R(x, y)))

≡ ∃x ¬(P(x) → ∃y (Q(y) ∧ R(x, y)))

≡ ∃x (P(x) ∧ ¬∃y (Q(y) ∧ R(x, y)))

≡ ∃x (P(x) ∧ ∀y ¬(Q(y) ∧ R(x, y)))

≡ ∃x (P(x) ∧ ∀y (¬Q(y) ∨ ¬R(x, y)))

hard

Are these two formulas equivalent? If not, give a counterexample model (a small finite domain and an interpretation of R).

  1. ∀x ∃y R(x, y)

  2. ∃y ∀x R(x, y)

Hint: Try a domain with two elements {a,b}. Make R relate each element to itself only.

Show solution

They are not equivalent.

Counterexample:

Then:

  1. ∀x ∃y R(x,y) is True (for x=a choose y=a; for x=b choose y=b).

  2. ∃y ∀x R(x,y) is False (no single y works for both x=a and x=b).

Connections #

Next nodes you’re ready for:

Background refreshers:

Quality: A (4.2/5)

← back to treebrowse all →