1
\$\begingroup\$

Given a full adder with inputs $$A, B \text{ and } C_{in}$$ The formulas for the outputs are $$S = A \oplus B \oplus C_{in} \text{ , Where } \oplus \text{means XOR}$$ and $$C_{out} = AB + AC_{in} + BC_{in}$$

But when a Full Adder is created by combining two half-adders, the obtained equation for carry out is $$C_{out} = AB + (A \oplus B)C_{in}$$

The two expressions have equivalent Truth Tables, but the reason for their equality is not obvious.
Can someone please help me understand how it can easily be seen they're equal?

\$\endgroup\$
1
\$\begingroup\$

Boolean Algebra Approach
The equivalence of the two forms may be proven using boolean identities

Start off with the second expression $$C_{out} = A B + (A \oplus B)C_{in}$$ Using the expansion, $$A \oplus B = \bar AB + A \bar B \quad \text{ for XOR}$$ The right hand side becomes $$AB + \bar A B C_{in} + A \bar B C_{in} \tag{1}$$ Taking B common between the forst two terms, we get (Property of Boolean Algebra) $$B(A + \bar AC_{in})$$ Using the fact that addition distributes over multiplication (In boolean Algebra) $$A + BC = (A + B)(A + C) \tag{2}$$ Hence the term becomes $$B((A + \bar A)(A + C_{in})) = AB + BC_{in}$$ Plugging this back into (1) and reusing property (2) with $$B+ \bar B C_{in}$$ We get the alternate form $$AB + BC_{in} + C_{in} \tag {3}A$$ Intuitive Approach

The form (3) is true or 1, if any two among the 3 inputs are 1. This is the case since there will be a carry if and only if (iff) we add at least 2 1's.

The XOR form, on the other hand, suggests a different viewpoint. It treats the input carry differently than the other 2 inputs A and B. Effectively it is saying that the carry will be 1 iff both A and B are 1 (The AB term) or Exactly one among A and B is 1 and Cin is 1. Note that this is being unnecessarily specific and instead we could say part 2 of the condition is that Either A or B (or both) are 1 and Cin is also 1.

In boolean form this would be, $$AB + (A+B)C_{in}$$ Which is the same as (3)

The OP is advised to refer to the properties and Axioms of Boolean Algebra to prove similar equivalences.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.