15.2 Boolean Algebra and Logic Circuits

Main Content

1.1 The Half Adder

A half adder is a simple circuit that adds two single binary digits (bits) together. It takes two inputs, usually called A and B, and gives two outputs:

• Sum (S) — the result of adding A and B in the current column
• Carry (C or Cout) — the overflow bit that gets passed to the next (higher) column

Think of it like adding two digits by hand. If you add 1 + 1, you get 2. In binary, 2 is written as 10 — the 0 is the sum and the 1 is the carry.

The rules are simple:

• 0 + 0 = 0, with no carry
• 0 + 1 = 1, with no carry
• 1 + 0 = 1, with no carry
• 1 + 1 = 0, with a carry of 1

The truth table for a half adder looks like this:

If you look carefully at the Sum column, you will notice it matches the truth table for an XOR gate (output is 1 only when the inputs are different). The Carry column matches the truth table for an AND gate (output is 1 only when both inputs are 1).

So a half adder is built using:

• One XOR gate to produce the Sum
• One AND gate to produce the Carry

Boolean expressions for the half adder:

• Sum: S = A ⊕ B (A XOR B)
• Carry: C = A · B (A AND B)

The main limitation of a half adder is that it cannot accept a carry from a previous addition. When you add multi-bit numbers, each column (except the first) needs to include the carry from the column before it. A half adder cannot do this — that is where the full adder comes in.

1.2 The Full Adder

A full adder solves the problem of the half adder by accepting three inputs:

• A — one of the two bits being added
• B — the other bit being added
• Cin (Carry in) — the carry coming in from the previous column

It produces two outputs:

• Sum (S) — the result for the current column
• Cout (Carry out) — the carry passed on to the next column

To work out the outputs, add all three inputs together. Since each input is 0 or 1, the total can be 0, 1, 2, or 3. Write that total as a two-bit binary number: the right bit is the Sum, and the left bit is the Carry out.

For example: A = 1, B = 1, Cin = 1 → 1 + 1 + 1 = 3 = 11 in binary → Sum = 1, Cout = 1

The full truth table for a full adder:

A full adder can be built by combining two half adders and one OR gate:

1. The first half adder takes inputs A and B. Its Sum output (call it Sum1) and Carry output (call it Carry1) are passed on.
2. The second half adder takes Sum1 and Cin as inputs. Its Sum output is the final S, and its Carry output is called Carry2.
3. An OR gate takes Carry1 and Carry2 as inputs, and its output is the final Cout.

By chaining full adders together (connecting the Cout of one to the Cin of the next), you can add binary numbers with any number of bits. This is exactly how computers add numbers in their arithmetic logic unit (ALU).

Note on gates with more than two inputs: Logic gates can have more than two inputs. For example, a three-input AND gate gives an output of 1 only when all three inputs are 1. When producing a truth table for such circuits, you simply evaluate each gate one step at a time, working from left (inputs) to right (outputs).