In the following, we will limit ourselves to binary numbers and therefore set . We will also write instead of . We also have only two digits . An element of is called bit. An element of is called byte. The complement of a bit is defined as . A sequence of bits is called a bit string. In a bit string , bit is called the most significant bit and 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 | ||
There are actually operations that are more elementary than and, or, xor. One of them is nand which is if and otherwise. Show how to express and, or, xor using nand. What other elementary operations like nand are there?
Show that nand is indeed universal, i.e. every boolean function can be expressed only using nands.
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.
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 set . Defining
gives numbers in a base 16 system, so-called hexadecimal numbers.
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.