Boolean Logic

16 min read | Beginner Level

What You'll Learn

• The basic logic gates, their truth tables, and how to turn a word problem into an expression
• The laws of Boolean algebra, including absorption, consensus, and duality, and how to use them to simplify logic
• Minterms, maxterms, and how to move between sum-of-products and product-of-sums forms
• How De Morgan's theorem shapes the transistor networks inside a CMOS gate

Boolean Values and Operators

Boolean logic works with only two values: 0 (false) and 1 (true). In a digital circuit these are two voltage ranges: a voltage near ground reads as 0, and a voltage near the supply reads as 1. Every digital function, however large, is built from three basic operations:

The operators have a fixed precedence, just like multiplication before addition in ordinary arithmetic:

Precedence:  NOT  first,  then AND,  then OR

  A + B · C'    means   A + (B · (C'))
  (A + B) · C   needs the brackets to force the OR first
  (AB)'         is NOT of the product;   A'B'  is the product of two NOTs

Logic Gates and Their Truth Tables

A logic gate is a circuit that computes one Boolean operation. A truth table lists the output for every combination of inputs: n inputs give 2ⁿ rows. Besides AND, OR, and NOT, four combined gates are used everywhere:

Two quick ways to read the table: XOR is 1 when the inputs differ, and XNOR is 1 when they are equal, which makes XNOR a 1-bit equality checker. NAND and NOR are simply AND and OR with the output inverted.

From Words to an Expression to a Circuit

Take the voting rule from the opening: output F is 1 when at least two of the three inputs A, B, C are 1. The method works for any word problem:

Step 1  Write the truth table.        (8 rows for 3 inputs)
Step 2  Mark every row where F = 1.   (rows 011, 101, 110, 111)
Step 3  Write one AND term per marked row, using A for a 1 and A' for a 0:
          011 -> A'BC     101 -> AB'C     110 -> ABC'     111 -> ABC
Step 4  OR the terms together:
          F = A'BC + AB'C + ABC' + ABC
Step 5  Simplify (shown in the simplification section):
          F = AB + AC + BC

The Laws of Boolean Algebra

Boolean algebra has its own rules. Some look like ordinary algebra, and some, such as A + A = A, do not. Every law comes in a pair: swap AND with OR and 0 with 1, and you get its dual, which is also true. This is the duality principle.

Any law can be proved by perfect induction: check both sides on every row of the truth table. For the redundant-literal law A + A'B = A + B:

In words: if A is already 1, the OR is already 1, so the A' in the second term adds nothing. The consensus law says something similar: in AB + A'C + BC, the term BC is only 1 when B = C = 1, and then either AB or A'C is already 1, depending on A. BC is redundant.

Simplifying Expressions Step by Step

Simplification removes terms and literals, and every literal removed is a gate input, and two transistors, that never get built. Three worked examples:

