Proof without using truth tables

Question

I need some further explanation, as I feel I am just missing some critical piece of information. I have shown my work thus far (I excluded the truth tables as they take up so much space but included the pertinent values). Can someone shed some light on what I'm overlooking here?

Which of the following formulas are equivalent? Without showing truth tables, explain why which of the following five statements are equivalent. Hint – analyze the possible values of P, Q, and R that make each of the statements false.

a. P → (Q → R).

b. Q → (P → R).

c. (P → Q) ∧ (P → R).

d. (P ∧ Q) → R.

e. P → (Q ∧ R).

My work:

So using truth tables I was able to determine that a,b,d are all equivalent to each other AND c and e are equivalent to each other. A, B, D are all false ONLY when p and q are true and r is false, as that is the only time that the conditional statement becomes true implies false. C and E are false for several instances, when p=T q=T r=F; p=T q=F r=T; p=T q=F r=F.

What has me stumped is how to write a proof from that information. I have tried using the logical equivalence identities, but am unable to  come up with the correct answer, so I feel like that is not the proper way to do it. So I'm wondering, is there somethin I'm missing? Is this supposed to be a proof by implication, or and indirect proof, and if so, how am I supposed to start that? I understand that these are conditional statements, but again, I feel as if I am missing something.

Answer 1

(a), (b), and (d) can be proven equivalent by using (five times in total) the fact that $A\implies B$ is equivalent to $(\lnot A)\lor B$, together with de Morgan's law for negating an "and" statement and the associativity and commutativity of "or" statements.

Similarly, (c) and (e) can be proven equivalent by using that $A\implies B$ is equivalent to $(\lnot A)\lor B$ together with the distributive laws for "and"s and "or"s.

(I agree that the given hint is basically the same as using truth tables.)

Answer 2

If you are not allowed to use truth-tables to prove equivalence (even though that's a perfectly acceptable method), but you also don't want to rely on laws like DeMorgan, you could do something like this:

Since any conditional $P \to Q$ is False if and only if $P$ is True and $Q$ is False, we have:

$P \to (Q \to R)$ is False iff

$P$ is True and $Q \to R$ is False iff

$P$ is True and $Q$ is True and $R$ is False iff

$Q$ is True and $P$ is True and $R$ is False iff

$Q$ is True and $P \to R$ is False iff

$Q \to (P \to R)$ is False

... which of course also means that $P \to (Q \to R)$ is True iff $Q \to (P \to R)$ is True ... and hence a) and b) are equivalent

You should be able to do something similar for the other equivalences. Indeed, note how the equivalence of d) to these two statements can be established right after the third line from the above demonstration (which is called a proof by semantics by the way: a proof that simply applies the basic truth-conditions of the operators involved)

Good luck with your presentation!

Answer 3

(Posted after a previous answer was accepted)

Using a form natural deduction, we can prove as follows:

Similarly, we can prove:

Then, we have the required logical equivalence: