Boolean Logic and Algebra

Introduction

Every digital circuit inside a computer, no matter how complex, is built from the same simple mathematical foundation: Boolean Logic, developed by mathematician George Boole.

Concept

Boolean Logic works with variables that can only ever hold one of exactly two possible states — conventionally written as:

• 1 — True, High, On
• 0 — False, Low, Off

Three basic operators combine these values:

• AND, written as . (dot) — like multiplication.
• OR, written as + (plus) — like addition.
• NOT, written as ' (prime/apostrophe) — inverts a single value.

Explanation

The reason computers are built on Boolean logic specifically is physical, not just mathematical: a transistor is naturally either conducting electricity or not — a perfect physical match for a system with only two possible states. Every more complex digital operation ultimately reduces back to these three operators.

Note: The "+" and "." symbols in Boolean algebra look like ordinary arithmetic, but mean OR and AND respectively — not addition and multiplication, even though many of Boolean algebra's laws happen to resemble arithmetic ones.

Summary

Boolean Logic, developed by George Boole, works with two-state (1/0, True/False) variables combined using AND (.), OR (+), and NOT ('). This binary, two-state foundation is exactly why it maps naturally onto digital electronic circuits.

Primary Logic Gates

Introduction

A logic gate is the physical, electronic implementation of a Boolean operator — a real circuit component that takes electrical inputs and produces an output following AND, OR, or NOT logic.

Concept

Each gate's rule, and its complete truth table — every possible combination of inputs:

AND — Output is 1 only if ALL inputs are 1.

OR — Output is 1 if AT LEAST ONE input is 1.

NOT — Inverts the single input.

Explanation

NOT is the only gate here with just one input, which is exactly why it's nicknamed the Inverter — it doesn't combine anything, it simply flips whatever single value it receives, 0 becomes 1 and 1 becomes 0.

Note: AND requires EVERY input to be 1 to output 1 — even a single 0 among the inputs forces the output to 0. OR only needs ONE input to be 1 for the output to be 1.

Summary

AND outputs 1 only when every input is 1; OR outputs 1 when at least one input is 1; NOT (the Inverter) simply flips its one input — these three gates are the physical, circuit-level implementation of Boolean algebra's three basic operators.

The Basic Operations

Introduction

Two more gates are built by combining a basic gate with a NOT — and they turn out to be special enough to have their own name: Universal Gates.

Concept

NAND = NOT + AND — output is 0 only when all inputs are 1 (the exact opposite of AND).

NOR = NOT + OR — Boolean expression (A + B)', output is 1 only when all inputs are 0.

Both are called Universal Gates because either one, by itself, can be wired together to reproduce the behaviour of AND, OR, and NOT — meaning an entire digital circuit can theoretically be built using only NAND gates, or only NOR gates, with no other gate type needed at all. The simplest proof: feed a NAND gate the same input twice, A NAND A. Looking at the table above with B replaced by A — when A=0, the result is 1; when A=1, the result is 0. That's exactly the NOT gate's behaviour, built from nothing but a NAND.

Explanation

This "universal" property matters industrially, not just theoretically: manufacturing a circuit using just one type of gate component is simpler and cheaper than stocking and wiring together several different gate types — which is exactly why NAND and NOR are so heavily used in real chip design.

Note: NAND outputs 0 only when BOTH inputs are 1 (every other combination gives 1) — the mirror-opposite rule of AND, exactly as its name (NOT-AND) suggests.

Summary

NAND (NOT-AND) and NOR (NOT-OR) are each other's own gate family, and both are Universal Gates — either one alone can reconstruct AND, OR, and NOT, which is why real circuits are often built using only one gate type for simplicity and cost.

NAND vs. NOR Breakdown

Introduction

You've already seen NAND derive NOT, using nothing but itself. This topic goes one step further — showing that NAND alone can also build an OR gate, with no OR gate involved at all.

Concept

To build A OR B using only NAND gates:

1. Invert A using NAND: A NAND A gives NOT A (from the last topic).
2. Invert B the same way: B NAND B gives NOT B.
3. NAND the two inverted results together: (NOT A) NAND (NOT B).

That final result is exactly A OR B — built from three NAND gates and nothing else.

Worked Example

Trace all four input combinations through the three-step construction:

Take the second row as a concrete trace: A=0, B=1. Step 1: NOT A = 1. Step 2: NOT B = 0. Step 3: 1 NAND 0 — NAND is 0 only when both inputs are 1, so 1 NAND 0 = 1. The final column, A OR B for A=0, B=1, is also 1 — they match, exactly like every other row in the table.

Note: This table's final two columns are identical in every row — that's the actual proof that the three-NAND construction genuinely equals OR, not just a coincidence for one input combination.

Explanation

This works for the same reason NAND alone could build NOT: inverting both inputs before a final NAND flips the "only 0 when both are 1" rule into "only 1 when at least one is 1" — which is precisely OR's own rule. Having now built both NOT and OR from nothing but NAND, and already knowing AND is just NAND followed by a NOT, every basic gate can be reconstructed from NAND alone — the concrete evidence behind calling it a Universal Gate.

Summary

(A NAND A) NAND (B NAND B) equals A OR B — inverting both inputs before a final NAND reproduces OR's behaviour exactly, using three NAND gates and no OR gate at all, extending the last topic's proof that NAND alone can rebuild every basic gate.

The 3-Gate Blueprint

Introduction

The last topic showed, by tracing a truth table, that inverting both inputs before a final NAND produces OR. This topic gives the formal algebraic law that actually proves why — one that connects AND, OR, and NOT directly.

Concept

De Morgan's Laws are two rules connecting AND, OR, and NOT:

• Law 1: (A . B)' = A' + B' — NOT(A AND B) equals (NOT A) OR (NOT B).
• Law 2: (A + B)' = A' . B' — NOT(A OR B) equals (NOT A) AND (NOT B).

In words: negating a group changes AND to OR (or OR to AND), and negates each individual term inside it.

Worked Example

Verify Law 1, (A . B)' = A' + B', against every input combination:

The (A . B)' column and the A' + B' column are identical in every row — confirming the law holds for all four input combinations, not just some of them.

Note: (A . B)' is read "NOT of A AND B" — the NOT applies to the entire AND expression, not to A alone. This is different from A' . B, which only inverts A.

Explanation

Law 1 is exactly what the last topic's NAND-to-OR construction relied on, just written algebraically instead of traced by hand: A NAND B is (A . B)' by definition, and Law 1 says that equals A' + B' — which is precisely why inverting A and B first, then combining them, reproduces OR. The truth-table proof from the last topic and this algebraic law are two views of the exact same fact.

Summary

De Morgan's Laws: (A . B)' = A' + B' and (A + B)' = A' . B' — negating an AND/OR expression flips it to OR/AND and negates each term individually. Law 1 is the algebraic reason the last topic's NAND-based OR construction actually works.

Formal Statements

Introduction

A working recap of this whole chapter — from the two-state values Boolean logic is built on, through to the algebraic law that ties everything together.

Concept

• Boolean values: exactly two states — 1/True/High/On, or 0/False/Low/Off.
• Three basic operators: AND (.), OR (+), NOT (') — and the physical circuits that implement them: the AND, OR, and NOT logic gates.
• NAND and NOR: each is a basic gate followed by a NOT, and both are Universal Gates — either one, alone, can rebuild AND, OR, and NOT.
• NAND alone can build NOT (A NAND A) and OR ((A NAND A) NAND (B NAND B)) — the concrete, traced proof of NAND's universality.
• De Morgan's Laws: (A . B)' = A' + B' and (A + B)' = A' . B' — the algebraic rule underlying that NAND-to-OR construction.

Worked Example

Confirm the chapter's central claim — that NAND alone reconstructs AND — using De Morgan's Law 2 this time, (A + B)' = A' . B':

A AND B can be rewritten as ((A AND B)')' , since inverting something twice returns the original value. (A AND B)' is exactly what a single NAND gate computes. So A AND B is just that NAND result, inverted once more — and inverting is itself just NAND applied to two copies of the same signal, from the very first proof in this chapter. AND, OR, and NOT can all be rebuilt from NAND alone: NOT and OR were traced directly by truth table in earlier topics, and AND follows by inverting a NAND's own output the same way.

Tip: Whenever a question asks you to build one gate using only another, start from what you already know NAND (or NOR) can already reproduce — NOT is the simplest case, and every other gate builds on top of it.

Summary

Boolean logic works with two-state values, combined by AND/OR/NOT and their physical gate implementations. NAND and NOR are Universal Gates — capable of rebuilding every basic gate alone — proven concretely for NOT and OR by truth table, and explained algebraically by De Morgan's Laws, which connect AND, OR, and NOT into one consistent system.

The Simplification Workflow