A half adder has two inputs (the two bits to be added) and two outputs (the sum and the carry). Here's our target truth table for a half adder x + y.

The sum column is 1 when exactly one input is 1. This is exclusive or, another logic gate. We don't use it often, but most programming languages support it with the ^ operator, including Python. Here are the four possible binary inputs to Python's exclusive or. Notice that they exactly match the sum column in the truth table above.

>>> [0^0, 0^1, 1^0, 1^1]
[0, 1, 1, 0]

The Python function below is an XOR gate built from our existing gates, all of which are ultimately built from NAND. In English, this code reads: "XOR is true when at least one of the bits is true, but they're not both true."

>>> def XOR(x, y):
...     return AND(OR(x, y),
...                NOT(AND(x, y)))

# Check
>>> [XOR(0, 0), XOR(0, 1), XOR(1, 0), XOR(1, 1)]
[0, 1, 1, 0]

We can also represent this as a circuit diagram. Every logic gate here corresponds directly to an AND, OR, or NOT in the Python code. As before, all intermediate values are labeled with logical expressions.

(We could use NAND instead of the AND followed by a NOT, but we'll usually stick to NOT and AND because they're more familiar.)

That takes care of the sum, but we still need to compute the carry. In our table, the carry column is only 1 when both inputs are 1, so we can use AND: carry = x AND y. Putting the sum and carry together, we can write a half adder in Python:

>>> def HALF(x, y):
...     carry = AND(x, y)
...     sum = XOR(x, y)
...     return (carry, sum)

>>> [HALF(0, 0), HALF(0, 1), HALF(1, 0), HALF(1, 1)]
[(0, 0), (0, 1), (0, 1), (1, 0)]

The output of this function correctly computes both the sum and the carry, matching the truth table that we started with. We can also express it as a circuit diagram, which takes up more space but also makes it easier to see how data flows through the system. To make reading easier, the XOR gate is shown as a single unit, as is traditional in electronics.