I am given a truth table of a function as follows:
\begin{array}{rrrr|r} & x & y & z & f \\ \hline & 0 & 0 & 0 & 1 \\ & 0 & 0 & 1 & 1 \\ & 0 & 1 & 0 & 0 \\ & 0 & 1 & 1 & 0 \\ & 1 & 0 & 0 & 0 \\ & 1 & 0 & 1 & 0 \\ & 1 & 1 & 0 & 1 \\ & 1 & 1 & 1 & 1 & \end{array}
And is asked to prove it is functionally complete/incomplete. I guess the function is incomplete, because there are an even number of 1's and 0's at the output, and an AND function, for example, has an odd number.
The only property of a function I know is related to the above statement is linearity of a function. Then I can say the function is linear, thus not functionally complete. But the function is not linear, because for every 1 or 0 at the output, the number of 1's and 0's at the input is sometimes odd and sometimes even. Is there any other property of a function I can use for this function to prove it is functionally incomplete?
Thanks.
The function is not strictly linear, but it is affine -- in boolean-ring ($\mathbb F_2$) notation it is $$ f(x,y,z) = 1x+1y+0z+1 $$
It looks like you're confused by the fact that the function ignores its $z$ input so the coefficient is $0$.
Since affine functions are closed under composition, you can't make a non-affine Boolean function such as $x\mathbin{\rm AND}y$.