## SectionD.1Exercise Sheet 1

### ExercisesExercises

#### 1.Different Number Systems.

Convert the following numbers into the specified number system.

1. $$\langle 43 \rangle_{10}$$ into the base 7 system

2. $$\langle212 \rangle _{3}$$ into the base 9 system

3. $$\langle313\rangle _{4}$$ into the base 6 system

4. $$\langle 3142 \rangle _{5}$$ into the base 3 system

5. $$\langle 621 \rangle _{11}$$ into the base 5 system

202207281550

202204151400
Solution.
1. $$\displaystyle \langle 43\rangle_{10} = 6\times 7+1\times 1 = \langle 61\rangle_{7}$$

2. $$\displaystyle \langle 212\rangle_{3} = 2\times 9+1\times 3+2\times 1 = \langle 23\rangle_{10} = 2\times 9+5\times 1 = \langle25\rangle_{9}$$

3. $$\displaystyle \langle313\rangle_{4} = 3\times 16+1\times 4+3\times 1= \langle 55\rangle_{10} = 1 \times 36 + 3 \times 6 + 1 \times 1 = \langle131\rangle_{6}$$

4. $$\displaystyle \langle3142\rangle_{5} = 3\times 125+1\times 25+4\times 5+2\times 1 = \langle422\rangle_{10}= 1 \times 243 + 2 \times 81 + 0 \times 27 + 1 \times 9 + 2 \times 3 + 2 \times 1 = \langle120122\rangle_{3}$$

5. $$\displaystyle \langle621\rangle_{11} = 6\times 121+2\times 11+1\times 1 = \langle749\rangle_{10} = 1 \times 625 + 0 \times 125 + 4 \times 25 + 4 \times 5 + 4 \times 1 = \langle10444\rangle_{5}$$

#### 2.Some Positional Number Systems.

We consider the following positional number systems:

Name Base Prefix Digits
Binary System 2 0b 0,1
Octal System 8 0 0,...,7

The digits are denoted in the order of their value, e.g. the digit F in the hexadecimal system has the value 15.

To specify the number system a number is prefixed by the content of the column “Prefix”. For example, 013 is an octal number, 0x13 is a hexadecimal number and 13 is a decimal number.

1. State the following decimal numbers in each of the three number systems. Do it on your own, don't use a calculator or computer.
 5 16 49 81 257 317 1721 4096
2. How did you do it? Describe your approach such that other students could use it as instruction.

3. Assume a function $$\textit{dig} : [0,15] \rightarrow \{0,\dots,9,A,\dots,F\}\text{.}$$ $$\textit{dig}$$ computes for any decimal number in the interval $$[0,15]$$ the corresponding hexadecimal digit. Complete the following recursive definition of a function $$\rangle\cdot\langle_b : \Nat\rightarrow\{0,\dots,9,A,\dots,F\}^\ast$$ which computes for any natural number the representation in base $$b\text{.}$$ For example, it should hold that $$\rangle257\langle_8 = 401\text{.}$$

202207281550

202204151400
Solution.
1. Table:

10 2 8 16
5 0b101 05 0x5
16 0b10000 020 0x10
49 0b110001 061 0x31
81 0b1010001 0121 0x51
257 0b100000001 0401 0x101
317 0b100111101 0475 0x13D
1721 0b11010111001 03271 0x6B9
4096 0b1000000000000 010000 0x1000

2. Translation of a number $$n$$ into base $$b$$ using the example $$\langle{}401\rangle_8 = 257$$

1. Note all $$b^k \lt n$$
 $$8^2$$ $$8^1$$ $$8^0$$
2. Starting on the left, determine the maximal $$a$$ such that $$a\cdot{} b^k \lt n\text{.}$$ Compute $$n'$$ where $$n' = n - (a\cdot{} b^k)\text{.}$$ Here we have $$n' = 1\text{.}$$
 $$8^2$$ $$8^1$$ $$8^0$$ 4
