Constructing Logical Expressions – Digital Logic Fundamentals (Senior 4 ICT) | Ganzaa

Digital Logic Fundamentals

Lessons

Senior 4 · ICT

Digital Logic Fundamentals

5 lessons

Lesson 4 of 5

Constructing Logical Expressions

25 min

Three prefects, one decision

A school's disciplinary committee has three prefects. Each presses a button: 1 for "yes", 0 for "no". A light on the patron's desk must come on when the majority, at least two of the three, say yes. Nobody gives you an expression for the light; you are given a rule in words. This lesson turns rules like this into a truth table and then into a Boolean expression that can be built as a circuit.

Definition

Minterm: an AND of all the input variables, each written plain or barred, that is 1 in exactly one row of the truth table. Example: $A \cdot \overline{B} \cdot C$ is 1 only in the row $A = 1, B = 0, C = 1$ .

Sum of products (SOP): an OR of AND terms, such as $\overline{A}B + A\overline{B}$ .

Maxterm: an OR of all the input variables, each plain or barred, that is 0 in exactly one row. Example: $A + \overline{B} + C$ is 0 only in the row $A = 0, B = 1, C = 0$ .

Product of sums (POS): an AND of OR terms, such as $(A + B)(\overline{A} + \overline{B})$ .

Method 1: sum of products, from the 1s

Find every row where the output is 1.
For each such row write a minterm: the variable plain if it is 1, barred if it is 0.
OR the minterms together.

For XOR, the output is 1 in rows $(A, B) = (0, 1)$ and $(1, 0)$ . Their minterms are $\overline{A} \cdot B$ and $A \cdot \overline{B}$ , so $Y = \overline{A} \cdot B + A \cdot \overline{B}$ Every SOP expression can be built as a two-level circuit: a layer of AND gates, one per term, all feeding one OR gate (plus NOT gates for the barred inputs).

Worked example 1: the majority voter

Inputs: $A, B, C$ (1 = yes). Output: $Y = 1$ when at least two inputs are 1.

A	B	C	Y	Minterm (rows with Y = 1)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1	$\overline{A}BC$
1	0	0	0
1	0	1	1	$A\overline{B}C$
1	1	0	1	$AB\overline{C}$
1	1	1	1	$A B C$

$Y = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC$

Built directly, this needs 3 NOT gates, 4 three-input AND gates and a four-input OR gate. In lesson 5 you will reduce it to $Y = A B + B C + A C$ .

python

# Build the sum of products of the majority voter automatically.
# A' means NOT A (a common way to type a bar).
names = ["A", "B", "C"]
terms = []
for A in (0, 1):
    for B in (0, 1):
        for C in (0, 1):
            Y = int(A + B + C >= 2)          # at least two yes votes
            if Y == 1:
                term = ""
                for name, value in zip(names, (A, B, C)):
                    term += name if value == 1 else name + "'"
                terms.append(term)
print("Y =", " + ".join(terms))

Code Explanation

