© 1996-2018

IV.1 Introduction

Quantifiers [Slide 110]

  • 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 1 IsPrime(I)


    I 1 ¬IsPrime(2I 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) I1 D 1 D divides I D = 1 D = I

Contact | Home | ITL home | Course | Proofs | Algebra | FL