MATHEMATICS: A DISCRETE INTRODUCTION teaches students the fundamental concepts in discrete mathematics and proof-writing skills. With its clear presentation, the text shows students how to present cases logically beyond this course. All of the material is directly applicable to computer science and engineering, but it is presented from a mathematician's perspective. Students will learn that discrete mathematics is very useful, especially those whose interests lie in computer science and engineering, as well as those who plan to study probability, statistics, operations research, and other areas of applied mathematics.
Table of Contents
Joy. Speaking (and Writing) of Mathetimatics. Definition. Theorem. Proof. Counterexample. Boolean Algebra. Self Test.
Lists. Factorial. Sets I: Introduction, Subsets. Quantifiers. Sets II: Operations. Combinatorial Proof: Two Examples. Self Test.
3. COUNTING AND RELATIONS.
Relations. Equivalence Relations. Partitions. Binomial Coefficients. Counting Multisets. Inclusion-Exclusion. Self Test.
4. MORE PROOF.
Contradiction. Smallest Counterexample. Induction. Recurrence Relations. Self Test.
Functions. The Pigeonhole Principle. Composition. Permutations. Symmetry. Assorted Notation. Self Test.
Sample Space. Events. Conditional Probability and Independence. Random Variables. Expectation. Self Test.
7. NUMBER THEORY.
Dividing. Greatest Common Divisor. Modular Arithmetic. The Chinese Remainder Theorem. Factoring. Self Test.
Groups. Group Isomorphism. Subgroups. Fermat's Little Theorem. Public-Key Cryptography I: Introduction. Public-Key Cryptography II: Rabin's Method. Public-Key Cryptography III: RSA. Self Test.
Graph Theory Fundamentals. Subgraphs. Connection. Trees. Eulerian Graphs. Coloring. Planar Graphs. Self Test.
10. PARTIALLY ORDERED SETS.
Partially Ordered Sets Fundamentals. Max and Min. Linear Orders. Linear Extensions. Dimension. Lattices. Self Test.
Lots of Hints and Comments; Some Answers. Solutions to Self Tests. Glossary. Fundamentals.