Boolean Algebra & Logic Circuits

Lesson 9 · OKSTEM College · AS Computer Science

Boolean Algebra Laws

Boolean algebra operates on values {0, 1} with three operations: AND (·), OR (+), and NOT (¬). The laws mirror set algebra and underlie all digital logic.

Law	AND form	OR form
Identity	a · 1 = a	a + 0 = a
Null	a · 0 = 0	a + 1 = 1
Idempotent	a · a = a	a + a = a
Complement	a · ¬a = 0	a + ¬a = 1
De Morgan	¬(a · b) = ¬a + ¬b	¬(a + b) = ¬a · ¬b
Absorption	a · (a + b) = a	a + (a · b) = a

NAND Universal Gate

NAND (NOT-AND) is functionally complete: any Boolean function can be built using only NAND gates. This matters in chip fabrication — one transistor type needed.

NOT a = a NAND a a AND b = (a NAND b) NAND (a NAND b) a OR b = (a NAND a) NAND (b NAND b)

Sum of Products (SOP)

Any Boolean function can be written in Sum of Products form: OR of AND terms, one per row where the output is 1.

Write the truth table for f(a,b,c) = 1 when exactly two inputs are 1.

Identify the rows where f=1: (0,1,1), (1,0,1), (1,1,0).

Write a minterm for each: ¬a·b·c, a·¬b·c, a·b·¬c.

SOP: f = ¬a·b·c + a·¬b·c + a·b·¬c.

Practice Problems

1. Simplify: a + (a · b) using absorption.

Absorption law: a + (a · b) = a.
Intuition: if a is already 1, the whole expression is 1 regardless of b.

2. Apply De Morgan: ¬(x + ¬y · z).

¬(x + (¬y · z)) = ¬x · ¬(¬y · z) [De Morgan on OR]
= ¬x · (y + ¬z) [De Morgan on AND, double negative]

Knowledge Check

De Morgan's law states ¬(a · b) equals

That's De Morgan applied to OR, not AND.

Correct — negating an AND flips to OR and negates each operand.

The negations of a and b are missing.

That's a different expression; De Morgan would expand it to ¬a · ¬b.

Recap: De Morgan AND: ¬(a AND b) = ¬a OR ¬b. De Morgan OR: ¬(a OR b) = ¬a AND ¬b. Negate and flip the operator.

A NAND gate is 'functionally complete' means

Functional completeness is about expressibility, not speed.

Correct — NAND alone can simulate NOT, AND, and OR.

All 2-input gates have 4 rows in their truth table.

'Complete' here means logically sufficient, not time-efficient.

Recap: NAND is universal — NOT(a) = a NAND a. This is why real chips often use only NAND or NOR gates: one transistor design, any function.

The complement law states a · ¬a =

a + ¬a = 1; a AND ¬a = 0.

Correct — a AND (NOT a) is always 0; they can't both be true.

That's the identity law (a · 1 = a).

No standard law gives ¬a as the result of a · ¬a.

Recap: complement · (AND): a AND ¬a = 0. Complement + (OR): a OR ¬a = 1. These are the exclusion laws.

Sum of Products (SOP) form is

That's Product of Sums (POS), the dual form.

Correct — each minterm is one row where the function is 1.

SOP is a specific canonical form, not just any simplified expression.

SOP works for any number of variables.

Recap: SOP = sum (OR) of products (AND-terms). Each product term covers exactly one truth table row where output = 1. Always correct; may not be minimal.

The absorption law says a + (a · b) =

No; absorption simplifies to the simpler term.

Correct — if a=1, the whole thing is 1; if a=0, a · b = 0, so result = 0. Either way, it equals a.

Only if a itself is 1; in general it equals a.

That would need a distributive expansion, not absorption.

Recap: absorption: a + (a·b) = a. The b is 'absorbed'. Dual: a · (a+b) = a.

← Previous Next →