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 Answers 2

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, 2014 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 and acknowledge you have read our privacy policy.

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