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


1 Answer 1


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.
  • $\begingroup$ 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$ $\endgroup$
    – Andrew Kor
    Oct 12, 2015 at 18:30
  • $\begingroup$ @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. $\endgroup$
    – 5xum
    Oct 12, 2015 at 18:32
  • $\begingroup$ @AjeetKljh If $A\to B$ is true and $A$ is true, then $B$ is true. This rule of inference is called modus ponens. $\endgroup$
    – 5xum
    Oct 12, 2015 at 18:40
  • $\begingroup$ In my book it says modus tollens is $\neg$$q$ | $p$$\rightarrow$$q$ | therefore $\neg$$p$. That implies $\neg$$p$ is true? $\endgroup$
    – Andrew Kor
    Oct 12, 2015 at 18:45
  • $\begingroup$ 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. $\endgroup$
    – 5xum
    Oct 12, 2015 at 18:49

You must log in to answer this question.

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