A bit (binary digit) is a unit of measure for information, introduced by C. Shannon in 1948.
It might be seen as the minimal amount of information needed in order to distinguish among two events occurring with the same probability.
Bits are used in Information Theory and - in general - in most of Computer Science applications.
They are denoted with the constants \(0\) and \(1\), representing the two events with the same probability. Their set is often denoted with \(\{0,1\}\), but we need another notation, that is,

Indeed, with this different notation we mean that we can perform operations on bits. More precisely, we want to introduce two operations, sum and multiplication, retaining some similarity with the usual operations of sum and product for numbers. The numbers we are interested in are integers, which we collect in a set called \(\mathbb{Z}=\{\ldots,-1,0,1,2,\ldots\}\), non-negative integers, which we collect in a set called \(\mathbb{N}=\{0,1,2,\ldots\}\), and rational numbers, which we collect in a set called \(\mathbb{Q}=\{\ldots,\frac{-5}{101},0,\frac{1}{2},3,\ldots\}\).
Since \(\mathbb{F}_{2}\) is so small, we can use the following table to show how to sum and multiply bits.

The first column and the second contain the values of two input variables, \(a\) and \(b\), representing the two bits we sum or multiply; the third and the fourth, respectively, contain the sum and the product of \(a\) and \(b\).

Operations on bits share properties with those involving integer or rational numbers.
Let us start with a comparison between the sum in \(\mathbb{F}_{2}\) and the sum in \(\mathbb{Z}\).

We can sum \(2,3\) and \(4\) in \(\mathbb{Z}\) and it happens that

so we can write also \(9=2+3+4\), omitting the parentheses. Actually, this holds for any three numbers in \(\mathbb{Z}\).
We claim that this holds also for the sum of bits. For example

The reader can verify our claim for any \(a,b,c\in\mathbb{F}_{2}\).
Any time we have a set and a sum operation which satisfies the general property

we say that the operation is associative.
Therefore, we can conclude that both the sum in \(\mathbb{Z}\) and the sum in \(\mathbb{F}_{2}\) are associative operations.

Consider now \(2,3\in\mathbb{Z}\). We know that \(2+3=3+2=5\) and this holds for any pair of integers. We claim that this holds also for bits, as for example

We leave to the reader the verification of this statement for each \(a,b\in\mathbb{F}_{2}\).
We can formalize this property by saying that both the sum in \(\mathbb{Z}\) and the sum in \(\mathbb{F}_{2}\) are commutative operations. In a more general setting, a sum operation on a set is called commutative if for any \(a,b\) in that set we have

Now we take a close look at \(0\in\mathbb{Z}\). Considering any integer \(a\), we have that \(a+0=0+a=a\), as for example \(3+0=0+3=3\). In other words, summing a number with zero leaves the number unchanged (and this happens only for \(0\)).
The same happens with \(0\in\mathbb{F}_{2}\), since in \(\mathbb{F}_{2}\) \(0+0=0\) and \(0+1=1+0=1\).
In a general setting, if we have a sum operation with a special element \(e\) such that \(a+e=e+a=a\) for any \(a\) in the set, then we say that \(e\) is the neutral element of the operation.
Therefore, we can say that \(0\in\mathbb{F}_{2}\) is the neutral element of the sum in \(\mathbb{F}_{2}\), while \(0\in\mathbb{Z}\) is the neutral element in \(\mathbb{Z}\).

Another important property of the sum in \(\mathbb{Z}\) is that, given an element \(a\in\mathbb{Z}\), we can always find an element \(b\in\mathbb{Z}\) such that \(a+b=b+a=0\). For example, for \(a=3\), we have \(b=-3\), getting \(3+(-3)=(-3)+3=0.\)
In the general case, when there is a set with a sum, if for any element \(a\) there is another element \(b\) such that \(a+b=0\) and this element is unique, then we say that \(b\) is the opposite of \(a\) and we write \(b=-a\).
Opposites exist also for the sum in the set of bits, indeed

and so in \(\mathbb{F}_{2}\):

• •

  the opposite of \(1\) is \(1\) (and \(-1=1\)),

• •

  the opposite of \(0\) is \(0\) (and \(-0=0\)).

It is time that we introduce more formalism. We can consider any set \(G\) endowed with an operation \(*\) such that for any \(a,b\) in \(G\) the operation outputs another element \(a*b\) of \(G\). If the operation satisfies the following stringent properties

• i)

  \(*\) is associative;

• ii)

  \(*\) is commutative;

• iii)

  \(*\) has a neutral element;

• iv)

  each element of \(G\) has an opposite w.r.t. \(*\)

then \(G\) (with the operation \(*\)) is called an abelian group.

Our previous observations about the sum in \(\mathbb{Z}\) and the sum in \(\mathbb{F}_{2}\) lead us to claim that both \(\mathbb{Z}\) and \(\mathbb{F}_{2}\) are abelian groups w.r.t. their sum.

Having dealt with the sum, we pass now to compare the multiplication of integers and that of bits.
Consider again \(2,3,4\in\mathbb{Z}\). We have that

so, as it was for the sum, we can remove the parentheses and write

