Discrete Mathematics Using a ComputerComputer science abounds with applications of discrete mathematics, yet s- dents of computer science often study discrete mathematics in the context of purely mathematical applications. They have to ?gure out for themselves how to apply the ideas of discrete mathematics to computing problems. It is not easy. Most students fail to experience broad success in this enterprise, which is not surprising, since many of the most important advances in science and engineeringhavebeen, precisely, applicationsofmathematicstospeci?cscience and engineering problems. Tobesure,mostdiscretemathtextbooksincorporatesomeaspectsapplying discrete math to computing, but it usually takes the form of asking students to write programs to compute the number of three-ball combinations there are in a set of ten balls or, at best, to implement a graph algorithm. Few texts ask students to use mathematical logic to analyze properties of digital circuits or computer programs or to apply the set theoretic model of functions to understand higher-order operations. A major aim of this text is to integrate, tightly, the study of discrete mathematics with the study of central problems of computer science. |
Contents
| 3 | |
Equational Reasoning | 37 |
Recursion | 47 |
Induction | 61 |
Trees | 83 |
Propositional Logic | 109 |
Predicate Logic | 163 |
Set Theory 187 | 189 |
Inductively Defined Sets | 207 |
Relations | 223 |
Functions | 267 |
The AVL Tree Miracle | 313 |
Discrete Mathematics in Circuit Design | 355 |
A Software Tools | 377 |
| 431 | |
Other editions - View all
Common terms and phrases
adder algebra algorithm and2 application argument balanced binary relation BinLeaf BinNode BinTree bitValue Bool Boolean calculate Cel k d Cel x a lf Cely blf Celz circuit closure codomain concat contains data item dataElems defined definition diagram Digraph discrete mathematics domain elements equational reasoning evaluate example Exercise expression False False False True Figure finite number foldl foldr formal formula functional programming getItem graph Haskell height imp1 implication inference rules infinite inorder t2 input Integer left subtree length xs list comprehension map f natural deduction natural numbers node notation operator ordered pairs predicate logic programming languages proof properties propositional logic prove recursion reflexive result right subtree says search tree string subset surjective tree induction True False True True True truth table variables well-formed formula WFFs wordValue Write a function x a lf rt