Select Page

The theory of predicates, also known as predicate logic or first-order logic, is an extension of propositional logic that allows for more complex and expressive statements about the relationships between objects and properties. First-order logic introduces quantifiers and predicates to reason about objects and their attributes in a structured and formalized manner.

Predicates:

  • Definition: A predicate is a function that takes one or more objects as input and evaluates to either true or false, depending on whether the objects satisfy the condition specified by the predicate.
  • Examples:
    • : “x is a prime number.”
    • : “x is taller than y.”
    • : “x loves y.”
  • Components:
    • Variables: Predicates typically involve variables that represent objects or entities in the domain of discourse.
    • Atomic Formulas: Predicates can be expressed as atomic formulas by applying predicates to variables or constant symbols.
  • Quantifiers: Predicates can be combined with quantifiers such as universal quantifier ) to make statements about all or some objects in a domain.

First-Order Logic:

  • Definition: First-order logic (FOL) is a formal system of logic that extends propositional logic by introducing quantifiers and predicates to reason about objects and their properties.
  • Syntax:
    • Variables: Represent objects or entities in the domain of discourse.
    • Predicates: Express relationships or properties that can be true or false about objects.
    • Quantifiers: Specify the scope of variables in a formula, indicating whether the formula applies universally or existentially to objects in the domain.
    • Connectives: Include logical connectives such as AND (∧

      ), OR (), NOT (¬), implication (→, etc., for forming compound formulas.

  • Semantics:
    • Interpretations: Assign meanings to the symbols and structures of the language, mapping variables to elements of the domain and predicates to relations or properties.
    • Truth Values: Formulas are evaluated as either true or false under an interpretation, depending on whether the objects satisfy the conditions specified by the predicates.
  • Applications:
    • First-order logic is widely used in mathematics, computer science, philosophy, linguistics, and artificial intelligence for formalizing knowledge, reasoning about objects and relationships, and modeling complex systems.

Example:

Consider the statement: “For all integers x, if x is even, then x + 2 is even.”

  • Predicate: Let denote “x is even.”
  • Quantifiers: The statement can be expressed as

    .

  • Interpretation: Under the interpretation where

    ranges over integers, the formula is true if, for every integer

    , i
    is even, thenx+2 is even.

 the theory of predicates, or first-order logic, provides a formal framework for reasoning about objects and their properties using predicates and quantifiers. It extends propositional logic by introducing richer syntax and semantics for expressing complex relationships and making precise statements about the world.