Example 1: the majority function
  F = A'BC + AB'C + ABC' + ABC
    = A'BC + AB'C + ABC' + ABC + ABC + ABC     idempotent: ABC = ABC + ABC + ABC
    = (A'+A)BC + A(B'+B)C + AB(C'+C)            group each term with one copy of ABC
    = BC + AC + AB                              complement: X' + X = 1, identity: 1 . Y = Y

Example 2: removing a consensus term
  G = AB + A'C + BC
    = AB + A'C                                  consensus: BC is covered by AB or A'C

Example 3: complementing with De Morgan
  H = (AB + C)'
    = (AB)' . C'                                De Morgan on the OR
    = (A' + B') . C'                            De Morgan on the AND

What the majority simplification saves in hardware, built as two-level NAND logic (an n-input NAND uses 2n transistors, an inverter uses 2):

What comes out of synthesis: you never have to do this by hand in a real design. Synthesis tools apply the same laws automatically: they remove redundant terms, share common sub-expressions, and propagate constants (a signal tied to 0 makes every AND it feeds 0, by the null law, so that logic disappears). The majority function above typically comes out as a NAND2/NAND3 network or a single complex AND-OR-INVERT cell plus an inverter, whichever meets timing with less area.

Minterms, Maxterms, and Canonical Forms

A product term is an AND of literals, such as AB or A'C. A minterm is a special product term that contains every variable exactly once, such as A'BC. Each minterm is 1 on exactly one row of the truth table. A maxterm is an OR of every variable, and is 0 on exactly one row.

Note the opposite conventions: in a minterm, a 0 in the row becomes a complemented variable; in a maxterm, a 1 becomes a complemented variable. Each one is built to match exactly its own row.

• Sum of products (SOP) is an OR of product terms, such as AB + AC + BC. The canonical SOP uses only minterms, one per row where F = 1.
• Product of sums (POS) is an AND of sum terms, such as (A + B)(A + C). The canonical POS uses only maxterms, one per row where F = 0.

Converting between the two canonical forms needs no algebra: just list the rows that are missing.

Majority function, rows where F = 1: 3, 5, 6, 7
  Canonical SOP:  F = sum of m(3, 5, 6, 7)  = A'BC + AB'C + ABC' + ABC

Rows where F = 0 are all the others: 0, 1, 2, 4
  Canonical POS:  F = product of M(0, 1, 2, 4)
                    = (A + B + C)(A + B + C')(A + B' + C)(A' + B + C)

Use whichever form needs fewer terms: a function that is 1 on most rows has a short POS, and a function that is 1 on few rows has a short SOP.

De Morgan's Theorem Inside a CMOS Gate

De Morgan's theorem is not just an algebra trick: it is how every static CMOS gate is designed. A CMOS gate has two transistor networks:

• The pull-down network of NMOS transistors connects the output to ground. An NMOS conducts when its input is 1. Transistors in series conduct only if all are on (AND); transistors in parallel conduct if any is on (OR).
• The pull-up network of PMOS transistors connects the output to the supply. A PMOS conducts when its input is 0, so it naturally works with complemented inputs.

For Y = (AB + C)', the pull-down must conduct when AB + C = 1: A and B in series, in parallel with C. The pull-up must conduct exactly when the output is 1, that is, when (AB + C)' = 1. De Morgan's theorem turns this into (A' + B')C', which tells you the pull-up structure directly: A and B in parallel, in series with C.

Rule that falls out of De Morgan's theorem:
  pull-down network:   series   <->   parallel   :pull-up network
                       parallel <->   series
  (the pull-up is the dual of the pull-down, so exactly one of them conducts)

This gate is a single AOI21 cell (AND-OR-INVERT) of 6 transistors, with one stage of delay. Building the same function from separate gates, an AND2 (6 transistors) driving a NOR2 (4 transistors), takes 10 transistors and two stages. Synthesis tools look for exactly this pattern.

Common Mistakes

1. A B C | F
   0 0 0 | 0
   0 0 1 | 1   m1
   0 1 0 | 0
   0 1 1 | 1   m3
   1 0 0 | 0
   1 0 1 | 1   m5
   1 1 0 | 1   m6
   1 1 1 | 1   m7

   F = sum of m(1, 3, 5, 6, 7) = A'B'C + A'BC + AB'C + ABC' + ABC

2. A'B'C + A'BC = A'C(B' + B) = A'C        distributive, complement, identity
   AB'C  + ABC  = AC(B' + B)  = AC         same laws
   A'C + AC     = C(A' + A)   = C          same laws
   F = C + ABC'
     = C + AB                              redundant literal: X + X'Y = X + Y, with X = C

3. Rows where F = 0: 0, 2, 4
   Canonical POS:  F = (A + B + C)(A + B' + C)(A' + B + C)
   Simplified POS: F = (A + C)(B + C)      distributive: C + AB = (C + A)(C + B)

4. F = C + AB = ((AB)' . C')'              De Morgan
     = (A NAND B) NAND (C NAND C)
   3 NAND gates: one for A NAND B, one as an inverter for C, one to combine.