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

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