Propositional Logic with rules of inference problem.

Question

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

Answer 1

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.

Answer 2

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