3. Repeat the previous step from left to right until all digits are computed:
 $$8^2$$ $$8^1$$ $$8^0$$ 4 0 1
3. Idea: The inverse of the tree example from the lecture notes. In every recursion step until $$n \lt b$$ holds: $$n \mathrel{\text{mod}} b$$ is the index of the child in the currently considered subtree. The factor $$\frac{n}{b}$$ ensures that the algorithm descends one layer in every step.

\begin{equation*} \rangle{}n\langle_b =\left\{ \begin{array}{cl} \rangle\lfloor\frac{n}{b}\rfloor\langle_b \cdot \textit{dig}(n \mathrel{\text{mod}} b) \amp \textup{if} \\ \textit{dig}(n)\amp \textup{else} \end{array}\right. \end{equation*}

#### 3.Translate!

Fill in the following form.
binary $$\buintpb{\cdot}{2}$$ octal $$\buintpb{\cdot}{8}$$ decimal $$\buintpb{\cdot}{10}$$ hexadecimal $$\buintpb{\cdot}{16}$$
$$\buintpb{21}{16}$$
$$\buintpb{1101}{2}$$
$$\buintpb{103}{8}$$
$$\buintpb{1011}{2}$$
$$\buintpb{2D}{16}$$
$$\buintpb{417}{8}$$
$$\buintpb{17}{16}$$
$$\buintpb{111101}{2}$$
$$\buintpb{315}{8}$$
202207281550

202204151400
Solution.
binary $$\buintpb{\cdot}{2}$$ octal $$\buintpb{\cdot}{8}$$ decimal $$\buintpb{\cdot}{10}$$ hexadecimal $$\buintpb{\cdot}{16}$$
$$\buintpb{100001}{2}$$ $$\buintpb{41}{8}$$ $$\buintpb{33}{10}$$ $$\buintpb{21}{16}$$
$$\buintpb{1101}{2}$$ $$\buintpb{15}{8}$$ $$\buintpb{13}{10}$$ $$\buintpb{D}{16}$$
$$\buintpb{1000011}{2}$$ $$\buintpb{103}{8}$$ $$\buintpb{67}{10}$$ $$\buintpb{43}{16}$$
$$\buintpb{1011}{2}$$ $$\buintpb{13}{8}$$ $$\buintpb{11}{10}$$ $$\buintpb{B}{16}$$
$$\buintpb{101101}{2}$$ $$\buintpb{55}{8}$$ $$\buintpb{45}{10}$$ $$\buintpb{2D}{16}$$
$$\buintpb{100001111}{2}$$ $$\buintpb{417}{8}$$ $$\buintpb{271}{10}$$ $$\buintpb{10F}{16}$$
$$\buintpb{10111}{2}$$ $$\buintpb{27}{8}$$ $$\buintpb{23}{10}$$ $$\buintpb{17}{16}$$
$$\buintpb{111101}{2}$$ $$\buintpb{75}{8}$$ $$\buintpb{61}{10}$$ $$\buintpb{3D}{16}$$
$$\buintpb{11001101}{2}$$ $$\buintpb{315}{8}$$ $$\buintpb{205}{10}$$ $$\buintpb{CD}{16}$$

#### 4.Unsigned Arithmetics.

1. State the decimal representation of the following binary number (we use $$\buintp{\cdot}$$ instead of $$\buintpb{\cdot}{2}$$):

1. $$\displaystyle \buintp{11}$$

2. $$\displaystyle \buintp{011}$$

3. $$\displaystyle \buintp{1001}$$

4. $$\displaystyle \buintp{1111}$$

5. $$\displaystyle \buintp{101111}$$

2. Compute and state the result in the binary system.

1. $$\displaystyle \buintp{1011}+\buintp{1101}$$

2. $$\displaystyle \buintp{11}+\buintp{1101}$$

3. $$\displaystyle \buintp{10111}+\buintp{1101}$$

4. $$\displaystyle \buintp{1011 + 1101}$$

202207281550

202204151400
Solution.
1. $$\displaystyle \buintp{11} = 3$$

2. $$\displaystyle \buintp{011} = 3$$

3. $$\displaystyle \buintp{1001} = 9$$

4. $$\displaystyle \buintp{1111} = 15$$

5. $$\displaystyle \buintp{101111} = 47$$

1. $$\displaystyle \buintp{1011} + \buintp{1101} = 11 + 13 = 24 = \buintp{11000}$$

2. $$\displaystyle \buintp{11} + \buintp{1101} = 3 + 13 = 16 = \buintp{10000}$$

3. $$\displaystyle \buintp{10111} + \buintp{1101} = 23 + 13 = 36 = \buintp{100100}$$

4. $$\displaystyle \langle 1011 + 1101 \rangle = \buintp{11000} = 24 = \buintp{11000}$$

#### 5.and, or, xor.

1. Show $$\bxor$$ and $$\bor$$ associative using a truth table.

2. Which of the three operations distribute over which other operation? In other words, for which operators $$\circ, \circ'\in\{\band,\bor,\bxor\}$$ does $$a\circ(b\circ' c)=(a\circ b)\circ'(a\circ c)$$ hold for any $$a,b,c\in \Bit\text{?}$$

