Boolean Logic and Gates

Why This Matters

Every computer ever built --- from room-sized mainframes to the phone in your pocket --- operates on boolean logic. It is the mathematical framework that converts the transistor’s ability to switch on and off into the ability to compute anything. Master this, and you can design any digital circuit: from a simple alarm system to a full processor.

What You Need

For learning and building logic gates:

• NPN transistors: at least 20 (2N2222, 2N3904, BC547, or any general-purpose NPN)
• Resistors: 1k, 4.7k, 10k, 47k (at least 10 of each)
• Signal diodes: 1N4148 or equivalent (for DTL gates)
• LEDs (any color) for output indication
• 330-ohm resistors (for LED current limiting)
• Push buttons or toggle switches (for inputs)
• Breadboard (solderless prototyping board)
• 5V regulated DC power supply (three AA batteries with a 5V regulator, or USB power)
• Hookup wire (solid core, 22 AWG)
• Multimeter

---

Boolean Algebra: The Mathematics of Logic

In 1854, George Boole published a mathematical system with only two values: TRUE (1) and FALSE (0). This seemed like a mathematical curiosity until Claude Shannon proved in 1937 that electrical switches could implement Boolean algebra, making computation possible with hardware.

Two Values, Three Operations

Everything in Boolean algebra reduces to three fundamental operations on binary values:

NOT (Inversion):

Input A	Output (NOT A)
0	1
1	0

The output is the opposite of the input. Written as A’ or ~A or a bar over A.

AND (Conjunction):

Input A	Input B	Output (A AND B)
0	0	0
0	1	0
1	0	0
1	1	1

The output is 1 only when ALL inputs are 1. Written as A * B or A.B or AB.

OR (Disjunction):

Input A	Input B	Output (A OR B)
0	0	0
0	1	1
1	0	1
1	1	1

The output is 1 when ANY input is 1. Written as A + B.

Boolean Laws

These laws let you simplify complex logical expressions, which directly translates to using fewer transistors:

Law	Expression	Equivalent
Identity	A AND 1 = A	A OR 0 = A
Null	A AND 0 = 0	A OR 1 = 1
Complement	A AND (NOT A) = 0	A OR (NOT A) = 1
Idempotent	A AND A = A	A OR A = A
Commutative	A AND B = B AND A	A OR B = B OR A
Associative	(A AND B) AND C = A AND (B AND C)	Same for OR
Distributive	A AND (B OR C) = (A AND B) OR (A AND C)	Similar for OR over AND
De Morgan’s	NOT(A AND B) = (NOT A) OR (NOT B)	NOT(A OR B) = (NOT A) AND (NOT B)

Tip

De Morgan’s laws are the most practically useful. They tell you that a NAND gate is equivalent to an OR gate with inverted inputs, and a NOR gate is equivalent to an AND gate with inverted inputs. This means you can build any logic function using only NAND gates (or only NOR gates).

---

Building Logic Gates With Transistors

The NOT Gate (Inverter)

The simplest gate. One transistor, two resistors:

        +5V
         |
       [4.7k]  (Pull-up resistor)
         |
    +----+----> Output
    |
  Collector
    |
  [NPN]
    |
  Emitter
    |
   GND

  Input ---[10k]--- Base

When input is LOW (0V): No base current, transistor is OFF, output is pulled to +5V through the resistor. Output = HIGH (1).

When input is HIGH (5V): Base current flows through 10k resistor, transistor saturates, collector drops to about 0.2V. Output = LOW (0).

Input HIGH gives output LOW. Input LOW gives output HIGH. This is logical inversion.

The NAND Gate

Two transistors in series, sharing a pull-up resistor:

        +5V
         |
       [4.7k]
         |
    +----+----> Output
    |
  Collector (Q1)
    |
  Emitter/Collector (Q2)
    |
  Emitter
    |
   GND

  Input A ---[10k]--- Base Q1
  Input B ---[10k]--- Base Q2

Both transistors must be ON (both inputs HIGH) for the output to go LOW. If either input is LOW, its transistor is OFF, breaking the series path, and the output stays HIGH through the pull-up resistor.

A	B	Output
0	0	1
0	1	1
1	0	1
1	1	0

This is the truth table for NAND: NOT-AND.

The NOR Gate

Two transistors in parallel with a shared pull-up resistor:

        +5V
         |
       [4.7k]
         |
    +----+----+----> Output
    |         |
  Col(Q1)  Col(Q2)
    |         |
  Emt(Q1)  Emt(Q2)
    |         |
   GND       GND

  Input A ---[10k]--- Base Q1
  Input B ---[10k]--- Base Q2

If either transistor is ON (either input HIGH), the output is pulled LOW. Only when both transistors are OFF (both inputs LOW) does the output stay HIGH.

A	B	Output
0	0	1
0	1	0
1	0	0
1	1	0

This is NOR: NOT-OR.

AND and OR From NAND

Since NAND is universal, you can build any other gate from NAND alone:

NOT from NAND: Connect both inputs of a NAND gate together. With a single input A: NAND(A,A) = NOT(A AND A) = NOT(A).

