Vani question paper

Question

If f=x'yz+xy'+yz' and g=x'yz+xy+x'yz' which of them are functionally complete

Answer 1

Given  f  =  x'yz + xy' + yz'

          g  =  x'yz + xy + x'yz'

Let us simplify g :

          g  =  x'yz + xy + x'yz'

              =  x'y(z + z') + xy

              =  x'y + xy

              =  y(x + x')

              =  y

So the function only reduces to y..Hence it is not functionally complete..

Now  f    =  x'yz + xy' + yz'

             =  y(x'z + z') + xy'

             =  y(x' + z')  + xy'

             =  x'y + xy'  + yz'

Keeping  z = 1 and y = 1, we have :

       f    =   x' (1)  + x (0) + 1 (0)

            =   x'

Hence NOT gate can be realised by the above substitution..

Likewise , keeping z  =  0 , we have :

      f    =   x'y + xy' + y

          =    x'y  + y + x

          =    y + x  

Hence OR gate is realised using the above substitution..

Now we know that  { OR , NOT } is functionally complete ..And as we are able to reduce the given function to this set of known functions which is a functionally complete set of functions , hence f is functionally complete as well..

Hence f is functionally complete but g is not functionally complete..

EDIT : But one thing to mention here is in hardware level , for implementation of OR and NOT as shown above , we have taken help of 0 and 1 to achieve the functionality of OR and NOT functions..

Hence f is not fully functionally complete..

Comments

Is it like substituting any value so that expression of 'not ' , 'and ', 'or'  all can be obtained into it ??

---

@Ashwani Kumar 2 , Implication with NOT is fully functionally complete : without NOT it isnt..

As x ==> y means x' + y , so with the help of NOT we have :

x' ==> y which is nothing but x + y which is realisation of OR function.

And we know {OR , NOT} is functionally complete..

Hence  { ==> , NOT } is fully functionally complete but not { ==> }..

In the given solution to the mentioned link by you also , they have taken help of external "0" ..So assuming external "0" is present already , it is functionally complete..But this may not be the case always..Hence it is partially functionally complete.

But as the question is saying to prove that it is functionally complete ; it means it considers usage of external inputs.

---

Thanks Habib :)