## Introduction

When studying programming and algorithms, it’s inevitable that we will need some math. Math is used in computer science in many ways:

• To know if our programs are correct.
• To figure out how fast or slow our programs runs.
• To solve some contest problems.

I’m here to introduce to you all the math we’ll need. (Well, almost all :P)

By the way, one major reference we’ll use will be MIT’s 6.042 course, fittingly called Mathematics for Computer Science. If you want to know more details, or if you want to do some advanced reading, I highly suggest you check it out!

Note: Some of you may already know a lot about math and stuff (presumably from training for math contests, etc.). If that’s the case, you can just skim through sections you are already familiar with, because you probably already know a lot of the things we’ll talk about. But probably not all, so please try not to skip whole sections entirely. skim $\not=$ skip. :D

# Mathematics and Logic

It’s important for us to learn how to communicate mathematically. Unfortunately, English is too ambiguous for math. Here are a couple of examples:

• “You may have cake, or you may have ice cream.” Does this mean you can have both, or just one?
• “If you can solve any problem we come up with, then you get a gold medal.” Does this mean that you get a gold medal if you solve all problems we come up with, or just any one?

Precision is very important in math (and programming), but it’s hard to communicate if the language itself is full of problems like this. This is why mathematicians have developed a more precise language for this purpose.

An excellent introduction to this language is Chapter 1 of MIT 6.042. (The examples above were taken from it.) Please read it. The writing style is quite relaxed and informal, and I’m sure you’ll learn a lot from it. Also, almost all the following topics will require it.

Important: When reading it, you don’t need to memorize the terms. We won’t give you an exam about them. Instead, we want you to really understand them. If you encounter a term again in a later chapter but forgot what it means, you can simply refer back to it.