0
$\begingroup$

Here's my problem: I understand how to create the sum of products (SOP) and product of sums (POS) forms of boolean functions, but I don't understand why we do it the way we do it. And I haven't found an answer anywhere online. Literally every source I've read simply tells you how to form these expressions but never explains the intuition.

Example: Suppose we have a truth table for some boolean function $F$.

enter image description here

The rules for forming a sum-of-products (SOP) expression say to:

  • look at only the rows where $F = 1$
  • create product terms out of $A$, $B$, and $C$, inverting any of these three variables that are $0$ and leaving the remaining variables that equal $1$ as they are
  • sum all the product terms

So I would do:

$F = A'BC + AB'C+ABC'$

For the three rows where $F = 1$.

Question: why exactly do I ignore rows where $F=0$, and why do I invert any variables that are $0$?

$\endgroup$
2
$\begingroup$

Remember that the goal is to find an expression for which $F=1$ (or, in terms of logic, for which the function is 'True').

So immediately, that's why it ignores the rows where $F=0$; we are only interested in those rows where $F=1$, which is rows3, 5, and 6

So, we are going to 'capture' $F=1$ by saying that we are dealing with row 3, or row 5, or row 6. Since the $+$ captures the logical 'or', we thus get as our basic form:

$$F = row_3 + row_5 + row_6$$

where we want $row_3$ to be an expression that equals to $1$ if and only if we are 'dealing' with row $3$. OK, so when are we dealing with row 3? It is when $A=0$, and $B=1$, and $C=1$. Since the logical 'and' is the 'multiplication' in boolean logic, this corresponds to $A'BC$. That is, we want the inverse of $A$ to be $1$, and $B$ to be 1, and $C$ to be 1. Likewise, we get the terms $AB'C$ and $ABC'$ for rows 5 and 6 respectively, and thus end up with:

$$F = A'BC+AB'C + ABC'$$

For another example, accompanied with some further explanation, see: Can AND, OR and NOT be used to represent any truth table?

$\endgroup$
  • $\begingroup$ If we want to capture F in its entirety, would that then be SOP + POS? That is, one long chain of ORs? $\endgroup$ – AleksandrH May 25 '18 at 19:21
  • $\begingroup$ @AleksandrH One long chain of ORs, where every or-term is a chain of AND's of literals (so, what you have now) is in SOP, and that fully captures F. $\endgroup$ – Bram28 May 25 '18 at 19:24
  • $\begingroup$ Oh, so in that case, if I'm only doing SOP, would I consider both cases, when F = 0 and F = 1? And for F = 0, would I use the reverse of the logic you used in your answer? $\endgroup$ – AleksandrH May 25 '18 at 19:31
  • $\begingroup$ @AleksandrH No, you just generate the expression for $F=1$; that will capture $F$ just by itself. But you can generate an expression by focusing just on the $0$'s ... and then you get a POS. For example, with $F$ being $0$ in row $0$, you would generate the term $A+B+C$ (yes; just the 'reverse of $A'B'C'$), and combining this for all $5$ rows where $F=0$, you thus get: $F=(A+B+C)(A+B+C')(A+B'+C)(A'+B+C)(A'+B'+C')$ $\endgroup$ – Bram28 May 25 '18 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.