128 views

f (X, Y, Z) = X'YZ + XY' + Y'Z'f (X, Y, Z) = X'YZ + XY' + Y'Z' and g (X, Y, Z) = X'YZ + X'YZ' + XYg (X, Y, Z) = X'YZ + X'YZ' + XY

Which one of the following is correct?

1. Both {f}{f} and  {g}{g} are functionally complete
2. Only  {f}{f}  is functionally complete
3. Only  {g}{g}  is functionally complete
4. Neither {f}{f}  nor  {g}{g} is functionally complete

I'm working on function f, here are my findings
1. f is not preserving 0  ;  2. f is not preserving 0
3. Checking Linearity
f=0 for X=1 Y=1 Z=0 (Number of ones is even for f=0)
f=1 for X=1 Y=0 Z=0 (Number of ones is odd for f=1)

Linearity satisfied, so the function is not Functional Complete, but for other values of X,Y,Z we can prove non-Linearity and proceed further.
PS: I already read @Arjun's solution but please go through my solution and let me know where im getting it wrong.

closed as a duplicate of: GATE2015-1_39
closed | 128 views
0
u mean u want to chk linearity only

and based on that u want ans right?
0
Yes using linearity, if a bool function is not linear, will check for monotonicity to check for functional complete
0

From Wikipedia:-

A Boolean function is linear if one of the following holds for the function's truth table:

1. In every row in which the truth value of the function is T, there are an odd number of Ts assigned to the arguments, and in every row in which the function is F there is an even number of Ts assigned to arguments. Specifically, f(F, F, ..., F) = F, and these functions correspond to linear maps over the Boolean vector space.
2. In every row in which the value of the function is T, there is an even number of Ts assigned to the arguments of the function; and in every row in which the truth value of the function is F, there are an odd number of Ts assigned to arguments. In this case, f(F, F, ..., F) = T.

Can, we conclude that all the function which have, odd no of argument are always, linear?