LECTURE NOTES OF WILLIAM CHEN
DISCRETE MATHEMATICS
This set of notes has been compiled over a period of more than 30 years. Chapters 1 - 4 were used in various forms and on many occasions between 1981 and 1990 by the author at Imperial College, University of London. An extra 14 chapters were written in Sydney in 1991 and 1992. Chapters 7 and 12 were added in 1997.
The material has been organized in such a way to create a single volume suitable for an introduction to the rudiments of discrete mathematics. Some basic mathematical concepts are covered in Chapters 1 - 4, computational techniques are discussed in Chapters 5 - 12, and mathematical techniques are discussed in Chapters 13 - 20.
To read the notes, click the links below for connection to the appropriate PDF files.
The material is available free to all individuals, on the understanding that it is not to be used for financial gain, and may be downloaded and/or photocopied, with or without permission from the author. However, the documents may not be kept on any information storage and retrieval system without permission from the author, unless such system is not accessible to any individuals other than its owners.
SECTION A --- BASIC MATERIAL
Chapter 1 : LOGIC AND SETS >>
- Sentences
- Tautologies and Logical Equivalence
- Sentential Functions and Sets
- Set Functions
- Quantifier Logic
- Negation
Chapter 2 : RELATIONS AND FUNCTIONS >>
- Relations
- Equivalence Relations
- Equivalence Classes
- Functions
Chapter 3 : THE NATURAL NUMBERS >>
Chapter 4 : DIVISION AND FACTORIZATION >>
- Division
- Factorization
- Greatest Common Divisor
- An Elementary Property of Primes
SECTION B --- COMPUTATIONAL ASPECTS
Chapter 5 : LANGUAGES >>
- Introduction
- Regular Languages
Chapter 6 : FINITE STATE MACHINES >>
- Introduction
- Pattern Recognition Machines
- An Optimistic Approach
- Delay Machines
- Equivalence of States
- The Minimization Process
- Unreachable States
Chapter 7 : FINITE STATE AUTOMATA >>
- Deterministic Finite State Automata
- Equivalence of States and Minimization
- Non-Deterministic Finite State Automata
- Regular Languages
- Conversion to Deterministic Finite State Automata
- A Complete Example
Chapter 8 : TURING MACHINES >>
- Introduction
- Design of Turing Machines
- Combining Turing Machines
- The Busy Beaver Problem
- The Halting Problem
Chapter 9 : GROUPS AND MODULO ARITHMETIC >>
- Addition Groups of Integers
- Multiplication Groups of Integers
- Group Homomorphism
Chapter 10 : INTRODUCTION TO CODING THEORY >>
- Introduction
- Improvement to Accuracy
- The Hamming Metric
Chapter 11 : GROUP CODES >>
- Introduction
- Matrix Codes --- An Example
- Matrix Codes --- The General Case
- Hamming Codes
- Polynomials in Z2[X]
- Polynomial Codes
Chapter 12 : PUBLIC KEY CRYPTOGRAPHY >>
- Basic Number Theory
- The RSA Code
SECTION C --- MATHEMATICAL ASPECTS
Chapter 13 : PRINCIPLE OF INCLUSION-EXCLUSION >>
- Introduction
- The General Case
- Two Further Examples
Chapter 14 : GENERATING FUNCTIONS >>
- Introduction
- Some Simple Observations
- The Extended Binomial Theorem
Chapter 15 : NUMBER OF SOLUTIONS OF A LINEAR EQUATION >>
- Introduction
- Case A --- The Simplest Case
- Case B --- Inclusion-Exclusion
- Case C --- A Minor Irritation
- Case Z --- A Major Irritation
- The Generating Function Method
Chapter 16 : RECURRENCE RELATIONS >>
- Introduction
- How Recurrence Relations Arise
- Linear Recurrence Relations
- The Homogeneous Case
- The Non-Homogeneous Case
- The Method of Undetermined Coefficients
- Lifting the Trial Functions
- Initial Conditions
- The Generating Function Method
Chapter 17 : GRAPHS >>
- Introduction
- Valency
- Walks, Paths and Cycles
- Hamiltonian Cycles and Eulerian Walks
- Trees
- Spanning Tree of a Connected Graph
Chapter 18 : WEIGHTED GRAPHS >>
- Introduction
- Minimal Spanning Tree
Chapter 19 : SEARCH ALGORITHMS >>
- Depth-First Search
- Breadth-First Search
- The Shortest Path Problem
Chapter 20 : DIGRAPHS >>
- Introduction
- Networks and Flows
- The Max-Flow-Min-Cut Theorem