How to prove premise-conclusion statements with rules of inference? I have a question here:


*For each of the premise-conclusion pairs below, give a valid step-by-step argument (proof)
along with the name of the inference rule used in each step. For examples, see pages 73
and 74 in textbook.


First question:
(a) Premise: {¬p ∨ q → r, s ∨ ¬q, ¬t, p → t, ¬p ∧ r → ¬s}, conclusion: ¬q.
I only got this far:
¬p v ¬q v r 
I have absolutely no idea what to do next. If someone could give me some general tips to solve this problem and others like it it would be great. I know, i only did one step..
Help is very much appreciated
 A: Starting from the simplest atoms and working down:


*

*The simplset atom is $\neg t$. What does that give me? Where does $t$ appear? Oh look! From $\neg t$ and $p\implies t$, you have $\neg p$

*Ok, now I have $\neg p$ as well as $\neg t$. Where does $p$ appear? Oh! From $\neg p \lor q\to r$, I now have $r$, since $\neg p\lor q$ is true!.

*Now, where do $p$ and $r$ appear? Oh, in the last premise! $\neg p \land r\to \neg s$ gives me $\neg s$, since I know $\neg p\land r$ is true!


Starting from the conclusion and working up:


*

*Where does $s$ appear as a conclusion? Ok, it appears either in $s\lor \neg q$ or it appears in $\neg p \land r\to \neg s$. Well, my intuition tells me that the second one looks more promising, since I don's see how I could disprove $\neg q$.

*So, how can I prove $\neg p \land r$? Well, I need to prove both $r$ and $\neg p$. Let's start with $r$ first.


*

*I can prove $r$ if I prove $\neg p \lor q$, since $\neg p \lor q \to r$. Oh, but I have to prove $\neg p$ anyway, so as long as I can prove $\neg p$, I'm done!

*There is no $\neg p$ anywhere to prove. Is this a problem? Well, no, since $p\to t$ is the same as $\neg t\to \neg p$. OK, so I only need to prove $\neg t$. How can I prove that? Oh! I don't have to ! It's an axiom! Well, job done.