202207281550

202204151400
Solution.
1. \begin{equation*} \begin{array}{|c|c|c|c|c|c|c|} \hline a \amp b \amp c \amp (b \bxor c) \amp a \bxor(b\bxor c) \amp (a \bxor b) \amp (a\bxor b)\bxor c\\ \hline 0 \amp0 \amp 0 \amp 0 \amp 0 \amp 0 \amp0 \\ 0\amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \amp1 \\ 0\amp 1 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1\\ 0\amp 1 \amp 1 \amp 0 \amp0 \amp1 \amp 0\\ 1\amp 0 \amp 0 \amp 0 \amp1 \amp 1 \amp 1\\ 1\amp 0 \amp 1 \amp 1 \amp 0 \amp 1 \amp 0\\ 1\amp 1 \amp 0 \amp1 \amp 0 \amp 0 \amp 0\\ 1\amp 1 \amp1 \amp0 \amp 1 \amp 0 \amp 1\\ \hline \end{array} \end{equation*}
\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|} \hline a \amp b \amp c \amp (b \bor c) \amp a \bor(b\bor c) \amp (a \bor b) \amp (a\bor b)\bor c\\ \hline 0 \amp0 \amp 0 \amp 0 \amp 0 \amp 0 \amp0 \\ 0\amp 0 \amp 1 \amp 1 \amp 1 \amp 0 \amp 1\\ 0\amp 1 \amp 0 \amp1 \amp 1 \amp1 \amp 1\\ 0\amp 1 \amp 1 \amp1 \amp 1 \amp 1 \amp1 \\ 1\amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1\\ 1\amp 0 \amp 1 \amp1 \amp1 \amp1 \amp1 \\ 1\amp 1 \amp 0 \amp1 \amp1 \amp1 \amp1 \\ 1\amp 1 \amp1 \amp 1 \amp1 \amp1 \amp1 \\ \hline \end{array} \end{equation*}
2. The following distributive laws hold:

• $$\displaystyle a\bor(b\band c)=(a\bor b)\band(a\bor c)$$

• $$\displaystyle a\band(b\bor c)=(a\band b)\bor(a\band c)$$

• $$\displaystyle a\band(b\bxor c)=(a\band b)\bxor(a\band c)$$

#### 6.Elementary Operations on Bits.

There are actually operations that are more elementary than and, or, xor. One of them is nand $$\bneg{a\band b}$$ which is $$0$$ if $$a=b=1$$ and $$1$$ otherwise. Show how to express and, or, xor using nand. What other elementary operations like nand are there?

202207281550

