Logical equivalence proofs

Trying to master logical equivalence proofs out of a textbook is proving to be difficult. I’m hung up on these four problems. I can make some progress, but usually get stuck towards the very end. Any solutions and breakdowns for these four, using laws of logic?

1. ~~D & ~(~D&B) and D v (D & ~B)
2. F & ~I and ~(I v ~F)
3. (P & ~~Q) & M and (Q & Q) & (P & M)
4. ((A & (B ∨ ~~C)) ∨ D) & (E ∨ ~~~E) and (A & (B ∨ C)) ∨ D
• What equivalences ? 2.F & ~I and ~(I v ~G) are obviously not equivalent. Can you provide more detail, please ? – Mauro ALLEGRANZA Mar 18 at 16:07
• My apologies, I entered it incorrectly. It’s fixed now. – A. Delarge Mar 18 at 16:11
• For 2, use De Morgan's laws. – Mauro ALLEGRANZA Mar 18 at 16:22
• 3 is trivial : Q & Q is equiv to Q. Use Idempotent laws. – Mauro ALLEGRANZA Mar 18 at 16:24
• "laws of logic" is a little vague. Which rules are you allowed to use for these exercises? – Eliran Mar 18 at 17:47

Here's a solution to #1 using only 4 rules of equivalence: Double Negation (DN), Demorgan's Laws (DM), Distribution (Dist), and Tautology (Taut). I have answered it as if it were a derivation, but it is easy to turn it into a proof of a logical truth. Just make the conclusion the consequent of the given, then assume the given (ACP) and derive the conclusion in the manner I have outlined below. 2, 3, and 4 can all be answered using these rules + Association (Assoc). Learning from a textbook without use of a truth table generator and natural deduction proof checker can lead to errors.

I will do the first one as an example.

If the answer isn't obvious, I would place it in a truth table generator to see if it is an equivalence. In this case it wasn't obvious to me so I entered the following into a truth table generator and found that indeed it was a logical equivalence. At this point I could stop because I have shown the logical equivalence, but your question asks for a derivation and not a truth table. Here is one proof: See the proof checker and the forallx text for details of how the proof checker works and the rules it permits one to use.

This provides a second way to get that first result, but you may be asked to use different rules and format them differently. However, you should be able to use the resources below to make those changes.

The other three problems can be approached similarly and I will leave them for you to explore.

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Winter 2018. http://forallx.openlogicproject.org/

Michael Rieppel. Truth Table Generator. https://mrieppel.net/prog/truthtable.html