Digital Logic Fundamentals

Lessons

Senior 4 · ICT

Digital Logic Fundamentals

5 lessons

Lesson 2 of 5

Boolean Algebra and Logic Gates

25 min

Logic as algebra

In 1854 the English mathematician George Boole published An Investigation of the Laws of Thought, in which statements that are either true or false are combined with operations, just as numbers are combined with + and ×. For eighty years it looked like pure mathematics. Then, in 1937, the American engineer Claude Shannon showed in his master's thesis that circuits of switches obey exactly Boole's rules. Every digital device since, from a calculator to a smartphone, is built from circuits that compute Boolean algebra.

George Boole (1815 to 1864), the mathematician whose algebra of true and false is now called Boolean algebra. A coloured engraving. Image: unknown author, public domain, via Wikimedia Commons.

Definition

Boolean variable: a quantity with only two values, written 1 (true, on, high voltage) and 0 (false, off, low voltage).

Logic gate: an electronic circuit with one or more binary inputs and one binary output, whose output is a Boolean function of its inputs.

Truth table: a table listing every combination of input values with the output for each. With $n$ inputs there are $2^{n}$ rows.

Boolean expression: a formula built from variables with AND (written $A \cdot B$ or $A B$ ), OR ( $A + B$ ) and NOT ( $\overline{A}$ , read "A bar" or "not A").

The three basic operations

Think of switches in a lamp circuit. Two switches in series light the lamp only if both are closed; two in parallel light it if either is closed.

AND: $Y = A \cdot B$ is 1 only when all inputs are 1.
OR: $Y = A + B$ is 1 when at least one input is 1. (So in Boolean algebra $1 + 1 = 1$ .)
NOT (inverter): $Y = \overline{A}$ has one input and gives the opposite value: $\overline{0} = 1$ , $\overline{1} = 0$ .

Order of operations: brackets first, then NOT, then AND, then OR. So $A + B \cdot C$ means $A + (B \cdot C)$ , just as $2 + 3 \times 4 = 14$ .

The seven gates

Combining NOT with AND and OR gives the inverted gates NAND and NOR. XOR (exclusive OR) is 1 when the inputs are different, and XNOR when they are the same.

A	B	AND $A \cdot B$	OR $A + B$	NAND $\overline{A \cdot B}$	NOR $\overline{A + B}$	XOR $A \oplus B$	XNOR $\overline{A \oplus B}$
0	0	0	0	1	1	0	1
0	1	0	1	1	0	1	0
1	0	0	1	1	0	1	0
1	1	1	1	0	0	0	1

NOT has one input: $A = 0 \to Y = 1$ ; $A = 1 \to Y = 0$ . Each inverted gate's column is the opposite of its partner's: compare AND with NAND, OR with NOR, XOR with XNOR.

A 7400 integrated circuit (bottom, a Texas Instruments SN7400N made in 1976) and the layout of its 14 pins (top). Inside are four separate 2-input NAND gates; pin 14 takes the +5 V supply and pin 7 goes to ground. The drawing uses the international (IEC) symbol, a rectangle marked & with a bubble, for the same NAND gate this lesson draws as a D shape with a bubble. Image: Audrius Meskauskas, CC BY-SA 3.0, via Wikimedia Commons.

Universal gates

NAND and NOR are called universal gates: any circuit can be built from NAND gates alone (or NOR gates alone). For example, joining both inputs of a NAND gate gives $\overline{A \cdot A} = \overline{A}$ , a NOT gate; a NAND followed by that NOT gives AND. Chip makers like this, because one kind of gate is cheaper to make in large numbers, which is why the 7400 chip above is a NAND chip.

Crash Course Computer Science #3: Boolean Logic and Logic Gates. Watch how AND, OR, NOT and XOR are built from transistors, and how the gate symbols correspond to the truth tables in this lesson.

Worked example 1: evaluate an expression

Find $Y = \overline{A \cdot B} + C$ when $A = 1$ , $B = 1$ , $C = 0$ .

Brackets and bar first: $A \cdot B = 1 \cdot 1 = 1$ , so $\overline{A \cdot B} = \overline{1} = 0$ .
Then OR: $Y = 0 + C = 0 + 0 = 0$ .

Now complete the truth table of $Y = A \cdot \overline{B} + \overline{A} \cdot B$ :

A	B	$\overline{A}$	$\overline{B}$	$A \cdot \overline{B}$	$\overline{A} \cdot B$	Y
0	0	1	1	0	0	0
0	1	1	0	0	1	1
1	0	0	1	1	0	1
1	1	0	0	0	0	0

The output column 0, 1, 1, 0 is the XOR column, so $A \oplus B = A \cdot \overline{B} + \overline{A} \cdot B$ .

