Discrete Mathematics
by WWL Chen
This set of notes has been compiled
over a period of more than 25 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 use in the unit
MATH237 at Macquarie University. This unit is currently taught
in two parallel strands. The following is the suggested order
for the presentation of the material:
- C: Chapters 1, 2, 5, 6, 7, 8, 9,
10, 11 and 12.
- M: Chapters 3, 4, 13, 14, 15, 16,
17, 18, 19 and 20.
To read the notes, click the chapters
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