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
- 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
- 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
- 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
- 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
- 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
No comments:
Post a Comment