GATE CSE 1993 | Question: 9

Question

Assume that only half adders are available in your laboratory. Show that any binary function can be implemented using half adders only.

Comments

But it is partially functionally complete.

---

Yes it should be partially complete , because input 1 is not given to you seperately , to implement the negation .

Answer 1

Half Adder gives two outputs:

• $S = A\oplus B$
• $C = A . B$

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

• AND operation $C = A.B$
• Not operation $= S(\text{with}\; A\; \text{and}\; 1) = A\oplus 1 = A'.1+A.1' = A'$
• OR operation $= ((A\oplus 1).(B\oplus 1))\oplus 1= (A'.B')' = A+B$

Comments

S + C cannot be done like this rt? As it needs an OR gate

---

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

---

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 S₁ and the Carry C₁ of the 1st half adder.

So S₂=S₁⊕ C₁=(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

---

@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.

---

so it means half adder is functionally complete. ??

---

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

---

@Arjun Sir Is deriving AND and NOT not enough to prove that any binary function can be implemented using half adder in this case ?

---

So here basically we have to prove that half adder is functionally complete !! as in half adder two gates are present (for sum = XOR And for carry =AND ) . 

and to prove functionally complete , either (AND ,NOT) OR (OR,NOT)   must be generated.

is this logic right?

 

Answer 2

The other answer is correct but the logic is that we need to prove functional completeness ( partial functional completeness is not a thing ). The most simple way to do that is making an AND and a NOT gate ( or an OR and a NOT gate ). Half adders have XOR and AND ( sum is the XOR of the two inputs and the carry is the AND of the two digits ). XOR and AND by themselves are not functionally complete ( they are 0 – preserving ).