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.
Lessons
Lesson
This lesson introduces the fundamental principles of set theory, emphasizing that sets are unordered collections defined by their members rather than their sequence. It explores how set operations like union, intersection, and power sets function as the structural foundations for logical operators and deductive reasoning.
This lesson explores the anatomy of a mathematical system, explaining how undefined terms, axioms, definitions, and proofs form a logical hierarchy to establish truth. Students will learn how these foundational components prevent circular reasoning and serve as the basis for constructing theorems, lemmas, and corollaries.
This lesson explores the fundamental principles of mathematical mappings, defining functions as precise, deterministic relationships between domains and codomains. Students will learn to evaluate algorithmic correctness using loop invariants and apply discrete structures like sequences and relations to model computational data.
This lesson introduces the fundamental definition of an algorithm as a finite, deterministic, and general sequence of steps used to solve a specific class of problems. Students will learn to verify algorithmic logic through pseudocode and manual tracing while exploring mathematical concepts like divisibility that underpin effective problem-solving.
This lesson explores the transition from continuous calculus to discrete mathematics, highlighting how number theory and prime factorization provide the foundation for modern cryptographic systems like RSA. Students will learn to apply mathematical induction for algorithmic verification and master the mechanics of divisibility to understand the security of one-way "trapdoor" functions.
This lesson introduces the fundamental principles of counting, teaching students how to use the Addition Principle for mutually exclusive choices and the Multiplication Principle for successive, independent steps. By mastering these rules and techniques like complementary counting, students learn to efficiently determine the size of finite sets and solve complex combinatorial problems.
This lesson explores recurrence relations as a framework for modeling combinatorial sequences, such as Stirling and Catalan numbers, and analyzing the efficiency of algorithms like binary search and selection sort. Students will learn to solve linear homogeneous relations using characteristic equations and apply recursive modeling to complex problems like the Tower of Hanoi and derangements.
This lesson introduces the fundamentals of graph theory, defining graphs as sets of vertices and edges used to model complex networks and connectivity. Students will learn to identify graph types, analyze paths and subgraphs, and apply the Handshaking Lemma to solve structural problems.
This lesson introduces the fundamental concepts of tree structures in graph theory, covering the distinction between free and rooted trees and the hierarchical terminology used to describe them. Students will learn how these mathematical models serve as essential frameworks for organizing data and solving complex optimization problems in real-world applications.
This lesson introduces transport networks as directed, weighted graphs defined by a source with no incoming edges, a sink with no outgoing edges, and non-negative capacities on all edges. Students learn to distinguish between these structural capacity limits and the actual flow of commodities through a system.
This lesson explores combinatorial logic, defining it as a system where circuit outputs are determined solely by current inputs without the use of memory or feedback. Students learn to map Boolean algebraic expressions directly onto physical circuit topologies using structural induction, operator precedence, and efficient n-input gate designs.
This lesson introduces sequential logic by distinguishing it from memoryless combinatorial circuits through the use of unit time delays and feedback loops. Students will learn how these components enable the creation of finite-state machines, which allow systems to store information and base future outputs on past states.
Course Overview
📚 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
- 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.
- 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.
- 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.
- Define an algorithm and verify its seven core properties (Input, Output, Precision, Determinism, Finiteness, Correctness, and Generality).
Lessons
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.
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.
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.
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.
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).
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.
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.
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.
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.
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.
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).
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.