Discrete Mathematics

Discrete Mathematics

by WWL Chen

This set of notes has been compiled over a period of more than 20 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. You will need Adobe Acrobat Reader Version 4.0 or later.

The material is available free to all individuals, on the understanding that it is not to be used for financial gains, 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 (last uploaded on 2 December 2002)

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

Chapter 2: RELATIONS AND FUNCTIONS (last uploaded on 2 December 2002)

• Relations
• Equivalence Relations
• Equivalence Classes
• Functions

Chapter 3: THE NATURAL NUMBERS (last uploaded on 2 December 2002)

• Introduction
• Induction

Chapter 4: DIVISION AND FACTORIZATION (last uploaded on 2 December 2002)

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

SECTION B --- COMPUTATIONAL ASPECTS

Chapter 5: LANGUAGES (last uploaded on 2 December 2002)

• Introduction
• Regular Languages

Chapter 6: FINITE STATE MACHINES (last uploaded on 2 December 2002)

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

Chapter 7: FINITE STATE AUTOMATA (last uploaded on 2 December 2002)

• 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 (last uploaded on 2 December 2002)

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

Chapter 9: GROUPS AND MODULO ARITHMETIC (last uploaded on 2 December 2002)

• Addition Groups of Integers
• Multiplication Groups of Integers
• Group Homomorphism

Chapter 10: INTRODUCTION TO CODING THEORY (last uploaded on 2 December 2002)

• Introduction
• Improvement to Accuracy
• The Hamming Metric

Chapter 11: GROUP CODES (last uploaded on 2 December 2002)

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

Chapter 12: PUBLIC KEY CRYPTOGRAPHY (last uploaded on 2 December 2002)

• Basic Number Theory
• The RSA Code

SECTION C --- MATHEMATICAL ASPECTS

Chapter 13: PRINCIPLE OF INCLUSION-EXCLUSION (last uploaded on 2 December 2002)

• Introduction
• The General Case
• Two Further Examples

Chapter 14: GENERATING FUNCTIONS (last uploaded on 2 December 2002)

• Introduction
• Some Simple Observations
• The Extended Binomial Theorem

Chapter 15: NUMBER OF SOLUTIONS OF A LINEAR EQUATION (last uploaded on 2 December 2002)

• 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 (last uploaded on 2 December 2002)

• 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 (last uploaded on 2 December 2002)

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

Chapter 18: WEIGHTED GRAPHS (last uploaded on 25 August 2003)

• Introduction
• Minimal Spanning Tree

Chapter 19: SEARCH ALGORITHMS (last uploaded on 2 December 2002)

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

Chapter 20: DIGRAPHS (last uploaded on 2 December 2002)

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