202204151400
Solution.
This is the truth table for nand.
\begin{equation*} \begin{array}{|c|c|c|} \hline a \amp b \amp \bneg{a\band b}\\ \hline 0\amp 0 \amp 1\\ 0\amp 1 \amp 1\\ 1\amp 0 \amp 1\\ 1\amp 1 \amp 0\\ \hline \end{array} \end{equation*}
We can express negation using nand:
\begin{equation*} \begin{array}{|c|c|c|} \hline a \amp \bneg{a\band a} \amp \bneg{a}\\ \hline 0\amp 1 \amp 1\\ 1\amp 0 \amp 0\\ \hline \end{array} \end{equation*}
We can express conjunction (and) using nand. We can use plain old negation, since we already know how to encode it just using nand.
\begin{equation*} \begin{array}{|c|c|c|c|} \hline a \amp b \amp \bneg{\bneg{a\band b}} \amp a \band b\\ \hline 0\amp 0 \amp 0 \amp 0\\ 0\amp 1 \amp 0 \amp 0\\ 1\amp 0 \amp 0 \amp 0\\ 1\amp 1 \amp 1 \amp 1\\ \hline \end{array} \end{equation*}
We can now express disjunction (or) using nand. Again, we also use negation and conjunction since we know how to express them.
\begin{equation*} \begin{array}{|c|c|c|c|c|c|} \hline a \amp b \amp \bneg{a} \amp \bneg{b} \amp \bneg{\bneg{a}\band\bneg{b}} \amp a \bor b\\ \hline 0\amp 0 \amp 1 \amp 1 \amp 0 \amp 0\\ 0\amp 1 \amp 1 \amp 0 \amp 1 \amp 1\\ 1\amp 0 \amp 0 \amp 1 \amp 1 \amp 1\\ 1\amp 1 \amp 0 \amp 0 \amp 1 \amp 1\\ \hline \end{array} \end{equation*}
We have already shown that we can express and and or with nand. So it is enough to show that xor can be expressed with and and or to prove that we can only express it with nand.
\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|c|} \hline a \amp b \amp \bneg{a} \amp \bneg{b} \amp \bneg{a}\band b \amp a\band \bneg{b} \amp (\bneg{a}\band b)\bor(a\band\bneg{b}) \amp a\bxor b\\ \hline 0\amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0\\ 0\amp 1 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1\\ 1\amp 0 \amp 0 \amp 1 \amp 0 \amp 1 \amp 1 \amp 1\\ 1\amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0\\ \hline \end{array} \end{equation*}
Another elementary operation like nand is nor. It is $$1$$ if $$a=b=0$$ and $$0$$ otherwise.

#### 7.Nand is elementary.

Show that nand is indeed universal, i.e. every boolean function $$f(a,b)$$ can be expressed only using nands.

202207281550

202204151400
Hint.

First, show that every boolean function can be represented using and, not and or. Then use the other exercise to relate this to nand. You may also need to prove that not can be expressed using nand.

Solution.

In total, there are 16 different possibilities for boolean functions with two arguments: Since $$f(a,b)$$ takes two arguments, each of which can be either $$0$$ or $$1\text{,}$$ there are exactly $$4$$ possible different inputs. For each of these inputs there are 2 different possible results: $$0$$ and $$1\text{.}$$ This means in total we can find $$2^4 = 16$$ functions. All of functions can be represented only using and, or, and negation, as follows:

\begin{equation*} \begin{array}{|c||c|c|c|c|c|c|c|c|} \hline f(0,0) \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \\ f(0,1) \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \\ f(1,0) \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \\ f(1,1) \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ \hline f(a,b) \amp a \band \bneg{a} \amp \bneg{a} \band \bneg{b} \amp \bneg{a} \band b \amp \bneg{a} \amp a \band \bneg{b} \amp \bneg{b} \amp (a \band \bneg{b}) \bor (b \band \bneg{a})\amp \bneg{a} \bor \bneg{b}\\ \hline \end{array} \end{equation*}
\begin{equation*} \begin{array}{|c||c|c|c|c|c|c|c|c|} \hline f(0,0) \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \amp 0 \amp 1 \\ f(0,1) \amp 0 \amp 0 \amp 1 \amp 1 \amp 0 \amp 0 \amp 1 \amp 1 \\ f(1,0) \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \amp 1 \amp 1 \\ f(1,1) \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \amp 1 \\ \hline f(a,b) \amp a \band b \amp (a \band b) \bor (\bneg{a} \band \bneg{b}) \amp b \amp b \bor \bneg{a} \amp a \amp a \bor \bneg{b} \amp a \bor b \amp a \bor \bneg a \\ \hline \end{array} \end{equation*}