The same holds for bits, for example

We leave to the reader the verification that this holds for each bit triplet.
This property can be formalized by saying that both the multiplication in \(\mathbb{Z}\) and the multiplication in \(\mathbb{F}_{2}\) are associative. In formulas, we say that for any \(a,b,c\) (which are elements of \(\mathbb{Z}\) or of \(\mathbb{F}_{2}\)), we have

Consider now \(2,3\in\mathbb{Z}\). We know that \(2\cdot 3=3\cdot 2=6\) and this holds for every pair of integers. We claim the same for bits, since for example

We leave, as an exercise to the reader, to verify this for each \(a,b\in\mathbb{F}_{2}\).
Again, this property can be formalized by saying that both the product in \(\mathbb{Z}\) and the product in \(\mathbb{F}_{2}\) are commutative. In formulas, we say that for any \(a,b\) (which are elements of \(\mathbb{Z}\) or of \(\mathbb{F}_{2}\)), we have

We examine now the behaviour of \(1\in\mathbb{Z}\). Taken any other integer number \(a\), we have that \(a\cdot 1=1\cdot a=a\), for example \(3\cdot 1=1\cdot 3=3\), so multiplying a number with \(1\) gives, as result, again that number.
Also the bit \(1\in\mathbb{F}_{2}\), has the same behaviour, since \(1\cdot 0=0\cdot 1=0\) and \(1\cdot 1=1.\)
We can formalize this statement by saying that \(1\) is the neutral element of the product, both in \(\mathbb{Z}\) and in \(\mathbb{F}_{2}\).
Once we have introduced a neutral element, we might wish to go on and define a group, as we did with the sum. Unfortunately, this cannot always be done, as we will see from now on.

Given \(2\in\mathbb{Z}\), we know that we cannot find any integer \(b\) such that \(2\cdot b=b\cdot 2=1\). It is still possible to find such a number \(b\), but we need to move to fractions i.e. consider the set of rational numbers \(\mathbb{Q}\) instead of \(\mathbb{Z}\). The set \(\mathbb{Q}\) is not so different from \(\mathbb{Z}\), in particular all the properties previously stated for \(\mathbb{Z}\) also hold for \(\mathbb{Q}\). Still, if we consider \(2\in\mathbb{Q}\) we can easily find \(b=\frac{1}{2}\in\mathbb{Q}\), for which \(2\cdot\frac{1}{2}=\frac{1}{2}\cdot 1=1\).
We can easily find a similar rational for each nonzero element of \(\mathbb{Q}\) (while we cannot for \(0\)).
It is of utmost interest to observe that bits behave like rational numbers rather than integers. Indeed, \(1\cdot 1=1\) in \(\mathbb{F}_{2}\), but we cannot find any bit \(b\) such that \(1\cdot b=b\cdot 1=1\).
We can formalize this property, saying that each nonzero element of \(\mathbb{Q}\) (respectively \(\mathbb{F}_{2}\)) has a multiplicative inverse, i.e.
\(\forall a\in\mathbb{Q}\setminus\{0\}(\textrm{ resp }\mathbb{F}_{2}\setminus\{0\}),\exists a^{-1}\in\mathbb{Q}\setminus\{0\}(\textrm{ respectively }\mathbb{F}_{2}\setminus\{0\})\textrm{ s.t. }a\cdot a^{-1}=a^{-1}\cdot a=1.\) In \(\mathbb{F}_{2}\), the (multiplicative) inverse of \(1\) is \(1\) and \(0\) has no (multiplicative) inverse (but keep in mind that the opposite of \(0\) exists: \(-0=0\) in \(\mathbb{F}_{2}\)).
Finally, we show how sum and multiplication interact. Taken \(2,3,4\in\mathbb{Q}\), we have that

This holds in general for three elements of \(\mathbb{Q}\) and we can notice the same good property also in \(\mathbb{F}_{2}\), for example:

We can formalize this property, saying that, both in \(\mathbb{Q}\) and in \(\mathbb{F}_{2}\), the multiplication is distributive w.r.t. the sum. In formulas

A set \(G\), endowed with two operations (sum and multiplication), denoted by \(+,\cdot\), is called field if

• i)

  \(G\) is an abelian group w.r.t. \(+\); let \(0\) be the neutral element;

• ii)

  \(G\setminus\{0\}\) is an abelian group w.r.t. \(\cdot\);

• iii)

  \(\cdot\) is distributive w.r.t. \(+\).

According to the above definition, we can say that both \(\mathbb{Q}\) and \(\mathbb{F}_{2}\) are fields, whereas \(\mathbb{Z}\) is not a field.

The notation \(\mathbb{F}_{2}\) for the set of bits (that - from now on - we will call the field of bits), reflects this fact, since \(\mathbb{F}\) stands for ”field” and the subscript \(2\) stands for its size.

Bits can also be seen as a way to represent the logical values TRUE/FALSE. The usual notation is \(0=\mathrm{FALSE}\) and \(1=\mathrm{TRUE}\).
Once fixed this notation, we have the following well known truth tables:

We conclude this section with proposing a few exercises.