Sets, Logic and Maths for Computing

"University studies in computing require the ability to pass from a concrete problem to an abstract representation, reason with the abstract structure, and return with useful solutions to the specific situation." "This easy-to-follow text allows readers to carry out their computing studies with a clear understanding of the basic finite mathematics and logic that they will need. Written explicitly for undergraduates, it requires only a minimal mathematical background and is ideal for self-study as well as classroom use."--BOOK JACKET.

David Makinson is currently Visiting Professor at London School of Economics (LSE). Previous affiliations include the Department of Computer Science at King's College London, UNESCO in Paris, and the American University of Beirut in Lebanon. He is well known for his early research in modal and deontic logics, and more recently in the logic of belief change (as one of the founders of the AGM paradigm) and nonmonotonic reasoning.

Collecting Things Together: Sets	p. 1
The Intuitive Concept of a Set	p. 1
Basic Relations between Sets	p. 2
Inclusion	p. 2
Identity	p. 4
Proper Inclusion	p. 5
Euler Diagrams	p. 6
Venn Diagrams	p. 6
Ways of Defining a Set	p. 7
The Empty Set	p. 11
Emptiness	p. 11
Disjoint Sets	p. 12
Boolean Operations on Sets	p. 12
Intersection	p. 12
Union	p. 14
Difference and Complement	p. 17
Generalised Union and Intersection	p. 20
Power Sets	p. 22
Some Important Sets of Numbers	p. 25
Comparing Things: Relations	p. 29
Ordered Tuples, Cartesian Products, Relations	p. 29
Ordered Tuples	p. 30
Cartesian Products	p. 31
Relations	p. 34
Tables and Digraphs for Relations	p. 36
Tables for Relations	p. 36
Digraphs for Relations	p. 37
Operations on Relations	p. 38
Converse	p. 39
Join of Relations	p. 40
Composition of Relations	p. 42
Image	p. 44
Reflexivity and Transitivity	p. 46
Reflexivity	p. 46
Transitivity	p. 47
Equivalence Relations and Partitions	p. 48
Symmetry	p. 48
Equivalence Relations	p. 49
Partitions	p. 51
The Correspondence between Partitions and Equivalence Relations	p. 52
Relations for Ordering	p. 54
Partial Order	p. 54
Linear Orderings	p. 55
Strict Orderings	p. 56
Closing with Relations	p. 58
Transitive Closure of a Relation	p. 58
Closure of a Set under a Relation	p. 59
Associating One Item with Another: Functions	p. 63
What is a Function?	p. 63
Operations on Functions	p. 66
Domain and Range	p. 66
Image, Restriction, Closure	p. 67
Composition	p. 69
Inverse	p. 70
Injections, Surjections, Bijections	p. 71
Injectivity	p. 71
Surjectivity	p. 72
Bijective Functions	p. 74
Using Functions to Compare Size	p. 75
The Equinumerosity Principle	p. 75
The Principle of Comparison	p. 76
The Pigeonhole Principle	p. 77
Some Handy Functions	p. 79
Identity Functions	p. 79
Constant Functions	p. 80
Projection Functions	p. 81
Characteristic Functions	p. 81
Families of Sets	p. 81
Sequences	p. 82
Recycling Outputs as Inputs: Induction and Recursion	p. 87
What are Induction and Recursion?	p. 88
Proof by Simple Induction on the Positive Integers	p. 89
An Example	p. 89
The Principle behind the Example	p. 90
Definition by Simple Recursion on the Natural Numbers	p. 93
Evaluating Functions Defined by Recursion	p. 96
Cumulative Induction and Recursion	p. 97
Recursive Definitions Reaching Back more than One Unit	p. 97
Proof by Cumulative Induction	p. 99
Simultaneous Recursion and Induction	p. 101
Structural Recursion and Induction	p. 103
Defining Sets by Structural Recursion	p. 103
Proof by Structural Induction	p. 107
Defining Functions by Structural Recursion on their Domains	p. 108
Condition for Defining a Function by Structural Recursion	p. 109
When the Unique Decomposition Condition Fails?	p. 112
Recursion and Induction on Well-Founded Sets	p. 112
Well-Founded Sets	p. 112
The Principle of Proof by Well-Founded Induction	p. 114
Definition of a Function by Well-Founded Recursion on its Domain	p. 116
Recursive Programs	p. 118
Counting Things: Combinatorics	p. 123
Two Basic Principles: Addition and Multiplication	p. 124
Using the Two Basic Principles Together	p. 128
Four Ways of Selecting k Items out of n	p. 128
Counting Formulae: Permutations and Combinations	p. 133
The Formula for Permutations (O+R-)	p. 134
The Formula for Combinations (O-R-)	p. 136
Counting Formulae: Perms and Coms with Repetition	p. 140
The Formula for Permutations with Repetition Allowed (O+R+)	p. 141
The Formula for Combinations with Repetition Allowed (O-R+)	p. 142
Rearrangements and Partitions	p. 144
Rearrangements	p. 144
Counting Partitions with a Given Numerical Configuration	p. 146
Weighing the Odds: Probability	p. 153
Finite Probability Spaces	p. 153
Basic Definitions	p. 154
Properties of Probability Functions	p. 155
Philosophy and Applications	p. 158
Some Simple Problems	p. 161
Conditional Probability	p. 164
Interlude: Simpson's Paradox	p. 171
Independence	p. 172
Bayes' Theorem	p. 176
Random Variables and Expected Values	p. 178
Random Variables	p. 178
Expectation	p. 179
Induced Probability Distributions	p. 181
Expectation Expressed using Induced Probability Functions	p. 183
Squirrel Math: Trees	p. 189
My First Tree	p. 189
Rooted Trees	p. 192
Labelled Trees	p. 198
Interlude: Parenthesis-Free Notation	p. 202
Binary Search Trees	p. 204
Unrooted Trees	p. 209
Definition of Unrooted Tree	p. 210
Properties of Unrooted Trees	p. 211
Finding Spanning Trees	p. 214
Yea and Nay: Propositional Logic	p. 219
What is Logic?	p. 220
Structural Features of Consequence	p. 221
Truth-Functional Connectives	p. 226
Tautologicality	p. 230
The Language of Propositional Logic	p. 230
Assignments and Valuations	p. 231
Tautological Implication	p. 231
Tautological Equivalence	p. 234
Tautologies and Contradictions	p. 237
Normal Forms, Least letter-Sets, Greatest Modularity	p. 240
Disjunctive Normal Form	p. 240
Conjunctive Normal Form	p. 242
Eliminating Redundant Letters	p. 244
Most Modular Representation	p. 245
Semantic Decomposition Trees	p. 247
Natural Deduction	p. 252
Enchainment	p. 253
Second-Level (alias Indirect) Inference	p. 255
Something about Everything: Quantificational Logic	p. 265
The Language of Quantifiers	p. 265
Some Examples	p. 266
Systematic Presentation of the Language	p. 267
Freedom and Bondage	p. 272
Some Basic Logical Equivalences	p. 273
Semantics for Quantificational Logic	p. 276
Interpretations	p. 276
Valuating Terms under an Interpretation	p. 277
Valuating Formulae under an Interpretation: Basis	p. 277
Valuating Formulae under an Interpretation: Recursion Step	p. 278
The x-Variant Reading of the Quantifiers	p. 278
The Substitutional Reading of the Quantifiers	p. 281
Logical Consequence etc	p. 283
Natural Deduction with Quantifiers	p. 289
Index	p. 297
Table of Contents provided by Ingram. All Rights Reserved.

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.