Chapter 1 · Boolean and mathematical logic

A proposition is a statement that is either true (1) or false (0), never both. Connectives are defined solely by their truth tables: the table, not your intuition about everyday language, tells you what an expression is worth.

$p$	$q$	$p \land q$	$p \lor q$	$p \Rightarrow q$
1	1	1	1	1
1	0	0	1	0
0	1	0	1	1
0	0	0	0	1

b) On which row, and on that row alone, is the implication $p \Rightarrow q$ false? Translate that row into plain English with the example: “if the file exists, then the read succeeds”.

See the solution

Answer

b) The row $p=1$ , $q=0$ : the promise is broken only if the file exists and the read fails

b) A single row: $p=1$ and $q=0$ . An implication is false only when the premise is true and the conclusion is false. In the example, the promise “if the file exists, then the read succeeds” is broken only when the file really does exist and the read fails anyway. If the file does not exist, the promise is never tested, and we declare it kept: the last two rows equal 1. This is the point students resist the longest, because the “if” of everyday language carries an idea of cause that the logical $\Rightarrow$ does not have.

The full exercise, with all its questions →

The chapter's set · the revision sheet

Chapter 2 · Proof techniques

The contrapositive is not a stylistic variant: it is the choice you make when the hypothesis $P$ is POOR, that is, impossible to translate into anything useful, while the negation of the conclusion can be handled effortlessly. The move is always the same: write $\lnot Q$ , see whether it is rich, and if so prove $\lnot Q \Rightarrow \lnot P$ , which has exactly the same truth value by exercise 2.

One negation rule comes back in every question: the negation of “ $A$ or $B$ ” is “ $\lnot A$ and $\lnot B$ ”, and the negation of “ $A$ and $B$ ” is “ $\lnot A$ or $\lnot B$ ”.

b) Let $x$ and $y$ be two positive integers. Prove: if $xy>1{,}000$ , then $x>31$ or $y>31$ .

See the solution

Answer

b) Negation of the conclusion: $x \leq 31$ and $y \leq 31$ , so $xy \leq 961 \leq 1{,}000$ . The statement is true

b) The conclusion is an OR, and the negation of an OR is an AND: “ $x \leq 31$ AND $y \leq 31$ ”. That is where everything happens, because this negation is rich, it gives two usable upper bounds, whereas the original conclusion, an OR, cannot be manipulated. Contrapositive to prove: if $x \leq 31$ and $y \leq 31$ , then $xy \leq 1{,}000$ . Proof: since $x$ and $y$ are positive, $xy \leq 31 \times 31 = 961 \leq 1{,}000$ . So the statement is true. The bound is sharp: $31^{2}=961$ fits, and $32^{2}=1{,}024$ does exceed 1,000, which shows that the threshold 31 is not chosen at random. The pitfall, penalized on every exam: writing the negation as “ $x \leq 31$ or $y \leq 31$ ”. With that or, the pair $(10, 200)$ satisfies the hypothesis and gives $xy=2{,}000$ , the proof collapses and the student wrongly concludes that the statement is false.

The full exercise, with all its questions →

The chapter's set · the revision sheet

Chapter 3 · Number systems in computing

To convert a decimal integer to base $b$ , divide repeatedly by $b$ and read the remainders from BOTTOM TO TOP. For a fractional part, multiply repeatedly by $b$ and read the integer parts from TOP TO BOTTOM. The two algorithms look alike, but the reading direction is reversed: that is where half the marks are lost.

a) Convert 156 to binary by repeated division and check with the weights.

See the solution

Answer

a) $156 = 10011100_2$

a) $156 = 2(78) + 0$ ; $78 = 2(39)+0$ ; $39 = 2(19)+1$ ; $19 = 2(9)+1$ ; $9 = 2(4)+1$ ; $4 = 2(2)+0$ ; $2 = 2(1)+0$ ; $1 = 2(0)+1$ . The remainders read from bottom to top give $10011100_2$ . Check with the weights: $128 + 16 + 8 + 4 = 156$ . The weight check is compulsory, because it catches the reading-direction error, which would give $00111001$ .

The full exercise, with all its questions →

The chapter's set · the revision sheet

Chapter 4 · Modular arithmetic

All of modular arithmetic rests on an operation you think you have known since elementary school. The thread of the set: we no longer care about the QUOTIENT but about the REMAINDER, and a remainder is always nonnegative, even when the dividend is not.

c) Compute $-17 \bmod 5$ and $-1 \bmod 12$ . Watch the sign of the remainder.

See the solution

Answer

c) $-17 \bmod 5 = 3$ and $-1 \bmod 12 = 11$

c) For $-17$ divided by 5: the quotient must be chosen so that the remainder falls in $[0, 5)$ . With $q=-4$ : $-17=5\times(-4)+3$ , so $r=3$ . The knee-jerk division $-17=5\times(-3)-2$ would give $r=-2$ , which is not a valid remainder. For $-1$ divided by 12: $-1=12\times(-1)+11$ , so $r=11$ : it is the last notch on the clock before going back through zero, which is exactly the picture to remember.

The full exercise, with all its questions →

The chapter's set · the revision sheet

Chapter 5 · Set theory and relations

Let $E = \{1,2,\dots,10\}$ be the universal set, $A = \{1,2,3,4,5,6\}$ and $B = \{4,5,6,7,8\}$ . We write $\overline{A}$ for the complement of $A$ in $E$ .

