Introduction to Predicate Logic

Introduction

Predicate logic, also known as first-order logic or predicate calculus, is a powerful extension of propositional logic that allows us to reason about objects, their properties, and relationships between objects. While propositional logic treats statements as atomic units, predicate logic provides the ability to look inside statements and express their internal structure.

This expressive power makes predicate logic essential for mathematics, computer science, artificial intelligence, linguistics, and formal verification. It provides the logical foundation for describing mathematical structures, database queries, software specifications, and knowledge representation systems.

Limitations of Propositional Logic

Propositional logic, while useful for reasoning about complete statements, has significant limitations when we need to express generalizations, properties of objects, or relationships. In propositional logic, statements like "Socrates is a man" and "Plato is a man" must be represented as separate, unrelated propositions (P and Q), even though they share a common structure.

Propositional logic cannot express statements involving "all," "some," "every," or "there exists." It cannot capture the logical relationship between statements like "All men are mortal" and "Socrates is a man," which should logically entail "Socrates is mortal." This is where predicate logic becomes essential.

Example of Limitation

Consider the statement "All humans are mortal." In propositional logic, we can only represent this as a single proposition H. But this fails to capture the internal structure involving "all humans" and the property of "being mortal." Predicate logic allows us to express this more precisely as ∀x (Human(x) → Mortal(x)).

Predicates

A predicate is a property or relation that can be attributed to one or more objects. Think of predicates as functions that take objects as input and return truth values (true or false) as output. Predicates allow us to express properties of objects and relationships between objects.

Predicates are denoted using capital letters followed by one or more arguments in parentheses. For example, P(x) represents "x has property P," while R(x, y) represents "x is related to y by relation R."

Examples of Predicates

Human(x) - "x is human" (unary predicate, one argument)
GreaterThan(x, y) - "x is greater than y" (binary predicate, two arguments)
Between(x, y, z) - "x is between y and z" (ternary predicate, three arguments)
Prime(n) - "n is a prime number" (unary predicate)

Quantifiers

Quantifiers are special symbols that specify the quantity of specimens in the domain of discourse for which a predicate holds. The two fundamental quantifiers are:

Universal Quantifier (∀)

Expresses that a predicate holds for all elements in the domain of discourse. It makes a claim about every object in the universe under consideration.

Notation: ∀x P(x) (read as "for all x, P(x) holds")

Example: ∀x (Human(x) → Mortal(x)) - "For all x, if x is human, then x is mortal"

Existential Quantifier (∃)

Expresses that there exists at least one element in the domain for which the predicate holds. It asserts the existence of something with a particular property.

Notation: ∃x P(x) (read as "there exists an x such that P(x)")

Example: ∃x Prime(x) - "There exists a number that is prime"

Structure of Predicate Logic

A predicate logic expression has several key components:

Terms

Constants (specific objects like 'Socrates'), variables (placeholders like x, y), and functions (operations that produce terms).

Formulas

Well-formed formulas (WFFs) are syntactically correct expressions combining predicates, quantifiers, variables, and logical connectives.

Bound and Free Variables

Variables that are bound by quantifiers (e.g., the x in ∀x) versus free variables that are not quantified.

Examples

Here are some examples showing the expressive power of predicate logic:

Mathematical Statement

∀x ∀y ((x > 0 ∧ y > 0) → (x + y > 0)) - "For all positive numbers x and y, their sum is positive"

Relationships

∀x (Parent(x, y) → ∃z Loves(x, z)) - "For all x, if x is a parent of y, then there exists someone z whom x loves"

Complex Statement

∃x (Student(x) ∧ ∀y (Course(y) → Enrolled(x, y))) - "There exists a student who is enrolled in all courses"

Logical Equivalences with Quantifiers

Just as propositional logic has logical equivalences, predicate logic has important equivalences involving quantifiers:

Negation of Universal: ¬(∀x P(x)) ≡ ∃x ¬P(x) - "Not all x have property P" is equivalent to "There exists an x that does not have property P"
Negation of Existential: ¬(∃x P(x)) ≡ ∀x ¬P(x) - "It is not the case that there exists an x with property P" is equivalent to "For all x, x does not have property P"
Distribution Laws: ∀x (P(x) ∧ Q(x)) ≡ (∀x P(x)) ∧ (∀x Q(x)) - Universal quantifiers distribute over conjunction

Applications

Predicate logic is fundamental to many areas of computer science and mathematics:

Databases

Relational database query languages like SQL are based on predicate logic principles, where queries express predicates over database relations.

Formal Verification

Formal verification of software and hardware systems relies heavily on predicate logic to specify and prove correctness properties.

Artificial Intelligence

Predicate logic enables knowledge representation in AI systems, allowing machines to reason about objects, their properties, and relationships in automated planning and expert systems.

Mathematics

Virtually all mathematical statements and proofs use predicate logic, from defining properties of numbers to expressing theorems about mathematical structures.

Relationship to Propositional Logic

Predicate logic builds upon propositional logic by adding predicates and quantifiers. All the logical connectives from propositional logic (¬, ∧, ∨, →, ↔) remain valid and work the same way in predicate logic. The difference is that instead of combining atomic propositions, we combine predicates and quantified expressions.

Every propositional logic statement can be viewed as a special case of predicate logic where no predicates or quantifiers are used. Conversely, predicate logic reduces to propositional logic when dealing with specific instances rather than general statements.

Using the Propositional Calculator

While this calculator focuses on propositional logic and Boolean algebra, understanding the relationship between propositional and predicate logic helps deepen your grasp of both systems. The operators and truth tables you work with here form the foundation of the more expressive predicate logic.

Try the Logic Calculator for propositional logic →