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'
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.
