Discrete Mathematics Using a ComputerSeveral 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. |
Contents
1 | |
2 | |
Inductively Defined Sets | 6 |
1 | 18 |
Predicate Logic | 91 |
Set Theory | 111 |
Recursion | 131 |
Relations | 189 |
100 | 238 |
109 | 245 |
114 | 253 |
129 | 259 |
Discrete Mathematics in Circuit Design | 273 |
A Software Tools for Discrete Mathematics | 295 |
Bibliography | 331 |
334 | |
Other editions - View all
Discrete Mathematics Using a Computer John O'Donnell,Cordelia Hall,Rex Page Limited preview - 2007 |
Common terms and phrases
algorithms and2 application argument bijective binary relation bit Value Bool calculate called circuit codomain computer science contains defining equation definition Digraph discrete mathematics domain elements evaluate example Exercise expression False False False True Figure finite number foldr following function following theorem formal function that takes graph hand side Haskell Haskell function higher order function imp1 imp2 implement implication induction inference rules infinite input Integer irreflexive length list comprehension loop map f means Modus Ponens natural deduction natural numbers Node notation operator ordered pairs output partial order Peano predicate logic programming languages properties propositional logic prove quasi order R₁ real numbers recursion reflexive returns True says Show software tools specify statement String subset Succ Suppose surjective symmetric transitive closure tree True False True True truth table tuple Write a function Zero