First Year 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.

Logic gates and Boolean algebra

Core of digital design: Boolean algebra, truth tables, canonical forms (SOP/POS), and implementation with basic and universal logic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR).

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

Engineers use logic gates and Boolean algebra to design, analyze, and simplify digital circuits in microcontrollers, IoT nodes, communication systems, and VLSI chips. Every digital system—from adders and multiplexers to flip-flops and counters—starts from correct logical expressions and their efficient gate-level implementation.

Key ideas

  • Boolean algebra: An algebra over the set {0,1} with operations defined as logical AND (·), OR (+), and NOT (′). It follows specific postulates and theorems different from ordinary (real-number) algebra. Operator precedence in Boolean expressions: NOT has highest precedence, then AND, then OR; use parentheses as needed.
  • Logic gate: An electronic circuit that implements a Boolean operation. Ideal gates output exact 0/1; real gates have logic-level voltage ranges (volts) and nonzero delay (seconds), but we treat them as ideal in this topic.
  • Truth table: A table listing output(s) for all possible input combinations. For n inputs, there are 2^n rows.
  • AND gate (·): Output is 1 only if all inputs are 1. Symbol: D-shaped gate with a flat input side and curved output side; label inputs A, B, output Y = A·B.
  • OR gate (+): Output is 1 if any input is 1. Symbol: curved input side merging to a pointed output side; label Y = A + B.
  • NOT gate (inverter, ′): Output is the complement: Y = A′. Symbol: triangle with bubble (small circle) at output.
  • NAND gate: NOT of AND, Y = (A·B)′. Symbol: AND symbol with output bubble. Universal gate (can implement any Boolean function with only NANDs).
  • NOR gate: NOT of OR, Y = (A + B)′. Symbol: OR symbol with output bubble. Universal gate.
  • XOR gate (⊕): Exclusive-OR, Y = A⊕B = A′B + AB′. Output 1 when inputs differ.
  • XNOR gate: Exclusive-NOR (equivalence), Y = (A⊕B)′ = AB + A′B′. Output 1 when inputs are equal.
  • Complement (′): If A is 1 then A′ is 0, and if A is 0 then A′ is 1.
  • Minterm: A product (AND) term in which every variable appears exactly once, either in true or complemented form, e.g., for variables A, B, C: A′B C′ is a minterm. Each minterm corresponds to exactly one input combination where it equals 1.
  • Maxterm: A sum (OR) term in which every variable appears exactly once, either true or complemented, e.g., A + B′ + C is a maxterm. Each maxterm equals 0 at exactly one input combination.
  • Canonical Sum of Products (SOP): A sum (OR) of minterms that produce 1. Written as F = Σ m(indices).
  • Canonical Product of Sums (POS): A product (AND) of maxterms that produce 0. Written as F = Π M(indices).
  • Duality principle: In Boolean algebra, interchanging + with · and 0 with 1 in a valid identity produces another valid identity (variables stay unchanged). Every theorem has a dual.
  • Algebraic simplification: Using identities to reduce expressions to fewer literals or gates without changing function.
  • Gate-level realization: Drawing a circuit with logic gate symbols to implement a Boolean expression.

Exact statements of fundamental laws and theorems (all variables Boolean unless noted):

  • Commutative laws: A + B = B + A; A·B = B·A. Assumes binary operations on Boolean domain.
  • Associative laws: (A + B) + C = A + (B + C); (A·B)·C = A·(B·C). Parentheses can be regrouped.
  • Distributive laws: A·(B + C) = A·B + A·C; A + (B·C) = (A + B)·(A + C).
  • Identity laws: A + 0 = A; A·1 = A.
  • Null (domination) laws: A + 1 = 1; A·0 = 0.
  • Idempotent laws: A + A = A; A·A = A.
  • Complementarity laws: A + A′ = 1; A·A′ = 0.
  • Involution law: (A′)′ = A.
  • Absorption laws: A + A·B = A; A·(A + B) = A.
  • Consensus theorem: A·B + A′·C + B·C = A·B + A′·C. (The term B·C is redundant.) Dual: (A + B)·(A′ + C)·(B + C) = (A + B)·(A′ + C).
  • De Morgan’s theorems: (A·B)′ = A′ + B′; (A + B)′ = A′·B′. For more than two variables: complement of a product is sum of complements, and vice versa.
  • Transposition (or elimination) rules: Not required for this topic; omit unless your syllabus explicitly includes a correct, vetted statement.

Derivations commonly asked:

  1. De Morgan’s theorem (two-variable) using truth table:
    • List all four combinations of A, B.
    • Compute A·B, then (A·B)′.
    • Compute A′, B′, then A′ + B′.
    • Show columns (A·B)′ and (A′ + B′) match for all rows; hence proved. Similarly for (A + B)′ = A′·B′.
  2. Absorption law derivation: A + A·B = A·1 + A·B = A·(1 + B) = A·1 = A. Similarly, A·(A + B) = A.
  3. Consensus theorem derivation (sketch): Start with A·B + A′·C + B·C. Add the redundant term’s expansion A·B·C + A′·B·C, factor and use absorption to eliminate B·C. Exams accept either algebraic proof or Karnaugh-map based proof (but K-map belongs to combinational simplification; here we stick to algebra).

