## Discrete Mathematics: Proof Techniques and Mathematical StructuresThis book offers an introduction to mathematical proofs and to the fundamentals of modern mathematics. No real prerequisites are needed other than a suitable level of mathematical maturity. The text is divided into two parts, the first of which constitutes the core of a one-semester course covering proofs, predicate calculus, set theory, elementary number theory, relations, and functions, and the second of which applies this material to a more advanced study of selected topics in pure mathematics, applied mathematics, and computer science, specifically cardinality, combinatorics, finite-state automata, and graphs. In both parts, deeper and more interesting material is treated in optional sections, and the text has been kept flexible by allowing many different possible courses or emphases based upon different paths through the volume. |

### What people are saying - Write a review

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

### Contents

PART | 1 |

Part B Methods of Proof | 24 |

Predicate Calculus | 45 |

Set Theory | 93 |

Elementary Number Theory | 151 |

Relations | 179 |

Functions | 259 |

Cardinality | 313 |

Elements of Combinatorics | 341 |

Languages and Finite State Automata | 383 |

Graphs | 425 |

Hamiltonian and Eulerian Paths | 438 |

Connectivity Matching and Coloring | 446 |

Suggestions for Further Reading | 455 |

### Other editions - View all

### Common terms and phrases

actually Algorithm alphabet arbitrary Aſh Axiom of Choice basic basis step bi-implications bijection binary operation binary relation called cardinality Cartesian product codomain collection composition compute concatenation conclude consider corresponding countable cycle define denote digraph discussion disjoint divisor equation equivalence relation EXERCISES fact finite sets finite state automaton function f Furthermore given graph G identity implication inclusion induction hypothesis induction step inductive definition injection instance integer inverse language lattice least element Lemma linear ordering logically equivalent mathematics monoid natural numbers non-empty notation ordered pair parentheses partial ordering partition polynomials poset predicate calculus predicate form previous example prime proof propositional form propositional variables Prove your assertions R C A reader real numbers recursion reflexive regular expression result sequence set theory simply subset Suppose that f surjective symbol symmetric THEOREM Suppose transitive truth table truth values vertex vertices words