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

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

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

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

Not in particular order.

Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019Applied Discrete Mathematics, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

Discrete Mathematics, Jean Gallier, Universitext, Springer, 2011

A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998