Predicate Logic

Introduction

Predicate logic—also known as first-order logic (FOL)—is a formal system in mathematical logic that extends propositional logic by introducing quantifiers and predicates. While propositional logic handles simple true/false statements, predicate logic allows for expressing statements involving objects, properties, and relations, making it vastly more expressive and powerful.

In computer science, predicate logic forms the theoretical foundation of fields like artificial intelligence, automated reasoning, formal verification, and database query languages. Whether you’re writing logical assertions in a program, constructing a proof in a theorem prover, or designing a complex rule-based system, predicate logic gives you the formalism to reason about structure, behavior, and inference.

What Is Predicate Logic?

Predicate logic is a system of logic that evaluates the truth of statements involving variables, functions, and quantifiers, rather than just fixed statements. It enables us to write logical sentences like:

“For all x, if x is a dog, then x is a mammal.”

This cannot be expressed in propositional logic but is easily captured in predicate logic using quantifiers and predicates.

Basic Components of Predicate Logic

1. Predicates

A predicate is a function that maps objects to truth values. It’s often written like a function:

• Dog(x) – “x is a dog”
• Loves(x, y) – “x loves y”

Predicates express properties of objects or relations between objects.

2. Terms

Terms are the objects that predicates refer to. These include:

• Constants: specific named entities (e.g., a, John, 2)
• Variables: placeholders for arbitrary elements (e.g., x, y)
• Functions: mappings from one or more objects to another (e.g., FatherOf(x))

3. Quantifiers

Quantifiers allow you to make general or existential claims:

• Universal Quantifier (∀): “for all”
  • ∀x Dog(x) – “All x are dogs”
• Existential Quantifier (∃): “there exists”
  • ∃x Dog(x) – “There exists at least one x that is a dog”

4. Logical Connectives

Just like in propositional logic, predicate logic uses:

• ¬ (NOT)
• ∧ (AND)
• ∨ (OR)
• → (IMPLIES)
• ↔ (IF AND ONLY IF)

These connect predicates into complex logical formulas.

Syntax and Semantics

Syntax (how formulas are constructed)

A valid predicate logic formula follows rules of formation:

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

This states: “For all x, if x is human, then x is mortal.”

Semantics (what formulas mean)

Semantics defines how these formulas are interpreted in a domain of discourse (the set of all things we’re talking about).

For example, the formula:

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

is true if there exists at least one black cat in the domain.

Examples of Predicate Logic

1. Socratic Syllogism

Premise 1: ∀x (Man(x) → Mortal(x))  
Premise 2: Man(Socrates)  
Conclusion: Mortal(Socrates)

This classical syllogism demonstrates universal instantiation and modus ponens.

2. Family Relationships

∀x ∀y (Parent(x, y) → Loves(x, y))

Interpretation: “Every parent loves their child.”

∃x ∃y (Sibling(x, y) ∧ Older(x, y))

Interpretation: “There exists a pair of siblings where one is older.”

Predicate Logic vs Propositional Logic

Applications in Computer Science

1. Artificial Intelligence

• Used in knowledge representation and automated reasoning.
• Tools like Prolog use predicate logic to infer facts and answer queries.

2. Formal Verification

• Used to prove properties of programs and hardware systems (e.g., safety, correctness).
• The basis of model checking and proof assistants (like Coq, Isabelle).

3. Databases and SQL

• Relational database theory is based on first-order logic.
• A SQL query like:

SELECT * FROM Employees WHERE Age > 40;

…is logically equivalent to:

∃x (Employee(x) ∧ Age(x) > 40)

4. Programming Languages

• Type systems and logical rules in languages like Haskell, Scala, and OCaml are built on predicate logic.
• Enables dependent types and logical inference at compile time.

Rules of Inference in Predicate Logic

Some common rules used to derive logical conclusions:

• Universal Instantiation: From ∀x P(x), infer P(a)
• Existential Instantiation: From ∃x P(x), infer P(c) (where c is new)
• Modus Ponens: From P → Q and P, infer Q
• Modus Tollens: From P → Q and ¬Q, infer ¬P
• Contrapositive: P → Q is equivalent to ¬Q → ¬P

These are used in formal proofs, theorem provers, and logic-based programming.

Common Techniques

1. Skolemization

Transforming existential quantifiers into functions to eliminate them, used in automated theorem proving.

2. Unification

A technique to match logical expressions by finding consistent substitutions for variables.

Example:

Loves(x, y) =? Loves(John, y)

Unifier: {x = John}

3. Resolution

A method for automated theorem proving, particularly in logic programming and SAT solving.

Limitations of Predicate Logic

While powerful, predicate logic has limitations:

• Undecidability: Not all formulas are decidable (no algorithm can always determine truth).
• Expressiveness Boundaries: Cannot quantify over predicates (that requires second-order logic).
• Performance: Reasoning can be computationally expensive (NP-complete or worse).

Predicate Logic vs Second-Order Logic

Predicate logic is often a sweet spot: powerful enough to model most real-world logic, but constrained enough to automate (with effort).

Best Practices

✅ Clearly define the domain of discourse.
✅ Use meaningful predicate names (IsDog(x) is better than P(x)).
✅ Prefer quantifier nesting only when necessary to avoid confusion.
✅ Use predicate logic to formalize assumptions, not just to manipulate symbols.
✅ Keep formulas readable using indentation and parentheses.

Real-World Analogy

Think of predicate logic as the difference between:

• Propositional: “The light is on.”
• Predicate: “For every room r, if it’s nighttime, then the light in room r is on.”

Predicate logic brings structure and abstraction, allowing logic to scale beyond fixed truths to universally applicable rules.

Summary Table

Related Keywords

Artificial Intelligence
Automated Reasoning
First Order Logic
Formal Semantics
Inference Rule
Knowledge Representation
Logical Connective
Logic Programming
Model Theory
Predicate Function
Proof Assistant
Propositional Logic
Quantifier
Skolemization
Symbolic Logic
Theorem Proving
Truth Value
Unification Algorithm
Universal Quantification
Variable Binding