Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2020 | Book

Collecting Things Together: Sets Read chapter Read first chapter

Sets, Logic and Maths for Computing

Author: Prof. David Makinson

Publisher: Springer International Publishing

Book Series : Undergraduate Topics in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This easy-to-understand textbook introduces the mathematical language and problem-solving tools essential to anyone wishing to enter the world of computer and information sciences. Specifically designed for the student who is intimidated by mathematics, the book offers a concise treatment in an engaging style.

The thoroughly revised third edition features a new chapter on relevance-sensitivity in logical reasoning and many additional explanations on points that students find puzzling, including the rationale for various shorthand ways of speaking and ‘abuses of language’ that are convenient but can give rise to misunderstandings. Solutions are now also provided for all exercises.

Topics and features: presents an intuitive approach, emphasizing how finite mathematics supplies a valuable language for thinking about computation; discusses sets and the mathematical objects built with them, such as relations and functions, as well as recursion and induction; introduces core topics of mathematics, including combinatorics and finite probability, along with the structures known as trees; examines propositional and quantificational logic, how to build complex proofs from simple ones, and how to ensure relevance in logic; addresses questions that students find puzzling but may have difficulty articulating, through entertaining conversations between Alice and the Mad Hatter; provides an extensive set of solved exercises throughout the text.

This clearly-written textbook offers invaluable guidance to students beginning an undergraduate degree in computer science. The coverage is also suitable for courses on formal methods offered to those studying mathematics, philosophy, linguistics, economics, and political science. Assuming only minimal mathematical background, it is ideal for both the classroom and independent study.

Table of Contents

Frontmatter

Sets

Frontmatter
1. Collecting Things Together: Sets
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.
David Makinson
2. Comparing Things: Relations
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.
David Makinson
3. Associating One Item with Another: Functions
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.
David Makinson
4. Recycling Outputs as Inputs: Induction and Recursion
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.
David Makinson

Maths

Frontmatter
5. Counting Things: Combinatorics
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.
David Makinson
6. Weighing the Odds: Probability
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.
David Makinson
7. Squirrel Math: Trees
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.
David Makinson

Logic

Frontmatter
8. Yea and Nay: Propositional Logic
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.
David Makinson
9. Something About Everything: Quantificational Logic
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.
David Makinson
10. Just Supposing: Proof and Consequence
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.
David Makinson
11. Sticking to the Point: Relevance in Logic
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.
David Makinson
Backmatter
Metadata
Title
Sets, Logic and Maths for Computing
Author
Prof. David Makinson
Copyright Year
2020
Electronic ISBN
978-3-030-42218-9
Print ISBN
978-3-030-42217-2
DOI
https://doi.org/10.1007/978-3-030-42218-9

Premium Partner

    Image Credits