Predicate Logic

Predicate logic, also known as first-order logic, extends propositional logic by adding quantifiers and predicates. It is a more expressive form of logic, allowing us to reason about objects and their properties. Predicate logic is widely used in mathematics, computer science, and artificial intelligence due to its ability to describe statements involving mutable objects and the relationships between them.

Basic concepts

Unlike propositional logic, which works with simple, declarative statements known as propositions, predicate logic introduces the notion of quantifiers and predicates, making it much more powerful. Let's break down these components:

Constants, variables and predicates

In predicate logic, we often work with several types of symbols:

• Constants: These represent specific objects or entities in the domain of communication. For example, if our domain consists of people, then the constants can be people such as a (for Alice), b (for Bob), etc.
• Variables: Variables, such as x, y, z, are placeholders that can represent any object in the domain.
• Predicates: Predicates express properties or relationships between objects. For example, P(x) might mean "x is a person," and Q(x, y) might mean "x knows y."

Quantifiers

Quantifiers specify the scope of a statement, allowing us to make claims about some or all of the objects within the domain. In predicate logic, there are two primary quantifiers:

• Universal quantifier ∀ : The statement ∀x P(x) is "for all x, P(x) is true." It asserts that the property P applies to every object in the domain.
• Existential quantifier ∃ : The statement ∃x P(x) is "There exists an x for which P(x) is true." It asserts that there is at least one object in the domain for which P is true.

The syntax and semantics of predicate logic

Syntax

The syntax of predicate logic involves forming sentences using constants, variables, predicates, logical connectives (such as ∧ - and, ∨ - or, ¬ - not, → - implies) and quantifiers. Let us consider an example:

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

This statement asserts that for every object x, if P(x) is true, then Q(x) must also be true.

Semantics

In predicate logic, the meaning of a sentence is determined by its interpretation. Interpretation provides:

• A nonempty set called the domain of discourse.
• A function that assigns meaning to constants, variables, and predicates in the context of this domain.

For example, if we have a predicate P(x) meaning "x is a cat," and a domain consisting of animals, then an interpretation might assign to P the set of all cats.

Building blocks of predicate logic

Atomic formula

An atomic formula is the simplest type of formula in predicate logic. It consists of a predicate applied to a fixed number of terms. For example:

P(a), R(x, y)

Here, P(a) could mean "a is happy" and R(x, y) could mean "x loves y."

Complex formulas

Complex formulas are constructed from atomic formulas using logical connectives. For example, the formula:

∀x (P(x) ∧ Q(x) → R(x))

For every x if both P(x) and Q(x) are true, then R(x) is true.

Visual representation:

Examples of predicate logic

Example 1: Universal quantification

Consider the domain of animals, and the predicates P(x) meaning "x can fly" and Q(x) meaning "x is a bird." We can express the statement "All birds can fly" as follows:

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

This proposition says that for every object x in the domain, if x is a bird, then x can fly.

Example 2: Existential quantification

In this same domain, if we want to express "there exists an animal that cannot fly," we can use:

∃x (¬P(x))

This statement asserts that there is at least one object x such that x cannot fly.

Visual representation:

Importance of predicate logic

Predicate logic is foundational to mathematical logic and is a fundamental part of fields such as artificial intelligence and computer science. Its power comes from its ability to express statements and reasoning about objects and their properties in complex and varied ways. This expressive capability makes it possible to handle complex structures and proofs that are unmanageable using propositional logic alone.

Let's demonstrate this with a slightly more complex example, involving multiple quantifiers and predicates:

Advanced example: Multiple quantifiers

Consider the domain of students and courses, in which the predicate Enrolled(x, y) means "x is enrolled in y," and Passed(x, y) means "x has passed y." To express "every student enrolled in a course has passed it," we can write:

∀x ∀y (Enrolled(x, y) → Passed(x, y))

This statement indicates that for every student x and every course y, if student x is enrolled in y, then x has passed y.

Formal systems and proofs in predicate logic

Predicate logic serves as the basis for formal proofs. In a formal system, we use axioms (statements assumed to be true) and rules of inference to draw conclusions. These operations are performed through structured arguments called proofs.

Example of a simple proof

Suppose we have these axioms:

1. ∀x (A(x) → B(x)) 2. A(a)

Our goal is to prove B(a). The proof is as follows:

1. From ∀x (A(x) → B(x)), we can obtain A(a) → B(a).
2. From A(a), with A(a) → B(a), we use modus ponens to conclude B(a).

Conclusion

Predicate logic is a powerful language and tool for formal reasoning. Its ability to handle objects, their properties, and quantifiers opens the door to expressing complex statements and conducting rigorous proofs. The skills and concepts learned from predicate logic serve as the foundation for many areas of advanced study in logic, mathematics, and computer science.

Despite its complexity, understanding and mastering predicate logic unlocks tremendous potential for logical reasoning and problem-solving in a variety of fields. As we develop and embrace logical rigor, predicate logic stands as a central pillar in the architecture of modern mathematical thought and computational theory.

Comments