LECTURE NOTES OF WILLIAM CHEN
# DISCRETE MATHEMATICS

## SECTION A --- BASIC MATERIAL

### Chapter 1 : LOGIC AND SETS >>

### Chapter 2 : RELATIONS AND FUNCTIONS >>

### Chapter 3 : THE NATURAL NUMBERS >>

### Chapter 4 : DIVISION AND FACTORIZATION >>

## SECTION B --- COMPUTATIONAL ASPECTS

### Chapter 5 : LANGUAGES >>

### Chapter 6 : FINITE STATE MACHINES >>

### Chapter 7 : FINITE STATE AUTOMATA >>

### Chapter 8 : TURING MACHINES >>

### Chapter 9 : GROUPS AND MODULO ARITHMETIC >>

### Chapter 10 : INTRODUCTION TO CODING THEORY >>

### Chapter 11 : GROUP CODES >>

### Chapter 12 : PUBLIC KEY CRYPTOGRAPHY >>

## SECTION C --- MATHEMATICAL ASPECTS

### Chapter 13 : PRINCIPLE OF INCLUSION-EXCLUSION >>

### Chapter 14 : GENERATING FUNCTIONS >>

### Chapter 15 : NUMBER OF SOLUTIONS OF A LINEAR EQUATION >>

### Chapter 16 : RECURRENCE RELATIONS >>

### Chapter 17 : GRAPHS >>

### Chapter 18 : WEIGHTED GRAPHS >>

### Chapter 19 : SEARCH ALGORITHMS >>

### Chapter 20 : DIGRAPHS >>

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.

- Sentences
- Tautologies and Logical Equivalence
- Sentential Functions and Sets
- Set Functions
- Quantifier Logic
- Negation

- Relations
- Equivalence Relations
- Equivalence Classes
- Functions

- Introduction
- Induction

- Division
- Factorization
- Greatest Common Divisor
- An Elementary Property of Primes

- Introduction
- Regular Languages

- Introduction
- Pattern Recognition Machines
- An Optimistic Approach
- Delay Machines
- Equivalence of States
- The Minimization Process
- Unreachable States

- 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

- Introduction
- Design of Turing Machines
- Combining Turing Machines
- The Busy Beaver Problem
- The Halting Problem

- Addition Groups of Integers
- Multiplication Groups of Integers
- Group Homomorphism

- Introduction
- Improvement to Accuracy
- The Hamming Metric

- Introduction
- Matrix Codes --- An Example
- Matrix Codes --- The General Case
- Hamming Codes
- Polynomials in Z2[X]
- Polynomial Codes

- Basic Number Theory
- The RSA Code

- Introduction
- The General Case
- Two Further Examples

- Introduction
- Some Simple Observations
- The Extended Binomial Theorem

- Introduction
- Case A --- The Simplest Case
- Case B --- Inclusion-Exclusion
- Case C --- A Minor Irritation
- Case Z --- A Major Irritation
- The Generating Function Method

- 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

- Introduction
- Valency
- Walks, Paths and Cycles
- Hamiltonian Cycles and Eulerian Walks
- Trees
- Spanning Tree of a Connected Graph

- Introduction
- Minimal Spanning Tree

- Depth-First Search
- Breadth-First Search
- The Shortest Path Problem

- Introduction
- Networks and Flows
- The Max-Flow-Min-Cut Theorem