Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Boolean algebra and De Morgan's theorems

Clear, exam-focused notes on Boolean algebra and De Morgan's theorems: definitions, laws with proofs, formulas, worked simplifications and NAND/NOR conversions, common mistakes and quick revision questions.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Boolean algebra and De Morgan's theorems give the mathematical rules engineers use to design and simplify digital logic (gates, combinational circuits, ALUs). Good mastery reduces gate count, power and cost, and helps convert logic to NAND-only or NOR-only implementations used in IC libraries and programmable logic.

Key ideas

Start from the first principles and vocabulary you must know.

  • Boolean algebra: an algebraic system for variables that take only two values: 0 (false, Low) or 1 (true, High). All operations are closed in {0,1}.
  • Boolean variable: a symbol (A, B, C...) that can be 0 or 1.
  • Literal: a Boolean variable or its complement (for example, A or A').
  • Complement (also called NOT): the unary operation that maps 0→1 and 1→0. We write the complement of A as A' (or an overbar A̅). Define A' = NOT A.
  • AND: binary operation written A·B (or simply AB). It outputs 1 only when both inputs are 1.
  • OR: binary operation written A + B. It outputs 1 when at least one input is 1.
  • Minterm: an AND (product) of all variables in either direct or complemented form (e.g., A·B'·C). Minterms are 1 for exactly one input combination.
  • Maxterm: an OR (sum) of all variables each in direct or complemented form (e.g., A + B' + C). Maxterms are 0 for exactly one input combination.
  • Sum of Products (SOP) and Product of Sums (POS) are canonical forms built from minterms and maxterms respectively.
  • Duality principle: If you swap AND ↔ OR and 0 ↔ 1 in any valid Boolean identity you get another valid identity (assumes the same variables and complements remain complements).

Basic Boolean laws (state and where they apply). Variables are Boolean (0 or 1); + is OR; · is AND; ' is complement.

  1. Commutative laws: A + B = B + A ; A·B = B·A. (order doesn't matter)
  2. Associative laws: (A + B) + C = A + (B + C) ; (A·B)·C = A·(B·C). (grouping doesn't matter)
  3. Distributive laws: A·(B + C) = A·B + A·C ; A + (B·C) = (A + B)·(A + C). (note second is also used frequently)
  4. Identity laws: A + 0 = A ; A·1 = A.
  5. Null (domination) laws: A + 1 = 1 ; A·0 = 0.
  6. Idempotent laws: A + A = A ; A·A = A.
  7. Complement laws: A + A' = 1 ; A·A' = 0.
  8. Involution: (A')' = A.
  9. Absorption laws: A + A·B = A ; A·(A + B) = A.
  10. Consensus (redundancy) theorem: A·B + A'·C + B·C = A·B + A'·C. (useful for eliminating a term)

Exact statements of De Morgan's theorems (these are required as exact forms in most exams):

  • De Morgan 1: (A + B)' = A'·B'.
  • De Morgan 2: (A·B)' = A' + B'. Assumptions: A and B are Boolean; complement ' denotes NOT. These generalise to any number of variables:
  • (A + B + C + ...) ' = A'·B'·C'·...
  • (A·B·C·...)' = A' + B' + C' + ...

Derivation universities commonly ask for (two methods):

  1. Truth-table proof for (A + B)' = A'·B':
    • Draw a table with columns labelled: A, B, A + B, (A + B)', A', B', A'·B'.
    • Write the four input rows in binary order: 00, 01, 10, 11. Compute each column and show (A + B)' column equals A'·B' column for all rows.
  2. Algebraic proof using complement and distributive laws:
    • Show that X = A'·B' is the complement of (A + B) by verifying the two complement conditions: (i) (A + B) + A'·B' = (A + B + A')·(A + B + B') = 1·1 = 1 (using x + yz = (x + y)(x + z) and A + A' = 1, B + B' = 1). (ii) (A + B)·A'·B' = A·A'·B' + B·A'·B' = 0 + 0 = 0.
    • Therefore A'·B' is the unique complement of (A + B), so (A + B)' = A'·B'.

Diagram to draw for truth-table proof: a table 7 columns wide (labels as above) and 4 rows for inputs. Shade or circle the columns (A + B)' and A'·B' to show they match row-by-row.

Other useful theorems derived from De Morgan (state them):

  • NAND and NOR are functionally complete: any Boolean function can be implemented using only NAND gates or only NOR gates. (Use De Morgan when converting.)
  • Converting OR to NAND: A + B = (A'·B')' by De Morgan.
  • Converting AND to NOR: A·B = (A' + B')' by De Morgan.

Be explicit that all above hold only for Boolean (binary) variables and standard two-valued logic. If you see multi-valued logic, different rules apply.

Formulas

A + B means A OR B. A and B are Boolean (0 or 1); unitless; applies to binary logic.

A·B means A AND B. A and B are Boolean; unitless; applies to binary logic.

A' means NOT A (complement). A is Boolean; unitless; applies to binary logic.

A + 0 = A identity law. Symbols unitless; valid for Boolean variables.

A·1 = A identity law. Unitless; Boolean logic.

A + A = A and A·A = A idempotent laws. Unitless; Boolean.

A + A' = 1 and A·A' = 0 complement laws. Unitless; Boolean.

(A + B)' = A'·B' De Morgan's first theorem. Unitless; Boolean.

(A·B)' = A' + B' De Morgan's second theorem. Unitless; Boolean.

A + (B·C) = (A + B)·(A + C) distributive law (OR over AND). Unitless; Boolean.

A·(B + C) = A·B + A·C distributive law (AND over OR). Unitless; Boolean.

Note: All formulas are dimensionless (no SI units) because they describe logical values.

Worked examples

Example 1 — Truth-table proof of De Morgan (typical exam question) Question: Prove (A + B)' = A'·B' by truth table and state why this proves the identity. Solution:

  1. Draw a table with columns: A | B | A + B | (A + B)' | A' | B' | A'·B'.
  2. Fill rows for A,B = 00, 01, 10, 11.
    • Row 00: A + B = 0; (A + B)' = 1; A' = 1; B' = 1; A'·B' = 1.
    • Row 01: A + B = 1; (A + B)' = 0; A' = 1; B' = 0; A'·B' = 0.
    • Row 10: A + B = 1; (A + B)' = 0; A' = 0; B' = 1; A'·B' = 0.
    • Row 11: A + B = 1; (A + B)' = 0; A' = 0; B' = 0; A'·B' = 0.
  3. Observe the column (A + B)' equals column A'·B' for every row; therefore the two expressions are equal for all possible inputs. This completes the proof. Answer: (A + B)' = A'·B' (shown by truth table).

Example 2 — Algebraic simplification (exam-style long question) Question: Simplify F = A·(B + A'·C) + A'·(B + C) to minimal SOP. Solution:

  1. Expand terms: F = A·B + A·A'·C + A'·B + A'·C.
  2. Use A·A' = 0: F = A·B + 0·C + A'·B + A'·C = A·B + A'·B + A'·C.
  3. Factor B from first two terms: F = (A + A')·B + A'·C.
  4. Use A + A' = 1: F = 1·B + A'·C = B + A'·C.
  5. Check if further simplification possible: B + A'·C = (B + A')·(B + C) by distributive law; this is not simpler in SOP. So minimal SOP is B + A'·C. Answer: F = B + A'·C.

Example 3 — Convert to NAND-only using De Morgan Question: Convert F = A + B·C to an expression using only NAND and complements (show steps). Solution:

  1. F = A + (B·C).
  2. Use De Morgan to express OR as NAND: X + Y = (X'·Y')' so F = (A'·(B·C)')'.
  3. Apply De Morgan on the inner product: (B·C)' is a NAND of B and C. Thus F = (A'·(B·C)')'.
  4. NAND-only implementation: realize A' with a NAND inverter (A NAND A = A'), realize (B·C)' with a NAND on B and C, then NAND those two results for the outer ' of the product. This uses only NAND gates. Answer: F = ((A·A)'·(B·C)')' (pure NAND form; single-input NANDs used as inverters).

Common mistakes

  • Dropping parentheses incorrectly when using distributive law (A + B·C ≠ (A + B)·(A + C) unless you explicitly apply the law correctly).
  • Assuming algebraic operations behave like arithmetic (e.g., thinking A + A = 2A). Boolean + is logical OR; A + A = A.
  • Trying to cancel terms that are not complements (e.g., removing B from A·B + B without application of absorption/consensus rules).
  • Not checking simplification by truth table or by substitution for all input combinations when unsure.

For your exam

Kinds of questions you will get on this topic:

  • Definitions: define Boolean algebra, complement, minterm, maxterm, duality, De Morgan's theorems.
  • Short notes: list and state laws with brief examples (commutative, distributive, absorption, De Morgan).
  • Derivations/proofs: prove De Morgan by truth table and by algebra; derive distributive from axioms; show duality examples.
  • Numericals / simplification: simplify given expressions to minimal SOP/POS; convert to NAND-only or NOR-only.
  • Diagrams: draw truth tables; show gate-level implementation before and after simplification.

What a full-marks answer includes:

  • Precise definitions (bold or underlined in answer scripts where allowed).
  • Correct statements of laws with assumptions (boolean variables, operations defined).
  • Clear truth-table or step-by-step algebraic proof for De Morgan.
  • If simplification question: each algebra step labelled with the law used (e.g., apply distributive, absorption), final simplified expression and optional check such as a 2- or 3-row truth sample or reasoning by consensus.
  • For gate conversion: a final gate-level description or clear statement how many NAND/NOR gates and where complements are produced.

Quick check

  1. State De Morgan's two theorems in symbols.
  2. Simplify: F = A·B + A'·B.
  3. Convert A·(B + C) to an equivalent using only OR and NOT (no AND).

Answers: 1) (A + B)' = A'·B' and (A·B)' = A' + B' ; 2) F = B·(A + A') = B ; hence F = B ; 3) Using only OR and NOT: A·(B + C) = (A' + (B + C)')'. (Show steps in exams.)

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?