Boolean Operations
Part of Boolean Logic and Gates
The core logical operations AND, OR, NOT, and their derivatives that form the basis of all digital computation.
Why This Matters
Every computation a digital system performs, whether adding two numbers or comparing strings, decomposes into a sequence of Boolean operations on individual bits. AND, OR, and NOT are the atoms of digital logic. Understanding them physically — as switches, as current paths, as voltage levels — builds the intuition needed to design circuits from scratch.
In a civilization rebuild scenario, you will construct logic gates from discrete transistors or relays before you can fabricate integrated circuits. Each gate implements a specific Boolean operation. Knowing what each operation means, how to test it, and how gates can be combined gives you a complete toolkit for building any digital device.
These operations also underlie programming: every conditional branch, every bitmask, every comparison instruction eventually executes as combinations of Boolean operations on registers. The software and hardware layers share the same mathematical foundation.
The AND Operation
AND outputs 1 only when both inputs are 1. In all other cases it outputs 0. The truth table has four rows for two inputs:
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The physical model is two switches in series. Current flows only when both switches are closed simultaneously. With relays, connect two relay contacts in series between the supply and load. With transistors in a relay driver, connect the two transistors’ collector-emitter paths in series.
AND is commonly written as A·B, AB, or A∧B. In code it is often the & operator (bitwise) or && (logical).
AND is used for masking: AND-ing a byte with a mask pattern forces specific bits to 0 while preserving others. To test whether bit 3 of a byte is set, AND the byte with 0b00001000 and check if the result is nonzero.
For multi-input AND, all inputs must be 1 for the output to be 1. A three-input AND gate can be built from two two-input AND gates in series: (A AND B) AND C.
The OR Operation
OR outputs 1 when at least one input is 1. It outputs 0 only when all inputs are 0.
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
The physical model is two switches in parallel. Current flows if either switch (or both) is closed. Connect two relay contacts in parallel, or use a diode-OR circuit where diodes point toward the output and their anodes connect to the respective input signals.
OR is written A+B, A∨B, or using | in code.
OR is used for flag aggregation: if any one of several error signals is active, raise an alarm. OR-ing a byte with a mask forces specific bits to 1 while preserving others. To set bit 5 of a byte, OR it with 0b00100000.
Note the important difference between OR (inclusive) and XOR (exclusive). OR includes the case where both inputs are 1; XOR excludes it. In natural language “or” is often exclusive, but in logic and electronics, OR is always inclusive unless explicitly stated otherwise.
The NOT Operation
NOT (inverter) has a single input and outputs its complement. If the input is 0, the output is 1; if the input is 1, the output is 0.
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
NOT is written as A’, Ā, ¬A, or ~A in code.
With a transistor, NOT is implemented as a common-emitter switch: when the input drives the transistor into saturation, the collector is pulled low (output = 0); when the input is low, the transistor is off and the collector is pulled high through a resistor (output = 1). This is the simplest active logic stage and is the building block for RTL (resistor-transistor logic).
NOT is essential for generating complementary signals. Many circuits require both a signal and its inverse — flip-flops, transmission gates, and differential signal pairs all need complementary inputs. A pair of inverters driven from the same source generates a complementary signal pair.
NAND and NOR
NAND is AND followed by NOT. NOR is OR followed by NOT.
NAND truth table:
| A | B | A NAND B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR truth table:
| A | B | A NOR B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Both NAND and NOR are universal gates — any Boolean function can be implemented using only NAND gates, or using only NOR gates. This is crucial in practice: TTL and CMOS integrated circuits often come in packages of four NAND gates. Knowing how to synthesize AND, OR, NOT, and XOR from NAND alone means one IC type can build any circuit.
In DTL and TTL technology, NAND is the natural operation of the transistor circuit topology, making it the most efficiently implemented gate.
XOR and XNOR
XOR (exclusive OR) outputs 1 when inputs differ, 0 when they are the same.
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR is written A⊕B. In code it is ^.
XOR has special properties that make it invaluable:
- A XOR A = 0 (a variable XORed with itself is always 0 — used to clear registers)
- A XOR 0 = A (XOR with 0 is identity)
- A XOR 1 = NOT-A (XOR with 1 is inversion — used for selective bit flipping)
- XOR is its own inverse: (A XOR B) XOR B = A
XOR is the key operation in binary addition (the sum bit of a half-adder is A XOR B) and in many error detection schemes (parity is computed by XOR-ing all bits together).
XNOR (exclusive NOR) is the complement of XOR — it outputs 1 when inputs are equal. It is used for equality comparison: if A XNOR B is 1, the two bits match.
Combining Operations: Derived Functions
All other Boolean operations derive from combinations of AND, OR, NOT. Implication (A implies B, written A→B) equals NOT-A OR B. Equivalence (A↔B) equals XNOR. Any truth table can be implemented by writing the sum-of-minterms form — OR-ing together AND terms for each row where the output is 1.
For example, to implement a function that is 1 only when A=1, B=0, C=1: F = A AND NOT-B AND C
If the function is 1 for multiple input combinations, OR these terms together: F = (A AND NOT-B AND C) OR (NOT-A AND B AND NOT-C)
This canonical form, called sum of minterms or sum of products (SOP), is a direct recipe for building any Boolean function from basic gates, before any simplification is applied.