Worked example 2: from words to Boolean algebra

A water pump on a school's tank must run ( $P = 1$ ) when its switch is on ( $S = 1$ ) and the tank is not full ( $F = 0$ ). Write $P$ .

"Switch on" is $S$ ; "tank not full" is $\overline{F}$ ; "and" is AND: $P = S \cdot \overline{F}$ Check: switch on, tank full: $P = 1 \cdot \overline{1} = 1 \cdot 0 = 0$ , so the pump stops and the tank does not overflow.

Warning

OR is not "one or the other but not both". In logic, $1 + 1 = 1$ : OR is true when both inputs are 1. "One or the other but not both" is XOR.

$\overline{A \cdot B}$ is not $\overline{A} \cdot \overline{B}$ . A bar over the whole term (NAND) is different from bars over each letter. With $A = 1, B = 0$ : $\overline{1 \cdot 0} = 1$ but $\overline{1} \cdot \overline{0} = 0$ . Lesson 5 gives the rule (De Morgan's law) that links them.

Tip

One word per gate. AND: all. OR: any. XOR: different. XNOR: same. NAND and NOR: the opposite of AND and OR. A bubble always means NOT.

✦

Practice

How many rows does the truth table of a 3-input gate have? A 4-input gate?
Write the output of each gate for $A = 1, B = 0$ : AND, OR, NAND, NOR, XOR, XNOR.
Evaluate $Y = A + B \cdot \overline{C}$ for $A = 0, B = 1, C = 0$ .
Complete the truth table of $Y = \overline{A + B}$ and name the gate.
Show, with a truth table, that joining both inputs of a NOR gate gives a NOT gate.
A car's warning buzzer sounds ( $W = 1$ ) when the engine is running ( $E$ ) and the driver's seat belt is not fastened ( $S$ ). Write $W$ as a Boolean expression.
A lamp at the bottom of a staircase is controlled by a switch at the bottom ( $A$ ) and one at the top ( $B$ ); flipping either switch changes the lamp. Which gate describes the lamp, and why?
A student claims that $\overline{A \cdot B} = \overline{A} \cdot \overline{B}$ . Test the claim for all four input pairs and evaluate it.

Show answersHide answers

$2^{3} = 8$ rows; $2^{4} = 16$ rows.
AND 0, OR 1, NAND 1, NOR 0, XOR 1, XNOR 0.
$\overline{C} = 1$ , $B \cdot \overline{C} = 1$ , $Y = 0 + 1 = 1$ .
(0,0) → 1; (0,1) → 0; (1,0) → 0; (1,1) → 0. NOR.
With both inputs equal to $A$ : $A = 0$ : $\overline{0 + 0} = 1$ ; $A = 1$ : $\overline{1 + 1} = 0$ . The output is $\overline{A}$ .
$W = E \cdot \overline{S}$ .
XOR (or XNOR, depending on how the lamp was wired at the start): each flip of one switch changes whether the inputs are the same or different, so the lamp toggles from either end.
Rows (A, B): (0,0): 1 and 1; (0,1): 1 and 0; (1,0): 1 and 0; (1,1): 0 and 0. The two sides differ in two rows, so the claim is false. (The correct statement, De Morgan's law, is $\overline{A \cdot B} = \overline{A} + \overline{B}$ .)

Quick check

Which gate gives 1 only when its two inputs are different?

Key points

Boolean variables take 0 or 1; AND ( $A \cdot B$ ) needs all inputs 1, OR ( $A + B$ ) needs any, NOT ( $\overline{A}$ ) inverts.
NAND, NOR and XNOR invert AND, OR and XOR; XOR is 1 when the inputs differ.
Order: brackets, NOT, AND, OR. A truth table with $n$ inputs has $2^{n}$ rows.
NAND and NOR are universal: any circuit can be built from either alone.

Sources and credits

Boolean algebra, Logic gate and A Symbolic Analysis of Relay and Switching Circuits, Wikipedia contributors, Wikipedia, licensed under CC BY-SA 4.0. Adapted by Ganzaa.
Portrait: George Boole color, unknown author, public domain, via Wikimedia Commons.
Image: TexasInstruments 7400 chip, view and element placement, Audrius Meskauskas, CC BY-SA 3.0, via Wikimedia Commons.
Video: Boolean Logic & Logic Gates, Crash Course Computer Science #3, CrashCourse, embedded from YouTube.
The gate and switch diagrams, truth tables, worked examples and practice items were written by Ganzaa.

This lesson adapts CC BY-SA material and is shared under CC BY-SA 4.0.

1Logic as algebra

2The three basic operations

3The seven gates

4Universal gates

Logic as algebra

The three basic operations

The seven gates

Universal gates