Discrete Mathematics Using a Computer

Several areas of mathematics find application throughout computer science, and all students of computer science need a practical working understanding of them. These core subjects are centred on logic, sets, recursion, induction, relations and functions. The material is often called discrete mathematics, to distinguish it from the traditional topics of continuous mathematics such as integration and differential equations. The central theme of this book is the connection between computing and discrete mathematics. This connection is useful in both directions: • Mathematics is used in many branches of computer science, in applica­ tions including program specification, datastructures,design and analysis of algorithms, database systems, hardware design, reasoning about the correctness of implementations, and much more; • Computers can help to make the mathematics easier to learn and use, by making mathematical terms executable, making abstract concepts more concrete, and through the use of software tools such as proof checkers. These connections are emphasised throughout the book. Software tools (see Appendix A) enable the computer to serve as a calculator, but instead of just doing arithmetic and trigonometric functions, it will be used to calculate with sets, relations, functions, predicates and inferences. There are also special software tools, for example a proof checker for logical proofs using natural deduction. Discrete Mathematics Using a Computer offers a new, "hands-on" approach to teaching Discrete Mathematics. Using software that is freely available on Mac, PC and Unix platforms, the functional language Haskell allows students to experiment with mathematical notations and concepts -- a practical approach that provides students with instant feedback and allows lecturers to monitor progress easily. This second edition of the successful textbook contains significant additional material on the applications of formal methods to practical programming problems. There are more examples of induction proofs on small programs, as well as a new chapter showing how a mathematical approach can be used to motivate AVL trees, an important and complex data structure. Designed for 1st and 2nd year undergraduate students, the book is also well suited for self-study. No prior knowledge of functional programming is required; everything the student needs is either provided or can be picked up easily as they go along. Key features include: • Numerous exercises and examples • A web page with software tools and additional practice problems, solutions, and explanations, as well as course slides • Suggestions for further reading Complete with an accompanying instructor's guide, available via the web, this volume is intended as the primary teaching text for Discrete Mathematics courses, but will also provide useful reading for Conversion Masters and Formal Methods courses. Visit the book’s Web page at: http://www.dcs.gla.ac.uk/~jtod/discrete-mathematics/ Several areas of mathematics find application throughout computer science, and all students of computer science need a practical working understanding of them. These core subjects are centred on logic, sets, recursion, induction, relations and functions. The material is often called discrete mathematics, to distinguish it from the traditional topics of continuous mathematics such as integration and differential equations. The central theme of this book is the connection between computing and discrete mathematics. This connection is useful in both directions: " Mathematics is used in many branches of computer science, in applicaƯ tions including program specification, datastructures, design and analysis of algorithms, database systems, hardware design, reasoning about the correctness of implementations, and much more; " Computers can help to make the mathematics easier to learn and use, by making mathematical terms executable, making abstract concepts more concrete, and through the use of software tools such as proof checkers. These connections are emphasised throughout the book. Software tools (see Appendix A) enable the computer to serve as a calculator, but instead of just doing arithmetic and trigonometric functions, it will be used to calculate with sets, relations, functions, predicates and inferences. There are also special software tools, for example a proof checker for logical proofs using natural deduction "Discrete Mathematics Using a Computer offers a new, "hands-on" approach to teaching Discrete Mathematics. Using software that is freely available on Mac, PC and Unix platforms, a simple functional language allows students to experiment with mathematical notations and concepts - a practical approach that provides students with instant feedback and allows lecturers to monitor progress easily." "Designed for 1st and 2nd year undergraduate students it is ideally suited to self-study. No prior knowledge of Functional Programming is required; everything the student needs is either provided or can be picked up easily as they go along." "Complete with an accompanying instructor's guide, available via the WWW, this volume is intended as the primary teaching text on Discrete Mathematics courses but will also provide useful reading for Conversion Masters and Formal Methods courses."--Jacket. Front Matter....Pages i-xviii Introduction to Haskell....Pages 1-33 Propositional Logic....Pages 35-87 Predicate Logic....Pages 89-109 Set Theory....Pages 111-127 Recursion....Pages 129-145 Inductively Defined Sets....Pages 147-162 Induction....Pages 163-184 Relations....Pages 185-227 Functions....Pages 229-271 Discrete Mathematics in Circuit Design....Pages 273-293 Back Matter....Pages 295-339 Offers a approach to teaching Discrete Mathematics. This volume uses a functional language to allow students to experiment with mathematical notations. It provides students with instant feedback and also allows lecturers to monitor progress. It also includes an Instructors guide, to help lecturers adapt existing courses.