Boolean Algebra: Standard Expression Formats

Dr. Flora Runji

April 7, 2025

1 Introduction to Standard Forms

Boolean algebra provides a formalized way of representing and manipulating logical expressions.
All Boolean expressions, regardless of their form, can be converted into either of two standard forms:
• The Sum-of-Products (SOP) form – an OR of multiple AND terms
• The Product-of-Sums (POS) form – an AND of multiple OR terms
Standardization makes the evaluation, simplification, and implementation of Boolean expressions much more
systematic and easier. Standardized Boolean expressions are essential for:
• Systematic analysis of logic circuits
• Efficient hardware implementation and optimization
• Simplification and minimization of Boolean expressions
• Consistent documentation across engineering teams
• Use in digital circuit synthesis and design
Definition 1.1. A literal is a Boolean variable or its complement (negation). A minterm of n Boolean
variables x1 , x2 , . . . , xn is a Boolean product (AND operation) of n literals, where each literal corresponds
to either the variable itself or its complement. Formally, a minterm is an expression of the form y1 y2 · · · yn ,
where each yi is either xi or xi .
Examples:
• For two variables x1 and x2 , one minterm is x1 ∧ x2 (or simply x1 x2 ).
• For three variables x1 , x2 , x3 , a minterm is x1 ∧ x2 ∧ x3 (or x1 x2 x3 ).
• The expression xyz is a minterm for variables x, y, z.
Each minterm evaluates to true (1) for exactly one combination of variable assignments, making them
fundamental in constructing canonical Boolean expressions.
A minterm is a special case of a product term where:
• The term contains all variables of the Boolean function.
• Each variable appears exactly once, either in complemented or uncomplemented form.
• Minterms are canonical forms used in sum-of-products (SOP) expansions, where each minterm corre-
sponds to one unique truth table row.
Thus, a minterm is a maximal product term that uniquely represents one row of a truth table.
In summary,
A minterm is a product term that contains each of n variables as factors, either in complemented or
uncomplemented form.
A maxterm is a sum term that contains each of n variables as factors, either in complemented or
uncomplemented form.

1
Definition 1.2. A product term is any Boolean expression consisting of literals (a variable or its com-
plement, e.g., xi or xi ) that are AND-ed together. It may contain fewer literals than the total number of
variables in the Boolean function.
Product Term Examples (may omit variables):
• x (single literal, 1-variable function).
• xy (2-literals, 2-variable function).
• yz (2-literals, 3-variable function; x is missing).

2 Sum-of-Products (SOP) Form

A sum-of-products (SOP) expression is a canonical representation of a Boolean function, structured as
a logical OR (sum) of one or more product (AND) terms. Each product term consists of literals (a variable
or its complement) combined with AND operations.

2.1 Structure and Characteristics

• Form: An SOP expression has the form:
F (x1 , . . . , xn ) = P1 + P2 + · · · + Pk
where each Pi is a product term (e.g., xyz), and + denotes the OR operation.
• Circuit Implementation:
– AND-OR Structure:
∗ First, AND gates combine inputs (either normal or negated)
∗ Then, all AND outputs connect to one final OR gate
– Simple Example:
∗ For F = xy + yz:
· One AND gate computes xy
· Another AND gate computes yz
· An OR gate combines both results
– Why It Matters:
∗ All inputs take exactly 2 gate delays to reach output
∗ Same delay for all inputs = predictable timing
Example 2.1. Consider the following SOP expression for a function F (x, y, z):
F (x, y, z) = xyz + xz + xyz
Here:
• xyz, xz, and xyz are product terms.
• The ”+” symbols represent OR operations.

2.2 Key Properties

• Canonical SOP: A special case where every product term is a minterm (i.e., covers all variables).
For example:
F (x, y) = xy + xy + xy
• Non-Canonical SOP: Product terms may omit literals (e.g., x + yz).
• Two-Level Logic: The AND-OR structure inherently limits logic depth, simplifying timing analysis.

2
3 Product-of-Sums (POS) Form
A product-of-sums (POS) expression is a canonical representation of a Boolean function, structured as
a logical AND (product) of one or more sum (OR) terms. Each sum term consists of literals combined
with OR operations.

3.1 Structure and Characteristics

