Canonical Expressions

Abstract

For SOP:
Look at the rows where the output is 1. Then add the conjunctions of these rows.

For POS:
Look at all the rows where the output is 1. Then multiply all the disjunctions of these rows.

Canonical Sum of Products

Definition

Given a truth table, it is always possible to write a logic expression for the function by taking a logical OR of the minterms for which the function has a value of 1. This representation of a function is a logical sum of minterms, and is called the canonical sum of products (SOP).

Also see: disjunctive normal form

Example


0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

So we have:

Remark

The SOP is not necessarily the lowest cost implementation of the function

We can lower the cost with some algebraic manipulation. Observe that the first and third term have and second and fourth term have , so we can simplify:

which is not canonical SOP, but shorter nonetheless.

NAND NAND Realization

Any SOP implementation can be re-written using only NAND gates.

Example

Canonical Product of Sums

Definition

Given a truth table, it is always possible to write a logic expression for the function by taking a logical AND of the maxterms for which the function has a value of 0. This representation of a function is a logical sum of maxterms, and is called the canonical sum of products (SOP).

Also see: conjunctive normal form

Example


0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

So we have:

to simplify, observe that , so

NOR NOR Realization

Any POS implementation can be re-written using only NOR gates.

Example