GATE CSE 1998 | Question: 5

Question

The implication gate, shown below has two inputs ($x \text{ and }y)$; the output is 1 except when $x =1 \text{ and } y=0\text{, realize }f=\bar{x}y+x\bar{y}$ using only four implication gates.

Show that the implication gate is functionally complete.

Comments

There is a image.An or gate with bubbled input x.

@arjun this isn't functionally complete.The function x'+xy preserves 1 for f(1,1) so we can say that it is not functionally complete right?

---

Notice @krish__ ji's answer,

implication function is only partially complete

Good point.  

---

$\color{red}{\text{Find Detailed Video Solution Below}}$ $\color{BLACK}{\text{  , With best way to check functional completeness:}}$

https://youtu.be/RH-H5fRiewQ

Answer 1

Implication gate is A->B which becomes A'+B

So, let $f(A,B)=A'+B$

$f(A,0)=A'$ (we get complement )

$f(f(A,0),B)=f(A',B)=A+B$ (we get OR gate)

Thus it is functionally complete.

Let $F(X,Y) =X'+Y$

$F(Y,X)=Y'+X$

$F(F(Y'+X),0)=X'Y$

$F(F(X,Y),X'Y)=XY'+XY'$  Therefore, the above function is implemented with $4$ implication gates.

Comments

implication is not fully functionally complete. Its partially functionally complete. Because it can derive NOT gate with the help of 0 as input.  I

---

i just want to clear that

if with the help of f(x,x) or f(y,y) we are able to get 0 or 1

and that 0 or 1 is helping us in getting the AND or OR

than we can say it fully functional complete ?

means in above questions we are not able to get 0

so it is partial but what if it would derive 0 than it would have full fun complete or not

---

@sushmita mam in the ques. it was given that it is Functionally complete, but it is Partially functionally complete...but both are diff. things..means we need help of (0 or 1) in Partially func. complete, but here they're treated same so should we consider both same or mention that its not fully functionally complete..??

---

@Riya Roy(Arayana), I think you wrongly did last step. As, question asks for X'Y +XY'.

$F((X+Y'),XY')=(X+Y')' + XY' = X'Y +XY'$

Answer 2

Assuming the special block as representing  $(\bar{x} + y)$ with the bottom inverted, the $XOR\,(\bar{x}y + x\bar{y})$ expression can be derived as shown above using 4 implication gates. 

But the implication function is only partially complete, i.e. can only represent a functionally complete set with an additional $0$ input. And that can be seen above where the gate in the middle represents a $NOT$ gate. 

Comments

best solution bro