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$
1

2 Answers 2

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$
3
  • 1
    $\begingroup$ I just saw your edit. I think you're thinking along the right lines. $\endgroup$
    – amWhy
    Feb 14, 2014 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, 2014 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$ Feb 14, 2014 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$

You must log in to answer this question.

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