How Boolean Logic Works — AND, OR, NOT, and Every Decision a Computer Makes
Every decision a computer makes reduces to boolean logic: is this condition true or false? Every if statement, every search filter, every permission check, every bit operation in the CPU — all built from three operations: AND, OR, NOT.
George Boole formalized this algebra in 1854. A century later, Claude Shannon proved that boolean algebra could be implemented with electrical circuits, founding the entire field of digital electronics.
The Three Basic Operations
AND — true only when both inputs are true.
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
In code: if (user.isAdmin && request.isValid) — both must be true.
OR — true when at least one input is true.
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
In code: if (cache.has(key) || db.has(key)) — either source is sufficient.
NOT — inverts the input.
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
In code: if (!user.isBlocked) — proceed when the condition is false.
Every other logical operation can be built from these three. In fact, NAND (NOT AND) alone is sufficient — every digital circuit can be constructed from NAND gates. This is called functional completeness.
XOR — The Odd One Out
XOR (exclusive or) — true when exactly one input is true. Different from OR, which is also true when both are true.
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR appears everywhere in computing:
- Cryptography — XOR is the basis of many encryption schemes. XORing data with a key encrypts it. XORing the ciphertext with the same key decrypts it.
- Error detection — parity checks use XOR to detect single-bit errors.
- Swapping values —
a ^= b; b ^= a; a ^= b;swaps a and b without a temporary variable. - Hash functions — combining hash values often uses XOR.
Bitwise Operations
Boolean operations apply not just to single true/false values but to every bit in a number simultaneously. These are bitwise operations:
1100 1010 (0xCA, decimal 202)
& 1111 0000 (0xF0, decimal 240)
-----------
1100 0000 (0xC0, decimal 192)
AND (&) — mask bits. Extracting the top 4 bits of a byte: byte & 0xF0.
OR (|) — set bits. Adding a flag: permissions | WRITE_FLAG.
XOR (^) — toggle bits. Flipping specific bits without affecting others.
NOT (~) — flip all bits. ~0 = all ones.
Shift left (<<) — multiply by powers of 2. 1 << 3 = 8.
Shift right (>>) — divide by powers of 2. 16 >> 2 = 4.
Where Does Boolean Logic Appear?
Database queries — WHERE age > 18 AND country = 'AT' is boolean AND. SQL's WHERE clause is boolean algebra over table rows.
Search filters — BM25 combines term matches with AND (all terms must appear) or OR (any term). Search query parsing is boolean expression evaluation.
Permission systems — Unix permissions are bit flags. 0755 = rwxr-xr-x. Checking if a file is writable: permissions & WRITE_BIT != 0.
Network masks — a subnet mask like 255.255.255.0 is ANDed with an IP address to extract the network portion. 192.168.1.42 & 255.255.255.0 = 192.168.1.0.
CPU arithmetic — the ALU (Arithmetic Logic Unit) in your CPU performs addition using chains of AND, OR, and XOR gates. A binary adder is just boolean logic wired together.
eBPF packet filtering — BPF (Berkeley Packet Filter) programs are boolean expressions over packet fields. "Match packets where destination port is 80 AND protocol is TCP."
De Morgan's Laws
Two rules that simplify boolean expressions:
- NOT (A AND B) = (NOT A) OR (NOT B)
- NOT (A OR B) = (NOT A) AND (NOT B)
In code: !(a && b) is the same as !a || !b. This is useful for refactoring complex conditions and understanding short-circuit evaluation.
Short-Circuit Evaluation
Most programming languages evaluate boolean expressions lazily:
A && B— if A is false, B is never evaluated (result is already false).A || B— if A is true, B is never evaluated (result is already true).
This isn't just an optimization — it changes behavior:
if (ptr != null && ptr.value > 10) // safe: second check only runs if ptr is not null
Without short-circuit evaluation, ptr.value would crash on a null pointer.
Next Steps
- How Complexity Works — measuring how fast or slow algorithms are as data grows.
- How Binary Works — the number system boolean logic operates on.