AND from NAND: Take a NAND gate and follow it with a NOT (another NAND with tied inputs). NAND then NOT = AND.

OR from NAND: Apply NOT to each input (two NANDs with tied inputs), then feed both into a third NAND. By De Morgan’s law: NAND(NOT A, NOT B) = NOT(NOT A AND NOT B) = A OR B.

Tip

In practice, you will standardize on one gate type (usually NAND) and build everything from it. This simplifies manufacturing, reduces the types of components you need, and makes circuit design more systematic. The 7400 series TTL chip family is built around the quad 2-input NAND gate (four NAND gates in one package).

---

Number Systems

Binary (Base 2)

Computers work in binary because transistors have two states: on and off. Each binary digit (bit) is either 0 or 1.

Counting in binary:

Decimal	Binary	Explanation
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000	2^3
15	1111	2^3 + 2^2 + 2^1 + 2^0
255	11111111	8 bits = 1 byte, maximum value 255

Place values (right to left): 1, 2, 4, 8, 16, 32, 64, 128, …

To convert binary to decimal, multiply each bit by its place value and sum: 1101 = 8 + 4 + 0 + 1 = 13.

Binary Arithmetic

Addition rules:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10  (0 with carry 1)

Example:

    0110  (6)
  + 0011  (3)
  ------
    1001  (9)

Hexadecimal (Base 16)

Binary numbers get unwieldy. Hexadecimal uses 16 symbols (0-9, A-F) and maps directly to groups of 4 bits:

Hex	Binary	Decimal
0	0000	0
1	0001	1
9	1001	9
A	1010	10
B	1011	11
F	1111	15

Example: Binary 11010110 = D6 in hex = 214 in decimal.

---

Combinational Logic: Computing With Gates

The Half Adder

The simplest arithmetic circuit: adds two single-bit numbers and produces a sum and a carry.

Inputs: A, B
Outputs: Sum = A XOR B, Carry = A AND B

A	B	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

XOR (exclusive OR) is built from NAND gates: XOR(A,B) = NAND(NAND(A, NAND(A,B)), NAND(B, NAND(A,B))). It takes 4 NAND gates.

The Full Adder

Adds two bits plus a carry-in from the previous column. This is what you chain together to add multi-bit numbers.

Inputs: A, B, Carry_in
Outputs: Sum, Carry_out

Sum = A XOR B XOR Carry_in
Carry_out = (A AND B) OR (Carry_in AND (A XOR B))

An 8-bit adder is 8 full adders chained together, with each carry-out feeding into the next carry-in. This circuit can add any two numbers from 0 to 255. It requires about 40-50 NAND gates total.

Tip

The full adder is the single most important combinational circuit. With addition, you can implement subtraction (add the negative), multiplication (repeated addition), and division (repeated subtraction). A computer that can add can compute anything --- it just takes more steps for complex operations.

The Multiplexer

A multiplexer (MUX) selects one of several input signals and routes it to the output, based on a binary select code.

2-to-1 MUX: Two data inputs (D0, D1), one select input (S), one output (Y).

• When S = 0, Y = D0
• When S = 1, Y = D1

Built from 2 AND gates, 1 OR gate, and 1 NOT gate (or 4 NAND gates).

Why it matters: Multiplexers route data within a computer. The select lines act as addresses, choosing which piece of data to process. An 8-to-1 MUX can replace complex arrays of switches.

---

Sequential Logic: Memory

Combinational circuits produce output purely from current inputs. Sequential circuits remember previous states. This is how computers store data.

The SR Latch

