Logical equivalence proofs

Question

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?

~~D & ~(~D&B) and D v (D & ~B)
F & ~I and ~(I v ~F)
(P & ~~Q) & M and (Q & Q) & (P & M)
((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 '19 at 16:07
3 is trivial : Q & Q is equiv to Q. Use Idempotent laws. — Mauro ALLEGRANZA, Mar 18 '19 at 16:24
For 4, use Negation : (E ∨ ~~~E) is equiv to TRUE and by Identity ((A & (B ∨ ~~C)) ∨ D) & (TRUE) is equiv to ((A & (B ∨ ~~C)) ∨ D). — Mauro ALLEGRANZA, Mar 18 '19 at 16:26
For 1, the same as 2: use De Morgan. In all cases, you have to use heavily Double Negation : ~~A = A. — Mauro ALLEGRANZA, Mar 18 '19 at 17:13
"laws of logic" is a little vague. Which rules are you allowed to use for these exercises? — E..., Mar 18 '19 at 17:47
I really wish highschool textbooks would stop presenting the author's favorite set of rules as "THE Laws of Logic™" — Graham Kemp, Mar 19 '19 at 22:35

score 1 · Answer 1 · answered Mar 19 '19 at 22:57

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

Frank Hubeny · Answer 2 · 2019-05-26T22:49:03.417

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

Logical equivalence proofs

2 Answers2