The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 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 Veteran (52.1k points)
edited by | 914 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

+12 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.
by Loyal (7.4k points)
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
+7 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. 

by Active (5.1k points)
best solution bro

Related questions

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
49,807 questions
54,729 answers
79,911 users