# $p\land\neg q\to r, \neg r, p ⊢ q$ -natural deduction

I have the following:

$$p\land\neg q\to r, \neg r, p ⊢ q$$

I know that my attempt is incorrect, but I will show it anyways:

Step 1) $$p\land\neg q\to r$$ ----premise

Step 2) $$\neg r$$ -----premise

Step 3) $$p$$ -----premise

Step 4) $$\neg q\to r$$ ---- e1

Step 5) $$\neg \neg q$$ ----MT4,2

Can someone show me the proper steps? I do not think I can use MT in the way shown above, but I cannot find out how to get to q.

OP's remark from a comment: "I was curious, is there a way to bypass DeMorgan's law?"

• In Step 4) you are reading the premise : $p∧¬q→r$ as $p∧(¬q→r)$; if you think that MT is not available, after Step 4) you have to (temporary) assume $\lnot q$ and derive : $r$. With the premise $\lnot r$ you have a contradiction and you can "blame" the assumption $\lnot q$ in order to derive (by Double Negation) : $q$. If instead you read the premise $p∧¬q→r$ as $(p∧¬q)→r$, the proof is different (see answers below) : from premise $p$ and (temporary) assumption $\lnot q$ derive $p \land \lnot q$ by $\land$-intro and then derive $r$ which gives you a contradiction with $\lnot r$. – Mauro ALLEGRANZA Feb 9 '15 at 11:03

Something like this?

$$\begin{split} p\wedge\neg q \to r , \neg r &\vdash \neg (p\wedge \neg q)&\quad&\textsf{Premise 1,Premise 2, Modus Tollens} \\ \neg (p\wedge \neg q)&\vdash \neg p\vee q &&1,\textsf{de Morgan's} \\ \neg p\vee q, p &\vdash q&&2,\textsf{Premise 3},\textsf{Disjunctive Syllogism} \\\hline p∧¬q→r,¬r,p &⊢q \end{split}$$

Avoiding de Morgan's

$$\begin{split} (p\wedge \neg q)\to r, p, \lnot q&\vdash r &\quad&\textsf{Premise 1,Premise 3, Assumption of q, Modus Tolens} \\ r, \lnot r &\vdash \bot&&1,\textsf{Premise 2},\textsf{Negation Elimination}\\\hline(p\wedge\neg q)\to r,\lnot r,p,\lnot q&\vdash \bot&&\textsf{Cut}\\\hline (p\wedge\neg q)\to r,\lnot r,p&\vdash \lnot\lnot q&&\textsf{Negation Introduction (discharges the assumtion)}\\\hline (p\wedge\neg q)\to r,\lnot r,p& \vdash q &&\textsf{Double Negation Elimination}\end{split}$$

• this is really good, but I was curious, is there a way to bypass DeMorgan's law? – Bolboa Feb 9 '15 at 20:39

$$p\land\neg q\to r \iff \neg(p\land\neg q) \vee r \iff (\neg p \vee q \vee r)$$ (ref)

Since $\neg r$ and $p$ are in the premise, $q$ follows.

• I think the question asked for natural deduction steps to prove the result: Can someone show me the proper steps? Because of that I don't think this is an answer. – Frank Hubeny Feb 21 '19 at 18:19

$$¬r \Rightarrow ¬(p \land ¬q) \mbox{ by modus tollens}$$

$$¬(p \land ¬q) \iff ¬p \lor ¬¬q \iff ¬p \lor q$$

$$( ¬p \lor q) \land p \Rightarrow q \mbox{ by definition of the disjunction operator.}$$

$$\therefore p\land\neg q\to r, \neg r, p ⊢ q$$

• I don't think this answer shows the natural deduction steps asked for in the question. – Frank Hubeny Feb 21 '19 at 18:21

The following proof uses neither modus tollens nor De Morgan's law.

It, however, uses the precedence of logical operators where the conjunction operator (∧) has higher precedence over the conditional operator (→). That is, $$p∧¬q→r$$ is the same as $$(p∧¬q)→r$$.

Given the above, here is a proof:

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

"Operator Precedence" Introduction to Logic http://intrologic.stanford.edu/glossary/operator_precedence.html