Problem: Prove $p \rightarrow (q \vee r), \neg q, \neg r \vdash \neg p$ using Modus Tollens.

I need to prove the validity of the above sequent by using natural deduction. Initially, I didn't read the entire problem, and went the long way by doing an implication-elimination, two negation-eliminations, an or-elimination, and finally a negation-introduction. Then I read the problem and realized I had to use MT, and now I'm stuck. I don't have the greatest grasp on propositional logic and natural deduction. Am I allowed to do the following?

Since I have $\neg q$ and $\neg r$ as my premises, can I use an and-introduction and do $\neg q \wedge \neg r$, which would allow me to immediately use MT to deduce $\neg p$? If not, could someone point me in the correct direction? Thanks.


Modus Tollens is the following rule:

Given $A \to B$ and $\lnot B$, deduce $\lnot A$.

In your case, you are given $p \to (q \lor r)$, and so $A = p$ and $B = q \lor r$. Therefore you need to prove $\lnot B = \lnot (q \lor r)$. This is not the same as $\lnot q \land \lnot r$, though the two are logically equivalent. What you have to do is deduce $\lnot (q \lor r)$ from the premises $\lnot q$ and $\lnot r$.


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.