I started working through the classic book “Elements of computing systems” (Nand2tetris) back in 2024, finished the first half on hardware and then stopped for reasons. It was fantastic and I learnt so much about how computers work under the hook from first principles. It is on my bucket list to finish this when I have time again in the future.

Here are my notes for the first chapter on Boolean algebra.

Boolean algebra

In boolean logic, we have two states 1.

We can operate on states using boolean operations.

{And, Or, Not} is a functionally complete set of such operators. All logical expressions can be expressed using only these operators.

---

How this maps to physical reality

Just like how numerical operators map to physical reality by explaining quantities (if I have 3 oranges, and I multiply by 2, then I have 6 oranges); boolean operators map to physical states of systems in the real world.

For example:

1. OR operator → I have two light switches connected in parallel. I want the bulb to turn on if either of the switches are on. x || y
2. AND operator → I have two light switches in series to a bulb. I want the bulb to turn on only if both switches are on. x && y
3. NOT operator → I have a light sensitive switch. I want the bulb to turn off when the light is bright. !x

---

Just like we can often simplify elementary algebra expressions knowing equivalence rules and so forth, we can do the same for boolean expressions:

https://www.geeksforgeeks.org/boolean-algebra/#laws-for-boolean-algebra

---

Nand operator

{And, Or, Not} can be proven and reduced to the smaller functionally complete set {Not, And} ~ The Nand operator. We can express Or by using only Not and And as follows:

**Using De Morgan's law:**
A OR B = Not(Not(A) And Not(B))

It can also be reduced to {Not, Or} , another functionally complete set.

---

Truth tables

Truth tables list all the possible combinations of states in our binary systems.

Any boolean expression can be represented in a truth table. The converse is also true, and practically derivable (NP-hard problem).

The practical application of truth tables is when we want to map the physical states of a system into computation.

Here is a practical application of truth tables.

1. Automated Security System (Door Alarm)

Problem: An alarm should sound if: • The door is open, or • The window is open, but • The system is not disarmed.

Inputs: • Door open (1) or closed (0) • Window open (1) or closed (0) • System armed (1) or disarmed (0)

Output: • Alarm (1 = ON, 0 = OFF)

Truth Table:

**D W S A**
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

Boolean Expression: A = (D OR W) AND S

Real-World Mapping: • Sensors on the door and window provide binary inputs and • A control unit checks if the alarm system is armed (). • The logic determines if the alarm should trigger.