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 \lor q) \land (\lnot q \lor \lnot r)) \to (r \to p) \equiv$

$\lnot((p \lor q) \land (\lnot q \lor \lnot r)) \lor (r \to p) \equiv$

$\lnot((p \lor q) \land (\lnot q \lor \lnot r)) \lor (\lnot r \lor p) \equiv$

$\lnot((p \lor q) \land (\lnot q \lor \lnot r)) \lor\lnot ( r \land \lnot p) \equiv$

$\lnot(((p \lor q) \land (\lnot q \lor \lnot r)) \lor ( r \land \lnot p) )\equiv$

$\lnot((p \lor q) \land ((\lnot q \lor \lnot r)) \lor ( r \land \lnot p) ))\equiv$


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$
5
  • 2
    $\begingroup$ Aren't truth-tables a nice tool for this? $\endgroup$
    – drhab
    Commented Sep 4, 2018 at 11:19
  • $\begingroup$ After the 3rd line, you have to "move inside" the leftmost negation sign using De Morgan. $\endgroup$ Commented Sep 4, 2018 at 11:21
  • $\begingroup$ @drhab Yes, but I need to know how to do this using logical equivalences as well. $\endgroup$ Commented Sep 4, 2018 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$ Commented Sep 4, 2018 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
    Commented Sep 4, 2018 at 12:30

1 Answer 1

3
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .