Predicate Logic

A system of logic that lets us describe properties, relationships, and statements about objects within a particular domain.

What is Predicate Logic?

Predicate logic extends the ideas of propositional logic by allowing statements to contain variables and by describing properties or relationships involving those variables.

Instead of treating an entire statement as one indivisible unit, predicate logic allows us to describe what a statement is about.

Predicates

A predicate is a statement containing one or more variables. Its truth value depends on the values assigned to those variables.

A predicate can describe a property of an object or a relationship between multiple objects.

Example: One Variable

Here, x is the variable and P represents the predicate.

Example: Multiple Variables

Predicates can also describe relationships between multiple objects.

The predicate Q(x, y) depends on both x and y.

Domain of Discourse

A domain specifies the collection of objects that a variable is allowed to represent.

For example, if the domain is the set of natural numbers, then a variable such as x represents a natural number.

Specifying a domain is important because the truth of a predicate can depend on which objects are being considered.

Quantifiers

Quantifiers tell us how widely a predicate applies within its domain. The two fundamental quantifiers are the universal quantifier and the existential quantifier.

Universal Quantifier

The universal quantifier is written using the symbol ∀ and means “for all” or “for every.”

This expression states that P(x) is true for every value of x in the specified domain.

Example

Let P(x) mean “x is an even number,” with x ∈ ℕ.

This reads: “For every natural number x, x is even.”

The statement is false because not every natural number is even. For example, 3 is a natural number but is not even.

Existential Quantifier

The existential quantifier is written using the symbol ∃ and means “there exists” or “there is at least one.”

This expression states that there is at least one value of x in the domain for which P(x) is true.

Example

Again, let P(x) mean “x is an even number,” where x ∈ ℕ.

This reads: “There exists a natural number x such that x is even.”

This statement is true because numbers such as 2, 4, and 6 satisfy the predicate.

Predicates vs. Quantifiers

Predicates and quantifiers work together, but they have different roles.

Applications

Predicate logic is useful well beyond theoretical mathematics. It provides a way to express precise conditions and relationships in computer science and engineering.