Prove a function is functionally complete/incomplete

272 Views Asked by At

I am given the following function H(n):

Inputs: $A[2^n-1:0] , I[n-1:0]$

Outputs: $B[2^n-1:0]$

The function is defined as follows:

$B[i] = \begin{cases} A[i], & {if\ 0\le i \le [I]} \\ NOT(A[i]), & {else} \end{cases}$

$[I]$ is the 10 base value of I.

The question is whether given the function H(2) and constant values 0/1 is it possible to express all boolean functions.

I attempted to write a truth table for the function, which is basically turned out to be a gate similar to a NOT gate, with four inputs for A and two don't care inputs for I and 4 outputs for B. Every row outputs the opposite value of the input except for the first row. Something like this:

\begin{array}{rrrrrrr|rrrr} & A_3 & A_2 & A_1 & A_0 & I_1 & I_0 & B_3 & B_2 & B_1 & B_0 \\ \hline & 0 & 0 & 0 & 0 & x & x & 0 & 0 & 0 & 0 \\ & 0 & 0 & 0 & 1 & x & x & 1 & 1 & 1 & 0 \\ & 0 & 0 & 1 & 0 & x & x & 1 & 1 & 0 & 1 \\ & 0 & 0 & 1 & 1 & x & x & 1 & 1 & 0 & 0 \\ & ... & ... & ... & ... & ... & ... & ... & ... & ... & ... \end{array}

From here I don't know what to do. To prove that the function is functionally complete i tried to prove i can build a NOT and AND/OR gates with it. NOT gate is trivial, but i couldn't figure out how to express AND/OR with it. Couldn't also figure out how to prove the function is not functionally incomplete.

Please help, Thanks.