Michela Ceria edited bits4.tex  about 6 years ago

Commit id: 7f9af9d1d7919df8fe2e761c65909cf0b9fdd68d

deletions | additions      

       

The following function, often used in cryptography, is called the \emph{majority function}:  $$f: (\Fb)^3 \rightarrow \Fb $$  $$(x,y,z)\mapsto xy+xz+yz.$$ $$(\overline{x},\overline{y},\overline{z})\mapsto \overline{x}\overline{y}+\overline{x}\overline{z}+\overline{y}\overline{z}.$$  This function returns value $1$ if and only if the majority among the input bits $\{x,y,z\}$ $\{\overline{x},\overline{y},\overline{z}\}$  holds value $1$. Obviously, it returns $0$ otherwise, i.e. if and only if the majority among the three input bits holds value $0$. \begin{Exercise}  Verify the above statement, by evaluating $f$ at all $3$-tuples of bits.  \end{Exercise}