Sets, logic and maths for computing

Description

This easy-to-follow textbook introduces the mathematical language, knowledge and problem-solving skills that undergraduates need to study computing. The language is in part qualitative, with concepts such as set, relation, function and recursion/induction; but it is also partly quantitative, with principles of counting and finite probability. Entwined with both are the fundamental notions of logic and their use for representation and proof. Features: teaches finite math as a language for thinking, as much as knowledge and skills to be acquired; uses an intuitive approach with a focus on examples for all general concepts; brings out the interplay between the qualitative and the quantitative in all areas covered, particularly in the treatment of recursion and induction; balances carefully the abstract and concrete, principles and proofs, specific facts and general perspectives; includes highlight boxes that raise common queries and clear confusions; provides numerous exercises, with selected solutions.  Read more... Abstract: This easy-to-follow book introduces the mathematical language, knowledge and problem-solving skills needed for the study of computing. The language is both qualitative and quantitative, and includes basic notions of logic used for representation and proof.  Read more... Content: Sets, Logic and Mathsfor Computing Preface For the Student What Is in This Book? How Should You Use It? For the Instructor Manner of Presentation Choice of Topics Courses Outside Computer Science The Second Edition Acknowledgements Contents List of Figures 1 Collecting Things Together: Sets 1.1 The Intuitive Concept of a Set 1.2 Basic Relations Between Sets 1.2.1 Inclusion 1.2.2 Identity and Proper Inclusion 1.2.3 Diagrams 1.2.4 Ways of Defining a Set 1.3 The Empty Set 1.3.1 Emptiness 1.3.2 Disjoint Sets 1.4 Boolean Operations on Sets 1.4.1 Intersection 1.4.2 Union -- 1.4.3 Difference and Complement1.5 Generalized Union and Intersection 1.6 Power Sets Selected Reading 2 Comparing Things: Relations 2.1 Ordered Tuples, Cartesian Products and Relations 2.1.1 Ordered Tuples 2.1.2 Cartesian Products 2.1.3 Relations 2.2 Tables and Digraphs for Relations 2.2.1 Tables 2.2.2 Digraphs 2.3 Operations on Relations 2.3.1 Converse 2.3.2 Join, Projection, Selection 2.3.3 Composition 2.3.4 Image 2.4 Reflexivity and Transitivity 2.4.1 Reflexivity 2.4.2 Transitivity 2.5 Equivalence Relations and Partitions 2.5.1 Symmetry 2.5.2 Equivalence Relations -- 2.5.3 Partitions2.5.4 The Partition/Equivalence Correspondence 2.6 Relations for Ordering 2.6.1 Partial Order 2.6.2 Linear Orderings 2.6.3 Strict Orderings 2.7 Closing with Relations 2.7.1 Transitive Closure of a Relation 2.7.2 Closure of a Set Under a Relation Selected Reading 3 Associating One Item with Another:Functions 3.1 What Is a Function? 3.2 Operations on Functions 3.2.1 Domain and Range 3.2.2 Restriction, Image, Closure 3.2.3 Composition 3.2.4 Inverse 3.3 Injections, Surjections, Bijections 3.3.1 Injectivity 3.3.2 Surjectivity 3.3.3 Bijective Functions -- 3.4 Using Functions to Compare Size3.4.1 Equinumerosity 3.4.2 Cardinal Comparison 3.4.3 The Pigeonhole Principle 3.5 Some Handy Functions 3.5.1 Identity Functions 3.5.2 Constant Functions 3.5.3 Projection Functions 3.5.4 Characteristic Functions 3.6 Families and Sequences 3.6.1 Families of Sets 3.6.2 Sequences and Suchlike Selected Reading 4 Recycling Outputs as Inputs: Induction and Recursion 4.1 What Are Induction and Recursion? 4.2 Proof by Simple Induction on the Positive Integers 4.2.1 An Example 4.2.2 The Principle Behind the Example -- 4.3 Definition by Simple Recursion on the Positive Integers4.4 Evaluating Functions Defined by Recursion 4.5 Cumulative Induction and Recursion 4.5.1 Cumulative Recursive Definitions 4.5.2 Proof by Cumulative Induction 4.5.3 Simultaneous Recursion and Induction 4.6 Structural Recursion and Induction 4.6.1 Defining Sets by Structural Recursion 4.6.2 Proof by Structural Induction 4.6.3 Defining Functions by Structural Recursion on Their Domains 4.7 Recursion and Induction on Well-Founded Sets* 4.7.1 Well-Founded Sets 4.7.2 Proof by Well-Founded Induction.