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$
2
  • $\begingroup$ The domain of $f$ and $g$ is $\mathbb{R}^n$ or $\{0,1\}^n$ ? $\endgroup$
    – Zubzub
    Commented Apr 26, 2017 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
    Commented Apr 26, 2017 at 13:05

1 Answer 1

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$
1
  • $\begingroup$ thanx, thought about the same solution afterwards $\endgroup$
    – Jonathan
    Commented Apr 27, 2017 at 22:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .