Logic gates and Boolean algebra: How computers decide

In short: Computers calculate with true and false (1 and 0); logic gates such as AND, OR and NOT are the basic building blocks from which processors are built.

In more detail: Boolean algebra (George Boole, 1847) describes combinations of truth values. In electronics they correspond to logic gates: circuits that combine voltage levels (high = 1, low = 0). A processor consists of billions of such gates.

In Depth

The basic gates and truth tables

A	B	AND	OR	XOR	NAND	NOR
0	0	0	0	0	1	1
0	1	0	1	1	1	0
1	0	0	1	1	1	0
1	1	1	1	0	0	0

• NOT: inverts (0↔1).
• AND: 1 only if both are 1. OR: 1 if at least one is 1. XOR (exclusive or): 1 if exactly one is 1.
• NAND and NOR are universal: all other gates can be built from them.

Rules of calculation

• Commutative: A ∧ B = B ∧ A. Associative, distributive: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C).
• De Morgan: ¬(A ∧ B) = ¬A ∨ ¬B and ¬(A ∨ B) = ¬A ∧ ¬B.
• Neutral/zero: A ∧ 1 = A, A ∨ 0 = A, A ∧ 0 = 0, A ∨ 1 = 1.
• Double negation: ¬¬A = A. Absorption: A ∨ (A ∧ B) = A. With these rules you simplify expressions and circuits; Karnaugh maps help too.

From gates to a computer

• Half adder: sum = A XOR B, carry = A AND B.
• Full adder: adds A, B and carry; chained they form an adder for multi-digit binary numbers.
• Multiplexer (selects one of several lines), decoder, comparator.
• Flip-flops (made of feedback gates) store a bit; from them registers and memory arise.
• The ALU (arithmetic logic unit) in the processor combines such building blocks.

Use in programming

Boolean algebra is in if conditions (and, or, not), in bit operations (&, |, ^, ~), search filters, databases (WHERE) and test-case tables. Simplify complicated conditions with De Morgan. IHK tasks often contain truth tables and drawing/reading circuits. Practise with a logic simulator (Logisim, CircuitVerse in the browser).

See also: Bit masks and bit operations, Binary, decimal, hexadecimal, CPU structure, Comparison operators