Lecture Notes
Discrete Mathematics
While a statement (a claim) in natural sciences is validated by observations or experiments, in mathematics it is done by proofs using principles of logical reasoning. We discuss various techniques of proofs that will be useful in studying mathematics and computer science. (Recall that computers are built upon the same sytem of logic that is the foundation of mathematics.) In addition, we also discuss some topics of finite and discrete mathematics, which will be important not only for the students of mathematics but also for the students of computer science. Those topics include: Basic Proof Techniques, Proof by Mathematical Induction, Sets, Logic, Graphs, Automata, Languages, Probability, Modular Arithmetics and Public Key Cryptography. The target readers of these lecture notes are freshmen undergraduates in mathematics and computer science.
Lecture Notes
Problem Sets
References and Further Reading
Click on linked topics to view lecture notes.
The Pigeonhole Principle
Basic Proof Techniques
Proof by Mathematical Induction
Strong Induction
Sets
Graphs and Functions
Propositional Logic
Normal Forms
Logic and Computer
Quantificational Logic
Directed Graphs
Equivalence Relations
Introductory Combinatorics: The Basic Principle of Counting
Introductory Combinatorics: Permutations
Introductory Combinatorics: Combinations 1
Introductory Combinatorics: Combinations 2
Introductory Probability: Outcomes, Events, Probability, Independence
Introductory Probability: Conditional Probability
Introductory Probability: Baye's Theorem
Introductory Probability: Random Variables and Expectation
Click on the following links for problems.
Problem Set 1. The Pigeonhole Principle
Problem Set 2. Basic Proof Techniques
Problem Set 3. Proof by Mathematical Induction
Problem Set 4. Strong Induction
Problem Set 5. Sets
Problem Set 6. Graphs and Functions
Problem Set 7. Propositional Logic
Problem Set 8. Normal Forms
Problem Set 9. Logic and Computer
Problem Set 10. Quantificational Logic
Problem Set 11. Directed Graphs
Problem Set 12. Equivalence Relations
Problem Set 13. Introductory Combinatorics: The Basic Principle of Counting
Problem Set 14. Introductory Combinatorics: Permutations
Problem Set 15. Introductory Combinatorics: Combinations 1 and 2
Problem Set 16. Introductory Probability: Outcomes, Events, Probability, Independence
Problem Set 17. Introductory Probability: Conditional Probability
Problem Set 18. Introductory Probability: Baye's Theorem
Al Doerr and Ken Levasseur, Applied Discrete Mathematics. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.
Jean Gallier, Discrete Mathematics, Universitext, Springer, 2011
Harry Lewis and Rachel Zax, Essential Discrete Mathematics for Computer Science, Princeton University Press, 2019
Sheldon Ross, A First Course in Probability, 5th Edition, Prentice-Hall, 1998