Predicate Logic: Quantifiers, Negation, and Reasoning with Properties of Objects

Explore predicate logic, extending propositional logic to reason about properties of objects and relationships between them. This guide explains predicates, quantifiers (universal ∀, existential ∃), negation of quantified statements, and how to construct and analyze logical statements in predicate logic.

Predicate Logic: Quantifiers and Negation

Introduction to Predicate Logic

Predicate logic extends propositional logic by allowing for statements about properties of objects and relationships between objects. It uses predicates (which describe properties or relationships) and quantifiers (which specify how many objects a statement applies to).

Predicates

A predicate is an expression containing one or more variables. When values are assigned to these variables, the predicate becomes a proposition (a statement that's either true or false). Examples:

  • E(x, y): x = y
  • X(a, b, c): a + b + c = 0
  • M(x, y): x is married to y

Quantifiers

Quantifiers specify the scope of a variable in a predicate. The two main quantifiers are:

1. Existential Quantifier (∃):

Means "there exists at least one". The notation ∃x P(x) means "There exists at least one x such that P(x) is true."

2. Universal Quantifier (∀):

Means "for all" or "for every". The notation ∀x P(x) means "For every x, P(x) is true."

Negation of Quantified Propositions

Negating quantified propositions involves applying De Morgan's Laws:

  • ¬(∀x P(x)) ≡ ∃x ¬P(x)
  • ¬(∃x P(x)) ≡ ∀x ¬P(x)

In simpler terms: The negation of "all" is "at least one is not"; the negation of "at least one" is "none are".

Examples of Negation:

  1. ¬(∀x P(x) ∧ ∃y Q(y)) ≡ ∃x ¬P(x) ∨ ∀y ¬Q(y)
  2. ¬(∃x ∈ U (x + 6 = 25)) ≡ ∀x ∈ U (x + 6 ≠ 25)
  3. ¬(∃x P(x) ∨ ∀y Q(y)) ≡ ∀x ¬P(x) ∧ ∃y ¬Q(y)

Propositions with Multiple Quantifiers

Statements can have multiple quantifiers. The order of quantifiers matters.

  • ∀x ∀y P(x, y) is equivalent to ∀y ∀x P(x, y).
  • ∃x ∃y P(x, y) is equivalent to ∃y ∃x P(x, y).
  • ∀x ∃y P(x, y) is *not* equivalent to ∃y ∀x P(x, y).

Example: Negating Propositions with Multiple Quantifiers

Assume U = ℝ (the set of real numbers):

1. ¬(∀x ∃m (x² < m)) ≡ ∃x ∀m (x² ≥ m)

This means "There exists an x such that for all m, x² ≥ m". This is true because for any m, there's an x large enough such that x² is greater than or equal to m.

2. ¬(∃m ∀x (x² < m)) ≡ ∀m ∃x (x² ≥ m)

This means "For every m, there exists an x such that x² ≥ m". This is also true.

Conclusion

Predicate logic extends propositional logic by introducing quantifiers, allowing us to make statements about properties and relationships of objects. Understanding quantifiers and their negation is crucial for working with logical statements and analyzing their truth values.