deletions | additions
diff --git a/bits1.tex b/bits1.tex
index 1623d73..e0dd757 100644
--- a/bits1.tex
+++ b/bits1.tex
...
most of Computer Science applications.
\\
They are represented with the constants $0 $ and $1$ (the two events with the
same probability).
In Mathematics, the The set of
bits the bits, in Mathematics is usually denoted by
%We have the Field of Bits $\Fb$. When we work in Computer Science we often
%consider
...
1 & 0 & 1 & 0\\
1 & 1 & 0 & 1
\end{tabular}
\caption{Sum and
product of bits}\label{SumProd} product}\label{SumProd}
\end{table}
The first and second columns represent the values of the input variables $a$ and $b$,
whereas the third and the fourth
ones denote respectively the results of the sum and product of $a$ and
$b$.\\ $b$. Look at third row. We
notice 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 (from now on we represent the set of real numbers with $\RR$). \\
Look for example at the third row of the table above.
We can observe that, summing the bit $1$ with the bit $1$, one gets $0$, i.e.
$$1+1=0 \textrm{ in }\Fb.$$ numbers.
% indexed
% by a bit ($0$ or $1$) except that the first that contains the symbol
...
% performing operations with bits is not the same as doing so with ``usual''
% (real) numbers.
Even if its operations $+$ and $\cdot$ are similar but different wrt the ones on real numbers, Anyway, $\Fb$ has very good properties with respect to
these operations. 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
\emph{opposite} opposite for the sum,
``$+$'', ``+'', and every element of $\Fb$, that is different from $0$, has an
\emph{inverse}, inverse, exactly as
it happens with the field of real numbers.
\\ For example in the field
$\RR$ of real numbers
\[
5+(-5)=0 \mbox{ and } 5\cdot \frac{1}{5}=1.
\]
In The notation for the set of
bits, bits (that - from now on - we
have: 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}
\medskip
The notation for the set of bits (that - from now on - we will call the \emph{field of bits}), reflects this fact.\\
Indeed, $\mathbb{F}$ stands for ``field'' and the subscript $2$ stands for the \emph{size} of the set itself, i.e. the number of its elements.
%
...
% 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
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$.\\
We can conclude that $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,
namely the concept of
\emph{characteristic}.\\ \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
(in the field $\Fb$ the (the characteristic is
$p=2$). \\ $p=2$ in the field $\Fb$). If there are no number with this
property, 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}
...
\item $2482 \cdot 1=?$
\item $1234 \cdot 0=?$
\end{itemize}
What can you conclude?
What does the characteristic implies?
\end{Exercise}
Bits can also be seen as a way to represent the logical values TRUE/FALSE. The
usual notation
in Computer Science 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$,
Once fixed this notation, we have the well known truth tables:
\begin{table}[!htb]
\centering
\begin{tabular}{c|c|c|c|c}
...
\caption{Logic}\label{Logic}
\end{table}
\begin{Exercise}\label{XorIsNice}
What can we observe by comparing tables \ref{SumProd} and \ref{Logic}?
Are there any similarities?
\end{Exercise}
\begin{Exercise}\label{Not}
Can you represent $\NOT$
using by some
expression on bits? expression?
\begin{table}[!htb]
\centering
\begin{tabular}{c|c}