The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 votes
  1. 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.

  2. Show that the implication gate is functionally complete.

asked in Digital Logic by Veteran (59.5k points)
edited by | 643 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

+10 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.
answered 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
+5 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. 

answered by Active (4.3k points)

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

38,079 questions
45,571 answers
49,040 users