1
$\begingroup$

$$ \begin{array}{l} 1.\>\>\>\> (r ∧ ¬s) ∨ (q ∧ ¬s)\\ 2.\>\>\>\> ¬s → ((p ∧ r) → u)\\ 3.\>\>\>\> u → (s ∧ ¬t)\\ \dfrac{\quad\qquad\qquad\qquad\qquad\qquad}{\text{Prove from the previous arguments. }\quad p → q} \end{array} $$

Hey guys, I am really lost, so far I have a few arguments but not sure if they're correct. Can you please give some arguments to get this solved or a game plan using Inference laws and equivalences. Inferences: Modus Ponens, Tollens, Hypothetical, Disjunctive, Resolution, Conjunction, Simplification, Addition.

This is what I have so far.... 4. (r ∨ q) ∧ ¬s Distributive of 1 5. ¬s Simplification of 1 6. (p ∧ r) → u Modus Ponens of 2 7. ¬u Modus Tollens of 3 8. ¬(p ∧ r) Modus tollens 9. p → ¬r DeMorgans and Implication Definition\ 10. (r ∨ q) Simplification 11. ( ¬r → q) Implication 12. p → q Hypothetical

Are these steps valid?

$\endgroup$
3
$\begingroup$

I'll give a summary "sketch" of one proof approach.

I'd suggest you start from the first premise:

First check what follows from $r\land \lnot s$ and then what follows when $q \land \lnot s$. (At least one of these must be true. Why?)

From each of the above, we can use conjunction elimination (or simplification) to obtain $\lnot s$. And so, we can use disjunction elimination to conclude $\lnot s$.

From $\lnot s$ and premise $(2)$, we can derive (infer), by modus ponens, $(p\land r)\rightarrow u$.

From $(p \land r) \rightarrow u$ together with premise $(3)$, we get $(p\land r) \rightarrow (s \land \lnot t)$

Now, we already derived $\lnot s.$ This means $\lnot s \lor t$ is true. Why?

But $\lnot s \lor t \equiv \lnot (s \land \lnot t).$

From $\lnot (s \land \lnot t),$ together with our derived $(p\land r )\rightarrow (s\land \lnot t)$, by modus ponens, we get $\not(p \land r)$

This means that either $\lnot p$, or $\lnot r$ is true.

If $\lnot p$ is true, we can build from this (addition) to get $\lnot p \lor q \equiv p\rightarrow q$, as desired.

If $\lnot r$ is true, then $r\land \lnot s$ is false (first alternative from premise $(1)$. Then it must follow that $q\land \lnot s$ is true. So it follows that $q$ is true (simplification). And given $q$, we have $\lnot p \lor q$ (addition), which is equivalent to $p \rightarrow q$, as desired.

Therefore, from $\lnot (p \land r)\equiv \lnot p \lor \lnot r$ we can conclude $(q\rightarrow q)$.

I'll leave this to you to write formally (including keeping proper track of temporary assumptions), with proper justifications.

$\endgroup$
  • 1
    $\begingroup$ I just saw your edit. I think you're thinking along the right lines. $\endgroup$ – Namaste Feb 14 '14 at 14:43
  • $\begingroup$ Thank you, can you please clarify the following if you have a chance: Now, we already derived ¬s. This means ¬s∨t is true. Why? But ¬s∨t≡¬(s∧¬t). $\endgroup$ – DrJonesYu Feb 14 '14 at 14:44
  • $\begingroup$ Becuase if $\lnot s$ is true, $\lnot s \lor$ ... "something else" is certainly true (truth-table for $\lor$); so, we use as "something else" $t$. $\endgroup$ – Mauro ALLEGRANZA Feb 14 '14 at 18:06
1
$\begingroup$

Solution


  • 1: (r∧¬s)∨(q∧¬s) Premise
  • 2: ¬s→((p∧r)→u) Premise
  • 3: u→(s∧¬t) Premise
  • 4: (r∨q)∧ ¬s Distribution 1
  • 5: ¬s Simplification 4
  • 6: (p∧r)→u Modus Ponens 2, 5
  • 7: ¬s∨t Addition 5
  • 8: ¬(s∧¬t) DeMorgan 7
  • 9: ¬u Modus Tollens 3, 8
  • 10: ¬(p∧r) Modus Tollens 6, 9
  • 11: ¬p∨¬r DeMorgan 10
  • 12: p→¬r Material implication 11
  • 13: r∨q Simplification 4
  • 14: ¬r→q Material implication 13
  • 15: p→q Hypothetical silogism 12, 14
$\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.