Following reference of what functionally complete functions are from below :
http://cs.ucsb.edu/~victor/ta/cs40/posts-criterion.pdf
f (X, Y, Z) = X'YZ + XY' + Y'Z' and g (X, Y, Z) = X'YZ + X'YZ' + XY
Consider f(X,Y,Z) = X'YZ + XY' + Y'Z'
Above is K map of f where row denotes variable X(row 1-0 and row 2-1)
Column denotes YZ with respective column values as 00 01 11 and 10.Usual 3 variable K-map implementation we have considered.
As we can see Function f now cannot be simplified further.
If we make truth table of the above function
X |
Y |
Z |
f |
0 |
0 |
0 |
1 (F does not preserve 0) |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 (F does not preserve 1) |
Consider the output of function at inputs (X,Y,Z) (0,1,1) and (1,0,0) which is 1, so for functional value of f to be 1 sometimes number of 1's input is even sometimes odd hence f(X,Y,Z) is not linear.
Consider when input (X,Y,Z) changes from (0,0,0) to (0,0,1) change in variable of Z from 0 to 1 results in changing of functional values from 1 to 0. Hence f(X,Y,Z) is not monotone.
f(X,Y,Z) is not self-dual as f(X,Y,Z) ≠ ⌐f(⌐X,⌐Y,⌐Z).
f(X,Y,Z) dis-satisfies all five properties talked about above. Hence, f(X,Y,Z) is functionally complete.
Now consider g (X, Y, Z) = X'YZ + X'YZ' + XY
Consider above K map for g (X, Y, Z) = X'YZ + X'YZ' + XY where row denotes variable X and column denotes variables YZ.
We can see now that g(x,y,z) can be reduced to Y.
Hence g(X,Y,Z) = Y
consider below truth table for g(X,Y,Z)
Y |
F |
0 |
0 (G preserves 0) |
1 |
1 (G preserves 1) |
G is linear as change in input of Y from 0 to 1 can only make output change from 0 to 1.
G is monotone as when output is 1 number if 1's in output is odd.
G(X,Y,Z)=Y=⌐(⌐Y)
Hence G(X,Y,Z) is self dual.
Hence g(X,Y,Z) is not functionally complete.
Ans- (b)