Discrete Mathematics

📚 Content Summary

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.

🎯 Learning Objectives

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).

🔹 Lesson 1: Foundations of Logic and Set Theory

Overview: This lesson establishes the fundamental building blocks of discrete mathematics, focusing on the rigorous manipulation of sets and the formal structures of logic. Students will progress from set operations and identities to the construction of logical arguments, the evaluation of conditional propositions, and the analysis of nested quantifiers. These concepts provide the essential framework for algorithm design, database theory, and formal verification in computer science and engineering.

Learning Outcomes:

• Perform operations on sets, including differences and complements, and verify set identities using Venn diagrams and Theorem 1.1.22.
• Construct and evaluate truth tables for propositions involving negation, disjunction, and conditional statements.
• Apply rules of inference and deductive reasoning to determine the validity of logical arguments.

🔹 Lesson 2: Mathematical Proof Techniques

Overview: This lesson covers the formal methodologies used to establish the validity of mathematical statements and the logical rigor required in computer science and mathematics. Students will progress from foundational mathematical systems and direct proofs to sophisticated techniques such as resolution proofs, mathematical induction (including strong induction), and the application of loop invariants in algorithmic verification.

Learning Outcomes:

• Define and apply components of a mathematical system, including axioms, definitions, and theorems.
• Construct direct proofs, proofs by contradiction, and proofs by cases for algebraic and set-theoretic propositions.
• Utilize the Principle of Mathematical Induction and Strong Induction to prove identities, divisibility properties, and algorithmic correctness.

🔹 Lesson 3: Functions, Sequences, and Relations

Overview: This lesson covers the fundamental mathematical structures used to model data and processes in computer science. It progresses from the definition of functions and their various types (injective, surjective, bijective) to the study of sequences, strings, and the formal properties of binary relations. Students will explore practical applications such as hash functions, ISBN check digits, task scheduling via partial orders, and the representation of relations through matrices and databases.

Learning Outcomes:

• Define and classify functions (injective, surjective, bijective) and perform operations such as composition and inversion.
• Apply sequence notation, string concatenation, and recursive rules to model discrete data sets.
• Analyze binary relations for properties like reflexivity, symmetry, and transitivity using both digraphs and matrix representations.

🔹 Lesson 4: Algorithm Analysis and Complexity

Overview: This lesson covers the fundamental definition and properties of algorithms, their implementation in searching and sorting (specifically Text Search and Insertion Sort), and the rigorous mathematical frameworks used to analyze their efficiency. Students will explore asymptotic notations, growth rates of functions, and the mechanics of recursive problem-solving, including divide-and-conquer strategies like board tiling and Fibonacci-based sequences.

Learning Outcomes:

• Define an algorithm and verify its seven core properties (Input, Output, Precision, Determinism, Finiteness, Correctness, and Generality).
• Apply Big-O, Omega, and Theta notations to express the time and space complexity of algorithms.
• Analyze best-case, worst-case, and average-case scenarios using techniques like repeated halving and polynomial ordering.

🔹 Lesson 5: Introduction to Number Theory and Cryptography

Overview: This lesson explores the foundational principles of number theory, ranging from the basic properties of divisors and primes to the complex algorithms that underpin modern secure communications. Students will master the mathematical mechanics of greatest common divisors (GCD), base conversions, and modular exponentiation to understand and implement the RSA public-key cryptosystem.

Learning Outcomes:

• Define and apply the concepts of divisibility, primality, and the Fundamental Theorem of Arithmetic.
• Perform efficient conversions between decimal, binary, and hexadecimal number systems.
• Execute the Euclidean Algorithm and its extended form to find GCDs and linear combinations (sa + tb).

🔹 Lesson 6: Counting Methods and Discrete Probability

Overview: This lesson explores the fundamental techniques for counting finite structures and the application of these techniques to discrete probability. Students will progress from basic addition and multiplication principles to advanced concepts like Catalan numbers, Stirling numbers, and the Binomial Theorem. The lesson concludes with the Pigeonhole Principle and its various forms, providing a rigorous framework for proving the existence of specific configurations in discrete systems.

Learning Outcomes:

• Apply the Addition, Multiplication, and Inclusion-Exclusion Principles to solve complex counting problems.
• Differentiate between and calculate permutations and combinations, including cases with identical objects and repetitions.
• Utilize generating algorithms for permutations and combinations in lexicographical order.

🔹 Lesson 7: Recurrence Relations

