A set of product terms covers a function when every row where F = 1 is made 1 by at least one of the terms, and none of them is 1 on a row where F = 0. In other words, it is a correct SOP for F.
Finding a minimal SOP is a covering problem, solved in two stages:
- Find all the prime implicants. Only primes need to be considered, because any non-prime term can be swapped for a bigger prime that covers at least as much.
- Choose the cheapest set of primes that covers every 1.
For the second stage:
- List, for each 1 of F, the primes that cover it.
- A 1 covered by only one prime forces that prime into the cover. It is an essential prime implicant.
- Remove the 1s already covered, then add the cheapest primes for whatever is left.
Primes that are left out are redundant. Sometimes there is a tie, and the function has more than one minimal SOP.
Overlap is fine: covering a 1 twice costs nothing. What costs is an extra term.
| A\BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1m0 | 0m1 | 0m3 | 0m2 |
| 1 | 1m4 | 1m5 | 1m7 | 0m6 |