Electrical Engineering › Section S · Logic gates and Boolean algebra › Topic S.4

Boolean simplification, standard forms, and truth tables

Any gate circuit can be written as a Boolean expression, simplified with the laws of Boolean algebra and rebuilt with fewer gates. This topic shows how to analyse a circuit, simplify its expression, put it into the standard sum-of-products and product-of-sums forms, and move freely between expressions and truth tables.

From circuit to expression

To analyse a combinational circuit, start at the inputs and write the output of each gate in terms of its inputs, working towards the final output. Each gate adds one operation: an AND multiplies its inputs, an OR adds them, and an inverter or output bubble puts a bar over everything that gate produces. Put brackets around any sum that feeds an AND, so the order of operations stays clear. The result is one expression for the whole circuit, which gives its truth table or a smaller equivalent.

Worked example: analysing a circuit

Gate 1 ANDs inputs C and D. Gate 2 is a NOR whose inputs are B and the output of gate 1. Gate 3 ANDs input A with the output of gate 2, giving X. Find X and its truth table. 1. Gate 1 gives \(CD\). 2. Gate 2 gives \(\overline{B + CD}\). 3. Gate 3 gives \(X = A\overline{B + CD}\). 4. For X = 1, A must be 1 and \(B + CD\) must be 0, so B = 0 and CD = 0. 5. With A = 1 and B = 0, the pairs CD = 00, 01 and 10 work and 11 does not. So X = 1 for ABCD = 1000, 1001 and 1010 only, and is 0 in the other 13 of the 16 rows.

Why simplify

Expressions with the same truth table behave identically but may need very different hardware. Fewer terms and literals mean fewer gates and gate inputs, so less power, lower cost and usually less delay. Algebraic simplification uses the laws and rules of "Boolean operations, laws, and DeMorgan's theorems": multiply out brackets, collect terms that differ in only one variable, then apply absorption and \(A + \overline{A}B = A + B\). There is no fixed recipe, so check the final answer against the original with a truth table.

Worked example: algebraic simplification

Simplify \(X = \overline{A}BC + AB\overline{C} + ABC\). 1. Since \(ABC + ABC = ABC\), write ABC twice: \(\overline{A}BC + ABC + AB\overline{C} + ABC\). 2. The first pair shares BC: \(BC(\overline{A} + A) = BC\). 3. The second pair shares AB: \(AB(\overline{C} + C) = AB\). 4. So \(X = BC + AB = B(A + C)\). Check: both forms are 1 for ABC = 011, 110 and 111 only. The original needs three 3-input ANDs, a 3-input OR and two inverters; the result needs one 2-input OR and one 2-input AND.

Sum-of-products form

An expression in sum-of-products (SOP) form is an OR of product terms, such as \(AB + \overline{B}CD + \overline{A}\), with no bar covering more than one variable. Its domain is the set of variables it uses. SOP maps straight onto hardware: one AND gate per product term, all feeding one OR gate, the AND-OR form. The same circuit can be built entirely from NAND gates, a NAND per term feeding a NAND: by DeMorgan, \(\overline{\overline{X}\,\overline{Y}} = X + Y\), so NAND-NAND equals AND-OR. Any expression can be converted to SOP by multiplying out and applying DeMorgan's theorems: an alarm that sounds when armed, A, and a door is open, D, or motion is sensed, M, is \(A(D + M) = AD + AM\).

Standard SOP and minterms

In standard SOP form every product term contains every variable of the domain, either plain or complemented. Such a term is a minterm, equal to 1 for exactly one input combination: write 1 for a plain variable and 0 for a complemented one, so \(A\overline{B}C\overline{D}\) is 1 only for 1010. Minterms are numbered by that binary value, \(m_{10}\) here. To make a term standard, multiply it by \((D + \overline{D})\) for each missing variable D and expand. With domain A, B, C, \(\overline{A}B + C\) expands to minterms 2 and 3 from the first term and 1, 3, 5, 7 from the second, so it equals \(\sum m(1, 2, 3, 5, 7)\).

Product-of-sums form

The product-of-sums (POS) form is an AND of sum terms, such as \((A + \overline{B})(B + C + D)\). It maps onto an OR-AND circuit: one OR gate per sum term, feeding one AND gate. In standard POS every sum term contains every variable, and such a term is a maxterm, equal to 0 for exactly one input combination. Here the rule flips: write 0 for a plain variable and 1 for a complemented one, so \(A + \overline{B} + C\) is 0 only for 010, and it is maxterm \(M_2\). To make a sum term standard, add \(D\overline{D}\), which is 0, for each missing variable and expand with \((A + B)(A + C) = A + BC\).

Converting between SOP and POS

In n variables there are \(2^n\) combinations. A standard SOP lists the combinations that give 1; a standard POS lists those that give 0. So the minterm numbers missing from a standard SOP are exactly the maxterm numbers of the equivalent standard POS. For three variables,

\textstyle\sum m(1, 3, 6, 7) = \prod M(0, 2, 4, 5)

Together the two lists use each of the eight numbers once. Choose whichever list is shorter.

Expressions and truth tables

To build a truth table from a standard SOP, put a 1 in the row of each minterm and 0 everywhere else; from a standard POS, put a 0 in the row of each maxterm and 1 elsewhere. A non-standard expression can be evaluated row by row, or expanded first. Going the other way, from a truth table, gives the standard SOP by writing one minterm for each row with output 1, and the standard POS by writing one maxterm for each row with output 0. A function that is 1 when exactly one of A and B is 1 has 1 rows 01 and 10, so it is \(\overline{A}B + A\overline{B}\), the XOR. Either standard form completely describes the function and, for a given domain, is unique apart from term order.

Worked example: truth table to standard forms

A function F of A, B, C is 1 for rows 001, 011, 110 and 111. Write its standard SOP and POS, then simplify. 1. Minterms: \(\overline{A}\,\overline{B}C + \overline{A}BC + AB\overline{C} + ABC\), that is \(\sum m(1, 3, 6, 7)\). 2. The 0 rows are 000, 010, 100 and 101, giving

\begin{aligned} F = {} &(A + B + C)(A + \overline{B} + C) \\ &(\overline{A} + B + C)(\overline{A} + B + \overline{C}) \end{aligned}

3. Simplify the SOP: the first two terms share \(\overline{A}C\) and the last two share AB, so \(F = \overline{A}C + AB\). Check: \(\overline{A}C\) covers 001 and 011, AB covers 110 and 111, and no other row.

Common mistakes to avoid

First, losing brackets when writing a circuit's expression: \(A\overline{B + CD}\) is not \(A\overline{B} + CD\). Second, writing a maxterm with the minterm rule; for POS a 0 in the row means the plain variable. Third, calling \(\overline{AB} + C\) SOP; a bar over a product must be removed with DeMorgan first. Fourth, forgetting a variable when making a term standard, so a supposed minterm covers two rows. Fifth, assuming a simplification is right without checking it on a truth table.

Key takeaways

Analyse a circuit gate by gate, keeping brackets, to get its expression, then evaluate it row by row for the truth table. Simplify with the Boolean laws and rules, and confirm with a truth table. SOP is an OR of products, built as AND-OR or NAND-NAND; POS is an AND of sums, built as OR-AND. In standard form every term has every variable: minterms are 1 for one row (plain = 1), maxterms are 0 for one row (plain = 0). Standard SOP lists the 1 rows, standard POS the 0 rows, and the two lists of numbers are complementary.

Flashcards

Flashcard

Circuit analysis

Write each gate's output from the inputs forward

Keep brackets around sums feeding ANDs.

Test your understanding

Question 1 of 5

Inputs B and C feed an AND gate; its output and input A feed an OR gate; the OR output then passes through an inverter. What is the output expression?

Question 2 of 5

For which input combination does the minterm A·B'·C·D' equal 1?

Question 3 of 5

A function of A, B and C is 1 only for ABC = 011 and ABC = 110. What is its standard SOP?

Question 4 of 5

A function of A, B and C is 0 only for ABC = 010. Which maxterm is its standard POS?

Question 5 of 5

In the domain A, B, C, how many minterms are there in the standard SOP form of A + B'·C?

← Previous topicNext topic →