# How to prove premise-conclusion statements with rules of inference?

I have a question here:

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

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.
• Why do we need to look at $\neg$$t? doesnt p⟹t mean \neg$$p$ anyway? I'm confused on this.. Ok since $\neg$$p is true, then \neg$$p$ v $q$ has to be true. I'm with you so far. I'm getting confused when you say that you have $r$ since $TRUE$$\rightarrow$$r$ Oct 12, 2015 at 18:30
• @AjeetKljh Certainly not. For example, if $p=\text{water is wet}$, and $t=\text{the earth is round}$, then the statement $p\to t$ is true, but the statement $\neg p$ is not true.
– 5xum
Oct 12, 2015 at 18:32
• @AjeetKljh If $A\to B$ is true and $A$ is true, then $B$ is true. This rule of inference is called modus ponens.
– 5xum
Oct 12, 2015 at 18:40
• In my book it says modus tollens is $\neg$$q | p$$\rightarrow$$q | therefore \neg$$p$. That implies $\neg$$p$ is true? Oct 12, 2015 at 18:45
• Yes, you prove $\neg p$ by using modus tollens. Modus tollens says that if $A\to B$ is true and if $\neg B$ is true, then $\neg A$ is true. In your case, $p\to t$ is true and $\neg t$ is true, so $\neg p$ is also true.
– 5xum
Oct 12, 2015 at 18:49