• Support PF! Buy your school textbooks, materials and every day products Here!

Boolean Algebra, Minimum Sum of Products Problem

  • Thread starter s3a
  • Start date
  • #1
s3a
799
8
Hello to everyone who's reading this.

The problem I need help with is the following.:

Homework Statement


"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
*2*********8,12****12,13**10,11**10,11***5,13
...*******************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.):
https://www.docdroid.net/PacYXo3/1a-main-solution-and-alternate-solution.pdf

Homework 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

Source:
https://www.electronics-tutorials.ws/boolean/bool_6.html

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):

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

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

3)
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):
4)
How does one go from (C’D’ + BC’ + B’C)A to A(CC’+B’C)?

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

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


Any input would be greatly appreciated!
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,792
1,390
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.
 
  • #3
56
10
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:
  • #4
56
10
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:
  • #5
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,580
1,196
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:
  • #6
56
10
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'.
I missed the missing D prime. Thanks for correcting my mistake.
 

Related Threads on Boolean Algebra, Minimum Sum of Products Problem

Replies
2
Views
5K
  • Last Post
Replies
3
Views
701
  • Last Post
Replies
3
Views
13K
  • Last Post
Replies
3
Views
1K
Replies
2
Views
36K
Replies
4
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
1
Views
3K
Top