Inside a computer, every wire carries one of two voltage levels, low or high, read as 0 and 1. Two levels are easy to tell apart even with electrical noise, so a signal can pass through billions of circuits without being misread. This is digital logic.
A logic gate is a tiny circuit, built from a few transistors, that computes one output bit from its input bits. A truth table lists the output for every combination of inputs: with n inputs there are 2ⁿ rows.
The basic gates
| Gate | Output is 1 when… | Written as | In Python, for bits |
|---|---|---|---|
| NOT | the input is 0 | A' (or Ā) | 1 - a |
| AND | all inputs are 1 | A·B, or just AB | a & b |
| OR | at least one input is 1 | A + B | a or b, a | b |
| NAND | not all inputs are 1 | (AB)' | 1 - (a & b) |
| NOR | no input is 1 | (A + B)' | 1 - (a | b) |
| XOR | the inputs differ | A ⊕ B | a ^ b |
| XNOR | the inputs are equal | (A ⊕ B)' | 1 - (a ^ b) |
In Boolean notation, + means OR and · means AND. They are not ordinary addition and multiplication: 1 + 1 = 1.
print("a b | AND OR XOR NAND NOR")
for a in [0, 1]:
for b in [0, 1]:
print(a, b, "|", a & b, " ", a | b, " ", a ^ b, " ", 1 - (a & b), " ", 1 - (a | b))Try it
Type any formula with and, or, not and xor, using letters as inputs. This one is NAND:
XOR is "one or the other, but not both". It shows up in adders (next lessons), in parity checks and in encryption.
Common mistakes
- Reading A + B as arithmetic: in Boolean algebra 1 + 1 = 1.
- Mixing up NAND and NOR: NAND is 0 only when all inputs are 1; NOR is 1 only when all inputs are 0.
- Forgetting how many rows a table needs: 3 inputs need 2³ = 8 rows, not 6.
Quick check
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.