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 >>

• Introduction
• Induction

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