## Mathematical Foundations of Computer ScienceMathematical Foundations of Computer Science, Volume I is the first of two volumes presenting topics from mathematics (mostly discrete mathematics) which have proven relevant and useful to computer science. This volume treats basic topics, mostly of a set-theoretical nature (sets, functions and relations, partially ordered sets, induction, enumerability, and diagonalization) and illustrates the usefulness of mathematical ideas by presenting applications to computer science. Readers will find useful applications in algorithms, databases, semantics of programming languages, formal languages, theory of computation, and program verification. The material is treated in a straightforward, systematic, and rigorous manner. The volume is organized by mathematical area, making the material easily accessible to the upper-undergraduate students in mathematics as well as in computer science and each chapter contains a large number of exercises. The volume can be used as a textbook, but it will also be useful to researchers and professionals who want a thorough presentation of the mathematical tools they need in a single source. In addition, the book can be used effectively as supplementary reading material in computer science courses, particularly those courses which involve the semantics of programming languages, formal languages and automata, and logic programming. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Relations and Functions | 23 |

Partially Ordered Sets | 127 |

Induction | 177 |

Copyright | |

2 other sections not shown

### Common terms and phrases

alphabet applied argument assume axiom of choice basis rule basis step bijection chain closure contains Corollary countable define a function denote digraph disjoint endloop equal equivalence Example Exercise exists family of constructors finite set function g G pi give given Godel number goto graph Hasse diagram hence implies induction hypothesis inductive definition inductive rule inductive step infinite sequence injection integer inverse language least element least fixed point loop mapping matrix monotonic function multiset n-ary natural numbers nonempty notation obtained one-to-one ordered pairs partial function partial recursive Peano structure poset poset M,p primitive recursive functions Proof propositional logic Prove recursive definition relation satisfies Seq(N statement strict partial order strong induction structural induction subset Suppose surjection symbols Theorem transitive true tuples unique readability condition upper bound variable vertex VSPL program well-ordering well-ordering principle words