Gate universality proofs (outline to draw/describe):

  • NAND as universal:
    • NOT from NAND: Tie both inputs together: Y = (A·A)′ = A′. Draw a 2-input NAND with both inputs labeled A and a single output bubble not shown (NAND already has inversion).
    • AND from NAND: First NAND then NOT the output: A·B = [(A·B)′]′. Draw NAND gate followed by a NAND-as-inverter.
    • OR from NAND: Using De Morgan, A + B = (A′·B′)′. Invert A and B with NAND-inverters, then feed to a NAND gate.
  • NOR as universal: Dual arguments using NOT from NOR (tie inputs), OR from NOR followed by inversion, AND using De Morgan.

Canonical forms and mapping to minterms/maxterms:

  • Given a truth table for F(A,B,C), list rows where F = 1. For each such row, write the corresponding minterm (variable is uncomplemented if its row value is 1, complemented if 0). Sum them: canonical SOP. Write as Σ m(i) using minterm indices (binary value of row with A as MSB unless the variable order is specified; state your order on the paper).
  • For canonical POS, list rows where F = 0. For each such row, write maxterm with variables ORed, uncomplemented if row value is 0, complemented if 1. Multiply (AND) the maxterms. Write as Π M(i).

How to draw standard diagrams (describe exactly what to draw and label):

  • Gate symbols: For each gate you use, draw the standard shape, label inputs on the left (A, B, C…) and the output on the right as Y. For NAND/NOR/XNOR place a small bubble at the output. For NOT, draw a triangle pointing right with a bubble at the tip.
  • Realization from SOP: Draw an AND gate per product term, inputs taken (with inverters added where variables are complemented), then feed all AND outputs to a single multi-input OR gate to form the sum; label the final output Y. Show signal names on each interconnection.
  • Realization from POS: Draw an OR gate per sum term (add inverters where variables are complemented inside the sum), then feed all OR outputs into a single multi-input AND gate.
  • “Only-NAND” realization: Replace all inverters by NAND-tied inputs, all AND gates by NAND followed by inversion using a NAND, and all OR gates by input inversions followed by NAND. Clearly mark each replacement.

Notes on interpretation and assumptions used in exams:

  • Signal levels are ideal Boolean 0/1; timing, fan-out, and analog voltage levels belong to later topics (e.g., Electronic instruments, MOSFET basics, VLSI technology). Use ideal gates unless asked otherwise.
  • Variable ordering for minterm indices must be stated (e.g., A is MSB, then B, then C). Without stating order, indices can be ambiguous.

Formulas

  • Y = A + B — OR of A and B; logical disjunction.
  • Y = A′ — NOT (complement) of A.
  • Y = A ⊕ B = A′B + AB′ — XOR; 1 when A and B differ.
  • Y = A ⊙ B = (A ⊕ B)′ = AB + A′B′ — XNOR; 1 when A and B are equal.
  • A + 0 = A, A · 1 = A — Identity laws.
  • A + 1 = 1, A · 0 = 0 — Null (domination) laws.
  • A + A = A, A · A = A — Idempotent laws.
  • A + A′ = 1, A · A′ = 0 — Complementarity.
  • (A′)′ = A — Involution.
  • A + A · B = A — Absorption; and A · (A + B) = A.
  • (A · B)′ = A′ + B′ — De Morgan’s (product form).
  • (A + B)′ = A′ · B′ — De Morgan’s (sum form).
  • A · (B + C) = A · B + A · C — Distributive.
  • A + (B · C) = (A + B) · (A + C) — Distributive (dual form).
  • A · B + A′ · C + B · C = A · B + A′ · C — Consensus theorem.
  • F = Σ m(i…) — Canonical SOP over listed minterm indices; i are integers from 0 to 2^n−1 for n variables (unitless indexing).
  • F = Π M(i…) — Canonical POS over listed maxterm indices.

Worked examples

Example 1: Algebraic simplification and gate count Given: Simplify F(A,B,C) = A·B + A′·C + B·C and realize using only NAND gates. Steps:

  1. Use consensus theorem: Formula before numbers: A·B + A′·C + B·C = A·B + A′·C. So F = A·B + A′·C. (B·C is redundant.)
  2. Check if further reduction is possible: No direct absorption between A·B and A′·C; expression is minimal for many implementations.
  3. NAND-only realization procedure:
    • Each product term (A·B) is realized as NAND followed by inversion; but in NAND-only, perform: T1 = NAND(A,B) = (A·B)′.
    • For A′·C: First invert A using a NAND-inverter: A1 = NAND(A,A) = A′. Then T2 = NAND(A1,C) = (A′·C)′.
    • OR of two terms via De Morgan: F = ( (A·B) + (A′·C) ) = ( (A·B)′ · (A′·C)′ )′ = NAND( T1, T2 ).
    • Final: F = NAND( T1, T2 ), where T1 and T2 are as above, using only NAND gates. Answer: Draw four NAND gates: one for T1 with inputs A,B; one for A1 with both inputs tied to A; one for T2 with inputs A1 and C; and a final NAND combining T1 and T2 to give Y = F. Add clear labels.

