Number of different functions that satisfied the following requirements

50 Views Asked by At

I have two questions please. I know the answers because it was in last year exam (multiple choice). I would like to know the way to get the answers.

1)I need to find the Number of different functions with 4 variables $f(x,y,z,w)$ that satisfied the following requirements: $f(0,0,0,0)=0$ And $f(0,y,z,w) = f(1,y,z,w)$

The answer in the exam was:128

2)I need to find the Number of different functions with 6 variables $f(x1, x2, x3, x4, x5, x6)$ that satisfied the following requirements: $f(0,0,0,0,0,0)=0$ And $f(1,1,1,1,1,1)=0$ And $f(x1, x2, 0, x4, x5, x6) = f(x1, x2, 1, x4, x5, x6)$

The answer in the exam was: 2^30

1

There are 1 best solutions below

0
On
  1. As $f(0,y,z,w) = f(1,y,z,w)$, the value of $f$ only really depends on $y,z$ and $w$. So, equivalently we count all Boolean functions $g : \{0,1\}^3 \to\{0,1\}$ meeting the requirement $g(y,z,w) = 0$ for $y= z = w = 0$. Observe that we have $|\{0,1\}|^3 = 8$ possible combinations of values for $y,z,w$, i.e. $8$ elements in our domain. By the requirement, one of those is mapped to $0$. This leaves us with $7$ elements in the domain of $g$, for which we have two possible choices for the image, $0$ or $1$. So, the total number of such functions $g$ is $2^7 = 128$.
  2. This really is just the same as the first problem (so I will go less in depth). Without loss of generality, we can enumerate the Boolean functions $g: \{0,1\}^5 \to\{0,1\}$ that satisfy $g(0,0,0,0,0) = 0$ and $g(1,1,1,1,1) = 0$, as those functions $f$ don't really depend on $x_3$. Now, the number of elements in the domain is $|\{0,1\}|^5 = 2^5 = 32$. For two of those, the image is already given by the requirements, leaving us with $30$ elements, for whom we have two choices for their image. So, the total number of such functions $g$ is $2^{30}$.