Press Run. The program goes through the 8 rows, keeps the rows where $ Y = 1 $, and writes a minterm for each: plain for 1, primed (A') for 0. It prints Y = A'BC + AB'C + ABC' + ABC, the same as worked example 1. Change the rule on the Y = line, for example to A + B + C == 1 ("exactly one yes"), and run it again.

Method 2: product of sums, from the 0s

Find every row where the output is 0.
For each such row write a maxterm: the variable plain if it is 0, barred if it is 1.
AND the maxterms together.

POS is shorter when the output has few 0s. Suppose $Y = 0$ only in rows $(A, B, C) = (0, 0, 0)$ and $(0, 1, 0)$ . Then $Y = (A + B + C)(A + \overline{B} + C)$ Each bracket is 0 in exactly one of those rows, and the AND is 0 if any bracket is 0. (Here $Y$ is 0 exactly when $A = 0$ and $C = 0$ , so it simplifies to $A + C$ .)

Worked example 2: straight from words

A security light ( $L$ ) must come on when it is dark ( $D = 1$ ) and either a motion sensor detects movement ( $M = 1$ ) or the manual switch is on ( $S = 1$ ).

Translate the words: "and" → AND, "either … or" → OR, and the brackets follow the meaning: $L = D \cdot (M + S)$

Check with the truth table method: $L = 1$ in rows $(D, M, S) = (1, 0, 1), (1, 1, 0), (1, 1, 1)$ , giving $L = D\overline{M}S + DM\overline{S} + DMS$ . Factorising, $D(\overline{M}S + M\overline{S} + MS) = D(M + S)$ , since the bracket is 1 whenever $M$ or $S$ is 1. Both methods agree, and the word method gave the shorter answer at once.

Computing Tutor: Deriving a Boolean expression from a truth table (sum of products). Watch how each row with output 1 becomes one AND term, then repeat the method on the majority-voter table above.

Warning

Plain for 1 in SOP, plain for 0 in POS. The rules are opposite. A minterm is written so that it equals 1 in its row; a maxterm so that it equals 0 in its row. Test one term in its own row to be sure.

Define every variable first. " $S$ = seat belt" is not enough: say whether $S = 1$ means fastened or unfastened, or the expression will be the wrong way round.

Tip

Count before you choose. If the output column has fewer 1s than 0s, write the SOP; if it has fewer 0s, write the POS. Fewer terms means fewer gates before you even start simplifying.

✦

Practice

Write the minterm for the row $A = 1, B = 0, C = 1$ .
Write the maxterm for the row $A = 0, B = 1, C = 1$ .
A function of $A, B, C$ is 1 only in rows 001, 011 and 110. Write its SOP expression.
A function of $A, B$ is 0 only in rows 00 and 11. Write its POS expression and name the gate.
A school gate opens ( $G = 1$ ) when the guard presses a button ( $P$ ) or a staff card is read ( $K$ ), but never while the fire alarm ( $F$ ) is sounding. Write $G$ .
Write the SOP for "exactly one of $A, B, C$ is 1".
How many AND gates and how many NOT gates does the unsimplified majority-voter SOP need? (Count one NOT per input that is ever barred.)
A function of 3 inputs is 1 in seven rows and 0 only in row 100. Which form would you write, and what is it? Explain your choice.

Show answersHide answers

$A\overline{B}C$ .
$A + \overline{B} + \overline{C}$ .
$\overline{A}\,\overline{B}C + \overline{A}BC + AB\overline{C}$ .
$(A + B)(\overline{A} + \overline{B})$ : it is 1 only when the inputs differ, so it is XOR.
$G = (P + K) \cdot \overline{F}$ .
$\overline{A}\,\overline{B}C + \overline{A}B\overline{C} + A\overline{B}\,\overline{C}$ .
4 AND gates (one per minterm) and 3 NOT gates (each of $A, B, C$ appears barred once), plus one OR gate.
POS, because there is only one 0: one maxterm. Row 100 gives $Y = \overline{A} + B + C$ . The SOP would need seven minterms.

Quick check

Which minterm is 1 only in the row A = 0, B = 1, C = 1?

Key points

SOP: one minterm per row where the output is 1 (plain for 1, barred for 0), joined by OR; it builds as a two-level AND–OR circuit.
POS: one maxterm per row where the output is 0 (plain for 0, barred for 1), joined by AND.
Choose SOP when the output has few 1s and POS when it has few 0s.
A rule in words can be translated directly: "and" → AND, "or" → OR, "not" → bar, with brackets to keep the meaning.

Sources and credits

Canonical normal form and Majority function, Wikipedia contributors, Wikipedia, licensed under CC BY-SA 4.0. Adapted by Ganzaa.
Video: Deriving a Boolean expression from a truth table (Sum of products), Computing Tutor, embedded from YouTube.
The scenarios, circuit diagram, truth tables, code, worked examples and practice items were written by Ganzaa.

This lesson adapts CC BY-SA material and is shared under CC BY-SA 4.0.

1Three prefects, one decision

2Method 1: sum of products, from the 1s

3Method 2: product of sums, from the 0s

Three prefects, one decision

Method 1: sum of products, from the 1s

Method 2: product of sums, from the 0s