Example 2: From truth table to canonical forms and minimal expression Given: Function F(A,B,C) defined by table rows (A,B,C → F): 000→0, 001→1, 010→1, 011→0, 100→1, 101→0, 110→1, 111→0. Assume variable order A (MSB), B, C (LSB). Steps:

  1. List rows where F = 1: binary ABC = 001 (1), 010 (2), 100 (4), 110 (6). Indices: 1, 2, 4, 6.
  2. Canonical SOP: F = Σ m(1,2,4,6) = A′B′C + A′BC′ + AB′C′ + ABC′.
  3. Canonical POS: Rows where F = 0: indices 0, 3, 5, 7. So F = Π M(0,3,5,7) = (A + B + C)·(A + B′ + C′)·(A′ + B + C′)·(A′ + B′ + C′).
  4. Simplify algebraically to a minimal SOP (one path): Starting from SOP terms, notice all four 1s have C′ in three minterms but not in 001. Try grouping by C:
    • Observe F can be expressed as F = A′B′C + C′(A′B + AB′ + A B). Now AB′ + AB = A(B′ + B) = A. So inside bracket: C′(A′B + A). Apply absorption: A + A′B = A + B (careful: A + A′B = (A + A′)(A + B) = 1·(A + B) = A + B). Thus C′(A + B). Finally F = A′B′C + C′(A + B).
  5. This is a reduced SOP with three product terms: F = A′B′C + A·C′ + B·C′. Draw two-input ANDs for A with C′ and B with C′, one three-input AND for A′B′C, then OR them. Final minimal expression (one acceptable form): F = A′B′C + A·C′ + B·C′. Bold the final line when you write your answer: Final: F = A′B′C + AC′ + BC′.

Example 3: Prove De Morgan and implement XOR from basic gates Part A (proof): Prove (A + B)′ = A′·B′ using truth table.

  1. List all combinations: (A,B) = (0,0),(0,1),(1,0),(1,1).
  2. Compute A + B and then complement to get (A + B)′.
  3. Compute A′ and B′ and then A′·B′.
  4. Compare columns: both are 1 only when A = 0 and B = 0; otherwise 0. Hence (A + B)′ = A′·B′. Part B (XOR realization): Y = A⊕B = A′B + AB′. Draw two NOT gates for A and B, two AND gates forming A′B and AB′, and an OR gate to sum them. Label Y = A⊕B.

Common mistakes

  • Forgetting variable order when writing Σm/ΠM, leading to wrong indices. Always state your order (e.g., A,B,C with A as MSB).
  • Dropping complements incorrectly: Misusing De Morgan (e.g., thinking (A + B)′ = A′ + B′, which is false).
  • Misapplying absorption: Writing A + AB = AB (wrong). Correct is A + A·B = A.
  • XOR confusions: Writing A⊕B = AB + A′B′ (that is XNOR). Remember XOR is 1 when inputs differ.
  • Implementation mismatch: Drawing an SOP circuit from a POS expression without converting properly.
  • NAND/NOR universality errors: Forgetting that OR using NAND requires inverting inputs first: A + B = (A′·B′)′.
  • Omitting inverters in canonical terms: In a minterm, every variable must appear once; leaving a variable out breaks canonicity.

For your exam

  • Laws/theorems: State commutative, associative, distributive, identity, null, idempotent, complementarity, involution, absorption, De Morgan, and consensus theorem. If asked, provide step-by-step derivations using accepted identities or a truth table proof.
  • Simplification: Reduce a given Boolean expression using algebra. Show every step, cite the law used in the margin (e.g., “by absorption”). Box the final minimal expression.
  • Canonical forms: From a truth table, write Σm and ΠM. State variable order. Optionally show conversion between SOP and POS using De Morgan and complements.
  • Realization: Draw gate-level circuits for SOP/POS and using only NAND or only NOR. Neat, labeled diagrams: inputs left, outputs right, inversion bubbles shown.
  • XOR/XNOR design: From definition Y = A⊕B = A′B + AB′, draw the circuit; give the truth table.
  • Short notes: Universality of NAND/NOR, duality principle, consensus theorem (with an example), difference between SOP and POS.

A full-marks answer is neat, uses correct symbols, states assumptions (variable order), cites theorems by name, carries the derivation step-by-step, and includes a clearly labeled diagram.

Quick check

  1. Write the dual of the identity A + 0 = A and state whether it is valid.
  2. Give canonical SOP for F(A,B) that is 1 only for A B = 10 and 11 (A is MSB).
  3. Realize OR using only NAND gates in one line using De Morgan’s theorem. Answers: (1) Dual: A · 1 = A; valid. (2) F = Σ m(2,3) = A B′ + A B. (3) A + B = (A′ · B′)′.

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

Stuck on something here?