Discrete Mathematics

An introductory course in discrete mathematics for mathematics and computer science majors. It covers fundamental topics such as logic, sets, proof techniques, algorithms, number theory, combinatorics, graph theory, and automata. The course emphasizes mathematical reasoning and problem-solving skills necessary for advanced study in computer science.

Master the logic and structures that form the foundation of computer science.

Author: Richard Johnsonbaugh

Acknowledgments: Reviewers including Venkata Dinavahi, Matthew Elsey, Christophe Giraud-Carrier, Yevgeniy Kovchegov, Filix Maisch, Tyler McMillen, Christopher Storm, Donald Vestal, and Guanghua Zhao. Support from Pearson staff: Deirdre Lynch, Jeff Weidenaar, Lauren Morse, and others.

1. Perform operations on sets, including differences and complements, and verify set identities using Venn diagrams and Theorem 1.1.22.
2. Construct and evaluate truth tables for propositions involving negation, disjunction, and conditional statements.
3. Apply rules of inference and deductive reasoning to determine the validity of logical arguments.
4. Define and apply components of a mathematical system, including axioms, definitions, and theorems.
5. Construct direct proofs, proofs by contradiction, and proofs by cases for algebraic and set-theoretic propositions.
6. Utilize the Principle of Mathematical Induction and Strong Induction to prove identities, divisibility properties, and algorithmic correctness.
7. Define and classify functions (injective, surjective, bijective) and perform operations such as composition and inversion.
8. Apply sequence notation, string concatenation, and recursive rules to model discrete data sets.
9. Analyze binary relations for properties like reflexivity, symmetry, and transitivity using both digraphs and matrix representations.
10. Define an algorithm and verify its seven core properties (Input, Output, Precision, Determinism, Finiteness, Correctness, and Generality).