Math A: Discrete Mathematics

The discrete-mathematics module covers logic, sets, relations, proof, recursion, and correctness. Every claim names its quantifiers and assumptions, because one missing condition usually costs more than an extra page of algebra.

Prerequisites

• Be familiar with basic algebra, functions, and integer arithmetic. Sets, logic, and proof methods are introduced here.
• Being able to read simple loops and recursive code helps; consult Volume 1 as needed.

Coverage

Chapters 1–2 establish the language of logic and sets. Chapters 3–4 develop proofs, program correctness, induction, and recurrences. Chapter 5 uses relations and mappings to describe classification, dependencies, and correspondence.

Chapter 1

• 1.1 Propositional Logic: From Requirement Sentences to Decidable Formulas
• 1.2 Logical Equivalence, Normal Forms, and SAT: Letting Machines Search for Solutions
• 1.3 Predicate Logic: Objects, Quantifiers, and Program Specifications

Chapter 2

• 2.1 Sets and Operations: Describing Object Scope via Membership
• 2.2 Power Sets, Cartesian Products, and Cardinality: How Sets Construct New Spaces
• 2.3 Sets in Software Systems: Data Structures, SQL, and Approximate Membership Queries

Chapter 3

• 3.1 Direct Proof, Contrapositive, and Case Analysis: Building Verifiable Reasoning Chains
• 3.2 Counterexamples, Proof by Contradiction, and Existence: Knowing Whether to Find One or Rule Out All
• 3.3 Program Correctness: Specifications, Loop Invariants, and Termination

Chapter 4

• 4.1 Recursive Definitions and Mathematical Induction: Proving Along the Construction Process
• 4.2 Recurrence Relations: Expansion, Summation, and Characteristic Equations
• 4.3 Divide-and-Conquer Recurrence and Master Theorem: First Verify the Model, Then Apply the Result

Chapter 5

• 5.1 Binary Relations: Properties, Composition, and Closure
• 5.2 Equivalence Relations and Partial Orders: Classification, Dependencies, and Lattices
• 5.3 Functions and Mappings: Domain, Image, Injectivity, and Bijectivity

Outcomes

• Translate conditions into logical formulas, check quantifier scope, and construct counterexamples.
• Give invariants, induction steps, and termination arguments for loops or recursive programs.
• Use sets, relations, and functions to describe object ranges, equivalence classes, and dependency orders.

How to use this map

If proofs are new, start with logic and sets and read in order. Try small examples for each claim, then examine why the reasoning covers every relevant object. For algorithm prerequisites, focus on Chapters 3–4. Return to the definitions when a condition is unclear; memorizing the layout of a proof will only get you so far.