retagged by
2,760 views
17 votes
17 votes
Assume that only half adders are available in your laboratory. Show that any binary function can be implemented using half adders only.
retagged by

2 Answers

Best answer
31 votes
31 votes

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$
edited by
1 votes
1 votes
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 ).

Related questions

21 votes
21 votes
2 answers
1
Kathleen asked Sep 29, 2014
8,970 views
Identify the logic function performed by the circuit shown in figure. exclusive ORexclusive NORNANDNORNone of the above
25 votes
25 votes
4 answers
2
1 votes
1 votes
0 answers
3
admin asked Dec 15, 2022
230 views
Given a truth table of the full adder for three inputs. Draw a full adder circuit with a decoder and two $\text{OR}$ gates.$$\begin{array}{|c|c|c|c|c|}\hline \mathrm{X} &...
1 votes
1 votes
3 answers
4