edited by
3,703 views
23 votes
23 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.

edited by

2 Answers

Best answer
18 votes
18 votes
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.
edited by
21 votes
21 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. 

Related questions

23 votes
23 votes
3 answers
1
Kathleen asked Sep 26, 2014
4,970 views
Design a synchronous counter to go through the following states:$$1, 4, 2, 3, 1, 4, 2, 3, 1, 4 \dots $$
10 votes
10 votes
3 answers
2
makhdoom ghaya asked Nov 29, 2016
1,586 views
Show that {NOR} is a functionally complete set of Boolean operations.
17 votes
17 votes
2 answers
3
Kathleen asked Sep 29, 2014
2,756 views
Assume that only half adders are available in your laboratory. Show that any binary function can be implemented using half adders only.
1 votes
1 votes
1 answer
4
go_editor asked Sep 20, 2018
426 views
Show that $\{1,A \bar{B}\}$ is functionality complete, i.e., any Boolean function with variables $A$ and $B$ can be expressed using these two primitives.