# Exercise 1.2: Decimal/Binary Converter

A number generator  $Z$  supplies decimal values in the range  $1$  to  $15$.

• These are converted into binary numbers  (block outlined in red).
• The output consists of the four binary values  $A$,  $B$,  $C$  and  $D$  with decreasing significance.
• For example  $Z = 11$  delivers the binary values
$$A = 1, \ B = 0, \ C = 1, \ D = 1.$$

Set-theoretically,  this can be represented as follows:

$$Z = 11\qquad\widehat{=}\qquad A \cap\overline{ B} \cap C \cap D.$$

Three more Boolean expressions are formed from the binary quantities  $A$,  $B$,  $C$  and  $D$  and their union set is denoted  $X$ :

$U = A \cap \overline{D}$
$V = \overline{A} \cap B \cap \overline{D}$
$$W,\; {\rm where} \; \, \overline{W} = \overline{A} \cup \overline{D} \cup (\overline{B} \cap C) \cup (B \cap \overline{C}).$$
• Note that  $Z = 0 \ ⇒ \ A = B = C = D = 0$  is already excluded by the number generator.
• Note also that not all input quantities  $A$,  $B$,  $C$  and  $D$  are used to calculate all intermediate quantities  $U$,  $V$  and  $W$,  resp.

Hints:

• The exercise belongs to the chapter  Set theory basic.
• The topic of this chapter is illustrated with examples in the (German language) learning video:
"Mengentheoretische Begriffe und Gesetzmäßigkeiten"   ⇒   "Set-theoretical terms and laws".

### Questions

1

Which statements are true regarding the random variable  $U$?

 $U$  contains two elements. $U$  contains four elements. The smallest element of  $U$  is  $4$. The largest element of  $U$  is  $14$.

2

Which statements are true regarding the random variable  $V$?

 $V$  contains two elements. $V$  contains four elements. The smallest element of  $V$  is  $4$. The largest element of  $V$  is  $14$.

3

Which statements are true regarding the random variable  $W$?

 $W$  contains two elements. $W$  contains four elements. The smallest element of  $W$  is  $4$. The largest element of  $W$  is  $14$.

4

Which statements are true regarding the random quantity  $P$ ?

 $P$  contains all powers of two. $P$  contains all prime numbers. $P$  describes the empty set  $\phi$. $P$  is identical with the universal set  $G = {1,2, \ \text{...} \ , 15}$.

### Solution

#### Solution

(1)  The event  $U$  contains

• those numbers greater/equal to eight  $(A = 1)$,
• which are even  $(D = 0)$:  $8, 10, 12, 14$

⇒  Proposed solutions 2 and 4  are correct.

(2)  The event  $V$  consists of the two numbers  $4$  (binary 0100) and  $6$  (binary 0110)   ⇒   The correct solutions are 1 and 3.

(3)  For the event  $W$,  de Morgan's theorem holds:

$$\overline W = \overline A \cup \overline D \cup (\overline B \cap C) \cup (B \cap \overline C) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} W = \overline{\overline W} = A \cap D \cap (\overline{\overline B \cap C}) \cap (\overline{B \cap \overline C}).$$
• Using de Morgan's theorems,  it further follows:
$$W = A \cap D \cap (B \cup \overline C) \cap (\overline B \cup C).$$
• Finally,  using the Boolean relation  $(B \cup \overline C) \cap (\overline B \cup C) = (B \cap C) \cup (\overline B \cap \overline C)$  we obtain  (see sketch):
$$W = (A \cap B \cap C \cap D) \cup (A \cap \overline B \cap \overline C \cap D).$$
• Thus,  $W$  contains the numbers  $15$  and  $9$    ⇒   only the  proposed solution 1  is correct.

(4)  The union of  $U$,  $V$  and  $W$  contains the following numbers:   $4, 6, 8, 9, 10, 12, 14, 15$.

• Accordingly, the set  $P$  as the complement of this union is:
$$P = {\{1, 2, 3, 5, 7, 11, 13\}}.$$
• These are exactly the prime numbers which can be represented with four bits   ⇒   Proposed solution 2.