Author(s): Harris Kwong
This is a text that covers the standard topics in a sophomore-level course in discrete mathematics: logic, sets, proof techniques, basic number theory, functions, relations, and elementary combinatorics, with an emphasis on motivation. It explains and clarifies the unwritten conventions in mathematics, and guides the students through a detailed discussion on how a proof is revised from its draft to a final polished form. Hands-on exercises help students understand a concept soon after learning it. The text adopts a spiral approach: many topics are revisited multiple times, sometimes from a different perspective or at a higher level of complexity. The goal is to slowly develop students’ problem-solving and writing skills.
A Spiral Workbook for Discrete Mathematics
PDF 2MB
1.1 An Overview
1.2 Suggestions to Students
1.3 How to Read and Write Mathematics
1.4 Proving Identities
2.1 Propositions
2.2 Conjunctions and Disjunctions
2.3 Implications
2.4 Biconditional Statements
2.5 Logical Equivalences
2.6 Logical Quantifiers
3.1 An Introduction to Proof Techniques
3.2 Direct Proofs
3.3 Indirect Proofs
3.4 Mathematical Induction: An Introduction
3.5 More on Mathematical Induction
3.6 Mathematical Induction: The Strong Form
4.1 An Introduction
4.2 Subsets and Power Sets
4.3 Unions and Intersections
4.4 Cartesian Products
4.5 Index Sets
5.1 The Principle of Well-Ordering
5.2 Division Algorithm
5.3 Divisibility
5.4 Greatest Common Divisors
5.5 More on GCD
5.6 Fundamental Theorem of Arithmetic
5.7 Modular Arithmetic
6.1 Functions: An Introduction
6.2 Definition of Functions
6.3 One-to-One Functions
6.4 Onto Functions
6.5 Properties of Functions
6.6 Inverse Functions
6.7 Composite Functions
7.1 Definition of Relations
7.2 Properties of Relations
7.3 Equivalence Relations
7.4 Partial and Total Ordering
8.1 What is Combinatorics?
8.2 Addition and Multiplication Principles
8.3 Permutations
8.4 Combinations
8.5 The Binomial Theorem