Predicate Logic

Understanding Predicate Logic

Predicate logic (also called first-order logic) extends propositional logic by introducing predicates that depend on variables, together with quantifiers that describe how many objects satisfy a property. Where propositional logic can only say "it is raining," predicate logic can say "for every city, if it is raining there, then the streets are wet" — letting us reason precisely about entire classes of objects, which is essential for writing rigorous mathematical proofs and formal specifications.

Key Definitions & Formulas

• Predicate: a statement P(x) whose truth depends on the value substituted for x, e.g. P(x): "x is even."
• Universal quantifier (∀x, P(x)): true when P(x) holds for every x in the domain.
• Existential quantifier (∃x, P(x)): true when P(x) holds for at least one x in the domain.
• Negating quantifiers: ¬(∀x, P(x)) is equivalent to ∃x, ¬P(x), and vice versa.
• Nested quantifiers: order matters — ∀x∃y P(x,y) is generally not the same as ∃y∀x P(x,y).

Worked Example

Let P(x): "x > 0" over the domain of all integers. The statement ∀x, P(x) is false (x = -1 is a counterexample), while ∃x, P(x) is true (e.g. x = 1 works). Negating the first statement gives ∃x, ¬P(x) — "there exists an integer that is not positive" — which correctly matches our counterexample.

Where This Is Used

• Writing precise mathematical definitions and theorem statements.
• Specifying correctness conditions for software (pre/post-conditions in formal verification).
• Database query languages, where SQL's EXISTS and ALL map directly onto ∃ and ∀.
• Artificial intelligence knowledge representation and automated reasoning systems.