edited by
2,190 views
17 votes
17 votes

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.

  1. $2^{2n}$
  2. $2^{n+1}$
  3. $2^{n-1}+1$
  4. $n!$
  5. $2^{n}$
edited by

3 Answers

Best answer
14 votes
14 votes

Take an example

Suppose the function $f$ is from $\{0,1\}^3$  to $\{0,1\}$

Now, here we have to find the number of functions possible from $\{0,1\}^3$ to $\{0,1\}$ such that

$f (x \oplus y) = f(x) \oplus f(y)$

Now, observe that if we maintain the linearity of XOR then the values $f(000),f(101),f(110),f(011)$ and $f(111)$ are dependent on the values $f(100) , f(010)$ and $f(001)$ (Reason given below)

So, if we fix the values of $f(100),f(010)$ and $f(001)$ then we will get the whole function.

Now, each of $f(100),f(010)$ and $f(001)$ has $2$ options, either $0$ or $1.$

So, the number of linear functions possible is $2^3 = 8.$

Now, we can see how the values $f(000),f(101),f(110),f(011)$ and $f(111)$ are dependent on the values $f(100) , f(010)$ and $f(001).$

Let $f(100) = 0 , f(010) = 0 , f(001) = 0$

Now,

  • $f(000) = f(100 \oplus 100) = f(100) \oplus f(100) = 0 \oplus 0 = 0$
  • $f(101) = f(100 \oplus 001) = f(100) \oplus f(001) = 0 \oplus 0 = 0$
  • $f(110) = f(100 \oplus 010) = f(100) \oplus f(010) = 0 \oplus 0 = 0$
  • $f(011) = f(010 \oplus 001) = f(010) \oplus f(001) = 0 \oplus 0 = 0$
  • $f(111) = f(100 \oplus 011) = f(100) \oplus f(011) = f(100) \oplus f(010) \oplus f(001) = 0$


So, we have seen how the values $f(000),f(101),f(110),f(011)$ and $f(111)$ are dependent on the values $f(100) , f(010)$ and $f(001)$

Now, suppose the function is from $\{0,1\}^n$ to $\{0,1\}$

In this case if we fix the values of $f(100\ldots 0),f(010\ldots 0),f(001\ldots 0),\ldots ,f(000\ldots 1)$ then we will get the whole function since rest of the values are dependent on the above $n$ values.

Now, each of the $n$ values $f(100\ldots 0),f(010\ldots 0),f(001\ldots 0),\ldots ,f(000\ldots 1)$ has $2$ options - either $0$ or $1.$

So, the number of linear functions possible is $2^n$.

Correct Answer: $E$

7 votes
7 votes

Here, $x,y$ are $n$ length binary strings.

If $n=2$, we have $x,y \in \{00, 01, 10, 11\}$

For a generic function mapping to $\{0,1\}$ we have $2$ options for each of the four $2$ bit strings thus giving $2^4$ functions which is $2^{2^n}.$ But here, our function must be linear. Lets see all the possibilites:

$00 \oplus 00 = 00$
$00 \oplus 01 = 01$
$00 \oplus 10 = 10$
$00 \oplus 11 = 11$
$01 \oplus 01 = 00$
$01 \oplus 10 = 11$
$01 \oplus 11 = 10$
$10 \oplus 10 = 00$
$10 \oplus 11 = 01$
$11 \oplus 11 = 00$

Since, $\oplus$ is commutative not considering the remaining $6$ combinations.

If $F$ maps every thing to $0,$ it does preserve linearity. This way we get $1$ linear function.

Now, $F(00)$ must map to $0,$ because it equals $F(01) \oplus F(01)$ which is $0$ irrespective of the value of $F(01).$ Now, lets assume $F(01) = 1.$ Since $F(01) \oplus F(10) = F(11),$ either $F(10)$ or $F(11)$ but not both must be $1.$ Both of these are valid. Now, if we take $F(01) = 0,$ both $F(10)$ and $F(11)$ must be $1$ (both can also be $0$ but this we considered as our first case). Thus, we get $4$ linear functions in total

  1. $\{F(00) = 0,F(01) = 0, F(10) = 0, F(11) = 0\}$
  2. $\{F(00) = 0,F(01) = 1, F(10) = 1, F(11) = 0\}$
  3. $\{F(00) = 0,F(01) = 1, F(10) = 0, F(11) = 1\}$
  4. $\{F(00) = 0,F(01) = 0, F(10) = 1, F(11) = 1\}$

So, $2^n$ should be the answer. General case discussion can be seen here: https://math.stackexchange.com/questions/496185/number-of-linear-binary-function-in-a-vector-space

https://math.stackexchange.com/questions/2244907/the-number-of-linear-functions-from-left-0-1-right-n-to-left-0-1-ri?noredirect=1&lq=1

edited by
2 votes
2 votes

let us consider $x, y\in \left\{0, 1\right\}$

Now let we define F as $F:\left\{0, 1\right\}\rightarrow\left\{0, 1\right\}$

Al the possible combinations of $F(x ⊕ y)= F(x) ⊕ F(y)$ is what we have to find out

possible combinations of $F(x ⊕ y)$ are 

  • $F(0 ⊕ 0)$
  • $F(1 ⊕ 1)$
  • $F(0 ⊕ 1)$

Now, for the first one we consider $F(0 ⊕ 0)=F(0) ⊕ F(0) \implies F(0)=F(0) ⊕ F(0)$ Since on the RHS both the terms are same so the XOR operation will give 0. so, $F(0)=0$ always.

similarly , for the second one $F(1) ⊕ F(1)$ will be 0 and $F(1)$ can be 0 or 1.so, it has 2 possibilities.

for the third one as value of F(1) can be 0 or 1 so the value of $F(1) ⊕ F(0)=F(1⊕0)=F(1)$  can be 0 or 1. so, 2 possibilities.

So, total combinations possible is = $2 \times 2=4$.

so, answer will be (e).

Answer:

Related questions

16 votes
16 votes
4 answers
2
40 votes
40 votes
2 answers
3
makhdoom ghaya asked Oct 26, 2015
3,087 views
How many pairs of sets $(A, B)$ are there that satisfy the condition $A, B \subseteq \left\{1, 2,...,5\right\}, A \cap B = \{\}?$$125$$127$$130$$243$$257$