This set of reading assignments introduces some basic mathematics that will be helpful for your studies in computer science. Depending on your background, you may already be familiar with (part of) this material, or you may see it for the first time. In the first case, you can just browse through the five reading assignments. Otherwise, we encourage you to really work on the material and solve the integrated online exercises in order to assess your understanding.

We start with language and logic (this document), then move on to variables, sets and tuples, functions, sums and subscripts, and modular arithmetic.

If you get lost, you can always ask your peers, or me, through the forums that we provide on the moodle page of the computer science course that you will be attending.

1Mathematicians speak differently

Mathematical language is not the same as natural language. We’re not even talking about formulas here, simply about how mathematicians read and write English texts, versus how other people do it. Mathematical sentences are mostly speaking about things being true or false, and they apply logical arguments to explain why the thing in question is true or false.

The “things” that can be true or false are called statements, and the logical arguments are called proofs. When speaking about statements and proofs, mathematical language is very precise, typically much more precise and less “forgiving” than natural language. The mathematician needs a very clear understanding of what a statement really means, in order to argue about it in a proof.

There are a number of misunderstandings that you may run into while reading even a very simple mathematical text, formulated in natural language. The main reason is that logical arguments often involve phrases such as “if ..., then ...”, and these have very precise meanings in mathematical language. In natural language, they are often interpreted differently, where the perceived meaning may also depend on the context.

In writing mathematical text (which you will do to some extent, for example in solving written exercises and answering exam questions), your main task will be to reach a level of precision that makes it clear what you really mean.

In this reading assignment, we will introduce you to some basics of mathematical language, in particular the precise meanings of logical phrases as the one mentioned above. On the way, you will also get a first glimpse of how mathematicians think, and why precision is so important to them. This will also make you aware of the imprecisions and ambiguities in natural language, and it will help you to write more precisely yourself.

Our initial example is a statement that you have heard many times (with different locations and percentages) in the weather forecast: “The probability of rain in Zurich today is 65%."

The correct answer is the one the weather people would give you if you asked them. But if you selected any another answer, you are in good company: there are many different ways of understanding the statement. Everybody seems to have an intuitive idea about what it means and is reasonably happy about it.

But the mathematician is not even satisfied with the “correct” answer given here. A statement about the future (“It will rain...”) is problematic, since one can only say in retrospect whether it was true or false. The mathematician would like to understand what is actually meant by “the probability of rain." It’s important to understand that statements involving probabilities can be true or false even though we cannot predict the future. For example, it is true that in a fair coin toss, the probability of heads coming up is 50%, and it is false that the probability of heads is 75%.

Digging deeper, the mathematician gets to the bottom of things and finds out what the weather people actually do (we give a simplified description here): knowing today’s weather conditions (temperature, atmospheric pressure, wind,...), they look into the weather recordings to find the days in the past that had similar weather conditions. Let’s say there were 100 such days within the observation period. The weather recordings also say on how many of these days it has actually rained. Let’s say there were 65 rainy days. Then the probability of rain today is announced as 65%. Hence, this is a statement about the past and not about the future, and as such it is checkable for being true or false. Not that the mathematician actually wants to do this by inspecting old weather recordings; the important thing is that the statement “the probability of rain in Zurich today is 65%" actually has a precise meaning, and based on this, one can decide whether it is true or false.

Here are some easier true/false statements:

• “The product of two odd numbers is an odd number.”

• “If you add 2 to an even number, then you get another even number.”

• “$1+1=5$.”

• “It is raining.”

Even though the first two statements do not define the terms product, odd, or even, they are considered to be mathematical statements, since everybody knows what the product of two numbers is, what odd numbers are ($1,3,5,7,...$), and what even numbers are ($0,2,4,6...$). In fact, both statements are true.

The third statement is false, of course. But it is still a mathematical statement that we can unambiguously mark as either true or false. Again, it is assumed that everybody knows the Arabic numerals, and the symbols for addition ($+$) and equality ($=$).

In this sense, mathematics is like law. Legal texts are very precise in defining the terms they use, but they stop doing this when it comes to terms that everybody knows. In specialized and advanced mathematical texts, “everybody” is replaced by “every domain expert”, and such texts are no longer understandable to everybody.

But this is similar to natural language: if you overhear a conversation between two Baseball experts, and you are not into Baseball yourself, you will not understand much.

The fourth statement in the list above (“It is raining”) is of a different nature. Whether it is true or false depends on the moment in which it is being made. But in this very moment, there is again a precise answer (either it rains, or it doesn’t), so this is also a statement that the mathematician is comfortable with. The answer to a statement (true or false) is called its truth value.

2Logic