a) Give $A \cup B$ , $A \cap B$ , $A \setminus B$ and $B \setminus A$ in roster form.

See the solution

Answer

a) $A \cup B = \{1,\dots,8\}$ , $A \cap B = \{4,5,6\}$ , $A \setminus B = \{1,2,3\}$ , $B \setminus A = \{7,8\}$

a) $A \cup B = \{1,2,3,4,5,6,7,8\}$ : all the elements that are in one OR the other, counted only once. $A \cap B = \{4,5,6\}$ : those that are in both. $A \setminus B = \{1,2,3\}$ : in $A$ but not in $B$ . $B \setminus A = \{7,8\}$ . Note that $A \setminus B$ and $B \setminus A$ have nothing to do with each other: the difference is not symmetric.

The full exercise, with all its questions →

The chapter's set · the revision sheet

Chapter 6 · Injective, surjective and bijective functions

A relation from $A$ to $B$ is any subset of $A \times B$ . A FUNCTION $f : A \to B$ is a relation that meets two conditions, and only two: every element of $A$ has an image (EXISTENCE), and it has only one (UNIQUENESS). The whole chapter rests on this starting point, because a relation that fails either condition does not even deserve the question of whether it is injective.

The figure shows four relations from $A = \{1,2,3\}$ to $B = \{a,b,c\}$ , drawn as arrow diagrams: one arrow from the domain to the codomain for each pair in the relation.

a) Which of the four relations in the figure are functions from $A$ to $B$ ? For each relation you reject, name the missing condition.

See the solution

Answer

a) The functions are (1) and (4); (2) fails existence, (3) fails uniqueness

a) The functions are (1) and (4). Relation (2) fails EXISTENCE: no arrow leaves the element 2, so $f(2)$ refers to nothing and the notation itself loses its meaning. Relation (3) fails UNIQUENESS: two arrows leave 1, towards $a$ and towards $b$ , so $f(1)$ would refer to two objects at once. The test is read at a glance on an arrow diagram: there must be EXACTLY ONE arrow leaving EACH element on the left. Not zero, not two. Nothing at all is required on the codomain side, however: an element of $B$ may receive zero, one or ten arrows without leaving the world of functions. It is precisely this asymmetry between domain and codomain that will produce injectivity and surjectivity in the next exercises.

The full exercise, with all its questions →

The chapter's set · the revision sheet

Chapter 7 · Induction and recursion

Induction is the only tool that proves infinitely many statements in two lines. The thread of the set: a proof by induction has TWO steps, and dropping either one does not produce an incomplete proof, it produces a wrong one.

d) What happens if you forget the INDUCTIVE STEP? Illustrate with “ $n^{2}+n+41$ is prime”.

See the solution

Answer

d) $n^{2}+n+41$ is prime from $n=0$ to $n=39$ , then $40^{2}+40+41 = 1681 = 41^{2}$

d) Without an inductive step, checking cases proves nothing either. The property “ $n^{2}+n+41$ is prime” is true for $n=0$ , which gives 41, for $n=1$ , which gives 43, and in fact for every integer from 0 to 39. It is FALSE at $n=40$ , because $40^{2}+40+41=1681=41^{2}$ . Forty successive checks are not worth a proof: the inductive step is what replaces infinitely many checks.

The full exercise, with all its questions →

The chapter's set · the revision sheet

Chapter 8 · Introduction to graphs and matrices

The adjacency matrix $M$ of a graph with $n$ vertices is the $n \times n$ matrix whose entry $M_{ij}$ is 1 if there is an arc from vertex $i$ to vertex $j$ , and 0 otherwise. It holds exactly the same information as the drawing, but it can be computed with. The directed graph below has four vertices numbered 1 to 4.

b) What does the sum of the entries of a row represent? And of a column?

See the solution

Answer

b) Row: OUT-degree. Column: IN-degree

b) The sum of row $i$ is the number of arcs leaving $i$ , that is, its OUT-degree. The sum of column $j$ is the number of arcs arriving at $j$ , its IN-degree. Confusing the two is the mistake that skews the whole rest of the chapter, because it amounts to transposing the graph.

The full exercise, with all its questions →

The chapter's set · the revision sheet

Chapter 9 · Counting and probability

The binomial coefficient counts subsets, and its recurrence relation is the same as that of a recursive algorithm. It is also a chance to meet dynamic programming again, from the recursion chapter.

a) Prove Pascal's identity $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ by a counting argument, with no computation.

See the solution

Answer

a) The subsets split according to whether they contain $x$ or not: $\binom{n-1}{k-1} + \binom{n-1}{k}$

a) Count the $k$ -element subsets of an $n$ -element set, singling out one particular element $x$ . These subsets split into two categories with no overlap. Those that CONTAIN $x$ : you still have to choose $k-1$ elements among the $n-1$ others, which gives $\binom{n-1}{k-1}$ . Those that do NOT contain it: you must choose the $k$ elements among the $n-1$ others, which gives $\binom{n-1}{k}$ . Every subset falls into exactly one of the two cases, hence the equality. No computation, only a split into two.

The full exercise, with all its questions →

The chapter's set · the revision sheet

Self-check: 201-N11, Mathematics for Computer Science

The chapters of the course

What next?