In this chapter, we introduce a uniform notation for quantifiers. We also give rules for manipulating quantifiers and illustrate their use with several examples.
Two quantifers that are particularly important are universal quantification and existential quantification. Additional rules governing such quantifications are also presented.
14.1 DOTDOTDOT AND SIGMAS
Most readers will have encountered the dotdotdot notation already. It is a notation that is rarely introduced properly; mostly, it is just used without explanation as in, for example, “1 + 2 + ... + 20 = 210” and “let x0, x1, ... ,xn be”.
The dotdotdot notation is used when some operation is to be applied to a bag of values in cases where the bag is too large to be enumerated, or the size of the bag is given by some variable. In the case of “1 + 2 + ... + 20 = 210”, the operation is addition and there are twenty values to be enumerated; in the case of “let x0, x1, ... ,xn be”, the operation is sequencing (indicated by commas) and the number of values is given by the variable n.
The dotdotdot notation is convenient in the very simplest cases. But it puts a major burden on the reader, requiring them to interpolate from a few example values to the general term in a bag of values.
The so-called Sigma notation is a well-established notation for continued summations. An example is the sum of the squares of all numbers from 0 ...
Get Algorithmic Problem Solving now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
