Elvin tells his friends: “If the weather is good on Saturday and I finish my homework, I'll go to the Baku Boulevard.” This sentence has two conditions joined by the word “and”. A computer makes decisions in exactly this way — it joins simple conditions with logical operations. Only instead of “yes” and “no” it uses 1 and 0.
Statements: true and false
Statement (proposition)Definition
A sentence that is definitely either true or false. A true statement has the value 1, and a false one has the value 0.
For example, “Baku is the capital of Azerbaijan” is a true statement (1), and “5 > 8” is a false statement (0). “What's the weather like today?” is not a statement at all, because a question can be neither true nor false.
The basic logical operations
- NOT (negation) flips the value: NOT 1 = 0, NOT 0 = 1.
- AND (conjunction) gives 1 only when both statements are true.
- OR (disjunction) gives 1 when at least one statement is true.
- Exclusive OR (XOR) gives 1 only when exactly one statement is true, that is, when the inputs differ.
You can picture these operations with ordinary switches and a lamp. A closed switch is 1, an open one 0; a lamp that is on is 1, a lamp that is off 0.
| Operation | An everyday picture |
|---|---|
| AND | Two switches one after the other (in series): the lamp lights only when both are closed |
| OR | Two switches side by side (in parallel): the lamp lights if at least one is closed |
| NOT | A “contrary” button: press it and the light goes off, let go and it comes on |
| XOR | A staircase light: there is a switch at the bottom and one at the top, and flipping either one changes the lamp |
A table that shows the result of an operation for every possible case is called a truth table. With two inputs there are only 4 cases:
| A | B | A AND B | A OR B | A XOR B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Count the cases
n inputs have 2ⁿ cases: two inputs — 4 rows, three inputs — 8 rows.
Write the rows by counting in binary
Write the inputs as if you were counting in binary: 00, 01, 10, 11 — this way no case is forgotten.
Fill in column by column
AND works like ordinary multiplication: 1 · 1 = 1, everything else gives 0. OR answers the question “is there at least one 1?”
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
In maths and in many textbooks these operations are written with symbols: A ∧ B (AND), A ∨ B (OR), ¬A (NOT), A ⊕ B (XOR). They obey the laws of Boolean algebra, and each law can be checked with a truth table of 4 or 8 rows. Some look like ordinary algebra and some do not: the second distributive law, for example, has no counterpart for numbers (a + b · c ≠ (a + b) · (a + c)).
| Law | Formula |
|---|---|
| Commutative | A ∧ B = B ∧ A, A ∨ B = B ∨ A |
| Distributive | A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C), A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) |
| De Morgan’s laws | ¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B |
| Absorption | A ∨ (A ∧ B) = A, A ∧ (A ∨ B) = A |
| Complement and double negation | A ∨ ¬A = 1, A ∧ ¬A = 0, ¬¬A = A |
| Idempotence | A ∧ A = A, A ∨ A = A |
Logic gates
Inside a computer, logical operations are carried out by logic gates. These are tiny electronic circuits built from transistors: signals of 0 or 1 go into the inputs, and the result comes out of the output. A modern processor contains billions of transistors, and the gates built from them add numbers, compare them and store them in memory.
Interactive
Besides the basic gates, their combinations are widely used: NAND (NOT AND) flips the result of AND, and NOR (NOT OR) flips the result of OR. Interestingly, any other logic circuit can be built from NAND gates alone.
There are two more gates. NAND (NOT AND) means “not both”: it flips the answer of AND. NOR (NOT OR) means “neither”: it flips the answer of OR. Interestingly, NAND gates alone are enough to build any other logic circuit — like building a whole house from a single kind of brick.
| A | B | A AND B | NAND | NOR |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 |
Everything from NAND
Problem
Using only NAND gates, build NOT, AND, OR and XOR. How many gates does XOR need?
Show solutionHide solution
Solution
A AND B = NOT NAND(A, B) = NAND(N, N), where N = NAND(A, B).
A OR B = NAND(¬A, ¬B) — by De Morgan’s law, ¬(¬A ∧ ¬B) = A ∨ B.
XOR: let N = NAND(A, B); then A ⊕ B = NAND(NAND(A, N), NAND(B, N)) — only 4 gates. A truth table confirms it: in all four cases the result matches A ⊕ B.
Because of this property, chips are often built from one kind of gate.
Logical expressions and binary addition
Operations combine into a logical expression. Without brackets, NOT is done first, then AND, and OR last — much like multiplication comes before addition in math.
Read an expression without brackets as in maths: NOT is like a minus sign stuck to its letter and is done first, AND is like multiplication and OR like addition. So NOT A OR B AND C is read as (NOT A) OR (B AND C) — just like −a + b · c.
Work it out in order
Problem
Find the value of NOT A OR B AND C when A = 1, B = 1, C = 0.
Show solutionHide solution
Solution
2) B AND C = 1 AND 0 = 0.
3) 0 OR 0 = 0.
Order: NOT → AND → OR.
Example: evaluating an expression
Problem
Find the value of (A OR B) AND NOT C when A = 1, B = 0, C = 1.
Show solutionHide solution
Solution
2) NOT C = NOT 1 = 0.
3) 1 AND 0 = 0.
The expression is false, because one of the inputs of AND is 0.
There is also the reverse task: a truth table is given and a formula must be found. A universal method: for each row whose result is 1, join that row’s variables with ∧ (put ¬ in front of a variable equal to 0), join these terms with ∨, then simplify with the laws of Boolean algebra. A table of n variables has 2ⁿ rows, so there are 2^(2ⁿ) different functions: 16 for two variables.
From a table to a formula
Problem
A function F is given: F(0, 0) = 1, F(0, 1) = 1, F(1, 0) = 0, F(1, 1) = 1. Find the shortest formula for F.
Show solutionHide solution
Solution
F = (¬A ∧ ¬B) ∨ (¬A ∧ B) ∨ (A ∧ B).
Take ¬A out of the first two terms: ¬A ∧ (¬B ∨ B) = ¬A ∧ 1 = ¬A.
F = ¬A ∨ (A ∧ B) = (¬A ∨ A) ∧ (¬A ∨ B) = ¬A ∨ B (the second distributive law).
This function is implication, A → B (“if A, then B”): it is false only when A = 1 and B = 0.
How does a computer add? The half adder
Problem
We need to add two bits, A and B. Which gates give the sum digit (S) and the carry to the next position (C)?
Show solutionHide solution
Solution
0 + 0 = 00₂ → S = 0, C = 0
0 + 1 = 01₂ → S = 1, C = 0
1 + 0 = 01₂ → S = 1, C = 0
1 + 1 = 10₂ → S = 0, C = 1
The S column matches the XOR table, and the C column matches the AND table.
So S = A XOR B and C = A AND B. By combining such circuits, a processor adds numbers of any length.
A half adder can only add the rightmost place: it ignores the carry coming from the previous place. A full adder has three inputs — A, B and the incoming carry Cin: S = A ⊕ B ⊕ Cin, Cout = (A ∧ B) ∨ (Cin ∧ (A ⊕ B)). It is built from two half adders and one OR gate. Chain 8 full adders together and you get a circuit that adds 8-bit numbers — the simplest part of a processor’s arithmetic logic unit (ALU).
| A | B | Cin | S | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Interactive
print('A B | AND OR XOR')
for a in (0, 1):
for b in (0, 1):
print(f'{a} {b} | {a & b} {a | b} {a ^ b}')Expected output
A B | AND OR XOR 0 0 | 0 0 0 0 1 | 0 1 1 1 0 | 0 1 1 1 1 | 1 1 0
& is AND, | is OR and ^ is XOR on bits. The program builds the whole truth table by itself.Remember
- A statement is either true (1) or false (0).
- AND gives 1 only when both inputs are 1; OR gives 1 when at least one input is 1.
- NOT flips the value; XOR gives 1 when the inputs differ.
- Without brackets the order is NOT, then AND, then OR.
- Logic gates are built from transistors; XOR and AND together add two bits.