1
$\begingroup$

Suppose the vector boolean function be

$$\begin{align} f:F^n_2 \longrightarrow F_2^n \\ (x_1,\dots ,x_n) \longrightarrow (x_2,\dots x_n,g) \\ \\ g:F^n_2 \longrightarrow F_2 \\ (x_1,\dots ,x_n) \longrightarrow \{0,1\} \end{align}$$

What should be the condition on the Boolean function $g$ so that $f$ becomes bijective i.e. 1-1 and Onto?

$\endgroup$
2
$\begingroup$

The condition is that:

$$g(0, x_2, x_3, ..., x_n) \ne g(1, x_2, x_3, ..., x_n)$$

for all $x_2, x_3, ..., x_n$

This can easily be derived from the condition that implies bijectivity of $f$; that is, $f(x_1, x_2, ..., x_n) = f(y_1, y_2, ..., y_n)$ implies that $x_1 = y_1$, $x_2 = y_2$, ..., $x_n = y_n$

$\endgroup$
1
  • $\begingroup$ Ok, I voted for your answer, but please fix the latex typo in the third line. It is driving me crazy! :) $\endgroup$ – Guut Boy Nov 13 '14 at 15:00
0
$\begingroup$

For any fixed $x_2, \ldots, x_n$, $g$ must be a surjective function of $x_1$ (i.e. onto).

$\endgroup$

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.