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.

in Digital Logic by
edited by | 1.3k views
Is a figure here?
There is no figure on the test paper I have. I have searched a few test papers and there is no figure on them.
Okay.. Thanks :)

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.  

2 Answers

+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(F(X,Y),X'Y)=XY'+XY'$  Therefore, the above function is implemented with $4$ implication gates.
edited by
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'$

+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. 

best solution bro
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,437 answers
95,257 users