## 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 PrincipleBasic Proof Techniques

Proof by Mathematical Induction

Strong Induction

Sets

Click on the following links for problems.

Problem Set 1. The Pigeonhole PrincipleProblem Set 2. Basic Proof Techniques

Problem Set 3. Proof by Mathematical Induction

Problem Set 4. Strong Induction

Not in particular order.

Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019Discrete Mathematics, Jean Gallier, Universitext, Springer, 2011