Overview: This lesson explores the theory and application of recurrence relations in mathematics and computer science. Students will learn to solve these relations using iteration and characteristic equations for both homogeneous and inhomogeneous forms. Furthermore, the lesson demonstrates how recurrence relations are essential tools for analyzing the time complexity of recursive algorithms like Selection Sort, Binary Search, and Merge Sort.

Learning Outcomes:

• Solve recurrence relations using the Iteration Method and Characteristic Equations (for distinct and equal roots).
• Model and solve classic mathematical problems, including the Tower of Hanoi, Fibonacci Sequence (Golden Ratio), and Derangements.
• Analyze the worst-case time complexity of recursive algorithms using recurrence relations.

🔹 Lesson 8: Graph Theory and Shortest-Path Algorithms

Overview: This lesson explores the foundational principles of Graph Theory, ranging from basic definitions of simple and weighted graphs to complex algorithmic solutions for shortest paths and cycle identification. Students will examine structural properties like planarity, connectivity, and isomorphism while applying these concepts to classic problems such as the Königsberg Bridge problem, the Traveling Salesperson Problem (TSP), and the Instant Insanity puzzle.

Learning Outcomes:

• Define and differentiate between graph types, including simple, weighted, complete, bipartite, and n-cubes.
• Analyze graph connectivity to identify Euler cycles, Hamiltonian cycles, and determine shortest paths using Dijkstra's algorithm.
• Apply matrix representations (adjacency and incidence) and graph invariants to verify isomorphisms and planarity.

🔹 Lesson 9: Trees and Search Algorithms

Overview: This lesson covers the fundamental properties, characterizations, and applications of trees in computer science and mathematics. Students will explore rooted and binary trees, spanning tree algorithms (BFS/DFS), optimization techniques like Prim’s algorithm for minimal spanning trees, and decision-making frameworks including backtracking, tournament sorts, and game trees with the minimax procedure.

Learning Outcomes:

• Define and identify rooted trees, their levels, height, and hierarchical structures in real-world systems.
• Characterize trees based on connectivity, acyclicity, and edge-to-vertex ratios.
• Implement and trace algorithms for spanning trees (BFS, DFS), Minimal Spanning Trees (Prim’s), and Binary Search Tree construction.

🔹 Lesson 10: Network Models and Flow Optimization

Overview: This lesson covers the mathematical modeling of transport networks, focusing on how resources (flow) move through a directed graph from a source to a sink. It details the rules of flow conservation, the algorithmic steps to maximize throughput, the relationship between network cuts and flow capacity, and the application of these principles to solve matching problems in bipartite graphs.

Learning Outcomes:

• Define and verify the properties of a transport network and valid flow assignments.
• Execute the Maximal Flow Algorithm (Algorithm 10.2.4) to find optimal throughput.
• Apply the Max Flow-Min Cut Theorem to prove flow optimality using network partitions.

🔹 Lesson 11: Boolean Algebra and Logic Circuits

Overview: This lesson explores the mathematical foundations of digital logic, focusing on how Boolean algebra provides a formal language for designing and simplifying combinatorial circuits. Students will learn to translate between logic gates, switching circuits, and Boolean expressions, ultimately applying these tools to synthesize complex functions and construct essential arithmetic components like adders and 2's complement logic.

Learning Outcomes:

• Design and analyze combinatorial circuits using standard logic gates (AND, OR, NOT) and switching configurations.
• Apply the laws of Boolean algebra and the Dual Theorem to prove circuit equivalence and simplify expressions.
• Synthesize Boolean functions from truth tables into Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF).

🔹 Lesson 12: Automata, Grammars, and Formal Languages

Overview: This lesson explores the mathematical foundations of computation, starting with sequential circuits and finite-state machines that model internal memory via unit time delays. It covers the formal definition and classification of phrase-structure grammars (Types 1, 2, and 3), the application of Backus Normal Form (BNF), and the specialized use of Lindenmayer grammars for fractal generation. Finally, it establishes the critical relationship between deterministic and nondeterministic finite-state automata and the formal languages they accept.

Learning Outcomes:

• Analyze and design finite-state machines (FSM) and automata (FSA/NFA) using transition diagrams and state functions.
• Classify grammars within the Chomsky hierarchy and derive strings using production rules and BNF notation.
• Model self-similar structures like the von Koch snowflake using Lindenmayer grammars and simultaneous replacement rules.