Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Boolean Algebra, Minimum Sum of Products Problem

  1. May 17, 2018 #1


    User Avatar

    Hello to everyone who's reading this.

    The problem I need help with is the following.:
    1. The problem statement, all variables and given/known data
    "Simplify to obtain minimum SOP.
    F(A, B, C, D) = A’B’CD’+AC’D’+ABC’+AB’C+AB’C+BC’D"

    The problem stated above has two provided solutions, the "main" one and the "alternate" one.

    I'm confused with both of them.

    Here they are (within this post directly and indirectly within a PDF, since some people prefer it directly here, but I think it looks better in the pdf).:
    "Main" solution:

    ("*"s are used for preserving formatting)

    A’B’CD’ + AC’D’ + ABC’ + AB’C + AB’C + BC’D
    ...*******************ABC'(D+D')*************ABC' is deleted (There is an arrow going from AC'D' on the line above to the left whitespace of ABC'(D+D'), on this line. There is also another arrow going from BC'D to ABC'(D+D') (from the left - not that I think that the direction from which it's coming matters).)
    2 & 10,11**A'B'CD' + AB'C = B'C(A+A'D)
    Final result: B'CD' + AC'D' + AB'C + BC'D

    "Alternate" solution:
    = A’B’CD’ + AC’D’ + ABC’ +AB’C + AB’C + BC’D
    = A’B’CD’ + (C’D’ + BC’ + B’C)A + BC’D
    = A(CC’+B’C) + BC’D + A’B’CD’
    = AC’D’ +A’B’CD’ +AB’C +BC’D
    = AC’D’ + B’CD’+AB’C + BC’D

    PDF version of "main" and "alternate" solutions (The problem is problem 1a.):

    2. Relevant equations
    A + 1 = 1 Annulment
    A + 0 = A Identity
    A + 0 = A Identity
    A ⋅ 1 = A Identity
    A ⋅ 0 = 0 Annulment
    A + A = A Idempotent
    A ⋅ A = A Idempotent
    (A')' Double Negation
    A + A' = 1 Complement
    A ⋅ A' = 0 Complement
    A+B = B+A Commutative
    A⋅B = B⋅A Commutative
    (A+B)' = A' ⋅ B' de Morgan’s Theorem
    (A⋅B)' = A' + B' de Morgan’s Theorem


    3. The attempt at a solution
    When I tried to follow the logic of the solutions, I encountered some problems.

    Here they are.:
    For the main solution of Q1 a):

    What are the numbers 2, 8, 12, 12, 13, 10,11, 10,11, 5, 13?

    What is meant by ABC’ is deleted? Is what is meant (D + D’) is “deleted”?

    What is done on the before-last linute to get to the last line / line with text “Final Result:”?

    For the alternate solution of Q1 a):
    How does one go from (C’D’ + BC’ + B’C)A to A(CC’+B’C)?

    How does one go from A(CC’+B’C) to AC’D’ +AB’C?

    How does the A’B’CD’ become B’CD’ from the before-last line to the last line?

    Any input would be greatly appreciated!
  2. jcsd
  3. May 18, 2018 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I can help a bit, but not much I'm afraid!

    The numbers are the binary encodings of the terms, as explained here.
    So for instance to get the binary encoding for the term AC'D' we first put all the variables in it, by writing it as (ABC'D' + AB'C'D') and then write those with a 1 for an unprimed variable and a 0 for a primed one, to get (1100 + 1000). Then we interpret those as binary numbers to get 12 (=##1\cdot 2^3+1\cdot2^2+0\cdot 2^1+0\cdot 2^0##) and 8 (=##1\cdot 2^3+0\cdot2^2+0\cdot 2^1+0\cdot 2^0##), which are the two numbers written below the term AC'D'. The same is done for all the other terms. The numbers are called 'minterm indices'

    The expression is then an OR (+) of all the terms with their numeric representations. Repeated terms can be ignored by Idempotence of OR ('+'). So the expression is ##m_2+m_5+m_8+m_{10}+m_{11}+m_{12}+m_{13}## where I have used the standard convention of writing ##m_k## to denote the boolean term whose minterm index is ##k## (in the problem, and in the previous para, just the bare numeral ##k## was used).

    I think the statement "ABC' is deleted" may be a typo that should read "AB'C is deleted". That would make sense because AB'C appears twice so the expression does not change if we remove one of them (by Idempotence of '+').

    However, I still can't follow the reasoning of either the presented solution or the alternate.

    The above minterm form has seven terms and the solution has four terms, Some further manipulation is needed to get the seven down to four, and I'm afraid I can't see an obvious way to do that right now.
  4. May 18, 2018 #3
    It's been awhile, so take these suggestions for what they're worth....

    Starting with the alternate solution:
    I'm pretty sure the answer to your question #4 is that the final term should actually be C'D'; not CC'. I think this for two reasons:

    1) If it were CC' as it is presently shown, then the result would equal zero--using the second equation (theorem) shown for "complement". Since the steps that follow do not indicate a zero, I think it is indeed a typo.

    2) Also, if you put in C'D' instead, then the steps that follow it make sense. [Note that some of the lines that are shown tend to be confusing--because the writer often changes the order from line to line, in addition to the simplifications.] I think this also answers your questions #5 and #6.
    Last edited: May 18, 2018
  5. May 18, 2018 #4
    Regarding the main posted solution for question 1a:

    1.) For your question #2, I believe the ABC' is removed because it is redundant. There is probably an easier/better way to convince yourself of this, but if you create a truth table (for the 3 terms the writer identifies in the solution), it seems that the ABC' term is redundant to the other two (AC'D' and BC'D), and is thus unnecessary.

    As to the reference to (D + D'), if you look at the final line you see those letters actually are not deleted. (Although as shown, that combination does represent the first complement equation--that results in a "1.") I'm not sure how/why the writer pulled that part out there. There's undoubtedly some equation/simplification that I am missing.

    2.) For your question #3: the writer doesn't explicitly show it, but he/she is adding the the simplification shown on the right side of the next to the last line, i.e. " B'C(A+A'D)", to the remaining terms from above (that is, the AC'D' and BC'D). Then, if you compare those last two lines in the problem, you'll note the minor* difference between them. I think there's a version of an "absorption" equation/theorem/law not shown in the list you posted that explains it, but again... if you do a truth table comparing the before and after... you'll see the results are identical.​

    * [Note, again, the writer does a switch up on the order of the terms, which repeatedly makes keeping track of the terms a little tricky.]
    Last edited: May 18, 2018
  6. May 19, 2018 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    The AC'D' term corresponds to 8 and 12, which means it's true when ABCD=1000 or ABCD=1100. Similarly, the BC'D term corresponds to 5 and 13, so it's true when ABCD=0101 or ABCD=1101.

    The ABC' term corresponds to 12 and 13, so it's true when ABCD=1100, which means AC'D' is also true, or when ABCD=1101, which means BC'D is also true. So the ABC' term turns out to be redundant.

    I think the notation in the solution means that the 12 from AC'D' and 13 from BC'D combine to form ABC', so that term can be deleted.

    The next line in the solution is the combining of the A'B'CD' and AB'C terms.There's a typo as a prime on D inside the parentheses is missing. It should say A'B'CD' + AB'C = B'C (A'D' + A) = B'C (D' + A) = AB'C + B'CD'.
    Last edited: May 19, 2018
  7. May 19, 2018 #6
    I missed the missing D prime. Thanks for correcting my mistake.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?