Prove using Boolean algebra that two expressions are equivalent

In summary, The speaker suggests that the listener forgets about the canonical forms and focuses on the two minimal forms, trying to convert one into the other using only Boolean axioms. The speaker also notes that there may have been an error in the minimal POS expression and that the LHS of the statement should be F(A,B,C,D). The listener follows the suggestions and simplifies A'CD + A'D to A'D * [ C + 1 ] = A'D, showing that they can go from minimal POS to minimal SOP. The listener also asks if the reverse conversion is possible and the speaker confirms that it is. The speaker clarifies that the reverse conversion may depend on the rules used for the first direction. The speaker also mentions
  • #1
rugerts
153
11
Homework Statement
Obtain minimal product of sums expression for F. Using Boolean Algebra, show that the product of sums expression is equivalent to the sum of products expression. Ignore timing hazards.
Relevant Equations
Boolean algebra and DeMorgan's Laws.
1570929227333.png
Can anyone tell me if I'm doing this right so far? My question really is... does this mean that the next step for me is to expand the last statement shown?Asking because that seems like a lot of work.
 
Physics news on Phys.org
  • #2
The way you are going is unnecessarily long, and I don't know whether it can lead to an answer. Forget the canonical forms, which the problem does not ask you to use. Instead focus on the two minimal forms, and try and convert one into the other, using only the Boolean axioms. For me this took nine short lines, starting with the SOP.

Also, note that the LHS of the above statement of the minimal POS contains an error. There should be no prime over the F. The LHS is F(A,B,C,D), the same as for the minimal SOP.
 
  • #3
andrewkirk said:
The way you are going is unnecessarily long, and I don't know whether it can lead to an answer. Forget the canonical forms, which the problem does not ask you to use. Instead focus on the two minimal forms, and try and convert one into the other, using only the Boolean axioms. For me this took nine short lines, starting with the SOP.

Also, note that the LHS of the above statement of the minimal POS contains an error. There should be no prime over the F. The LHS is F(A,B,C,D), the same as for the minimal SOP.
THanks for the reply!
I've tried again following your suggestions and I came close to an answer but it's not quite the same expression... there's an extra term. I'm wondering if it may be that my original minimal expressions are incorrect? Could you please take a look at my work below?
1570940293333.png
Is there maybe some kind of 4 variable consensus going on for my last line?
 
  • #4
Consider the first and last terms.
Can you simplify A'CD + A'D using the Boolean axioms?
 
  • #5
andrewkirk said:
Consider the first and last terms.
Can you simplify A'CD + A'D using the Boolean axioms?
Does this simplify to: A'D * [ C + 1 ] = A'D? Since C+1 = 1. If so, I have the expression now and it looks like I've shown I can go from minimal P.O.S. to minimal S.O.P.

Is it also true I can go the other way (i.e. minimal SOP to minimal POS)? I originally tried doing this but it seemed to be more difficult.

Also, you said in the original post that you're not sure if it's possible to convert between the canonical forms... why would that be so? For me, it seems like that should be possible.

Thanks.
 
  • #6
rugerts said:
Does this simplify to: A'D * [ C + 1 ] = A'D? Since C+1 = 1.
Yes, that's right.
rugerts said:
Is it also true I can go the other way (i.e. minimal SOP to minimal POS)? I originally tried doing this but it seemed to be more difficult.
Yes, the reverse conversion is always possible. You may even be able to do it just by reversing the order of the steps in your proof for the first direction. Whether you can do it that way depends on which rules you used for the first direction. But that's the thing I'd try first.
rugerts said:
Also, you said in the original post that you're not sure if it's possible to convert between the canonical forms... why would that be so?
It will always be possible to convert between them, because they are equivalent. I just didn't examine the direction you headed above in trying to do so, to work out whether it was likely to succeed.
 
  • Like
Likes rugerts

1. How do you prove two expressions are equivalent using Boolean algebra?

To prove two expressions are equivalent using Boolean algebra, you can use a series of logical equivalences and algebraic manipulations to show that both expressions have the same truth values for all possible combinations of inputs. This is known as the "double arrow" method, where you show that the two expressions are logically equivalent by showing that each one implies the other.

2. What are the basic laws and rules of Boolean algebra?

The basic laws and rules of Boolean algebra include the commutative law, associative law, distributive law, identity law, complement law, and absorption law. These laws and rules govern how logical operations are performed on Boolean variables and expressions.

3. Can you give an example of proving two expressions are equivalent using Boolean algebra?

Yes, for example, to prove that (A + B)(A + C) is equivalent to A + BC, we can use the distributive law to expand the first expression to A(A + C) + B(A + C). Then, we can use the distributive law again to expand the first term to AA + AC, and the second term to BA + BC. Finally, we can use the commutative law to rearrange the terms to A + AC + BA + BC, and then the associative law to group the A terms and B terms together to get A + (AC + BA) + BC. Using the complement law, we can simplify AC + BA to 0, and then the identity law to simplify A + 0 to A. This leaves us with A + 0 + BC, which simplifies to A + BC, thus proving the two expressions are equivalent.

4. What are some common mistakes to avoid when proving equivalence using Boolean algebra?

Some common mistakes to avoid when proving equivalence using Boolean algebra include forgetting to use parentheses when necessary, failing to apply the correct laws and rules in the correct order, and not simplifying expressions fully. It is important to carefully follow the steps and laws of Boolean algebra to ensure a correct proof of equivalence.

5. How is proving equivalence using Boolean algebra useful in real-world applications?

Proving equivalence using Boolean algebra is essential in various fields such as computer science, electrical engineering, and mathematics. It helps to simplify complex logical expressions, design efficient digital circuits, and verify the accuracy of logical operations in computer programs. It also allows for the optimization of logical expressions and the identification of redundancies, ultimately leading to more efficient and reliable systems.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
15
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
3K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
700
  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
Back
Top