The Gateway to Computer Science Excellence

+17 votes

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.

0

There is no figure on the test paper I have. I have searched a few test papers and there is no figure on them.

+15 votes

Best answer

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.

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.

+23

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

0

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

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

0

@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..??

0

@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'$

+16 votes

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.

52,315 questions

60,437 answers

201,777 comments

95,257 users