Extra (optional) exercises – Long Day#
These exercises are optional extra material for students who have finished the exercises of the day and have the time and interest for more.
Extra exercise 1: The infinitude of primes#
A natural number \(d\) is said to be a divisor of (or to divide evenly) a natural number \(n\) if \(n/d\) is a natural number. A prime number is a natural number \(n\) greater than \(1\) whose only divisors are \(1\) and \(n\). Primes are of theoretical interest, but they are also used, for example, to secure online banking.
The aim of this exercise is to show that there are infinitely many primes. You may use without proof that any natural number can be written as a product of primes.
Question a#
Show that for every natural number \(n\) greater than \(1\), there exists at least one prime that is a divisor of \(n\).
Hint
Assume that there are natural numbers \(n\) greater than \(1\) that have no prime divisors. Then there exists a smallest possible natural number \(N\) greater than \(1\) that has no prime divisors. Show that this leads to a contradiction.
Question b#
Assume that there are only finitely many primes. Show that there then exists a natural number \(N\) greater than \(1\) that has no prime divisors.
Hint
Euclid (around 300 BC) had the following idea: if there are only finitely many primes, say \(p_1,\dots,p_\ell\), which primes are then divisors of the number \(1+p_1\cdot \cdots \cdot p_\ell\)?
Question c#
Conclude from Questions a and b that there are in fact infinitely many primes.
Extra exercise 2: Boolean algebra#
When a computer carries out logical operations, the two bit values \(0\) and \(1\) are used as truth values: \(1\) represents \(\mathrm T\) and \(0\) represents \(\mathrm F\). This representation makes it possible to describe logical operations in other ways, and it is related to a structure known as Boolean algebra.
Question a#
Applying the usual arithmetic multiplication to the numbers \(0\) and \(1\) produces the following multiplication table for bits, which we now interpret as a truth table:
\(P\) |
\(Q\) |
\(P\cdot Q\) |
|---|---|---|
\(1\) |
\(1\) |
\(1\) |
\(1\) |
\(0\) |
\(0\) |
\(0\) |
\(1\) |
\(0\) |
\(0\) |
\(0\) |
\(0\) |
Which logical operation does multiplication describe?
Answer
AND (\(\wedge\)).
Question b#
We define the operator \(\oplus\) on the bit values \(0\) and \(1\) as follows: \(0\oplus 0=0\), \(0\oplus1=1\), \(1\oplus 0=1\) and \(1\oplus 1=0\). We will call this operation addition, although it is not quite the usual arithmetic addition. This produces the following table, which we again interpret as a truth table:
\(P\) |
\(Q\) |
\(P\oplus Q\) |
|---|---|---|
\(1\) |
\(1\) |
\(0\) |
\(1\) |
\(0\) |
\(1\) |
\(0\) |
\(1\) |
\(1\) |
\(0\) |
\(0\) |
\(0\) |
Which logical operation does addition describe?
Hint
Have a look at Exercise 2 from the day’s main exercises.
Answer
XOR (“exclusive or”).
Question c#
How should we interpret \(1 \oplus P\)?
Answer
As \(\neg P\).
Question d#
What is the truth table of the logical expression \(P\cdot (1 \oplus Q)\)? Also, try to formulate a logical expression that takes the truth value \(1\) if \(P=1\) and \(Q=1\), and otherwise takes the value \(0\).
Question e#
Let \(a,b,c,d \in \{0,1\}\) be bit values. Find a logical expression \(X\) containing \(P\) and \(Q\) whose truth table is:
\(P\) |
\(Q\) |
\(X\) |
|---|---|---|
\(1\) |
\(1\) |
\(a\) |
\(1\) |
\(0\) |
\(b\) |
\(0\) |
\(1\) |
\(c\) |
\(0\) |
\(0\) |
\(d\) |
Hint
Two logical expressions can be added together using \(\oplus\). Note that \(P \oplus P =0\) for any value of \(P\).
Question f#
How can disjunction \(\vee\) be described using addition and multiplication of bit values?
Answer
\(P \vee Q\) can be described as \(P\cdot Q \oplus (1\oplus P)\cdot Q \oplus P\cdot(1 \oplus Q)=P \oplus Q \oplus P \cdot Q\).