1
$\begingroup$

Let $f, g$ be two functions from $x_1, x_2 , ..., x_n$ to $\{0,1\}$. Prove that the function $h$, defined by $h = (f\text{ XOR }g)$, maintains the following attribute: $N(h) = N(f) + N(g) - 2*k$, when $N$ is defined to be a function which operates on a function and returns the number of variable placements on the function which result in $1$. For example, if $f = x + y$, than $N(f) = 3$, since there are $3$ options to get $1$.

$k$ is defined to be the number of variable placement, $z$, which result in $1$ for both $f$ and $g$, $f(z) = 1$ and $g(z) =1$.

$\endgroup$
  • $\begingroup$ The domain of $f$ and $g$ is $\mathbb{R}^n$ or $\{0,1\}^n$ ? $\endgroup$ – Zubzub Apr 26 '17 at 9:49
  • $\begingroup$ @Jonathan I am confused about various things in this question ... Since you tagged this as boolean algebra, I assume the variables $x_1,x_2,...$ all are either $0$ or $1$? Also, in your example of $f = x + y$, can I read that as $f = x_1 \lor x_2$? And shouldn't $N(f)=2$, rather than 3? $\endgroup$ – Bram28 Apr 26 '17 at 13:05
1
$\begingroup$

$$h(x_1,x_2,...,x_n) = f(x_1,x_2,...,x_n) \ XOR \ g(x_1,x_2,...,x_n) = 1$$ iff either

A. $f(x_1,x_2,...,x_n) = 1$ and $g(x_1,x_2,...,x_n) = 0$

or

B. $f(x_1,x_2,...,x_n) = 0$ and $g(x_1,x_2,...,x_n) = 1$

$f(x_1,x_2,...,x_n) = 1$ for $N(f)$ variable placements, and $g(x_1,x_2,...,x_n) = 1$ for $N(g)$ variable placements

Since there are $k$ variable placements where $f(x_1,x_2,...,x_n) = 1$ and $g(x_1,x_2,...,x_n) = 1$, there are $N(f) - k$ placements where $f(x_1,x_2,...,x_n) = 1$ and $g(x_1,x_2,...,x_n) = 0$. Similarly, there are $N(g)-k$ placements where $f(x_1,x_2,...,x_n) = 0$ and $g(x_1,x_2,...,x_n) = 1$. So, there are in total $N(f) - k + N(g) - k = N(f) + N(g) - 2k$ placements where $h(x_1,x_2,...,x_n) = 1$, i.e. $N(h) = N(f) + N(g) - 2k$

$\endgroup$
  • $\begingroup$ thanx, thought about the same solution afterwards $\endgroup$ – Jonathan Apr 27 '17 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.