0
$\begingroup$

I've tried numerous ways at solving this problem but am stuck. I believe I need to use logical equivalences involving conditionals, De Morgan's law, associative law and distribution (I've used them below however most likely incorrectly). Here is the question and a way I've tried solving it. I need to do this without the use of truth tables by the way. To be clear I'm trying to find out if the beginning statement is a tautology, contradiction, or contingency. Thanks all!

((p v q) ∧ (¬q v ¬r)) → (r → p) ≡

¬((p v q) ∧ (¬q v ¬r)) ∨ (r → p) ≡

¬((p v q) ∧ (¬q v ¬r)) ∨ (¬r v p) ≡

¬((p v q) ∧ (¬q v ¬r)) ∨ ¬(r ∧ ¬p) ≡

¬(((p v q) ∧ (¬q v ¬r)) ∨ (r ∧ ¬p)) ≡

¬((p v q) ∧ ((¬q v ¬r)) ∨ (r ∧ ¬p))) ≡

And I seem to get stuck in here when trying to use the distributive property to perhaps evaluate one of these statements to true/false.

$\endgroup$
  • 2
    $\begingroup$ Aren't truth-tables a nice tool for this? $\endgroup$ – drhab Sep 4 '18 at 11:19
  • $\begingroup$ After the 3rd line, you have to "move inside" the leftmost negation sign using De Morgan. $\endgroup$ – Mauro ALLEGRANZA Sep 4 '18 at 11:21
  • $\begingroup$ @drhab Yes, but I need to know how to do this using logical equivalences as well. $\endgroup$ – John Johnson Sep 4 '18 at 11:25
  • 2
    $\begingroup$ A second possibility is to rewrite it as : $[(\lnot q \to p) \land (r \to \lnot q)] \to (r \to p)$ and use the fact that Hypothetical Syllogism is a tautology. $\endgroup$ – Mauro ALLEGRANZA Sep 4 '18 at 11:26
  • 1
    $\begingroup$ @MauroALLEGRANZA I based my answer on your first comment and didn't read your second one before posting, but it is way more straightforward. I think you should turn it into an answer. $\endgroup$ – F.Carette Sep 4 '18 at 12:30
2
$\begingroup$

As @Mauro ALLEGRANZA told in the comments, you should go back to your third line.

$$\begin{align}\color{red}{¬}((p \lor q) \land (¬q \lor ¬r)) \lor (¬r \lor p) \\ \end{align}$$

From there, we'll use De Morgan rule on the first $\lnot$

$$\begin{align}\color{red}{¬}((p \lor q) \land (¬q \lor ¬r)) \lor (¬r \lor p)\\ & \Leftrightarrow \lnot(p\lor q)\lor\lnot(\lnot q \land \lnot r) \lor (\lnot r \lor p) \\ &\Leftrightarrow (\lnot p \land \lnot q) \lor (q\lor r)\lor (\lnot r \lor p) \\ &\Leftrightarrow (\lnot p \land \lnot q) \lor q \lor \color{red}{r \lor \lnot r} \lor p \\ & \Leftrightarrow (\lnot p \land \lnot q) \lor q \lor \color{red}1 \lor p \\ & \Leftrightarrow 1 \end{align}$$

The equation seems to show that you have a tautologie.

Let's verify it with a truth table.

(The table was too big to enter the page, so I had to introduce (A) and (B), I hope the notation is consistent)

$$\begin{array}{|c|c|c|} \hline p & q & r & (A)=p\lor q & (B)=\lnot q \lor \lnot r & (A) \land (B) & r \implies p & (A) \land (B) \implies (r \implies p) \\\hline 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\\hline 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1\\\hline 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\\hline 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1\\\hline 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\\hline 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1\\\hline 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\\hline 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1\\\hline \end{array}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.