### IV.1 Introduction

#### Quantiﬁers [Slide 110]

• Quantiﬁers extend the expressive power of the logical notation but can be motivated as abbreviations.
• Existential quantiﬁer. This is denoted by and is read as “there exists a...”

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

This quantiﬁed expression can be read as:

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

• The I is the bound identiﬁer, the I ∈ {  } is the constraint and the expression after the dot is the body of the quantiﬁed expression.
• Any free occurrences of the bound identiﬁer within the body become bound in the quantiﬁed expression. All such occurrences refer to the bound identiﬁer. The quantiﬁers thus provide a way of deﬁning a context for free identiﬁers.
• 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 quantiﬁers extend the expressive power of the logic is that the sets in the constraint of a quantiﬁed expression can be inﬁnite. Such an expression abbreviate a disjunction which could never be completely written. For example:

I 1 IsPrime(I)

or:

I 1 ¬IsPrime(2I 1)

• Universal Quantiﬁers. Denoted by and is read as “for all...”.
• Just as a disjunction can be viewed as an existentially quantiﬁed expression, a conjunction such as:

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

can be written as a universally quantiﬁed expression:

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

• here again, universal quantiﬁcation increase the expressive power of the logic when we deal with inﬁnite sets:

I IsEven(2 I)

• We can now formally deﬁne IsPrime as

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

 2018-03-10 Contact | Home | ITL home | Course | Proofs | Algebra | FL