Section 1.2 Binary Numbers
In the following, we will limit ourselves to binary numbers and therefore set \(\bbase=2\text{.}\) We will also write \(\buintp{x}\) instead of \(\buintpb{x}{2}\text{.}\) We also have only two digits \(\Bit\defeq\{0,1\}\text{.}\) An element of \(\Bit\) is called bit. An element of \(\Bit^8\) is called byte. The complement \(\bneg b\) of a bit \(b\) is defined as \(\bneg b\defeq 1-b\text{.}\) A sequence of bits is called a bit string. In a bit string \(\bseq bn\text{,}\) bit \(b_{n-1}\) is called the most significant bit and \(b_0\) is called the least significant bit.
We define three binary operations on bits and, or, and xor (exclusive or) by means of a value table. These primitive operations are enough to formulate the addition of bit strings (sequences of bits).
| and | or | xor | ||
| \(a\) | \(b\) | \(a\band b\) | \(a\bor b\) | \(a\bxor b\) |
| \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(1\) | \(1\) | \(1\) | \(0\) |
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?
202412201714
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.Checkpoint 1.2.2. Nand is elementary.
Show that nand is indeed universal, i.e. every boolean function \(f(a,b)\) can be expressed only using nands.
202412201714
Hint.
Solution.
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.
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.
Hexadecimal Numbers.
It is common to write bit strings more compactly by grouping four bits together. There are 16 possible combinations of four bits, so four bits can encode 16 different numbers, and therefore, a packet of four bits can be represented by one symbol of the following set \(\{0,\dots,9,\mathrm{a},\dots\mathrm{f}\}\text{.}\) Defining
\begin{equation*}
\buintpb{a}{\mathrm{16}}=10,\dots,\buintpb{f}{\mathrm{16}}=15
\end{equation*}
gives numbers in a base 16 system, so-called hexadecimal numbers.
Example 1.2.3.
\begin{align*}
\buintpb{\mathrm{ff}}{16} \amp =\buintpb{11111111}2=\buintpb{255}{10}\\
\buintpb{80}{16} \amp =\buintpb{1000 0000}2=\buintpb{128}{10}\\
\buintpb{19\mathrm{fa}}{16} \amp = \buintpb{0001 1001 1111 1010}{2}
\end{align*}
Many programming languages support hexadecimal numbers. In C and languages that are syntactically inspired by C, you can use the prefix
0x to denote a hexadecimal number such as 0x19fa. Another common prefix used by some assembly lanaguges and Pascal-like languages is $ as in $19fa.
