4

I know it is a duplicate of this question.But still, i am posting this because I am completely stuck.I think i have not understand the question itself.

I am posting my attempt.Please guide me to move further.

Question

For $x, y\in \left\{0, 1\right\}^{n}$, let $x ⊕ y$ be the element of $\left\{0, 1\right\}^{n}$ obtained by the component-wise exclusive-or of $x$ and $y$. A Boolean function $F:\left\{0, 1\right\}^{n}\rightarrow\left\{0, 1\right\}$ is said to be linear if $F(x ⊕ y)= F(x) ⊕ F(y)$, for all $x$ and $y$. The number of linear functions from $\left\{0, 1\right\}^{n}$ to $\left\{0, 1\right\}$ is.

Attempt

let the value of $n$=4

Now we have the size of domain as $2^{4}$ which are $\left\{0000,0001,0010,0011,0100\,\,\cdot\cdot\cdot\cdot 1111\right\}$

Total number of binary function possible $F:\left\{0, 1\right\}^{n}\rightarrow\left\{0, 1\right\}$ =$2^{2^{4}}=2^{16}$

We have to find actually the size of domain.

Now among $16$ possible combination of $\left \{0, 1\right\}^{4}$,

Let $x=0010$ and $y=1010$

Now $$x ⊕ y=1000$$

Now$F(x ⊕ y)$=$F(0010)$=$F(x)⊕ F(y)$=????

Completely stuck !!,no clue what to do !Even the accepted answer is not clear to me !

Please help me out using this example!

laura
  • 2,530

1 Answers1

2

Here is a hint. (In fact, it's what the accepted answer is getting at.) Every element of $\{0,1\}^n$ is uniquely determined by a sum of elements with exactly one $1$, and it uniquely determines which such elements are needed.

For example, in the $n=4$ case, $$y=1010=1000\oplus0010.$$ In order for your function $F$ to be linear, you then require that $$F(y)=F(1000)\oplus F(0010).$$ In how many ways can you assign function values to the elements with only one $1$? Once those are assigned, all the other function values will follow by linearity. For example, if we make $F(1000)=1$ and $F(0010)=1,$ then $F(y)=1\oplus1=0,$ and indeed, $$F(x\oplus y)=F(1000)=1=1\oplus0=F(x)\oplus F(y),$$ as desired.

Cameron Buie
  • 102,994