Sets, Logic and Maths for Computing

Inhaltsverzeichnis

1. Frontmatter

2. Sets

   1. Frontmatter

   2. 1. Collecting Things Together: Sets

      David Makinson

      Abstract

      In this chapter we introduce the student to the world of sets. Actually, only a little bit of it, enough 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 look closely at the empty set, basic Boolean operations, generalized meet and union, and powersets.

   3. 2. Comparing Things: Relations

      David Makinson

      Abstract

      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.

   4. 3. Associating One Item with Another: Functions

      David Makinson

      Abstract

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

   5. 4. Recycling Outputs as Inputs: Induction and Recursion

      David Makinson

      Abstract

      This chapter introduces induction and recursion, which are omnipresent in computer science and logic. 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, and describe two different methods for evaluating such functions. From this familiar terrain, the basic concepts of recursion and induction are extended to the forms known as structural induction and recursion, to which we give special attention. We 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 when a special condition of unique decomposability is satisfied. The broadest kind of induction/recursion may be formulated for any set at all, provided it is equipped with a relation that is well-founded in a sense we explain.

3. Maths

   1. Frontmatter

   2. 5. Counting Things: Combinatorics

      David Makinson

      Abstract

      Up to now, our work has been almost entirely qualitative. The concepts of a set, relation, function, recursion and induction are, in themselves, 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 directly quantitative matters, and specifically to problems of counting. We tackle two topics: rules for determining the number of elements of a large set from the number of elements of smaller sets, rules for calculating the number of possible selections of k items out of a set with n elements.

   3. 6. Weighing the Odds: Probability

      David Makinson

      Abstract

      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, outlining its behaviour, connections with independence, and deployment in Bayes’ rule. An interlude reflects on a curious configuration known as Simpson’s paradox. In the final section we explain the notions of a payoff function and expected value.

   4. 7. Squirrel Math: Trees

      David Makinson

      Abstract

      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 ingredients, varieties and uses—more than proving things about them. The flavour of the chapter, except for its last section, is thus rather different from that of the preceding one on probability: much more use of spatial intuition, rather less in the way of verifications.

4. Logic

   1. Frontmatter

   2. 8. Yea and Nay: Propositional Logic

      David Makinson

      Abstract

      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.

   3. 9. Something About Everything: Quantificational Logic

      David Makinson

      Abstract

      Although fundamental to logic, truth-functional connectives have very limited expressive power. In this chapter we go further, explaining the basic ideas of quantificational logic (also known as first-order or predicate logic), which is sufficiently expressive to cover most of the deductive reasoning that is carried out in standard mathematics and computer science.

   4. 10. Just Supposing: Proof and Consequence

      David Makinson

      Abstract

      In the last two chapters we learned some of the basics of propositional and quantificational logic and, in particular, the relations of logical implication that they provide. In this chapter, we look at how simple logical 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.

   5. 11. Sticking to the Point: Relevance in Logic

      David Makinson

      Abstract

      When presenting classical propositional logic in Chap. 8, we observed that the connective of material implication, defined by its truth-table, makes no claim of any kind of ‘relevance’ between antecedent and consequent; nor does the relation of tautological implication require that premises and conclusion share any content. This leads to some rather surprising results, notably the so-called principles of ‘explosion’. In this chapter, we explore a way of excluding such runaway principles while retaining a logic that is smoothly behaved and easily applied. The basic idea is to adapt the method of truth-trees, from Chap. 8 Sect. 8.5, by imposing syntactic constraints of ‘actual use’ of antecedents and consequents in the production of crash-pairs.

5. Backmatter