The simplest memory element, built from two cross-coupled NAND gates (or NOR gates):

       +-------+
  S ---| NAND  |--+----> Q
       +-------+  |
                   |
       +-------+  |
  R ---| NAND  |--+----> Q' (not Q)
       +-------+
  (Cross-coupled: Q feeds back to second NAND input,
   Q' feeds back to first NAND input)

S	R	Q (next)	Action
1	1	Q (unchanged)	Hold (no change)
0	1	1	Set
1	0	0	Reset
0	0	Invalid	Both outputs go HIGH (forbidden)

Key insight: When both S and R are inactive (both HIGH for NAND version), the latch holds its previous state. This is memory --- one bit of storage using just two gates.

The D Flip-Flop

The SR latch is difficult to use because of the forbidden state and the lack of timing control. The D (Data) flip-flop solves both problems:

• It has one data input (D) and one clock input (CLK)
• On the rising edge of the clock, the output Q takes the value of D
• Between clock edges, the output does not change regardless of what D does

This is edge-triggered storage: data is captured only at the precise moment the clock transitions from LOW to HIGH.

Building a D flip-flop: Requires 4-6 NAND gates in a master-slave configuration. The master latch captures D when clock is HIGH; the slave latch transfers to the output when clock goes LOW.

Registers

A register is a group of D flip-flops sharing a common clock signal. An 8-bit register stores one byte (8 bits) simultaneously.

        D7  D6  D5  D4  D3  D2  D1  D0   (8 data inputs)
         |   |   |   |   |   |   |   |
        [FF][FF][FF][FF][FF][FF][FF][FF]  (8 flip-flops)
         |   |   |   |   |   |   |   |
        Q7  Q6  Q5  Q4  Q3  Q2  Q1  Q0   (8 data outputs)
                        |
                      CLK (shared clock)

On each clock pulse, all 8 bits are captured simultaneously. This is how a computer holds a number in its processor.

Counters

Chain flip-flops so that each one’s output clocks the next:

• First flip-flop toggles on every input pulse (divides frequency by 2)
• Second flip-flop toggles on every transition of the first (divides by 4)
• Third toggles on every transition of the second (divides by 8)
• The outputs represent a binary count: 000, 001, 010, 011, 100, 101, 110, 111, then back to 000

A 4-bit counter counts from 0 to 15. An 8-bit counter counts from 0 to 255. Counters are used for addressing memory, timing, generating sequences, and many other tasks.

---

Practical Logic Families

Resistor-Transistor Logic (RTL)

The simplest approach, used in early computers:

• Resistors at the inputs, transistor does the switching
• NOR gate is the basic element
• Slow (propagation delay ~50 ns), limited fan-out (can drive 3-4 other gates)
• Easy to build from discrete components on breadboard

Diode-Transistor Logic (DTL)

Uses diodes for the AND/OR function, transistor for inversion and gain:

• Faster than RTL, better fan-out
• The basic AND gate uses diodes with a common pull-up resistor, followed by a transistor inverter
• Reasonable for small custom circuits

Transistor-Transistor Logic (TTL)

The standard for decades (the 7400 series):

• Uses multi-emitter transistors for the input stage
• Very fast (propagation delay ~10 ns for standard TTL)
• Good fan-out (drives 10 standard TTL inputs)
• Standard voltage levels: LOW = 0-0.8V, HIGH = 2.0-5.0V

Parameter	RTL	DTL	TTL
Propagation delay	~50 ns	~30 ns	~10 ns
Fan-out	3-4	8-10	10
Noise margin	Low	Medium	Good
Power per gate	~10 mW	~10 mW	~10 mW
Ease of discrete build	Easy	Medium	Difficult

Tip

For a post-collapse rebuild, start with RTL (it is the simplest to construct from individual transistors and resistors) for your first logic circuits. Upgrade to DTL for anything that needs more than a few gates. If you can salvage 7400-series TTL chips, use them --- each chip contains 4-6 gates in a single package, saving enormous amounts of wiring.

---

Common Mistakes

Mistake	Why It’s Dangerous	What to Do Instead
Floating inputs (unconnected gate inputs)	Pick up noise, cause random behavior, oscillation	Tie unused inputs to VCC or GND through a resistor
Mixing logic families without level shifting	Different voltage thresholds, unreliable operation	Check input/output voltage specifications, add buffers if needed
Forgetting decoupling capacitors	Switching transients on power supply cause false triggering	Place 0.1 uF ceramic capacitor across VCC-GND at every IC or every 4-5 transistors
Clock signal ringing	Noisy clock causes double-triggering of flip-flops	Use short clock wires, add series termination resistor (33-100 ohm)
No pull-up/pull-down on switch inputs	Switch bounces cause multiple triggers	Add debounce circuit (RC filter + Schmitt trigger) or pull-up resistor
Exceeding fan-out	Output cannot drive all connected inputs, voltage levels sag	Count gate loads, add buffer/driver if exceeding specification
Ignoring propagation delay in timing	Signals arrive at different times, causing glitches	Add synchronizing flip-flops, use registered outputs
Race conditions in asynchronous design	Two signals arrive at slightly different times, wrong result	Use synchronous design with a common clock wherever possible

---

What’s Next

With boolean logic and gates, you can build any digital circuit. The next steps on the computing path:

• Programming Fundamentals --- learn how to write sequences of instructions that command a processor built from these gates
• Data Storage --- learn how to store data persistently, beyond the volatile flip-flop memory covered here

---

Quick Reference Card

Boolean Logic and Gates --- At a Glance

Three fundamental operations: NOT (inversion), AND (all inputs true), OR (any input true)

Universal gates: NAND or NOR alone can build any other gate

NOT gate: 1 transistor + 2 resistors

NAND gate: 2 transistors in series + pull-up resistor

NOR gate: 2 transistors in parallel + pull-up resistor

De Morgan’s laws: NOT(A AND B) = (NOT A) OR (NOT B); NOT(A OR B) = (NOT A) AND (NOT B)

Binary: Base-2, place values 1-2-4-8-16-32-64-128

Full adder: Adds two bits plus carry, chain 8 for byte addition

SR Latch: 2 cross-coupled NANDs = 1 bit of memory

D Flip-Flop: Edge-triggered 1-bit storage, captures on clock rising edge

Register: N flip-flops sharing clock = N-bit word storage

Logic levels (TTL): LOW = 0-0.8V, HIGH = 2.0-5.0V, supply = 5V

Decoupling: 0.1 uF ceramic capacitor across every power connection