Discrete Mathematics for Computing

by Haggarty, Rod

• ISBN13: 9780201730470
• ISBN10: 0201730472
• Edition: 1st
• Format: Paperback
• Copyright: 2002-01-01
• Publisher: Addison Wesley

Summary

This book is a short, concise introduction to key mathematical ideas for computing students which develops their understanding of discrete mathematics and its application in computing. The topics are presented in a well defined, logical order that build upon each other and are constantly reinforced by worked examples. Reliance on students' previous mathematical experience is kept to a minimum, though some basic algebraic manipulation is required. This book is appropriate for CS and Math students in an undergraduate Discrete Math course. The content constitutes an accepted core of mathematics for computer scientists (for example, the formal methods used in computer science draw heavily on the discrete methematical concepts covered here, particularly logic, sets, relations and functions). Emphasis is placed on clear and careful explanations of basic ideas and on building confidence in developing mathematical competence through carefully selected exercises. All chapters conclude with short applications/case studies relevant to computing, which provide further motivation to engage with the mathematical ideas involved, and also demonstrate how the mathematics can be applied in a computing context.

Table of Contents

Preface	viii
List of symbols	x
Introduction	1	(13)
Modelling	1	(4)
Pseudocode	5	(9)
Exercise set 1	9	(3)
Chapter summary	12	(2)
Logic and proof	14	(20)
Propositions and logic	14	(5)
Predicates and quantifiers	19	(2)
Methods of proof	21	(2)
Mathematical induction	23	(11)
Exercise set 2	26	(2)
Chapter summary	28	(1)
Application: Correctness of algorithms	29	(5)
Set theory	34	(22)
Sets and set operations	34	(6)
The algebra of sets	40	(2)
Further properties of sets	42	(14)
Exercise set 3	47	(2)
Chapter summary	49	(2)
Application: Knowledge-based systems	51	(5)
Relations	56	(21)
Binary relations	56	(5)
Properties of relations	61	(3)
Equivalence relations and partial orders	64	(13)
Exercise set 4	68	(2)
Chapter summary	70	(1)
Application: Database management systems	71	(6)
Functions	77	(24)
Inverse relations and composition of relations	77	(5)
Functions	82	(5)
Inverse functions and composition of functions	87	(3)
The pigeonhole principle	90	(11)
Exercise set 5	93	(3)
Chapter summary	96	(1)
Application: Functional programming languages	97	(4)
Combinatorics	101	(20)
The addition and multiplication principles	101	(2)
Counting formulae	103	(6)
The binomial expansion	109	(12)
Exercise set 6	113	(2)
Chapter summary	115	(1)
Application: Efficiency of algorithms	116	(5)
Graphs	121	(28)
Graphs and terminology	121	(6)
Hamiltonian graphs	127	(4)
Trees	131	(18)
Exercise set 7	137	(4)
Chapter summary	141	(2)
Application: Sorting and searching	143	(6)
Directed graphs	149	(21)
Directed graphs	149	(4)
Paths in digraphs	153	(4)
Shortest paths	157	(13)
Exercise set 8	161	(3)
Chapter summary	164	(1)
Application: Communications networks	165	(5)
Boolean algebra	170	(21)
Boolean algebra	170	(5)
Karnaugh maps	175	(4)
Logic circuits	179	(12)
Exercise set 9	182	(3)
Chapter summary	185	(1)
Application: Designing a 2-bit adder	186	(5)
Solutions	191	(41)
Further reading	232	(1)
Index	233