Functional Completeness Digital Logic


Consider the operations

f(x,y,z,w) = (xy)’ + (wz)’ + xz
g(x,y) = (xy)’

Which of the following is correct?

(i) Both are fully functionally complete
(ii) Only f is fully functionally complete
(iii)Only g is fully functionally complete
(iv) None


Emil post proved that a boolean function is fully functionally complete if it does not possess any of the following properties:

(i) 1-preserving : if all inputs are 1 then output is 1.

(ii) 0-preserving : if all inputs are 0 then output is 0.

(iii) Linearity : If odd number of 1’s are there in input then output is 1 and for even number of 1’s the output is 0, or vice-versa.
(iv) Monotonicity : Increasing the number of 1’s in the input will never change the output from 1 to 0.
(v) Self duality : if the function is self dual.

In the above question function ‘f’ follows 1st property hence it is not functionally complete.
function ‘g’ doesn’t follow any of the given properties, so it is fully functionally complete.

Hence option (iii) is the correct answer.