Discrete Math · Undergraduate
Boolean Algebra and Logic Gates
Quick answer
Boolean algebra is the arithmetic of the two values 0 and 1, with AND (written AB), OR (A + B) and NOT (A′). Its laws, such as A + AB = A and De Morgan's (A + B)′ = A′B′, simplify expressions, and every expression is a circuit of logic gates. Any truth table can be written as a sum of products, one product for each row that outputs 1, and then simplified. A half adder, the circuit that adds two bits, needs only an XOR gate for the sum and an AND gate for the carry.
What you'll learn
- Evaluate Boolean expressions with AND, OR and NOT
- Simplify expressions with the laws of Boolean algebra
- Write a sum-of-products formula from a truth table
- Describe simple circuits such as a half adder
Arithmetic with 0 and 1
Propositional logic becomes algebra when true is and false is :
| (AND) | (OR) | (NOT) | (XOR) | ||
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Each operation is a logic gate in a circuit, and each expression is a wiring diagram. The laws of Boolean algebra simplify those diagrams:
| Law | AND form | OR form |
|---|---|---|
| identity | ||
| complement | ||
| idempotent | ||
| absorption | ||
| distributive | ||
| De Morgan |
Why every truth table has a formula
Look at one row where the output is , say , , . The product is on that row and on every other, because some factor fails elsewhere. ORing together one such product for each row that outputs gives an expression that is on exactly those rows: a sum of products. So any function of bits can be built from AND, OR and NOT gates. The laws then shrink the formula, saving gates.
Worked examples
Common mistakes
Practice problems
-
Simplify .
Answer
Full solution
By the distributive law, .
-
Apply De Morgan’s law to .
Answer
Full solution
.
-
Evaluate at , , .
Answer
Full solution
and , so .
-
Simplify .
Answer
Full solution
Every term contains the factor , so absorption reduces the whole sum to .
-
Write a sum of products for the function that is exactly when .
Answer
Full solution
The rows and give the products and . This is NOT of XOR.
-
How many different Boolean functions of three variables are there?
Answer
Full solution
A truth table has rows, each with output or : tables.
-
Show that .
Answer
Both are exactly when one input is .
Full solution
.
-
A student writes . Give inputs that show the error.
Answer
,
Full solution
, but . The correct law is .
Frequently asked questions
What is Boolean algebra?
Algebra on the values 0 and 1 with three operations: AND (AB is 1 only if both are 1), OR (A + B is 1 if either is 1) and NOT (A′ flips the value).
How is it related to logic?
It is propositional logic with 1 for true and 0 for false: AND is ∧, OR is ∨ and NOT is ¬.
What is a sum of products?
An OR of AND terms, such as A′B + AB′. Every truth table has one: take a product for each row that outputs 1.
What are De Morgan's laws in Boolean form?
(A + B)′ = A′B′ and (AB)′ = A′ + B′. Negating flips AND and OR and negates each variable.
What does a half adder do?
It adds two bits A and B, producing a sum bit S = A ⊕ B (exclusive OR) and a carry bit C = AB.