Exercise 1.
\((1+1)+0=(0)+0=0\);
\((1+1)+1=(0)+1=1\);
\((1+1)\cdot 1=(0)\cdot 1=0\);
\((0+0)+1+(1+0)\cdot 1=(0)+1+[(1)\cdot 1]=0+1+1=0\).
Exercise 2.
\(1+1+1+0+0+0+0+1=(1+1)+(1+0)+(0+0)+(0+1)=0+1+0+1=0\)
\(1+1+1+1+0+0+0+0=1+1+1+0+0+0+0+1=0\); the first equality comes from the commutativity of the sum in \(\mathbb{F}_{2}\). Thanks to this property one sees that the expression in b. is exactly the same as in a., up to the ordering of the summands, so the result is the same.
Exercise 3.
\((1+0)\cdot 1=1\) so the opposite is \(1\);
\((0+0)\cdot 0=0\) so the opposite is \(0\);
\(1+1+1+1+0+1+(1·1)=0\) so the opposite is \(0\).
Exercise 4.
\(1\cdot(1+0)=(1\cdot 1)+(1\cdot 0)=1+0=1\)
\(1\cdot(0+1)+0\cdot(1+1)=(1\cdot 0)+(1\cdot 1)+(0\cdot 1)+(0\cdot 1)=0+1+0+0=1\)
Exercise 5.
First of all, we notice that XOR behaves as the sum of bits, whereas AND behaves as multiplication.
We cannot say the same for OR. Moreover:
\(\textrm{NOT }((\textrm{NOT }a)\textrm{ AND }(\textrm{NOT }b))=a\textrm{ OR }b\)
\(\textrm{NOT }((\textrm{NOT }a)\textrm{ OR }(\textrm{NOT }b))=a\textrm{ AND }b\)
\((\textrm{NOT }a)\textrm{ XOR }(\textrm{NOT }b)\) and \(a\textrm{ XOR }b\) have the same truth table.
Exercise 6.
\(\textrm{NOT }a=a+1\)
Exercise 7.
\(a\textrm{ OR }b=(a+1)(b+1)+1\)
Exercise 8.
Yes, \(\mathbb{Q}\) is an abelian group w.r.t. the sum. Indeed the sum is associative and commutative, \(0\in\mathbb{Q}\) is the neutral element and if \(a\in\mathbb{Q}\), its opposite is \(-a\); for example, for \(a=\frac{1}{2}\), its opposite is \(-\frac{1}{2}\).
Exercise 9.
Well, not exactly; \(\mathbb{Q}^{*}=\mathbb{Q}\setminus\{0\}\) is an abelian group w.r.t. the multiplication. Indeed the multiplication is associative and commutative, \(1\in\mathbb{Q}\) is the neutral element and if \(a\in\mathbb{Q}^{*}\), its opposite is \(\frac{1}{a}\); for example, for \(a=\frac{1}{2}\), its opposite is \(\frac{1}{\frac{1}{2}}=2\). The element \(0\in\mathbb{Q}\) is not invertible.
Actually, \(\mathbb{Q}\) is a field.
Exercise 10.
\((x^{3}+x^{2}+x+1)+(x^{4}+x^{2}+x)=x^{4}+x^{3}+1\);
\((x^{10}+x^{7}+x+1)+(x^{5}+x)+(x^{7}+1)=x^{10}+x^{5}\);
\(x+(x^{8}+x^{5}+1)+(x^{6}+x^{2}+x)=(x^{8}+x^{6}+x^{5}+x^{2}+1)\)
Exercise 11
\((x^{4}+x^{3}+1)(x^{3}+x^{2}+1)=x^{7}+x^{5}+x^{4}+x^{2}+1\), so its degree is \(7\);
\((x^{3}+x^{2}+x)+(x^{4}+x^{3})=x^{4}+x^{2}+x\) so its degree is \(4\);
\((x^{2}+x+1)+(x^{2}+x)=1\) so it has degree \(0\).
We can desume that \(\deg(fg)=\deg(f)+\deg(g)\)
and \(\deg(f+g)\leq\max(\deg(f),\deg(g))\).
Exercise 12
Consider for example \(f=a_{0}+a_{1}x+a_{2}x^{2}\).
We have \(f^{2}=(a_{0}+a_{1}x+a_{2}x^{2})=(a_{0}+a_{1}x+a_{2}x^{2})(a_{0}+a_{1}x+a_{2}x^{2})=a_{0}^{2}+a_{0}a_{1}x+a_{0}a_{2}x^{2}+a_{0}a_{1}x+a_{1}^{2}x^{2}+a_{1}a_{2}x^{3}+a_{0}a_{2}x^{2}+a_{1}a_{2}x^{3}+a_{2}^{2}x^{4}=a_{0}^{2}+a_{1}^{2}x^{2}+a_{2}^{2}x^{4}\)
Exercise 13
\((x^{2}+x)^{2}=x^{4}+x^{2}\)
\((x^{3}+x+1)^{2}=x^{6}+x^{2}+1\)
\((x+1)^{4}=x^{4}+1\)
\((x^{2}+x+1)^{3}=(x^{2}+x+1)^{2}*(x^{2}+x+1)=(x^{4}+x^{2}+1)(x^{2}+x+1)=x^{6}+x^{5}+x^{4}+x^{4}+x^{3}+x^{2}+x^{2}+x+1=x^{6}+x^{5}+x^{3}+x+1\)
Observe that \((x+1)^{4}=x^{4}+1\), so raising a polynomial to an exponent \(b\) which is a power of two means raising its monomials to the power \(b\) and sum the results. Notice that this is not true for an even exponent that is not power of \(2\). For example
\begin{equation} (x+1)^{6}=x^{6}+x^{4}+x^{2}+1\neq x^{6}+1\nonumber \\ \end{equation}Here there are some more steps to do, indeed, since \(6=2\cdot 3\), we can write \((x+1)^{6}=((x+1)^{3})^{2}\), then we compute \((x+1)^{3}=x^{3}+x^{2}+x+1\) and then we have to raise it to the power two, so here we can raise its monomial to the power two and sum them
\begin{equation} (x+1)^{6}=((x+1)^{3})^{2}=(x^{3}+x^{2}+x+1)^{2}=x^{6}+x^{4}+x^{2}+1.\nonumber \\ \end{equation}Exercise 14
Let us recall that in \(\mathbb{F}_{2}[x]\) we have
\((x+1)^{0}=1\rightarrow\mathbf{1}\)
\((x+1)^{1}=x+1\rightarrow\mathbf{1\;1}\)
\((x+1)^{2}=x^{2}+1\rightarrow\mathbf{1\;0\;1}\)
\((x+1)^{3}=x^{3}+x^{2}+x+1\rightarrow\mathbf{1\;1\;1\;1}\)
\((x+1)^{4}=x^{4}+1\rightarrow\mathbf{1\;0\;0\;0\;1}\)
and so on.
So, we have the triangle:
Now, in \(\mathbb{Z}[x]\)
\((x+1)^{0}=1\rightarrow\mathbf{1}\)
\((x+1)^{1}=x+1\rightarrow\mathbf{1\;1}\)
\((x+1)^{2}=x^{2}+2x+1\rightarrow\mathbf{1\;0\;1}\)
\((x+1)^{3}=x^{3}+3x^{2}+3x+1\rightarrow\mathbf{1\;3\;3\;1}\)
\((x+1)^{4}=x^{4}+4x^{3}+6x^{2}+4x+1\rightarrow\mathbf{1\;4\;6\;4\;1}\)
and so on.
We have then the Pascal’s (Tartaglia’s!) Triangle:
We can notice that if in the Pascal’s Triangle we have an even number, the corresponding position in the Triangle for \(\mathbb{F}_{2}\) we have \(0\), whereas if in the Pascal’s Triangle we have an odd number, the corresponding position in the Triangle for \(\mathbb{F}_{2}\) we have \(1\).
See the chapter \ref{Friends} for further explanations on this behaviour.
Exercise 15
\(x^{4}+x^{3}+x\rightarrow 0\)
\(x^{3}+x+1\rightarrow\emptyset\)
\(x^{6}+x^{5}+1\rightarrow\emptyset\)
\(x^{4}+x^{3}+x^{2}+x\rightarrow 0,1\)
Exercise 16
Take the polynomials \(f=x+1\) and \(g=x^{2}+1\); it holds \(f(0)=g(0)=1\), \(f(1)=g(1)=0\)
\(p(x)=0\), \(q(x)=1\), \(r(x)=x\), \(s(x)=x+1\)
there are \(4\) functions from \(\mathbb{F}_{2}\) to \(\mathbb{F}_{2}\).
Exercise 17
\(p_{1}=x^{5}+x^{4}+x+1=(x+1)^{5}\);
\(p_{2}=x^{4}+x^{2}+1=(x^{2}+x+1)^{2}\).
Exercise 18
The only irreducible polynomial of \(\mathbb{F}_{2}[x]\) with degree \(2\) is \(x^{2}+x+1\); now since it does not divide \(f=x^{4}+x+1\) and \(f\) has no roots in \(\mathbb{F}_{2}\), we can desume that it is irreducible.
Exercise 19
Divisioni: solo il risultato o mettiamo proprio tutto il disegnino??
Exercise 20
\((0,0,0,0)+(0,0,0,0)=(0,0,0,0)\)
\((0,1,0,1)+(0,1,0,1)=(0,0,0,0)\)
\((1,1,1,1)+(1,1,1,1)=(0,0,0,0)\)
\((1,1,0,0)+(1,1,0,0)=(0,0,0,0)\)
The opposite of a vector of bits is itself.
Exercise 21
\(5\cdot(1,1,0)=(5\cdot 1,5\cdot 1,5\cdot 0)=(1,1,0)\)
\(6\cdot(0,1,0)=(6\cdot 0,6\cdot 1,6\cdot 0)=(0,0,0)\)
Multiplication for an odd number is the same as multiplication by \(1\), so it keeps the given vector unchanged; multiplication for an even number is the same as multiplication by \(0\), so it annihilates the given vector.
Exercise 22
The two equations give two representations of the same operation, in the sense that we can identify a polynomial \(f\in\mathbb{F}_{2}[x]\) with the list of its coefficients, decreasingly ordered by degree, for example
Then the sum of polynomials can be performed as the sum of vectors.
Exercise 23
Exercise
\(1^{2}\equiv 1\)
\(2^{2}\equiv 4\), \(2^{3}\equiv 1\)
\(4^{2}\equiv 2\), \(4^{3}\equiv 1\)
\(6^{2}\equiv 1\).