Now that we have shown that every boolean function with two arguments can be represented with and, not, and or and that we have shown in exercise 6 that and and or can be expressed with nand, the only thing left to show is that not can also be expressed using only nand.

\begin{equation*} \begin{array}{|c|c|c|} \hline a \amp \bneg{a} \amp \bneg{a \band a} \\ \hline 0 \amp 1 \amp 1 \\ 1 \amp 0 \amp 0 \\ \hline \end{array} \end{equation*}

In conclusion, we have now shown that and, or and not can be expressed using only nand, because we have also shown that every boolean function with two arguments can be represented by and, or and not we can conclude that nand is universal.

#### 8.Arithmetics Proofs.

Prove:
1. Let $$x$$ be a sequence of digits of length $$n$$ and let $$y$$ be a sequence of digits of length $$m\text{.}$$
Show that $$\buintpb{x\cdot y}{\beta} = \buintpb{x}{\beta}\cdot\beta^m + \buintpb{y}{\beta}$$ holds for any $$\beta\in\Nat^\ast\text{.}$$
Remember that $$\cdot$$ on sequences of digits is concatenation. For instance, $$ab\cdot cd = abcd$$

2. Show that for all $$n\gt 0, \buintpb{(\beta -1)^n}{\beta} + 1 = \beta^n\text{.}$$

3. Let $$x$$ be a sequence of digits of length $$n\text{.}$$ Show that $$\buintpb{x}{\beta}\lt\beta^n$$ holds.

202207281550

202204151400
Solution.
1. \begin{align*} \buintpb{x\cdot y}{\beta} \amp= \sum_{i=0}^{n-1} x_i\beta^{m+i}+\sum_{i=0}^{m-1} y_i\beta^i\\ \amp= \beta^m\cdot\sum_{i=0}^{n-1} x_i\beta^{i}+\sum_{i=0}^{m-1} y_i\beta^i \\\\ \amp= \beta^m\cdot\buintp{x} + \buintp{y}\qquad\square \end{align*}

2. \begin{align*} \buintpb{(\beta -1)^n}{\beta} + 1 \amp= \sum_{i=0}^{n-1}(\beta -1)\beta^i + 1\\ \amp=(\beta-1)\beta^{n-1}+(\beta-1)\beta^{n-2}+\cdots+(\beta-1)\beta+(\beta-1)+1\\ \amp= \beta^n-\underbrace{\beta^{n-1}+\beta^{n-1}}_0+\cdots\underbrace{-\beta+\beta}_0\underbrace{-1+1}_0\\ \amp= \beta^n\qquad\square \end{align*}

3. Using induction:

$$n = 1:$$

\begin{equation*} x \leq \beta -1 \lt \beta^1\text{.} \end{equation*}

$$n\rightarrow n + 1:$$

Induction hypothesis: $$\buintpb{x_{n-1}\cdots x_0}{\beta}\lt\beta^n$$

\begin{align*} \buintpb{x_{n}\cdots x_0}{\beta} \amp= x_n\cdot\beta^n + \buintpb{x_{n-1}\cdots x_0}{\beta}\\ \amp\lt x_n\cdot\beta^n + \beta^n ~~~~~~~~~~~~~~~|\ \text{induction hypothesis}\\ \amp\leq (\beta-1)\cdot\beta^n + \beta^n ~~~~~~~~~|\ x_n \leq \beta -1\\ \amp= \beta^{n+1} - \beta^n + \beta^n\\ \amp= \beta^{n+1}\qquad\square \end{align*}