The Gateway to Computer Science Excellence
+11 votes
698 views
Assume that only half adders are available in your laboratory. Show that any binary function can be implemented using half adders only.
in Digital Logic by | 698 views
+6
But it is partially functionally complete.

1 Answer

+21 votes
Best answer
Half Adder give two outputs:

$S = A⊕B$

$C = A.B$

We can Perform any operation using Half adder if we can implement basic gates using half adder

AND operation $C = AB$

Not operation $= S$ $($with $A$ and $1$$)$ $= A⊕1 = A'.1+A.1' = A'$

OR operation $= ((A⊕1).(B⊕1))⊕1= (A'.B')' = A+B$
by
edited by
+1
S + C cannot be done like this rt? As it needs an OR gate
+2
I mean if any of Led  get ON . we will get S+ C

I think  (A'.B')' will be Ok .

((A⊕1).(B⊕1))⊕1
+3

Since Not is not a binary function i think it is not required to derive it.

If external 1 is not supplied then also we can get A+B by using two half adders where the inputs of the 2nd half adder will be the Sum S1 and the Carry C1 of the 1st half adder.

So S2=S1⊕ C1=(A ⊕ B) ⊕ (AB) = A+B.

(A ⊕ B) ⊕ (AB)

=(AB'+A'B)(AB)' + (A'B'+AB)(AB)

= (AB'+A'B)(A'+B')+ (0+AB)

=(0+A'B+AB'+0)+AB

= A'B+AB'+AB

= B(A'+A)+AB'

=B+AB'

=A+B

+1

@MiNiPanda 

right but without deriving NOT we can't say it functionally complete...

we can derive OR and AND without using external 1 but for NOT we have to use external 1.

0
so it means half adder is functionally complete. ??
+1
It's partially functionally complete

Because u got AND and  OR gate without use of external 1.

But for drive NOT gate use external 1.

Hence it's partially functionally complete
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,345 questions
60,482 answers
201,809 comments
95,283 users