deletions | additions       diff --git a/bits1.tex b/bits1.tex  index 9848d9a..540c57e 100644  --- a/bits1.tex  +++ b/bits1.tex 
...
The first column and the second one represent the values of two input variables, $a$ and $b$, used here to represent the two bits we have to sum or multiply; the third and the fourth ones, respectively, represent the results of the sum and the product of $a$ and $b$.\\  \medskip   Performing %Performing  operations with bits is not the same as doing so with ``usual''   (real) %``usual''   %(real)  numbers (from now on, we denote the set of real numbers with $\RR$).  \\  Look $\RR$%).  %\\  %Look  now at third row. We observe that, summing the bit $1$ with the bit $1$, %$1$,  one gets $0$: $$1+1=0.$$ %$$1+1=0.$$  % indexed %indexed  % by %by  a bit ($0$ or $1$) except that the first that contains the symbol % representing %representing  the operation.    
...
% performing operations with bits is not the same as doing so with ``usual''   % (real) numbers.  Even %Even  if the operations on $\Fb$ are similar but not equals to the corresponding %corresponding  ones on bits, $\Fb$ has very good properties with respect to %to  the operations $+$ and $\cdot$, that are in common with the real numbers.   \\  We %numbers.   %\\  %We  can observe that $\Fb$ is a \emph{field}, as well as $\RR$ is. \\ In %In  particular, every element of $\Fb$ has an \emph{opposite} for the sum, ``$+$'', %``$+$'',  and every element of $\Fb$, that is different from $0$, has an \emph{inverse}, %\emph{inverse},  exactly as the field of real numbers. For example in the field %field  of real numbers \[ %\[  %  5+(-5)=0 \mbox{ and } 5\cdot \frac{1}{5}=1. %  \] In %In  the set $\Fb$ we have: \begin{enumerate} %\begin{enumerate}  %  \item The opposite of $1$ is $1$, in fact $1+1=0$. %  \item The opposite of $0$ is $0$, as in $\RR$. %  \item The inverse of $1$ is $1$, in fact $1\cdot 1=1$. %  \item The inverse of $0$ does not exist as in $\RR$. \end{enumerate} %\end{enumerate}    %  The notation for the set of bits (that - from now on - we will call the \emph{field %\emph{field  of bits}), reflects this fact. Indeed, $\mathbb{F}$ stands for %for  ``field'' and the subscript $2$ stands for the \emph{size} of the set itself, %itself,  i.e. the number of its elements. %  
...
% Can you prove that $\Fb$ is actually a field?   % \end{Exercise}  From %From  the rules of the sum of bits, we can derive how to compute \emph{multiples} \emph{mul% tiples}  of bits.\\ As we can see by the above table, operations with bits are similar, but not equal, to the operations involving integer or rational numbers (i.e. operations in $\ZZ$ or $\QQ$), to which we are used.  \\  Let us first see the similarities among them, starting with a comparison between the sum in $\Fb$ and in $\ZZ$.\\  \smallskip  We know that $2,3$ and $4$ can be summed and it happens that  $$(2+3)+4=5+4=9=2+7=2+(3+4),$$  so we can write also $9=2+3+4$, omitting the parentheses. Clearly, this holds in general, considering three arbitrary numbers in $\ZZ$.  \\  The same property also holds for the sum of bits. For example  $$ (1+0)+1=1+1=0=1+(0+1)=1+0+1.$$  The reader can verify that it is true for each $a,b,c \in \Fb$.\\  This property can be formalized by saying that both the sum in $\ZZ$ and the sum in $\Fb$ are \emph{associative}. In formulas, we say that $\forall a,b,c$ (which are elements of $\ZZ$ or of $\Fb$), we have  $$(a+b)+c=a+(b+c)=a+b+c.$$  \smallskip  Consider now $2,3 \in \ZZ$. We know that $2+3=3+2=5$ and this holds for every couple of integer numbers. But this is again true also for bits, for example  $$0+1=1+0=1.$$  We leave, as an exercise to the reader, to verify that it is true for each $a,b \in \Fb$.\\  This property can be formalized by saying that both the sum in $\ZZ$ and the sum in $\Fb$ are \emph{commutative}. In formulas, we say that $\forall a,b$ (which are elements of $\ZZ$ or of $\Fb$), we have  $$a+b=b+a.$$  \smallskip  Now we examine the behaviour of $0 \in \ZZ$. Taken any other integer number $a$, we have that $a+0=0+a=a$, for example $3+0=0+3=3$, so summing a number with zero gives, as result, again that number.  \\  Also the bit $0 \in \Fb$, has the same behaviour, since $0+0=0$ and $0+1=1+0=1.$\\  We can formalize this statement by saying that $0$ is the \emph{neutral element} of the sum, both in $\ZZ$ and in $\Fb$.  \\  \smallskip  Another important property of the sum in $\ZZ$ is that, given an element $a \in \ZZ$, we can always find an element $b \in \ZZ$ such that $a+b=b+a=0$. For example, for $a=3$, we have $b=-3$, getting $3+(-3)=(-3)+3=0.$  \\  This property is shared also by the set of bits, indeed   $$0+0=0 \textrm{ and } 1+1=0.$$  More formally, we can say that each element $a \in \ZZ$ (resp. in $\Fb$) has an \emph{opposite} w.r.t. the sum.\\  In $\Fb$, we have:  \begin{itemize}  \item the opposite of $1$ is $1$  \item the opposite of $0$ is $0$.  \end{itemize}  \\  Now, an arbitrary set $G$, endowed with an operation $*$ s.t.:  \begin{itemize}  \item[i)] $*$ is associative;  \item[ii)] $*$ is commutative;  \item[iii)] $*$ has a neutral element;  \item[iv)] each element of $G$ has an opposite w.r.t. $*$  \end{itemize}  is called \emph{abelian group}.  \\  The adjective "abelian" only indicates that ii) holds, i.e. that the operation $*$ is commutative. If only i), iii) and iv) hold, $G$ is only a \emph{group}.\\  In our context, from the argument above, we can say that both $\ZZ$ and $\Fb$ are \emph{abelian groups w.r.t. the sum}.  \begin{Exercise}\label{QAbelian}  Is $\QQ$, the set of rational numbers, an abelian group w.r.t. the sum? Give detailed comments.  \end{Exercise}  \medskip  Let us examine now the multiplication of integer numbers and of bits.  \\  Consider again $2,3,4 \in ZZ$. We have that   $$(2\cdot 3)\cdot 4 = 6 \cdot 4 =24 =2 \cdot (3\cdot 4) = 2 \cdot 12,$$  so, as it was for the sum, we can remove the parentheses and write   $$2\cdot 3 \cdot 4=24.$$  The same holds for bits, for example  $$(0\cdot 1)\cdot 1= 0\cdot 1 =0 = 0\cdot (1 \cdot 1) = 0\cdot 1 = 0\cdot 1\cdot 1.$$  We leave the verification that it holds for each three bits to the reader.  \\  This property can be formalized by saying that both the product in $\ZZ$ and the product in $\Fb$ are \emph{associative}. In formulas, we say that $\forall a,b,c$ (which are elements of $\ZZ$ or of $\Fb$), we have  $$(a \cdot b)\cdot c=a\cdot (b \cdot c)=a\cdot b \cdot c.$$  \smallskip  Consider now $2,3 \in \ZZ$. We know that $2\cdot 3=3\cdot 2=6$ and this holds for every couple of integer numbers. But this is again true also for bits, for example  $$0\cdot 1=1\cdot 0=1.$$  We leave, as an exercise to the reader, to verify that it is true for each $a,b \in \Fb$.\\  This property can be formalized by saying that both the product in $\ZZ$ and the product in $\Fb$ are \emph{commutative}. In formulas, we say that $\forall a,b$ (which are elements of $\ZZ$ or of $\Fb$), we have  $$a\cdot b=b\cdot a.$$  \smallskip  We examine now the behaviour of $1 \in\ZZ$.  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 one gives, as result, again that number.  \\  Also the bit $1 \in \Fb$, 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 \emph{neutral element} of the product, both in $\ZZ$ and in $\Fb$.  \\  \smallskip  Now, given $2 \in \ZZ$, we know that we \emph{cannot} find any integer number $b$ such that $2 \cdot b = b \cdot 2 =1$; in order to find such an element, we need to move to \emph{fractions} i.e. consider the set of \emph{rational numbers} $\QQ$ instead of $\ZZ$.  \\  Notice that all the properties that we stated for $\ZZ$ also hold for $\QQ$ and consider $2 \in \QQ$. In this case, we can easily find $b= \frac{1}{2} \in \QQ$, for which $2 \cdot \frac{1}{2} = \frac{1}{2} \cdot 1 =1$.  \\  This can be easily done for each \emph{nonzero} element of $\QQ$, while it is false for $0$.  \\  We point out that exactly the same holds for bits: $1 \cdot 1=1$ but no elements in $\Fb$ can be multiplied by zero, getting $1$ as results.  \\  We can formalize this property, saying that each nonzero element of $\QQ$ (resp $\Fb$) has a \emph{inverse} w.r.t. multiplication, i.e.  $$\forall a \in \QQ\setminus \{0\}\, (\textrm{ resp } \Fb\setminus \{0\}),\, \exists a^{-1} \in \QQ\setminus \{0\}\, (\textrm{ resp } \Fb\setminus \{0\}) \textrm{ s.t. } a\cdot a^{-1} =a^{-1} \cdot a =1. $$  In $\Fb$, the inverse of $1$ is $1$ and $0$ has no inverse.  \\  Finally, we show how sum and multiplication interact. Taken $2,3,4\in \QQ$, we have that   $$2 \cdot(3+4)= 2\cdot 7 =14 = (2\cdot 3)+(2\cdot 4) = 6+8. $$  This holds in general for three elements of $\QQ$ and we can notice the same good property also in $\Fb$, for example:  $$1 \cdot(0+1)= 1\cdot 1 =1 = (1\cdot 0)+(1\cdot 1) = 0+1. $$  We can formalize this property, saying that, both in $\QQ$ and in $\Fb$, the multiplication is \emph{distributive} w.r.t. the sum \footnote{The operations are commutative, so it is not necessary to multiply to the right}.  In formulas  $$\forall a,b,c \in \QQ (\textrm{resp } $\Fb$) a\cdot (b+c)=(a\cdot b) + (a \cdot c).$$  Now, a set $G$, endowed with two operations, denoted by $+,\cdot$, is called \emph{field} if  \begin{itemize}  \item[i)] $G$ is an abelian group w.r.t. $+$;  \item[ii)] $\cdot$ is associative;  \item[iii)] $\cdot$ is commutative;  \item[iv)] $\cdot$ has a neutral element;  \item[v)] each nonzero element of $G$ has an inverse w.r.t. $\cdot$  \item[vi)] $\cdot$ is distributive w.r.t. $+$.  \end{itemize}  According to the above definition, we can say that both $\QQ$ and $\Fb$ are fields, whereas $\ZZ$ is not a field.  The notation for the set of bits (that - from now on - we will call the field of bits), reflects this fact. Indeed, $\FF$ stands for "field" and the subscript $2$ stands for the size of the set itself, i.e. the number of its elements.  \begin{Exercise}\label{nogroup}  Is $\QQ$ an abelian group, with respect to the multiplication?  If so, prove it; if not, provide a counterexample.  \end{Exercise}  All the properties we have shown so fare, represent similarities between the operations in $\Fb$ and in $\ZZ$ or $\QQ$.  \\  An important difference between the sum in $\Fb$ and in $\ZZ$ or $\QQ$ is that summing the bit $1$ with the bit $1$, one gets $0$:  $$1+1=0.$$  We see now that this difference reflects also in the computation of \emph{multiples} of bits.  \\  Let us consider first $2\cdot 0$. It means $0+0$ then it   is $0$. \\  If we take $2 \cdot 1$ we have $2 \cdot 1=1+1=0$, so we can notice that $0$ is also the \emph{double} of $1$.