2.2 First-order logic and quantifiers

First-order logic expands on propositional logic by introducing predicates, variables, and quantifiers. These tools allow us to express more complex statements about objects and their relationships, bridging the gap between natural language and formal reasoning.

Despite its power, first-order logic has limitations. It can't handle higher-order concepts or self-referential statements, which led to the development of more advanced logics. These limitations also sparked investigations into incompleteness and undecidability in formal systems.

First-Order Logic

Predicates and quantifiers in first-order logic

Top images from around the web for Predicates and quantifiers in first-order logic

• 

  Predicate Logic Problem: Proof Using Change of Quantifier rule +Rules of Inference - Mathematics ... View original

  Is this image relevant?

• 

  File:Predicate logic; 2 variables; 2x2 list e2a1.svg - Wikimedia Commons View original

  Is this image relevant?

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  Predicate Logic Problem: Proof Using Change of Quantifier rule +Rules of Inference - Mathematics ... View original

  Is this image relevant?

• 

  File:Predicate logic; 2 variables; 2x2 list e2a1.svg - Wikimedia Commons View original

  Is this image relevant?

1 of 3

Top images from around the web for Predicates and quantifiers in first-order logic

• 

  Predicate Logic Problem: Proof Using Change of Quantifier rule +Rules of Inference - Mathematics ... View original

  Is this image relevant?

• 

  File:Predicate logic; 2 variables; 2x2 list e2a1.svg - Wikimedia Commons View original

  Is this image relevant?

• 

  Truth Tables – Critical Thinking View original

  Is this image relevant?

• 

  Predicate Logic Problem: Proof Using Change of Quantifier rule +Rules of Inference - Mathematics ... View original

  Is this image relevant?

• 

  File:Predicate logic; 2 variables; 2x2 list e2a1.svg - Wikimedia Commons View original

  Is this image relevant?

1 of 3

• First-order logic (FOL) extends propositional logic by introducing:
  • Predicates: Functions that take one or more arguments and return a truth value
    • $P(x)$ could represent "x is a prime number"
  • Variables: Symbols representing objects in the domain of discourse
    • $x$, $y$, $z$
  • Quantifiers: Symbols that specify the quantity of objects satisfying a predicate
    • Universal quantifier ($\forall$): Represents "for all" or "for every"
      • $\forall x P(x)$ means "for all x, P(x) is true"
    • Existential quantifier ($\exists$): Represents "there exists" or "for some"
      • $\exists x P(x)$ means "there exists an x such that P(x) is true"

Translation between natural language and logic

• Translating natural language statements into FOL formulas:
  • Identify the predicates, variables, and quantifiers in the statement
  • Construct the formula using logical connectives ($\land$, $\lor$, $\rightarrow$, $\leftrightarrow$, $\neg$)
    • "All humans are mortal" can be translated to $\forall x (H(x) \rightarrow M(x))$, where $H(x)$ means "x is a human" and $M(x)$ means "x is mortal"
• Translating FOL formulas into natural language statements:
  • Identify the predicates, variables, and quantifiers in the formula
  • Construct the natural language statement by interpreting the logical connectives and quantifiers
    • $\exists x (P(x) \land Q(x))$ can be translated to "There exists an x such that P(x) and Q(x) are both true"

Truth values in first-order logic

• An interpretation or model assigns meanings to the predicates and specifies the domain of discourse
• To evaluate the truth value of a FOL formula:
  1. Substitute the variables with objects from the domain according to the quantifiers
  2. Evaluate the truth values of the predicates for the given objects
  3. Combine the truth values using the logical connectives
• Given the interpretation $I = \{1, 2, 3\}$ and $P(x)$ meaning "x is even", evaluate $\exists x (P(x) \land x > 1)$
  • The formula is true because there exists an object (2) in the domain that satisfies both $P(x)$ and $x > 1$

Limitations of First-Order Logic

Limitations of first-order logic

• FOL has limitations in expressing certain concepts:
  • Higher-order concepts: FOL cannot quantify over predicates or functions
    • "For every property P, there exists an object x such that P(x)" cannot be expressed in FOL
  • Self-referential statements: FOL cannot express statements that refer to themselves
    • "This statement is false" cannot be expressed in FOL
• These limitations lead to the development of higher-order logics and the study of incompleteness and undecidability in formal systems