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