IV.1 Introduction

Quantifiers [Slide 112]

• Quantifiers extend the expressive power of the logical notation but can be motivated as abbreviations.

• Existential quantifier. This is denoted by ∃ and is read as “there exists a...”

  ∃I  ∈  {7,8,9}IsPrime(I)

  This quantified expression can be read as:

  there exists a value in the set {7,8,9} which satisfies the truth-valued function IsPrime.

• The I is the bound identifier, the I ∈{ … } is the constraint and the expression after the dot is the body of the quantified expression.
• Any free occurrences of the bound identifier within the body become bound in the quantified expression. All such occurrences refer to the bound identifier. The quantifiers thus provide a way of defining a context for free identifiers.

• The expression

  ∃I ∈  {11,12,13}IsOdd(I)

  is indeed true as it is equivalent to the proposition:

  IsOdd(11) ∨IsOdd(12) ∨IsOdd(13)

• The reason that quantifiers extend the expressive power of the logic is that the sets in the constraint of a quantified expression can be infinite. Such an expression abbreviate a disjunction which could never be completely written. For example:

  ∃I ∈ ℕ₁ IsPrime(I)

  or:

  ∃I ∈ ℕ₁ ¬IsPrime(2^I − 1)

  express facts about prime numbers.

• Universal Quantifiers. Denoted by ∀ and is read as “for all...”.

• Just as a disjunction can be viewed as an existentially quantified expression, a conjunction such as:

  IsEven(2) ∧IsEven(4) ∧IsEven(8)

  can be written as a universally quantified expression:

  ∀I ∈{2,4,8}IsEven(I)

• here again, universal quantification increase the expressive power of the logic when we deal with infinite sets:

  ∀I ∈ ℕ IsEven(2 ∗ I)

• We can now formally define IsPrime as

  IsPrime(I) ≜	I≠1 ∧
  	∀D ∈ ℕ1 D divides I ⊃ D = 1 ∨ D = I