# Proof without using truth tables

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.

• Truth tables are completely valid. If you use a deductive system, it will ultimately just be an encoding of truth tables anyway. Also your answer to the question is correct. Also there is no such thing as "the laws of logic". Feb 20, 2021 at 6:52
• "Hint – analyze the possible values of P, Q, and R that make each of the statements false". This is basically using a truth table! Feb 20, 2021 at 6:59
• That's what I thought, I think it's just the wording of "without showing truth tables" that had me thinking I had to somehow prove these in another way.
– Emm
Feb 20, 2021 at 7:05

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

• So I was able to use the contrapositive identity, associative, de morgan's, commutative and distributive laws to show the equivalency, your hint really helped. I just wanted to get a bit more clarification on one more thing, when I write this proof, I can just show the use of the laws to prove equivalency, and that's all I need in the actual proof part, correct? But when I have to defend my proof (it's an oral presentation), I can respond to questions of validity by stating I verified the equivalencies by using truth tables?
– Emm
Feb 20, 2021 at 9:31
• In my opinion, the method you describe is completely valid on its own, and a separate method using truth tables would also be completely valid on its own. If people want to hear both perspectives, that's fine I guess, but there's no mathematical necessity to include both. Feb 20, 2021 at 22:48

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)