Sets, Logic and Maths for Computing

In this chapter, we introduce the student to the world of sets. Actually, only a little bit of it, the part that is needed to get going.After giving a rough intuitive idea of what sets are, we present the basic relations between them: inclusion, identity, proper inclusion and exclusion. We describe two common ways of identifying sets and pause to look more closely at the empty set. We then define some basic operations for forming new sets out of old ones: intersection, union, difference and complement. These are often called Boolean operations, after George Boole, who first studied them systematically in the middle of the nineteenth century.Up to this point, the material is all ‘flat’ set theory, in the sense that it does not look at what we can do when the elements of sets are themselves sets. However, we need to go a little beyond flatland. In particular, we need to generalize the notions of intersection and union to cover arbitrary collections of sets and introduce the very important concept of the power set of a set, that is, the set of all its subsets.

Relations play an important role in computer science, both as tools of analysis and for representing computational structures such as databases. In this chapter, we introduce the basic concepts you need to master in order to work with them.We begin with the notions of an ordered pair (and more generally, ordered n-tuple) and the Cartesian product of two or more sets. We then consider operations on relations, notably those of forming the converse, join and composition of relations, as well as some other operations that make relations interact with sets, notably the image and the closure of a set under a relation.We also explore two of the main jobs that relations are asked to carry out: to classify and to order. For the former, we explain the notion of an equivalence relation (reflexive, transitive, symmetric) over a set and how it corresponds to the notion of a partition of the set. For the latter, we look first of all at several kinds of reflexive order, and then at their strict parts.

Functions occur everywhere in mathematics and computer science. In this chapter, we introduce the basic concepts needed in order to work with them.We begin with the intuitive idea of a function and its mathematical definition as a special kind of relation. We then see how the general concepts for relations that were studied in the previous chapter play out in this particular case (domain, range, restriction, image, closure, composition, inverse) and distinguish some important kinds of function (injective, surjective, bijective) with special behaviour.These concepts permit us to link functions with counting, via the equinumerosity, comparison and surprisingly versatile pigeonhole principles. Finally, we identify some very simple kinds of function that appear over and again (identity, constant, projection and characteristic functions) and explain the deployment of functions to represent sequences and families.

This chapter introduces induction and recursion, which are omnipresent in computer science. The simplest context in which they arise is in the domain of the positive integers, and that is where we begin. We explain induction as a method for proving facts about the positive integers, and recursion as a method for defining functions on the same domain. We will also describe two different methods for evaluating such functions.From this familiar terrain, the basic concepts of recursion and induction can be extended to structures, processes and procedures of many kinds, not only numerical ones. Particularly useful for computer scientists are the forms known as structural induction and recursion, and we give them special attention. We will look at structural recursion as a way of defining sets, structural induction as a way of proving things about those sets, and then structural recursion once more as a way of defining functions with recursively defined domains. At this last point, special care is needed, as the definitions of such functions succeed only when a special condition of unique decomposability is satisfied which, happily, is the case in many computer science applications.The broadest and most powerful kind of induction/recursion may be formulated for sets of any kind, provided they are equipped with a relation that is well founded, in a sense we explain. All other kinds may be seen as special cases of that one. In a final section, we look at the notion of a recursive program and see how the ideas that we have developed in the chapter are manifested there.

Up to now, our work has been almost entirely qualitative. The concepts of a set, relation, function, recursion and induction are non-numerical, although they have important numerical applications as, for example, sets of integers or recursive definitions on the natural numbers. In this chapter, we turn to quantitative matters, and specifically to problems of counting. We will tackle two kinds of question.First: Are there rules for determining the number of elements of a large set from the number of elements of smaller ones? Here we will learn how to use two very simple rules: addition (for unions of disjoint sets) and multiplication (for Cartesian products of arbitrary sets).Second: Are there rules for calculating the number of possible selections of k items out of a set with n elements? Here we will see that the question is less straightforward, as there are several different kinds of selection, and they give us very different outcomes. We will untangle four basic modes of selection, give arithmetical formulae for them and practice their application. In the final section, we will turn to the problems of counting rearrangements and configured partitions of a set.

In this chapter, we introduce the elements of probability theory. In the spirit of the book, we confine ourselves to the discrete case, that is, probabilities on finite domains, leaving aside the infinite case.We begin by defining probability functions on a finite sample space and identifying some of their basic properties. So much is simple mathematics. This is followed by some words on different philosophies of probability, and warnings of traps that arise in applications. Then back to the mathematical work, introducing the concept of conditional probability and setting out its properties, its connections with independence and its use in Bayes’ theorem. An interlude presents the curious configurations known as Simpson’s paradox. In the final section, we explain the notions of a payoff function and expected value.

This chapter introduces a kind of structure that turns up everywhere in computer science: trees. We will be learning to speak their language – how to talk about their components, varieties and uses – more than proving things about them. The flavour of the chapter is thus rather different from that of the preceding one on probability: more use of spatial intuition, rather less in the way of demonstration.We begin by looking at trees in their most intuitive form – rooted (alias directed) trees – first of all quite naked and then clothed with labels and finally ordered. Special attention will be given to the case of binary trees and their use in search procedures. Finally, we turn to unrooted (or undirected) trees and their application to span graphs. As always, we remain in the finite case.

We have been using logic on every page of this book – in every proof, verification and informal justification. In the first four chapters, we inserted some ‘logic boxes’; they gave just enough to be able to follow what was being done. Now we gather the material of these boxes together and develop their principles. Logic thus emerges as both a tool for reasoning and an object for study.We begin by explaining different ways of approaching the subject and situating the kind of logic that we will be concerned with, then zooming into a detailed account of classical propositional logic. The basic topics there will be the truth-functional connectives, the family of concepts around tautological implication, the availability of normal forms and unique minimalities for formulae and the use of semantic decomposition trees as a shortcut method for testing logical status.

Although fundamental, the logic of truth-functional connectives has very limited expressive power. In this chapter we go further, explaining the basic ideas of quantificational (alias first-order or again predicate) logic, which is sufficiently expressive to cover most of the deductive reasoning that is carried out in standard mathematics and computer science.We begin by presenting its language, built around the universal and existential quantifiers, and the ways they can be used to express complex relationships. With no more than an intuitive understanding of the quantifiers, some of the basic logical equivalences involving them can already be appreciated. For a deeper understanding, we then present the semantics of the language, which is still bivalent but goes beyond truth tables. This semantics may be given in two versions, substitutional and x-variant, which, however, are equivalent, under a suitable condition, for the basic logical relations. After explaining the distinction between free and bound occurrences of variables, and the notion of a clean substitution, the chapter ends with a review of some of the most important logical implications with quantifiers and with the identity relation.

In the last two chapters, we learned quite a lot about propositional and quantificational logic and in particular their relations of logical implication. In this chapter, we look at how simple implications may be put together to make a deductively valid argument or proof. At first glance, this may seem trivial: just string them together! But although it starts like that, it goes well beyond, and is indeed quite subtle.We begin by looking at the easy process of chaining, which creates elementary derivations, and show how its validity is linked with the Tarski conditions defining consequence relations/operations. We then review several higher-level proof strategies used in everyday mathematics and uncover the logic behind them. These include the strategies traditionally known as conditional proof, disjunctive proof and proof by cases, proof by contradiction and argument to and from an arbitrary instance. Their analysis leads us to distinguish second-level from split-level rules, articulate their recursive structures and explain the informal procedure of flattening a split-level proof into its familiar ‘suppositional’ form.