Simplify into sum of products

Question

Simplifying expression into SOP or POS expressions

How do i go from 5,9,13 to p,q,r,s? I have the answer but unsure how to derive it.

Answer:

G(p,q,r,s) =  M(5, 9, 13)
    = (p+q'+r+s')∙(p' + q + r + s')∙(p'+q'+r+s') [distributive]
    = ( ( q' + r + s' ) + (p∙p') ) ∙ ( p' + q + r + s' ) [complement]
    = ( ( q' + r + s' ) + 0 ) ∙ ( p' + q + r + s' ) [identity]
    = (q' + r + s' ) ∙ ( p' + q + r + s' ) [distributive]
    = ( q' ∙ (p' + q) ) + ( r + s' )     [absorption]
    = p'∙q' + r + s'

Answer 1

Assuming that $M(5, 9, 13)$ stands for the following truth-table:

    p q r s  G
 0: 0 0 0 0  0
 1: 0 0 0 1  0
 2: 0 0 1 0  0
 3: 0 0 1 1  0 
 4: 0 1 0 0  0
 5: 0 1 0 1  1
 6: 0 1 1 0  0
 7: 0 1 1 1  0
 8: 1 0 0 0  0
 9: 1 0 0 1  1
10: 1 0 1 0  0
11: 1 0 1 1  0
12: 1 1 0 0  0
13: 1 1 0 1  1
14: 1 1 1 0  0
15: 1 1 1 1  0

It might be, that $M()$ stands for a list of maxterms. In this case, the output values have to be inverted.

To find a simplified sum-of-products, draw the following Karnaugh-Veitch map:

                 rs
          00   01   11   10
        +----+----+----+----+
     00 |  0 |  0 |  0 |  0 |
        +----+----+----+----+
     01 |  0 |  1 |  0 |  0 |
pq      +----+----+----+----+
     11 |  0 |  1 |  0 |  0 |
        +----+----+----+----+
     10 |  0 |  1 |  0 |  0 |
        +----+----+----+----+

Notice that three of the sixteen map cells are set to $1$, corresponding to minterms $5$, $9$ and $13$. The block of three adjacent $1$ cells can be covered by two prime implicants. This leads to a sum of two products:

$$G(p,q,r,s) = (q \land \neg r \land s) \lor (p \land \neg r \land s)$$

To find a simplified product of sums, cover the $0$ cells of the map. The $0$ cells can be covered by a total of three blocks: $\neg p \land \neg q$, $\neg s$ and $r$.

To get the product of sums, the literals (= inverted or non-inverted input variables) of the blocks have to be inverted:

$$G(p,q,r,s) = (p \lor q) \land (\neg r) \land s$$

The reasoning behind the inverted literals is that all literals in a sum have to be false to get a false sum.