The daily bread and butter of a mathematician is to find new and useful statements that are true. The way of doing this is to take statements that are already known to be true, and from them logically derive new true statements. Such a derivation is a proof of the new statement.

This process is per se not a mathematical one, and it is actually very familiar to you. Suppose you leave the apartment in the morning, with the newspaper on the kitchen table. When you return, the newspaper is on the sofa. Then you can logically derive and therefore have proof that someone was in the apartment in between. For this derivation, you of course take some things for granted, for example that there is no magic. What mathematicians take for granted in their proofs are axioms. Also, the literature genre of crime fiction is full of logical derivations that finally expose the culprit. In our brains, logical derivations happen automatically and give us aha moments. For example, you are missing a bottle of vodka that you are sure was still around a couple of days ago. Then you remember that two days ago, your teenage daughter had invited some friends to your house while you were having dinner with your spouse in a restaurant. Suddenly you know what happened to the bottle. Jokes also work with aha moments: after setting things up, they let you draw the (funny) conclusion for yourself.

3If ..., then ...

The general structure of a logical derivation is the following: if something is true, then something else is also true. For example, if the newspaper was moved, then someone was in the apartment. If a bottle of vodka is missing, and there was a teenager party, then the teenagers consumed the vodka.

The “somethings” here are statements that can either be true or false: “The newspaper was moved,” “Someone was in the apartment,” “A bottle of vodka is missing, and there was a teenager party,” “The teenagers consumed the vodka.” We also see that a statement can be a combination of other statements: if we combine the statement “A bottle of vodka is missing” with the statement “There was a teenager party” by putting an and in between them, we get the statement “A bottle of vodka is missing, and there was a teenager party.” This statement is true exactly if both individual statements are true.

Another way of combining statements is by putting an or in between, and we can also turn a statement into its opposite by putting a not in front: If it is raining tomorrow, or I’m feeling lazy, then I’m not taking the bicycle to work. And, or, and not are essential building blocks in logical derivations (in real life and in mathematics), so let’s look at them in some more detail.

4And ($\wedge$), Or ($\vee$), Not ($\neg$)

In mathematics, and, or and not work in the same way as in natural language, except for a frequent misunderstanding of the or that we discuss below.

The logical And.If we have two statements, we can combine them with the logical and (the mathematical symbol is $\wedge$) to a new statement that is true exactly if both individual statements are true. To specify the behavior of this logical combination, we can also use a truth table where $S_1$ and $S_2$ are placeholders for two statements, and $S_1\wedge S_2$ stands for the combined statement $S_1$ and $S_2$:

The placeholders just mean that you can replace $S_1$ and $S_2$ by any two concrete statements, and then you can read off what happens for these two statements. For example, if $S_1$ is replaced by “All cats are animals” (which is true), and $S_2$ by “All animals are mammals” (which is false), then the third row of the table tells us that the combined statement “All cats are animals, and all animals are mammals” is false.

The logical Or.For the logical or, we have to be careful, as its mathematical meaning differs from a widespread intuitive meaning. When a robber says “Your money, or your life!”, then the victim naturally interprets this as “I will either take your money, or your life, but not both!” Any robber taking both would be accused of having lied to the victim. But from a mathematical point of view, such a really rotten robber would still have spoken the truth. A combined statement of the form $S_1$ or $S_2$ (mathematically written as $S_1\vee S_2$) is true exactly if at least one of the individual statements is true, possibly both. This corresponds to the following truth table:

We also say that the logical or is the inclusive or in order to distinguish it more clearly from the exclusive or, corresponding to “either ..., or ...” in natural language. This has no standard symbol and is often simply called xor; but the symbol $\oplus$ is common. The truth table here is as follows:

The difference between the inclusive and the exclusive or is only in the last row. When both individual statements $S_1$ and $S_2$ are true, then the inclusive or is also true, while the exclusive or is false.

Actually, how we interpret the or in natural language varies—it is definitely not always the exclusive or as in the robber example. In the statement “It is raining tomorrow, or I’m feeling lazy” (which, if true, would lead to not taking the bicycle to work), we understand the or as inclusive, since we still consider the statement true if rain and laziness come together.

In mathematics, it’s much simpler: $\vee$ is the inclusive or, $\oplus$ is the exclusive or. Case closed.

The logical Not.The mathematical not (symbol $\neg$) is again very simple and behaves exactly as in natural language. Not false is true and not true is false. At least in situations where true and false are the only options.

Here is the truth table (as there is only one statement involved, we use the placeholder $S$).

The statement $\neg S$ is also called the negation of $S$.

5Combining And, Or, Not

So far, we have looked at each of and, or, and not in isolation, but in natural language, we are frequently combining them. You may say the following: “I stay home and watch football, or I go out and don’t watch football.” Logically, this corresponds to

Here is how you can define a leap year: “The year is divisible by 4 and not divisible by 100, or it is divisible by 400.” The logical formula for this is

By combining two statements with and, or, not, we can actually generate any truth table, and this is why these three are so important. Let’s say that we want to generate the truth table (3) of the exclusive or ($S_1\oplus S_2$), but only using $\wedge ,\vee ,\neg$. What is the formula that we should put in for the three question marks?

Well, there are many possibilties, but here is one that works: $(S_1\vee S_2) \wedge \neg (S_1\wedge S_2)$. How do we come up with this? We remember that except for the last row, this looks like the truth table (2) for $S_1\vee S_2$, so we start with this table and just correct the lower right entry (turn true into false). We can do this by saying “$S_1$ or $S_2$, and not $S_1$ and $S_2$.” The corresponding formula is $(S_1\vee S_2) \wedge \neg (S_1\wedge S_2)$. This corresponds to the following explanation of the exclusive or in natural language: “$S_1$ or $S_2$, but not both.”

6Saying the same, but differently

Up to a possible undertone, the double negation “I’m not unfamiliar with this place” is saying the same as “I’m familiar with this place.” Logically, this corresponds to the fact that the statement $\neg \neg S$ has the same truth value as the statement $S$. Either both are true, or both are false. In natural language, the double negation is a stylistic device; in logic, it is simply rewriting a statement into another, equivalent form. We write $S_1\Leftrightarrow S_2$ to indicate that the statements $S_1$ and $S_2$ are equivalent, meaning that they are either both true or both false. For example, $(\neg \neg S) \Leftrightarrow S$.

Here is another example. “Picasso was not a mathematician or computer scientist” is the same as saying “Picassso was not a mathematician, and Picasso was not a computer scientist.” As formula,

This is a special case of the first De Morgan’s law: We can convince ourselves of this equivalence by simply writing down the truth tables for both sides. Below is the one for $\neg (S_1 \vee S_2)$. We simply add another column to the truth table for $S_1\vee S_2$, corresponding to the negation $\neg (S_1 \vee S_2)$ of $S_1\vee S_2$ (in bold, and actually corresponding to the “neither..., nor...” that we have discussed in Exercise 4):

The truth table for $(\neg S_1) \wedge (\neg S_2)$ is obtained by first adding two more columns for the negations $\neg S_1$ and $\neg S_2$ of the individual statements, and then doing the logical and of these two new columns. The last three columns are hence the truth table for the logical and (but with rows reordered compared to how we wrote them down before).

We see that the two bold columns are the same, and this shows that $\neg (S_1 \vee S_2)$ and $(\neg S_1) \wedge (\neg S_2)$ always have the same truth value, no matter what the truth values of $S_1$ and $S_2$ are. This is exactly what it means that $\neg (S_1 \vee S_2)$ and $(\neg S_1) \wedge (\neg S_2)$ are equivalent.

The second De Morgan’s law is the same, with $\vee$ and $\wedge$ interchanged:

Actually, you can logically derive (prove) the second De Morgan’s law from the first one and vice versa, so the two De Morgan’s laws are also just two different ways of saying the same.

In our example, the second De Morgan’s law goes as follows: “Picasso was not a mathematician and computer scientist” is the same as saying “Picasso was not a mathematician, or Picasso was not a computer scientist.”

What both laws boil down to is that negating a statement interchanges and and or. If you’re not rich and beautiful, then you’re poor or ugly (which is bad but certainly better than poor and ugly). But if you’re not rich or beautiful, then you’re indeed poor and ugly.

7Implications

Not every statement of the form “If $S_1$, then $S_2$” is true. In a logical derivation (or proof), we expect that if $S_1$ is true, then $S_2$ is also true, but it may happen that there is a flaw in the argument and the derivation is false. A flaw means that even though $S_1$ is true, $S_2$ is false.

Consider this statement made by the hotel clerk when you check in: “If it’s sunny, then the pool is open.” When is this true? And when false? The only situation in which you can complain is when it’s sunny but the pool is closed. When it’s not sunny, the pool may still be open, but as nothing was said about what happens if it’s not sunny, you cannot argue that what the clerk has said is false. In logic, it must then be true, there is no third option. Hence, for this particular statement, the truth table is the following:

In mathematics, a statement of the form “if $S_1$, then $S_2$” is called an implication, written as $S_1\Rightarrow S_2$. People also say“$S_1$ implies $S_2$,” or “$S_2$ follows from $S_1$.” We can copy the truth table from the pool example:

