1

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$.

Especially Lime
  • 40,828
Jonathan
  • 81
  • The domain of $f$ and $g$ is $\mathbb{R}^n$ or ${0,1}^n$ ? – Zubzub Apr 26 '17 at 09:49
  • @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? – Bram28 Apr 26 '17 at 13:05

1 Answers1

1

$$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$

Bram28
  • 100,612
  • 6
  • 70
  • 118