1

For $x,y\in\{0,1\}^n$,

let $x\oplus y$ be the element of $\{0,1\}^n$ obtained by the component-wise exclusive-or of $x$ and $y$. A Boolean function $F : \{0,1\}^n\to\{0,1\}$ is said to be linear if $F(x\oplus y) = F(x)\oplus F(y),\forall x\ and\ y$. Then what is the number of linear functions from $\{0,1\}^n$ to $\{0,1\}$ ?

P.S : It's easy to figure out that the total number of binary function is $2^{2^n}$

dibyendu
  • 539

2 Answers2

4

HINT: Suppose that $F$ is linear, and for $k=1,\ldots,n$ let $e^k=\langle e_1^k,\ldots,e_n^k\rangle$, where $$e_j^k=\begin{cases}1,&\text{if }j=k\\0,&\text{otherwise}\;.\end{cases}$$

Show that $F$ is completely determined by its values on $E=\{e^1,\ldots,e^n\}$, meaning that if you know $F(e^k)$ for each $k\in\{1,\ldots,n\}$, then you know $F(x)$ for all $x\in\{0,1\}^n$. How many ways are there to determine the values of $F$ on $E$?

Brian M. Scott
  • 616,228
  • So, the answer will be $2^n$ – dibyendu Sep 17 '13 at 08:56
  • @dibyendu: It will indeed. – Brian M. Scott Sep 17 '13 at 08:57
  • Suppose linearity was defined by logical AND i.e $F(x\land y) = F(x) \land F(y)$, then the set of vectors that would completely determine $F$ is $E={e^1,\ldots,e^n} \cup \langle 1,\ldots n\ times\ldots,1\rangle $ where $e^k=\langle e_1^k,\ldots,e_n^k\rangle\ \ \forall k\in{1,\ldots,n}$ such that $$e_j^k=\begin{cases}0,&\text{if }j=k\1,&\text{otherwise};.\end{cases}$$

    So, $$e^1 = \langle0,1,\ldots n-1\ times\ldots,1\rangle$$ $$e^2 = \langle1,0,1\ldots n-2\ times\ldots,1\rangle$$ etc.

    Now the number of linear functions would be $2\times2^n = 2^{n+1}$. Is it ?

     – dibyendu Sep 18 '13 at 08:32
  • 2
    @dibyendu: Yes, that works fine. – Brian M. Scott Sep 18 '13 at 08:43
3

Hint: Show, that the map $f \mapsto \bigl(f(e_1), \ldots, f(e_n)\bigr)$ mapping linear functions $\{0,1\}^n \to \{0,1\}$ to their values on $e_1 = (1, 0,\ldots, 0)$, $\ldots$, $e_n = (0,\ldots, 0, 1)$ is a bijection.

martini
  • 84,101