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.
  • $\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 '15 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 '15 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 '15 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 '15 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 '15 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.