So the only way of making an implication false is to make the first statement (the premise) true but the second statement (the conclusion) false. This corresponds exactly to what we called a flaw in a logical derivation before.

This allows absurd but still correct logical derivations (true statements) such as “If snow is red, then rain is green.” Like in the pool example, this is true simply because you cannot argue that it is false (for that, you would need snow to be red in the first place). In natural language, where we are not restricted to true and false, we can call such a statement absurd. In logic, we have to call it true—but we may still find it absurd.

A simple “hack” to get rid of such absurdities is to say $S_1\Rightarrow S_2$ differently. We already know that the implication is false exactly when $S_1$ is true and $S_2$ is false. Using De Morgan’s laws (or simply daily life logic), the implication is true exacly when $S_1$ is false or $S_2$ is true. Hence, $S_1\Rightarrow S_2$ is equivalent to $(\neg S_1) \vee S_2$. Now, we also have a less absurd way of saying “If snow is red, then rain is green.” Namely, “Snow is not red, or rain is green.” This is rather obviously true, simply because snow is not red.

The emotional table.Much of the confusion around implications comes from the fact that we typically do not have the truth table in mind, but an “emotional table”. Which feeling does the implication evoke? Let’s stick to our example of the clerk saying “If it’s sunny, then the pool is open.”

How do you feel about it in concrete cases? For example, if it’s not sunny but the pool is open, you will probably feel positively surprised. Here is the full emotional table for the pool example.

Your personal emotional table might look a bit different, but many people will agree with the above emotional table. Due to the positive surprise in the second row, you may find it acceptable when we tell you that the hotel clerk’s statement is true in this case.

But now consider this statement: “If it’s rainy, then the pool is closed.” Here is the emotional table:

Indeed, if it’s not rainy but the pool is closed (second row), you will be annoyed and find it much harder to accept that the statement is mathematically true in this case. Vice versa, if it’s rainy but the pool is open (third row), you are happy that you can still use the pool, and you couldn’t care less that the statement is mathematically false.

To summarize, the statement “If it’s rainy, then the pool is closed” has the same emotional table (up to the row ordering) as “If it’s sunny, then the pool is open.” But logically, the two are different. If it’s rainy and the pool is open, the first one is false, but the second one is true. And if it’s sunny and the pool is closed, the first one is true, but the second one is false.

As with the logical or, it’s clear and simple in mathematics: the implication (logical derivation) “If $S_1$, then $S_2$” is false only if $S_1$ is true and $S_2$ is false. Otherwise it’s true. Another case closed.

8Contraposition

“If I’m late, then you get a call from me” is the same as saying “If you don’t get a call from me, then I’m on time.” Here, the second implication is the contraposition of the first one. In general, the contraposition of “If $S_1$, then $S_2$” is “If not $S_2$, then not $S_1$.”

That both are saying the same is due to the following equivalence:

We can easily understand this equivalence. We know that the only way to make the left implication false is to make $S_1$ true and $S_2$ false. The only way to make the right implication false is to make $\neg S_2$ true and $\neg S_1$ false. But this is the same as making $S_1$ true and $S_2$ false.

In natural language, the contraposition is often used to reinforce statements. Logically, this does not provide any additonal information, but as a stylistic device, it (sometimes) works. To follow up an the above example: “If I’m late, then you get a call from me” says Peter to his boss. “Really?” says the boss, recalling that Peter hasn’t always called when he was late. But Peter reinforces his statement by using the contraposition: “Sure! If you don’t get a call from me, then I’m on time.”

To summarize, “If $S_1$, then $S_2$” is logically equivalent to its contraposition “If not $S_2$, then not $S_1$”. But “If $S_1$, then $S_2$” is not logically equivalent to “If $S_2$, then $S_1$”.

Remember Peter saying “If I’m late, then you get a call from me.”’ This is not the same as saying “If you get a call from me, then I’m late.” When Peter says “If I’m late, then you get a call from me,” this doesn’t rule out the possibility that he is on time but is calling the boss for a different reason. But “If you get a call from me, then I’m late” says that Peter will only call his boss when he’s late.

Thinking that “If $S_1$, then $S_2$” is saying the same as “If $S_2$, then $S_1$” is logically wrong but easily happens due to our emotional tables. In particular, if the conclusion $S_2$ in “If $S_1$, then $S_2$” has a negative connotation (“the pool is closed”), we emotionally expect that $S_2$ only happens under the premise $S_1$ (“it’s rainy.”) So we expect “If not $S_1$, then not $S_2$”. Which is the same as expecting the contraposition “If $S_2$, then $S_1$”.

Now, it’s probably time to take a little break—your brain deserves it!