- Hardware — the ALU in your CPU is built entirely from AND, OR and NOT gates.
- Software —
if,whileand the keywordsand / or / notin Python are Boolean operations. - Search — "laptop AND <50000 NOT refurbished" on an e-commerce site is a Boolean query.
- Everyday logic — "I will go out only if it is not raining and I have finished homework."
4.1 Boolean Values, Variables & Constants
A Boolean variable can hold only one of two values. Several equivalent names are used depending on context — all refer to the same pair:
| Logic term | Bit | Electronics | Python |
|---|---|---|---|
| TRUE | 1 | HIGH (e.g., +5 V) | True |
| FALSE | 0 | LOW (0 V) | False |
Boolean variables are usually written as capital letters A, B, C …. They are combined using three basic operators — NOT, AND and OR — which together form a complete set (every possible logic function can be built from them).
4.2 NOT — Inversion (unary)
The NOT operator has just one input. It flips the value: TRUE becomes FALSE, FALSE becomes TRUE. Also called inversion or complement.
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
4.3 AND — Conjunction
The AND operator returns TRUE only when every input is TRUE. With any FALSE input, the output is FALSE. It behaves like multiplication of 0s and 1s.
| A | B | A · B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
4.4 OR — Disjunction
The OR operator returns TRUE if at least one input is TRUE. It returns FALSE only when all inputs are FALSE. It behaves like addition (with 1 + 1 = 1, saturated).
| A | B | A + B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
- AND = "both must be true" — "You pass if attendance > 75% AND marks > 33%."
- OR = "at least one must be true" — "Tickets are free for senior citizens OR children under 5."
- NOT = "the opposite" — "I will attend the match only if it is NOT raining."
4.5 Logic Gate Symbols — Reference Chart
A logic gate is the physical electronic circuit that implements a Boolean operator. Each gate has a standard shape so that anyone, anywhere, can read a circuit drawing:
4.6 NAND — NOT-AND
A NAND gate is exactly an AND gate followed by a NOT. Every row of its truth table is the opposite of the AND row.
| A | B | A · B | NAND = (A · B)' |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
4.7 NOR — NOT-OR
A NOR gate is an OR gate followed by a NOT. Output is TRUE only when every input is 0.
| A | B | A + B | NOR = (A + B)' |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
4.8 XOR — Exclusive OR
The XOR gate returns TRUE only when the two inputs differ — exactly one is 1 and the other is 0. In words: "A or B, but not both."
| A | B | XOR = A ⊕ B | Inputs are… |
|---|---|---|---|
| 0 | 0 | 0 | same |
| 0 | 1 | 1 | different |
| 1 | 0 | 1 | different |
| 1 | 1 | 0 | same |
- Half-adder — sum bit in binary addition is computed with XOR.
- Parity / error detection — XOR of all bits gives the parity bit.
- Simple encryption — XOR-ing plain text with a key gives cipher text; XOR-ing again with the same key recovers the original.
4.9 Summary — All Six 2-Input Gates in One Table
| A | B | A · B (AND) | A + B (OR) | NAND | NOR | A ⊕ B (XOR) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
NOT A=A NAND AA AND B=NOT (A NAND B)=(A NAND B) NAND (A NAND B)A OR B=(NOT A) NAND (NOT B)=(A NAND A) NAND (B NAND B)
4.10 Fundamental Boolean Laws / Identities
Boolean algebra has a small set of laws that are used to simplify large expressions. Simpler expression = fewer gates = cheaper, faster circuit.
| Law | For AND (·) | For OR (+) |
|---|---|---|
| Identity | A · 1 = A | A + 0 = A |
| Null / Dominance | A · 0 = 0 | A + 1 = 1 |
| Idempotent | A · A = A | A + A = A |
| Complement | A · A' = 0 | A + A' = 1 |
| Double negation | (A')' = A | |
| Commutative | A · B = B · A | A + B = B + A |
| Associative | (A · B) · C = A · (B · C) | (A + B) + C = A + (B + C) |
| Distributive | A · (B + C) = A·B + A·C | A + (B · C) = (A+B) · (A+C) |
| Absorption | A · (A + B) = A | A + A · B = A |
| De Morgan's | (A · B)' = A' + B' | (A + B)' = A' · B' |
Y = A · B + A · B'
Y = A · B + A · B' = A · (B + B') ← distributive = A · 1 ← complement: B + B' = 1 = A ← identity ∴ Y = A (the variable B is irrelevant!)This is the power of Boolean algebra — an expression that looks like it needs 4 gates reduces to a wire.
4.11 De Morgan's Laws
Two special laws are named after Augustus De Morgan (1806 – 1871). They tell us how to push a NOT through an AND or an OR — and are the single most useful identity for simplifying logic circuits.
Law 2: (A + B)' = A' · B' "the NOT of an OR is the AND of the NOTs"
4.11.1 Verification by Truth Table
Build a truth table for both sides of Law 1 and check that the last two columns match — row by row.
| A | B | A · B | (A · B)' | A' | B' | A' + B' |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
The two bold columns are identical → Law 1 is proved. Law 2 can be verified the same way.
4.11.2 An Everyday Illustration
De Morgan's Law 1 lets us rewrite this as:
"Entry allowed if you are not under 18, OR you are not unaccompanied (i.e., you have an adult with you)."
Both sentences mean exactly the same thing — but the second one is easier to read at a glance.
4.11.3 Extended De Morgan (more variables)
(A + B + C)' = A' · B' · C'
In general: to negate a product, complement each variable and change · into +; to negate a sum, complement each variable and change + into ·.
4.12 Logic Circuits
A logic circuit is a drawing that shows how several gates are wired together so that their combined output computes a given Boolean expression. Circuits are read left to right: inputs on the left, output on the right.
4.12.1 Drawing a Circuit from an Expression
Work from the innermost part of the expression outwards — that is, in the same order you would evaluate it arithmetically.
4.12.2 Reading a Circuit — Expression from Diagram
The reverse direction is just as important in exams: given the circuit, write the Boolean expression. Work from left to right, labelling the output of each gate, then combine.
Stage 1 — output of NAND(P, Q) = (P · Q)'
Stage 2 — output of NOR((P · Q)', R) = ((P · Q)' + R)'
∴ Y = ((P · Q)' + R)'
Using De Morgan on the outside:
Y = ((P · Q)')' · R'
= (P · Q) · R'
= P · Q · R'
The simplified form P · Q · R' has only 3 gates' worth of cost (2 ANDs + 1 NOT) instead of the original 3 gates, and tells us immediately when Y = 1: when P = 1, Q = 1 and R = 0.
4.13 Universal Gates — Building Everything from NAND
Because NAND and NOR are functionally complete, entire CPUs can be built out of just one type of gate. Here is how the three basic operations look when built from NAND gates only:
📌 Quick Revision — Chapter 4 at a Glance
- Boolean algebra has only 2 values: 1 (TRUE) and 0 (FALSE). Named after George Boole (1854).
- Basic operators: NOT (flip), AND (both must be 1), OR (at least one is 1).
- Truth table = a table listing the output for every combination of inputs. n inputs → 2n rows.
- Derived gates: NAND = NOT AND; NOR = NOT OR; XOR = TRUE when inputs differ.
- Gate symbols: NOT = triangle + bubble; AND = D-shape; OR = shield; N-variants = add bubble; XOR = OR with an extra curve.
- Universal gates: NAND alone (or NOR alone) can build every other gate.
- Key laws: Identity (A·1=A, A+0=A), Null (A·0=0, A+1=1), Idempotent (A·A=A), Complement (A·A'=0, A+A'=1), Double-negation ((A')' = A), Commutative, Associative, Distributive, Absorption.
- De Morgan's Laws: (A · B)' = A' + B' and (A + B)' = A' · B'. Generalises to any number of variables.
- Logic circuit = drawing of gates wired to implement a Boolean expression. Inputs on left, output on right.
- Draw a circuit by going outwards from the innermost sub-expression; read a circuit by labelling each gate's output left to right.
- Simplification via Boolean laws reduces gate count → cheaper and faster hardware.