+11 votes
754 views
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
edited | 754 views
0
Is a figure here?
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.
0
Okay.. Thanks :)
0

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?

0

Notice @krish__ ji's answer,

implication function is only partially complete

Good point.

## 2 Answers

+11 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.
answered by Loyal (7.5k points)
edited
+14
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
+6 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.8k points)
+1
best solution bro

+13 votes
2 answers
1
+5 votes
2 answers
2
+2 votes
2 answers
3
+14 votes
3 answers
4
+3 votes
2 answers
5
+17 votes
2 answers
6
+23 votes
3 answers
7
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}