• Formal Definition:
k
Y
F (x1 , . . . , xn ) = Si = S1 · S2 · . . . · Sk
i=1
where each sum term Si = (y1 + y2 + · · · + ym ) contains literals yj ∈ {xj , xj }.
• Circuit Implementation:
– First-level OR gates compute each sum term
– Second-level AND gate combines all OR outputs
– Maximum gate delay: 2 levels (ignoring inverters)

3.2 Example
For variables A, B, C, D, a valid POS expression:
F (A, B, C, D) = (A + B + C + D)(A + B + D)(C + D)(A + D)
• Each parenthesis represents a sum term
• The implied AND operation between terms is denoted by juxtaposition

3.3 Key Properties

• Canonical POS (Maxterm expansion):
F (x, y, z) = (x + y + z)(x + y + z)(x + y + z)

• Non-Canonical POS (May omit variables):

(A + B)(C + D)

3.4 Invalid Cases

The following is not a valid POS expression:
(A + B) · (C + D) (Invalid complemented sum term)
Valid alternative for the same logic:
(A · B) · (C + D) (Converted to AND terms)
Example 3.1. Find a sum of products (SOP) and a product of sums (POS) for the truth table below.
Output
A B C Z
1 1 1 1
1 1 0 1
1 0 1 0
1 0 0 0
0 1 1 0
0 1 0 1
0 0 1 0
0 0 0 1

3
Solution:
Sum of Products: To find a sum of products from a truth table:
• Identify the rows having output 1.
• For each such row, write the variable if the variable input is 1 or write the complement of the variable
if the variable input is 0, then multiply the variables forming a term.
• add all such terms.
Product of Sums To find a product of sums from a truth table:
• identify the rows having output 0.

• For each such row, write the variable if the variable input is 0 or write the complement of the variable
if the variable input is 1, then add the variables forming a sum
• Multiply all such sums.
Sum of Products (SOP):

i) Identify rows where the output Z = 1:

Rows: (A, B, C) = (1, 1, 1), (1, 1, 0), (0, 1, 0), (0, 0, 0).

ii) Write a product term for each row:

(1, 1, 1) : A · B · C,
(1, 1, 0) : A · B · C,
(0, 1, 0) : A · B · C,
(0, 0, 0) : A · B · C.

iii) Combine the terms with +:

Z = A · B · C + A · B · C + A · B · C + A · B · C.

Product of Sums (POS):

i) Identify rows where the output Z = 0:

Rows: (A, B, C) = (1, 0, 1), (1, 0, 0), (0, 1, 1), (0, 0, 1).
ii) Write a sum term for each row:

(1, 0, 1) : (A + B + C),
(1, 0, 0) : (A + B + C),
(0, 1, 1) : (A + B + C),
(0, 0, 1) : (A + B + C).

iii) Combine the terms with ·:

Z = (A + B + C) · (A + B + C) · (A + B + C) · (A + B + C).

Example 3.2. Consider the following truth table.

4
Output
A B C Y
1 1 1 0
1 1 0 0
1 0 1 1
1 0 0 0
0 1 1 0
0 1 0 0
0 0 1 1
0 0 0 0

i) Determine and simplify the logic expression for the output Y above.
Solution:
There are two rows with output 1’s and their corresponding binary values are 001 and 101 which
correspond to product terms ĀB̄C and AB̄C respectively.
The resulting expression for the output is
Y = ĀB̄C + AB̄C = (Ā + A)B̄C = 1.B̄C = B̄C.
ii) Sketch the logic circuit for the simplified expression.

Example 3.3. Derive the truth table for the Sum Of Product expressions
x̄ȳz̄ + x̄ȳz + x̄yz̄ + x̄yz + xyz
Solution:
x y z F Minterms
1 1 1 1 xyz
1 1 0 0
1 0 1 0
1 0 0 0
0 1 1 1 x̄yz
0 1 0 1 x̄yz̄
0 0 1 1 x̄ȳz
0 0 0 1 x̄ȳz̄

Example 3.4. Simplify the boolean expression P̄ Q̄R̄ + P̄ Q̄R + P̄ QR̄ + P̄ QR + P QR.
Solution:

P̄ Q̄R̄ + P̄ Q̄R + P̄ QR̄ + P̄ QR + P QR = P̄ Q̄(R̄ + R) + P̄ Q(R̄ + R) + P QR

= P̄ Q̄(1) + P̄ Q(1) + P QR = P̄ Q̄ + P̄ Q + P QR
= P̄ (Q̄ + Q) + P QR
= P̄ (1) + P QR
= P̄ + P QR