deletions | additions       diff --git a/bits1.tex b/bits1.tex  new file mode 100644  index 0000000..e0dd757  --- /dev/null  +++ b/bits1.tex 
...
\section{Bits standard operations and logic}\index{LectNo1}  A \emph{bit} (binary digit) is a unit of measure for information, introduced   by C. Shannon in 1948. Roughly speaking, it represents the minimal amount of   information needed in order to distinguish among to events occurring with the   same probability. Bits are used in Information Theory and - in general - in   most of Computer Science applications.  \\  They are represented with the constants $0 $ and $1$ (the two events with the   same probability). The set of the bits, in Mathematics is usually denoted by   %We have the Field of Bits $\Fb$. When we work in Computer Science we often   %consider  %two fundamental constants: $0 $ and $1$. These, viewed as a set   \[  \Fb = \{0,1\}   \]  The first topic we need to introduce in order to work with bits is the   possibility of performing operations with them.  \\  In the following table, we can see how to sum and multiply bits.  %can be enriched with the standard operations ``$+$'' and ``$\cdot$'':    \begin{table}[!htb]  \centering  \begin{tabular}{c|c|c|c}  $a$ & $b$ & $a+ b$ &$a \times b$\\  \hline  0 & 0 & 0 & 0\\  0 & 1 & 1 & 0\\  1 & 0 & 1 & 0\\  1 & 1 & 0 & 1  \end{tabular}  \caption{Sum and product}\label{SumProd}  \end{table}    The first and second columns represent the values of the input variables $a$ and $b$, the third and the fourth respectively the results of the sum and product of $a$ and $b$. Look at third row. We observe that summing the bit $1$ with the bit $1$ one gets $0$: $1+1=0$.  This also highlights that performing operations with bits is not the same as doing so with ``usual''   (real) numbers.  % indexed   % by a bit ($0$ or $1$) except that the first that contains the symbol   % representing the operation.           % \begin{table}[!htb]  % \begin{minipage}{.5\linewidth}  % % \caption{}  % \centering  % \begin{tabular}{c|cc}   % + & 0 & 1\\  % \hline  % 0 & 0 & 1\\  % 1 & 1 & 0  % \end{tabular}  %   % \end{minipage}%  % \begin{minipage}{.5\linewidth}  % \centering  % % \caption{}  % \begin{tabular}{c|cc}  % $\cdot$ & 0 & 1\\  % \hline  % 0 & 0 & 0\\  % 1 & 0 & 1  % \end{tabular}  %   %   % \end{minipage}   % \caption{Sum and product}\label{SumProd}  %   % \end{table}        %\begin {table}  % \caption {Sum}\label{Operat1}    % \caption {Product}\label{Operat2}  % \end{table}  % The left table in \ref{SumProd} is the table of sum. Both rows and columns are   % indexed   % by a bit ($0$ or $1$) except that the first that contains the symbol   % representing the operation.   % \begin{table}[!htb]  % \centering  % \begin{tabular}{c|cc} \label{OperatBold}  % + & 0 & \textbf{1}\\  % \hline  % 0 & 0 & 1\\  % \textbf{1} & 1 & \textbf{0}  % \end{tabular}  % \caption{$1+1=0$}\label{OnePlusOne}  %   % \end{table}  %     %   % Look at the boldface numbers in table \ref{OnePlusOne}; they indicate that summing the bit $1$ (row)   % with the bit $1$ (column) one gets $0$: $1+1=0$. This also highlights that   % performing operations with bits is not the same as doing so with ``usual''   % (real) numbers.  Anyway, $\Fb$ has very good properties with respect to the operations $+$ and $\cdot$, that are in common with the real numbers, from now on represented with $\RR$. Indeed, we can observe that $\Fb$ is a \emph{field}, as well as $\RR$ is. In particular every element of $\Fb$ has an opposite for the sum, ``+'', and every element of $\Fb$, that is different from $0$, has an inverse, exactly as the field of real numbers. For example in the field of real numbers  \[  5+(-5)=0 \mbox{ and } 5\cdot \frac{1}{5}=1.   \]  The notation for the set of bits (that - from now on - we will call the \emph{field of bits}), reflects this fact. Indeed, $\Fb$ stands for ``field'' and the subscript $2$ stands for the \emph{size} of the set itself, i.e. the number of its elements. That is   \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}  %   % \begin{Exercise}\label{ProveField}  % Can you prove that $\Fb$ is actually a field?   % \end{Exercise}  From the rules of the sum of bits, we can derive how to compute \emph{multiples} of bits. Let us consider $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$.  \begin{quote}  Multiplying a bit by $2$ we always obtain $0$.  \end{quote}  This has a precise meaning from a mathematical point of view, the concept of \emph{characteristic}. Given a field (in our case $\Fb$), it can happen that   some positive\footnote{notice: positive means \emph{different} from $0$!!} integer numbers, multiplied to all the elements of the field, give $0 $ as   result (in our case, we saw that $2$ has this property).\\  The smallest such number $p$ - if it exists - is called \emph{characteristic} of the field (the characteristic is $p=2$ in the field $\Fb$). If there are no number with this properties, we say that the field has characteristic $p=0$.  \begin{Exercise}\label{ProofChar}  We have already observed that $2\cdot 0 = 2 \cdot 1=0$, so $2$ is one of the numbers that multiplied to all the elements of the field of bits,   give $0 $ as result. Can you prove that $2$ is actually the characteristic of $\Fb$?  \end{Exercise}  \begin{Exercise}\label{MaxiSum}  Compute the following operations in $\Fb$:  \begin{itemize}  \item $1+1+1+1+1+0+1+1+0+1=?$  \item $1+1+1+0+1+1+1+0+1+1+1=?$  \item $\underbrace{1+1+...+1}_{1235 \textrm{ times}}=?$  \item $\underbrace{1+1+...+1}_{15754 \textrm{ times}}=?$  \item $1245 \cdot 1=?$  \item $2482 \cdot 1=?$  \item $1234 \cdot 0=?$  \end{itemize}  What can you conclude?  \end{Exercise}  Bits can also be seen as a way to represent the logical values TRUE/FALSE. The   usual notation is $0=\FALSE$ and $1=\TRUE$. Stating this notation,   %Indeed, we have $1 \cdot 1= 1$ and $0 \cdot 1 = 1 \cdot 0 =0$; this means that   %each element different from $0$ (i.e. $1$) has an inverse.   % In formulas $a \neq 0 \Rightarrow \exists \frac{1}{a}$.  % We remark that $1 +1= 0 $ in $\Fb$, so in this field $-1 = 1$.  %By the point of view of logic, considering $0=\FALSE$ and $1=\TRUE$,  we have the well known truth tables:  \begin{table}[!htb]  \centering  \begin{tabular}{c|c|c|c|c}  a & b & a OR b & a AND b & a XOR b\\  \hline  0 & 0 & 0 & 0 & 0\\  0 & 1 & 1 & 0 & 1\\  1 & 0 & 1 & 0 & 1\\  1 & 1 & 1 & 1 & 0  \end{tabular}  \caption{Logic}\label{Logic}  \end{table}  \begin{Exercise}\label{XorIsNice}  What can we observe by comparing tables \ref{SumProd} and \ref{Logic}?  \end{Exercise}  \begin{Exercise}\label{Not}  Can you represent $\NOT$ by some expression?  \begin{table}[!htb]  \centering  \begin{tabular}{c|c}  a & NOT a\\  \hline  0 & 1\\  1 & 0  \end{tabular}  \end{table}  Hint: Try to complete the following expression  \[  \NOT\; a = a \_ \_   \]  where $a$ is in $\Fb=\{0,1\}$ and using $0,1,+,\cdot$.  \end{Exercise}